Natural Sums of Ordinals

Created in February 14, 2025

2025   ·   notes   ·   order-theory

The usual operations on ordinals are not well-behaved; commutativity, for example, doesn't hold in general. However, there are well-behaved versions of these operations, called the natural sums and natural products. In this post, I'll unravel the definitions of natural sums and explore their connection to the usual ordinal sum. I'll also discuss their order-theoretic interpretations. As usual, all references to papers and books will be listed at the bottom of this post. Let's dive in!

As a refresher, let's first look at the usual ordinal addition and multiplication. Recall that if $\alpha>0$ is an ordinal, then $\alpha = \{\gamma : \gamma<\alpha \text{ and } \gamma \text{ is an ordinal}\}$. Now, for ordinals $\alpha$ and $\beta$, we have the following definition for $\alpha + \beta $.

Definition 1: $\alpha + \beta = type\big((\{0\}\times\alpha)\cup (\{1\}\times\beta),<_{\alpha + \beta}\big)$, where $<_{\alpha+\beta}$ is the lexicographical ordering induced by the usual ordering $<$.

Let's look at an example; \(3+5=8\) as we have \[(0,0) <_{3+5} (0,1) <_{3+5} (0,2) <_{3+5} (1,0) <_{3+5} (1,1) <_{3+5} (1,2) <_{3+5} (1,3) <_{3+5} (1,4).\] Note that we used the fact that \(3=\{0,1,2\}\) and \(5=\{0,1,2,3,4\}\) here. From now on, I'll use \(<\) to represent the lexicographical ordering, as the context should make it clear.

Recall that $\omega = type\big((\mathbb{N},<)\big)$. So for example, the order type of $1+\omega$ is \[type\big((0,0)<(1,0)<(1,1)<(1,2)<\cdots\big) = \omega.\] So we have $1+\omega = \omega$. On the other hand $\omega+1 \neq \omega$ because what we get is \[(0,0)<(0,1)<(0,2)<\cdots<(1,0).\] This shows that the usual ordinal additional is not commutative.

Okay! I hope the definition is clear now. As most things in math, we can also define the usual addition using induction, or, more precisely, transfinite recursion. I will not discuss the principle of transfinite recursion here. Let's leave it for another post. Without any further ado:

Definition 2: Let $\alpha$ and $\beta$ be ordinals.

  1. $\alpha+0=\alpha$.
  2. $\alpha + (\beta +1) = (\alpha + \beta) +1$.
  3. For a limit ordinal $\gamma$, $\alpha+\gamma = \sup \{\alpha +\beta : \beta<\gamma\}$.

Of course, $\alpha$ and $\beta$ are ordinals in the above definition. Now, even though the usual addition didn't turn out to be commutative, it is indeed associative. We can easily show using the inductive definition that for all ordinals $\alpha,\beta,$ and $\gamma$, $(\alpha +\beta)+\gamma = \alpha + (\beta+\gamma)$. The induction argument happens in three steps; first, show for $0$, second, show for successors $\delta+1$ assuming the result is true for $\delta$, and thirdly and finally, show it's true for limits $\gamma$ assuming it's true for all $\delta<\gamma$. Of course, one may prove it using the first definition as well.

Now it's time to look at the definition of product. Let $\alpha$ and $\beta$ be two ordinals. Then:

Definition 3: $\alpha\cdot\beta$, that is the ordinal product of $\alpha$ and $\beta$, is $type\big(\beta\times \alpha,<_{\beta\times\alpha})\big)$, where $<_{\beta\times\alpha}$ is the lexicographical ordering on $\beta\times\alpha$. Here $\beta\times\alpha$ is the Cartesian product of $\beta$ and $\alpha$.

Let's look at some examples. Again I'll omit the subscript on the lexicographical ordering. We know $3\cdot 4 = 12$. This is because \[(0,0)<(0,1)<(0,2)<(1,0)<(1,1)<(1,2)<(2,0)<(2,1)<(2,2)<(3,0)<(3,1)<(3,2).\] In the same way, $\omega\cdot 2 = \omega +\omega$ and $2\cdot \omega = \omega$. We can view these two examples as two copies of omega, and omega copies of two, respectively. And this tells us that the usual multiplication of ordinals is not commutative.

The following result let's us define the usual ordinal multiplication inductively. Let $\alpha,\beta$ and $\gamma$ be ordinals. Then:

Fact: $\alpha \cdot (\beta +\gamma) = (\alpha \cdot \beta) + (\alpha \cdot \gamma)$.

Warning: However $(\alpha +\beta)\cdot \gamma = (\alpha \cdot \gamma) + (\beta \cdot \gamma)$ does not hold in general. Because \[(1+\omega)\cdot\omega = \omega\cdot\omega \neq \omega + \omega\cdot\omega = 1\cdot\omega +\omega\cdot\omega.\]

Now multiplication is defined inductively as follows. Let $\alpha,\beta$, and $\gamma$ be ordinals.

Definition 4: Let $\alpha$ and $\beta$ be ordinals.

  1. $\alpha\cdot 0 = 0$.
  2. $\alpha \cdot (\beta +1) =\alpha\cdot \beta +\alpha$.
  3. $\alpha \cdot \gamma = \sup \{\alpha\cdot \beta : \beta<\gamma\}$ for limit ordinals $\gamma$.

We will now look at something called the Cantor Normal Form of an ordinal number, that is:

