Ordinal addition

After we’ve met the order type of a well ordered set, we are finally ready to discuss about ordinal arithmetic. In this post I’ll present the term of addition. As I said in the previous post – It might not be as easy as you think.

“Almost” addition

Suppose that \alpha,\beta are ordinals. I am now going to define a new set:

\alpha\oplus \beta=\alpha\times\{0\}\cup\beta\times\{1\}

We can also describe the set as:

\alpha\oplus \beta=\{(a,0),(b,1)|a\in A,b\in B\}=\{(a,0)|a\in A\}\cup\{(b,1)|b\in B\}

The order on the set will be:

(a,b)<(c,d)\iff b< d\text{ or } (b=d \text{ and }a< c)

It seems a little complicated but it’s actually not:

Given two pairs, First we check if they have the same ‘index’ (which is 0 or 1). If they don’t, then the one with index 0 is smaller.

If they do have the same index, then they are both of the form (a,0) or (b,0), and then we just decide who is smaller using the order on the ordinals.

Making thing clearer

For example, Let’s pick \alpha = 2=\{0,1\}, \beta = 3=\{0,1,2\}. The elemets of the new set are:


And the order is:


You can also visualise the order by a sketch:

I find it very helpul!

What’s so special about this order?

As it turns out – the set \alpha\oplus\beta equipped with this order, is well ordered (It’s actullay pretty clear from the sketch…)!

Let’s prove it:

Suppose that B\subseteq \alpha\oplus\beta. There are two cases:

Case 1 B\cap (\alpha\times \{0\})=\emptyset

Then all the elements of B are of the form (b,1) with b\in\beta.

Now, define the subset:

B^\prime=\{b\in\beta:(b,1)\in B\}\subseteq \beta

\beta is an ordinal, which is in particual well-ordered. Thus B^\prime has a first elemet b^\prime.

Now, it’s not hard to see that (b^\prime,1) is the first element of B:

For every (b,1)\in B:

(b^\prime,1)<(b,1)\iff \overbrace{1<1}^{\text{false}}\lor\overbrace{(1=1\land b^\prime< b)}^{\text{true}}
Case 2 B\cap (\alpha\times \{0\})\neq\emptyset

The proof is almost identical:

Define the set:

B^\prime=\{a\in \alpha:(a,0)\in B\}\subseteq \alpha

Again, \alpha is an ordinal, so it’s well-ordered. Let a^\prime be the first element of B^\prime and it’s not hard to check that (a^\prime,0) is the first element of B. (check it!)

The actual addition

All the last post was dedicated to the order type, which is defined for well-ordered sets.

Since we just proved that \alpha\oplus\beta is well ordered, we know it has an order type. And now we can finally define the addition of to ordinals to be:


Quick example

Recall that we defined the ordinal \alpha +1 to be the ordinal \alpha\cup\{\alpha\}. However, we now have a new definition for \alpha +1:


Let’s see that this is the same as the previous definition.

In other words, we need to show that \text{otp}(\alpha\oplus 1)=\alpha\cup\{\alpha\}.

To do so, we need to find an order-isomorphism from alpha\oplus 1 to \alpha\cup\{\alpha\}. Let’s see how we can visualise both of the sets structure:

This sketch shows you exactly how to define an order isomorphism:

f:\alpha\cup\{\alpha\}\to\alpha\oplus1, \\ 
 \ \\f(k)=\begin{cases}
(0,1) & k=\alpha\\
(k,0) & k\neq\alpha

This one works (you are more than welcome to check it).

Weird example

What is 1+\omega? Let’s see a sketch:

It looks like we have an order isomorphism between \omega and 1+\omega. Let’s even define it:

f:\omega\to1\oplus\omega, \\ 
 \ \\f(k)=\begin{cases}
(0,0) & k=0\\
(k-1,1) & k\neq0

So we have:


Pretty weird huh? Get ready for something even weirder: We also know that:




And this is really weird. We’ve just proved that addition is not commutative – and that stands against our intutition!

It’s not like I haven’t met non-commutative actions before (such as matrix multiplication, function composition…). It’s just, I always used to denote commutative actions with the sign ‘+‘.

This fact brings up a questions like:

  • Is this a good definition?
  • Do we really need addition to be commutative?

I’ll give a short answer – It is a good definition. You can check that if we are dealing with finite ordinals only, the addition is commutative. The ordinals that cause us problem are the infinite ordinals. And as you probably seen before, infinity causes problems, and we can’t trust our intuition when dealing with it (for example, see this)

