# Ordinals Exponentiation

After defining ordinals addition and multiplication, it’s now time for the next action – ordinals exponentiation. Before I’ll define it properly, I do neet to make some preparations.

In contrast to the previous actions, here the preperations may seem a little unrelated and not intuitive al all, but I’ll try to make it as intuitive as possible. In the end we’ll see that it makes sense in a way…

## The supremum

I’ve already defined the supremum (here) of sets of ordinals: it is the first ordinal that is greater (or equal) than all the elements of the set.

It turns out, that we know exactly what is the supremum.

If $F$ is a set of ordinals, then:

\sup F=\bigcup F

In other words, the supremum is the union of all the elements of the set. Let’s prove it:

First, we need to show that this is even an ordinal. Since it is a set of ordinals (elements of ordinals are ordinals), then we already know it is transitive. So we only need to prove that it is well-ordered.

Let $B\sub\bigcup F$ be some subset. Since $F$ is a set of ordinals, then so as $B$. However, we proved that a set of ordinals has a first element – it’s intersection $\bigcap B$. Thus $\bigcup F$ is indeed well-ordered.

Great, so $\bigcup F$ is indeed an ordinal, and now we only need to prove it is the supremum.

First, notice that it is an upper bound of $B$: If $x\in F$ then $x\sube \bigcup F$. Therefore $x\leq \bigcup F$.

Moreover, it is the minimal upper bound: Suppose not, so there exists another upper bound $A$ such that $A< \bigcup F$. Therefore, $A\in \bigcup F$ which implies that there is some $X\in F$ such that $A\in X$, hence $A which is a contradiction of $A$ being an upper bound!

Great, now that we know what the supremum exactly is, we have a better understanding of it that will be useful soon.

## Sets of functions

Suppose that $A,B$ are some sets. You probably know that we can define the set of all the functions from $B$ to $A$:

^{B}{A}=\{f:B\to A\}

If the sets are finite, we know that:

|^{B}{A}|=|A|^{|B|}

This is an easy combinatorical argument – you have $|A|$ options to map each element of $B$ to, and there are $|B|$ elements in $B$.

This motivates us to define the exponantiation as some sort of set of functions. That’s not exactly what we are going – we are going to define a more specific set than the set of functions, and we’ll see why would I do that. And of course, we still need to add order (In fact, I am interested in well-order) to this set. After we do all that stuff, we can define the ordinal exponantiation, in a similar way to the previous actions, as the order type of this set.

## The exponentiation

We will build up for the definition in three steps:

#### The support of a function

After this preview, we can start our journey for the definition of ordinals exponantiation.

Suppose that $\alpha,\beta$ are two ordinals. We define the support of a function $f:\beta\to \alpha$ as:

\text{Supp}(f)=\{b\in\beta:f(\beta)\neq0\}

This is just the set of all the elements that are not being mapped to zero. (It’s the opposite term of a kernel in algebra) After doing so, I want to define the following set:

E(\beta,\alpha)=\{f:\beta\to\alpha|\ |\text{Supp}(f)|<\infty\}

This is the set of all the functions from $\beta$ to $\alpha$ with finite support. If $\beta$ is finite, then the support of every function from it is finite. Moreover, if $\alpha$ is also finite, then the size of $E(\beta,\alpha)$ is exactly $|\alpha|^{|\beta|}$.

This is good news, though it’s not really clear why we need the support to be finite. We’ll see it in a moment when we will define the order.

#### Order on $E(\beta,\alpha)$$E(\beta,\alpha)$

Suppose that $f,g\in E(\beta,\alpha)$.

Obviously, there are elements in $\beta$ that $f$ and $g$ map to a different element in $\alpha$. Since the support of both of them is finite, we can conclude that they differ only in a finite number of elements. Thus, the function:

\Gamma:E(\beta,\alpha)\times E(\beta,\alpha)\to \beta
\\
\Gamma(f,g)=\max\{x\in\beta:f(x)\neq g(x)\}

Is well defined – that is, the maximum exists. It takes both functions as inputs, check when the outputs of $f$ and $g$ are different, and then, returns the maximal element with this property.

For example, If $\beta=2,\alpha=3$ And:

f(0)=0 \ \ \ , g(0)=1
\\f(1)=2 \ \ \ , g(1)=1

Then:

