MATH 582, INTRODUCTION TO SET THEORY, WINTER 1999

Answers to Problem Set 8

Problem 7.11 (a) Let <′ be the following ordering on the integers ℤ:

0 <′ 1 <′ 2 <′ … <′ −1 <′ −2 <′ −3 <′ …

Clearly, this is a linear ordering. To see that it is a well-ordering, consider any non-empty subset of ℤ. Case 1: If A contains some non-negative number, then the set B = {n ∈ ω | n ∈ A} is non-empty and has a least element n_{0} by the well-ordering property of ω (for convenience, we regard ω as a subset of ℤ). Then for any x ∈ A, either x is non-negative and thus in B, in which case n_{0} ⩽′ x by leastness of n_{0}, or else x is negative, and thus n_{0} <′ x by definition of <′. So n_{0} is least in A.

Case 2: If A contains only negative numbers, then let B′ = {m ∈ ω | −m ∈ A}. The set B′ is non-empty, and thus has a least element m_{0} by the well-ordering property of ω. Then for any x ∈ A, we have x = −m for some m ∈ B′, and thus m_{0} ⩽ m, which implies −m_{0} ⩽′ −m = x by definition of <′. It follows that −m_{0} is least in A. In any case, A has a least element, and thus <′ is a well-order.

(b) One has E(3) = 3, E(−1) = ω, and E(−2) = ω^{+}.

Problem 7.14 We use the non-strict version of the definition of a partial order: First, notice that if a ⩽ b, then for all x ∈ A, we have x ∈ F (a) ⇒ x ⩽ a ⇒ x ⩽ b ⇒ x ∈ F (b) by transitivity, and thus F (a) ⊆ F (b). Conversely, assume that F (a) ⊆ F (b), for a, b ∈ A. Since a ∈ F (a), we have a ∈ F (b), and thus a ⩽ b, by definition of F. So for a, b ∈ A, we have a ⩽ b iff F (a) ⊆ F (b). It remains to be shown that F is one-to-one and onto. So suppose that F (a) = F (b), then F (a) ⊆ F (b) and F (b) ⊆ F (a), thus a ⩽ b and b ⩽ a by what we have just shown, and thus a = b by antisymmetry. So F is one-to-one. Also, F is clearly onto S since S = ran F. It follows that F is an isomorphism from ⟨A, ⩽⟩ onto ⟨S, ⊆⟩.

Problem 7.16 Recall that for any sets, x ∈ y^{+} iff x ∈ − y. This follows immediately from the definition of y^{+} = y∪{y}. Assume α and β are ordinal numbers with α ∈ β. Then β ∉ − α by trichotomy, and thus β ∉ α^{+} by the above remark. But α^{+} is an ordinal by Lemma 12(2), so by trichotomy again, it follows that α^{+} ∈ − β. This implies, again by the above remark, α^{+} ∈ β^{+}. Finally, if α ≠ β, then α ∈ β or β ∈ α by trichotomy. In the first case, α^{+} ∈ β^{+}, and in the second case, β^{+} ∈ α^{+}. In either case, α^{+} ≠ β^{+}.

If we use the regularity axiom, then we can prove that for any two sets x and y (not necessarily ordinals), if x ≠ y then x^{+} ≠ y^{+}. Suppose to the contrary that x^{+} = y^{+}. Then x ∈ x^{+} = y^{+} and y ∈ y^{+} = x^{+}. So by our first remark, x ∈ − y and y ∈ − x. But x ≠ y, and thus x ∈ y and y ∈ x, contradicting regularity.

Problem 7.17 We first show the following claim: If α, β are ordinals, and if there exists a one-to-one, order-preserving map f : β → α, then β ∈ − α. Proof: We first prove, as in Problem 7.5, that for all x ∈ β, x ∈ − f(x). For otherwise there would be a least x ∈ β such that x ∉ − f(x). But x ∈ α and f(x) ∈ β are ordinals, so by trichotomy, f(x) ∈ x. Since f is order-preserving, we have f(f(x)) ∈ f(x), contradicting the leastness of x. This shows that for all x ∈ β, x ∈ − f(x) ∈ α, and thus, by transitivity of α, x ∈ α. In particular, it follows that β ⊆ α, and by Corollary 8, β ∈ − α.

Now Problem 7.17 follows easily: Let E_{A} : A → α and E_{B} : B → β be the respective isomorphisms from ⟨A, <⟩ and ⟨B, <⟩ onto their ∈-images. Then E_{A} ∘ E_{B}^{−1} : β → α is one-to-one and order-preserving, and thus β ∈ − α by our first claim.

Problem 7.18 Recall from Lemma 12(3) that if S is a set of ordinals, then ⋃ S is an ordinal. We distinguish two cases. Case 1: ⋃ S ∈ S. In this case, for any α ∈ S, we have α ⊆ ⋃ S (by definition of union), and thus α ∈ − ⋃ S (by Corollary 8). It follows that ⋃ S is the greatest element of S.

Case 2: ⋃ S ∉ S. We claim that S has no greatest element in this case. Assume, to the contrary, that α was a greatest element of S. Then for any x ∈ α, we would have x ∈ ⋃ S by definition of union. Conversely, for any x ∈ ⋃ S, we would have x ∈ y ∈ S for some y ∈ S, but y ∈ − α, and thus x ∈ α by transitivity of α. It follows that α = ⋃ S, contradicting ⋃ S ∉ S. Thus, S has no greatest element.

We further claim that in Case 2, ⋃ S is not the successor of another ordinal. Suppose, to the contrary, that ⋃ S = β^{+}. Then β ∈ ⋃ S, and thus β ∈ α ∈ S for some ordinal α, hence ⋃ S = β^{+} ∈ − α. On the other hand, since α ∈ S, we have α ⊆ ⋃ S by definition of union, and hence α ∈ − ⋃ S, since ⋃ S is an ordinal. It follows that ⋃ S = α ∈ S, contradicting ⋃ S ∉ S. Therefore, ⋃ S is not the successor of an ordinal.