19  Ordinal Numbers

The successor \(x^{+}\) of a set \(x\) was defined as \(x \cup \{ x \}\), and then \(\omega\) was constructed as the smallest set that contains \(0\) and that contains \(x^{+}\) whenever it contains \(x\). What happens if we start with \(\omega\), form its successor \(\omega^{+}\), then form the successor of that, and proceed so on ad infinitum? In other words: is there something out beyond \(\omega\), \(\omega^{+}\), \((\omega^{+})^{+}, \cdots\), etc., in the same sense in which \(\omega\) is beyond \(0\), \(1\), \(2\), \(\cdots\), etc.?

The question calls for a set, say \(T\), containing \(\omega\), such that each element of \(T\) (other than \(\omega\) itself) can be obtained from \(\omega\) by the repeated formation of successors. To formulate this requirement more precisely we introduce some special and temporary terminology. Let us say that a function \(f\) whose domain is the set of strict predecessors of some natural number \(n\) (in other words, \(dom f = n\)) is an \(\omega\)-successor function if \(f(0) = \omega\) (provided that \(n \neq 0\), so that \(0 < n\)), and \(f(m^{+}) = (f(m))^{+}\) whenever \(m^{+} < n\). An easy proof by mathematical induction shows that for each natural number \(n\) there exists a unique \(\omega\)-successor function with domain \(n\). To say that something is either equal to \(\omega\) or can be obtained from \(\omega\) by the repeated formation of successors means that it belongs to the range of some \(\omega\)-successor function. Let \(S(n,x)\) be the sentence that says “\(n\) is a natural number and \(x\) belongs to the range of the \(\omega\)-successor function with domain \(n\).” A set \(T\) such that \(x \in T\) if and only if \(S(n,x)\) is true for some \(n\) is what we are looking for; such a set is as far beyond \(\omega\) as \(\omega\) is beyond \(0\).

We know that for each natural number \(n\) we are permitted to form the set \(\{ x: S(n,x) \}\). In other words, for each natural number \(n\), there exists a set \(F(n)\) such that \(x \in F(n)\) if and only if \(S(n,x)\) is true. The connection between \(n\) and \(F(n)\) looks much like a function. It turns out, however that none of the methods of set construction that we have seen so far is sufficiently strong to prove the existence of a set \(F\) of ordered pairs such that \((n, y) \in F\) if and only if \(y = \{ x: S(n,x) \}\). To achieve this obviously desirable state of affairs, we need one more set-theoretic principle (our last). The new principle says, roughly speaking, that anything intelligent that one can do to the elements of a set yields a set.

Axiom 19.1 (Axiom of substitution) If \(S(a,b)\) is a sentence such that for each \(a\) in a set \(A\) the set \(\{ b: S(a, b) \}\) can be formed, then there exists a function \(F\) with domain \(A\) such that \(F(a) = \{ b: S(a,b) \}\) for each \(a\) in \(A\).

To say that \(\{ b: S(a,b) \}\) can be formed means, of course, that there exists a set \(F(a)\) such that \(b \in F(a)\) if and only if \(S(a,b)\) is true. The axiom of extension implies that the function described in the axiom of substitution is uniquely determined by the given sentence and the given set. The reason for the name of the axiom is that it enables us to make a new set out an old one by substituting something new for each element of the old.

The chief application of the axiom of substitution is in extending the process of counting far beyond the natural numbers. From the present point of view, the crucial property of a natural number is that it is a well ordered set such that the initial segment determined by each element is equal to that element. (Recall that if \(m\) and \(n\) are natural numbers, then \(m < n\) means \(m \in n\); this implies that \(\{ m \in \omega : m < n \} = n\).) This is the property on which the extended counting process is based; the fundamental definition in this circle of ideas is due to von Neumann. An ordinal number is defined as a well ordered set \(\alpha\) such that \(s( \xi ) = \xi\) for all \(\xi\) in \(\alpha\); here \(s( \xi )\) is, as before, the initial segment \(\{ \eta \in \alpha: \eta < \xi \}\).

An example of an ordinal number that is not a natural number is the set \(\omega\) consisting of all the natural numbers. This means that we can already “count” farther than we could before; whereas before the only numbers at our disposal were the elements of \(\omega\), now we have \(\omega\) itself. We have also the successor \(\omega^{+}\) of \(\omega\); this set is ordered in the obvious way, and, moreover, the obvious ordering is a well ordering that satisfies the condition imposed on ordinal numbers. Indeed, if \(\xi \in \omega^{+}\), then, by the definition of successor, either \(\xi \in \omega\), in which case we already know that \(s( \xi ) = \xi\), or else \(\xi = \omega\), in which case \(s( \xi ) = \omega\), by the definition of order, so that again \(s( \xi ) = \xi\). The argument just presented is quite general; it proves that if \(\alpha\) is an ordinal number, then so is \(\alpha^{+}\). It follows that our counting process extends now up to and including \(\omega\), and \(\omega^{+}\) and \((\omega^{+})^{+}\), and so on ad infinitum.

