2
$\begingroup$

QUESTION

Let X be any set and $d : X \times X \to \mathbf{R}$ be given by $$ d(x,y) = \begin{cases} 0, & \text{if $x = y$} \\ 1, & \text{if $x \neq y$} \\ \end{cases}$$

Show that $d$ is a metric on $X$.

REMARKS

I'm interested in getting to understand this question. First, I assume we're discussing what is known as the Discrete Metric here. But I'm finding it a bit "too easy" to prove the axioms. And so I get the impression that I'm doing it wrong.

For example; when looking at the axioms:

  1. $d(x,y) \ge 0$
  2. $d(x,y) = 0 ,\text{iff}: x=y$
  3. $d(x,y) = d(y,x)$

Both appear to be self-explanatory. The definition of the metric space does make it clear and I find myself doing nothing more than re-stating the definition of the metric to "prove" these points.

$4.$ Triangle Inequality: $d(x,y) \le d(x,z) + d(z,y)$ This I showed by considering a number of different cases (but not all of them - should I do all possible computations of the $x=/\neq y = /\neq z$ combination?) and find this to be true in each case.

I guess all I want to know - is, is the proof of this as simple as it looks?

Thanks

$\endgroup$
  • 1
    $\begingroup$ In fact you did something wrong, the first axiom is $d(x,y)\geq 0$ you wrote $\leq$. You show that the axioms are fulfilled via looking at different cases $\endgroup$ – Dominic Michaelis Aug 26 '13 at 18:34
  • 3
    $\begingroup$ Yes, in this case the proof is as simple as it looks. The Discrete Metric is the simplest of all metrics, so proving it is indeed a metric SHOULD amount to more or less restating the axioms. Also it should be $1. \ d (x,y) \ge 0$ $\endgroup$ – Daron Aug 26 '13 at 18:36
  • $\begingroup$ Thanks for showing my mistake. Edited. @DominicMichaelis $\endgroup$ – Siyanda Aug 26 '13 at 18:37
3
$\begingroup$

Of courses some of the cases for the triangle equality can be subsumed: For example, if $x=y$, then the left side is always zero and therefore smaller than the right side. And if $x\ne y$, then all you have to show is that there is a pair of distinct values on the right side, i.e. at least one of $x\ne z,\ z\ne y$ holds.

$\endgroup$
5
$\begingroup$

This already has an answer, but I'd still like to share this method! Often we feel it is "necessary" to give a direct proof of the properties which define a metric, however sometimes it is far easier and less painful to simply prove by contradiction!

Assume that $$d(x,y) > d(x,z) + d(y,z)$$ If $x = y$ the we have an immediate contradiction. If $x \not = y$ then $d(x,y) = 1$ then we must have $d(x,z) = 0$ and $d(y,z) = 0$ but now $x = y$ so we have a contradiction.

$\endgroup$
2
$\begingroup$

We want to prove $$ d(x,y)≤d(x,z)+d(z,y) $$ Since each of the $3$ terms has two possible states ($0$ or $1$) there are $2^3=8$ possible cases. However, we can do better using some logic. In fact we will only need to consider 2 cases: $x=y, x \neq y$

Case 1: $x=y$: By (1): the non-negativity property $$d(x,z)+d(z,y) \geq 0 $$ Therefore when $x=y$, $d(x,y)=0$ and the triangle inequality is satisfied. There's 4 cases gone.

Case 2: $x\neq y$: In the case the only way the triangle inequality can fail is if $x=z,z=y$ giving $0\geq1$. Suppose this is possible. By the transitive property (of the equivalence relation known as equality "="):$$x=z,z=y \implies x=y$$ which is a contradiction to our assumption $x \neq y$. Therefore at least one of the following is true $x\neq z,z\neq y$. This takes care of the final 4 cases.

Therefore the inequality is satisfied.

$\endgroup$

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.