A note on a proof of Zorn’s Lemma from Axiom of Choice without transfinite induction

Koji Nuida

December 8, 2011

Abstract

In this note, we give a proof of Zorn’s Lemma from Axiom of Choice without transfinite induction (whose essential idea is the same as the proof of Theorem 4.19 in the book [H. Rubin and J. E. Rubin, “Equivalents of the Axiom of Choice, II”, Second Edition, Studies in Logic and the Foundations of Mathematics vol.116, North-Holland, 1985], as I noticed after writing the note ...). For the sake of comparison, we also include as an appendix a proof of the claim using transfinite induction.

Throughout this note, let (X, ≤) denote an arbitrary non-empty partially ordered set in which every chain (linearly or totally ordered subset) C has an upper bound (with respect to ≤), that is, an element x ∈ X satisfying that c ≤ x for every c ∈ C. Then Zorn’s Lemma states that such an X always has a maximal element (with respect to ≤), that is, an element x ∈ X satisfying that there exist no elements y ∈ X with x < y. In this note, we give a proof of Zorn’s Lemma from Axiom of Choice (in Zermelo–Fraenkel set theory), without transfinite induction which would be used in a “natural” proof of the claim.

Assume, for the contrary, that an X satisfying the hypothesis has no maximal elements. We will derive a contradiction from this assumption.

We summarize some basic definitions and terminologies:

• We say that a chain C in a subset Y of X is bounded in Y if there exists an element x ∈ Y \C satisfying that c < x for every c ∈ C, and unbounded in Y otherwise.

• A chain C in X is called well-ordered if any non-empty subset of C has a unique minimal element.

• For a chain C and an element c ∈ C, the subset {d ∈ C | d < c} is called the initial segment of C relative to c and is denoted by s_{C}(c).

Let C denote the set of all non-empty chains in X. For each C ∈ C, define U_{C} = {x ∈ X \ C | c < x for every c ∈ C}. We notice the following property:

Lemma 1. We have U_{C} ≠ ∅ for every C ∈ C.

Proof. By the hypothesis of Zorn’s Lemma, C has an upper bound x ∈ X. If y ∈ U_{{x}}, then we have c ≤ x < y (hence c < y) for every c ∈ C, therefore y ∉ C and y ∈ U_{C}. Hence we have U_{{x}} ⊂ U_{C}, while U_{{x}} ≠ ∅ by the assumption that X has no maximal elements, therefore we have U_{C} ≠ ∅.

We would like to construct (by using Axiom of Choice) a choice function f of the family {U_{C}}_{C∈C} which satisfies some more appropriate properties described below.

For an arbitrary pair of C_{1}, C_{2} ∈ C, we define a symmetric relation C_{1} ∼_{pre} C_{2} to mean that the chain C_{1} ∩ C_{2} is unbounded in both C_{1} and C_{2}. Then we define an equivalence relation ∼ on C to be the transitive closure of ∼_{pre}, that is, we have C_{1} ∼ C_{2} if and only if there exists a finite sequence C_{1} = C′_{0}, C′_{1}, …, C′_{n} = C_{2} (n ≥ 0) of elements of C with C′_{i} ∼_{pre} C′_{i+1} for every 0 ≤ i ≤ n − 1. Note that if C_{1} ∼ C_{2} and C_{1} has a maximum element c, then c ∈ C_{2} and c is also a maximum element of C_{2}. Now we present the following lemma:

Lemma 2. If C_{1}, C_{2} ∈ C and C_{1} ∼ C_{2}, then U_{C_{1}} = U_{C_{2}}.

