Equivalents and Consequences of Choice

The equivalence of AC, ZL, and WOT underlies enormous swaths of modern mathematics precisely because different fields prefer different faces of the same axiom. In algebra, Zorn's Lemma is the standard route to maximal ideals in a ring with unity (hence to the existence of maximal ideals needed for quotient fields and localization), to the existence of a basis in every vector space (Example 1 above), to algebraic closures of fields, and to extending group homomorphisms via injective/divisible module arguments. In general topology, Zorn's Lemma proves the Tychonoff Theorem (arbitrary products of compact spaces are compact) via ultrafilters, and ultrafilter existence itself is a Zorn's Lemma application (extend a filter to a maximal one). In analysis, AC underlies the existence of non-measurable sets (Vitali sets) and of finitely-additive but not countably-additive measures on all subsets of $\mathbb{R}$; it also underlies the Hahn–Banach theorem in its general (not merely separable) form, proved via Zorn's Lemma on the poset of dominated linear extensions. In mathematical logic and model theory, the Well-Ordering Theorem and AC together justify the general Completeness Theorem for uncountable languages and the existence of models via ultraproducts. In combinatorics, order-extension (Example 2) is the infinite analog of topological sorting, used in the theory of dimension of posets. In computer science, choice principles appear at the meta-level in proofs that certain infinite-state systems have well-founded orderings enabling termination arguments, though computable analogues of AC are generally false or trivial, which is exactly why AC is a "pure existence" tool: it certifies that bases, maximal ideals, and well-orderings exist without providing algorithms to construct them, a tension that motivates the study of constructive mathematics and of weaker choice principles (countable choice, dependent choice) sufficient for most of analysis without the full strength — and strangeness — of general AC.

Ask the tutor: Can you show me why the "initial segment" condition, if dropped, also breaks Hartogs' Lemma's own proof — or is that proof immune to the same issue?

The three statements describe the same underlying power from different angles. AC says: given many nonempty boxes, you may simultaneously reach into all of them and pull out one item from each, even if there is no rule telling you which item — and even if there are infinitely many, even uncountably many, boxes. Zorn's Lemma says: if a poset has the property that every totally ordered "staircase" of elements can be capped off by something at least as high, then the whole poset has a top step somewhere — a maximal element, not necessarily unique, but one that cannot be improved upon. The Well-Ordering Theorem says: any set, no matter how unstructured, secretly admits an order in which every nonempty piece has a first element, just like the natural numbers. The bridge between these ideas is transfinite recursion. To go from AC to ZL, imagine trying to build a maximal element by greedily climbing: start anywhere, and at each step use a choice function to pick a strictly larger element if one exists. If this process ever had to run through all the ordinals without stopping, it would produce an injection from a proper-class-sized collection of ordinals into a single set — impossible, by Hartogs' theorem, since a set has only a set's worth of elements. So the climb must stop, and where it stops is a maximal element. The picture below shows this climb as a chain being extended rung by rung, forced to terminate because a set the size of $P$ cannot absorb arbitrarily many distinct ordinal-indexed rungs. To go from ZL to WOT, we look not at elements of $X$ but at partial well-orderings of subsets of $X$, ordered by "one order extends the other." A chain of such partial well-orderings has an upper bound — their union — and Zorn's Lemma hands us a maximal one. The only way such a maximal partial well-order could fail to cover all of $X$ is if some point were left out, in which case we could always extend it by tacking that point on top, contradicting maximality. So the maximal partial well-order must be a well-order of the whole set.

We prove this via the cycle $\text{AC} \Rightarrow \text{ZL} \Rightarrow \text{WOT} \Rightarrow \text{AC}$, which establishes all three equivalences.

Having shown $\mathrm{AC} \Rightarrow \mathrm{ZL} \Rightarrow \mathrm{WOT} \Rightarrow \mathrm{AC}$, all three statements are equivalent over ZF, completing the proof of the theorem. $\blacksquare$

Example 1: Every vector space has a basis. Let $V$ be a vector space over a field $F$ (allow $V = \{0\}$, allow $\dim V$ infinite — no finiteness assumption). We show $V$ has a basis, using ZL. Let $P$ be the set of all linearly independent subsets of $V$, partially ordered by inclusion $\subseteq$. Note $P \neq \emptyset$ since $\emptyset \in P$ (the empty set is linearly independent vacuously). Chains have upper bounds. Let $\mathcal{C} = \{L_i\}_{i\in I}$ be a chain in $P$ (a collection of linearly independent sets, totally ordered by $\subseteq$). Let $L = \bigcup_i L_i$. We claim $L$ is linearly independent. Suppose $c_1 v_1 + \cdots + c_n v_n = 0$ is a finite linear dependence among distinct $v_1,\dots,v_n \in L$ with not all $c_k = 0$. Each $v_k \in L_{i_k}$ for some $i_k$. Since $\mathcal{C}$ is a chain and there are finitely many indices $i_1,\dots,i_n$, one of the $L_{i_k}$ contains all the others (a finite chain under $\subseteq$ has a maximum), so all $v_1,\dots,v_n$ lie in a single $L_{i_k}$, which is linearly independent — contradicting the nontrivial relation. So $L$ has no nontrivial finite dependence: $L \in P$, and it is clearly an upper bound for $\mathcal{C}$ since $L_i \subseteq L$ for all $i$. By Zorn's Lemma, $P$ has a maximal element $B$: a linearly independent set contained in no strictly larger linearly independent set. $B$ spans $V$. Suppose not; pick $v \in V \setminus \mathrm{span}(B)$. We claim $B \cup \{v\}$ is linearly independent, contradicting maximality of $B$. Indeed if $c_0 v + c_1 b_1 + \cdots + c_n b_n = 0$ with $b_i \in B$ distinct and not all coefficients zero, then $c_0 \neq 0$ (else we'd get a nontrivial dependence among elements of $B$, contradicting independence of $B$), so

