MATH 582, INTRODUCTION TO SET THEORY, WINTER 1999

Answers to Problem Set 9

Problem 1 Let 𝒜 be the set of all chains of a given poset ⟨P, ⩽⟩. Notice that the elements of 𝒜 are chains in P, but we can also speak of chains in 𝒜 (in the sense of Zorn’s Lemma). To avoid confusion, we will speak of P -chains C ⊆ P, and of 𝒜 -chains 𝒞 ⊆ 𝒜.

To apply Zorn’s Lemma, we must show that 𝒜 is closed under unions of 𝒜 -chains. So let 𝒞 ⊆ 𝒜 be an 𝒜 -chain. We claim that ⋃ 𝒞 ∈ 𝒜, i.e., that ⋃ 𝒞 is a P -chain. Clearly, ⋃ 𝒞 ⊆ P, so we must show that for all x, y ∈ ⋃ 𝒞, either x ⩽ y or y ⩽ x. Since x, y ∈ ⋃ 𝒞, we must have x ∈ C and y ∈ D for some C, D ∈ 𝒞. Since 𝒞 is an 𝒜 -chain, either C ⊆ D or D ⊆ C. Assume without loss of generality that C ⊆ D. Then x, y ∈ D. But since D ∈ 𝒜 is a P -chain, we have x ⩽ y or y ⩽ x, as desired. Thus, ⋃ 𝒞 is a P -chain, and 𝒜 is closed under unions of 𝒜 -chains. It follows by Zorn’s Lemma that 𝒜 has a maximal element, i.e., there is a maximal P -chain.

Problem 2 Suppose ⟨P, ⩽⟩ is a poset such that any P -chain has an upper bound in P. By Problem 1, there exists a maximal chain C ⊆ P. By assumption, C has an upper bound x ∈ P, i.e., there is x ∈ P such that for all y ∈ C, y ⩽ x. We claim that x is a maximal element in P. For otherwise, there would exist z ∈ P such that x < z. But then C ∪ {z} would be a P -chain which strictly contains C, contradicting the maximality of C.

Problem 3 The original hint given with this problem was wrong. The problem is that the given set

𝒜 = {R ⊆ A × A | R is a well-order on some subset of A}

is not closed under unions of chains, because a union of a chain of well-orders is not necessarily a well-order. For instance, the usual order < on the integers ℤ is the union of a chain of well-orders on subsets of ℤ, namely the subsets of the form {x ∈ ℤ | x ⩾ a} for a ∈ ℤ.

So we need to modify the argument somewhat. Instead of considering the inclusion ordering on 𝒜, we will consider the more restrictive ordering of “being an initial piece”. We will then use the poset version of Zorn’s Lemma (from Problem 2).

For a relation R, recall that the field of R, fld R, was defined to be dom R ∪ ran R. Thus, any R ∈ 𝒜 is a well-order on fld R. If R, Q ∈ 𝒜, we say that R is an initial piece of Q, in symbols R ⩽_{ip} Q, if R ⊆ Q and for all x, y ∈ A,

yQx and x ∈ fld R implies yRx.  (1)

It is easily seen that ⩽_{ip} is reflexive, anti-symmetric, and transitive, and thus ⩽_{ip} defines a partial order on 𝒜. We claim that every ⩽_{ip}-chain has an upper bound in 𝒜. Let 𝒞 be any such chain. Define R̄ = ⋃ 𝒞. Notice that fld R̄ = ⋃{fld R | R ∈ 𝒞 } ⊆ A. We claim that R̄ is a well-order on fld R̄, and that it is an upper bound for 𝒞 with respect to ⩽_{ip}.

Irreflexivity: Consider x ∈ fld R̄. Since any R ∈ 𝒞 is irreflexive, we have ¬xRx, and hence ¬xR̄x. Transitivity: Consider x, y, z ∈ fld R̄ such that xR̄y and yR̄z. Then xRy for some R ∈ 𝒞, and yQz for some Q ∈ 𝒞. Since 𝒞 is a ⩽_{ip}-chain, either R ⊆ Q or Q ⊆ R; assume without loss of generality that R ⊆ Q. Then xQyQz, hence xQz by transitivity of Q, and hence xR̄z as desired. Connectedness: Consider x, y ∈ fld R̄. Then x ∈ fld R for some R ∈ 𝒞, and y ∈ fld Q for some Q ∈ 𝒞. As before, we can assume without loss of generality that R ⊆ Q. Then x, y ∈ fld Q, and hence xQy or x = y or yQx by connectedness of Q. But since Q ⊆ R̄, this implies xR̄y or x = y or yR̄x.

