MATH 582, INTRODUCTION TO SET THEORY, WINTER 1999 Answers to Problem Set 2

Problem 2.12 Both C − (A ∩ B) and (C − A) ∪ (C − B) correspond to the same shaded region in the following Venn diagram:

Problem 2.16 Notice that for any sets x and y, one has x ⊆ x ∪ y, and thus (x ∪ y) ∩ x = x. This formula, and its dual (x ∩ y) ∪ x = x, are called absorption laws. By absorption, the term (A ∪ B ∪ C) ∩ (A ∪ B) simplifies to A ∪ B. Also by absorption, (A ∪ (B − C)) ∩ A simplifies to A. So the whole expression simplifies to (A ∪ B) − A, which further simplifies to B − A.

Problem 2.17 There are several ways to organize this proof. I’ll show that if (a) holds then so do the other three parts, and if (a) fails then so do the other three parts.

Assume (a) holds. To prove (b), notice that an element of A − B must be in A but not in B; but being in A it has to be in B, by (a), a contradiction. So nothing is in A − B. To prove (c), observe that any element of B is in A ∪ B by definition of ∪ (this part didn’t use (a)) and any element of A ∪ B is either in A or in B, and if it’s in A then it’s also in B by (a), so it’s in B in any case. To prove (d), observe that any element of A ∩ B is in A by definition of ∩ (again, this part didn’t use (a)) and any element of A is also in B, by (a), and is therefore in A ∩ B.

Now assume that (a) fails. So there is an x ∈ A such that x ∉ B. Then x ∈ A − B, so (b) fails. x ∈ A ∪ B but x ∉ B, so (c) fails. And x ∈ A but x ∉ A ∩ B, so (d) fails.

Problem 2.19 P(A−B) is never equal to PA−PB, because one always has ∅ ∈ P(A−B), but never ∅ ∈ PA−PB.

Problem 2.20 Assume A ∪ B = A ∪ C and A ∩ B = A ∩ C. We first show that B ⊆ C. So take any x ∈ B. We will show that x ∈ C. First, we know that x ∈ A ∪ B, and thus, by the first hypothesis, x ∈ A ∪ C. If x ∈ C, we are done. Otherwise, x ∈ A, and since x ∈ B, we have x ∈ A ∩ B. But then, by the second hypothesis, x ∈ A ∩ C, and again, it follows that x ∈ C. This proves B ⊆ C. An analogous argument shows that C ⊆ B, and thus B = C by extensionality.

Problem 2.23 Suppose that B is nonempty. We want to show that A ∪ ⋂ B = ⋂{A ∪ X | X ∈ B}.

⊆: Take any x ∈ A ∪ ⋂ B. To show that x ∈ ⋂{A ∪ X | X ∈ B}, we take an arbitrary X ∈ B, and we must show that x ∈ A ∪ X. If x ∈ A, this is clear; otherwise we have x ∈ ⋂ B. Since X ∈ B, it follows that x ∈ X, and it follows that x ∈ A ∪ X as desired.

⊇: Take any x ∈ ⋂{A ∪ X | X ∈ B}. We must show that x ∈ A ∪ ⋂ B. If x ∈ A, then we are done. Otherwise, x ∉ A. By hypothesis and definition of intersection, we have x ∈ A ∪ X for all X ∈ B, but since x ∉ A, this implies x ∈ X for all X ∈ B. Hence x ∈ ⋂ B, from which the result follows.

Problem 3.1 With this definition of Kuratowski “triples”, we would have ⟨x, x, y⟩^{∗} = ⟨x, y, y⟩^{∗} = ⟨x, y, x⟩^{∗} = {{x}, {x, y}}, for all x, y.

Problem 3.2

(a) The elements of A×(B ∪C) are exactly the pairs ⟨a, x⟩ where a ∈ A, and x ∈ B or x ∈ C. These are precisely the elements of (A × B) ∪ (A × C).

(b) Suppose A × B = A × C and A ≠ ∅. Since A is non-empty, there is some a ∈ A; fix such an a. Now for any x, one has x ∈ B iff ⟨a, x⟩ ∈ A × B iff ⟨a, x⟩ ∈ A × C iff x ∈ C. Thus, B = C by extensionality.