Metric Spaces

Book 2A was about one space, the real line, and one way of measuring distance in it, $|x - y|$. Almost everything proved there used only a few properties of that distance: it is never negative, it is zero only between a point and itself, it is symmetric, and it obeys the triangle inequality. This chapter takes those four properties as a definition. Anything that satisfies them is a metric, and a set with a metric is a metric space.

The gain is enormous. Points on the Earth, strings of letters, binary codewords, continuous functions and (much later) whole geometric shapes all carry natural metrics. Once they do, convergence, continuity, open and closed sets, completeness and compactness all make sense for them, with the same definitions and often the same proofs as on $\mathbb{R}$. The route to Perelman runs through several such spaces: spaces of functions in Courses 3, 4 and 6, a Riemannian manifold viewed as a metric space in 9A.3 Geodesics and the Exponential Map, and finally a space whose points are themselves metric spaces, in which limits of Ricci flows are taken (9B.4 Convergence of Manifolds).

By the end of this chapter you will be able to:

• check the four axioms of a metric, and recognise the standard metrics on $\mathbb{R}^n$, on spheres, on strings and on function spaces;
• define open and closed balls, open and closed sets, interior, closure and boundary, and prove the basic facts that connect them to convergent sequences;
• work with subsets of a metric space, and tell "open in $Y$" from "open in $X$";
• decide whether two metrics on the same set are equivalent, and show that two natural metrics on continuous functions are not;
• compute great-circle, taxicab, Hamming and edit distances, and say what the triangle inequality buys in each case.

1.1Distance, in general

The distance an aircraft cares about is not the distance in any map. It is measured on the sphere, and it differs from the straight-line distance through the Earth and from the distance a ruler measures on a chart. Each of these is a legitimate way of measuring distance between the same pairs of points, and each obeys the same four rules.

The triangle inequality carries nearly all of the weight. It says that a detour through $y$ can't be shorter than going directly. In every argument of 2A.6 Sequences and 2A.9 Continuous Functions that split $|a - c|$ into $|a - b| + |b - c|$, the triangle inequality for $d$ does the same job here, and those arguments carry over word for word.

A useful consequence, the reverse triangle inequality, says that distances to a fixed point change no faster than the point moves:

(Apply the triangle inequality twice, once with $y$ as the detour and once with $x$.)

Limits are unique: if $x_n \to x$ and $x_n \to y$, then $d(x, y) \leq d(x, x_n) + d(x_n, y) \to 0$, so $d(x, y) = 0$ and $x = y$ by positivity. This is the first place positivity is used. Without it, "the limit" would not make sense.

1.2A zoo of metric spaces

1.2.1Three metrics on $\mathbb{R}^n$

For points $x = (x_1, \dots, x_n)$ and $y = (y_1, \dots, y_n)$ of $\mathbb{R}^n$ there are three standard distances:

The first is the Euclidean metric, the ruler distance. The second is the taxicab metric, the distance travelled along a grid of streets. The third is the sup (or maximum) metric, the largest disagreement in any one coordinate.

For $d_{\ell^1}$ and $d_{\ell^\infty}$, the triangle inequality follows coordinate by coordinate from the one on $\mathbb{R}$. For the Euclidean metric it needs one idea.

With $u = x - y$ and $v = y - z$, expanding $\|u + v\|^2 = \|u\|^2 + 2\,u\cdot v + \|v\|^2 \leq (\|u\| + \|v\|)^2$ gives $d_{\ell^2}(x, z) \leq d_{\ell^2}(x, y) + d_{\ell^2}(y, z)$.

The three metrics give the same answer on the real line, and different answers in the plane. The clearest way to see the difference is to draw each one's unit ball, the set of points at distance less than $1$ from the origin.

1.2.2The sphere

Put the Earth's centre at the origin and represent a place by its unit vector $x \in S^2 = \{x \in \mathbb{R}^3 : \|x\| = 1\}$. The great-circle distance on a sphere of radius $R$ is $R$ times the angle between the vectors:

