Addition and multiplication are commutative but exponentiation and tetration are not. Do we know why?

Question

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

Answer 1

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.)

Answer 2

The other answer is excellent, but this is a question I have thought a lot about as a high-schooler so I will ad a second answer.

The form in which I pondered this question was:

Addition and multiplication look very much alike. They are both commutative, both associative etc. How is it then possible that exponentiation, which is 'created from multiplication' in exactly the same way that multiplication was created from addition is so much more ugly than multiplication? What mysterious property $P$ that addition possesses but multiplication lacks explains the commutativity of multiplication?

Part of my fascination with my question came from the fact that a priori, intuitively, I would have expected that it was the commutativity of addition, not some stealthy property $P$, that guaranteed the commutativity of multiplication. Now that this is patently false, we have a mystery at our hands. (I read a similar sentiment in the Original Post.)

---

The answer to the bold question above that I arrived it is this:

(P) Under addition the natural numbers are generated by the single number 1, meaning that every number can be made my adding 1 to itself

By contrast, under multiplication, no single number genarates all of $\mathbb{N}$. There we need infinitely many generators: the primes.

I will prove that (in the language of the Original Post) $f$ having property $P$ above is necessary for $g$ being commutative.

Of course similarly one can ask for a property $Q$ of $f$ that explains associativity of $g$ in the same way, but this has been taken care of in the other answer.

---

Before the proof some remarks on $g$:

In the expression $g(a, b)$ the number $a$ need not really be a number. It can be an element of any set $A$ on which a binary operation $f$ is defined.

By contrast the number $b$ really must be a natural number.

This is already true in order for the induction in the definition by the OP to make sense, but I'd like to go a step further and claim that the 'correct' definition of $g$ (given arbitrary $f$ on some $A$) is this:

$g(a, b) := f(f(f(\ldots f(f(a, a), a), \ldots),a), a)$ with $b$ appearances of $a$

I know that there is a taboo among adult mathematicians to openly view numbers as actually counting actual stuff that you can actually see with your actual eyes, and I appreciate that the OP went through the trouble of rewriting the definition in a form that resembles mathematics as it is written, but I think that we can all agree that in this case this is the $g$ we are all secretly thinking about.

---

With this definition in hand the proof is essentially one line.

From the natural definition of $g$ we immediately have that $g(a, 1) = a$ for all $a$ (just write a single $a$ and conclude that you just wrote a single $a$). Putting this in more mathematical terms:

For every $g$ (including multiplication, exponentiation, tetration etc) we have that $1$ is a right unit, with no conditions whatsoever on $f$

Now in general there is no reason to expect $g$ to have a left unit as well, except, of course, when we demand $g$ to be commutative! When $g$ is commutative it follows from $g(a, 1) = a$ for all $a$ that $g(1, a) = a$ for all $a$ and unpacking the definition this just says that:

(P') For all $a$ we have that $a = f(f(f(\ldots f(f(1, 1), 1), \ldots),1), 1)$ with $a$ appearances of the number $1$.

(This is of course just the property $P$ from above, which is a bit clearer if we write it for the special case that $f = +$:

($P''$) For all $a$ we have that $a = 1 + \ldots + 1$ with $a$ appearances of $1$

)

---

Final question:

Comparing $P'$ to $P''$ it is clear that when we demand that $f$ is associative in addition to $g$ being commutative we get that $f$ necessary equals $+$, similar to what happens in the other answer.

What is not clear to me is if we can define a (necessarily) non-associative $f$ on $\mathbb{N}$ not equal to $+$ that still leads to commutative $g$, (and hence necessarily satisfies $P'$).

This is a question I never asked as a high-schooler partially because back then I still considered the non-commutativity of exponentiation (rather than the commutativity of multiplication) to be the miracle and partially because it was inspired by the other answer.