Properties of exponantiation of ordinals

Tair GaliliDecember 15, 2020December 15, 2020Set Theory

In the last post, we worked pretty hard to define ordinals exponentiation, however, This hard work revealed some great properties:

$\alpha^0 = 1$
If $\beta$ is a successor then: $\alpha^{\beta+1}=\alpha^\beta\cdot\alpha$
If $\beta$ is a limit ordinal then; $\alpha^{\beta}=\sup\{\alpha^{\gamma}:\gamma<\beta\}$

Those properties are great – the first two are pretty intuitive, and the third is also a pretty comfortable definition of $\alpha^{\beta}$ . We can now prove properties on the $\alpha^{\beta}$ without ‘going back’ to the orginial definition, which is less intuitive…

So let’s see what we can learn from these three properties alone about this action:

The properties you would expect

I think the most famous properties of the action of exponantiation are:

\alpha^{\beta+\gamma}=\alpha^{\beta}\cdot\alpha^{\gamma}

(\alpha^{\beta})^{\gamma}=\alpha^{\beta\gamma}

Luckily, those properties apply to ordinal exponentiation as well!

However before I’ll prove those, I want to show a way to compare ordinals first:

Just a little remark: I am going to use transfinite induction a lot!

Comparing powers

If $\alpha>1$ and $\beta<\gamma$ then $\alpha^{\beta}<\alpha^{\gamma}$ .

Note that it is important that $\alpha>1$ . Indeed, if $\alpha=0$ the statement is not always true (why? How many function are there to 0? What happens if $\alpha=1$ ?).

Let’s prove it with transfinite induction on $\gamma$ :

Base case

Suppose that $\gamma=0$ then there is no such $\beta$ , so the statement is vacuous truth…

Successor case

Supposet that the statement is true for $\gamma$ , we shall prove it is true for $\gamma+1$ as well:

\alpha^{\beta}\overset{\text{induction}}{<}\alpha^{\gamma}=\alpha^{\gamma}\cdot1\overset{\alpha>1}{<}\alpha^{\gamma}\cdot\alpha=\alpha^{\gamma+1}

Limit case

Suppose that the statement is for every $\delta<\gamma$ and $\gamma$ is a limit ordinal. Then:

\alpha^{\gamma}=\sup\{\alpha^{\delta}:\delta<\gamma\}=\bigcup_{\delta<\gamma}\alpha^{\delta}

However, since $\gamma$ is a limit ordinal and $\beta<\gamma$ , we know that $\beta+1<\gamma$ as well. Therefore:

\alpha^{\beta}\overset{\text{induction}}{<}\alpha^{\beta+1}<\bigcup_{\delta<\gamma}\alpha^{\delta} =\alpha^\gamma \\ \Downarrow \\ \alpha^{\beta}<\alpha^{\gamma}

And that’s it.

Now we are ready to prove the major properties:

The first property : $\alpha^{\beta+\gamma}=\alpha^{\beta}\cdot\alpha^{\gamma}$

We shall prove it by transfinite induction on $\gamma$ :

Base case

If $\gamma=0$ then:

\alpha^{\beta+0}{=}\alpha^{\beta}=\alpha^{\beta}\cdot1\overset{\alpha^0=1}{=}\alpha^{\beta}\cdot\alpha^{0}

Successor case

Suppose that the statement is true for $\gamma$ , we shall prove it’s true for $\gamma+1$ :

\alpha^{\beta+(\gamma+1)}\overset{\text{associativity}}{=}\alpha^{(\beta+\gamma)+1}\overset{(a^{b+1}=a^b\cdot a)}{=}\alpha^{\beta+\gamma}\cdot\alpha\overset{\text{induction}}{=}(\alpha^{\beta}\cdot\alpha^{\gamma})\cdot\alpha

\overset{\text{associativity}}{=}\alpha^{\beta}\cdot(\alpha^{\gamma}\cdot\alpha)\overset{(a^{b+1}=a^b\cdot a)}{=}\alpha^{\beta}\cdot\alpha^{\gamma+1}

Limit case

Before I’ll prove the limit case, I want to prove two sub-statements first:

Sub-statement 1

Note that since $\gamma$ is a limit ordinal, then so as $\beta+\gamma$ . Why?

Suppose that’s not the case, then there exists some $\delta$ such that $\delta+1=\beta+\gamma$ . However:

