MATH 582, INTRODUCTION TO SET THEORY, WINTER 1999

Answers to the Final Exam

Problem 1 For one implication, assume A ⊆ 𝒫B. Then by Problem 1.4, ⋃ A ⊆ ⋃ 𝒫B, and by Problem 2.6(a), ⋃ 𝒫B = B, thus ⋃ A ⊆ B. For the converse, assume ⋃ A ⊆ B. We showed in class that X ⊆ Y ⇒ 𝒫X ⊆ 𝒫Y, and thus 𝒫 ⋃ A ⊆ 𝒫B. By Problem 2.6(b), A ⊆ 𝒫 ⋃ A, and thus A ⊆ 𝒫B.

Problem 2 First suppose f is one-to-one, and let X, Y ⊆ A. We know that f[[X ∩ Y]] ⊆ f[[X]] ∩ f[[Y]] by Theorem 3K(b). For the converse inclusion, suppose z ∈ f[[X]] ∩ f[[Y]]. Then z = f(x) for some x ∈ X and z = f(y) for some y ∈ Y. But since f is one-to-one, x = y, and thus x ∈ X ∩ Y and z ∈ f[[X ∩ Y]]. It follows that f[[X ∩ Y]] = f[[X]] ∩ f[[Y]].

Conversely, suppose that for all X, Y ⊆ A, f[[X ∩ Y]] = f[[X]] ∩ f[[Y]]. To show that f is one-to-one, assume f(x) = f(y) for x ≠ y ∈ A. Let X = {x} and Y = {y}. Then f[[X]] ∩ f[[Y]] = {f(x)}, whereas f[[X ∩ Y]] = f[[∅]] = ∅, a contradiction. Thus, f is one-to-one.

Problem 3 Suppose R and R^{−1} are both well-orderings on some set S. Let α be the ordinal number of ⟨S, R⟩. If S is infinite, then α ∉ ω, hence ω ∈ − α by trichotomy, hence ω ⊆ α. Therefore α, and thus ⟨S, R⟩, has an infinite increasing chain. But this amounts to an infinite decreasing chain in ⟨S, R^{−1}⟩, contradicting the fact that R^{−1} is a well-order on S.

Problem 4 Recall that an ordinal is a transitive set of transitive sets. If A is a non-empty set of ordinals, then ⋂ A is transitive, and so are its elements. So ⋂ A is an ordinal. If B is any set of ordinals, then ⋃ B is transitive, and so are its elements, so ⋃ B is an ordinal. So the answer to the first two questions is yes. However, the set-theoretic difference of two ordinals is not usually an ordinal: For instance, 2 − 1 = {∅, {∅}} − {∅} = {{∅}}, which is not an ordinal.

Problem 5 Let 𝒜 be the set of antichains in P. We claim that 𝒜 is closed under unions of chains: Consider any chain 𝒞 ⊆ 𝒜. We must show that ⋃ 𝒞 is an antichain. So consider any x, y ∈ ⋃ 𝒞. Then x ∈ C_{1} and y ∈ C_{2} for some C_{1}, C_{2} ∈ 𝒞. Since 𝒞 is a chain, we have C_{1}, C_{2} ⊆ C_{i} for some i ∈ {1, 2}. So x, y ∈ C_{i}. But C_{i} is an antichain, and thus x ≮ y. Since x, y ∈ ⋃ 𝒞 were arbitrary, it follows that ⋃ 𝒞 is an antichain, and thus ⋃ 𝒞 ∈ 𝒜. Thus, 𝒜 is closed under unions of chains and has a maximal element by Zorn’s lemma. This element is a maximal antichain in P.

Problem 6 Recall that card ℝ = 2^{ℵ_{0}} and card ω = ℵ_{0}. Thus we have

card(^{ω}ℝ) = (2^{ℵ_{0}})^{ℵ_{0}} = 2^{ℵ_{0}·ℵ_{0}} = 2^{ℵ_{0}} = card ℝ.

Problem 7 Let S be a set of cardinals. We know that ⋃ S is an ordinal by Problem 4b. It remains to be shown that ⋃ S is a cardinal, i.e., that for all β ∈ ⋃ S, β ≉ ⋃ S. So take β ∈ ⋃ S. By definition of union, there is κ ∈ S with β ∈ κ. Because β, κ, and ⋃ S are all ordinals, we have β ⊆ κ ⊆ ⋃ S, and thus β ≼ κ ≼ ⋃ S. If β ≈ ⋃ S, then we would have β ≈ κ by the Schröder-Bernstein Theorem, but this can’t be since β ∈ κ and κ is a cardinal. It follows that β ≉ ⋃ S, as desired. Thus, ⋃ S is not equinumerous to any smaller ordinal, and hence it is a cardinal.

Problem 8 An ordinal is, by definition, a transitive set of transitive sets. We also know that ordinals are well-ordered by ∈, and thus in particular they are ∈-connected. So the left-to-right implication is trivial.

Conversely, let A be a transitive set that is ∈-connected. To show that A is an ordinal, we must show that each x ∈ A is transitive. So consider z ∈ y ∈ x. By transitivity of A, we have y ∈ A, and then z ∈ A. Since, by regularity, z ≠ x, we have x ∈ z or z ∈ x by ∈-connectedness. But x ∈ z is impossible, lest x ∈ z ∈ y ∈ x, which would contradict regularity. Therefore, the only possibility is z ∈ x. This shows that x is transitive, as desired.