So addition is not commutative, it’s not a big deal, it still has some nice other properties, let’s check them out:

Properties of addition

0 as additive identity

I state that:


Let’s prove it:

Recall that 0=\emptyset, thus:


And an isomorphism f:\alpha\cup{0}\to \alpha would be: f(\alpha,0)=\alpha



And an isomorphism f:\alpha\cup{1}\to \alpha would be: f(\alpha,1)=\alpha

Canceling out from left

If \alpha+\beta_1 = \alpha+\beta_2 then \beta_1=\beta_2.

Since they are equal to each other – they have the same order type. Thus, they are also isomorphic to each other.

Suppose that:

f:\alpha\times\{0\}\cup\beta_1\times\{1\}\to \alpha\times\{0\}\cup\beta_2\times\{1\}

Is an order isomorphism between them.

Notice that in both sets, \alpha\times\{0\} is a lower set.

Therefore, the image f[\alpha\times \{0\}] is a lower set as well.

[short proof : suppose that y<x\in f[\alpha\times\{0\}], then f^{-1}(x)\in \alpha\times\{0\}, and f^{-1}(y)<f^{-1}(x) (since f^{-1} is order preserving). \alpha\times\{0\} is a lower set, thus: f^{-1}(y)\in \alpha\times\{0\} which implies y\in f[\alpha\times\{0\}] as required.]

Since f is an isomorphism:


And we’ve seen that:




So we have two isomorphic lower sets in \alpha\times{0}\cup\beta_2\times{1}. They can’t be proper subsets of each other, since well-ordered sets are not isomorphic to their proper lower sets.

So they have to be the same set,


This means that f maps \alpha\times{0} to \alpha\times{0}. Therefore it has to map \beta_1\times\{1\} to \beta_2\times\{1\}. But f is an isomorphism, thus:

\beta_1\underset{b\mapsto (b,1)}{\cong}\beta_1\times\{1\}\underset{f}{\cong}\beta_2\times\{1\}\underset{(b,1)\mapsto b}{\cong}\beta_2

And since \beta_1,\beta_2 are ordinals, we can conclude that \beta_1=\beta_2.

Note that we can’t ‘cancel out’ from the right! For example:


But, 1\neq 0.

Order preserving

I’ll show that if \beta_1 < \beta_2 then \alpha+\beta_1 < \alpha+\beta_2.

Since \beta_1 <\beta_2 are ordinals, then \beta_1 is a proper lower set of \beta_2. Therefore:


Is a proper lower set of:


(Convince yourself why it’s true!) Suppose that \text{otp}(\alpha\times{0}\cup\beta_2\times{1})=\gamma, and:

f:\alpha\times\{0\}\cup\beta_2\times\{1\}\to \gamma

Is an isomorphism. So

f|_{\alpha\times{0}\cup\beta_1\times{1}}:\alpha\times{0}\cup\beta_1\times{1}\to f[\alpha\times{0}\cup\beta_1\times{1}]

is an isomorphism from \alpha\times{0}\cup\beta_1\times{1} to it’s image, \delta = f[\alpha\times{0}\cup\beta_1\times{1}].

Again, since \alpha\times{0}\cup\beta_1\times{1} is a proper lower set, then so is it’s image. Moreover, a lower set of an ordinal is an ordinal, thus:




As we wanted.

Again, note that if \beta_1< \beta_2 it is not necessarily that \beta_1+\alpha< \beta_2+\alpha. For example:





I shall prove that for any three ordinals \alpha,\beta,\gamma:


That’s not obvious! why? Consider the following sketch:

You can actualy see why they are not the same, but you can also ‘feel’ that they are odred-isomoprhic.


(\alpha+\beta)+\gamma=\text{otp}((\alpha+\beta)\oplus \gamma)=\text{otp}((\alpha+\beta)\times\{0\}\cup\gamma\times\{1\})

(Explain yourself why the last transition is true!)

Similarly, we get:


Now we can easily define an order isomorphism:

f:(\alpha\times\{0\}\cup\beta\times\{1\})\times\{0\}\cup\gamma\times\{1\}\to \alpha\times\{0\}\cup(\beta\times\{0\}\cup\gamma\times\{1\})\times\{1\}


