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 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 **or** , and then we just decide who is smaller using the order on the ordinals.

**Making thing clearer**

For example, Let’s pick . The elemets of the new set are:

\alpha\oplus\beta=2\oplus3=\{\overbrace{(0,0),(1,0)}^{\in2\times\{0\}},\overbrace{(0,1),(1,1),(2,1)}^{\in3\times\{1\}}\}

And the order is:

(0,0)<(1,0)<(0,1)<(1,1)<(2,1)

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 equipped with this order, is well ordered (It’s actullay pretty clear from the sketch…)!

Let’s prove it:

Suppose that . There are two cases:

**Case 1 **–

Then all the elements of are of the form with .

Now, define the subset:

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

is an ordinal, which is in particual well-ordered. Thus has a first elemet .

Now, it’s not hard to see that is the first element of :

For every :

(b^\prime,1)<(b,1)\iff \overbrace{1<1}^{\text{false}}\lor\overbrace{(1=1\land b^\prime< b)}^{\text{true}}

**Case 2 **–

The proof is almost identical:

Define the set:

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

Again, is an ordinal, so it’s well-ordered. Let be the first element of and it’s not hard to check that is the first element of . (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 is well ordered, we know it has an order type. And now we can finally define the addition of to ordinals to be:

\alpha+\beta=\text{otp}(\alpha\oplus\beta)

#### Quick example

Recall that we defined the ordinal to be the ordinal . However, we now have a new definition for :

\alpha+1=\text{otp}(\alpha\oplus1)

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

In other words, we need to show that .

To do so, we need to find an order-isomorphism from to . 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 \end{cases}

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

#### Weird example

What is ? Let’s see a sketch:

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

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

So we have:

1+\omega=\text{otp}(1\oplus\omega)=\omega

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

\omega+1=\omega\cup\{\omega\}\neq\omega

Therefore:

1+\omega\neq\omega+1

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:

\alpha+0=0+\alpha=\alpha

Let’s prove it:

Recall that , thus:

\alpha\oplus0=\alpha\times\{0\}\cup\overbrace{0\times\{1\}}^\empty=\alpha\cup\{0\}

And an isomorphism would be:

Similarly:

\alpha\oplus1=\overbrace{0\times\{0\}}^\empty\cup\alpha\times\{1\}=\alpha\cup\{1\}

And an isomorphism would be:

#### Canceling out from left

If then .

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, is a **lower set**.

Therefore, the image is a lower set as well.

[short proof : suppose that , then , and (since is order preserving). is a lower set, thus: which implies as required.]

Since is an isomorphism:

f[\alpha\times\{0\}]\cong\alpha\times\{0\}

And we’ve seen that:

\alpha\times\{0\}\cong\alpha

Thus:

f[\alpha\times\{0\}]\cong\alpha\cong\alpha\times\{0\}

So we have two isomorphic lower sets in . 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,

\alpha\times\{0\}=f[\alpha\times\{0\}]

This means that maps to . Therefore it **has to** map to . But 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 are ordinals, we can conclude that .

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

1+\omega=0+\omega

But, .

#### Order preserving

I’ll show that if then .

Since are ordinals, then is a proper lower set of . Therefore:

\alpha\times\{0\}\cup\beta_1\times\{1\}

Is a proper lower set of:

\alpha\times\{0\}\cup\beta_2\times\{1\}

(Convince yourself why it’s true!) Suppose that , 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 to it’s image, .

Again, since is a proper lower set, then so is it’s image. Moreover, a lower set of an ordinal is an ordinal, thus:

\text{otp}(\alpha\times\{0\}\cup\beta_1\times\{1\})=\delta<\gamma=\text{otp}(\alpha\times\{0\}\cup\beta_2\times\{1\})

Therefore:

\alpha+\beta_1<\alpha+\beta_2

As we wanted.

Again, note that if it is not necessarily that . For example:

0<1

However:

0+\omega=1+\omega

#### Associative

I shall prove that for any three ordinals :

(\alpha+\beta)+\gamma=\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.

Formally:

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

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

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

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

(Explain yourself why the last transition is true!)

Similarly, we get:

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

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\}

Where:

((\alpha,0),0)\mapsto(\alpha,0) \\ ((\beta,1),0)\mapsto((\beta,0),1) \\ (\gamma,1)\mapsto((\gamma,1),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: is 1. That’s not so interesting tohugh… Here is a better example:

The supremum of is . Why? Since 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 , then there is an ordinal such that .

For exmaple, 3 < 5, and we can pick to get .

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:

“ and are just two **sets**, so why not pick to be their difference – ?”

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

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

\delta:=\text{otp}(\beta\setminus\alpha)

That one would work! Let’s prove it:

FIrst, let:

f:\delta\to\beta\setminus\alpha

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

\alpha+\delta=\text{otp}(\alpha\oplus\delta)=\beta

Therefore, we need to deine an order isomorphism:

g:\overbrace{\alpha\oplus\delta}^{\alpha\times\{0\}\cup\delta\times\{1\}}\to\beta

That’s not hard at all, if :

(a,0)\mapsto a

( since and is -transitive.)

Moreover, if , then:

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

This is indeed an order isomorphism (verifty it!)

Note that this is **unique** – suppose that:

\alpha+\delta=\beta=\alpha+\delta^{\prime}

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

\delta=\delta^\prime

## 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 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 where is an ordinal smaller than .

To prove it, we need to show that is an upper bound, and then prove that it is the **first**.

For any we proved that . Thus, is indeed an upper bound of the set.

Now, suppose that is also un upper bound. If then:

\delta\leq\alpha<\alpha+1

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

Thus, . So by the statement we just proved, we know that there is some ordinal such that:

\alpha+\epsilon=\delta

Note that . Why?

- If then and that’s a contradiction to our assumption
- If , then , which is again, a contradicition.

Now, since is a **limit** ordinal we know that:

\epsilon<\epsilon+1<\beta

Therefore:

\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 and that’s a contradiction to being an upper bound!

Therefore, such doesn’t exist, so is indeed the supremum of the set!

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

\beta=0+\beta=\sup\{0+\delta:\delta<\beta\}=\sup\{\delta:\delta<\beta\}

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**.

## Summary

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

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