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.
$\begingroup$
$\endgroup$
9
-
1$\begingroup$ 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. $\endgroup$– Kevin BuzzardCommented Jul 9, 2010 at 12:45
-
1$\begingroup$ 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. $\endgroup$– Elemer E RosingerCommented Jul 9, 2010 at 13:15
-
3$\begingroup$ Some exotic associative operations are listed <a href="math.uni-bielefeld.de/~sillke/PUZZLES/… here</a>. 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. $\endgroup$– Kevin O'BryantCommented Jul 9, 2010 at 13:27
-
5$\begingroup$ I don't understand. This question is the same as "classify all countable monoids", which is surely an unreasonable question. $\endgroup$– David E SpeyerCommented Jul 9, 2010 at 14:05
-
6$\begingroup$ 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? $\endgroup$– Qiaochu YuanCommented Jul 9, 2010 at 20:08
|
Show 4 more comments