4

Which are all the associative binary operations on natural numbers ? Certain results in this regard can be found in arxiv:math/0508215. It appears that such associative operations cannot grow too fast. Or perhaps, there are also those which have to grow very fast. It is easy to prove that there are infinitely many such associative operations. And in fact, uncountably many, as shown in the mentioned paper. Amusingly, under rather simple natural conditions, the usual addition and multiplication are the only associative binary operations on natural numbers, as wes proved back in 1981, and cited in the mentioned paper. This fact is the motivation for the above question, namely, what happens if we do not ask any conditions on such associative binary operations ? The whole story arose from the observation that certain minimal algebraic and topological axioms determine uniquely the sets on which they hold. An example is the theorem of Pontriaghin proved in the 1930s that the only commutative and algebraically closed field which is not discrete and it is complete is that of complex numbers. And then, one can turn the issue around and ask whether there are simplest infinite sets which determine uniquely some of the algebraic, topological, or other structures on them ? Well, it turns out the the set of natural integers just about determines uniquely addition and multiplication.

Qiaochu Yuan
  • 114,941
Elemer E Rosinger
  • 93
  • 1
    Why not first write down a bijection from the natural numbers to itself that "grows too fast" (e.g. write down a sequence $a_n$ that grows faster than any computable sequence, and then define a bijection swapping 1 and $a_1$, 2 and $a_2$ etc, but not swapping $n$ and $a_n$ if $n$ was $a_m$ for some smaller $m$) and then look at the map on the natural numbers induced by addition, i.e. $a*b=\pi^{-1}(\pi(a)+\pi(b))$ with $\pi$ the bijection$. I don't see any reasonable way of classifying all associative binary ops on the natural numbers. – Kevin Buzzard Jul 09 '10 at 12:45
  • 1
    The construction you suggest is in the mentioned paper. It seems that my question was not clear enough. So that, let me reformulate it again, this time as an open problem :

    Characterize all associative binary operations on the natural integers.

    Or equivalently, characterize all monoidal structures on the natural integers.

    In the mentioned paper, the two theorems characterize addition in this way. For instance, addition is the only associative binary operation whose iterate is commutative. Or, addition is the only right regular associative operation whose iterate is associative.

     – Elemer E Rosinger Jul 09 '10 at 13:15
  • 3
    Some exotic associative operations are listed Link here. My favorite (with $\phi=(1+\sqrt{5})/2$) is $a\ast b = ab - a\lfloor b \phi\rfloor - b \lfloor a \phi \rfloor$, due to Fraenkel, Stolarsky and Porta. – Kevin O'Bryant Jul 09 '10 at 13:27
  • 5
    I don't understand. This question is the same as "classify all countable monoids", which is surely an unreasonable question. – David E Speyer Jul 09 '10 at 14:05
  • The mentioned characterization of addition, obtained in 1981, may possibly suggests that, perhaps, a similar thing could happen with associative binary operations ? Mathematics - even when practiced by young smart fellas - need not be reduced to mere jerk reactions ... It is indeed far more appropriate to keep wondering and pondering about issues ... – Elemer E Rosinger Jul 09 '10 at 18:08
  • 6
    Elemer, I think you are trying to ask two different questions. I think we can all agree that there is probably no reasonable classification of countable monoids. But the fact that you keep saying "the natural numbers" instead of "a countable set" indicates to me that you have a different question in mind, which is something like "classify all monoidal structures which interact nicely with some natural structure on the natural numbers," where you have yet to define either "nicely" or "natural structure on the natural numbers." So... which is it? – Qiaochu Yuan Jul 09 '10 at 20:08
  • 1
    I don't even understand the statement of the theorem of Pontrjagin you use as motivation. Any field $K$ of characteristic $0$ admits a nontrivial rank one valuation; completing, taking the algebraic closure, and completing again gives a complete, algebraically closed nondiscrete valued field of cardinality at least that of $K$. Thus there exist such fields of arbitrarily large cardinality. – Pete L. Clark Jul 09 '10 at 20:34
  • Pete, I do not recall exactly Pontrjagin's theorem, however, it made him famous while still very young in the early 1930s, and it was an answer to a question by the famous topologist Alexandrov : are there minimal algebraic plus topological axioms which nail down a set ? – Elemer E Rosinger Jul 10 '10 at 07:23
  • Qiaochu, indeed, I focus on the natural integers, and not on an arbitrary countable set, since the hoped for description of all associative operations could also contain the natural total order on those integers. The two 1981 theorems which characterize addition, both make use of that total order, since refer to the iterate of a binary oeration, iterate which is defined based on the total order. Most certainly, I would not ask the question in that generality of arbitrary countable sets. – Elemer E Rosinger Jul 10 '10 at 07:24

0 Answers0