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.
"Also known as nim-sum."

The question is originally due to John H. 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]$.


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.

  • 1
    $\begingroup$ Assuming $x\star y\leq x+ y$, $x\star x=0$, commutativity and associativity of $\star$, then $x\star z=x\star y\star y\star z\leq x\star y + y\star z$. Right? $\endgroup$ – Konrad Swanepoel Feb 25 '10 at 10:57
  • 1
    $\begingroup$ @Konrad Swanepoel: Yes, that's what I meant. @ Pandelis Dodos: No, I mean that $S$ has a set of generators which is an initial segment of the order on all of ${\mathbb R}^{\ge 0}$. If you prefer, you can consider the largest initial segment that is contained in $S$ and require that it generates $S$ as a group; this way, we won't need to mention $I$ explicitly. $\endgroup$ – t3suji Feb 25 '10 at 13:41
  • 2
    $\begingroup$ Your argument can be simplified into a straight transfinite recursion. Once you've fixed the well order, you don't need to apply Zorn's lemma as you do. Rather, you are giving a transfinite recursion: at limit ordinals, you take unions of what you've done so far (this is the content of your Zorn argument), and at successor ordinals, you have the main part of your construction. $\endgroup$ – Joel David Hamkins Feb 25 '10 at 14:35
  • 2
    $\begingroup$ Continuing my earlier comment, there is no need to consider the poset of all triples (I,S,star). Rather, you well order the reals in a order type c=continuum, and then you are defining the group S_alpha and star_alpha for each alpha less than c. Your construction describes how to build S_{alpha+1} and star_{alpha+1} from S_alpha and star_alpha, and at limit ordinals, you take unions. Indeed, I would say just that you are defining star itself by transfinite recursion, and omit the formality of star_alpha. That is, You define S_alpha and star on S_alpha by recursion on alpha. $\endgroup$ – Joel David Hamkins Feb 25 '10 at 15:05
  • 2
    $\begingroup$ @Konrad Swanepoel. Perhaps I am missing something, but why can't we use the same argument for $\mathbb{Q}$? Order it in order type $\omega$, and start the recursion (which is not even transfinite anymore). On each step, choose rational $k$ between $0$ and $1$, since only finitely many $k$ are prohibited, this can be done. $\endgroup$ – t3suji Feb 26 '10 at 13:40

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:

  1. 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$.
  2. Symmetry: $f(x,y) = \sum X \triangle Y = \sum Y \triangle X = f(y,x)$.
  3. 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.

  • $\begingroup$ If g is even, how can it be invertible? $\endgroup$ – Joel David Hamkins Feb 24 '10 at 5:21
  • $\begingroup$ Good point. Requiring g to be invertible is then too strong a condition. Actually, I hadn't really intended what I wrote. It isn't necessary that g be invertible, but only that for and given x>0, the g(x)=g(y) only for y=x or y=-x. Then g^{-1}(g(x)) is taken to be abs(x), but then its not clear the last bit holds. $\endgroup$ – Joe Fitzsimons Feb 24 '10 at 5:44
  • 2
    $\begingroup$ By the way, welcome to MO! It is possible to edit your answer, by clicking on 'edit', if you wanted to clarify your idea along the lines of your comment. $\endgroup$ – Joel David Hamkins Feb 24 '10 at 13:21
  • $\begingroup$ You can find a definite, symmetric, and associative function h by just picking an arbitrary bijection between the non-negative reals and a countable product of (Z mod 2)s. The latter has a natural structure of a group where every element is an involution, so the non-negative reals do as well. The triangle inequality is the hard part here. $\endgroup$ – aorq Feb 24 '10 at 19:57
  • $\begingroup$ The point I was trying to make was that given such a function h, any function of the form $g(h(g^{-1}(x),g^{-1}(y)))$ preserves definiteness, symmetry and associativity, but not necessarily the triangle inequality. So an approach is to pick some h of this form, and then look for a g which will allow you to satisfy the triangle inequality. Handily, g lets us change between, say, multiplication and addition, simply by picking g(x)=exp(x). $\endgroup$ – Joe Fitzsimons Feb 24 '10 at 20:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.