\Gamma(f,g)=\max\{x\in2:f(x)\neq g(x)\}=\max\{0,1\}=1

We don’t care which output is bigger ($f(x)$ or $g(x)$), we only care about the input, the element in $\beta$. But now we are going to care about the outputs, since it will allow to define an order:

f < g\iff f(\Gamma(f,g))< g(\Gamma(f,g))

So how do we know which function is bigger? We are searching for the maximal element in $\beta$ such that $f$‘s output is different than $g$‘s output. After we found it, we check the outputs of $f$ and $g$ at this element, and compare them. The bigger function is the one with the bigger output.

In our example, we saw that $\Gamma(f,g)=1$ and:

f(1)=2>1=g(1)

Thus, $f>g$.

It’s not hard to verify that it is indeed an order on $E(\beta,\alpha)$. Moreover, by it’s definition, we can easily see that it is a linear order.

#### The definition

Finally we can define the ordinal exponantiation:

\alpha^\beta:=\text{otp}(E(\beta,\alpha))

Wait, we actually can’t do it now… We didn’t prove that the order on $E(\alpha,\beta)$ is a well-order! So we don’t even know if it has an order type!

That’s going to be our goal for the rest of the post, I’ll show that this set is indeed well-ordered using transfinite induction on $\beta$.

### The transfinite induction

In fact, I’ll show something stronger than that, I’ll prove that for every $\alpha,\beta$, the set $E(\beta,\alpha)$ is isomorphic to an ordinal. The induction is, as usual, going to be done in three steps, here I’ll write the exact plan:

1. The base of the induction: $E(0,\alpha)\cong 1$
2. Induction on successors: If $E(\beta,\alpha)$ is isomorphic to and ordinal, then: $E(\beta+1,\alpha)\cong E(\beta,\alpha)\times\alpha$.
3. Induction on limit ordinals: If $\beta$ is a limit ordinal and every $\gamma<\beta$ is isomorphic to an ordinal, then: $E(\beta,\alpha)\cong \sup\{\text{otp}(E(\gamma,\alpha)):\gamma<\beta\}$.

Notice that if we manage to prove those three statments, then, in fact, we’ve proved that:

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

And those two first two properties are exactly what we want an exponantiation action to fulfill! This shows that our weird definition turns out to be a good one.

## The proof

It’s going to be pretty long…

##### The base of the induction

$0$ is the empty set, there is only one function from the empty set to any set. That is the empty function $\tilde{\empty}$. The empty function indeed has a finite support, so:

E(0,\alpha)=\{\tilde\empty\}\cong\{\empty\}=1
##### Induction on successors

We want to show that:

E(\beta+1,\alpha)\cong E(\beta,\alpha)\times\alpha

So the natural thing to do is to define a map:

F:E(\beta+1,\alpha)\to E(\beta,\alpha)\times\alpha

Note that $E(\beta+1,\alpha)$ are functions from $\beta+1$ to $\alpha$. We can restrict their domain to $\beta$ to get a function (with finite support) from $\beta$ to $\alpha$. Moreover, the restriction only omits one elements form the domain – $\beta$. This leads me to define $F$ as:

F(f)=(f|_\beta,f(\beta))

Now we need to show that $f$ is indeed an order-isomorphism, and it’s enough to show that $F$ is onto and order-preserving (order-preserving map from a well ordered set is one-to-one and if an inverse exists, then it is also order preserving). Let’s do it:

###### Onto

Let $(g,\gamma)\in E(\beta,\alpha)\times\alpha$ be some arbitrary element of the set. We can easily define a function $f:E(\beta+1,\alpha)\to \alpha$, such that: $f|_{\beta}=g$ and $f(\beta)=\gamma$.

The only thing we need to verify is that $f$ has a finite support. But this follows from the fact that $g$ has finite support.

###### Order preserving

Suppose that $f,g\in E(\beta+1,\alpha)$ and $f. We want to show that $F(f). Now there are two cases:

###### Case 1: $\Gamma(f,g)=\beta$$\Gamma(f,g)=\beta$

That is, the functions differ on the last element of the domain – $\beta$. Well, then $f(\beta). And by the definition of the order on cartesian product (That I’ve described here) we conclude that $F(f).

###### Case 2: $\Gamma(f,g)<\beta$$\Gamma(f,g)<\beta$