contradicting the choice of $v$. So $B \cup \{v\} \in P$ strictly contains $B$, contradicting maximality. Hence $B$ is a maximal linearly independent subset that also spans $V$: a basis. This argument used no special structure of $V$ — it works for the trivial space (basis $\emptyset$), a finite-dimensional space (recovers the usual basis extension argument), or a space like $\mathbb{R}$ viewed as a $\mathbb{Q}$-vector space, where an explicit basis (a Hamel basis) cannot be written down concretely at all; ZL guarantees existence without construction.

Example 2: The Order-Extension Principle (Szpilrajn's Theorem). Claim. Let $(X, \leq)$ be any partially ordered set. Then there exists a total order $\leq^*$ on $X$ extending $\leq$, meaning $x \leq y \implies x \leq^* y$ for all $x,y \in X$. Take $X = \{a,b,c,d\}$ with the partial order generated by $a \leq c$, $a \leq d$, $b \leq d$ (so $c$ and $b$ are incomparable, and $c, d$ are incomparable to each other where not forced) — an asymmetric, non-chain example illustrating a genuinely partial order. We construct a linear extension abstractly (the general proof) and note this example is completed by, e.g., $a \leq^* b \leq^* c \leq^* d$ or $a \leq^* c \leq^* b \leq^* d$; both are valid linear extensions, illustrating that the extension is not unique — Zorn's Lemma only guarantees existence of a maximal (here: total) extension. General proof, via ZL. Let $P$ be the set of all partial orders $R$ on $X$ that extend $\leq$ (i.e. $\leq \subseteq R$, as sets of pairs, and $R$ is reflexive, antisymmetric, transitive), ordered by inclusion of the relations: $R_1 \sqsubseteq R_2$ iff $R_1 \subseteq R_2$ as subsets of $X\times X$. Then $P \neq \emptyset$ since $\leq \in P$. Chains have upper bounds. If $\{R_i\}_{i \in I}$ is a chain in $P$, let $R = \bigcup_i R_i$. Reflexivity and containment of $\leq$ are immediate (each $R_i$ has them). Antisymmetry: if $(x,y), (y,x) \in R$ with $x \ne y$, they lie in some $R_i, R_j$; by the chain property one contains the other, say $R_i \subseteq R_j$, so both pairs lie in $R_j$, contradicting antisymmetry of $R_j$. Transitivity: if $(x,y),(y,z) \in R$, they lie in $R_i, R_j$ respectively; again one contains the other, say $R_j \subseteq R_i$, so both lie in $R_i$, giving $(x,z) \in R_i \subseteq R$ by transitivity of $R_i$. So $R \in P$, and it is an upper bound. By ZL, $P$ has a maximal element $R^*$. We must show $R^*$ is total: for every $x \neq y$ in $X$, either $(x,y) \in R^*$ or $(y,x) \in R^*$. Suppose not: there exist $x_0 \neq y_0$ with neither $(x_0,y_0)$ nor $(y_0,x_0)$ in $R^*$. Define

That is, $R'$ adds the pair $(x_0,y_0)$ together with all pairs forced by transitivity: everything below $x_0$ (in $R^*$) must now precede everything above $y_0$ (in $R^*$). $R'$ is a partial order extending $R^*$. Reflexivity and containment of $R^*$ (hence of $\leq$) are clear from the definition. Transitivity requires checking cases (e.g. $(u,v) \in R'\setminus R^*$ and $(v,w)\in R^*$ implies $u\,R^*\,x_0$, $y_0\,R^*\,v\,R^*\,w$, so $y_0\,R^*\,w$, so $(u,w)\in R'$) — each case reduces to transitivity of $R^*$ and the defining chain $u\,R^*\,x_0\,R'\,y_0\,R^*\,v$. Antisymmetry: if $R'$ had a cycle $(u,v),(v,u)\in R'$ with $u\ne v$, tracing through the construction one finds it forces $y_0\, R^*\, x_0$ together with $x_0\,R^*\,y_0$ already existing or being derivable, which would put $(y_0,x_0) \in R^*$ (using antisymmetry/transitivity of $R^*$) — contradicting our assumption that $(y_0,x_0) \notin R^*$. (This is the standard, slightly technical case-check underlying Szpilrajn's theorem; the key fact used is that $x_0, y_0$ are $R^*$-incomparable, so no cycle back through $R^*$ alone can reintroduce $(y_0,x_0)$.) Since $(x_0,y_0) \in R' \setminus R^*$, we have $R^* \sqsubsetneq R'$ and $R' \in P$, contradicting maximality of $R^*$. Hence $R^*$ is total, and $R^* = \,\leq^*$ is the desired linear extension of $\leq$. $\blacksquare$ This principle is used constantly: e.g., every poset embeds order-preservingly into a linear order, which is why "topological sorting" of a finite partial order (a DAG) is always possible — the finite case needs no choice at all, but the general infinite version genuinely requires it.