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:

\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 $\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:

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

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$ :

\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 $\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 \end{cases}

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 \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 $0=\emptyset$ , thus:

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

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

Similarly:

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

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:

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 $\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,

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

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:

1+\omega=0+\omega

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:

\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 $\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:

\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 $\beta_1< \beta_2$ it is not necessarily that $\beta_1+\alpha< \beta_2+\alpha$ . For example:

0<1

However:

0+\omega=1+\omega

Associative

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

(\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: $\{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:

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

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

We proved that we can cancel out the $\alpha$ ‘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 $\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:

\delta\leq\alpha<\alpha+1

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:

\alpha+\epsilon=\delta

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:

\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 $\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:

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

“Almost” addition

Making thing clearer

What’s so special about this order?

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

Case 2 – $B\cap (\alpha\times \{0\})\neq\emptyset$

The actual addition

Quick example

Weird example

Properties of addition

0 as additive identity

Canceling out from left

Order preserving

Associative

The Supremum

Back to addition

Addition is “continuous”

Summary

Like this:

Leave a Reply Cancel reply

“Almost” addition

Making thing clearer

What’s so special about this order?

Case 1 – <img data-lazy-fallback="1" src="https://s0.wp.com/latex.php?latex=B%5Ccap+%28%5Calpha%5Ctimes+%5C%7B0%5C%7D%29%3D%5Cemptyset&#038;bg=ffffff&#038;fg=394d55&#038;s=0&#038;c=20201002" alt="B&#92;cap (&#92;alpha&#92;times &#92;{0&#92;})=&#92;emptyset" class="latex" />

Case 2 – <img data-lazy-fallback="1" src="https://s0.wp.com/latex.php?latex=B%5Ccap+%28%5Calpha%5Ctimes+%5C%7B0%5C%7D%29%5Cneq%5Cemptyset&#038;bg=ffffff&#038;fg=394d55&#038;s=0&#038;c=20201002" alt="B&#92;cap (&#92;alpha&#92;times &#92;{0&#92;})&#92;neq&#92;emptyset" class="latex" />

The actual addition

Quick example

Weird example

Properties of addition

0 as additive identity

Canceling out from left

Order preserving

Associative

The Supremum

Back to addition

Addition is “continuous”

Summary

Share

Like this:

Leave a Reply Cancel reply

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

Case 2 – $B\cap (\alpha\times \{0\})\neq\emptyset$