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. 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.
I'd like to present a proof without transfinite induction. As has been mentioned, such a commutative group is a vector space over $\mathbb{F}_2$. It seems we cannot write down a Hamel basis explicitly, which means this proof is not constructive either. But by the Axiom of Choice, a Hamel basis exists. Denote this basis by $\mathcal{B}$. By definition, each $x \in \mathbb{R_{\geq 0}}$ can be uniquely identified with a finite subset $X \subset \mathcal{B}$ such that $x = \sum X$. (Here and throughout we write $\sum X := \sum_{x \in X}x$ as a shorthand; read $\sum X$ as 'sum the elements of $X$').
Claim: Let $x = \sum X$ and $y = \sum Y$ such that $X,Y$ are finite subsets of the aforementioned Hamel basis $\mathcal{B}$. Then $f(x,y) = \sum X \triangle Y$ is an associative metric on $\mathbb{R}_{\geq 0}$ where $\triangle$ is the symmetric difference $X \triangle Y := (X \cup Y)\setminus (X \cap Y)$.
Proof: First we check associativity, which follows from the associativity of the symmetric difference: \begin{align*} f(f(x,y),z) &= f\left(\sum X \triangle Y, z\right) \\ &= \sum X \triangle Y \triangle Z \\ &= f\left(x, \sum Y \triangle Z\right) \\ &= f(x,f(y,z)).\end{align*}
To check the metric axioms is much quicker:
- Definiteness: $f(x,x) = \sum X \triangle X = \sum \varnothing = 0$, and for the other direction $f(x,y) = 0 \implies X \triangle Y = \varnothing \implies X = Y \implies x=y$.
- Symmetry: $f(x,y) = \sum X \triangle Y = \sum Y \triangle X = f(y,x)$.
- Subadditivity: $f(x,y) = \sum X \triangle Y \leq \left(\sum X\right) + \left(\sum Y\right) = x+y$ which suffices.
And just like that, we are done. Note that although this answer is different to the accepted one, it also uses the Axiom of Choice. It would be interesting to know whether AC is not only sufficient but also necessary for such a metric to exist.
The question is unsolved even for $X = \mathbb{Q}_{\geq 0}$
Fortunately, not only is there such a metric, but it's also explicit! The Minkowski question-mark function is a continuous, strictly increasing bijection $?:\mathbb{Q}_{\geq 0} \to \mathbb{N}[\frac{1}{2}]$ given by $$?(q) = a_0 + 2\sum_{k=1}^n \frac{(-1)^{k+1}}{2^{a_1 + \cdots + a_k}}$$ where $q = [a_0 ; a_1,...,a_n]$ is the finite continued fraction representation. Since the bitwise exclusive-or operation $\oplus$ is a well-defined metric on the dyadic rationals, the composition $$f(p,q) = ?^{-1}(?(p) \oplus ?(q))$$ is an associative metric for all $p,q \in \mathbb{Q}_{\geq 0}$.
This is my first post, and so I hope this response is above the minimum level of usefulness expected of a response on MO.
Perhaps a start would be to consider metrics of the form $f(x,y)=g(h(g^{-1}(x),g^{-1}(y))$, where $g$ is some invertible function.
We can place restrictions on $g$ and $h$ by considering the conditions for $f(x,y)$ to be a valid metric.
Firstly, definiteness requires $f(x,x)=0$, so we have $h(g^{-1}(x),g^{-1}(x))=g^{-1}(0)$, and so the definiteness requirement reduces to $h(a,b)=g^{-1}(0)=g_0$ iff $a=b$.
Secondly, we have the symmetry requirement. Since we require $f(x,y) = f(y,x)$ it follows that $g(h(g^{-1}(x),g^{-1}(y))) = g(h(g^{-1}(y),g^{-1}(x)))$ and so $h(a,b) = h(b,a)$. If $h$ is continuous, then $g_0$ is either the maximum or minimum value taken on by $h$.
Now, lets turn to the associativity requirement you have specified: $f(x,f(y,z))=f(f(x,y),z)$. We have $f(f(x,y),z)=g(h(g^{-1}(g(h(g^{-1}(x),g^{-1}(y)))),g^{-1}(z)))$. Let $g^{-1}(x)=a$, $g^{-1}(y)=b$ and $g^{-1}(z)=c$. Then $g^{-1}(f(f(x,y),z))=h(h(a,b),c)$ and $g^{-1}(f(x,f(y,z)))=h(a,h(b,c))$, and so the associativity requirement on $f$ becomes an associativity requirement on $h$.
Applying the third condition, the triangle in equality, we obtain the restriction that $g \circ f$ obeys the triangle in equality. Since this is not specifically a condition on $f$, it seems that a reasonable approach would be to look for any function $h(a,b)$ with the following properties: 1) There exist some $g_0$ such that $h(a,b)=g_0$ iff $a=b$, 2) $h(a,b)=h(b,a)$ and 3) h(h(a,b),c)=h(a,h(b,c)). Since we can set $g_0=0$ without loss of generality (by choosing $g'(x) = g(x)-g_0$), finding a $h$ satisfying only 3 criteria: 1) Definiteness, 2) Symmetry and 3) Associativity, would seem to go a long way towards producing a metric of the desired form.