21  Ordinal Arithmetic

For natural numbers we used the recursion theorem to define the arithmetic operations, and, subsequently, we proved that those operations are related to the operations of set theory in various desirable ways. Thus, for instance, we know that the number of elements in the union of two disjoint finite sets \(E\) and \(F\) is equal to \(\# (E) + \# (F)\). We observe now that this fact could have been used to define addition. If \(m\) and \(n\) are natural numbers, we could have defined their sum by finding disjoint sets \(E\) and \(F\), with \(\# (E) = m\) and \(\# (F) = n\), and writing \(m + n = \# (E \cup F)\).

Corresponding to what was done and to what could have been done for natural numbers, there are two standard approaches to ordinal arithmetic. Partly for the sake of variety, and partly because in this context recursion seems less natural, we shall emphasize the set-theoretic approach instead of the recursive one.

We begin by pointing out that there is a more or less obvious way of putting two well ordered sets together to form a new well ordered set. Informally speaking, the idea is to write down one of them and then to follow it by the other. If we try to say this rigorously, we immediately encounter the difficulty that the two sets may not be disjoint. When are we supposed to write down an element that is common to the two sets? The way out of the difficulty is to make the sets disjoint. This can be done by painting their elements different colors. In more mathematical language, replace the elements of the sets by those same elements taken together with some distinguishing object, using two different objects for the two sets. In completely mathematical language: if \(E\) and \(F\) are arbitrary sets, let \(\hat{E}\) be the set of all ordered pairs \((x, 0)\) with \(x\) in \(E\), and let \(\hat{F}\) be the set of all ordered pairs \((x,1)\) with \(x\) in \(F\). The sets \(\hat{E}\) and \(\hat{F}\) are clearly disjoint. There is an obvious one-to-one correspondence between \(E\) and \(\hat{E}\) \((x \rightarrow (x,0))\) and another one between \(F\) and \(\hat{F}\) \((x \rightarrow (x,1))\). These correspondences can be used to carry over whatever structure \(E\) and \(F\) may possess (for example, order) to \(\hat{E}\) and \(\hat{F}\). It follows that any time we are given two sets, with or without some additional structure, we may always replace them by disjoint sets with the same structure, and hence we may assume, with no loss of generality, that they were disjoint in the first place.

Before applying this construction to ordinal arithmetic, we observe that it can be generalized to arbitrary families of sets. If, indeed, \(\{ E_{i} \}\) is a family, write \(\hat{E}_{i}\) for the set of all ordered pairs \((x,i)\), with \(x\) in \(E_{i}\). (In other words, \(\hat{E}_{i} = E_{i} \times \{ i \}\).) The family \(\{ \hat{E}_{i} \}\) is pairwise disjoint, and it can do anything the original family \(\{ E_{i} \}\) could do.

Suppose now that \(E\) and \(F\) are disjoint well ordered sets. Define order in \(E \cup F\) so that pairs of elements in \(E\), and also pairs of elements in \(F\), retain the order they had, and so that each element of \(E\) precedes each element of \(F\). (In ultraformal language: if \(R\) and \(S\) are the given order relations in \(E\) and \(F\) respectively, let \(E \cup F\) be ordered by \(R \cup S \cup (E \times F)\).) The fact that \(E\) and \(F\) were well ordered implies that \(E \cup F\) is well ordered. The well ordered set \(E \cup F\) is called the ordinal sum of the well ordered sets \(E\) and \(F\).

There is an easy and worth while way of extending the concept of ordinal sum to infinitely many summands. Suppose that \(\{ E_{i} \}\) is a disjoint family of well ordered sets indexed by well ordered set \(I\). The ordinal sum of the family is the union \(\bigcup_{i}E_{i}\), ordered as follows. If \(a\) and \(b\) are elements of the union, with \(a \in E_{i}\) and \(b \in E_{j}\), then \(a < b\) means that either \(i < j\) or else \(i =j\) and \(a\) precedes \(b\) in the given order of \(E_{i}\).

The definition of addition for ordinal numbers is now child’s play. For each well ordered set \(X\), let \(\text{ord } X\) be the unique ordinal number similar to \(X\). (If \(X\) is finite, then \(\text{ord } X\) is the same as the natural number \(\# (X)\) defined earlier.) If \(\alpha\) and \(\beta\) are ordinal numbers, let \(A\) and \(B\) be disjoint well ordered sets with \(\text{ord } A = \alpha\) and \(\text{ord } B = \beta\), and let \(C\) be the ordinal sum of \(A\) and \(B\). The sum \(\alpha + \beta\) is, by definition, the ordinal number of \(C\), so that \(\text{ord } A + \text{ord } B = \text{ord } C\). It is important to note that the sum \(\alpha + \beta\) is independent of the particular choice of the sets \(A\) and \(B\); any other pair of disjoint sets, with the same ordinal numbers, would have given the same result.

These considerations extend without difficulty to the infinite case. If \(\{ \alpha_{i} \}\) is a well ordered family of ordinal numbers indexed by a well ordered set \(I\), let \(\{ A_{i} \}\) be a disjoint family of well ordered sets with \(\text{ord } A_{i} = \alpha_{i}\) for each \(i\), and let \(A\) be the ordinal sum of the family \(\{ A_{i} \}\). The sum \(\sum_{i \in I} \mathit{\ ord\ } A_{i}\) is, by definition, the ordinal number of \(A\), so that \(\sum_{i \in I} \mathit{\ ord\ } A_{i} = \mathit{\ ord\ } A\). Here too the final result is independent of the arbitrary choice of the well ordered sets \(A_{i}\); any other choices (with the same ordinal numbers) would have given the same sum.

Some of the properties of addition for ordinal numbers are good and others are bad. On the good side of the ledger are the identities

\[ \begin{aligned} \alpha + 0 &= \alpha, \\ 0 + \alpha &= \alpha, \\ \alpha + 1 &= \alpha^{+}, \end{aligned} \]

and the associative law

\[ \alpha + (\beta + \gamma) = (\alpha + \beta) + \gamma. \]

Equally laudable is the fact that \(\alpha < \beta\) if and only if there exists an ordinal number \(\gamma\) different from \(0\) such that \(\beta = \alpha + \gamma\). The proofs of all these assertions are elementary.

Almost all the bad behavior of addition stems from the failure of the commutative law. Sample: \(1 + \omega = \omega\) (but, as we saw just above, \(\omega + 1 \neq \omega\)). The misbehavior of addition expresses some intuitively clear facts about order. If, for instance, we tack a new element in front of an infinite sequence (of type \(\omega\)), the result is clearly similar to what we started with; but if we tack it on at the end instead, then we have ruined similarity; the old set had no last element but the new set has one.

The main use of infinite sums is to motivate and facilitate the study of products. If \(A\) and \(B\) are well ordered sets, it is natural to define their product as the result of adding \(A\) to itself \(B\) times. To make sense out of this, we must first of all manufacture a disjoint family of well ordered sets, each of which is similar to \(A\), indexed by the set \(B\). The general prescription for doing this works well here; all we need to do is to write \(A_{b} = A \times \{ b \}\) for each \(b\) in \(B\). If now we examine the definition of ordinal sum as it applies to the family \(\{ A_{b} \}\), we are led to formulate the following definition. The ordinal product of two well ordered sets \(A\) and \(B\) is the Cartesian product \(A \times B\) with the reverse lexicographic order. In other words, if \((a,b)\) and \((c, d)\) are in \(A \times B\), then \((a, b) < (c, d)\) means that either \(b < d\) or else \(b = d\) and \(a < c\).

If \(\alpha\) and \(\beta\) are ordinal numbers, let \(A\) and \(B\) be well ordered sets with \(\text{ord } A = \alpha\), and \(\text{ord } B = \beta\), and let \(C\) be the ordinal product of \(A\) and \(B\). The product \(\alpha \beta\) is, by definition, the ordinal number of \(C\), so that \((\text{ord } A)(\text{ord } B) = \text{ord } C\). The product is unambiguously defined, independently of the arbitrary choice of the well ordered sets \(A\) and \(B\). Alternatively, at this point we could have avoided any arbitrariness at all by recalling that the most easily available well ordered set whose ordinal number is \(\alpha\) is the ordinal number \(\alpha\) itself (and similarly for \(\beta\)).

Like addition, multiplication has its good and bad properties. Among the good ones are the identities

\[ \begin{aligned} \alpha 0 &= 0, \\ 0 \alpha &= 0, \\ \alpha 1 &= \alpha, \\ 1 \alpha &= \alpha, \end{aligned} \]

the associative law

\[ \alpha ( \beta \gamma) = ( \alpha \beta ) \gamma, \]

the left distributive law

\[ \alpha ( \beta +\gamma) = ( \alpha \beta ) + \alpha \gamma, \]

and the fact that if the product of two ordinal numbers is zero, then one of the factors must be zero. (Note that we use the standard convention about multiplication taking precedence over addition; \(\alpha \beta + \alpha \gamma\) denotes \((\alpha \beta) + (\alpha \gamma)\).)

The commutative law for multiplication fails, and so do many of its consequences. Thus, for instance, \(2 \omega = \omega\) (think of an infinite sequence of ordered pairs), but \(\omega 2 \neq \omega\) (think of an ordered pair of infinite sequences). The right distributive law also fails; that is \((\alpha + \beta) \gamma\) is in general different from \(\alpha \gamma + \beta \gamma\). Example: \((1 + 1) \omega = 2 \omega = \omega\), but \(1 \omega + 1 \omega = \omega + \omega = \omega 2\).

Just as repeated addition led to the definition of ordinal products, repeated multiplication could be used to define ordinal exponents. Alternatively, exponentiation can be approached via transfinite recursion. The precise details are part of an extensive and highly specialized theory of ordinal numbers. At this point we shall be content with hinting at the definition and mentioning its easiest consequences. To define \(\alpha^{\beta}\) (where \(\alpha\) and \(\beta\) are ordinal numbers), use definition by transfinite induction (on \(\beta\)). Begin by writing \(\alpha^{0} = 1\) and \(\alpha^{\beta + 1} = \alpha^{\beta} \alpha\); if \(\beta\) is a limit number, define \(\alpha^{\beta}\) as the supremum of the numbers of the form \(\alpha^{\gamma}\), where \(\gamma < \beta\). If this sketch of a definition is formulated with care, it follows that

\[ \begin{aligned} 0^{\alpha} &= 0 \quad (\alpha \ge 1), \\ 1^{\gamma} &= 1, \\ \alpha^{\beta + \gamma} &= \alpha^{\beta} \alpha^{\gamma}, \\ \alpha^{\beta \gamma} &= (\alpha^{\beta})^{\gamma}. \end{aligned} \]

Not all the familiar laws of exponents hold; thus, for instance, \(( \alpha \beta)^{\gamma}\) is in general different from \(\alpha^{\gamma} \beta^{\gamma}\). Example: \((2 \cdot 2)^{\omega} = 4^{\omega} = \omega\), but \(2^{\omega} \cdot 2^{\omega} = \omega \cdot \omega = \omega^{2}\).

Warning: the exponent notation for ordinal numbers, here and below, is not consistent with our earlier use of it. The unordered set \(2^{\omega}\) of all functions from \(\omega\) to \(2\), and the well ordered set \(2^{\omega}\) that is the least upper bound of the sequence of ordinal numbers \(2\), \(2 \cdot 2\), \(2 \cdot 2 \cdot 2\), etc., are not the same thing at all. There is no help for it; mathematical usage is firmly established in both camps. If, in a particular situation, the context does not reveal which of the two interpretations is to be used, then explicit verbal indication must be given.