Is there an associative metric on the non-negative reals? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T16:37:03Z http://mathoverflow.net/feeds/question/16214 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/16214/is-there-an-associative-metric-on-the-non-negative-reals Is there an associative metric on the non-negative reals? aorq 2010-02-24T01:08:41Z 2010-02-26T02:18:40Z <p>Recall that a function $f\colon X\times X\to \mathbb{R}_{\ge 0}$ is a <em>metric</em> if it satisfies</p> <ul> <li>definiteness: $f(x,y) = 0$ iff $x=y$,</li> <li>symmetry: $f(x,y)=f(y,x)$, and</li> <li>the triangle inequality: $f(x,y) \le f(x,z) + f(z,y)$.</li> </ul> <p>A function $f\colon X\times X\to X$ is <em>associative</em> if it satisfies</p> <ul> <li>associativity: $f(x,f(y,z)) = f(f(x,y),z)$.</li> </ul> <p>If $X=\mathbb{R}_{\ge 0}$, then it might be possible for the same function to be a metric and associative. <strong>Is there an associative metric on the non-negative reals?</strong></p> <p>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$. </p> <p>In fact, the following question is equivalent. <strong>Is there an abelian group on the non-negative reals such that the group operation satisfies the triangle inequality?</strong></p> <p>Note also that the answer is <em>yes</em> if $X=\mathbb{N}$, the non-negative numbers! <a href="http://en.wikipedia.org/wiki/Bitwise_operation#XOR" rel="nofollow" title="Also known as nim-sum.">Click here for a spoiler</a>.</p> <p>The question is originally due to <a href="http://en.wikipedia.org/wiki/John_Horton_Conway" rel="nofollow">John H. Conway</a>. 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]$.</p> http://mathoverflow.net/questions/16214/is-there-an-associative-metric-on-the-non-negative-reals/16234#16234 Answer by Joe Fitzsimons for Is there an associative metric on the non-negative reals? Joe Fitzsimons 2010-02-24T05:01:09Z 2010-02-24T19:32:23Z <p>This is my first post, and so I hope this response is above the minimum level of usefulness expected of a response on MO.</p> <p>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.</p> <p>We can place restrictions on $g$ and $h$ by considering the conditions for $f(x,y)$ to be a valid metric.</p> <p>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$.</p> <p>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$.</p> <p>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$.</p> <p>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.</p> http://mathoverflow.net/questions/16214/is-there-an-associative-metric-on-the-non-negative-reals/16328#16328 Answer by t3suji for Is there an associative metric on the non-negative reals? t3suji 2010-02-25T00:01:15Z 2010-02-26T02:18:40Z <p>Seems that this is possible. Here is a (non-constructive) proof. Suggestions are welcome.</p> <p>The proof is inspired by <a href="http://www.mathnerds.com/best/Mazurkiewicz/solution.aspx" rel="nofollow">Mazurkiewicz's argument</a>. 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!</p> <p>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$.</p> <p>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.$$</p> <p>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 &lt; c$, we have $$|\iota([0,\alpha))| &lt; c.$$</p> <p>We may choose $\iota$ so that $\iota(0)=0$, although it is not strictly necessary.</p> <p>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$.</p> <p>In particular, we get a group structure with required properties on $S_c={\mathbb R}^{\ge 0}$, as claimed. </p> <p>Step 2: The construction proceeds by transfinite recursion. The base is $S_0=\lbrace 0\rbrace$ (generated by the empty set).</p> <p>Step 3. Let us now define $S_\alpha$ assuming that $S_\beta$ is already defined for $\beta&lt;\alpha$. If $\alpha$ is a limit ordinal, take $$S_\alpha=\bigcup_{\beta&lt;\alpha}S_\beta.$$ Therefore, let us assume $\alpha=\beta+1$. </p> <p>If $\iota(\alpha)\in S_\beta$, take $S_\alpha=S_\beta$.</p> <p>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$,<br> the cardinality of $S_\beta$ is at most the cardinality of the set of finite subsets of $I$. Therefore, $|S_\beta| &lt; c$.</p> <p>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,&amp;x\le\iota(\alpha)\cr x+k\iota(\alpha),&amp;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.)</p> <p>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.</p> <p>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:</p> <p>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).$$</p> <p>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.$$</p> <p>That's it.</p>