# Is this proof complete? Case of a metric space

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.

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

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$?

• 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. – dfeuer Jun 17 '13 at 21:58
• @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$. – Brian M. Scott Jun 18 '13 at 20:50
• I assume that $4$ was supposed to be a $3$, but aside from that, this does indeed appear to be a minimal example. – dfeuer Jun 18 '13 at 21:17
• @dfeuer: Yes, $4$ was a typo for $3$. – Brian M. Scott Jun 18 '13 at 21:24