Mathematics

Zorn's Lemma and the Axiom of Choice: The Most Controversial Axiom

We explore the Axiom of Choice, its equivalence with Zorn's Lemma and the Well-Ordering Principle, the controversies surrounding it, and its indispensable role throughout modern mathematics.

Set Theory Foundations

The Three Equivalents

The following three statements are equivalent (over ZF set theory):

Axiom of Choice (AC): For every collection of nonempty sets $\{A_i\}_{i \in I}$ , there exists a function $f: I \to \bigcup_{i \in I} A_i$ with $f(i) \in A_i$ for all $i$ .

Zorn's Lemma: If every chain in a partially ordered set $(P, \leq)$ has an upper bound in $P$ , then $P$ has a maximal element.

Well-Ordering Principle: Every set can be well-ordered.

The equivalence was established through work by Zermelo (1904, 1908), Kuratowski (1922), and Zorn (1935).

The Axiom of Choice: What It Says

For a finite collection of nonempty sets, the existence of a choice function is trivially provable in ZF. The Axiom of Choice is needed only when the collection is infinite — and particularly when there is no uniform rule for picking elements.

Bertrand Russell's shoes-and-socks analogy: Given infinitely many pairs of shoes, you can choose one from each pair without AC — just say "take the left shoe." But given infinitely many pairs of socks (which are indistinguishable), you need AC to make infinitely many simultaneous choices.

Formally, AC asserts the existence of a choice function without specifying how to construct one. This non-constructive nature is the root of the controversy.

Zorn's Lemma in Detail

Key Definitions

A partially ordered set (poset) $(P, \leq)$ has a relation $\leq$ that is reflexive, antisymmetric, and transitive.

A chain in $P$ is a totally ordered subset: for any $a, b$ in the chain, either $a \leq b$ or $b \leq a$ .

A maximal element $m \in P$ satisfies: if $m \leq x$ then $x = m$ .

An upper bound of a chain $C$ is an element $u \in P$ with $c \leq u$ for all $c \in C$ .

The Statement

Zorn's Lemma. Let $(P, \leq)$ be a nonempty partially ordered set. If every chain in $P$ has an upper bound in $P$ , then $P$ contains at least one maximal element.

Proof that AC $\Rightarrow$ Zorn's Lemma

Proof sketch.

Assume AC. Let $(P, \leq)$ satisfy the chain condition. For each chain $C$ in $P$ that is not maximal (i.e., $C$ has a strict upper bound), use AC to choose a strict upper bound $f(C)$ — an element $f(C) \in P$ with $c < f(C)$ for all $c \in C$ .

Build a chain by transfinite induction:

$x_0$ = some element of $P$
$x_{\alpha+1} = f(\{x_\beta : \beta \leq \alpha\})$ if the chain is not maximal
At limit ordinals, take the union of the chain so far

If this process never terminates, we build a chain indexed by all ordinals that injects into $P$ — contradicting $P$ being a set. Therefore, at some ordinal the chain must be maximal, and the corresponding element is a maximal element of $P$ . $\square$

Applications of Zorn's Lemma

Zorn's Lemma is the mathematician's tool of choice (no pun intended) for proving existence of maximal objects. Here are some of its most important applications.

Every Vector Space Has a Basis

Theorem. Every vector space $V$ over a field $F$ has a (Hamel) basis.

Proof. Let $P$ be the set of all linearly independent subsets of $V$ , ordered by inclusion. Every chain in $P$ has an upper bound (their union, which is still linearly independent). By Zorn's Lemma, $P$ has a maximal element $B$ . This $B$ must span $V$ — if not, we could add another vector, contradicting maximality. $\square$

Every Ring Has a Maximal Ideal

Theorem. Every ring $R$ with $1 \neq 0$ has a maximal ideal.

Proof. Let $P$ be the set of proper ideals of $R$ , ordered by inclusion. Every chain of proper ideals has an upper bound (their union, which is proper since $1$ is not in any ideal in the chain). Zorn gives a maximal element. $\square$

