20  Sets of Ordinal Numbers

An ordinal number is, by definition, a special kind of well ordered set; we proceed to examine its special properties.

The most elementary fact is that each element of an ordinal number \(\alpha\) is at the same time a subset of \(\alpha\). (In other words, every ordinal number transitive set.) Indeed, if \(\xi \in \alpha\), then the fact that \(s( \xi ) = \xi\) implies that each element of \(\xi\) is a predecessor of \(\xi\) in \(\alpha\) and hence, in particular, an element of \(\alpha\).

If \(\xi\) is an element of an ordinal number \(\alpha\), then, as we have just seen, \(\xi\) is a subset of \(\alpha\), and, consequently, \(\xi\) is a well ordered set (with respect to the ordering it inherits from \(\alpha\)). Assertion: \(\xi\) is in fact an ordinal number. Indeed, if \(\eta \in \xi\), then the initial segment determined by \(\eta\) in \(\xi\) is the same as the initial segment determined by \(\eta\) in \(\alpha\); since the latter is equal to \(\eta\), so is the former. Another way of formulating the same result is to say that every initial segment of an ordinal number is an ordinal number.

The next thing to note is that if two ordinal numbers are similar, then they are equal. To prove this, suppose that \(\alpha\) and \(\beta\) are ordinal numbers and that \(f\) is a similarity from \(\alpha\) onto \(\beta\); we shall show that \(f( \xi ) = \xi\) for each \(\xi\) in \(\alpha\). The proof is a straightforward transfinite induction. Write \(S = \{ \xi \in \alpha : f( \xi ) = \xi \}\). For each \(\xi\) in \(\alpha\), the least element of \(\alpha\) that does not belong to \(s( \xi )\) is \(\xi\) itself. Since \(f\) is a similarity, it follows that the least element of \(\beta\) that does not belong to the image of \(s( \xi )\) under \(f\) is \(f( \xi )\). These assertions imply that if \(s( \xi ) \subset S\), then \(f(\xi )\) and \(\xi\) are ordinal numbers with the same initial segments, and hence that \(f(\xi ) = \xi\). We have proved thus that \(\xi \in S\) whenever \(s( \xi ) \subset S\). The principle of transfinite induction implies that \(S = \alpha\) and from this it follows that \(\alpha = \beta\).

If \(\alpha\) and \(\beta\) are ordinal numbers, then, in particular, they are well ordered sets, and, consequently, either they are similar or else one of them is similar to an initial segment of the other. If, say, \(\beta\) is similar to an initial segment of \(\alpha\), then \(\beta\) is similar to an element of \(\alpha\). Since every element of \(\alpha\) is an ordinal number, it follows that \(\beta\) is an element of \(\alpha\), or, in still other words, that \(\alpha\) is a continuation of \(\beta\). We know by now that if \(\alpha\) and \(\beta\) are distinct ordinal numbers, then the statements

\[ \begin{gathered} \beta \in \alpha, \\ \beta \subset \alpha, \\ \alpha \mathit{\ is\ a\ continuation\ of\ } \beta, \end{gathered} \]

are all equivalent to one another; if they hold, we may write

\[ \beta < \alpha. \]

What we have just proved is that any two ordinal numbers are comparable; that is, if \(\alpha\) and \(\beta\) are ordinal numbers, then either \(\beta = \alpha\), or \(\beta < \alpha\), or \(\alpha < \beta\).

The result of the preceding paragraph can be expressed by saying that every set of ordinal numbers is totally ordered. In fact more is true: every set of ordinal numbers is well ordered. Suppose indeed that \(E\) is a non-empty set of ordinal numbers, and let \(\alpha\) be an element of \(E\). If \(\alpha \le \beta\) for all \(\beta\) in \(E\), then \(\alpha\) is the first element of \(E\) and all is well. If this is not the case, then there exists an element \(\beta\) in \(E\) such that \(\beta < \alpha\), i.e., \(\beta \in \alpha\); in other words, then \(\alpha \cap E\) is not empty. Since \(\alpha\) is a well ordered set, \(\alpha \cap E\) has a first element, say \(\alpha_{0}\). If \(\beta \in E\), then either \(\alpha \le \beta\) (in which case \(\alpha_{0} < \beta\)), or \(\beta < \alpha\) (in which case \(\beta \in \alpha \cap E\) and therefore \(\alpha_{0} \le \beta\)), and this proves that \(E\) has a first element, namely \(\alpha_{0}\).

