Define $\tau: \mathbf{Ord} \to \mathbf{Ord}$ such that $\tau(\alpha)$ is the order type of the minimal set $S$ of ordinals such that $\alpha \in S$ and $S$ is closed under ordinal exponentiation.

We have the following: $\tau(0)=2, \tau(1)=1$ and for all $\alpha \in [2, \omega), \tau(\alpha)=\omega$.

Question: What are the values $\tau(\alpha)$ for $\alpha\ge\omega$?


1 Answer 1


Take $\alpha$ to be any ordinal greater than or equal to $\omega$. The set of ordinals $S(\alpha)$ obtained generated from $\alpha$ using ordinal exponentiation are the ordinals of the form $\alpha^{\alpha^{E(\alpha)}}$ where $E(\alpha)$ is an exponential polynomial over the base $\alpha$. By "exponential polynomial over the base $\alpha$" I mean the set of ordinals defined by:

$E_0(\alpha)$ = the finite ordinals

$E_{n+1}(\alpha) = \lbrace 0 \rbrace \cup \lbrace\alpha^{\beta_1} + \alpha^{\beta_2} + \ldots + \alpha^{\beta_n} | \beta_i \in E_n(\alpha) \& \beta_1 \geq \beta_2 \geq \ldots \geq \beta_n \rbrace$

$E(\alpha) = \bigcup E_n(\alpha)$

First, observe that $\alpha = \alpha^{\alpha^0}$, and for arbitrary $\beta, \gamma$, $(\alpha^{\alpha^\beta})^{\alpha^{\alpha^\gamma}} = \alpha^{\alpha^{\beta + \alpha^\gamma}}$. So every element of $S(\alpha)$ is of the form $\alpha^{\alpha^\beta}$. It remains to show that the set of ordinals $T(\alpha)$ generated from $0$ using the function $\beta, \gamma \rightarrow \beta + \alpha^\gamma$ is exactly the exponential polynomials. It is easy to see that the exponential polynomials are closed under $\beta, \gamma \rightarrow \beta + \alpha^\gamma$; going the other direction, $0 + \alpha^0 + \ldots \alpha^0 = n$, so $E_0(\alpha) \subset T(\alpha)$. Assume $E_n(\alpha) \subset T(\alpha)$; for $\beta_1, \beta_2, \ldots, \beta_n \in E_n(\alpha) \subset T(\alpha)$, we have $0 + \alpha^{\beta_1} + \alpha^{\beta_2} + \ldots + \alpha^{\beta_n} \in T(\alpha)$. So $E_{n+1}(\alpha) \subset T(\alpha)$, and by induction, $E(\alpha) \subset T(\alpha)$. So $T(\alpha) = E(\alpha)$, and $S(\alpha)$ is as we described.

By an extension of Cantor's Normal Form Theorem, for any ordinal $\alpha$ and any ordinal $\beta$, $\beta$ is uniquely expressible in the form

$\alpha^{\beta_1} \gamma_1 + \alpha^{\beta_2} \gamma_2 + \ldots + \alpha^{\beta_n} \gamma_n$, where $\beta_1 > \beta_2 > \ldots > \beta_n$ and $\gamma_i < \alpha$ for all $1 \leq i \leq n$,

and more importantly, different values of $\beta_i$ and $\gamma_i$ lead to different values of $\beta$.

It follows that the set $E(\alpha)$, when iteratively described using the above form, has a unique expression for each ordinal, and different expressions lead to different ordinals. Indeed, $E_0(\alpha)$ has a different expression $\alpha^0 + \ldots + \alpha^0$ for each finite ordinal $n$. Next assume that different expressions lead to different ordinals in $E_n(\alpha)$. Given an pair of expressions $\beta = \alpha^{e(\beta_1)} + \ldots + \alpha^{e(\beta_n)}$ and $\gamma = \alpha^{e(\gamma_1)} + \ldots + \alpha^{e(\gamma_n)}$ for $\beta_i \in E_n(\alpha), \gamma_i \in E_n(\alpha)$, $\beta_i$ and $\gamma_i$ weakly decreasing, and $e(\beta_i)$ and $e(\gamma_i)$ representing expressions for $\beta_i$ and $\gamma_i$; if the two expressions are different, then for some $i$ we must have $e(\beta_i) \neq e(\gamma_i)$, and by the induction hypothesis $\beta_i$ is different from $\gamma_i$. But then by the extended Cantor Normal Form Theorem $\beta$ and $\gamma$ are different. So different expressions of $E_{n+1}(\alpha)$ represent different ordinals, so by induction different expressions of $E(\alpha)$ lead to different ordinals.

So for any ordinal $\alpha \geq \omega$, we can define an order-preserving bijection $E(\alpha) \rightarrow \varepsilon_0$ by simply replacing $\alpha$ with $\omega$ for every appearance in the iterative normal form expression. So $\tau (\alpha) = \varepsilon_0$.

  • $\begingroup$ There is something wrong with the definition of $E(\alpha)$. Note that $(\omega^{\omega^{\omega^\omega}})^\omega=\omega^{\omega^{(\omega^\omega+\omega^0)}}$, but there is no such $n$ that $\omega^\omega+\omega^0 \in E_n(\omega)$. $\endgroup$ Jul 30, 2012 at 17:06
  • $\begingroup$ Hmmm, I intended to include the empty sum, which equals 0. That should make the definition correct. I will edit to make this more explicit. $\endgroup$
    – Deedlit
    Aug 1, 2012 at 1:44
  • $\begingroup$ Ugh, LaTex isn't working for me... I intended to have braces around the 0 and the second expression for $E_{n+1}(\alpha)$, but it's not showing up. $\endgroup$
    – Deedlit
    Aug 1, 2012 at 1:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.