\delta<\delta+1=\beta+\gamma\overset{\gamma\text{ is limit}}{=}\beta+\sup\{\epsilon:\epsilon<\gamma\}\overset{\text{'continuous' property}}{=}\sup\{\beta+\epsilon:\epsilon<\gamma\} \\ \Downarrow \\ \delta\in\sup\{\beta+\epsilon:\epsilon<\gamma\}=\bigcup_{\epsilon<\gamma}(\beta+\epsilon)

So there exists some $\epsilon_0<\gamma$ such that $\delta\in\beta+\epsilon_0$ which is the same as $\delta<\beta+\epsilon_0$ . Therefore $\delta+1\leq \beta+\epsilon_0$ .

But $\gamma$ is a limit ordinal, so $\epsilon_0+1<\gamma$ . Thus:

\delta+1\leq \beta+\epsilon_0<\beta+(\epsilon_0+1) \\ \Downarrow\\ \delta+1\in \bigcup_{\epsilon<\gamma}(\beta+\epsilon)=\delta+1

And that’s a contradiction, since an ordinal is not a member of itself!

Sub-statement 2

\sup\{\alpha^{\beta+\delta}:\delta<\gamma\}=\sup\{\alpha^{\delta}:\delta<\beta+\gamma\}

If $\alpha=0$ or $\alpha=1$ , then the statment is obviously true (why?). So let’s assume that $\alpha>1$ .

Using the previous sub-statement, we know that $\beta+\gamma$ is a limit ordinal. Therefore:

\sup\{\alpha^{\delta}:\delta<\beta+\gamma\}=\alpha^{\beta+\gamma}

Now, suppose that $\delta<\gamma$ , so $\beta+\delta<\beta+\gamma$ . Hence:

\alpha^{\beta+\delta}<\alpha^{\beta+\gamma}=\sup\{\alpha^{\delta}:\delta<\beta+\gamma\}

And that’s true for every $\delta<\gamma$ , so we can conclude that:

\sup\{\alpha^{\beta+\delta}:\delta<\gamma\}\leq\sup\{\alpha^{\delta}:\delta<\beta+\gamma\}

On the other hand, if $x<\beta+\gamma$ then:

x<\beta+\gamma\overset{\text{'continuous'}}{=}\sup\{\beta+\delta:\delta<\gamma\}=\bigcup_{\delta<\gamma}(\beta+\delta)

So there exists some $\delta_0<\gamma$ such that $x<\beta+\delta_0$ . So $\alpha^x<\alpha^{\beta+\delta_0}$ . And that’s true for every $x<\beta+\gamma$ , therefore:

\sup\{\alpha^{\beta+\delta}:\delta<\gamma\}\geq\sup\{\alpha^{\delta}:\delta<\beta+\gamma\}

In total, we get that:

\sup\{\alpha^{\beta+\delta}:\delta<\gamma\}=\sup\{\alpha^{\delta}:\delta<\beta+\gamma\}

As we wanted.

Back to the proof

Suppose that $\gamma$ is a limit ordinal and the statement is true for every $\delta<\gamma$ . Then:

\alpha^{\beta}\cdot\alpha^{\gamma}\overset{\gamma\text{ is limit ordinal}}{=}\alpha^{\beta}\cdot\sup\{\alpha^{\delta}:\delta<\gamma\}\overset{\text{'continuous'}}{=}\sup\{\alpha^{\beta}\cdot\alpha^{\delta}:\delta<\gamma\}

\overset{\text{induction}}{=}\sup\{\alpha^{\beta+\delta}:\delta<\gamma\}\overset{\text{sub-statement 2}}{=}\sup\{\alpha^{\delta}:\delta<\beta+\gamma\}\overset{\text{sub-statement 1}}{=}\alpha^{\beta+\gamma}

And that’s it!

The second property : $(\alpha^{\beta})^{\gamma}=\alpha^{\beta\gamma}$

This case is actually very similar, again, we shall prove it with induction on $\gamma$ :

Base case

I $\gamma=0$ then:

(\alpha^\beta)^{0}=1=\alpha^{0}=\alpha^{\beta\cdot0}

Successor case

Suppose that the statement is true for $\gamma$ , we shall prove it’s true for $\gamma+1$ :

(\alpha^{\beta})^{\gamma+1}=(\alpha^{\beta})^{\gamma}\cdot\alpha^{\beta}\overset{\text{induction}}{=}\alpha^{\beta\gamma}\cdot\alpha^\beta\overset{\text{property 1}}{=}\alpha^{\beta\gamma+\beta}\overset{\text{distributive}}{=}\alpha^{\beta(\gamma+1)}

