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 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 be some subset. Since is a set of ordinals, then so as . However, we proved that a set of ordinals has a first element – it’s intersection . Thus is indeed well-ordered.

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

First, notice that it is an upper bound of : If then . Therefore .

Moreover, it is the minimal upper bound: Suppose not, so there exists another upper bound such that . Therefore, which implies that there is some such that , hence which is a contradiction of 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 are some sets. You probably know that we can define the set of all the functions from to :

^{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 options to map each element of to, and there are elements in .

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 are two ordinals. We define the **support** of a function 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 to with finite support. If is **finite**, then the support of every function from it is finite. Moreover, if is also finite, then the size of is exactly .

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

Suppose that .

Obviously, there are elements in that and map to a different element in . 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 and are different, and then, returns the maximal element with this property.

For example, If 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 ( or ), we only care about the input, the element in . 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 such that ‘s output is different than ‘s output. After we found it, we check the outputs of and at this element, and compare them. The bigger function is the one with the bigger output.

In our example, we saw that and:

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

Thus, .

It’s not hard to verify that it is indeed an order on . 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 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 .

### The transfinite induction

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

**The base of the induction**:**Induction on successors**: If is isomorphic to and ordinal, then: .**Induction on limit ordinals**: If is a limit ordinal and every is isomorphic to an ordinal, then: .

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

- If is a
**successor**then: - If is a
**limit ordinal**then:

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

is the empty set, there is only one function from the empty set to any set. That is the empty function . 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 are functions from to . We can restrict their domain to to get a function (with finite support) from to . Moreover, the restriction only omits **one** elements form the domain – . This leads me to define as:

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

Now we need to show that is indeed an order-isomorphism, and it’s enough to show that 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 be some arbitrary element of the set. We can easily define a function , such that: and .

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

**Order preserving**

Suppose that and . We want to show that . Now there are two cases:

###### Case 1:

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

###### Case 2:

So and in particular . Therefore, equals **on the right entry**, thus, we have to compare the functions in order to determine if or not.

Let’s denote . We know that . Thus is also the greater element such that differ in. That is:

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

And we know that by the assumption that 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 is indeed order preserving, hence it is an isomorphism, and together with the fact that it is onto we conclude that is an order-isomorphism and:

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

As desired.

**induction on limit ordinals**

Supopse that is a limit ordinal and for every , is order-isomorphic to an ordinal which we will denote as . 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 as a map from to .

Now here is the important part: Since the successor is **finite** for every there exists some such that is a function from to , and it maps elements that are bigger than to zero.

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

This fact encourages me to define as following

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

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

**Sub-Statement**

Suppose that are two ordinals that fulfill the property in the above. We shall prove that .

We can assume WLOG that .

First, note that by the property, if then . Thus, 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 , maps to (again, since every element that is not in is being mapped to 0 under ) and maps to .

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 is a lower set:

If then thus, for every (if there is some such that , we get by the definition of the order on functions that ), and this implies that .

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 . But we know that is also isomorphic to . Therefore, the ordinals are the same and the restrection of to 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 is onto and order preserving.

**Onto**

Every is an element of some . We now use the order-isomorphism:

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

which is **onto**. Thus there exists some such that . 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 is onto.

**Order preserving**

Let be some functions such that . So there are such that:

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

WLOG . We can now use the substatement to get:

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

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

But since we know that (here it’s also crucial that , try to explain yourself why).

However, 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 is order-preserving as well!

And… That’s it, We’ve proved that 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.