Proof. It suffices to show that U_{C_{1}} ⊂ U_{C_{2}} if C_{1} ∼_{pre} C_{2}. Let x ∈ U_{C_{1}}. If x ∈ C_{2}, then the upper bound x (∈ C_{2} \ (C_{1} ∩ C_{2})) of C_{1} is also an upper bound of C_{1} ∩ C_{2}, therefore C_{1} ∩ C_{2} is bounded in C_{2}, contradicting the hypothesis C_{1} ∼_{pre} C_{2}. Hence x ∉ C_{2}. If c ∈ C_{2} and c ≮ x, then, as C_{1} ∩ C_{2} is unbounded in C_{2}, there exists a d ∈ C_{1} ∩ C_{2} with c ≤ d ≮ x. Now we have d ∈ C_{1} and d ≮ x, contradicting the property x ∈ U_{C_{1}}. Hence we have c < x for every c ∈ C_{2}, therefore x ∈ U_{C_{2}}.

We define a subset U_{E} of X for each ∼-equivalence class E by U_{E} = U_{C}, where C ∈ E. This is well-defined by virtue of Lemma 2. Now we obtain (\underline{by using Axiom of Choice}) a choice function f of the family \{U_{E}\}_{E∈X/∼}. Moreover, for simplicity, we write f(C) = f([C]) for any C ∈ C, where [C] denotes the ∼-equivalence class of C. Hence f(C) ∈ U_{C} for any C ∈ C. Moreover, if C_{1}, C_{2} ∈ C and C_{1} ∼ C_{2}, then we have f(C_{1}) = f(C_{2}).

From now, we fix an element x_{0} ∈ X. We give the following definition:

• We say that a C ∈ C is f-consecutive if C is well-ordered, x_{0} is the minimum element of C, and we have f(s_{C}(c)) = c for any c ∈ C \ {x_{0}}.

We present some properties of f-consecutive chains:

Lemma 3. Let C ∈ C be f-consecutive, and suppose that ∅ ≠ C′ ⊂ C and C′ is bounded in C. Then we have f(C′) = d, where d is the unique minimal element of the set of all upper bounds x ∈ C \ C′ of C′.

Proof. Note that C′ ∈ C. Let d be as specified in the statement, which indeed exists by virtue of the fact that C is well-ordered and C′ is bounded in C. We show that s_{C}(d) ∼ C′. First, we have C′ ⊂ s_{C}(d), therefore s_{C}(d) ∩ C′ = C′ is unbounded in C′. On the other hand, if x ∈ s_{C}(d) \ C′, then x is not an upper bound of C′ by the choice of d. Therefore C′ is unbounded in s_{C}(d). Hence we have s_{C}(d) ∼ C′. Now we have f(C′) = f(s_{C}(d)) by the property of f, while we have f(s_{C}(d)) = d, as C is f-consecutive. This implies that f(C′) = d.

Lemma 4. Let C_{1}, C_{2} ∈ C be two f-consecutive chains. Then exactly one of the following three conditions is satisfied:

1. C_{1} = C_{2};

2. C_{1} is an initial segment of C_{2};

3. C_{2} is an initial segment of C_{1}.

Proof. It is obvious that two of the three conditions specified in the statement do not occur simultaneously.

First we show that for each i ∈ {1, 2}, the conditions x ∈ C_{1} ∩ C_{2} and y ∈ s_{C_{i}}(x) imply y ∈ C_{1} ∩ C_{2}. Assume, for the contrary, that a counterexample y exists for some x, and let y be the minimal counterexample relative to the fixed x (which exists, as C_{i} is well-ordered). Then we have s_{C_{i}}(y) ≠ ∅, as x_{0} ∈ C_{1} ∩ C_{2}. By the choice of y, we have s_{C_{i}}(y) ⊂ C_{3−i} and y ∉ C_{3−i}. We have f(s_{C_{i}}(y)) = y, as C_{i} is f-consecutive. On the other hand, as x ∈ C_{1} ∩ C_{2} and y < x, the subset s_{C_{i}}(y) of C_{3−i} is bounded in C_{3−i}, therefore we have f(s_{C_{i}}(y)) ∈ C_{3−i} by Lemma 3. But this contradicts the property y ∉ C_{3−i}. Hence the claim of this paragraph holds. Moreover, as C_{1} and C_{2} are wellordered, the above fact implies that C_{1} ∩ C_{2} is either equal to or an initial segment of C_{i} for each i ∈ {1, 2} (if C_{1} ∩ C_{2} ≠ C_{i}, consider the minimum element of C_{i} \ (C_{1} ∩ C_{2})).

