I was thinking about the idea that succession, addition, multiplication, exponentiation, tetration and so on form a sequence of operations where each is defined as a repeated self application of the previous one.


And then it struck me that the first 2 operations in this sequence are commutative but this breaks at exponentiation.


What exactly breaks? When repeated self application of a commutative operation is itself commutative and when it's not?


That is, for an operation:


$$f: \mathcal{N} \times \mathcal{N} \to \mathcal{N}$$


If I define:


$$g(m, 2) = f(m, m)$$
$$g(m, n) = f(m, g(m, n-1))$$


for any $n \geq 2$.


What conditions $f$ must satisfy for $g$ to be commutative? That is, for:


$$g(a,b) = g(b,a)$$


for all $a$ and $b$?



Addition and multiplication are commutative but exponentiation and tetration are not. Do we know why?
Not really an answer, but too long for a comment: it's worth noting that if we assume that


* $f$ is associative,
* $g$ is associative,
* $g$ is cancellative for at least one $a$, meaning that $g(a,u)=g(a,v)$ implies $u=v$ for this particular $a$,


then $f$ and $g$ *must* be addition and multiplication.


Indeed, let $a,p,q$ be natural numbers, with $a$ such that $g(a,—)$ is cancellative. Then $g(a,pq)$ is the application of $f$ to $pq$ terms all equal to $a$. By associativity of $f$ we can group this as $q$ terms all of which are the application of $f$ to $p$ terms, i.e., $g(a,p)$, so that $g(a,pq) = g(g(a,p),q)$. By associativity of $g$, we can rewrite this as $g(a,g(p,q))$. By the cancellativity assumption, we get $pq = g(p,q)$. We then have $g(1,n) = n$, and since $g(1,m+n)=f(g(1,m),g(1,n))$ (again, by associativity of $f$) we get $m+n=f(m,n)$, as claimed. ∎


**Update:** similarly, if we assume that


* $f$ is associative,
* $g$ has a unit element $e$, meaning that $g(e,n) = n$ for all $n$,


then the same conclusion holds.


The proof is pretty much the same: as above, $g(e,pq) = g(g(e,p),q)$ so the fact that $e$ is a unit for $g$ means $pq = g(p,q)$, and the rest of the proof is identical. ∎


(Note that for all this I'm assuming that $g(c,1) = c$, which is logical if $g(c,n)$ means “$n$-fold application of $f$ to $c$”, but you didn't actually make this part of your definition. I suppose it was an oversight.)