At this point we make contact with our earlier discussion of what happens beyond \(\omega\). The axiom of substitution implies easily that there exists a unique function \(F\) on \(\omega\) such that \(F(0) = \omega\) and \(F(n^{+}) = (F(n))^{+}\) for each natural number \(n\). The range of this function is a set of interest for us; a set of even greater importance is the union of the set \(\omega\) with the range of the function \(F\). For reasons that will become clear only after we have at least glanced at the arithmetic of ordinal numbers, that union is usually denoted by \(\omega 2\). If, borrowing again from the notation of ordinal arithmetic, we write \(\omega + n\) for \(F(n)\), then we can describe the set \(\omega 2\) as the set consisting of all \(n\) (with \(n\) in \(\omega\)) and of all \(\omega + n\) (with \(n\) in \(\omega\)).

It is now easy to verify that \(\omega 2\) is an ordinal number. The verification depends, of course, on the definition of order in \(\omega 2\). At this point both that definition and the proof are left as exercises; our official attention turns to some general remarks that include the facts about \(\omega 2\) as easy special cases.

An order (partial or total) in a set \(X\) is uniquely determined by its initial segments. If, in other words, \(R\) and \(S\) are orders in \(X\), and if, for each \(x\) in \(X\), the set of all \(R\)-predecessors of \(x\) is the same as the set of all \(S\)-predecessors of \(x\), then \(R\) and \(S\) are the same. This assertion is obvious whether predecessors are taken in the strict sense or not. The assertion applies, in particular, to well ordered sets. From this special case we infer that if it is possible at all to well order a set so as to make it an ordinal number, then there is only one way to do so. The set alone tells us what the relation that makes it an ordinal number must be; if that relation satisfies the requirements, then the set is an ordinal number, and otherwise it is not. To say that \(s( \xi ) = \xi\) means that the predecessors of \(\xi\) must be just the elements of \(\xi\). The relation in question is therefore simply the relation of belonging. If \(\eta < \xi\) is defined to mean \(\eta \in \xi\) whenever \(\xi\) and \(\eta\) are elements of a set \(\alpha\), then the result either is or is not a well ordering of \(\alpha\) such that \(s( \xi ) = \xi\) for each \(\xi\) in \(\alpha\), and is an ordinal number in the one case and not in the other.

We conclude this preliminary discussion of ordinal numbers by mentioning the names of the first few of them. After \(0\), \(1\), \(2\), \(\cdots\) comes \(\omega\), and after \(\omega\), \(\omega + 1\), \(\omega + 2\), \(\cdots\) comes \(\omega 2\). After \(\omega 2 + 1\) (that is, the successor of \(\omega 2\)) comes \(\omega 2 + 2\), and then \(\omega 2 + 3\); next after all the terms of the sequence so begun comes \(\omega 3\). (Another application of the axiom of substitution is needed at this point.) Next come \(\omega 3 + 1\), \(\omega 3 + 2\), \(\omega 3 + 3\), \(\cdots\), and after them comes \(\omega 4\). In this way we get successively \(\omega\), \(\omega 2\), \(\omega 3\), \(\omega 4\), \(\cdots\). An application of the axiom of substitution yields something that follows them all in the same sense in which \(\omega\) follows the natural numbers; that something is \(\omega^{2}\). After that the whole thing starts over again: \(\omega^{2} + 1\), \(\omega^{2} + 2\), \(\cdots\), \(\omega^{2} + \omega\), \(\omega^{2} + \omega + 1\), \(\omega^{2} + \omega + 2\), \(\cdots\), \(\omega^{2} + \omega 2\), \(\omega^{2} + \omega 2 + 1\), \(\cdots\), \(\omega^{2} + \omega 3\), \(\cdots\), \(\omega^{2} + \omega 4\), \(\cdots, \omega^{2} 2\), \(\cdots\), \(\omega^{2} 3\), \(\cdots\), \(\omega^{3}\), \(\cdots\), \(\omega^{4}\), \(\cdots\), \(\omega^{\omega}\), \(\cdots\), \(\omega^{(\omega^{\omega})}\), \(\cdots\), \(\omega^{(\omega^{(\omega^{\omega})})}\), \(\cdots\). The next one after all that is \(\varepsilon_{0}\); then come \(\varepsilon_{0} + 1\), \(\varepsilon_{0} +2\), \(\cdots\), \(\varepsilon_{0} + \omega\), \(\cdots\), \(\varepsilon_{0} + \omega 2\), \(\cdots\), \(\varepsilon_{0} + \omega^{2}\), \(\cdots\), \(\varepsilon_{0} + \omega^{\omega}\), \(\cdots\), \(\varepsilon_{0} 2\), \(\cdots\), \(\varepsilon_{0} \omega\), \(\cdots\), \(\varepsilon_{0} \omega^{\omega}\), \(\cdots\), \(\varepsilon_{0}^{2}\), \(\cdots \cdots \cdots\).