Now assume, for the contrary, that C_{1} ∩ C_{2} ≠ C_{1} and C_{1} ∩ C_{2} ≠ C_{2}. Then C_{1} ∩ C_{2} is an initial segment of both C_{1} and C_{2}, therefore we have f(C_{1} ∩ C_{2}) ∈ C_{1} ∩ C_{2}, as C_{1} and C_{2} are f-consecutive. But this contradicts the definition of f. Hence we have C_{1} ∩ C_{2} = C_{i} for some i ∈ {1, 2}, and now the above result implies that C_{i} = C_{3−i} or C_{i} is an initial segment of C_{3−i}.

Let C_{0} denote the union of all f-consecutive chains (note that at least one f-consecutive chain, say {x_{0}}, exists). Then Lemma 4 implies that C_{0} ∈ C (for two elements x, y ∈ C_{0}, there exist f-consecutive chains C containing x and C′ containing y, and x ∈ C ⊂ C′ or y ∈ C′ ⊂ C by the lemma). Now we present the following lemma:

Lemma 5. Let c ∈ C_{0}, and let C be an f-consecutive chain containing c. Then s_{C_{0}}(c) = s_{C}(c).

Proof. First note that s_{C}(c) ⊂ s_{C_{0}}(c), as C ⊂ C_{0} by the definition of C_{0}. We show that d ∈ C for an arbitrary element d ∈ s_{C_{0}}(c). By the definition of C_{0}, there exists an f-consecutive chain C′ such that d ∈ C′. Now we have d ∈ C′ ⊂ C if C′ = C or C′ is an initial segment of C. On the other hand, if C is an initial segment of C′, then the properties c ∈ C, d ∈ C′ and d < c imply d ∈ C. Hence we have d ∈ C by Lemma 4.

From now, we will show that C_{0} itself is f-consecutive. It is obvious that x_{0} is the minimum element of C_{0}.

Lemma 6. C_{0} is well-ordered.

Proof. Let A be an arbitrary non-empty subset of C_{0}. Choose an element a ∈ A, and let C be an f-consecutive chain with a ∈ C (which exists by the definition of C_{0}). As C is well-ordered, A ∩ C has the minimum element, say a_{0}. Now if a′ ∈ A and a′ < a_{0}, then we have a′ ∈ s_{C_{0}}(a_{0}) = s_{C}(a_{0}) by Lemma 5, therefore a′ ∈ A ∩ C and a′ < a_{0}, contradicting the choice of a_{0}. Hence we have a′ ≥ a_{0} for every a′ ∈ A, therefore A itself has the minimum element a_{0}.

Lemma 7. We have f(s_{C_{0}}(c)) = c for any c ∈ C_{0} \ {x_{0}}.

Proof. Let C be an f-consecutive chain with c ∈ C (which exists by the definition of C_{0}). Then we have s_{C_{0}}(c) = s_{C}(c) by Lemma 5. As C is f-consecutive, now we have f(s_{C_{0}}(c)) = f(s_{C}(c)) = c.

By Lemma 6 and Lemma 7, it follows that C_{0} is f-consecutive. Now it is straightforward to verify that C_{0} ∪ {f(C_{0})} is also an f-consecutive chain, but it is not a subset of C_{0}, contradicting the definition of C_{0}. Hence X should have a maximal element, concluding the proof of Zorn’s Lemma.

Appendix: A proof using transfinite induction

In this appendix, for the sake of comparison, we describe a proof of Zorn’s Lemma from Axiom of Choice using transfinite induction. First we clarify the statement of the principle for “definition by transfinite recursion” (see e.g., Theorem 9.3 in Chapter I of [K. Kunen, “SET THEORY, An Introduction to Independence Proofs”, Elsevier, 1980]):