((\alpha,0),0)\mapsto(\alpha,0) \\ 
((\beta,1),0)\mapsto((\beta,0),1) \\

It’s not hard to verify that it is indeed an order isomorphism.

The Supremum

I am now going to preset a term that is going to allow us understand ordinal addition better.

You probably already familiar with the term of Supremum of a set. It is the smallest / first upper bound of the set.

When the set is a set of ordinals, we define the supremum to be the first ordinal that is greater (or equal) than all the elements of the set.

For example, the supremum of the set: \{1\} is 1. That’s not so interesting tohugh… Here is a better example:

The supremum of \omega is \omega. Why? Since \omega is the set of the finite ordinals, and we’ve proved that it is the first ordinal which is not finite.

For now, I only want to introduce the term. Even though there are some pretty interesting things you can say about it, my focus in this post is on addition, so the definition only will be enough for our needs.

Back to addition

I want to present a useful theorem now that we will use right away. Moreover it is really intuitive – so that’s a good thing.

Suppose that \alpha < \beta, then there is an ordinal \delta such that \alpha +\delta = \beta.

For exmaple, 3 < 5, and we can pick \delta = 2 to get 3+2 =5.

This example makes the statement look boring, however, the cool thing this theorem shows us, is that it’s true for any pair of ordinals, finite and infinite.

My intuition was:

\alpha and \beta are just two sets, so why not pick \delta to be their difference – \beta\setminus\alpha?”

The idea sound great, however there is one problem: why would \beta\setminus\alpha be an ordinal? It is well-ordered as a subset of \beta, however, it may not be \in-transitive!

So let’s fix my idea – instead of defining \delta as the difference, we can define it as the order type of the difference:


That one would work! Let’s prove it:

FIrst, let:


be the order isomorphism between (which exists by definition). We need to prove that:


Therefore, we need to deine an order isomorphism:


That’s not hard at all, if a\in\alpha:

(a,0)\mapsto a

(a\in\beta since a\in\alpha\overbrace{<}^{\in}\beta and \beta is \in-transitive.)

Moreover, if b\in\delta, then:

(b,1)\mapsto f(b)\in\beta

This is indeed an order isomorphism (verifty it!)

Note that this \delta is unique – suppose that:


We proved that we can cancel out the \alpha‘s from both sided, thus:


Addition is “continuous”

How is the term ‘continuous’ related to the action of addition? In the future we’ll see that we can define a topology on the ordinals, and with respect to it, the addition is a continuous map!

The proposition that will allow us to prove it (when we’ll discuss about it) is:

If \beta is a limit ordinal, then:

\alpha+\beta=\sup\{\alpha+\gamma|\gamma< \beta\}

That is – the sum of an ordinal with a limit ordinal from the right is the supremum of the set of all the ordinals of the form \alpha+\gamma where \gamma is an ordinal smaller than \beta.

To prove it, we need to show that \alpha+\beta is an upper bound, and then prove that it is the first.

For any \gamma<\beta we proved that \alpha+\gamma<\alpha+\beta. Thus, \alpha +\beta is indeed an upper bound of the set.

Now, suppose that \delta < \alpha + \beta is also un upper bound. If \delta \leq \alpha then:


And that’s a contradiction to \delta being an upper bound!

Thus, \delta > \alpha. So by the statement we just proved, we know that there is some ordinal \epsilon such that:


Note that \epsilon < \beta. Why?

  • If \epsilon = \beta then \alpha+\beta=\delta and that’s a contradiction to our assumption
  • If \beta < \epsilon, then \alpha+\beta<\alpha+\epsilon=\delta, which is again, a contradicition.

Now, since \beta is a limit ordinal we know that:



\delta\overset{}{=}\alpha+\epsilon\overset{\epsilon<\epsilon+1}{<}\alpha+(\epsilon+1)\overset{\epsilon+1<\beta}{\in}\{\alpha+\gamma|\gamma< \beta\}

So we’ve found an element in the set that is greater than \delta and that’s a contradiction to \delta being an upper bound!

Therefore, such \delta doesn’t exist, so \alpha+\beta is indeed the supremum of the set!

Note that if \beta is a limit ordinal we just proved that:


And that’s a pretty interesting property! We now know that a limit ordinal is the supremum of all the ordinals that are smaller than it. We are going to use it a lot.


Now we know how to add two ordinals, and that’s great!

We are now ready for the next operation, the multiplication.

Leave a Reply

%d bloggers like this: