Discrete Mathematics: Set Theory Question?

Question

Assume A,B,C are subsets of a universal set U, and define * as A*B=(A-B)union(B-A). Prove or disprove the following statement: A*B=B*A

I was able to show graphically that (A-B) union (B-A) do not intersect and same for (B-A)union(A-B) which are graphically equal but I couldn't prove it using procedural version of set definitions and identities. Also, I don't know how the subset C takes place in this proof.

Any help will be greatly appreciated!

Answer 1

Note that for any sets X and Y, X∪Y = Y∪X. So in particular, A*B = (A\B)∪(B\A) = (B\A)∪(A\B) = B*A. Trivial really.

The set C doesn't factor into this one at all. However, my guess is that elsewhere in the problem you are asked to prove the identity (A*B)*C = A*(B*C), in which C does appear. So I will also cover how to do that problem.

First, we wish to show (A*B)*C ⊆ A*(B*C). Let x be an arbitrary element in (A*B)*C. Then X∈((A*B)\C)∪(C\(A*B)), so either x∈(A*B)\C or x∈C\(A*B)

Case 1: x∈(A*B)\C. In this case x∈A*B and x∉C. Since x∈A*B, x∈(A\B)∪(B\A), so either x∈A\B or x∈B\A.
-- Case 1a: x∈A\B. This means that x∈A and x∉B. Also, we still know that x∉C. Since x∉B, x∉B\C and since x∉C, x∉C\B. Therefore, x∉(B\C)∪(C\B) = B*C. However, x is an element of A, so x∈A\(B*C), thus x∈(A\(B*C))∪((B*C)\A) = A*(B*C)
-- Case 1b: x∈B\A. This means that x∈B and x∉A. Also, we still know that x∉C, so x∈B\C. Therefore, x∈(B\C)∪(C\B) = B*C. Since x∉A, this means that x∈((B*C)\A), and thus x∈(A\(B*C))∪((B*C)\A) = A*(B*C). So in either case, x∈(A*B)\C ⇒ x∈A*(B*C)

Case 2: x∈C\(A*B). In this case, x∈C and x∉A*B. Now, there are two possible cases, x∈A and x∉A.
-- Case 2a: x∈A. In this case, we must have also that x∈B, for if x∉B, then x∈A\B and thus x∈(A\B)∪(B\A) = A*B, contradicting the fact that x∉(A*B). Now, since x∈B, x∉C\B, and since x∈C, x∉B\C. Therefore, x∉(B\C)∪(C\B) = B*C. But since x is an element of A, we have x∈A\(B*C), and thus x∈(A\(B*C))∪((B*C)\A) = A*(B*C)
-- Case 2a: x∉A. In this case, we must also have that x∉B, for if x∈B, then x∈B\A and thus x∈(A\B)∪(B\A) = A*B, contradicting the fact that x∉(A*B). But x is an element of C, so x∈(C\B), and thus x∈(B\C)∪(C\B) = B*C. And since x∉A, x∈(B*C)\A, and thus x∈(A\(B*C))∪((B*C)\A) = A*(B*C). So in either case, x∈A*(B*C)

Since we have considered all possible cases where x∈(A*B)*C, and in each of them x∈A*(B*C), it follows that x∈(A*B)*C ⇒ x∈A*(B*C), so (A*B)*C ⊆ A*(B*C). And this holds for any sets A, B, and C.

Now, to show that (A*B)*C = A*(B*C), we could do a proof by cases of the other direction (namely, A*(B*C) ⊆ (A*B)*C), or we could simply use the commutativity and the result already obtained. Simply put, since this proof holds for any sets A, B, and C, it would still hold if we swapped the sets A and C. So using that result and commutativity of *, we have:

A*(B*C) = A*(C*B) = (C*B)*A ⊆ C*(B*A) = (B*A)*C = (A*B)*C.

And having established that (A*B)*C ⊆ A*(B*C) and A*(B*C) ⊆ (A*B)*C, it follows that (A*B)*C = A*(B*C). Q.E.D.

Answer 2

proof seems to be trivial due to commutativity of the operation "union of sets"

A*B=(A-B)union(B-A)
= (B-A) union(A-B)
= B*A