# Order type of the smallest set containing the identity function and closed under exponentiation

Let $E$ be the smallest set of functions $\mathbb{N}^+\to\mathbb{N}^+$ containing the identity function $n \mapsto n$ and closed under exponentiation $(f,g) \mapsto \left(n \mapsto f(n)^{g(n)}\right)$, i.e. $E=\{n \mapsto n, n \mapsto n^n, n \mapsto n^{n^n}, n \mapsto (n^n)^n, n \mapsto (n^n)^{n^n},\ \dots\}$. Let $E$ be ordered by eventual domination.

Is $E$ well-ordered? What is the least ordinal that cannot be embedded in $E$?

-

As Joel showed, the set $E$ is well-ordered with order type no more than the Cantor ordinal $\epsilon_0$. In fact, its order type is exactly $\epsilon_0$. This can be proved by constructing the order isomorphism between $\epsilon_0$ and $E$.

First, note that if $F,G\in E$ are of the form $F(n)=n^{n^{f(n)}}$, $G(n)=n^{n^{g(n)}}$ then $F^G$ is of also of the form $n\mapsto n^{n^{h(n)}}$, where $h(n) = f(n)+n^{g(n)}$. So, let me define $E^\prime$ to be the smallest subset of $\mathbb{N}^{\mathbb{N}}$ containing the zero function $n\mapsto0$ and such that for any pair $f,g\in E^\prime$ then the function $n\mapsto f(n)+n^{g(n)}$ is in $E^\prime$. Then the map taking $f\in E^\prime$ to $n\mapsto n^{n^{f(n)}}$ is an order isomorphism from $E^\prime$ to $E$.

I'll now define a map $\theta\colon\epsilon_0\to E^\prime$ and show that it is an order isomorphism. By Cantor normal form any ordinal $\alpha < \epsilon_0$ can be written uniquely as $\alpha=\omega^{\beta_1}+\cdots+\omega^{\beta_k}$ for ordinals $\beta_1\ge\cdots\ge\beta_k$ less than $\alpha$. Write, $$\theta(\alpha)(n)=n^{\theta(\beta_1)(n)}+\cdots+n^{\theta(\beta_k)(n)}.$$ This defines $\theta(\alpha)$ in terms of its values on smaller ordinals. Note that if $k=0$ then $\theta(\alpha)=0$ is in $E^\prime$. On the other hand, if $k\ge1$, then $\alpha = \omega^{\beta_1}+\gamma$ for ordinals $\beta_1,\gamma < \alpha$ and, $$\theta(\alpha)(n)=n^{\theta(\beta_1)(n)}+\theta(\gamma)(n).$$ So $\theta(\alpha)$ is in $E^\prime$ whenever $\theta(\beta_1)$ and $\theta(\gamma)$ are. Transfinite induction then defines $\theta\colon\epsilon_0\to E^\prime$.

To show that $\theta$ is onto, it just needs to be shown that for any two ordinals $\alpha,\gamma < \epsilon_0$ then $n\mapsto\theta(\alpha)(n)+n^{\theta(\gamma)(n)}$ is also in the image of $\theta$. Write $\alpha$ in Cantor normal form as above, and let $\tilde\beta_1\ge\cdots\ge\tilde\beta_{k+1}$ be the ordinals $\beta_1,\ldots,\beta_k,\gamma$ arranged into decreasing order. Setting $\tilde\alpha=\omega^{\tilde\beta_1}+\cdots+\omega^{\tilde\beta_{k+1}}$, $$\theta(\tilde\alpha)(n)=n^{\theta(\tilde\beta_1)(n)}+\cdots+n^{\theta(\tilde\beta_{k+1})(n)} =\theta(\alpha)(n)+n^{\theta(\gamma)(n)}.$$ So, $\theta$ is a surjective map from $\epsilon_0$ to $E^\prime$.

It just remains to be shown that $\theta$ is (strictly) order preserving. I'll show that if $\alpha > \gamma$ are ordinals then $\theta(\alpha)(n) > \theta(\gamma)(n)$ for large $n$. By induction, it can be assumed that this is true whenever $\alpha,\gamma$ are replaced by smaller values. Again, using Cantor normal form, $$\alpha=\omega^{\beta_1}+\cdots+\omega^{\beta_k}, \gamma=\omega^{\tilde\beta_1}+\cdots+\omega^{\tilde\beta_j}$$ where $\beta_1\ge\cdots\ge\beta_k$ and $\tilde\beta_1\ge\cdots\ge\tilde\beta_j$. Letting $i$ be the smallest number such that one of $\beta_i\not=\tilde\beta_j$, $i > j$ or $i > k$ holds then, as $\alpha > \gamma$, we have $i\le k$ and $\beta_i > \tilde\beta_r$ for all $r=i,\ldots,j$. Then, $$\theta(\alpha)(n)-\theta(\gamma)(n)\ge n^{\theta(\beta_i)(n)}-n^{\theta(\tilde\beta_i)(n)}-\cdots-n^{\theta(\tilde\beta_j)(n)}.$$ If $j < i$ then the right hand side is just $n^{\theta(\beta_i)(n)}$. On the other hand, if $j\ge i$ then, using the induction hypothesis, $n^{\theta(\beta_i)(n)}/n^{\theta(\tilde\beta_r)(n)}\to\infty$ for $r\ge i$, so the right hand side tends to infinity. In either case, $\theta(\alpha)(n) > \theta(\gamma)(n)$ for large $n$.

-
Does anything change if we replace exponentiation with tetration? en.wikipedia.org/wiki/Tetration – TauMu May 23 '13 at 2:25
Well, you couldn't use the identity $(n^{n^f})^{n^{n^g}}=n^{n^{f+n^g}}$, so this argument wouldn't work. I'm not sure if it would be well-ordered in that case. – George Lowther May 23 '13 at 2:33
With tetration, it will be a well quasi-order per mathoverflow.net/questions/131596 . I seems very plausible that the order is also linear (hence a well order), though I don’t see an immediate simple argument. As for the order type, if I understand it correctly, the results from www1.maths.leeds.ac.uk/~rathjen/KRUSKAL.neu.pdf should imply that it is bounded by $\vartheta\Omega^\omega$ (whatever that means), but that’s probably an overkill. – Emil Jeřábek May 24 '13 at 11:36

This is a partial answer, and I am unsure about part of it.

I claim that these functions are well-ordered by eventual domination, and the order type is at most the ordinal $\epsilon_0$.

First, your collection of functions can be identified with the unary terms that give rise to them, the unary terms in the term algebra in the language you have presented, terms with one free variable $n$ in the language with only the binary exponentiation function symbol. Examples of such terms are the expressions that appear in your question.

$$(n^n)^n\ \ \ \ \ (n^{n^n})^{n^n}\ \ \ \ \ n^{n^n}\ \ \ \ \ (n^{n^n})^{n^{n^n}}$$

To any such expression $f(n)$, we may associate to it the ordinal $f(\omega)$, obtained by replacing the variable $n$ with the ordinal $\omega$ and interpreting the resulting expression using the natural arithmetic on ordinals, rather than the usual arithmetic. That is, we resolve $(a^b)^c$ as $a^{b\mathop{\sharp}c}$ using the natural product $b\mathop{\sharp} c$, which is a commutative version of ordinal multiplication.

$$(\omega^\omega)^\omega\ \ \ \ \ (\omega^{\omega^\omega})^{\omega^\omega}\ \ \ \ \ \omega^{\omega^\omega}\ \ \ \ \ (\omega^{\omega^\omega})^{\omega^{\omega^\omega}}$$

All these resulting ordinals have a finitary exponential representation using $\omega$, and therefore are less than epsilon naught $\epsilon_0$.

I claim that this correspondence respects eventual domination; in other words, the function given by term $f(n)$ is eventually dominated by the function given by term $g(n)$ if and only if $f(\omega)\lt g(\omega)$ as interpreted in natural ordinal arithmetic. (Note: the reason to use the symmetric multiplication arises from the fact that $(\omega^{\omega})^{\omega^\omega}=\omega^{\omega^{1+\omega}}=\omega^{\omega^\omega}$ with usual ordinal arithmetic, even though $(n^n)^{n^n}$ dominates $n^{n^n}$; but the natural ordinal arithmetic gives the right answer here.) This claim has an affinity with the usual analysis of the representation of ordinals below $\epsilon_0$ in terms of complete (hereditary) base $n$, as used in Goodstein's theorem. Basically, the eventual domination order is determined by what might be called the stack height of the term expression, and one reduces inductively to comparing the terms that arise as coefficients of that tallest stack. The value of an ordinal exponential expression of $\omega$ is determined in exactly the same way, and so these two orders agree.