Theorem 1. Let φ(x, y) be a formula (in Zermelo–Fraenkel set theory) with free variables x, y satisfying ∀x∃!yφ(x, y). Then there exists a formula Φ(x, y) with free variables x, y satisfying the following two conditions;

1. ∀x((x ∈ ON → ∃!yΦ(x, y)) ∧ (¬x ∈ ON → ¬∃yφ(x, y)));

2. ∀x(x ∈ ON → ∀y, z(y = Φ↾_{x} ∧φ(y, z) → Φ(x, z))),

where “x ∈ ON” is an abbreviation of “x is an ordinal number” and “Φ ↾_{x}” is an abbreviation of the set {⟨a, b⟩ | a ∈ x ∧ Φ(a, b)} (with ⟨a, b⟩ denoting the ordered pair of a and b).

Intuitively, the theorem means that, if we would like to define a “function” Φ with domain consisting of all ordinal numbers (the whole of which is never a set) in such a way that the value of Φ at each ordinal number α is determined by a given rule from the values of Φ at ordinal numbers less than α, then there indeed exists such a “function” Φ. Note that this is a theorem of ZF set theory and does not depend on Axiom of Choice.

Now we give a proof of Zorn’s Lemma from Axiom of Choice using Theorem 1 (as well as transfinite induction). Let X ≠ 0 be a partially ordered set appeared in the statement of Zorn’s Lemma. Assume, for the contrary, that X has no maximal elements. Then, for each non-empty subset C of X which is isomorphic to an ordinal number (hence a chain), it follows \underline{from Axiom of Choice} that there exists a distinguished upper bound b_{C} of C with b_{C} ∈ X \ C.

To apply Theorem 1, first we define a formula φ(x, y) in the following manner, where we fix an element a ∈ X throughout the proof:

• If x = 0 (= ∅), then let φ(x, y) mean that y = a.

• If x is a function from an ordinal number α > 0 to X which is an isomorphism (between partially ordered sets) onto the image Im(x) of x, then let φ(x, y) mean that y = b_{Im(x)} (note that Im(x) is isomorphic to the non-empty ordinal number α, therefore b_{Im(x)} is indeed defined).

• Otherwise, let φ(x, y) mean that y = 0.

This formula φ(x, y) satisfies the hypothesis of Theorem 1, therefore a formula Φ(x, y) as in the theorem exists. Now we have the following lemma:

Lemma 8. Let x be an ordinal number, and let x′ be the unique element satisfying Φ(x, x′).

1. We have x′ ∈ X.

2. If y < x and Φ(y, y′), then y′ < x′ in X.

Proof. We prove the claim by transfinite induction on x. First, if x = 0, then it follows from the definition of the formula φ that x′ = a, therefore the specified conditions are satisfied. Secondly, suppose that x > 0. Then, by the hypothesis of the transfinite induction, the set Φ ↾_{x} in the statement of Theorem 1 is an isomorphism from x to a subset of X, say, C (note that x is totally ordered). Now by the definitions of Φ and φ, it follows that x′ = b_{C}, therefore the specified conditions are satisfied for x (the second condition follows from the property that b_{C} ∈ X \ C is an upper bound of C). Hence the claim holds.

By the second property shown in Lemma 8, for each element v ∈ X, there exists at most one ordinal number x satisfying Φ(x, v). Let X′ denote the subset of X defined in such a way that v ∈ X′ if and only if v ∈ X and Φ(x, v) for some (or equivalently, a unique) ordinal number x. By the Axiom Schema of Replacement applied to the set X′ and the formula Φ′(x, y) := Φ(y, x), there exists a set Y for which we have y ∈ Y if y is an ordinal number and the unique element y′ satisfying Φ(y, y′) belongs to X′. Now by the first property shown in Lemma 8, the set Y contains every ordinal number. However, this contradicts Burali–Forti Paradox (which states that there exist no sets containing all ordinal numbers). Hence X should have a maximal element, concluding the proof of Zorn’s Lemma.