# An example of symmetric associative increasing function which cannot be represented as addition

Let $X$ be some connected subset of $\mathbb{R}$. Let $f: X^2\to X$ have following properties:

1. $\forall x, y$: $f(x, y)=f(y,x)$ (Symmetry)
2. $\forall x, y, z$: $f(x, y)>f(x,z)\iff y>z$ (Strictly increasing on any argument)
3. $\forall x, y, z$: $f(x, f(y, z))=f(f(x, y), z)$ (Associativity)

We call $f$ addition-like, if there exists an injection $\phi:X\to\mathbb{R}$ such that $\forall x, y$: $\phi(f(x,y))=\phi(x)+\phi(y)$.

Can $f$ be not addition-like?

Some examples:

1. $f(x,y)=xy, x>0,y>0$, then $\phi(x)=\ln(x)$
2. $f(x,y)=xy+x+y, x>0,y>0$, then $\phi(x)=\ln(x+1)$

I do not know the answer to the question because I have trouble finding such $f$ at all except explitictly using addition/multiplication with some mapping, which obviously yields addition-like function by definition and multiplication being addition-like.

Let $$f(x,y) = [x] + [y] + s(s^{-1}\{x\} + s^{-1}\{y\})$$

Here $$[x]$$ is the integer part of $$x$$ and $$\{x\}$$ is the fractional part of $$x$$ and $$s$$ is any order preserving bijection between $$[0,\infty)$$ and $$[0,1)$$ (e.g. the sigmoid function).

Then there’s no [edit: order-preserving] $$\phi$$ because there are infinitely many elements, namely any element of $$[0,1)$$, which stay bounded under $$f$$. By this I mean:

Let $$f^2(x) = f(x,x)$$ and $$f^n(x) = f(f^{n-1}(x), x)$$. (For the case of addition this is just $$n \cdot x$$).

Let's say an element $$x$$ grows without bound positively (resp. negatively) under $$f$$ if for all $$t \in \mathbb{R}$$ there exists $$n$$ such that $$f^n(x) > t$$ (resp. $$f^n(x) < t$$).

Let's say an element $$x$$ stays bounded under $$f$$ if it neither grows without bound positively nor negatively.

Then for the case of $$\mathbb{R}$$ with addition, only $$0$$ stays bounded under $$+$$, so there can be no order-preserving injection $$\phi$$ as above given that we have infinitely many elements which stay bounded under $$f$$.

Essentially this is using the additive structure of $$\mathbb{Z} \times \mathbb{R}_{\geq 0}$$ with the dictionary ordering as the order structure.

Added: If we don't require $$\phi$$ to be order-preserving, then additively $$\mathbb{Z} \times \mathbb{R}_{\geq 0} \subset \mathbb{Q} \times \mathbb{R} \cong \mathbb{R}$$ as both are $$\mathbb{Q}$$ vector spaces of the same dimension, so there is a (necessarily non-order-preserving) $$\phi$$ for this example.

In general without the requirement that $$\phi$$ be order-preserving:

The commutative and associative properties of $$f$$ endow $$X$$ with the structure of a commutative monoid and the order property implies that it is cancellative and torsion-free (see Affine monoid on Wikipedia; not all of the properties on that page apply here as we are not in the finitely generated case).

Then the group of differences (see the article above again) of this monoid is a torsion-free commutative group in which it embeds. This then (see here) embeds in a $$\mathbb{Q}$$ vector space, which can be taken to be of cardinality at most $$\mathbb{R}$$, and thus embeds in $$\mathbb{R}$$ additively. The composition of these embeddings preserving the additive structure gives a map $$\phi$$ as in the question.

• Interesting. Seems like it works if $\phi$ is presumed to be monotonous, but I am not sure that it cannot be some ugly function, which sends every $[n,n+1)$ into some everywhere dense subset. Mar 15, 2018 at 3:20
• @SergeSeredenko Yes, if $\phi$ need not be order-preserving then there does exist such an "ugly function" in this case: see my added paragraph.
– aes
Mar 15, 2018 at 4:48
• Tbh, I only thought about ugly map when read your proof, initially I considered nice maps (looking for non-addition-like functions in kinda topological sense, not that AC group mess). So despite the fact that I cannot fully verify the last part of the answer, since it's just too hard, I will accept it because your example with interval magic is exactly what I had in mind when posing the problem. Thank you. Mar 15, 2018 at 16:09
• @SergeSeredenko It’s an interesting problem how different properties of f affect the result. My example above is not continuous, and in fact is sort of an end run around what you maybe were trying to avoid with your requirement that X be connected. If we impose continuity, or maybe we need differentiability, I suspect we’d again find that $\phi$ can always be found. Possibly via some integration / diff eq solution. (We’d want something like the exponential map from Lie groups.)
– aes
Mar 15, 2018 at 19:56