The Well-Ordering Theorem

The well-ordering theorem, equivalent to the axiom of choice, asserts that every set can be well-ordered. This powerful result was first proved by Zermelo in 1904 and was the original motivation for the explicit formulation of AC.

Statement

Theorem6.5Well-ordering theorem (Zermelo)

For every set $A$ , there exists a well-ordering $\leq$ on $A$ .

Proof from AC

Proof

Let $A$ be a set. By AC, fix a choice function $f: \mathcal{P}(A) \setminus \{\emptyset\} \to A$ with $f(S) \in S$ for every nonempty $S \subseteq A$ .

We construct a well-ordering by transfinite recursion. Define:

$a_0 = f(A)$ .
$a_{\alpha+1} = f(A \setminus \{a_\beta : \beta \leq \alpha\})$ , if $A \setminus \{a_\beta : \beta \leq \alpha\} \neq \emptyset$ .
For limit $\lambda$ : continue if $A \setminus \{a_\beta : \beta < \lambda\} \neq \emptyset$ .

This process must terminate at some ordinal $\theta$ when $A = \{a_\beta : \beta < \theta\}$ (since $A$ is a set and ordinals form a proper class). The resulting enumeration gives a well-ordering of $A$ with order type $\theta$ . $\blacksquare$

■

Proof that Well-Ordering Implies AC

Proof

Let $\{A_i\}_{i \in I}$ be a family of nonempty sets. Well-order $\bigcup_{i \in I} A_i$ by some well-ordering $\leq$ . Define $f(i) = \min_\leq(A_i)$ for each $i \in I$ . Since each $A_i$ is nonempty and well-ordered, the minimum exists. Then $f$ is a choice function. $\blacksquare$

■

Consequences

ExampleConsequences of the well-ordering theorem

Every set has a cardinality: If $A$ can be well-ordered with order type $\alpha$ , then $|A|$ is the initial ordinal $|\alpha|$ . Without well-ordering (in ZF without AC), cardinality is much harder to define.
Cardinal comparability: For any sets $A, B$ , either $|A| \leq |B|$ or $|B| \leq |A|$ . (Well-order both and compare.)
Infinite sets contain countable subsets: Well-order any infinite set $A$ ; the first $\omega$ elements form a countably infinite subset.

RemarkHistorical significance

Zermelo published his proof in 1904, provoking intense debate. The controversy centered on the choice function: critics (including Borel, Lebesgue, and Baire) objected to asserting the existence of an object without constructing it. This debate led Zermelo to axiomatize set theory (1908), making the axiom of choice explicit as a foundational principle. The independence results of Godel and Cohen eventually settled the question: AC is neither provable nor refutable from the other axioms.