So $\Gamma(f,g)\in\beta$ and in particular $f(\beta)=g(\beta)$. Therefore, $F(f)$ equals $F(g)$ on the right entry, thus, we have to compare the functions $f|_{\beta},g|_{\beta}$ in order to determine if $F(f) or not.

Let’s denote $x=\Gamma(f,g)$. We know that $x\in\beta$. Thus $x$ is also the greater element such that $f|_{\beta},g|_{\beta}$ differ in. That is:

\Gamma(f|_{\beta},g|_{\beta})=x

And we know that $f(x) by the assumption that $f and the definition of the order on the functions.

Therefore:

f|_{\beta}(\Gamma(f|_{\beta},g|_{\beta}))=f|_{\beta}(x)=f(x)< g(x)=g|_{\beta}(\Gamma(f|_{\beta},g|_{\beta})) \\ \Downarrow \\
f|_{\beta}< g|_{\beta}

And by the defintion of the order on the cartesian product, we conclude:

F(f)=(f|_{\beta},f(\beta))<(g|_{\beta},g(\beta))=F(g)

As we wanted.

So from both cases we now know that $F$ is indeed order preserving, hence it is an isomorphism, and together with the fact that it is onto we conclude that $F$ is an order-isomorphism and:

E(\beta+1,\alpha)\cong E(\beta,\alpha)\times\alpha

As desired.

##### induction on limit ordinals

Supopse that $\beta$ is a limit ordinal and for every $\gamma<\beta$, $E(\gamma,\alpha)$ is order-isomorphic to an ordinal which we will denote as $\delta_\gamma$. That is:

\text{otp}(E(\gamma,\alpha))=\delta_{\gamma}

Moreover, I want to denote the isomorphism between them as:

G_\gamma:E(\gamma,\alpha)\to\delta_{\gamma}

Now, we want to prove that:

E(\beta,\alpha)\cong\sup\{\delta_{\gamma}:\gamma<\beta\}

The natural thing to do is to define a map

F:E(\beta,\alpha)\to\sup\{\delta_{\gamma}:\gamma<\beta\}

and prove that it is an order isomorphism. However, we know that:

\sup\{\delta_{\gamma}:\gamma<\beta\}=\bigcup_{\gamma<\beta}\delta_{\gamma}

So we’ll think of $F$ as a map from $E(\beta,\alpha)$ to $\bigcup_{\gamma<\beta}\delta_{\gamma}$.

Now here is the important part: Since the successor is finite for every $f\in E(\beta,\alpha)$ there exists some $\gamma<\beta$ such that $f|_{\gamma}$ is a function from $\gamma$ to $\alpha$, and it maps elements that are bigger than $\gamma$ to zero.

(x\in\beta) \land (x>\gamma)\Rightarrow f(x)=0

This fact encourages me to define $F$ as following

F(f)=G_{\gamma}(f|_\gamma)

Wait, $F$ may not be even well defined! maybe there is more than one possible $\gamma$, which $G_\gamma$ should I choose? I’ll show that it doesn’t matter:

###### Sub-Statement

Suppose that $\gamma^\prime,\gamma$ are two ordinals that fulfill the property in the above. We shall prove that $G_{\gamma^\prime}(f|_{\gamma^\prime})=G_{\gamma}(f|_{\gamma})$.

We can assume WLOG that $\gamma^\prime<\gamma$.

First, note that by the property, if $x>\gamma^\prime$ then $f(x)=0$. Thus, $\gamma$ has no ‘new’ elements that are not being mapped to zero (elements in the support).

Recall that:

G_\gamma:E(\gamma,\alpha)\to\delta_{\gamma} \\
G_{\gamma^\prime}:E(\gamma^\prime,\alpha)\to\delta_{\gamma^\prime}

Re isomorphism. Now Consider the map:

H:E(\gamma^\prime,\alpha)\to E(\gamma,\alpha) \\
H(g)=\hat{g}

Where:

\hat{g}=\begin{cases}
g(x) & x\in\gamma^\prime\\
0 & x\notin\gamma^\prime
\end{cases}

In the case of our $f$, $H$ maps $f|_{\gamma^\prime}$ to $f|_{\gamma}$ (again, since every element that is not in $\gamma^\prime$ is being mapped to 0 under $f$) and $H^{-1}$ maps $f|_{\gamma}$ to $f|_{\gamma^\prime}$.

