35
$\begingroup$

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]$.

$\endgroup$

2 Answers 2

23
$\begingroup$

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.

$\endgroup$
15
  • 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$ Feb 25, 2010 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, 2010 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$ Feb 25, 2010 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$ Feb 25, 2010 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, 2010 at 13:40
2
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ If g is even, how can it be invertible? $\endgroup$ Feb 24, 2010 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$ Feb 24, 2010 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$ Feb 24, 2010 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, 2010 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$ Feb 24, 2010 at 20:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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