Identities of natural number exponentiation. Consider the binary operation of exponentiation on the set of nonnegative integers, defined so that $ n^0=1, \ \forall n \in \mathbb N $, including 0. Let us call this operation $p$. 
Are all the identities that are true for exponentiation generated by the single equation $p(p(x,y),z)=p(p(x,z),y)$? 
In other words, this would say that there are no nontrivial identities aside from $(x^y)^z=(x^z)^y$. 
And if this is not the case, is there some larger finite set of identities from which all the others can be derived?
 A: Call the above identity $R$, and where $X$ and $Y$ are two expressions in $\wedge$, say that $X =_R Y$ iff $X$ and $Y$ can be proven equivalent using $R$.
Intuitively, an exponential expression $X$ is equivalent to $x^{\prod T_i}$ for some variable $x$ and exponential expressions $T_i$. But we can't use products here, so define inductively the sequence $T_X$ of branches of $X$ as: $T_v = ()$, $T_{A^B} = (B).T_A$, where the dot denotes concatenation. Also define the leftmost variable $\ell(X)$ as $\ell(v) = v$, $\ell(A^B) = \ell(A)$.
Lemma. Exponential expressions are $R$-equivalent iff their leftmost variables are equal and their sequences of branches are $R$-equivalent (up to permutation).
The proof of this is rather long but straightforward.
It seems obvious that if we have two different exponential expressions in $x$ and some constants, one should be little-o of the other. However, as we will see, we need a relation that plays well with multiplication, similar to how big-O works with addition. In particular, we need something like $f, g \le h \implies f \cdot g \le h$, similar to the addition property for big-O.
Thinking about hyper operators, it seems like the natural thing to do is to bump up big-O one level in the hierarchy:
For functions $f, g : \mathbb{N} \to \mathbb{N}$, say that $f \le_\wedge g$ iff there is $n \ge 1$ such that $f \le_{ev} g^n$, where $ \le_{ev}$ means "eventually less than or equal to", and $g^n(x) := g(x)^n$.
However, since we are trying to separate functions (and $f = g \implies f \le_\wedge g$),  we will use the negation of this relation: $f >_\wedge g$ iff it is not true that $f \le_\wedge g$.
Theorem. If $X$ and $Y$ are expressions in $\wedge$ and a single variable $x$ that are not $R$-equivalent, then $X <_\wedge Y$ or $Y <_\wedge X$ (considered as functions $\mathbb{N} \to \mathbb{N}$).
(The contrapositive seems cleaner to prove looking back on it, but this requires inverting the whole proof.)
It should be possible to prove something similar for the general case by fixing all variables except $x$, but there are complications.
Proof. Since $\ell(X) = \ell(Y)$, $T_X$ and $T_Y$ are not $R$-equivalent as multisets. If there is something in $T_X$ which is $R$-equivalent to something in $T_Y$, remove them both and keep doing this until there are no such pairs. Call the resulting sequences $T_X'$ and $T_Y'$. Now, we proceed by strong induction on expression height/size. $T_X'$ and $T_Y'$ cannot both be empty, because then $X =_R Y$. So consider $S = T_X' \cup T_Y'$ (considered as sets). Since $S$ has no $R$-duplicates, by hypothesis, it is linearly ordered by $<_\wedge$. Let $M = \max S$. $M$ (considered as a function)  is in either $T_X'$ or $T_Y'$, but not both. WLOG it is in $T_X'$.
Lemma. $<_\wedge$ is an irreflexive relation which satisfies (1) $d <_\wedge f \le_{ev} p \implies d <_\wedge p$ and (2) $f \le_{ev} g <_\wedge h \implies fg <_\wedge h$.
Proof. $\le_\wedge$ is clearly reflexive. 
(1) If $p \le_\wedge d$, then for some $n$ we have $p \le_{ev} d^n$, so $f \le_{ev} d^n$.
(2) If $h \le_\wedge fg$, then for some $n$, $h \le_{ev} (fg)^n \le_{ev} g^{2n}$.
Corollary. $<_\wedge$ is transitive, and moreover $f <_\wedge g$ implies $f^2 <_\wedge g$.
Now notice that first of all, $M \le_{ev} \prod T_X'$. And for any $T, U \in T_Y'$ we have $T \le_{ev} U <_\wedge M$. So, by the above lemma, if we write out the branches in $T_Y'$ in order based on $\le_{ev}$ (which coincides with $<_\wedge$ except when two terms are equal) and successively "join" two adjacent branches by multiplying, we will have $\prod T_Y' <_\wedge M$. Thus $\prod T_Y' <_\wedge \prod T_X'$.
Lemma. If there is some $N$ such that $1 < N \le_{ev} g$ then $f \in O(g) \implies f \le_\wedge g$.
Proof. $f \le_{ev} Mg$ for some $M$ (WLOG $M \ge 1$) so $f \le_{ev} N^{\log_N(M)} g \le_{ev} g^{\log_N(M) + 1}$. And since $M \ge 1$ and $N > 1$, $\log_N(M) > 0$.
This condition clearly holds for all functions we are considering. Therefore, $\prod T_X' \notin O(\prod T_Y')$, so for all $M$, it is not true that $x^{\prod T_Y'} \le_{ev} x^{M\prod T_X'} = (x^{\prod T_X'})^M$, and if we add back in the duplicates, the same does not hold with $T_X$ and $T_Y$ (since $f^h \le_{ev} g^h$ implies $f \le_{ev} g$ for $f, g, h$ which are eventually not equal to 1 or 0). QED.
