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:

|^{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)$

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:

The base of the induction: $E(0,\alpha)\cong 1$
Induction on successors: If $E(\beta,\alpha)$ is isomorphic to and ordinal, then: $E(\beta+1,\alpha)\cong E(\beta,\alpha)\times\alpha$ .
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:

$\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=\{\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<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:

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

And we know that $f(x)<g(x)$ by the assumption that $f<g$ 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<g$ . 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<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:

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.

The supremum

Sets of functions

The exponentiation

The support of a function

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

The definition

The transfinite induction

The proof

The base of the induction

Induction on successors

Onto

Order preserving

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

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

induction on limit ordinals

Sub-Statement

Back to the proof

Onto

Order preserving

Summary

Like this:

Leave a Reply Cancel reply

The supremum

Sets of functions

The exponentiation

The support of a function

Order on <img data-lazy-fallback="1" src="https://s0.wp.com/latex.php?latex=E%28%5Cbeta%2C%5Calpha%29&#038;bg=ffffff&#038;fg=394d55&#038;s=0&#038;c=20201002" alt="E(&#92;beta,&#92;alpha)" class="latex" />

The definition

The transfinite induction

The proof

The base of the induction

Induction on successors

Onto

Order preserving

Case 1: <img data-lazy-fallback="1" src="https://s0.wp.com/latex.php?latex=%5CGamma%28f%2Cg%29%3D%5Cbeta&#038;bg=ffffff&#038;fg=394d55&#038;s=0&#038;c=20201002" alt="&#92;Gamma(f,g)=&#92;beta" class="latex" />

Case 2: <img data-lazy-fallback="1" src="https://s0.wp.com/latex.php?latex=%5CGamma%28f%2Cg%29%3C%5Cbeta&#038;bg=ffffff&#038;fg=394d55&#038;s=0&#038;c=20201002" alt="&#92;Gamma(f,g)&lt;&#92;beta" class="latex" />

induction on limit ordinals

Sub-Statement

Back to the proof

Onto

Order preserving

Summary

Share

Like this:

Leave a Reply Cancel reply

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

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

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