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

Problem 1.4 Assume that x, y ∈ B. Then {x} ⊆ B and {x, y} ⊆ B, and thus {x} ∈ PB and {x, y} ∈ PB. It follows that {{x}, {x, y}} ⊆ PB, and thus {{x}, {x, y}} ∈ PPB.

Problem 1.5 We have:

1. V_{0} = ∅,

2. V_{1} = PV_{0} = {∅},

3. V_{2} = PV_{1} = {∅, {∅}},

4. V_{3} = PV_{2} = {∅, {∅}, {{∅}}, {∅, {∅}}}, etc.

If A = {{∅}} and B = {∅, {∅}, {∅, {∅}}}, then we see that A ⊆ V_{2} but A ⊈ V_{1}. Thus the rank of A is 2. Similarly, B ⊆ V_{3} but B ⊈ V_{4}, thus the rank of B is 3.

Problem 2.2 Let A = {{a}, {b}} and B = {{a, b}}, for some a ≠ b.

Problem 2.3 Let a ∈ A. Then for any x ∈ a, by definition of union, we have x ∈ ⋃ A. Thus, a ⊆ ⋃ A.

Problem 2.4 Suppose A ⊆ B. We want to show ⋃ A ⊆ ⋃ B. So take any x ∈ ⋃ A. Then, by definition of ⋃ A, there is some a ∈ A with x ∈ a. But because A ⊆ B, we also have a ∈ B, and thus x ∈ ⋃ B by definition of ⋃ B. Since x was arbitrary, this shows ⋃ A ⊆ ⋃ B.

Problem 2.5 Assume every member of A is a subset of B. We want to show that ⋃ A ⊆ B. So take any x ∈ ⋃ A. If suffices to show that x ∈ B. By definition of ⋃ A, there is some a ∈ A with x ∈ a. By assumption, a ⊆ B. It follows that x ∈ B as desired.

Problem 2.6

(a) By extensionality, it is enough to show that each element of either of these sets is also in the other.

Suppose x ∈ ⋃ PA. We must show that x ∈ A. By definition of union, there is an a ∈ PA with x ∈ a. But, by definition of the power set, a ⊆ A, and hence x ∈ A.

Conversely, take any x ∈ A. Then we have x ∈ {x} and also {x} ∈ PA. Thus, by definition of union, x ∈ ⋃ PA.

(b) To show that A ⊆ P ⋃ A, take any x ∈ A. By Problem 2.3, we have x ⊆ ⋃ A, and thus x ∈ P ⋃ A, as desired.

Equality does not in general hold: For instance, let A by any set with ∅ ∉ A. Since ∅ ∈ P ⋃ A, we have P ⋃ A ⊈ A. However, A = P ⋃ A holds if A is a powerset: if A = PB, for some B, then P ⋃ A = P ⋃ PB = PB = A, where the second equality holds by part (a), applied to B.

Problem 2.7

(a) Each of the following statements is equivalent to the next, by definition of ∩, ⊆, and P: a ∈ PA∩PB. a ∈ PA and a ∈ PB. a ⊆ A and a ⊆ B. Any x ∈ a is in A and B. Any x ∈ a is in A ∩ B. a ⊆ A ∩ B. a ∈ P(A ∩ B). So the desired equality follows by extensionality.

(b) Note that A ⊆ A ∪ B, by definition of ⊆ and ∪. By Problem 1.3, this implies PA ⊆ P(A ∪ B), and similarly one has PB ⊆ P(A∪B). Now suppose a ∈ PA∪PB. Then a ∈ PA or a ∈ PB. In either case, a ∈ P(A∪B) by the above. This shows PA ∪ PB ⊆ P(A ∪ B), as desired.

The converse inclusion does not always hold. For example, let A be the set of even numbers and B be the set of odd numbers. Then {2, 3, 4} ∈ P(A ∪ B), but {2, 3, 4} ∉ PA ∪ PB.

The equality P(A ∪ B) = PA ∪ PB holds if and only if B ⊆ A or A ⊆ B. To show the “if” part is easy enough; for the “only if” part, suppose that P(A ∪ B) = PA ∪ PB. Since A ∪ B ∈ P(A ∪ B), it follows that A ∪ B ∈ PA ∪ PB, and thus A ∪ B ∈ PA or A ∪ B ∈ PB. In the first case B ⊆ A, and in the second case A ⊆ B.

Problem 2.8 Suppose B was a set such that ∀x ({x} ∈ B). Then for any set x, one would have x ∈ {x} ∈ B, and thus x ∈ ⋃ B. Thus ⋃ B would have everything as a member, contradicting Theorem 2A.

Problem 2.9 Let a be any nonempty set, and let B = {a}. Clearly a ∈ B. We have ∅ ⊆ a, and thus ∅ ∈ Pa, but not ∅ ∈ B. Thus, Pa ⊈ B, and hence Pa ∉ PB.