Positivity and symmetry are immediate. The triangle inequality, which says that angles between directions obey $\angle(x, z) \leq \angle(x, y) + \angle(y, z)$, is Exercise 1.16.

The arccos formula loses precision when $x$ and $y$ are close, because $\arccos$ is very steep near $1$. Navigation software uses an equivalent form, the haversine formula, which with latitudes $\varphi_i$ and longitudes $\lambda_i$ reads

For New York and Hong Kong this gives the $12{,}970$ km above.

The Mercator map is a function from (most of) the sphere to the plane, and it does not preserve distance. No map can: there is no way to flatten any piece of a sphere onto the plane while keeping every distance (Gauss's Theorema Egregium, 8A.9 The Curvature of Surfaces). That is the first sign of curvature, the subject of Book 9A.

1.2.3Discrete spaces, codes and strings

On any set, the discrete metric $d(x, y) = 1$ for $x \neq y$ (and $0$ for $x = y$) satisfies the axioms. It is useful mainly as a test case: it shows what can go wrong when a space has no notion of "nearby".

More interesting discrete spaces come from information.

The triangle inequality holds because a position in which $x$ and $z$ differ must be one in which $x$ differs from $y$ or $y$ differs from $z$. For binary strings of length $3$, the space is the eight corners of a cube, and $d_H$ counts edges along a shortest path between corners (Figure 1.4).

For strings of different lengths, Hamming distance is useless: "kitten" and "sitting" don't even line up. The edit distance (or Levenshtein distance) between two strings is the least number of single-character insertions, deletions and substitutions that turn one into the other. From "kitten" to "sitting" it is $3$: substitute k→s, substitute e→i, insert g. It is a metric. The triangle inequality holds because an edit sequence from $x$ to $y$ followed by one from $y$ to $z$ is an edit sequence from $x$ to $z$.

1.2.4Spaces of functions

The most important metric spaces in this guidebook are spaces whose points are functions.

It is a metric: the supremum is finite because $f$ and $g$ are bounded, and the triangle inequality holds pointwise and then for the supremum. Two functions are within $\varepsilon$ in this metric exactly when the graph of one lies in a band of height $\varepsilon$ around the graph of the other, everywhere. Convergence in $d_\infty$ is uniform convergence, the subject of 2B.5 Uniform Convergence and Arzelà–Ascoli. On a compact interval, every continuous function is bounded (2A.9 Continuous Functions), so $C([a, b])$, the continuous functions on $[a, b]$, is a metric space with $d_\infty$.

On $C([a, b])$ there is another natural metric, the area between the graphs:

The triangle inequality comes from $|f - h| \leq |f - g| + |g - h|$ and monotonicity of the integral (2A.11 The Riemann Integral). Positivity is the interesting axiom: if $f \neq g$, then $|f - g|$ is positive at some point, hence (by continuity) at least some $\delta > 0$ on a small interval around it, so the integral is positive. For merely integrable functions this fails. A function that is $1$ at one point and $0$ elsewhere has integral $0$. Course 3 deals with this by agreeing to identify functions that differ on a negligible set (3A.3 The Lebesgue Integral).

1.3Open and closed sets

From here on, $(X, d)$ is a metric space. The definitions are those of 2A.9 Continuous Functions for the real line, with $|x - y|$ replaced by $d(x, y)$.

Balls depend on the metric. In $\mathbb{R}^2$ they are diamonds, discs or squares (Figure 1.1). In $C([a, b])$ with $d_\infty$, the ball of radius $\varepsilon$ around $f$ is the set of continuous functions whose graphs stay inside the band of half-width $\varepsilon$ around the graph of $f$, with some room to spare (the supremum of $|g - f|$ is attained on $[a, b]$, so it must be strictly less than $\varepsilon$). In the discrete metric, the ball of radius $\tfrac12$ around $x$ is just $\{x\}$.

Open balls are open. If $x \in B(x_0, r)$, let $s = r - d(x, x_0) > 0$. Then $B(x, s) \subseteq B(x_0, r)$ by the triangle inequality: $d(y, x_0) \leq d(y, x) + d(x, x_0) < s + d(x, x_0) = r$. So every point of an open ball is an interior point. In the same way, closed balls are closed (Exercise 1.17).

Sets need not be either open or closed: $[0, 1)$ in $\mathbb{R}$ is neither. And a set can be both: $X$ and $\varnothing$ always are, and in the discrete metric every set is both, since every ball of radius $\tfrac12$ is a single point.

The most-used fact connects closedness to sequences. It is what lets us prove a set is closed by taking limits.

1.4Subspaces and relative topology

Any subset $Y \subseteq X$ is a metric space with the same distance, restricted to pairs of points of $Y$. This is how the sphere $S^2$ inherits the straight-line (chordal) distance from $\mathbb{R}^3$, and how $[0, 1]$ inherits its metric from $\mathbb{R}$.

Being open is then a statement relative to the space you are in. In $Y = [0, 1]$, the set $[0, \tfrac12)$ is open: the ball of radius $\tfrac12$ around $0$ in $Y$ is $\{y \in [0, 1] : |y| < \tfrac12\} = [0, \tfrac12)$. But $[0, \tfrac12)$ is not open in $\mathbb{R}$, because no interval around $0$ fits inside it.

Relative topology will matter as soon as we work on a manifold, which lives inside some larger space but is studied as a space in its own right (8A.1 Smooth Structures).

1.5Equivalent and inequivalent metrics

The three metrics on $\mathbb{R}^n$ give different numbers but, it turns out, the same convergent sequences and the same open sets. The reason is that each is bounded by a constant multiple of each other:

(The first two inequalities compare a largest term, a root-sum-of-squares and a sum of non-negative terms; the last bounds each of $n$ terms by the largest.)

Uniformly equivalent metrics are equivalent: $d(x_n, x) \to 0$ if and only if $d'(x_n, x) \to 0$. By Proposition 1.9, equivalent metrics have the same closed sets, hence the same open sets. So on $\mathbb{R}^n$, one can use whichever of the three is convenient for the problem at hand: $\ell^\infty$ to handle coordinates one at a time, $\ell^2$ for geometry, $\ell^1$ for counting.

In infinite-dimensional spaces, this freedom disappears.

Which metric is right depends on the question. For a sensor that must never exceed a threshold, the worst case matters, and the sup metric is the right one. For the total energy delivered by a signal, the area metric (or its square-integral cousin) is the right one. 2B.5 Uniform Convergence and Arzelà–Ascoli develops the sup metric, and Courses 3 and 4 develop the integral metrics. A whole family of them, one for each exponent $p$, will be needed (3A.7 Lᵖ Spaces and Jensen’s Inequality), and the inequalities that relate them, the Sobolev inequalities of 4A.10 Sobolev Embeddings and Critical Exponents, are among the main tools of geometric analysis.

1.6History

The idea of an abstract distance came from analysis, not geometry. Maurice Fréchet's 1906 thesis studied sets of functions and curves on which only a notion of distance was given, and showed that much of the theory of limits carried over to them. Felix Hausdorff named and systematised these "metric spaces" in his Grundzüge der Mengenlehre (1914), the founding text of general topology. The examples that drove both were spaces of functions, exactly the spaces that differential equations need. Hamming distance came from engineering: Richard Hamming introduced it in his 1950 paper on error-detecting and error-correcting codes, written at Bell Labs for computers that had to keep running despite occasional single-bit errors.

1.7Exercises

Hint

For (b) and (d), use that $\phi(t) = t^{1/2}$ and $\phi(t) = \frac{t}{1 + t}$ are increasing with $\phi(s + t) \leq \phi(s) + \phi(t)$ for $s, t \geq 0$.

Solution

(a) Not a metric: $d(0, 2) = 4 > 2 = d(0, 1) + d(1, 2)$, so the triangle inequality fails. (b) A metric: $|x - z|^{1/2} \leq (|x - y| + |y - z|)^{1/2} \leq |x - y|^{1/2} + |y - z|^{1/2}$, squaring the last inequality to check it. (c) Not a metric: $d(1, -1) = 0$ although $1 \neq -1$, so positivity fails. (d) A metric, by the hint. It is bounded by $1$ but has the same convergent sequences as $|x - y|$: so every metric is equivalent to a bounded one.

Solution

With $a = |x_1 - y_1|$ and $b = |x_2 - y_2|$: $(a + b)^2 = a^2 + b^2 + 2ab \geq a^2 + b^2$ gives the left inequality, and $(a + b)^2 \leq 2(a^2 + b^2)$, which is $(a - b)^2 \geq 0$, gives the right one, with equality when $a = b$. In $\mathbb{R}^n$, $d_{\ell^2} \leq d_{\ell^1} \leq \sqrt n\, d_{\ell^2}$, the right one by Cauchy–Schwarz applied to $(1, \dots, 1)$ and $(|x_i - y_i|)_i$.

Solution

$x \cdot z = \cos\alpha\cos\beta + \sin\alpha\sin\beta\,(u \cdot v) \geq \cos\alpha\cos\beta - \sin\alpha\sin\beta = \cos(\alpha + \beta)$, using $u \cdot v \geq -1$ (Cauchy–Schwarz) and $\sin\alpha, \sin\beta \geq 0$. If $\alpha + \beta \leq \pi$, then since $\arccos$ is decreasing on $[-1, 1]$, $\arccos(x \cdot z) \leq \arccos(\cos(\alpha + \beta)) = \alpha + \beta$. If $\alpha + \beta > \pi$, then $\arccos(x \cdot z) \leq \pi < \alpha + \beta$ anyway.

Solution

(a) If $d(x_n, x_0) \leq r$ and $x_n \to x$, then $|d(x_n, x_0) - d(x, x_0)| \leq d(x_n, x) \to 0$, so $d(x, x_0) = \lim d(x_n, x_0) \leq r$. (b) $B(x_0, 1) = \{x_0\}$, which is closed, so its closure is $\{x_0\}$. The closed ball of radius $1$ is the whole space.

Solution

A closed ball of radius $t$ in $\{0,1\}^n$ contains $\sum_{k=0}^t \binom nk$ strings (choose which $k$ positions to flip). The balls around distinct codewords are disjoint and all lie in a set of $2^n$ strings. For $n = 7$, $t = 1$: $2^7/(1 + 7) = 16 = 2^4$.

Solution

(a) $\int_a^b |f - g| \leq \int_a^b d_\infty(f, g) = (b - a)\,d_\infty(f, g)$. (b) The zero function is in the set. Every $d_1$-ball around $0$, of radius $r$, contains $2f_n$ for $n > 2/r$, since $d_1(2f_n, 0) = \tfrac2n$; but $d_\infty(2f_n, 0) = 2$, so $2f_n$ is not in the set. Hence $0$ is not a $d_1$-interior point.

Solution

(a) Every point of the disc is within $1$ of the circle, and the centre is exactly $1$ away, so $d_{\mathcal{H}} = 1$. For the grid, every point of $[0, 1]$ is within $\tfrac1{2n}$ of a grid point, and the midpoint of a gap is exactly that far, so $d_{\mathcal{H}} = \tfrac1{2n}$. (b) If $A \subseteq B_r$ and $B \subseteq C_s$, then $A \subseteq C_{r+s}$ by the triangle inequality in $\mathbb{R}^n$; similarly in the other direction. (c) By (a), the grids converge to $[0, 1]$.