1
$\begingroup$

I am looking to prove whether or not the following statement is true:

Let $M$ be a set and $D_1$ and $D_2$ metrics on M such that they form a metric space. Then $(M, \min(D_1 , D_2))$ forms a metric space.

Proof: By the definiton of a metric space, the above must satisfy the triangle inequality, or, for some $a,b,c \in M$:

$$ \min [ D_1 (a,c) , D_2 (a,c) ] \le \min [ D_1 (a,b) , D_2 (a,b) ] + \min [ D_1 (b,c) , D_2 (b,c) ] $$

Suppose $\min [ D_1 (a,c) , D_2 (a,c) ] = D_1(a,c)$, and suppose that at least one of the $\min$ functions on the right-hand side is equal to $D_2$, then the triangle-inequality may or may not hold.

From here, would my proof be considered complete?

Or, would I be better providing further clarification, such as a counter-example?

Assume some values for each of the $D$'s that satisfy the triangle inequality for each individually and insert them into the triangle inequality.

$$ \min [ 2 , 5 ] \le \min [ 2 , 1 ] + \min [ 0 , 4 ] $$

This inequality is false, and thus their exists some values such that $(M, \min(D_1 , D_2))$ does not form a metric space.

$\endgroup$
  • 2
    $\begingroup$ Counterexample is better. $\endgroup$ – Cameron Buie Jun 17 '13 at 3:59
  • $\begingroup$ Your numerical example can't occur for actual metrics. $\endgroup$ – Ted Shifrin Jun 17 '13 at 4:14
  • 1
    $\begingroup$ Note that you don't lose any generality assuming that $M$ has exactly three elements. $\endgroup$ – dfeuer Jun 17 '13 at 4:56
  • $\begingroup$ Also, a computer can look for counterexamples quite quickly. $\endgroup$ – dfeuer Jun 17 '13 at 5:04
3
$\begingroup$

The argument as it stands is far from complete: you’ve shown that there is at least a possibility that the triangle inequality might fail, but you’ve not actually shown that it can fail and sometimes does. For that you want a counterexample, and it has to be a real one, not a hypothetical one, arising from verified metrics $D_1$ and $D_2$.

As was noted in the comments, a three-point space is sufficient. Take $X=\{0,1,2\}$, and let $D_1$ be the usual metric. The idea will be to choose $D_2$ so that

$$\min\{D_1(0,2),D_2(0,2)\}>\min\{D_1(0,1),D_2(0,1)\}+\min\{D_1(1,2),D_2(1,2)\}\;,$$

i.e.,

$$\min\{2,D_2(0,2)\}>\min\{1,D_2(0,1)\}+\min\{1,D_2(1,2)\}\;.\tag{1}$$

To simplify matters, we could try building $D_2$ so that $D_2(0,2)=2$, and $(1)$ then becomes simply

$$2>\min\{1,D_2(0,1)\}+\min\{1,D_2(1,2)\}\;.\tag{2}$$

If one of $D_2(0,1)$ and $D_2(1,2)$ were less than $1$ and the other greater than $1$, $(2)$ would hold, and we’d have our counterexample. Can you find values for $D_2(0,1)$ and $D_2(1,2)$ so that $D_2(0,1)<1$, $D_2(1,2)>1$, and $D_2$ is a genuine metric on $X$?

$\endgroup$
  • $\begingroup$ Let $D_2(0,2) = 2$, $D_2(0,1) = 1/2$, and $D_2(1,2) = 2$. Then $2>1/2+1$, while $D_2$ is clearly a metric. Or so it appears to me. The minimalist in me wants the set of natural numbers with the smallest possible maximum for which there exist $D_1$ and $D_2$ with values in that set. That problem is easily solved by computer, but I don't have one on me. $\endgroup$ – dfeuer Jun 17 '13 at 21:58
  • 1
    $\begingroup$ @dfeuer: Yes, that will work. Or you could let $D_2(0,1)=\frac12$ and $D_2(1,2)=\frac32$. In fact, as long as $D_2(0,1),D_2(1,2)$, and $D_2(0,2)$ are the sides of a (possibly degenerate) triangle, you have a metric. Thus, you can take $X=\{0,2,3\}$ with the usual metric for $D_1$ and $D_2(0,2)=1,D_2(2,3)=2$, and $D_2(0,4)=3$ to get an example in which both metrics have integer values $\le 3$. $\endgroup$ – Brian M. Scott Jun 18 '13 at 20:50
  • $\begingroup$ I assume that $4$ was supposed to be a $3$, but aside from that, this does indeed appear to be a minimal example. $\endgroup$ – dfeuer Jun 18 '13 at 21:17
  • $\begingroup$ @dfeuer: Yes, $4$ was a typo for $3$. $\endgroup$ – Brian M. Scott Jun 18 '13 at 21:24

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.