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$?
 A: 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$.
A: 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.
