Zorn's lemma

Theorem

Zorn's lemma

T-126Home MU-403Threads logic

Statement

Let \( (P, \leq) \) be a nonempty partially ordered set. Suppose every chain \( C \subseteq P \) (i.e. every totally ordered subset of \( P \) under \( \leq \)) has an upper bound in \( P \) (an element \( u \in P \) with \( c \leq u \) for all \( c \in C \); \( u \) need not lie in \( C \), and the empty chain counts, so \( P \) itself must be nonempty and possess at least one element). Then \( P \) has a maximal element: there exists \( m \in P \) such that no \( x \in P \) satisfies \( m \lt x \). This statement, taken as an axiom scheme over ZF set theory, is logically equivalent to the Axiom of Choice (AC).

Why it matters

Zorn's Lemma is the workhorse form of the Axiom of Choice used throughout algebra, analysis, and topology whenever one needs to produce a maximal object without an explicit construction: a maximal ideal containing a given ideal, a basis of a vector space, an algebraic closure of a field, a maximal linearly independent set, a Hamel basis, the Hahn–Banach extension, a maximal filter (ultrafilter existence), or a maximal antichain. Its power is that it converts an existence question about "no upper limit to a construction" into a single hypothesis check on chains, entirely bypassing any need for a well-ordering or explicit recursion.

Historically it also matters because of its equivalence to AC and to the Well-Ordering Theorem: the three are interderivable in ZF, so accepting any one of them commits you to all three, with all the attendant nonconstructive consequences (e.g. the existence of non-measurable sets, the Banach–Tarski decomposition).

Hypotheses

P is a nonempty partially ordered set.If \( P = \varnothing \), the hypothesis "every chain has an upper bound" is vacuously true (the only chain is \( \varnothing \), and it has no upper bound since \( P \) has no elements at all — strictly this makes the hypothesis false unless one allows the bound to not exist, so the standard convention requires \( P \neq \varnothing \) outright); with \( P = \varnothing \) there is trivially no maximal element, so nonemptiness must be assumed explicitly. Every chain (including the empty chain) has an upper bound in P.Take \( P = \mathbb{N} \) with the usual order. Every finite chain has an upper bound, but the chain \( C = \mathbb{N} \) itself (which is totally ordered) has no upper bound in \( \mathbb{N} \). Indeed \( \mathbb{N} \) has no maximal element at all — for every \( n \) there is \( n+1 \gt n \). This shows the chain-bound hypothesis cannot be weakened to "every finite chain has an upper bound." The order relation is only required to be a partial order (reflexive, antisymmetric, transitive) — not a total order.This is not a further restriction but a clarification: Zorn's Lemma is not simply "totally ordered sets bounded above have maxima" (that would be a triviality via the top of the total order); its content lies precisely in posets with incomparable elements, where chains are proper subsets and maximal elements need not be unique or comparable to every other element.

Proof

We prove Zorn's Lemma from the Axiom of Choice (ZF + AC \( \Rightarrow \) Zorn). The converse (Zorn \( \Rightarrow \) AC) is sketched afterward; both directions together with the Well-Ordering Theorem give the classical equivalence in ZF.

Assume for contradiction that \( P \) has no maximal element.

Proof by contradiction: we will construct, using AC, a chain in \( P \) with no upper bound, contradicting the hypothesis. A

Since \( P \) has no maximal element, for every \( x \in P \) the set \( \{ y \in P : y \gt x \} \) is nonempty.

Unwinding the definition of "\(x\) maximal" (no \(y\) with \(y \gt x\)) and negating it. A

By the Axiom of Choice, fix a function \( f : P \to P \) such that \( f(x) \gt x \) for every \( x \in P \).

AC applied to the family of nonempty sets \( \{ \{y \gt x\} \}_{x \in P} \): a choice function selects one element from each. This is the only use of AC in the whole proof. B

Fix, using the hypothesis, some \( a \in P \) (an upper bound for the empty chain).

Existence of an upper bound for \( \varnothing \) forces \( P \neq \varnothing \); pick any such bound as a base point. A

