Zorn's Lemma

Zorn's Lemma is the standard existence engine wherever an infinite maximal or complete structure is asserted without an explicit algorithm to build it. In algebra, it produces bases of arbitrary vector spaces, maximal ideals in commutative rings (feeding directly into the definition of the spectrum $\mathrm{Spec}(R)$ in algebraic geometry), algebraic closures of fields, and transcendence bases of field extensions. In functional analysis, it underlies the Hahn–Banach theorem (extending a bounded linear functional while preserving a norm bound, via a maximal extension argument) and the existence of maximal orthonormal sets (Hilbert space bases) in infinite-dimensional Hilbert spaces. In topology, it is used to prove Tychonoff's theorem — that an arbitrary product of compact spaces is compact — via maximal filters or ultrafilters, and to show every filter extends to an ultrafilter. In order theory and logic itself, it gives the existence of maximal consistent extensions of theories (used in completeness proofs for first-order logic, via Lindenbaum's lemma) and maximal antichains in combinatorics of infinite posets. In graph theory, an infinite connected graph has a spanning tree by a Zorn's Lemma argument on the poset of forests ordered by inclusion of edge sets. Across all of these, the pattern is identical to the two worked examples above: define a poset of "partial approximations" ordered by extension, show unions along chains stay inside the class of approximations, and read off a maximal approximation as the desired complete object.

Ask the tutor: How does the proof that Zorn's Lemma implies the Axiom of Choice work in full detail, and what does the poset of "partial choice functions" look like?

Picture a poset as a landscape of dirt paths climbing a hillside, where $x \leq y$ means "you can walk from $x$ up to $y$." A chain is a single connected trail: any two points on it are comparable, so you can always tell which is further along. The hypothesis of Zorn's Lemma says that no matter how far you walk along any such trail — even one with no last step, climbing forever through infinitely many stages — there is always some point in the landscape sitting at or above the entire trail. Intuitively, no trail can escape to infinity without a ceiling somewhere above it. The conclusion says that under this hypothesis, the whole landscape has a peak: a point from which no further step is possible. This is not obvious, because the landscape may be infinite, may have no least element, and may not be well-ordered in any natural way. The proof strategy is to attempt to climb as high as possible, choosing at each stage a strictly higher point using the Axiom of Choice, and to show this climbing process must stop — not because we run out of steps in $\mathbb{N}$, but because it would otherwise produce a chain whose upper bound could be climbed past, contradicting that the bound already dominates the whole chain. A key subtlety: the hypothesis must give an upper bound for every chain, including the empty chain (which forces $P \neq \varnothing$) and chains with no largest element (like $\{1 - \tfrac1n : n \in \mathbb N\}$ inside $[0,1]$, whose upper bound $1$ need not be in the chain itself). The figure below shows a finite poset satisfying the hypothesis trivially (every chain is finite, hence has a maximum, which is an upper bound) and identifies its maximal elements, alongside a genuinely infinite example where the upper bound of an infinite chain is a new element not equal to any chain member.

Example 1: Every vector space has a basis (over an arbitrary field, arbitrary dimension). Let $V$ be a vector space over a field $K$, possibly infinite-dimensional and with no distinguished countable spanning set. We show $V$ has a basis, i.e., a linearly independent spanning subset. If $V = \{0\}$, the empty set is a basis; assume $V \neq \{0\}$. Let

partially ordered by inclusion $\subseteq$. This is a genuine partial order (inclusion is reflexive, antisymmetric, transitive). $P \neq \varnothing$: since $V \neq \{0\}$, pick any nonzero $v \in V$; then $\{v\}$ is linearly independent, so $\{v\} \in P$.

Checking the chain hypothesis. Let $\mathcal{C} \subseteq P$ be a chain (a collection of linearly independent subsets of $V$, totally ordered by inclusion). Let

We claim $U \in P$, i.e., $U$ is linearly independent, and $U$ is clearly an upper bound for $\mathcal C$ (each $S \subseteq U$). To check independence: suppose $v_1, \dots, v_n \in U$ are distinct and $c_1 v_1 + \cdots + c_n v_n = 0$ with $c_i \in K$. Each $v_i$ lies in some $S_i \in \mathcal{C}$. Since $\mathcal C$ is a chain and there are finitely many $S_1,\dots,S_n$, one of them — say $S_k$ — contains all the others (a finite chain under inclusion has a maximum, provable by induction on $n$: among finitely many totally ordered sets, compare pairwise and keep the larger). So $v_1, \dots, v_n \in S_k$, and since $S_k$ is linearly independent, $c_1 = \cdots = c_n = 0$. Hence $U$ is linearly independent, $U \in P$, and $U$ is an upper bound for $\mathcal C$ in $P$. (If $\mathcal C = \varnothing$, its upper bound is any element of $P$, e.g. $\{v\}$ above, or vacuously any element works since there is nothing to bound — take $\varnothing$, which is independent.)

Applying Zorn's Lemma. Every chain in $P$ has an upper bound in $P$, and $P \ne \varnothing$, so by Zorn's Lemma $P$ has a maximal element $B$.

$B$ is a basis. $B$ is linearly independent by construction ($B \in P$). Suppose $B$ does not span $V$; pick $w \in V \setminus \mathrm{span}(B)$. Then $B \cup \{w\}$ is linearly independent (a standard fact: if $w \notin \mathrm{span}(B)$ and $B$ is independent, then $B \cup \{w\}$ is independent — else some nontrivial combination $cw + \sum c_i b_i = 0$ with $b_i \in B$ would force $c \ne 0$, since otherwise $B$ itself would be dependent, giving $w = -c^{-1}\sum c_i b_i \in \mathrm{span}(B)$, a contradiction). So $B \cup \{w\} \in P$ and $B \subsetneq B \cup \{w\}$, contradicting maximality of $B$. Hence $B$ spans $V$, and $B$ is a basis. $\blacksquare$ Note the asymmetry deliberately built into this argument: $V$ is arbitrary, possibly with dimension larger than any cardinal one could enumerate, and no assumption of a spanning set or countability is used anywhere — the entire existence proof runs through the abstract chain/upper-bound check.

Example 2: Every nonzero commutative ring with identity has a maximal ideal. Let $R$ be a commutative ring with multiplicative identity $1 \ne 0$. (The hypothesis $1 \neq 0$ rules out the zero ring, which has no proper ideals at all.) Recall an ideal $I \subsetneq R$ is proper if $I \ne R$, equivalently $1 \notin I$. Let

ordered by inclusion. $P \ne \varnothing$ because $\{0\}$ is a proper ideal (as $1 \ne 0$, $1 \notin \{0\}$).

Checking the chain hypothesis. Let $\mathcal C \subseteq P$ be a nonempty chain of proper ideals, totally ordered by inclusion. (If $\mathcal C = \varnothing$, take $\{0\}$ as its upper bound.) Let

$J$ is an ideal. Let $a, b \in J$ and $r \in R$. Then $a \in I_1$, $b \in I_2$ for some $I_1, I_2 \in \mathcal C$; since $\mathcal C$ is a chain, one contains the other, say $I_1 \subseteq I_2$, so $a, b \in I_2$. Then $a - b \in I_2 \subseteq J$ and $ra \in I_2 \subseteq J$ (using that $I_2$ is an ideal). Also $0 \in J$ since $0 \in I$ for any $I \in \mathcal C$ (nonempty by assumption). So $J$ is an ideal. $J$ is proper. Suppose $J = R$. Then $1 \in J$, so $1 \in I$ for some $I \in \mathcal C$. But then $I$ contains $1$, forcing $I = R$ (for any $r \in R$, $r = r \cdot 1 \in I$ since ideals absorb multiplication), contradicting that $I$ is proper. So $1 \notin J$, i.e., $J \ne R$, so $J$ is proper. Thus $J \in P$, and clearly $I \subseteq J$ for every $I \in \mathcal C$, so $J$ is an upper bound for $\mathcal C$ in $P$.

Applying Zorn's Lemma. Every chain in $P$ has an upper bound in $P$, $P \ne \varnothing$, so by Zorn's Lemma, $P$ has a maximal element $\mathfrak m$.

$\mathfrak m$ is a maximal ideal. By construction $\mathfrak m$ is a proper ideal, and maximality in $P$ under inclusion means: no proper ideal strictly contains $\mathfrak m$. This is exactly the definition of a maximal ideal of $R$. $\blacksquare$ This example is structurally parallel to Example 1 (union along a chain gives the upper bound) but the "closure" property being preserved is different — proper-ness of an ideal versus linear independence — illustrating that the same Zorn's Lemma machinery adapts to entirely different closure properties, so long as arbitrary unions of chains preserve them.