Well-order: Consider any non-empty subset B ⊆ fld R̄. We claim that B has a least element with respect to R̄. First, since B is non-empty, there must be some R ∈ 𝒞 such that B ∩ fld R is non-empty. Since R is a well-order, there exists a least element x_{0} ∈ B ∩ fld R, with respect to R. We claim that x_{0} is a least element of B with respect to R̄. Assume to the contrary that there was some y ∈ B with yR̄x_{0}. Then yQx_{0} for some Q ∈ 𝒞. Since we cannot have yRx_{0} (by leastness of x_{0}), it follows that Q ⊈ R, and thus Q ⩽̸_{ip} R. But since 𝒞 is a chain, it must then be the case that R ⩽_{ip} Q. But x_{0} ∈ fld R and yQx_{0}, which implies yRx_{0} by (1), contradicting the leastness of x_{0}. Hence, yR̄x_{0} is impossible, and x_{0} is least in B with respect to R̄.

Thus, R̄ is a well-order, and since R̄ = ⋃ 𝒞 ⊆ A × A, it follows that R̄ ∈ 𝒜. Next, we show that R̄ is an upper bound for 𝒞. For any R ∈ 𝒞, we must show R ⩽_{ip} R̄. First, since R̄ = ⋃ 𝒞, it is clear that R ⊆ R̄. To show (1), consider any x, y ∈ A such that yR̄x and x ∈ fld R. Then yQx for some Q ∈ 𝒞. Since 𝒞 is a chain, either R ⩽_{ip} Q or Q ⩽_{ip} R. In the first case, yRx by (1), applied to R and Q. In the second case, Q ⊆ R, and thus also yRx. This proves R ⩽_{ip} R̄.

We have shown that any chain in ⟨𝒜 , ⩽_{ip}⟩ has an upper bound. Now we can apply Zorn’s Lemma for posets (Problem 2) to conclude that 𝒜 has a maximal element R with respect to ⩽_{ip}. We claim that fld R = A. For suppose otherwise. Then there is some x ∈ A such that x ∉ fld R. Consider R′ = R ∪ (fld R × {x}). It is easily seen that R′ is a well-order and that R <_{ip} R′, contradicting the maximality of R. Hence, fld R = A, and thus R is a well-order on A. This proves the well-ordering theorem.

Problem 4

(a) Let 𝒜 be the set of convex subsets of X. We claim that 𝒜 is closed under unions of chains. So let 𝒞 be a chain of convex subsets of X, and let Y = ⋃ 𝒞. We have to show that Y is convex. So take u, v ∈ Y. By definition of Y, we have u ∈ A and v ∈ B for some A, B ∈ 𝒞. Since 𝒞 is a chain, either A ⊆ B or B ⊆ A. Let us say, without loss of generality, that A ⊆ B. Then u, v ∈ B, and since B is convex, the line segment connecting u and v is contained in B. But B ⊆ Y, and thus the line segment connecting u and v is also contained in Y. Since u, v ∈ Y were arbitrary, this shows that Y = ⋃ 𝒞 is convex. Thus, 𝒞 is closed under unions of chains. It follows by Zorn’s Lemma that there is a maximal M ∈ 𝒞, i.e.a maximal convex subset of X.

(b) Here are some examples of maximal convex subsets of the given set X. As you can see, such sets are not at all unique.

Problem 5 Before we prove this, let us observe that any non-empty finite chain {B_{1}, …, B_{n}} has a maximal element. This is proved by induction on n: In case n = 1, this is clear. For the induction step, assume the claim holds for n and consider 𝒞 = {B_{1}, …, B_{n+1}}. By induction hypothesis, {B_{1}, …, B_{n}} has a maximal element, say, B_{i}. Then, since 𝒞 is a chain, either B_{n+1} ⊆ B_{i} or B_{i} ⊆ B_{n+1}. In the first case, B_{i} is maximal in 𝒞, and in the second case, B_{n+1} is maximal in 𝒞.

Now on to Problem 5. It suffices to show that 𝒜 is closed under unions of chains. So let 𝒞 ⊆ 𝒜 be an arbitrary chain. Let B = ⋃ 𝒞. We claim that B ∈ 𝒜. By assumption, it suffices to show that every finite subset of B is a member of 𝒜. So let F = {x_{1}, …, x_{n}} ⊆ B be an arbitrary such finite subset. Since x_{1}, …, x_{n} ∈ ⋃ 𝒞, there must be sets B_{1}, …, B_{n} ∈ 𝒞 such that x_{i} ∈ B_{i} for i = 1 … n. Since 𝒞 is a chain, the set {B_{1}, …, B_{n}} ⊆ 𝒞 is a finite chain, and thus it has a maximal element B_{i} by our above observation. Then x_{1}, …, x_{n} ∈ B_{i}, and thus F ⊆ B_{i}. However, B_{i} ∈ 𝒜, and thus also F ∈ 𝒜, by assumption on 𝒜. Since F was an arbitrary finite subset of B, it follows that B ∈ 𝒜, and thus 𝒜 is closed under unions of chains. By Zorn’s Lemma, 𝒜 has a maximal element.