The Discrete Metric

Recall from the Metric Spaces page that if $M$ is a nonempty set then a function $d : M \times M \to [0, \infty)$ is called a metric if for all $x, y, z \in M$ we have that the following three properties hold:

• $d(x, y) = d(y, x)$.

• $d(x, y) = 0$ if and only if $x = y$.

• $d(x, y) \leq d(x, z) + d(z, y)$.

Furthermore, the set $M$ with the metric $d$, denoted $(M, d)$ is called a metric space.

We will now look at a rather important metric of any nonempty set $M$ known as the discrete metric.

Definition: Let $M$ be a nonempty set. The Discrete Metric on $M$ is defined to be the function $d : M \times M \to [0, \infty)$ defined for all $x, y \in M$ by $d(x, y) = \left\{\begin{matrix} 0 & \mathrm{if} \: x = y\\ 1 & \mathrm{if} \: x \neq y \end{matrix}\right.$.

Let's verify that $d$ is indeed a metric. Let $x, y, z \in M$.

For the first condition, suppose that $x = y$. Then $d(x, y) = 0$ and $d(y, x) = 0$, so $d(x, y) = d(y, x)$. Now suppose that $x \neq y$. Then $d(x, y) = 1$ and $d(y, x) = 1$, so $d(x, y) = d(y, x)$ once again.

For the second condition, we have by the definition of $d$ we have that $d(x, y) = 0$ if and only if $x = y$.

For the third condition, suppose that $x = y$. Then $d(x, y) = 0$ and $d(x, z), d(z, y) \geq 0$ so $d(x, y) \leq d(x, z) + d(z, y)$. Now suppose that $x \neq y$. Then $d(x, y) = 1$. The element $z$ cannot equal both $x$ and $y$ since $x \neq y$, so $d(x, z) + d(z, y) \geq 1$ so $d(x, y) \leq d(x, z) + d(z, y)$.

Therefore $d : M \times M \to [0, \infty)$ is indeed a metric on $M$ and $(M, d)$ is a metric space.