Ordinals Multiplication

After we’ve defined properly the action of ‘addition’ on ordinals, it’s time to move on to the next action – the multiplication.

The process is going to be very similar:

we are are going to define the product of two ordinal as an order type of some well-ordered set.

How exactly? let’s find out:

The Cartesian product

For any two sets $A,B$ , we can define the cartesian product as:

A\times B=\{(a,b)|a\in A, b\in B\}

I am assuming that you are already familiar with this definition (I have even used it in previous posts…). Recall that the cartesian product satisfies:

|A\times B|=|A|\cdot|B|

This property motivates us in a way to define the product of two ordinals as the order type of their cartesian product:

\alpha\cdot\beta:=\text{otp}(\alpha\times\beta)

However, what is the order on $\alpha\times \beta$ ?

Order on the cartesian product

Suppose that you have a dictionary, and you wan’t to know what the word “Hey” means. How would you find the word on your dictionary?

First, you would go to the section of the letter ‘H‘. Then, you will search words that start with “He”. Those words come before words that start with “Hg”, and after words that start with “Hd”.

If you fonud those words, you now only need to search the word “Hey”. This word comes before words that start with “Hex” and after words that start with “Hez”.

In fact, the dictionary is a well-ordered set of words, where the order on it, is the one I described in the above. First comaring the first letter, then the second, after that, the third…

That’s exacly how we are going to define our order on the cartesian product:

(a_1,b_1)<(a_2,b_2)\iff b_1< b_2\text{ or } (b_1=b_2\text{ and } a_1< a_2)

We first comare the $b_i$ ‘s, if they are the same, we move on to the $a_i$ ‘s and compare them.

Just like in the previuos post, I find the sketch really helpul. You can think of the elements of $\beta$ as the ‘first letter’ in the word, and the elements of $\alpha$ as the ‘second letter’ in the word. I know that upside down in compare to a word, but we will benefit from it, as you will see soon.

Defining ordinals multiplication

So let’s summarize what we’ve got so far:

The ordinals multiplication is defined as the order type of their cartesian produt:

\alpha\cdot\beta:=\text{otp}(\alpha\times\beta)

Where the order on $\alpha \times\beta$ is defined as:

(a_1,b_1)<(a_2,b_2)\iff b_1< b_2\text{ or } (b_1=b_2\text{ and } a_1< a_2)

Infinite causes problem again

Let’s see what is the product $2\cdot \omega$ . Here is a sketch of the set $2\times\omega$ :

It seems like we can find an order isomorphism from $2\times \omega$ to $\omega$ :

f:2\times\omega\to\omega \\ f(0,n)= 2n\\ f(1,n)=2n+1

It’s not hard to prove that $f$ is an isomorphism, thus:

2\cdot\omega=\text{otp}(2\times\omega)=\omega

Ok, so that’s a pretty weird result , but acceptable – 2 times ‘infinity’ is infity. However, what about $\omega\cdot 2$ ? A skecth for that is:

Ok, that’s kind of suprising, we found out that $\omega\times 2$ and $\omega\oplus\omega$ are the exact same ordered set! Therefore:

\omega+\omega=\omega\cdot2

However, we also know that $\omega<\omega+\omega$ (since $\omega$ is isomorphic to a proper lower set of the sum) , thus:

2\cdot\omega=\omega\neq\omega+\omega=\omega\cdot 2

What’s the conclusion? Ordinals multiplication is not commutative – just like in addition. However, we’ve discovered some interesting property:

The fact $\omega\cdot 2 = \omega + \omega$ holds for any ordinal $\alpha$ . This follows from the fact that

\alpha\times2=\alpha\times\{0,1\}=\{(a,0):a\in\alpha\}\cup\{(a,1):a\in\alpha\}=\alpha\oplus\alpha

And the order is exactly the same! In both cases we first compare the right entries, if they are not the same, then we compare the left entries.

To summarize, we found that for every ordinal $\alpha$ satisfies:

\alpha\cdot2=\alpha+\alpha

Some properties of multiplication

There are two main properties that first came up to my mind:

$\alpha\cdot 0 =0\cdot\alpha = 0$
$\alpha\cdot 1=1\cdot \alpha = \alpha$

If those properties doesn’t hold, then it’s a sign that the definition is not good! We would definitly want a multiplication action to satisfise those. Let’s check if they are true:

\alpha\cdot0\overset{\text{def.}}{=}\text{otp}(\alpha\times0)\overset{0:=\emptyset}{=}\text{otp}(\alpha\times\emptyset)=\text{otp}(\emptyset)=\emptyset=0

From similar argument, we can conclude that $0\cdot\alpha=0$ .

Great! So the first one holds, what about the second?

\alpha\cdot 1=\text{otp}(\alpha\times1)\overset{1:=\{0\}}{=}\text{otp}(\alpha\times\{0\})

However, we proved that $\alpha\times\{0\}\cong\alpha$ (For the isomorphism between them, just map $(\alpha,0)$ to $\alpha$ ). Thus:

\text{otp}(\alpha\times\{0\})=\text{otp}(\alpha)=\alpha

And that’s what we wanted! From similar arguments, it’s not hard to see that $1\cdot \alpha = \alpha$ as well.

Now that we know the definition satisfies the elementary properties I’ve thought of, we can try and prove some more properties:

Associativity

I want to prove that:

(\alpha\beta)\gamma=\alpha(\beta\gamma)

