Ordinal Exponentiation and transfinite induction

Question

Let $a\ne0$ be any ordinal
By transfinite recursion theorem, we can define a function f:OR→OR such that
i) $f(0)=1$
ii) $f(b^+)=f(b)a$
iii) $f(b)=\sup\{f(r)|r<b\}$ if $b$ is a limit ordinal.

Then how can I show that $f(b)$ defined as above is equal to $a^b$ which is an ordinal that is similar to a set of 'functions from $b$ to $a$' ?

Answer 1

The thing which you want to prove is not true. (Also it is not correctly formulated. If you write ordinal similar to the set of all functions from $b$ to $a$, you should also write some well-ordering for this set.)

The important thing here is to understand the diference between ordinal exponentiantion and cardinal exponentiation.

If $a$, $b$ are cardinals then by $a^b$ we mean the cardinality of the set of all maps from $b$ to $a$.

If $a$, $b$ are ordinals then by $a^b$ we mean an ordinal, which is usually defined in the way you described in your question.

These two things are different, e.g. $\omega^\omega$ (as ordinal power) has cardinality $\aleph_0$ which is less than $\aleph_0^{\aleph_0}=\mathfrak c$.

I don't think that there is some natural well-ordering on the set of all maps from $b$ to $a$ for ordinals $a$, $b$.

---

To see that cardinality of $\omega^\omega$ is $\aleph_0$ we can:

• Show by induction that each $\omega^n$ for $n<\omega$ is countable.

• Notice that $\omega^\omega=\sup\{\omega^n; n<\omega\}=\bigcup_{n<\omega} \omega^n$ is a union of countably many countable sets.

---

Quote from Wikipedia:

Warning: Ordinal exponentiation is quite different from cardinal exponentiation. For example, the ordinal exponentiation $2^\omega = \omega$, but the cardinal exponentiation $2^{\aleph_0}$ is the cardinality of the continuum which is larger than $\aleph_0$. To avoid confusing ordinal exponentiation with cardinal exponentiation, one can use symbols for ordinals (e.g. $\omega$) in the former and symbols for cardinals (e.g. $\aleph_0$) in the latter.

---

I am not sure to which extent it's useful here, but I'll add one possible graphical representation of $\omega^\omega$, since I've mentioned this ordinal a few times.

Imagine all finite sequences of non-negative integers ordered as in the picture: first from left to right (by the length) and in each column from bottom to top (lexicographically). The symbol $\varepsilon$ represents empty sequence, each point represents the sequence given by the path from root to this dot.

It should be at least clear that in the first column we have $\omega$, in the second column $\omega^2$ etc. (Since $\omega+\omega^2=\omega^2$, if we take all points up to second column, we get still $\omega^2$.) So clearly the ordinal in the picture is at least $\sup\{\omega^n; n<\omega\}$. If you think about it a little bit, you'll find out that this ordinal is the union of $\omega^n$'s, if $\omega^n$ is represented by the first $n$ columns.

Answer 2

To complement Martin's answer, I would like to give a concrete well-ordering having order type $\alpha^\beta$ for ordinals $\alpha$ and $\beta$. We consider the finitely supported functions from $\beta$ to $\alpha$, i. e. we set \[ E_{\alpha,\beta} := \{f\colon \beta \to \alpha \mid f^{-1}[\alpha - \{0\}] \text{ is finite} \}. \] To define an ordering on it, for $f\ne g \in E_{\alpha, \beta}$ let $\delta_{f,g} := \max\{\delta < \beta \mid f(\delta) \ne g(\delta)\}$ (note that this is well-defined as the set in question is finite). Now define \[ f < g \iff f(\delta_{f,g}) < g(\delta_{f,g}) \] Obviously for $\beta \le \gamma$ we have an obvious order respecting injection $\imath\colon E_{\alpha, \beta} \to E_{\alpha, \gamma}$, mapping $f\in E_{\alpha,\beta}$ to the function which is $0$ on all $\delta \not\in \beta$ and agrees on $\beta$ with $f$. Let $f_\beta \in E_{\alpha,\gamma}$ given by $f_\beta(\beta) = 1$, and 0 otherwise. Then $\imath(E_{\alpha,\beta}) = \{f \in E_{\alpha,\gamma} \mid f < f_\beta\}$, hence $E_{\alpha,\beta}$ is an initial segment of $E_{\alpha,\gamma}$. We will identify $E_{\alpha,\beta}$ with its image from now on.

We will show by transfinite induction on $\beta$ that $E_{\alpha, \beta}$ is isomorphic to $\alpha^\beta$:

• For $\beta = 0$, $E_{\alpha,0}$ consits of only one element, namely $\emptyset\colon 0 \to \alpha$, hence is isomorphic to $1 = \alpha^0$.

• Now lets consider $E_{\alpha, \beta+1}$, we definie $\phi\colon E_{\alpha,\beta+1} \to E_{\alpha,\beta} \times \alpha$ wia $f \mapsto \bigl(f|_\beta, f(\beta)\bigr)$, $\phi$ is bijective and we have for $f,g \in E_{\alpha,\beta + 1}$ denoting the components of $\phi$ with $\phi_1$ and $\phi_2$ respectively \begin{align*} f < g &\iff \bigl(\delta_{f,g} < \beta \wedge (f|_\beta < g|_\beta) \bigr) \vee \bigl( f(\beta) < g(\beta)\bigr)\\\ &\iff \bigl(\phi_2(f) = \phi_2(g)\wedge \phi_1(f) < \phi_1(g)\bigr) \vee \bigl(\phi_2(f) < \phi_2(g)\bigr)\\\ &\iff \phi(f) < \phi(g) \end{align*} when the product is given the usual product ordering for ordinal multiplication. So $E_{\alpha,\beta+1} \cong E_{\alpha,\beta} \cdot \alpha \cong \alpha^\beta \cdot \alpha = \alpha^{\beta + 1}$.

• If $\lambda$ is a limit ordinal we have $E_{\alpha,\lambda} = \bigcup_{\beta<\lambda} E_{\alpha, \beta}$ under the above mentioned identification: Let $f \in E_{\alpha,\lambda}$, set $\beta := 1+\max f^{-1}[\alpha -\{0\}]$. Then $\beta < \lambda$ as $\lambda$ is a limit and $f \in E_{\alpha,\beta}$. Now the isomorphisms $E_{\alpha,\beta} \cong \alpha^\beta$ for $\beta < \lambda$ are compatible with the inclusions, we have \[E_{\alpha,\lambda} = \bigcup_{\beta < \lambda} E_{\alpha,\beta} \cong \sup_{\beta < \lambda} \alpha^\beta = \alpha^\lambda \]