Lesson 5

We are now fully prepared to prove the theorem comparing well-ordered sets. Theorem. Let \(A\) and \(B\) be two well-ordered sets. Then either \(A\) is isomorphic to an initial segment of \(B\), or \(B\) is isomorphic to an initial segment of \(A\).

Note that an initial segment may coincide with the entire set, so the case where \(A\) and \(B\) are isomorphic is also covered by this theorem.

Proof. Define a mapping \(f\) from \(A\) to \(B\) by the following recursive rule: for each \(a \in A\), \[f(a) \text{ is the least element of }B \text{ not appearing among the values }f(a') \text{ for }a' < a.\] This rule is undefined in the case where the values \(f(a')\) for \(a' < a\) already exhaust all of \(B\). By applying the previous Theorem, we obtain a function \(f\) consistent with this rule.

Now we consider two cases:

• The function \(f\) is defined on all of \(A\). Note that the recursive definition guarantees monotonicity, since \(f(a)\) is defined as the least unused element; the larger \(a\) is, the fewer unused elements remain, and hence the minimal unused element can only increase. (The definition also ensures that no two values are equal.)
  It remains to verify that the image \(f(A)\) is an initial segment of \(B\). Indeed, suppose \(b < f(a)\) for some \(a \in A\). Then we must check that \(b\) also lies in the image of \(f\). But according to the recursive rule, \(f(a)\) is the least unused element of \(B\), so \(b\) must have already been used—i.e., \(b = f(a')\) for some \(a' < a\).


• The function \(f\) is defined only on some initial segment \([0, a)\) of \(A\). In this case, the initial segment \([0, a)\) is isomorphic to \(B\), and the function \(f\) is the required isomorphism. Indeed, if \(f(a)\) is undefined, then all elements of \(B\) appear among the values of \(f\). On the other hand, \(f\) preserves order by virtue of the recursive definition.