III.2 · Metric Spaces — Problem 2 #

← Back to III. Metric Spaces, Problem 2

Problem. On \(\mathbb{R}^n\) define \(\rho_1(\vec{v},\vec{w}) = \sum_{i=1}^n |v_i - w_i|\) (the “taxicab metric” when \(n=2\)). Prove that \((\mathbb{R}^2, \rho_1)\) is a metric space.

Hint #

Check the four metric axioms in turn: non-negativity, the identity of indiscernibles (\(\rho_1(\vec v,\vec w)=0 \iff \vec v=\vec w\)), symmetry, and the triangle inequality. Each one reduces to the corresponding fact about absolute value of real numbers, applied coordinate-by-coordinate and then summed.

Solution #

We have to make sure that all axioms for a metric space are satisfied.

• In the first place, it is easy to see that \(\rho_1\) is always non-negative, since it is a sum of absolute values.
• If \(\vec{v} = \vec{w}\), then \(|v_i - w_i| = 0\) for all \(i\) and consequently \(\rho_1(\vec{v},\vec{w}) = 0\). Conversely, if \(\rho_1(\vec{v},\vec{w}) = 0\), and \(\rho_1(\vec{v},\vec{w})\) is a sum of non-negative numbers, then every \(|v_i - w_i| = 0\). But then \(v_i = w_i\) for all \(i\), or in other words, \(\vec{v} = \vec{w}\).
• Note that \(|v_i - w_i| = |w_i - v_i|\) for all \(i\), so that \(\rho_1(\vec{v},\vec{w}) = \rho_1(\vec{w},\vec{v})\), and the metric is symmetric.
• Note that for all \(i\), we have \(|v_i - z_i| \le |v_i - w_i| + |w_i - z_i|\) by the usual triangle inequality for real numbers. Adding these up for all \(i\), we obtain $$\sum_{i=1}^n |v_i - z_i| \le \sum_{i=1}^n |v_i - w_i| + \sum_{i=1}^n |w_i - z_i|,$$ or, by definition, \(\rho_1(\vec{v},\vec{z}) \le \rho_1(\vec{v},\vec{w}) + \rho_1(\vec{w},\vec{z})\).

Long solution #

Strategy. The proof is a checklist: verify each of the four metric axioms. Since \(\rho_1\) is built from absolute values coordinate by coordinate, every axiom reduces to the corresponding property of \(|\cdot|\) on \(\mathbb{R}\), applied in each coordinate and then summed.

Why “taxicab”: every monotone staircase path from \(\vec v\) to \(\vec w\) in a street grid has length \(|v_1-w_1| + |v_2-w_2| = 4 + 3 = 7\), whereas the straight-line distance is \(5\).

Definition (metric space). A function \(\rho : S \times S \to \mathbb{R}\) is a metric on a set \(S\) if for all \(x,y,z \in S\):

(M1) \(\rho(x,y) \geq 0\) (non-negativity); (M2) \(\rho(x,y) = 0\) if and only if \(x = y\) (identity of indiscernibles); (M3) \(\rho(x,y) = \rho(y,x)\) (symmetry); (M4) \(\rho(x,z) \leq \rho(x,y) + \rho(y,z)\) (triangle inequality).

We argue for general \(n\), since the argument is identical; the case \(n=2\) is the taxicab metric \(\rho_1(\vec v,\vec w) = |v_1 - w_1| + |v_2 - w_2|\) pictured above.

Properties of the absolute value. For all \(a, b \in \mathbb{R}\):

1. \(|a| \geq 0\), with \(|a| = 0\) if and only if \(a = 0\);
2. \(|-a| = |a|\);
3. \(|a + b| \leq |a| + |b|\) (triangle inequality on \(\mathbb{R}\)).

Now the checklist.

(M1) Non-negativity. Each term satisfies \(|v_i - w_i| \geq 0\) by property 1, and a finite sum of non-negative reals is non-negative. Hence \(\rho_1(\vec v, \vec w) \geq 0\).

(M2) Identity of indiscernibles. (\(\Leftarrow\)) If \(\vec v = \vec w\), then \(v_i = w_i\) for every \(i\), so every term \(|v_i - w_i|\) is \(0\) and \(\rho_1(\vec v, \vec w) = 0\).

(\(\Rightarrow\)) Suppose \(\sum_{i=1}^n |v_i - w_i| = 0\). If some term were strictly positive, the sum of non-negative terms would be positive too. So every \(|v_i - w_i| = 0\), which by property 1 gives \(v_i = w_i\) for all \(i\), i.e. \(\vec v = \vec w\).

(M3) Symmetry. For each \(i\), property 2 gives \(|v_i - w_i| = |-(w_i - v_i)| = |w_i - v_i|\). Summing over \(i\),

(M4) Triangle inequality. For each \(i\), add and subtract \(w_i\), then apply property 3:

Summing these \(n\) inequalities and splitting the right-hand sum,

which by definition of \(\rho_1\) says \(\rho_1(\vec v, \vec z) \leq \rho_1(\vec v, \vec w) + \rho_1(\vec w, \vec z)\).

All four axioms hold, so \((\mathbb{R}^2, \rho_1)\), and indeed \((\mathbb{R}^n, \rho_1)\) for every \(n\), is a metric space. \(\blacksquare\)