Some ordinal numbers are finite; they are just the natural numbers (i.e., the elements of \(\omega\)). The others are called transfinite; the set \(\omega\) of all natural numbers is the smallest transfinite ordinal number. Each finite ordinal number (other than \(0\)) has an immediate predecessor. If a transfinite ordinal number \(\alpha\) has an immediate predecessor \(\beta\), then, just as for natural numbers, \(\alpha = \beta^{+}\). Not every transfinite ordinal number does have an immediate predecessor; the ones that do not are called limit numbers.

Suppose now that \(\mathcal{C}\) is a collection of ordinal numbers. Since, as we have just seen, \(\mathcal{C}\) is a continuation chain, it follows that the union \(\alpha\) of the sets of \(\mathcal{C}\) is a well ordered set such that for every \(\xi\) in \(\mathcal{C}\), distinct from \(\alpha\) itself, \(\alpha\) is a continuation of \(\xi\). The initial segment determined by an element in \(\alpha\) is the same as the initial segment determined by that element whatever set of \(\mathcal{C}\) it occurs in; this implies that \(\alpha\) is an ordinal number. If \(\xi \in \mathcal{C}\), then \(\xi \le \alpha\); the number \(\alpha\) is an upper bound of the elements of \(\mathcal{C}\). If \(\beta\) is another upper bound of \(\mathcal{C}\), then \(\xi \subset \beta\) whenever \(\xi \in \mathcal{C}\), and therefore, by the definition of unions, \(\alpha \subset \beta\). This implies that \(\alpha\) is the least upper bound of \(\mathcal{C}\); we have proved thus that every set of ordinal numbers has a supremum.

Is there a set that consists exactly of all the ordinal numbers? It is easy to see that the answer must be no. If there were such a set, then we could form the supremum of all ordinal numbers. That supremum would be an ordinal number greater than or equal to every ordinal number. Since, however, for each ordinal number there exists strictly greater one (for example, its successor), this is impossible; it makes no sense to speak of the “set” of all ordinals. The contradiction, based on the assumption that there is such a set, is called the Burali-Forti paradox. (Burali-Forti was one man, not two.)

Our next purpose is to show that the concept of an ordinal number is not so special as it might appear, and that, in fact, each well ordered set resembles some ordinal number in all essential respects. “Resemblance” here is meant in the technical sense of similarity. An informal statement of the result is that each well ordered set can be counted.

Theorem 20.1 (Counting theorem) Each well ordered set is similar to a unique ordinal number.

Proof. Since for ordinal numbers similarity is the same as equality, uniqueness is obvious. Suppose now that \(X\) is a well ordered and suppose that an element \(a\) of \(X\) is such that the initial segment determined by each predecessor of \(a\) is similar to some (necessarily unique) ordinal number. If \(S(x, \alpha)\) is the sentence that says “\(\alpha\) is an ordinal number and \(s(x) \cong \alpha\),” then, for each \(x\) in \(s(a)\), the set \(\{ \alpha : S(x, \alpha ) \}\) can be formed; in fact, that set is a singleton. The axiom of substitution implies the existence of a set consisting exactly of the ordinal numbers similar to the initial segments determined by the predecessors of \(a\). It follows, whether \(a\) is the immediate successor of one of its predecessors or the supremum of them all, that \(s(a)\) is similar to an ordinal number. This argument prepares the way for an application of the principle of transfinite induction; the conclusion is that each initial segment in \(X\) is similar to some ordinal number. This fact, in turn, justifies another application of the axiom of substitution, just like the one made above; the final conclusion is, as desired, that \(X\) is similar to some ordinal number.