By definition:

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

However:

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

(Try to prove it! I’ll give a litlle hint: use the isomorphism between $\text{otp(}\alpha\times\beta)$ to $\alpha\times\beta$ ).

Therefore:

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

On the other hand (with similar argument):

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

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

Both $(\alpha\beta)\gamma$ and $\alpha(\beta\gamma)$ equals to $\text{otp}(\alpha\times\beta\times\gamma)$ . Hence, they are the same.

Order preserving from left

I shall prove that if $\alpha\neq 0$ and $\beta_1<\beta_2$ then:

\alpha\beta_1<\alpha\beta_2

Since $\beta_1<\beta_2$ we get that $\beta_1$ is a proper lower set of $\beta_2$ . Thus, $\alpha\times\beta_1$ is a proper lower set of $\alpha\times\beta_2$ .

Suppose that:

f:\alpha\times\beta_2\to\text{otp}(\alpha\times\beta_2)

Is an order-isomorphism. We’ve proved that the image of a proper lower set under isomorphism, is also a proper lower set. Thus:

f[\alpha\times\beta_1]\subset\text{otp}(\alpha\times\beta_2)

Is a proper lower set.Moreover, since it’s a proper lower set of an ordinal, it is an ordinal as well. Now:

\text{otp}(\alpha\times\beta_1)\cong\alpha\times\beta_1\cong f[\alpha\times\beta_1]<\text{otp}(\alpha\times\beta_2)

Since $\text{otp}(\alpha\times\beta_1)$ and $f[\alpha\times\beta]$ are two isomorphic ordinals, then they must be the same. Therefore:

\alpha\beta_1=\text{otp}(\alpha\times\beta_1)<\text{otp}(\alpha\times\beta_2)<\alpha\beta_2

As we wanted.

Cancel from left

An immediate result from the property in the above, is that if $\alpha\beta_1=\alpha\beta_2$ then $\beta_1=\beta_2$ .

Why? Suppose not, then WLOG, $\beta_1<\beta_2$ . By the last property, we know that $\alpha\beta_1<\alpha\beta_2$ and that’s a contradiction to the assumption.

The Distributive property

Suppose that $\alpha,\beta\gamma$ are ordinals, then:

\alpha(\beta+\gamma)=\alpha\beta+\alpha\gamma

This property is great! It shows us not only that we’ve chosen a good definition for multiplication, but it also shows that multiplication communicate with addition!

The proof for that is not so hard:

By definition:

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

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

On the other hand:

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

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

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

Now define:

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

As:

f(a,(b,0))=((a,b),0) \\ f(a,(c,1))=((a,c),1)

For any $a\in\alpha,b\in\beta,c\in\gamma$ . It’s not hard to check that this is an order isomorphism, however, I think like it’s kind of pointless, so I’ll skip it….

Important note

We just proved the distributive law “from left”. Note that this property “from right” may not be true:

(1+1)\cdot\omega=2\cdot\omega=\omega\neq\omega+\omega=1\cdot\omega+1\cdot\omega

So we need to be careful when using this law!

Multiplication is “continuous”

In a similar way addition – there is a special property of multiplication that relates to the term “continuous”. The property is:

If $\beta$ is a limit ordinal, then:

(\alpha\sup\{\gamma:\gamma<\beta\}=)\alpha\beta=\sup\{\alpha\gamma:\gamma<\beta\}

In order to prove it, I am going to have to give a little spoiler for the next post… In the next post, I’ll prove that If $F$ is a set of ordinals then:

\sup F=\bigcup_{}F

Which is basically saying that the supremum of the set is the union of the elements of it. For example, if $F=\{0,1,2\}$ Then:

\sup F=\bigcup\{0,1,2\}=\bigcup\{\empty,\{\empty\},\{\empty,\{\empty\}\}\}=\{\empty,\{\empty\}\}=2

Great, so now that’s clear, the proof is nothing but technical. In fact, we need to prove that:

\alpha\bigcup_{\gamma<\beta}\gamma=\bigcup_{\gamma<\beta}\alpha\gamma

So we’ll find an order isomorphism:

f:\alpha\times\bigcup_{\gamma<\beta}\gamma\to\bigcup_{\gamma<\beta}\alpha\times\gamma

If we’ll do so, then we’ll get that:

\alpha\bigcup_{\gamma<\beta}\gamma\overset{\text{otp}}{\cong }\alpha\times\bigcup_{\gamma<\beta}\gamma\overset{f}{\cong }\bigcup_{\gamma<\beta}\alpha\times\gamma\overset{\text{otp}}{\cong }\bigcup_{\gamma<\beta}\alpha \gamma

And that’s exactly what we want. Let’s define $f$ as:

f(a,b)=(a,b)

for every $a\in\alpha, b\in \bigcup_{\gamma<\beta}\gamma$ . That’s pretty simple, right?

It’s not hard to see that this function is onto and one-to-one. It’s also not hard to see it’s order preserving: If $(a_1,b_1)<(a_2,b_2)$ then there exists some $\gamma<\beta$ such that $b_1,b_2<\gamma$ (why?), and we can compare the pairs in $\alpha\times\gamma$ .

Summary

After we’ve learned about multiplication, the last action I want to talk about is exponentiation. However, before I’ll get to that, I would like to present a new method for proving theorems that we are going to use a lot – the transfinite induction.

The Cartesian product