Limit case

With almost identical proofs we can prove that if $\gamma$ is a limit ordinal, then $\beta\gamma$ is a limit ordinal as well. And that:

\sup\{\alpha^{\beta\delta}:\delta<\gamma\}=\sup\{\alpha^{\delta}:\delta<\beta\gamma\}

Try to prove it yourself! As I said, the proofs are almost identical to those of the sub-statements

Now, suppose that $\gamma$ is a limit ordinal and the statement is true for every $\delta<\gamma$ . So:

(\alpha^{\beta})^{\gamma}\overset{\gamma\text{ is limit}}{=}\sup\{(\alpha^{\beta})^{\delta}:\delta<\gamma\}\overset{\text{induction}}{=}\sup\{\alpha^{\beta\delta}:\delta<\gamma\}\overset{\text{sub-statement}}{=}\sup\{\alpha^{\delta}:\delta<\beta\gamma\}

\overset{\beta\gamma\text{ is limit}}{=}\alpha^{\beta\gamma}

That’s it.

Some cool tricks

Ok, now that we are equipped with lots of great properties of the ordinals operations, I would like to present some pretty cool results:

Consider the ordinal $\omega+\omega^{2}$ . We don’t really have an intuition to what it is exactly… However, maybe there is a ‘nicer’ way to represent it. Let’s see what we can do:

\omega+\omega^2=\omega+\omega^{1+1}\overset{\alpha^{\beta+1}=\alpha^{\beta}\cdot\alpha}{=}\omega+\omega\cdot\omega\overset{\text{distributive}}{=}\omega(1+\omega)

However, recall that $1+\omega=\omega$ , therefore, we are left with:

\omega+\omega^2=\omega(1+\omega)=\omega\cdot\omega\overset{\alpha^{\beta}\cdot\alpha}{=}\omega^2

Great, $\omega^2$ is much more intuitive than $\omega+\omega^2$ . It seems like the $\omega$ there is only “disturbing” the representation of the ordinal…

Let’s see another example: What about the ordinal $(\omega+1)\cdot\omega^2$ ? Well, let’s find out:

(\omega+1)\cdot\omega^2\overset{\alpha^{\beta}\cdot\alpha}{=}(\omega+1)\cdot(\omega\cdot\omega)\overset{\text{distributive}}{=}((\omega+1)\cdot\omega)\cdot\omega

Now let’s focus on $((\omega+1)\cdot\omega)$ . Since $\omega$ is a limit ordinal:

(\omega+1)\cdot\omega=(\omega+1)\cdot\sup\{n:n<\omega\}\overset{\text{'continuous'}}{=}\sup\{(\omega+1)\cdot n:n<\omega\}

Note that:

(\omega+1)\cdot n=\overbrace{(\omega+1)+(\omega+1)+\cdots+(\omega+1)}^{n\text{ times}}

This can be easilly proved by induction (try it!), therefore:

\sup\{(\omega+1)\cdot n:n<\omega\}=\sup\{\overbrace{(\omega+1)+(\omega+1)+\cdots+(\omega+1)}^{n\text{ times}}:n<\omega\}

\overset{\text{associative}}{=}\sup\{\omega+\overbrace{(1+\omega)+\cdots+(1+\omega)}^{n-1\text{ times}}+1:n<\omega\}

\overset{1+\omega=\omega}{=}\sup\{\omega+\overbrace{\omega+\cdots+\omega}^{n-1\text{ times}}+1:n<\omega\}

\sup\{\overbrace{\omega+\omega+\cdots+\omega}^{n\text{ times}}+1:n<\omega\}=\sup\{\omega\cdot n+1:n<\omega\}

However, it’s not hard to see that:

\sup\{\omega\cdot n+1:n<\omega\}=\sup\{\omega\cdot n:n<\omega\}

Therefore:

(\omega+1)\cdot\omega=\sup\{(\omega+1)\cdot n:n<\omega\}=\sup\{\omega\cdot n:n<\omega\}\overset{\text{'continuous'}}{=}\omega\cdot\sup\{ n:n<\omega\}

=\omega\cdot\omega=\omega^2

So, in total we get that:

(\omega+1)\cdot\omega^2=((\omega+1)\cdot\omega)\cdot\omega=\omega^{2}\cdot\omega=\omega^3

And that’s it!

Summary

So we’ve met some really great properties of exponantiation of ordinals, and we’ve also seen how all the operations behave together. That’s going to be it for now…

Leave a Reply Cancel reply

%d bloggers like this: