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



Order type of the smallest set containing the identity function and closed under exponentiation
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](http://en.wikipedia.org/w/index.php?title=Ordinal_arithmetic&oldid=550174961#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$.


