Order type of the minimal set closed under ordinal exponentiation

2012-07-30T00:49:05Z

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

Answer by Deedlit for Order type of the minimal set closed under ordinal exponentiation

2012-07-30T08:20:58Z

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

Order type of the minimal set closed under ordinal exponentiation - MathOverflow

Order type of the minimal set closed under ordinal exponentiation

Answer by Deedlit for Order type of the minimal set closed under ordinal exponentiation