The Axiom of Choice, Zorn's Lemma, and Well-Ordering

• Axiom of Choice, Zorn's Lemma, and Well-Ordering Theorem are logically equivalent under ZF set theory—any one implies the others.
• AC is non-constructive: asserts existence without providing construction methods, enabling proofs in functional analysis and topology.
• AC underlies critical results: vector space bases, Hahn-Banach Theorem, and Tychonoff's Theorem essential to modern mathematics.
• Zermelo (1904) formulated AC to prove Well-Ordering; Zorn (1935) offered a more intuitive alternative formulation for applications.
• Cohen (1963) proved AC is independent of ZF axioms—neither provable nor disprovable from standard set theory foundations.
• Initial philosophical controversy persists: AC's non-constructive nature challenges mathematical existence without explicit construction methods.

The Axiom of Choice, Zorn's Lemma, and Well-Ordering

Overview

The Axiom of Choice (AC), Zorn's Lemma, and the Well-Ordering Theorem form a trinity of equivalent principles that lie at the foundation of modern mathematics. Each statement appears on the surface to be quite different—AC asserts the existence of choice functions, Zorn's Lemma provides maximal elements in partially ordered sets, and the Well-Ordering Theorem claims every set can be totally ordered. Yet remarkably, assuming the standard Zermelo-Fraenkel Set Theory|ZF axioms, any one of these principles implies the other two. This equivalence, established in the early 20th century, revolutionized mathematics by unifying diverse existence arguments under a common framework.

The Axiom of Choice is perhaps the most controversial axiom in mathematics. Unlike other axioms of Set Theory, AC is non-constructive: it asserts the existence of certain sets without providing a method to construct them. This has led to profound philosophical debates about the nature of mathematical existence. Despite initial resistance, AC has become indispensable in modern mathematics—it underlies the existence of bases for Vector Spaces, the Hahn-Banach Theorem in Functional Analysis, and Tychonoff's Theorem in Topology. Without AC, much of 20th-century mathematics would collapse.

The historical development of these principles reflects a fundamental shift in mathematical thinking. Georg Cantor implicitly used choice principles in his work on Cardinal Numbers in the 1890s. Ernst Zermelo explicitly formulated AC in 1904 to prove the Well-Ordering Theorem, sparking immediate controversy. Max Zorn introduced his lemma in 1935 as a more intuitive alternative for applications. The equivalence of these statements was gradually established, and Paul Cohen's work in 1963 proved that AC is independent of ZF—it can neither be proved nor disproved from the other axioms of set theory.

The Axiom of Choice, Zorn's Lemma, and the Well-Ordering Theorem are three logically equivalent formulations of the same fundamental principle: that existence doesn't require explicit construction. They transform problems about finding specific elements into problems about the structure of partial orders.

Core Theory

Equivalence of AC, ZL, and WO

1. The Axiom of Choice
2. Zorn's Lemma
3. The Well-Ordering Theorem

We prove the cyclic implications: AC $\Rightarrow$ WO $\Rightarrow$ ZL $\Rightarrow$ AC.

For each nonempty subset $S\subseteq X$, use AC to choose an element $f(S)\in S$. This defines a choice function on the power set $\mathcal{P}(X)\setminus \{\varnothing \}$.

We now define a function $g$ from an Ordinal Number|ordinal into $X$ by transfinite recursion: for ordinal $\alpha$, let $g(\alpha )=f(X\setminus \{g(\beta ):\beta <\alpha \})$ if $X\setminus \{g(\beta ):\beta <\alpha \}\ne \varnothing$, and undefined otherwise.

Since $X$ is a set, there is a least ordinal $\gamma$ where $g(\gamma )$ is undefined, meaning $X=\{g(\beta ):\beta <\gamma \}$. The map $\beta \mapsto g(\beta )$ for $\beta <\gamma$ provides a bijection between $\gamma$ and $X$. Transfer the well-ordering of $\gamma$ to $X$ via this bijection.