Theorem (Cantor Normal Form): Any ordinal number $\alpha > 0$ can be written uniquely as $ \alpha = \omega^{\alpha_n} \cdot k_n + \cdots + \omega^{\alpha_0} \cdot k_0, $ where $n, k_0, \ldots, k_n \in {\mathbb{N}}^>$, and $\alpha \geq \alpha_n > \cdots > \alpha_0$ is a finite sequence of ordinals.

Since for any ordinal $\alpha$ and $k \in \mathbb{N}^>$, we have that $\omega^{\alpha} \cdot k$ equals $\omega^{\alpha}$ added to itself $k$-times, we can express the right-hand side of the equation in Cantor normal form as follows: $ \omega^{\alpha_n} + \cdots+ \omega^{\alpha_1} + \omega^{\alpha_0} $ for suitable $n \in \mathbb{N}^>$ and ordinals $\alpha_n\geq\cdots \geq \alpha_1 \geq \alpha_0$.

We are now ready to define the Hessenberg sum of two ordinals $\alpha$ and $\beta$. First, we write $\alpha,\beta$ in their Cantor Normal form. Say $$\alpha = \omega^{\alpha_n} \cdot r_n + \cdots + \omega^{\alpha_0} \cdot r_0$$ and $$\beta=\omega^{\beta_m}\cdot s_m+\cdots+\omega^{\beta_0}\cdot s_0,$$ where $n,m, r_1, \ldots, r_n,s_1,\ldots,s_m \in {\mathbb{N}}^>$, and $\alpha \geq \alpha_1 > \cdots > \alpha_n$, $\beta\geq \beta_1>\cdots \beta_m$ are ordinals. Then set $\gamma_k=\max(\alpha_n,\beta_m)$, where $k=\max(n,m)$. So we get, by introducing null-coefficients if we want, $$\alpha=\omega^{\gamma_k}\cdot u_k+\cdots+\omega^{\gamma_1}\cdot u_1+\omega^+\omega^{\gamma_0}\cdot u_0,$$ and $$\beta=\omega^{\gamma_k}\cdot v_k+\cdots+\omega^{\gamma_1}\cdot v_1+\omega^{\gamma_0}\cdot v_0,$$ where $k,u_k,\ldots,u_1,u_0,v_k,\ldots,v_1,v_0\in \mathbb{N}$ and $\gamma_k>\cdots>\gamma_1>\gamma_0$ are ordinals. We are now ready to define the Hessenberg sum of $\alpha$ and $\beta$. Let's denote it by $\alpha~{\#}~\beta$. Then:

Definition (Hessenberg Sum): \[ \alpha~\#~\beta=\omega^{\gamma_k}\cdot(u_k+v_k)+\cdots+\omega^{\gamma_1}\cdot(u_1+v_1)+\omega^{\gamma_0}\cdot (u_0+v_0).\]

Alright. Now let's look at a general notion of natural sums. According to Carruth [1], a binary operation $\oplus$ is a natural sum on the class of ordinals, if for all ordinals $\alpha,\beta$ and $\delta$ we have:

  1. $\alpha\oplus \beta =\beta \oplus \alpha$.
  2. $(\alpha \oplus \beta)\oplus\delta = \alpha \oplus (\beta\oplus \delta)$.
  3. $\alpha \oplus 0=\alpha$.
  4. $\delta\oplus \alpha >\delta\oplus \beta$ if and only if $\alpha>\beta$.

Note that by property (1) and (4), we get $\alpha \oplus \delta >\beta\oplus \delta$ if and only if $\alpha>\beta$. So these properties capture the idea of a ``natural" sum nicely; hence the name Natural Sum.

Now we define something called the ``mixed sum" also known as ``shuffled sum." We follow Lipparini's paper [2]. Let $\alpha,\beta$ and $\delta$ be ordinals as before. We say $\delta$ is the mixed sum of $\alpha$ and $\beta$ if:

  1. There are disjoint $A,B\subseteq \delta$ such that $\delta =A\cup B$, and
  2. $type_{\delta}(A)=\alpha$ and $type_{\delta}(B)=\beta$.

For instance, $type_\delta(A)$ means the order type of $A$ inherited by $\delta$. Note that if $A$ and $B$ are not disjoint, we can always take their join $A+B := (A\times\{0\}) \cup (B\times \{1\})$. Carruth [1] proves the following:

  1. $type_{\delta}(A + B)\leq \alpha\oplus \beta$.
  2. $type_{\delta}(A + B)=\alpha~\#~\beta$.
  3. $\alpha~\#~\beta\leq \alpha\oplus \beta$.
  4. $\alpha +\beta \leq \alpha \oplus \beta$.

From Carruth's theorem we get:

Theorem (Carruth): For any two ordinals $\alpha$ and $\beta$, the largest mixed sum of $\alpha$ and $\beta$ exists and equals $\alpha~\#~\beta$.

I'll end this post with the following example. We saw under usual ordinal addition that $1+\omega=\omega\neq \omega+1$. However, we have $1~\#~\omega=\omega~\#~1$. This is clear by definition of $\#$; remember the polynomial-like addition. On the other hand, if we write $A=\{0\}\times 1$ and $B=\{1\}\times\omega$, then the order type of the largest mixed sum of $1$ and $\omega$ is $\omega+1$, so $1~\#~\omega=\omega~\#~1$.

References

  1. Carruth, Philip W., 1942. Arithmetic of ordinals with applications to the theory of ordered Abelian groups
  2. Lipparini, Paolo, 2018. Some transfinite natural sums.