The Hahn-Banach Theorem

The Hahn-Banach extension theorem in functional analysis — extending bounded linear functionals from subspaces to the whole space — relies on Zorn's Lemma applied to the poset of extensions.

Tychonoff's Theorem

Tychonoff's theorem (arbitrary products of compact spaces are compact) is equivalent to AC.

The Well-Ordering Principle

A well-ordering on a set $S$ is a total order $\leq$ such that every nonempty subset has a least element.

The Well-Ordering Principle states that every set can be equipped with a well-ordering — including $\mathbb{R}$ .

This is perhaps the most counterintuitive form of AC. Can you well-order the real numbers? AC says yes, but no one can write down such an ordering. In fact, it is consistent with ZFC that no explicitly definable well-ordering of $\mathbb{R}$ exists.

Proof that Zorn's Lemma $\Rightarrow$ AC

Proof.

Given a collection $\{A_i\}_{i \in I}$ of nonempty sets, let $P$ be the set of partial choice functions — functions $f$ defined on a subset $J \subseteq I$ with $f(i) \in A_i$ for $i \in J$ .

Order $P$ by extension: $f \leq g$ iff $g$ extends $f$ (i.e., $\operatorname{dom}(f) \subseteq \operatorname{dom}(g)$ and $g|_{\operatorname{dom}(f)} = f$ ).

Every chain in $P$ has an upper bound (take the union). By Zorn's Lemma, $P$ has a maximal element $f^*$ .

If $\operatorname{dom}(f^*) \neq I$ , pick $i_0 \in I \setminus \operatorname{dom}(f^*)$ and any $a \in A_{i_0}$ to extend $f^*$ — contradicting maximality.

Therefore $\operatorname{dom}(f^*) = I$ , and $f^*$ is a choice function. $\square$

The Controversy

The Axiom of Choice has been debated since Zermelo first used it explicitly in 1904.

Arguments For AC

It is intuitive: of course you can choose one element from each nonempty set.
It is indispensable: without AC, every vector space might not have a basis, the Hahn-Banach theorem fails, and algebra loses many fundamental results.
It is consistent: Gödel (1940) showed AC is consistent with ZF (if ZF is consistent).

Arguments Against AC

It is non-constructive: it asserts existence without providing a method.
It produces paradoxes: the Banach-Tarski paradox, non-measurable sets.
It can be counterintuitive: well-ordering $\mathbb{R}$ is difficult to accept.

The Independence Result

Paul Cohen (1963) proved that AC is independent of ZF: it can neither be proved nor disproved from the other axioms. Mathematicians are free to accept or reject it.

In practice, the overwhelming majority of mathematicians accept AC (or at least ZFC), while being aware of where it is used.

Consequences with and without AC

With AC (ZFC)

Every vector space has a basis
Every ring has a maximal ideal
Tychonoff's theorem holds
Non-measurable sets exist
Banach-Tarski paradox

Without AC (just ZF)

Some vector spaces have no basis
Some rings have no maximal ideal
Tychonoff fails for infinite products
All sets of reals can be measurable (in some models)
No Banach-Tarski

Summary

\begin{aligned} &\text{Axiom of Choice} \iff \text{Zorn's Lemma} \iff \text{Well-Ordering Principle} \\[8pt] &\text{Applications: bases, maximal ideals, Hahn-Banach, Tychonoff, \ldots} \\[8pt] &\text{Status: independent of ZF (Gödel 1940, Cohen 1963)} \\[8pt] &\text{Accepted by most mathematicians, with awareness of its consequences} \end{aligned}

References

Jech, T., The Axiom of Choice, North-Holland, 1973. Reprinted by Dover, 2008.
Jech, T., Set Theory, 3rd edition, Springer, 2003.
Herrlich, H., Axiom of Choice, Springer Lecture Notes in Mathematics 1876, 2006.
Wikipedia — Axiom of choice
Wikipedia — Zorn's lemma
Stanford Encyclopedia of Philosophy — The Axiom of Choice

Back to all posts