If this is right, then the eventual domination order is indeed a well-order, and the order-type is at most $\epsilon_0$, as I claimed.

As to whether the order-type reaches $\epsilon_0$ or not, I'm unsure, but I suspect it is strictly less than $\epsilon_0$. The reason is that the ordinals $f(\omega)$ face a severe restriction in their representation in complete base $\omega$. The complication is that not every ordinal arises as $f(\omega)$ for a term in your algebra. For example, the ordinal $\omega^2\cdot 4+\omega^3\cdot99$ is less than $\epsilon_0$, but it does not arise as an ordinal $f(\omega)$ for any term in your algebra. The ordinals $f(\omega)$ seem to be restricted in their complexity, and so it is conceivable that the total order type might be less than $\epsilon_0$. Nevertheless, it is possible to get some natural number coefficients appearing, as with

$$(\omega^\omega)^\omega=\omega^{\omega^2}\ \ \ \text{ and }\ \ (\omega^{\omega^2})^\omega=\omega^{\omega^3},$$

which arise as the ordinals of the corresponding terms. Perhaps if one can percolate this phenomenon upward to get arbitrary hereditary base $n$ expressions eventually high up in the exponents, then the order type will be $\epsilon_0$.

Meanwhile, let me mention that if one had a slightly more generous algebra, allowing addition and the natural number constants (which would arise from the zero function via $1=\omega^0$), then the order type would be fully $\epsilon_0$, since every ordinal less than $\epsilon_0$ would arise as $f(\omega)$ for a corresponding term in the algebra in a completely natural way.

-
Looks to me that it is of ordinal type $\epsilon_0$. – George Lowther May 23 '13 at 0:03
It seems like it's easy to embed all the ordinals less than $\epsilon_0$ in this ordering, because by taking a 'virtual logarithm' we essentially shunt exponentiation is shunted down to multiplication, and by taking another multiplication is shunted down to addition. $(n^{f(n)})^n = n^{n\cdot f(n)}$ so if we can 'generate' an expression of the form $f(n)$ in an exponent then we can generate an expression of the form $n\cdot f(n)$. (continued next comment :-) – Steven Stadnicki May 23 '13 at 0:06
Likewise, if we have an expression of the form $n^{n^{f(n}}$ then by exponentiating by $n^{g(n)}$ we get $\left(n^{n^{f(n)}}\right)^{\left(n^{g(n)}\right)} = n^{\left(n^{f(n)}\cdot n^{g(n)}\right)} = n^{n^{(f(n)+g(n))}}$, so on the second level of exponential if we have expressions of the form $f(n)$ and $g(n)$ we can generate an expression of the form $f(n)+g(n)$ (and in particular, we can generate $f(n)+1$). This should be enough to generate all ordinals $\lt\epsilon_0$. – Steven Stadnicki May 23 '13 at 0:08
Define a map $\theta$, say, from $\epsilon_0$ to $\mathbb{N}^\mathbb{N}$ as follows. Take 0 to the 0 function. Then every ordinal $\alpha < \epsilon_0$ can be written as $\omega^\beta+\gamma$ for ordinals $\beta,\gamma < \alpha$. Write $\theta(\alpha)(n)=n^{\theta(\beta)(n)}+\theta(\gamma)(n)$. Transfinite induction defines $\theta\colon\epsilon_0\to\mathbb{N}^{\mathbb{N}}$. Now map to the set $E$ by taking an ordinal $\alpha$ to the function $n\mapsto n^{n^{\theta(\alpha)(n)}}$. – George Lowther May 23 '13 at 0:10
It is difficult to imagine any plausible candidate below $\epsilon_0$ because they all have a non-self-referential representation in the Cantor normal form, i.e. basically are exponential polynomials. So why it would be an $\alpha$ rather than, say, $\omega^\alpha$? – Vladimir Reshetnikov May 23 '13 at 0:59