Proving facts about sets

To prove two sets are equal, prove each is a subset of the other: X ⊂ Y and Y ⊂ X.

To prove X ⊂ Y, take any element x of X (not a particular number) and show, step by step, that x must also be in Y. Because x was any element, every element of X is in Y.

Example: if A ∪ B = A ∪ C and A ∩ B = A ∩ C, then B = C.

• Take the intersection of both sides of the first fact with B: B ∩ (A ∪ B) = B ∩ (A ∪ C).
• Left side: B (B is a subset of A ∪ B). Right side, by the distributive law: (B ∩ A) ∪ (B ∩ C).
• So B = (A ∩ B) ∪ (B ∩ C). Doing the same with C gives C = (A ∩ C) ∪ (B ∩ C).
• Since A ∩ B = A ∩ C, the two right sides are the same. So B = C.

Laws can also be chained, using A – B = A ∩ B′. Prove (A – B) ∪ B = A ∪ B: (A ∩ B′) ∪ B = (A ∪ B) ∩ (B′ ∪ B) = (A ∪ B) ∩ U = A ∪ B.

One counter-example is enough to show a general claim is false. Does A ∪ B = A ∪ C force B = C? No: A = {1, 2}, B = {1}, C = {2} give A ∪ B = A ∪ C = {1, 2}, but B ≠ C. (That is why the example above needed both facts.)

Sometimes you are asked to build sets with a property. Three sets that pairwise overlap but have nothing common to all three: A = {a, b}, B = {b, c}, C = {a, c}. Each pair shares one letter, but A ∩ B ∩ C = φ.

These all say the same thing, and any one can be used in place of another: A ⊂ B ⇔ A – B = φ ⇔ A ∪ B = B ⇔ A ∩ B = A.

Watch ∈ against ⊂ in proofs: from x ∈ A and A ∈ B you cannot conclude x ∈ B. With A = {1} and B = {{1}, 2}: 1 ∈ A and A ∈ B, but 1 ∉ B.