Standard Discrete Metric is Metric

From ProofWiki
Jump to navigation Jump to search

Theorem

The standard discrete metric is a metric.


Proof

Let $d: S \times S \to \R$ denote the standard discrete metric on the underlying set $S$ of some space $\struct {S, d}$.

By definition:

$\forall x, y \in S: \map d {x, y} = \begin {cases}

0 & : x = y \\ 1 & : x \ne y \end {cases}$


Proof of Metric Space Axiom $(\text M 1)$

\(\ds \map d {x, x}\) \(=\) \(\ds 0\) Definition of Standard Discrete Metric

So Metric Space Axiom $(\text M 1)$ holds for $d$.

$\Box$


Proof of Metric Space Axiom $(\text M 2)$: Triangle Inequality

Let $x = z$.

\(\ds \map d {x, z}\) \(=\) \(\ds 0\)
\(\ds \leadsto \ \ \) \(\ds \map d {x, y} + \map d {y, z}\) \(\ge\) \(\ds \map d {x, z}\) Definition of Standard Discrete Metric


Let $x \ne z$.

Either $x \ne y$ or $y \ne z$, or both.

So:

\(\ds \map d {x, y} + \map d {y, z}\) \(\ge\) \(\ds 1\) Definition of Standard Discrete Metric
\(\ds \) \(\ge\) \(\ds \map d {x, z}\) Definition of Standard Discrete Metric

So in either case:

$\map d {x, y} + \map d {y, z} \ge \map d {x, z}$

and Metric Space Axiom $(\text M 2)$: Triangle Inequality holds for $d$.

$\Box$


Proof of Metric Space Axiom $(\text M 3)$

Let $x \ne y$.

\(\ds \map d {x, y}\) \(=\) \(\ds 1\) Definition of Standard Discrete Metric
\(\ds \) \(=\) \(\ds \map d {y, x}\) Definition of $d$

So Metric Space Axiom $(\text M 3)$ holds for $d$.

$\Box$


Proof of Metric Space Axiom $(\text M 4)$

\(\ds x\) \(\ne\) \(\ds y\)
\(\ds \leadsto \ \ \) \(\ds \map d {x, y}\) \(>\) \(\ds 0\) Definition of Standard Discrete Metric

So Metric Space Axiom $(\text M 4)$ holds for $d$.

$\blacksquare$


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Standard_Discrete_Metric_is_Metric&oldid=541683"