Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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$?

share|improve this question
add comment

1 Answer

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$.

share|improve this answer
    
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)$. –  Vladimir Reshetnikov Jul 30 '12 at 17:06
    
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. –  Deedlit Aug 1 '12 at 1:44
    
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. –  Deedlit Aug 1 '12 at 1:52
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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