Call a subset \( T \subseteq P \) an \(f\)-tower if: (i) \( a \in T \); (ii) \( T \) is closed under \( f \) (\( x \in T \Rightarrow f(x) \in T \)); (iii) for every chain \( C \subseteq T \), \( \sup C \in T \) whenever the chain has a least upper bound taken within \( T \) that is realized as the union of an increasing enumeration — formally, if \( C \subseteq T \) is a chain of \( T \) totally ordered by \( \leq \) and \( C \) is well-ordered by \( \leq \), then the upper bound of \( C \) supplied by hypothesis, restricted to lie in \( T \), belongs to \( T \).

This is the technical device (following Bourbaki's tower argument via well-ordered chains) that lets us build, purely from \( f \), a single well-ordered chain that cannot close off — forcing a contradiction with \( P \)'s having a bound. C

The intersection \( T_0 \) of all \( f \)-towers is itself an \( f \)-tower (the minimal one), and one shows by transfinite induction on towers that \( T_0 \), ordered by \( \leq \), is a chain in \( P \).

Standard tower lemma (Bourbaki–Witt): given closure under \( f \) and under bounds-of-chains, the minimal tower is linearly ordered. The proof compares two elements of \( T_0 \) via the auxiliary notion of "comparable elements" and shows the set of elements comparable to any fixed \( t \in T_0 \) is itself a tower, hence equals \( T_0 \) by minimality. C

Since \( T_0 \) is a chain in \( P \), by hypothesis \( T_0 \) has an upper bound \( u \in P \); by tower-closure (iii), \( u \in T_0 \), so \( u = \max T_0 \).

Apply the chain-bound hypothesis to the chain \( T_0 \), then use closure property (iii) of the minimal tower to place the bound back inside \( T_0 \). B

But \( f(u) \gt u \) and \( f(u) \in T_0 \) by closure property (ii), contradicting that \( u \) is the maximum of \( T_0 \).

Definition of \( f \) from Step 3 gives \( f(u) \gt u \); tower closure under \( f \) gives \( f(u) \in T_0 \); but \( u = \max T_0 \) forbids any element of \( T_0 \) strictly exceeding it — contradiction. B

Therefore the assumption in Step 1 is false: \( P \) has a maximal element. \( \blacksquare \)

Reductio ad absurdum discharges the assumption of Step 1. A

Converse direction (Zorn \( \Rightarrow \) AC), sketch: given a family \( \{X_i\}_{i \in I} \) of nonempty sets, let \( P \) be the set of partial choice functions \( p \) (functions with domain a subset of \( I \) and \( p(i) \in X_i \)), partially ordered by extension (\( p \leq q \) iff \( q \) extends \( p \)). Any chain of partial choice functions has an upper bound, namely their union (which is again a function, since the chain is totally ordered by extension and hence pairwise-compatible). By Zorn, \( P \) has a maximal element \( p^* \); if \( \operatorname{dom}(p^*) \neq I \), pick \( i_0 \notin \operatorname{dom}(p^*) \) and any \( x_0 \in X_{i_0} \) (nonempty), extending \( p^* \) and contradicting maximality. Hence \( \operatorname{dom}(p^*) = I \), giving a global choice function.

Result

\( P \neq \varnothing \) a poset, every chain in \( P \) bound above \(\ \Longrightarrow\ \) \( P \) has a maximal element

Reading. If you can always find "somewhere to point to" for any totally ordered sub-collection of your structure, then the structure has a top-most (not necessarily unique, not necessarily largest) element that nothing strictly exceeds.

Scope. Applies to any nonempty poset under ZF+AC; it is not restricted to sets of sets ordered by inclusion, though that is its most common form (e.g. ideals, subspaces, independent sets ordered by \( \subseteq \), where chain unions are the natural upper bounds). It gives existence only — it is entirely non-constructive and yields no algorithm for finding the maximal element.

Corollaries & converses

Every vector space has a basis (apply Zorn to the poset of linearly independent subsets ordered by \( \subseteq \); a chain's union is still independent).
Every ring with \( 1 \neq 0 \) has a maximal ideal (apply Zorn to proper ideals containing a given ideal, ordered by \( \subseteq \); the union of a chain of proper ideals is proper because \( 1 \) lies in none of them).
Every filter on a set extends to an ultrafilter (chains of filters have their union as an upper bound, which is again a filter).
Well-Ordering Theorem: every set can be well-ordered (build a well-ordering by transfinite recursion using Zorn on the poset of well-orderings of subsets, ordered by "initial segment extension").
The converse holds in the strong sense of logical equivalence over ZF: Zorn's Lemma, the Axiom of Choice, and the Well-Ordering Theorem are all mutually derivable (Zermelo 1904/1908, Kuratowski 1922, Zorn 1935). None is a strictly weaker consequence of another within ZF — assuming any one is exactly as strong as assuming AC.
Zorn's Lemma does not hold in ZF alone (without choice); there are models of ZF with posets satisfying the chain-bound hypothesis yet having no maximal element.

Fails without

Drop "every chain has an upper bound": \( P = \mathbb{Z} \) with the usual order. Every finite chain is bounded, but \( P \) itself is an (infinite) chain with no upper bound in \( \mathbb{Z} \); indeed \( \mathbb{Z} \) has no maximal element whatsoever, since \( n \lt n+1 \) always.
Drop AC (work in ZF alone): in the Zermelo–Fraenkel universe without choice it is consistent that \( \mathbb{R} \) cannot be well-ordered; correspondingly one can construct (in suitable ZF models lacking AC) a poset in which every chain happens to have an upper bound yet no maximal element exists — the tower argument's Step 3 (choice function \(f\)) is exactly where such a construction breaks, since there is no way to select, uniformly and without choice, a strict successor for each non-maximal element.
Drop nonemptiness of \(P\): \( P = \varnothing \) vacuously satisfies "every chain has an upper bound" only under a degenerate reading, but has no maximal element by definition (there are no elements at all) — hence the standing convention explicitly assumes \( P \neq \varnothing \).

Common errors

Believing the upper bound guaranteed by the hypothesis must lie in the chain \( C \) itself — it need only lie in \( P \). Confusing this with "every chain has a supremum in \( C \)" makes the hypothesis strictly stronger than it is (and false in most applications, e.g. chains of proper ideals whose union may not itself be an element originally singled out).
Forgetting to check the empty chain, whose "upper bound" requirement is exactly the assertion \( P \neq \varnothing \); students sometimes verify the hypothesis only for nonempty chains and then wrongly invoke Zorn on a poset that could be empty.
Treating the maximal element produced as necessarily unique or as the greatest element of \( P \); a poset can (and typically does) have several incomparable maximal elements, none of which need dominate the whole poset.
Applying Zorn's Lemma to a poset ordered "the wrong way round" — e.g. wanting a minimal ideal but checking chains have upper bounds instead of lower bounds; one must dualize the hypothesis (chains bounded below) to get a minimal element.
Believing the proof is constructive because it "builds" a chain via \( f \); the tower/Bourbaki–Witt argument is entirely non-constructive because \( f \) itself is produced by an unspecified choice function, and the tower \( T_0 \) is generally a proper-class-sized transfinite construction with no explicit description.

Discussion

Zorn's Lemma was isolated by Kazimierz Kuratowski in 1922 and independently by Max Zorn in 1935, though the underlying maximal-principle idea traces to Hausdorff's 1914 maximal chain principle (every poset contains a maximal chain, itself equivalent to AC). Zorn advertised the lemma explicitly as a substitute for transfinite induction and well-ordering arguments in algebra, arguing that algebraists found "maximality" hypotheses more natural to verify than well-orderings. This is precisely why it became the default tool in commutative algebra and functional analysis rather than the Well-Ordering Theorem, even though the two are equivalent.

The proof given above is the Bourbaki–Witt style argument via towers, which deliberately avoids explicit ordinal induction by instead constructing the minimal closed set (tower) generated by a base point and a "next" function \(f\), then showing this minimal tower is well-ordered and must terminate at a fixed point of \(f\) — contradicting that \(f\) has no fixed points. An alternative, more classical proof proceeds by genuine transfinite recursion: build a chain \( \{x_\alpha\}_{\alpha \lt \kappa} \) indexed by ordinals, setting \( x_{\alpha+1} = f(x_\alpha) \) and \( x_\lambda \) an upper bound of \( \{x_\alpha : \alpha \lt \lambda\} \) at limit stages, until this must stop for cardinality reasons (the chain cannot be a proper-class-many distinct elements of the set \(P\)) — that stopping point is the desired maximal element.

A subtlety worth flagging: the equivalence "Zorn \(\Leftrightarrow\) AC" is a theorem of ZF (Zermelo–Fraenkel without choice) — that is, working only with ZF's other axioms, one can prove AC implies Zorn and Zorn implies AC. This means Zorn's Lemma is not "weaker" or "more constructive" than AC in any technical sense, despite feeling more concrete; it carries exactly the same nonconstructive strength, including all the paradoxical consequences of AC such as the Banach–Tarski paradox (which uses a free ultrafilter / well-ordering constructed via Zorn-type arguments on the rotation group).

Common misconception: that Zorn's Lemma somehow avoids the Axiom of Choice because "it's just about chains, not arbitrary choice functions." In fact the proof above uses AC essentially and irreducibly in Step 3, to select a successor \(f(x)\) simultaneously for every non-maximal \(x \in P\) — there is no way around this selection without further structure on \(P\) (e.g. if \(P\) were countable and successors could be picked by a definable rule, choice would not be needed, but for general \(P\) it is indispensable).

Worked examples

Claim: every proper ideal \( I \) of a nonzero commutative ring \( R \) with identity is contained in a maximal ideal.

Set up the poset to which Zorn will be applied. A

Let \( P = \{ J \trianglelefteq R : I \subseteq J,\ J \neq R \} \), ordered by \( \subseteq \); \( P \neq \varnothing \) since \( I \in P \).

Definition of the poset of proper ideals extending \(I\); nonemptiness verified directly. A

Let \( C = \{ J_\alpha \}_{\alpha \in A} \) be a chain in \( P \), and set \( J = \bigcup_{\alpha} J_\alpha \). Then \( J \) is an ideal: for \( x, y \in J \) there are \( J_\alpha, J_\beta \) with \( x \in J_\alpha, y \in J_\beta \); since \(C\) is a chain, WLOG \( J_\alpha \subseteq J_\beta \), so \( x, y \in J_\beta \), giving \( x - y \in J_\beta \subseteq J \); and \( rx \in J_\alpha \subseteq J \) for \( r \in R \).

Direct verification that a union of a chain of ideals is an ideal, using the total ordering of the chain to place any two elements in a common member. B

\( J \neq R \), since \( 1 \notin J \) (as \( 1 \notin J_\alpha \) for every \(\alpha\), \( J_\alpha \) being proper), so \( J \in P \) and \( J \) is an upper bound for \( C \).

Properness is preserved under the union because \(1\) is excluded from every member of the chain, hence from the union. A

Every chain in \( P \) has an upper bound in \( P \). By Zorn's Lemma, \( P \) has a maximal element \( \mathfrak{m} \).

Direct application of Zorn's Lemma (the Statement) to the poset \(P\). B

\( \mathfrak{m} \) is a maximal ideal of \( R \) containing \( I \): if \( \mathfrak{m} \subsetneq K \subsetneq R \) for an ideal \(K\), then \(K \in P\) and \(K \gt \mathfrak{m}\), contradicting maximality of \(\mathfrak{m}\) in \(P\).

Unwinding "maximal in \(P\)" back into "maximal ideal of \(R\)": there is no proper ideal strictly containing \(\mathfrak{m}\). A

Every proper ideal of \( R \) is contained in a maximal ideal of \( R \)

Reading. In particular every nonzero ring with identity has at least one maximal ideal (take \( I = (0) \)).

Claim: every vector space \( V \) over a field \( F \) has a basis.

Set up the poset of linearly independent subsets. A

Let \( P = \{ S \subseteq V : S \text{ linearly independent} \} \), ordered by \( \subseteq \); \( \varnothing \in P \) so \( P \neq \varnothing \).

Definition of the poset; the empty set is (vacuously) linearly independent. A

Let \( C \) be a chain in \( P \) and \( S = \bigcup C \). Any finite subset \( \{v_1, \dots, v_n\} \subseteq S \) lies, by the chain property, in a single \( S_\alpha \in C \) (take the largest of the finitely many members of \(C\) containing each \(v_i\)), hence is linearly independent since \( S_\alpha \) is.

Only finitely many vectors are involved in any linear dependence relation, so the chain property lets us find one member of \(C\) containing all of them. B

So every finite subset of \( S \) is independent, hence \( S \) itself is linearly independent, so \( S \in P \) and \( S \) bounds \( C \) above.

Linear independence of a set is by definition equivalent to linear independence of all its finite subsets. A

By Zorn's Lemma, \( P \) has a maximal element \( B \).

Direct application of the theorem. B

\( B \) spans \( V \): if not, pick \( v \in V \setminus \operatorname{span}(B) \); then \( B \cup \{v\} \) is linearly independent (a nontrivial dependence would force \(v \in \operatorname{span}(B)\)), and \( B \cup \{v\} \supsetneq B\), contradicting maximality of \(B\) in \(P\).

Standard linear algebra fact: adjoining a vector outside the span of an independent set keeps it independent; combined with maximality of \(B\), this is a contradiction. B

\( B \) is a linearly independent spanning set, i.e. a basis of \( V \)

Reading. Every vector space, including infinite-dimensional ones like the space of all real sequences, has a basis — though for infinite-dimensional spaces no explicit basis can generally be written down (e.g. no basis of \( \mathbb{R} \) as a \( \mathbb{Q} \)-vector space, a Hamel basis, is known constructively).

Problems

State precisely why the hypothesis of Zorn's Lemma must require an upper bound for the empty chain, and explain what this forces about \(P\).
Solution
The empty subset \( \varnothing \subseteq P \) is vacuously totally ordered by any relation, so it counts as a chain. An "upper bound" for \( \varnothing \) is any element \( u \in P \) such that the (vacuous) condition "\( c \leq u \) for all \( c \in \varnothing \)" holds — which is automatically true for every \( u \in P \). So requiring the empty chain to have an upper bound is exactly requiring \( P \) to contain at least one element, i.e. \( P \neq \varnothing \). This is why the nonemptiness hypothesis is often folded into "every chain, including the empty one, has an upper bound" rather than stated as a separate clause.
Let \( P \) be the set of all finite subsets of \( \mathbb{N} \), ordered by \( \subseteq \). Does \( P \) satisfy the chain-bound hypothesis of Zorn's Lemma? Does \(P\) have a maximal element?
Solution
No to both, and the example illustrates why the hypothesis is needed. The chain \( C = \{ \{0\}, \{0,1\}, \{0,1,2\}, \dots \} \) is totally ordered by \( \subseteq \), but its "natural" upper bound would be \( \mathbb{N} \) itself, which is infinite and hence not in \( P \). No finite set bounds all of \(C\) above (any finite set omits some large enough initial segment). So the hypothesis fails for this chain, and indeed \(P\) has no maximal element: any finite set \(S\) is properly contained in \(S \cup \{n\}\) for \(n \notin S\). This is consistent with Zorn's Lemma, since the hypothesis was never verified.
Use Zorn's Lemma to show that every filter \(\mathcal{F}\) on a nonempty set \(X\) (a nonempty collection of subsets of \(X\), closed upward and under finite intersection, not containing \(\varnothing\)) is contained in an ultrafilter (a maximal proper filter).
Solution
Let \(P\) be the set of all proper filters on \(X\) containing \(\mathcal{F}\), ordered by \(\subseteq\); \(P \neq \varnothing\) since \(\mathcal{F} \in P\). Given a chain \(C = \{\mathcal{F}_\alpha\}\) of such filters, let \(\mathcal{G} = \bigcup_\alpha \mathcal{F}_\alpha\). Check \(\mathcal{G}\) is a filter: it is nonempty (contains \(\mathcal{F}\)); if \(A, B \in \mathcal{G}\) then \(A \in \mathcal{F}_\alpha\), \(B \in \mathcal{F}_\beta\) for some \(\alpha,\beta\), and since \(C\) is a chain WLOG \(\mathcal{F}_\alpha \subseteq \mathcal{F}_\beta\), so \(A, B \in \mathcal{F}_\beta\), giving \(A \cap B \in \mathcal{F}_\beta \subseteq \mathcal{G}\) by closure under finite intersection; upward closure is immediate since each \(\mathcal{F}_\alpha\) is upward closed. \(\mathcal{G}\) is proper since \(\varnothing \notin \mathcal{F}_\alpha\) for every \(\alpha\), hence \(\varnothing \notin \mathcal{G}\). So \(\mathcal{G} \in P\) bounds \(C\). By Zorn's Lemma \(P\) has a maximal element \(\mathcal{U}\), which is by definition a proper filter containing \(\mathcal{F}\) maximal among such — i.e. an ultrafilter extending \(\mathcal{F}\) (maximality among proper filters is precisely the standard characterization of an ultrafilter).
Explain the flaw in the following "proof" that \(\mathbb{R}\) (with its usual order) has a maximal element: "Consider \(P = \mathbb{R}\) under \(\leq\). Every chain in \(P\) is just a subset of \(\mathbb{R}\) totally ordered by \(\leq\) (automatic, since \(\leq\) totally orders \(\mathbb{R}\)); by completeness every bounded chain has a supremum, hence an upper bound, so by Zorn's Lemma \(\mathbb{R}\) has a maximal element."
Solution
The flaw is the parenthetical "every bounded chain" — the hypothesis of Zorn's Lemma requires every chain to have an upper bound, not every bounded one. The chain \(C = \mathbb{R}\) itself (or \(C = [0,\infty)\)) is unbounded above and has no supremum in \(\mathbb{R}\), so the chain-bound hypothesis fails outright, and Zorn's Lemma simply does not apply. Consistently with this, \(\mathbb{R}\) indeed has no maximal element (for any \(x\), \(x+1 \gt x\)). The error is a circular/invalid restriction of "every chain" to "every bounded chain," which silently assumes the very boundedness that was supposed to be verified for arbitrary chains.
Assuming Zorn's Lemma, prove the Well-Ordering Theorem is derivable, i.e. every set \(X\) admits a well-ordering. (Sketch the poset and the key steps; full rigor on the "gluing" step is expected.)
Solution
Let \(P\) be the set of pairs \((A, \leq_A)\) where \(A \subseteq X\) and \(\leq_A\) is a well-ordering of \(A\). Order \(P\) by: \((A,\leq_A) \preceq (B,\leq_B)\) iff \(A \subseteq B\), \(\leq_B\) restricted to \(A\) equals \(\leq_A\), and \(A\) is an initial segment of \(B\) under \(\leq_B\) (i.e. if \(b \in B\), \(a \in A\), \(b \leq_B a\), then \(b \in A\)). \(P \neq \varnothing\) since \((\varnothing, \varnothing)\) (the trivial well-ordering of the empty set) is in \(P\). Given a chain \(C = \{(A_\alpha, \leq_\alpha)\}\) in \(P\), let \(A = \bigcup_\alpha A_\alpha\) and define \(\leq_A\) by \(x \leq_A y\) iff \(x \leq_\alpha y\) for some (any, by the initial-segment compatibility) \(\alpha\) with \(x, y \in A_\alpha\); this is well-defined and gives a well-ordering of \(A\) because any nonempty subset \(S \subseteq A\) meets some \(A_\alpha\) nontrivially, and by the initial-segment property the \(\leq_\alpha\)-least element of \(S \cap A_\alpha\) for the smallest such \(\alpha\) (in the chain's order) is the \(\leq_A\)-least element of all of \(S\). One checks \((A,\leq_A) \in P\) bounds \(C\) above. By Zorn's Lemma \(P\) has a maximal element \((M, \leq_M)\). If \(M \neq X\), pick \(x_0 \in X \setminus M\) and extend \(\leq_M\) to \(M \cup \{x_0\}\) by declaring \(x_0\) the new top element (greater than everything in \(M\)); this is still a well-ordering (every nonempty subset either meets \(M\), giving the same least element as before, or is \(\{x_0\}\)), and \((M\cup\{x_0\}, \leq) \succ (M,\leq_M)\) with \(M\) an initial segment, contradicting maximality. Hence \(M = X\), and \(\leq_M\) well-orders \(X\).