Chebyshev Distance
Chebyshev distance is a specific form of Minkowski norm (\(l_p\) norm): \[ d_p(x, x^\prime) = ||x - x^\prime||_p \coloneq (\sum_{i=1}^n|x_i - x^\prime_i|^p)^{1/p} \] where \(p \to \infty\). Chebyshev distance is in effect \(\max\limits_i (|x_i - x^\prime_i|)\).
Proof of Discrete Form
Let \(a_i = |x_i - x^\prime_i|\) and without loss of generality let \(a_1 = \max\limits_ia_i = \max\limits_i|x_i - x^\prime_i|\). \[ \begin{aligned} d_p(x, x^\prime) &= \lim_{p \to \infty}(\sum_{i=1}^n|x_i - x^\prime_i|^p)^{1/p} \\ &= \lim_{p \to \infty}(\sum_{i=1}^na_i^p)^{1/p} \\ &= \lim_{p \to \infty}(a_1^p\sum_{i=1}^n(\frac{a_i}{a_1})^p)^{1/p} \\ &= \lim_{p \to \infty}(a_1^p)^{1/p} \cdot \lim_{p \to \infty}(\sum_{i=1}^n(\frac{a_i}{a_1})^p)^{1/p} \\ &= a_1 \cdot \lim_{p \to \infty}(\sum_{i=1}^n(\frac{a_i}{a_1})^p)^{1/p} \\ \end{aligned} \] Because \(\forall i, a_1 > a_i\), then \(\frac{a_i}{a_1} \le 1\), and \[ \begin{aligned} 1 \le &\sum_{i=1}^n(\frac{a_i}{a_1})^p \le n \\ 1^{1/p} \le &(\sum_{i=1}^n(\frac{a_i}{a_1})^p)^{1/p} \le n^{1/p} \text{, where $p > 1$} \\ \lim_{p \to \infty}1^{1/p} \le &\lim_{p \to \infty}(\sum_{i=1}^n(\frac{a_i}{a_1})^p)^{1/p} \le \lim_{p \to \infty}n^{1/p} \\ 1 \le &\lim_{p \to \infty}(\sum_{i=1}^n(\frac{a_i}{a_1})^p)^{1/p} \le 1 \\ \end{aligned} \]
Therefore, \(d_p(x, x^\prime) = a_1 \cdot 1 = a_1 = \max\limits_i|x_i - x^\prime_i|\).
Proof of Continuous Form
Let \(f(x)\) be continuous and bounded on interval \((a, b)\), then, \[ \lim\limits_{p \to +\infty}(\int_a^b |f(x)|^pdx)^{1/p} = \sup\limits_{x \in (a,b)}|f(x)| \]
Let \(S = \sup\limits_{x \in (a,b)}|f(x)|\), then \(\forall\varepsilon > 0, \exists x_0 \in (a,b), |f(x_0)| > S - \varepsilon\). By continuity, \(\lim\limits_{x \to x_0}|f(x)| > S - \varepsilon\), then \(\exists\delta > 0, \forall x \in U(x_0, \delta), ||f(x)| - \lim\limits_{x \to x_0}|f(x)|| < \varepsilon \rightarrow |f(x)| > S - 2\varepsilon\). \[ \begin{aligned} (\int_{x_0 - \delta}^{x_0 + \delta} |f(x)|^pdx)^{1/p} &\ge (\int_{x_0 - \delta}^{x_0 + \delta} (S - 2\varepsilon)^pdx)^{1/p} \\ \lim\limits_{p \to +\infty}(\int_{x_0 - \delta}^{x_0 + \delta} |f(x)|^pdx)^{1/p} &\ge \lim\limits_{p \to +\infty}(\int_{x_0 - \delta}^{x_0 + \delta} (S - 2\varepsilon)^pdx)^{1/p} \\ &= \lim\limits_{p \to +\infty}(2\delta(S - 2\varepsilon)^p)^{1/p} \\ &= S - 2\varepsilon \end{aligned} \] Since \(U(x_0, \delta)\) in within the interval \((a,b)\) and \(|f(x)|^p \ge 0\), then, \[ \begin{aligned} (\int_a^b |f(x)|^pdx)^{1/p} &\ge (\int_{x_0 - \delta}^{x_0 + \delta} |f(x)|^pdx)^{1/p} \\ \lim\limits_{p \to +\infty}(\int_a^b |f(x)|^pdx)^{1/p} &\ge \lim\limits_{p \to +\infty}(\int_{x_0 - \delta}^{x_0 + \delta} |f(x)|^pdx)^{1/p} \\ &\ge S - 2\varepsilon \end{aligned} \] Because \(\varepsilon\) is arbitrarily and positively valued, \(\lim\limits_{p \to +\infty}(\int_a^b |f(x)|^pdx)^{1/p} \ge S\)
On the other hand, \[ \lim\limits_{p \to +\infty}(\int_a^b |f(x)|^pdx)^{1/p} \le \lim\limits_{p \to +\infty}(\int_a^b S^pdx)^{1/p} = \lim\limits_{p \to +\infty}((b - a)S^p)^{1/p} = S \] then, \[ \lim\limits_{p \to +\infty}(\int_a^b |f(x)|^pdx)^{1/p} = S = \sup\limits_{x \in (a,b)}|f(x)| \]