29
$\begingroup$

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

$\endgroup$
8
  • 16
    $\begingroup$ Not related to the problem at hand, but one curious fact that I saw on Wikipedia and I can vividly remember is that the list of commutative operations can be extended by taking $a^{\ln b}$ in place of exponentiation. As $a^{\ln b} = e^{\ln a+b} = b^{\ln a}$ this operation is commutative. $\endgroup$
    – mz71
    Feb 5, 2023 at 23:46
  • 4
    $\begingroup$ That logarithmic tower gives you an infinite family in both directions… $\ln(e^x + e^y)$ is the commutative associative operation which addition distributes over $\endgroup$ Feb 6, 2023 at 0:39
  • 7
    $\begingroup$ @mz71 $a^{\ln b}=e^{\ln a \ln b}$, not $e^{\ln(a+b)}$. $\endgroup$
    – Anixx
    Feb 6, 2023 at 1:46
  • 1
    $\begingroup$ @mz71. Nice remark. It is not surprising though, when one remark that $a\ast b = a^{ln(b)}$ is the operation induced on $(0,\infty)$ by $(\mathbb R,\times)$ and $f(x)=\exp(x)$, that is $a\ast b=f(f^{-1}(a)\times f^{-1}(b))$ for every $a,b>0$. $\endgroup$
    – Taladris
    Feb 6, 2023 at 3:01
  • 2
    $\begingroup$ perhaps it is more strange that multiplication is commutative... I remember some MO post saying this is very surprising when you look at it as stated in Peano arithmetic. $\endgroup$ Feb 8, 2023 at 0:03

2 Answers 2

34
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Wow. That's a super cool insight into it. I think the assumption that g(c, 1) = c is super fair. Perhaps it is more powerful than only assuming g(c, 2) = f(c, c) and it certainly implies that. $\endgroup$
    – Rorsa
    Feb 5, 2023 at 16:19
  • 2
    $\begingroup$ I think this gets pretty close to an answer. It seems that associativity + cancellativity is what explains what happens in the particular sequence of operations. Perhaps my question was too general. $\endgroup$
    – Rorsa
    Feb 5, 2023 at 16:24
  • $\begingroup$ In the both cases if $f$ and $g$ satisfy the requirements, then their swap also satisfies. $\endgroup$
    – Anixx
    Feb 6, 2023 at 1:43
6
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Looking at your answer, I can't help but think of how in the definition of the natural numbers using the Church Encoding, natural numbers are conceptualized as repeated application of a function to an argument. If you're not familiar with the Church Encoding, you might want to look into it. $\endgroup$ Nov 3, 2023 at 4:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.