# Proof that a discrete metric is indeed a metric space

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

• 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 – Dominic Michaelis Aug 26 '13 at 18:34
• 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$ – Daron Aug 26 '13 at 18:36
• Thanks for showing my mistake. Edited. @DominicMichaelis – Siyanda Aug 26 '13 at 18:37

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.

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.

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.