Recall that a function $f\colon X\times X \to \mathbb{R}\_{\ge 0}$ is a *metric* if it satisfies:


* definiteness: $f(x,y) = 0$ iff $x=y$,
* symmetry: $f(x,y)=f(y,x)$, and
* the triangle inequality: $f(x,y) \le f(x,z) + f(z,y)$.


A function $f\colon X\times X \to X$ is *associative* if it satisfies:


* associativity: $f(x,f(y,z)) = f(f(x,y),z)$.


If $X=\mathbb{R}\_{\ge 0}$, then it might be possible for the same function to be a metric and associative.  

**Is there an associative metric on the non-negative reals?**


Note that these demands actually make $X$ into a group. The element $0$ is the identity because $f(f(0,x),x) = f(0,f(x,x)) = f(0,0) = 0$ by associativity and definiteness, so again by definiteness $f(0,x) = x$. Every element is its own inverse because $f(x,x)=0$. 


In fact, the following question is equivalent. **Is there an abelian group on the non-negative reals such that the group operation satisfies the triangle inequality?**


Note also that the answer is *yes* if $X=\mathbb{N}$, the non-negative numbers! [Click here for a spoiler](http://en.wikipedia.org/wiki/Bitwise_operation#XOR).  

"Also known as nim-sum."


The question is originally due to [John H. Conway](http://en.wikipedia.org/wiki/John_Horton_Conway). To my knowledge, the question is unsolved even for $X = \mathbb{Q}\_{\ge 0}$, but he does not seem to care about that case. The spoiler above does extend to the non-negative dyadic rationals $\mathbb{N}[\frac 12]$, but apparently not to $\mathbb{N}[\frac 13]$.



Is there an associative metric on the non-negative reals?
Seems that this is possible. Here is a (non-constructive) proof. 
Suggestions are welcome.


The proof is inspired by [Mazurkiewicz's argument](http://www.mathnerds.com/best/mazurkiewicz/index.aspx). This is second version
of the proof: it includes improvements in
the set-theoretic argument suggested by Joel David Hamkins, and also 
hopefully clarifies some issues
raised in comments. Thanks for the comments!


Goal: Construct a commutative group structure $\star$ on non-negative 
reals
${\mathbb R}\_{\ge 0}$ such that $x\star y\le x+y$ and $x\star x=0$.


Remark: Note that $0$ is automatically a neutral element, and that such a 
commutative group is in fact
a vector space over $ {\mathbb F}\_2 $. Also, we automatically have the 
triangle inequality:
$$x\star z=x\star y\star y\star z\le x\star y+y\star z.$$


Step 1: Let us order ${\mathbb R}\_{\ge 0}$ in order type $c$ (continuum). Equivalently,
we choose a bijection $\iota:[0,c)\to{\mathbb R}\_{\ge 0}$, where $[0,c)$ is the set
of ordinals smaller than $c$. Note that for any $ \alpha < c $, we have
$$|\iota([0,\alpha))| < c.$$


We may choose $\iota$ so that $\iota(0)=0$, although 
it is not strictly necessary.


Plan: For every $\alpha\le c$, we will construct a subset 
$S\_\alpha\subset {\mathbb R}\_{\ge 0}$ and a group operation
$\star:S\_\alpha\times S\_\alpha\to S\_\alpha$. The group operation will have the 
required properties: $S\_\alpha$ is
a vector space over $F\_2$ with $0$ being the neutral element, 
and $x\star y\le x+y$. Besides
it will also have the additional property that $S\_\alpha$ is generated as 
a group by $\iota([0,\alpha))$
(in particular, the image is contained in $S\_\alpha$). Moreover, if 
$\beta\prec\alpha$, $S\_\beta$ is a subgroup
of $S\_\alpha$.


In particular, we get a group structure with required properties on $S\_c={\mathbb R}\_{\ge 0}$, 
as claimed. 


Step 2: The construction proceeds by transfinite recursion. The base is 
$S\_0=\lbrace 0\rbrace$ (generated by the empty set).


Step 3. Let us now define $S\_\alpha$ assuming that $S\_\beta$ is already defined for 
$\beta<\alpha$. If $\alpha$ is a limit ordinal, take
$$S\_\alpha=\bigcup\_{\beta<\alpha}S\_\beta.$$
Therefore, let us assume $\alpha=\beta+1$. 


If $\iota(\alpha)\in S\_\beta$, take $S\_\alpha=S\_\beta$.


Step 4. It remains to consider the case when $\alpha=\beta+1$ but $\iota(\alpha)\not\in S\_\beta$.
Since $I=\iota([0,\beta))$ generates $S\_\beta$,  

the cardinality of $S\_\beta$ is at most the cardinality of the set 
of finite subsets of $I$. Therefore, $|S\_\beta| < c$.


Fix a number $k$ between $0$ and $1$, to be chosen later. Define a 
function $f:{\mathbb R}\_{\ge 0}\to{\mathbb R}\_{\ge 0}$ by
$$f(x)=\cases{\iota(\alpha)+k x, \ x \le \iota(\alpha)\cr x+k \iota(\alpha), \ x > \iota(\alpha)}.$$
Now choose $k$ so that $f(S\_\beta)\cap S\_\beta=\emptyset$. This is possible because 
for every $x,y\in S\_\beta$, the equation $f(x)=y$ has at most one solution in 
$k$, so the set of prohibited values of $k$ has cardinality at most 
$|S\_\beta\times S\_\beta|$. (We can use $\iota$ to well-order the interval $(0,1)$;
we can then choose $k$ to be the minimal acceptable value, so as to remove arbitrary choice.)


Step 5. Now define $S\_\alpha=S\_\beta\cup f(S\_\beta)$ and set $\iota(\alpha)\star x=f(x)$ for 
$x\in S\_\beta$. The product naturally extends to all of $S\_\alpha$:
$$f(x)\star f(y)=x\star y\qquad f(x)\star y=y\star f(x)=f(x\star y).$$
It is not hard to see that it has the required properties.


First of all, $S\_\alpha$ is an isomorphic image of $S\_\beta\times({\mathbb Z}/2{\mathbb Z})$;
this takes care of group-theoretic requirement. It remains to 
check two inequalities:


Step 5a: $$f(x)\star f(y)\le f(x)+f(y)\quad(x,y\in S\_\beta),$$
which is true because $f(x)\ge x$, so
$$f(x)\star f(y)=x\star y\le x+y\le f(x)+f(y).$$


Step 5b: $$f(x)\star y\le f(x)+y\quad(x,y\in S\_\beta),$$
which is true because $f$ is increasing and $f(x+t)\le f(x)+t$, so
$$f(x)\star y=f(x\star y)\le f(x+y)\le f(x)+y.$$


That's it.


