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<X\in F 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:


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:


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)

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


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


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:


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:

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:


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:


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<g. We want to show that F(f)<F(g). Now there are two cases:

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

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

Case 2: \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)<F(g) 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:


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


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:


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:


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


Now, we want to prove that:


The natural thing to do is to define a map


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


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


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:


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

Re isomorphism. Now Consider the map:

H:E(\gamma^\prime,\alpha)\to E(\gamma,\alpha) \\


g(x) & x\in\gamma^\prime\\
0 & x\notin\gamma^\prime

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:


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.


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


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

\hat{f}(x) & x\in\gamma\\
0 & x\notin\gamma



And this proves that F is onto.

Order preserving

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

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

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


(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<g we know that f|_{\gamma_2}<g|_{\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:


As desired.


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.

Leave a Reply

%d bloggers like this: