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

💡 The Core Insight

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.

Definition

The Axiom of Choice (AC): Let $\{X_i\}_{i \in I}$ be a family of nonempty sets indexed by a set $I$ . Then there exists a function $f: I \to \bigcup_{i \in I} X_i$ such that $f(i) \in X_i$ for all $i \in I$ . Such a function $f$ is called a choice function.

Zorn's Lemma (ZL): Let $(P, \leq)$ be a nonempty poset. If every chain (totally ordered subset) $C \subseteq P$ has an upper bound in $P$ , then $P$ contains at least one maximal element.

Well-Ordering Theorem (WO): Every set $X$ can be well-ordered; that is, there exists a total order $\leq$ on $X$ such that every nonempty subset of $X$ has a least element.

TheoremEquivalence of AC, ZL, and WO

Theorem [1]: Assuming ZF, the following are equivalent: 1. The Axiom of Choice 2. Zorn's Lemma 3. The Well-Ordering Theorem

Theorem [2] (Hausdorff Maximal Principle): Every chain in a poset is contained in a maximal chain. This is also equivalent to AC in ZF.

Proof

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

AC $\Rightarrow$ WO: Let $X$ be any set. We construct a well-ordering on $X$ using Transfinite Recursion. 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 \{\emptyset\}$ . We now define a function $g$ from an 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\} \neq \emptyset$ , 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.

WO $\Rightarrow$ ZL: Let $(P, \leq)$ be a nonempty poset where every chain has an upper bound. By WO, we can well-order $P$ with some ordering $\prec$ . 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.

ZL $\Rightarrow$ AC: Let $\{X_i\}_{i \in I}$ be a family of nonempty sets. We must construct a choice function. 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 \leq g$ if $f \subseteq g$ (i.e., $g$ extends $f$ ). Clearly $(P, \leq)$ 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 \neq \emptyset$ ). 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} \neq \emptyset$ , we can choose $x_0 \in X_{i_0}$ and extend $g$ to $g' = g \cup \{(i_0, x_0)\}$ , contradicting maximality. Thus $g$ is a choice function for the family. □

∎

⚠️ Common mistake

Common Misconception: Many students believe Zorn's Lemma guarantees a unique maximal element or a greatest element. In fact, ZL only guarantees the existence of at least one maximal element. A maximal element $m$ satisfies: there is no $x$ with $m < x$ , but there may be incomparable elements or multiple maximal elements. For example, in $(\mathcal{P}(\{1,2\})\setminus\{\{1,2\}\}, \subseteq)$ , both $\{1\}$ and $\{2\}$ are maximal. Also, the hypothesis that "every chain has an upper bound" is essential—without it, the conclusion fails.

mathematician

Ernst Zermelo (1904) — First explicitly formulated the Axiom of Choice and used it to prove the Well-Ordering Theorem, establishing AC as a fundamental principle of set theory despite immediate philosophical controversy.

visualization

Example1

Every vector space has a basis: Let $V$ be a vector space over a field $F$ . We use Zorn's Lemma to prove $V$ has a basis. Let $P$ be the set of all linearly independent subsets of $V$ , ordered by inclusion $\subseteq$ . Then $P$ is nonempty (contains $\emptyset$ ). 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.

Example2

Existence of non-measurable sets: Using AC, we construct a subset of $\mathbb{R}$ that is not Lebesgue measurable. 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)) \leq \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.

Counterexample

Why the chain hypothesis is necessary: Consider the poset $(P, \leq)$ where $P = \{1/n : n \in \mathbb{N}^+\}$ with the usual ordering. This poset has a chain $P$ itself (it's totally ordered), but this chain has no upper bound in $P$ (the supremum would be $\lim_{n\to\infty} 1/n = 0 \notin P$ ). 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.

🧠 Intuition

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.

connection

<span class="wiki-link-missing">Banach-Tarski Paradox</span>: One of the most counterintuitive consequences of AC is that a solid ball in $\mathbb{R}^3$ can be decomposed into finitely many pieces (five suffice) which can be rigidly moved (rotated and translated) to reassemble into two solid balls, each identical to the original. This uses AC via the existence of non-measurable sets. The construction relies on the Free Group $F_2$ acting on the sphere, with AC needed to construct the paradoxical decomposition. This demonstrates that AC, while essential for mainstream mathematics, leads to results that violate physical intuition about volume and matter.

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

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

Overview

Core Theory

Examples and Applications

Historical Development

Connections to Other Areas

What You Need First

What This Opens Up

See Also