The Well-Ordering Theorem

Ordinals

As a recap in ordinal theory, an ordinal $\alpha$ is any set which is transitive ($x \in \alpha \implies x \subseteq \alpha$) and $x \in y$ is a well-order in $\alpha$. If we denote $x + 1 = x \cup \{x\}$, it follows that if $\alpha$ is an ordinal, so is $\alpha + 1$. And if $S$ is a set of ordinals, $\bigcup S$ is also an ordinal. $\emptyset$ is an ordinal and we label it 0. Any nonzero ordinal is either a successor ($\alpha = \beta + 1$ for some ordinal $\beta$) or limit ordinal ($\alpha$ is the union of all ordinals $\beta \in \alpha$).

It then follows that the class of all ordinals is well-ordered by $x \in y$. This means any nonempty class of ordinals has a minimum element, and given any two ordinals $\alpha \ne \beta$, either $\alpha < \beta$ or $\alpha > \beta$, where the order here is $\in$. The transfinite recursion principle allows us to inductively construct transfinite sequences, which are essentially families indexed by some ordinal.

Given a well-ordered set $W$, we denote $W(x) = \{ y \in W \ : \ y < x \}$. We shall say two well-orders $W_1 \simeq W_2$ are isomorphic if there exists a bijective function $f : W_1 \to W_2$ which is order-preserving. The isomorphism theorem of well-orders states that, given any $W_1,W_2$ well-ordered sets, one of three cases will always happen:

1. $W_1 \simeq W_2$

2. $W_1(x) \simeq W_2$ for some $x \in W_1$

3. $W_1 \simeq W_2(y)$ for some $y \in W_2$

Since the class of ordinals is a proper class, and every ordinal itself is well-ordered, we have the main result that every well-ordered set must be isomorphic to some ordinal.

Cardinals

If we denote the relation $\sim$ on the class of all sets to mean $X \sim Y$ iff there exists a bijection $f : X \to Y$, then this is an equivalence relation. A cardinal is any equivalence class of this relation. We shall denote the equivalence class containing $X$ (known as the cardinality of $X$) as $\card{X}$.

If we define a relation $X \le Y$ on the class of all sets to mean “there exists an injective function $f : X \to Y$”, then this relation is cardinality-preserving. This means, if $X \sim X'$ and $Y \sim Y'$, then $X \le Y \iff X' \le Y'$. Because of this, this relation can be induced into a relation on the cardinals, where $\card{X} \le \card{Y}$ iff $X \le Y$.

We have the following properties

1. (Reflexivity) $\card{X} \le \card{X}$

2. (Transitivity) If $\card{X} \le \card{Y}$ and $\card{Y} \le \card{Z}$, then $\card{X} \le \card{Z}$.

3. (Antisymmetry) If $\card{X} \le \card{Y}$ and $\card{Y} \le \card{X}$, then $\card{X} = \card{Y}$. This follows from the Cantor-Schröder-Bernstein theorem.

Evidently, this proves $\le$ is a partial order on the set of cardinals. But if we now inspect the set of ordinals, we know that every ordinal must lie inside a cardinal. By transfinite recursion, we can define the initial ordinals, which are ordinals $\alpha$ such that for all $\beta < \alpha$, we have $\card{\beta} < \card{\alpha}$ (meaning it is the smallest ordinal representing its cardinality).

Every ordinal has a corresponding unique initial ordinal which has the same cardinality, but the converse isn’t true in ZF theory. Similarly, every set $X$ can be associated with a least ordinal $\alpha$ such that $\alpha \not\le X$ (in the sense that no injective function $f : \alpha \to X$ exists), which is known as Hartogs number and can be proven with ZF theory. But in ZF theory, that doesn’t imply $X \le \alpha$, since we can’t use this fact to effectively construct an injective function $f : X \to \alpha$.

Well-ordering theorem

All of the results above are true under ZF, even without the axiom of regularity. We now introduce different versions of the well-ordering theorem (which is only a theorem assuming some other version of the axiom of choice).

Well-ordering theorem. Every set can be well-ordered.

Proposition. The following statements are all equivalent.

1. Every set can be well-ordered.

2. Axiom of choice

3. Every set is bijective to some ordinal.

4. Every cardinal contains some initial ordinal.

5. The $\le$ relation on cardinals is a total order.

Proof. (1) ⇒ (2) If $\bigcup X$ can be well-ordered, then every element of $X$ has a least element. Thus, the map $f : X \setminus \emptyset \to \bigcup X$ defined as $f(x) = \min x$ is a choice function.

(2) ⇒ (3) Let $f$ be a choice function on $\mathcal{P}(X)$. By transfinite recursion, let $x_0 \in X$ be anything, and for any ordinal $\alpha \ge 1$,

$$x_\alpha = f\left(X \setminus \bigcup_{\beta < \alpha} x_\beta\right)$$

unless $X = \bigcup_{\beta < \alpha} x_\beta$, in which case just let $x_\alpha = x_0$. This must happen eventually, as otherwise this would be an injective sequence from all ordinals to $X$ (making $X$ a proper class). If $\alpha > 0$ is the least ordinal where $x_\alpha = x_0$, then $(x_\beta)_{\beta < \alpha}$ is an injective transfinite sequence and contains every element of $X$, so $g : \alpha \to X$ defined as $g(\beta) = x_\beta$ is bijective.

(3) ⇒ (4) Let $\kappa$ be a cardinal and $X \in \kappa$. If $X$ is bijective to $\alpha$, then it must be bijective to the initial ordinal $\alpha_0$ associated with $\alpha$, so $\alpha_0 \in \card{X} = \kappa$.

(4) ⇒ (5) Let $\kappa$ and $\kappa'$ be cardinals with respective initial ordinals $\alpha \in \kappa$ and $\alpha' \in \kappa'$. Then $\alpha \le \alpha' \implies \kappa \le \kappa'$ and $\alpha' \le \alpha \implies \kappa' \le \kappa$. Since the ordinals are totally-ordered, so are the cardinals.

(5) ⇒ (1) Let $\alpha$ be the Hartogs number of a set $X$. Since $\alpha \not\le X$, by totality, there must be an injective function $f : X \to \alpha$. But then $f(X)$, being a subset of an ordinal, must be well-ordered, which induces a well-order on $X$ where $x < y \iff f(x) < f(y)$. $\square$