Moreover, this map is clearly order-preserving. Thus:

\delta_{\gamma^\prime}\cong E(\gamma^\prime,\alpha)\cong H[E(\gamma^\prime,\alpha)]

Now, notice that $H[E(\gamma^\prime,\alpha)]$ is a lower set:

If $h\in g\in H[E(\gamma^\prime,\alpha)]$ then $h< g$ thus, $h(x)=0$ for every $x\notin \gamma^\prime$ (if there is some $x$ such that $h(x)\neq 0$, we get by the definition of the order on functions that $h>g$), and this implies that $h\in H[E(\gamma^\prime,\alpha)]$.

Great, now that we know that, we can conclude that:

\overbrace{ G_\gamma[H[E(\gamma^\prime,\alpha)]]}^{\cong H[E(\gamma^\prime,\alpha)]}

is an ordinal (as a lower set of an ordinal – isomorphism maps a lower set to a lower set) that is isomorphic to $H[E(\gamma^\prime,\alpha)]$. But we know that $H[E(\gamma^\prime,\alpha)]$ is also isomorphic to $\delta_{\gamma^\prime}$. Therefore, the ordinals are the same and the restrection of $G_\gamma$ to $H[E(\gamma^\prime,\alpha)]$ is in fact:

{G_\gamma}|_{H[E(\gamma^\prime,\alpha)]}:H[E(\gamma^\prime,\alpha)]\to\delta_{\gamma^\prime}

This yield the following diagram:

Finally we can conclude that:

G_{\gamma}(f|_{\gamma})={G_\gamma}|_{H[E(\gamma^\prime,\alpha)]}(f|_\gamma)=G_{\gamma}^\prime\circ H^{-1}(f|_{\gamma})=G_{\gamma^\prime}(H^{-1}(f|_{\gamma}))=G_{\gamma^\prime}(f|_{\gamma^\prime})

As we wanted.

###### Back to the proof

We only need to prove that $F$ is onto and order preserving.

###### Onto

Every $x\in \bigcup_{\gamma<\beta}\delta_{\gamma}$ is an element of some $\delta_{\gamma}$. We now use the order-isomorphism:

G_\gamma:E(\gamma,\alpha)\to\delta_{\gamma}

which is onto. Thus there exists some $\hat{f}\in E(\gamma,\alpha)$ such that $G_\gamma(\hat{f})=x$. We can now define:

f(x)=\begin{cases}
\hat{f}(x) & x\in\gamma\\
0 & x\notin\gamma
\end{cases}

Now:

F(f)=G_{\gamma}(f|_{\gamma})=G_\gamma(\hat{f})=x

And this proves that $F$ is onto.

###### Order preserving

Let $f,g\in E(\beta,\alpha)$ be some functions such that $f. So there are $\gamma_1,\gamma_2$ such that:

F(f)=G_{\gamma_1}(f|_{\gamma_1}) \\
F(g)=G_{\gamma_2}(g|_{\gamma_2})

WLOG $\gamma_1\leq\gamma_2$. We can now use the substatement to get:

F(f)=G_{\gamma_1}(f|_{\gamma_1})=G_{\gamma_2}(f|_{\gamma_2})

(We need $\gamma_2$ to be greater since then we may ‘miss’ elements in the support of $f$ that are not in $\gamma_2$)

But since $f we know that $f|_{\gamma_2} (here it’s also crucial that $\gamma_1\leq \gamma_2$, try to explain yourself why).

However, $G_{\gamma_2}$ is an isomorphism and in particual order-preserving. Thus:

F(f)=G_{\gamma_2}(f|_{\gamma_2})< G_{\gamma_2}(g|_{\gamma_2})=F(g)

And we found out that $F$ is order-preserving as well!

And… That’s it, We’ve proved that $F$ is an isomorphism so we can conclude that:

E(\beta,\alpha)\cong\sup\{\delta_{\gamma}:\gamma<\beta\}

As desired.

## Summary

Well, I am glad that we’re done with it. The proof was really long but also had it’s benefits – we’ve seen another example of a proof with transinite induction, and of course, we’ve defined the exponantiation action on ordinals.

However, there is still a lot of things to say about this action that we will see in the next post.