Metric space

[vvaann]

For every set S and every metric d on S, which of the following is a metric on S?

A. 4 + d
B. exp(d) - 1
C. d - |d|
D. d^2
E. sqrt(d)

Answer:

SPOILER: E

[matroid]

It's E by definition.

[vvaann]

What is the definition actually??

[matroid]

Well, well, my favorite topology textbook says (without the important, but now not so very important details), d is a metric if it satisfies the following 2 axioms:

i) d(a, b) = 0 if and only if a=b
ii) d satisfies the triangle-inequality, ie. d(a, b) + d(a, c) >= d(b, c)

Obviously, the second axiom is the tricky one. But using only the first axiom one can immediately eliminate the answers A and C.

B and D will be wrong. Since these are convex functions, one can quickly find counterexamples. So E is just fine. (I hate selecting an answer by eliminating the other four... )

Md.

[vvaann]

Great again, matroid .

BTW, we can show the second axiom satisfied by the answer E as follows:

We have: d(a,b) + d(b,c) > d(a,c)

<=> sqrt(d(a,b))^2 + sqrt(d(b,c))^2 > sqrt(d(a,c))^2

=> sqrt(d(a,b))^2 + sqrt(d(b,c))^2 + 2*sqrt(d(a,b))*sqrt(d(b,c))> sqrt(d(a,c))^2

=> [sqrt(d(a,b)) + sqrt(d(b,c))]^2 > sqrt(d(a,c))^2

=> sqrt(d(a,b)) + sqrt(d(b,c)) > sqrt(d(a,c))

=> sqrt(d) is a metric

[Dragonfinity]

There were 2 very important parts left our of the definition above, specifically that the function d is always greater than or equal to zero, and the function is not affected by the order of the points. The famous Munkres text on Topology gives the following definition:

DEFINITION: A metric on a set Xis a function d:X x X -> R ("distance") such that
(1) d(x,y) >= 0, for all x,y in X AND d(x,y) = 0 iff x = y.
(2) d(x,y) = d(y,x)
(3) d(x,y) + d(y,z) >= d(x,z)

(a) is not a metric because d(x,x) = 4
(b) is clearly not a metric because it violates the non-negativity of a metric
(c) is not a metric because d(x,y) is nonnegative, so |d| = d, and d - |d| = 0, even if x is not equal to y
(d) is not a metric because of the triangle inequality: Let S be the real number line, and let d be the standard metric, and denote d^2 by D. Then, D(1,2) + D(2,4) = 1 + 4 < 9 = D(1,4), in violation of the triangle inequality.

It is unecessary to prove (e) as the question states that one of the choices is a metric and we have shown the other 4 are not metrics. Nevertheless, letting D denote sqrt(d):

(1) d(a,b) >= 0 implies that D(a,b) >= 0, since we always assume that the square root function takes the positive square. Further, let D(a,b) = 0, then D^2 = 0, so d(a,b) = 0, and a = b. Similarly, if a = b, d(a,b) = 0, so D(a,b) = 0.
(2) d(a,b) = d(b,a) implies sqrt(d(a,b)) = sqrt(d(b,a)) >= 0, again since the sqrt function takes the positive square; hence, D(a,b) = D(b,a).
(3) vvann's proof looks correct, except he used > instead of >=; however, that substitution can be made in every line w/o altering the proof (including the addition of 2*sqrt(d(a,b))*sqrt(d(b,c))>, as we do not know if a = b or b = c).

C

[matroid]

Originally Posted by Dragonfinity

There were 2 very important parts left our of the definition above, specifically that the function d is always greater than or equal to zero, and the function is not affected by the order of the points. The famous Munkres text on Topology gives the following definition:

DEFINITION: A metric on a set Xis a function d:X x X -> R ("distance") such that
(1) d(x,y) >= 0, for all x,y in X AND d(x,y) = 0 iff x = y.
(2) d(x,y) = d(y,x)
(3) d(x,y) + d(y,z) >= d(x,z)

I don't think I left out anything. What you write is correct, but if you write the triangle inequality the way I quoted, than the 2 "missing" properties follow from the other two axioms.

For example, if we substitute b=c in ii) we get:
d(a,b) + d(a,b) >= d(b,b) = 0, so 2d(a,b) >=0 which yields that d(a, b) >= 0

Also if we substitute a=c we get:
d(a,b)+d(a,a) >= d(b,a), so d(a,b)>=d(b,a). Since this holds for all a and b, it also holds when we swap the two variables. So d(a,b)>=d(b,a)>=d(a,b), and so we have proven that the function is not affected by the order of the points.

Md.

[Dragonfinity]

Interesting Matroid, thanks. Never really thought about it. Your reasoning is sound. Although defining the metric in this fashion makes more difficult the use of variants, such as quasi-metrics (which is obtained by dropping the property of symmetry).

C