Assume for contradiction that $P$ has no maximal element. For each $x\in P$, the set $S_x=\{y\in P:x<y\}$ is nonempty (since $x$ is not maximal). Using the well-ordering $\prec$, each $S_x$ has a $\prec$-least element; call it $s(x)$.

Define a sequence by transfinite recursion: let $p_0$ be the $\prec$-least element of $P$, and for each ordinal $\alpha$, let $p_{\alpha +1}=s(p_{\alpha })$. For limit ordinals $\lambda$, the set $\{p_{\alpha }:\alpha <\lambda \}$ is a chain (by construction, $p_{\alpha }<p_{\beta }$ whenever $\alpha <\beta$), so it has an upper bound; let $p_{\lambda }$ be the $\prec$-least upper bound.

This construction defines $p_{\alpha }$ for all ordinals $\alpha$, giving an injection from the class of all ordinals into the set $P$, which is impossible by the Burali-Forti Paradox. Therefore, $P$ must have a maximal element.

Let $P$ be the set of all partial choice functions: $P=\{f:f\text{ is a function},\text{dom}(f)\subseteq I,f(i)\in X_i\text{ for all }i\in \text{dom}(f)\}$.

Order $P$ by extension: $f\le g$ if $f\subseteq g$ (i.e., $g$ extends $f$). Clearly $(P,\le )$ is a poset.

Let $C$ be any chain in $P$. Then $h={\bigcup }_{f\in C}f$ is a function (since the chain is totally ordered, there are no conflicts), and $h$ is an upper bound for $C$. Also, $P$ is nonempty (each single-valued function $\{i\}\to X_i$ is in $P$ since $X_i\ne \varnothing$).

By Zorn's Lemma, $P$ has a maximal element $g$. We claim $\text{dom}(g)=I$. If not, there exists $i_0\in I\setminus \text{dom}(g)$. Since $X_{i_0}\ne \varnothing$, we can choose $x_0\in X_{i_0}$ and extend $g$ to $g^{\prime }=g\cup \{(i_0,x_0)\}$, contradicting maximality. Thus $g$ is a choice function for the family. □

Examples and Applications

1

Let $P$ be the set of all linearly independent subsets of $V$, ordered by inclusion $\subseteq$. Then $P$ is nonempty (contains $\varnothing$).

Let $\mathcal{C}$ be a chain in $P$. Set $U={\bigcup }_{S\in \mathcal{C}}S$. We verify $U$ is linearly independent: suppose ${\sum }_{i=1}^n{a}_i{v}_i=0$ with $v_i\in U$ and $a_i\in F$. Each $v_i$ belongs to some $S_i\in \mathcal{C}$. Since $\mathcal{C}$ is a chain, one of the $S_i$ contains all others; call it $S_{\max }$. Then all $v_i\in S_{\max }$, which is linearly independent, so all $a_i=0$. Thus $U\in P$ and is an upper bound for $\mathcal{C}$.

By Zorn's Lemma, $P$ has a maximal element $B$. We claim $B$ is a basis. It's linearly independent by construction. If $B$ doesn't span $V$, there exists $v\in V$ not in $\text{span}(B)$. Then $B\cup \{v\}$ is linearly independent (if $av+{\sum }_i{a}_i{b}_i=0$ with $b_i\in B$, then $a=0$ else $v\in \text{span}(B)$, so $\sum a_i{b}_i=0$ implies all $a_i=0$), contradicting maximality. Therefore $B$ spans $V$ and is a basis.

2

Define an equivalence relation on $[0,1)$ by $x\sim y$ if $x-y\in \mathbb{Q}$. This partitions $[0,1)$ into uncountably many equivalence classes (each class is countable and dense in $[0,1)$).

By AC, there exists a set $V\subseteq [0,1)$ containing exactly one representative from each equivalence class (a choice function on the quotient).

