# Chebyshev Distance is Metric

## Theorem

Let $M_1 = \struct {A_1, d_1}, M_2 = \struct {A_2, d_2}, \ldots, M_n = \struct {A_n, d_n}$ be metric spaces.

Let $\displaystyle \mathcal A = \prod_{i \mathop = 1}^n A_i$ be the cartesian product of $A_1, A_2, \ldots, A_n$.

Let $d_\infty: \mathcal A \times \mathcal A \to \R$ be the Chebyshev distance on $\mathcal A$:

$\displaystyle \map {d_\infty} {x, y} = \max_{i \mathop = 1}^n \set {\map {d_i} {x_i, y_i} }$

where $x = \tuple {x_1, x_2, \ldots, x_n}, y = \tuple {y_1, y_2, \ldots, y_n} \in \mathcal A$.

Then $d_\infty$ is a metric,

## Proof

### Proof of $M1$

 $\displaystyle \map {d_\infty} {x, x}$ $=$ $\displaystyle \max_{i \mathop = 1}^n \set {\map {d_i} {x_i, x_i} }$ Definition of $d_\infty$ $\displaystyle$ $=$ $\displaystyle 0$ as $d_i$ fulfils axiom $M1$

So axiom $M1$ holds for $d_\infty$.

$\Box$

### Proof of $M2$

Let $k \in \closedint 1 n$ such that:

 $\displaystyle \map {d_k} {x_k, z_k}$ $=$ $\displaystyle \max_{i \mathop = 1}^n \set {\map {d_i} {x_i, z_i} }$ $\displaystyle$ $=$ $\displaystyle \map {d_\infty} {x, z}$

Then by application of axiom $M2$ for metric $d_k$:

$\map {d_k} {x_k, z_k} \le \map {d_k} {x_k, y_k} + \map {d_k} {y_k, z_k}$

But by the nature of the $\max$ operation:

$\displaystyle \map {d_k} {x_k, y_k} \le \max_{i \mathop = 1}^n \set {\map {d_i} {x_i, y_i} }$

and:

$\displaystyle \map {d_k} {y_k, z_k} \le \max_{i \mathop = 1}^n \set {\map {d_i} {y_i, z_i} }$

Thus:

$\displaystyle \map {d_k} {x_k, y_k} + \map {d_k} {y_k, z_k} \le \max_{i \mathop = 1}^n \set {\map {d_i} {x_i, y_i} } + \max_{i \mathop = 1}^n \set {\map {d_i} {y_i, z_i} }$

Hence:

$\map {d_\infty} {x, z} \le \map {d_\infty} {x, y} + \map {d_\infty} {y, z}$

So axiom $M2$ holds for $d_\infty$.

$\Box$

### Proof of $M3$

 $\displaystyle \map {d_\infty} {x, y}$ $=$ $\displaystyle \max_{i \mathop = 1}^n \map {d_i} {x_i, y_i}$ Definition of $d_\infty$ $\displaystyle$ $=$ $\displaystyle \max_{i \mathop = 1}^n \map {d_i} {y_i, x_i}$ as $d_i$ fulfils axiom $M3$ $\displaystyle$ $=$ $\displaystyle \map {d_\infty} {y, x}$ Definition of $d_\infty$

So axiom $M3$ holds for $d_\infty$.

$\Box$

### Proof of $M4$

Let $x = \tuple {x_1, x_2, \ldots, x_n}$ and $y = \tuple {y_1, y_2, \ldots, y_n}$.

 $\displaystyle x$ $\ne$ $\displaystyle y$ $\displaystyle \leadsto \ \$ $\, \displaystyle \exists k \in \closedint 1 n \,$ $\displaystyle x_k$ $\ne$ $\displaystyle y_k$ $\displaystyle \leadsto \ \$ $\displaystyle \map {d_k} {x_k, y_k}$ $>$ $\displaystyle 0$ as $d_k$ fulfils axiom $M4$ $\displaystyle \leadsto \ \$ $\displaystyle \max_{i \mathop = 1}^n \map {d_i} {x_i, y_i}$ $>$ $\displaystyle 0$ $\displaystyle \leadsto \ \$ $\displaystyle \map {d_\infty} {x, y}$ $>$ $\displaystyle 0$ Definition of $d_\infty$

So axiom $M4$ holds for $d_\infty$.

$\blacksquare$