The Well-Ordering Theorem for Ordinals

Every set of ordinals is well-ordered, and any two well-ordered sets are comparable: one is isomorphic to an initial segment of the other. This establishes ordinals as the canonical representatives of well-order types.

Statement

Theorem4.5Comparability of well-orderings

Let $(A, \leq_A)$ and $(B, \leq_B)$ be well-ordered sets. Then exactly one of the following holds:

$(A, \leq_A)$ is order-isomorphic to $(B, \leq_B)$ .
$(A, \leq_A)$ is order-isomorphic to an initial segment of $(B, \leq_B)$ .
$(B, \leq_B)$ is order-isomorphic to an initial segment of $(A, \leq_A)$ .

Moreover, any order-isomorphism between well-ordered sets is unique.

Proof

Step 1: Uniqueness of isomorphisms. Let $f, g: (A, \leq_A) \to (B, \leq_B)$ be order-isomorphisms. By transfinite induction on $A$ , we show $f = g$ . If $a$ is the least element of $A$ , both $f(a)$ and $g(a)$ must be the least element of $B$ . If $f(a') = g(a')$ for all $a' < a$ , then $f(a)$ and $g(a)$ must both be the least element of $B \setminus \{f(a') : a' < a\}$ , so $f(a) = g(a)$ .

Step 2: No well-ordered set is isomorphic to a proper initial segment of itself. Suppose $f: A \to A_b = \{a \in A : a < b\}$ is an order-isomorphism. Then $f(b) < b$ . Define $c = f(b)$ , then $f(c) < f(b) = c$ (since $f$ preserves order and $c < b$ ). Iterating: $b > f(b) > f^2(b) > \cdots$ , an infinite strictly decreasing sequence, contradicting well-ordering.

Step 3: Comparability. Define a partial isomorphism $f$ as follows: by transfinite recursion on $A$ , set $f(a) =$ the least element of $B \setminus f[\{a' : a' < a\}]$ , if such an element exists. The domain of $f$ is an initial segment of $A$ , and the range is an initial segment of $B$ .

If $\mathrm{dom}(f) = A$ and $\mathrm{ran}(f) = B$ : Case 1. If $\mathrm{dom}(f) = A$ and $\mathrm{ran}(f) = B_b$ for some $b$ : Case 2. If $\mathrm{dom}(f) = A_a$ and $\mathrm{ran}(f) = B$ : Case 3. If $\mathrm{dom}(f) = A_a$ and $\mathrm{ran}(f) = B_b$ : impossible, since we could extend $f$ by $f(a) = b$ . $\blacksquare$

■

Consequences

Theorem4.6Every well-ordered set is isomorphic to a unique ordinal

For every well-ordered set $(A, \leq)$ , there exists a unique ordinal $\alpha$ and a unique order-isomorphism $f: (A, \leq) \to (\alpha, \in)$ . The ordinal $\alpha$ is called the order type of $(A, \leq)$ , written $\mathrm{otype}(A, \leq) = \alpha$ .

ExampleOrder types

$\mathrm{otype}(\{3, 7, 15\}, \leq) = 3$ (any finite set of size $n$ has order type $n$ ).
$\mathrm{otype}(\mathbb{N}, \leq) = \omega$ .
$\mathrm{otype}(\{0, 1, 2, \ldots\} \cup \{*\}$ , where $n < *$ for all $n) = \omega + 1$ .
$\mathrm{otype}(\mathbb{N} \times \{0, 1\}$ , lex order $) = \omega \cdot 2$ .

RemarkThe Burali-Forti paradox

The class of all ordinals $\mathbf{Ord}$ is not a set. If it were, it would itself be a transitive set well-ordered by $\in$ , hence an ordinal $\Omega$ . But then $\Omega \in \Omega$ , which contradicts the axiom of foundation (and well-ordering). This is the Burali-Forti paradox, the first of the set-theoretic paradoxes involving "too large" collections.