Let $\{r_n\}$ enumerate $\mathbb{Q}\cap [-1,1]$. Define $V_n=\{v+r_n:v\in V\}$ (addition modulo 1 to stay in $[0,1)$ when necessary).

The sets $V_n$ are pairwise disjoint: if $v_1+r_i=v_2+r_j$ (mod 1), then $v_1-v_2\in \mathbb{Q}$, so $v_1\sim v_2$, hence $v_1=v_2$ and $r_i=r_j$.

Also, $[0,1)\subseteq {\bigcup }_n{V}_n$ (every $x$ is equivalent to some $v\in V$, so $x-v=r_n$ for some $n$).

If $V$ were Lebesgue measurable with measure $m(V)$, then by translation invariance, $m(V_n)=m(V)$ for all $n$. But then $1=m([0,1))\le {\sum }_{n}m(V_n)={\sum }_{n}m(V)$, which is $0$ if $m(V)=0$ and $\infty$ if $m(V)>0$, a contradiction. Thus $V$ is not measurable.

Indeed, $P$ has no maximal element: for any $1/n\in P$, we have $1/n<1/(n-1)$ when $n>1$, and $1/1$ is not maximal since it's comparable to all others.

This shows Zorn's Lemma does not apply when chains lack upper bounds in the poset. The conclusion (existence of maximal elements) genuinely fails.

Imagine climbing a mountain range where you can always see "upward" directions (elements greater than where you are). Zorn's Lemma says: if whenever you follow any path continuously upward (a chain), there's always a ledge above that entire path (upper bound), then you must eventually reach a peak (maximal element)—a point from which you cannot go higher.

The Axiom of Choice is like having an infinite set of boxes, each containing at least one ball. AC says you can simultaneously reach into every box and pull out one ball from each, even if there's no rule telling you which ball to pick. The controversy is that this doesn't tell you how to choose—it just asserts the choice is possible.

Well-ordering is the claim that no matter how chaotic a collection appears, you can always line it up "first, second, third, ..." so that every subcollection has an earliest member. For finite sets this is obvious, but AC implies you can do this even for sets like $\mathbb{R}$, though no one has ever explicitly written down such an ordering.

Historical Development

The Axiom of Choice emerged from Georg Cantor's work on Set Theory and Cardinal Arithmetic in the 1870s-1890s. Cantor implicitly used choice principles but never formulated them explicitly. The first explicit formulation came from Ernst Zermelo in 1904, who needed AC to prove that every set can be well-ordered. This proof appeared in "Beweis, daß jede Menge wohlgeordnet werden kann" and immediately sparked controversy.

Mathematicians split on AC's acceptability. Bertrand Russell, David Hilbert, and Henri Lebesgue initially supported it, while L.E.J. Brouwer, Émile Borel, and Henri Poincaré opposed its non-constructive nature. Borel called applications of AC to uncountable sets "beyond the domain of mathematics." The debate intensified when Giuseppe Vitali (1905) and Felix Hausdorff (1914) used AC to construct pathological objects like non-measurable sets and paradoxical decompositions.

Zermelo refined his axiomatization of set theory in 1908, incorporating AC as an explicit axiom (ZFC: Zermelo-Fraenkel with Choice). In 1935, Max Zorn introduced his lemma as a more applicable formulation while working on Ring Theory. He initially called it the "maximum principle," though it was soon recognized as equivalent to AC. Hausdorff had earlier (1914) formulated the Maximal Principle.

The independence of AC was suspected but not proved until Kurt Gödel (1938) showed AC is consistent with ZF (by constructing the Constructible Universe $L$ where AC holds), and Paul Cohen (1963) showed AC is independent of ZF using his Forcing technique. Cohen's work won the Fields Medal in 1966. This proved AC can neither be proved nor disproved from ZF alone—mathematicians are free to accept or reject it.

Connections to Other Areas

What You Need First

What This Opens Up

See Also