Contents / Real Analysis / Metric Spaces & Topology

Chapter 7

Metric Spaces & Topology

Metrics, balls and the topology they generate; open and closed sets, closure, interior and boundary; compactness by open covers, Heine-Borel in R^n, and its equivalence with sequential compactness; completeness, Banach spaces and the completion construction; connectedness and path-connectedness with the topologist's sine curve; the Banach fixed point theorem with convergence rates and Picard-Lindelof; and the Baire category theorem with its generic consequences.

Introduction

Everything proved about $R$ so far leans on one thing: the absolute value $∣ x - y ∣$ , and the three facts that it is zero only when $x = y$ , that it is symmetric, and that it obeys $∣ x - z ∣ \leq ∣ x - y ∣ + ∣ y - z ∣$ . Nothing in the arguments for convergence, for continuity, for the Bolzano–Weierstrass theorem ever used that $x$ and $y$ were numbers. They used that there was a notion of how far apart two points are, and that going via a third point never shortens the trip.

This chapter takes that observation seriously. A metric space is a set together with a distance function obeying those three axioms and nothing else. The payoff is not generality for its own sake. It is that one proof, written once, then applies to the plane, to sequences, to the space of continuous functions on $[0, 1]$ , to a graph with its shortest-path distance, and to a set of DNA strings with the Hamming distance — and that in the process we find out which of our familiar theorems were really theorems about distance and which were secretly theorems about $R$ .

The chapter has six movements. First the definition itself, together with the vocabulary — balls, convergence, continuity, Cauchy sequences — transplanted from $R$ with the absolute value replaced by $d$ . Then topology: open sets, closed sets, closure and interior, which package that vocabulary into statements that never mention $ε$ at all. Then compactness, where the abstraction pays its first large dividend: in $R^{n}$ the Heine–Borel theorem says compact means closed and bounded, in a general metric space that is false, and what survives is the equivalence of open-cover compactness with sequential compactness. Then completeness, the property $Q$ lacks and $R$ has, and the normed spaces built on it. Then connectedness, which makes precise the idea that an interval is all one piece. Finally two theorems that are the reason the whole apparatus was built: the Banach fixed point theorem, which turns "solve this equation" into "iterate this map", and the Baire category theorem, which says a complete space cannot be assembled from countably many thin pieces, and from which existence proofs for objects nobody can write down fall out almost for free.

Notation throughout: $(X, d)$ is a metric space, $B (x, r)$ the open ball of radius $r$ about $x$ , and $x_{n} \to x$ means $d (x_{n}, x) \to 0$ in $R$ . Results about $R$ itself — the completeness axiom, the Bolzano–Weierstrass theorem, the Monotone convergence theorem — are taken from Sequences and Series of Real Numbers and used without reproof.

7.1Metrics: the axioms and what they already force

Definition 7.1 (Metric space). A metric on a set $X$ is a function $d : X \times X \to R$ such that for all $x, y, z \in X$ :

(Positivity) $d (x, y) \geq 0$ , with $d (x, y) = 0$ if and only if $x = y$ ;
(Symmetry) $d (x, y) = d (y, x)$ ;
(Triangle inequality) $d (x, z) \leq d (x, y) + d (y, z)$ .

The pair $(X, d)$ is a metric space, and the elements of $X$ are called points.

Three axioms is a short list, and it is worth noticing what is not on it. There is no requirement that $X$ carry addition, or scalar multiplication, or an order. There is no requirement that distances be small, or that $X$ be infinite. A one-point set is a metric space. The axioms are also not independent of one another in the loose sense: non-negativity is redundant, and the following proposition shows why — it is already hiding inside the other two.

Proposition 7.2 (Non-negativity is forced). Suppose $d : X \times X \to R$ satisfies $d (x, y) = 0 ⟺ x = y$ , symmetry, and the triangle inequality. Then $d (x, y) \geq 0$ automatically.

Proof. Fix $x, y \in X$ and apply the triangle inequality with the middle point $y$ and endpoints $x$ and $x$ :

d (x, x) \leq d (x, y) + d (y, x) .

The left side is $0$ because $x = x$ , and the right side is $2 d (x, y)$ by symmetry. Hence $0 \leq 2 d (x, y)$ , so $d (x, y) \geq 0$ .∎

A second consequence of the axioms is used constantly and deserves a name. The triangle inequality bounds a distance from above; the reverse triangle inequality bounds the change in a distance from below, and it is what makes $d$ itself a continuous function.

Proposition 7.3 (Reverse triangle inequality). For all $x, y, z$ in a metric space,

d (x, z) - d (y, z) \leq d (x, y) .

Proof. By the triangle inequality routed through $y$ , $d (x, z) \leq d (x, y) + d (y, z)$ , so

d (x, z) - d (y, z) \leq d (x, y) .

Now swap the roles of $x$ and $y$ : $d (y, z) \leq d (y, x) + d (x, z)$ , so $d (y, z) - d (x, z) \leq d (y, x) = d (x, y)$ by symmetry. The two displayed inequalities say that $d (x, z) - d (y, z)$ and its negative are both at most $d (x, y)$ , which is exactly the assertion that its absolute value is at most $d (x, y)$ .∎

Read the statement as a Lipschitz estimate: moving the point $x$ by at most $δ$ changes its distance to any fixed $z$ by at most $δ$ . Distance is never more sensitive than the motion that causes it. This single inequality will do the work in half a dozen proofs below, so it is worth having in the hand rather than rederiving each time.

Now the examples, which are the real content of the definition — a definition with two examples is a definition nobody trusts.

Example 7.4 (The standard metrics on $R^{n}$ ). Verify that $d_{2} (x, y) = (\sum_{i = 1}^{n} (x_{i} - y_{i})^{2})^{1/2}$ , $d_{1} (x, y) = \sum_{i = 1}^{n} ∣ x_{i} - y_{i} ∣$ and $d_{\infty} (x, y) = max_{1 \leq i \leq n} ∣ x_{i} - y_{i} ∣$ are all metrics on $R^{n}$ , and compute all three distances from $(1, 2)$ to $(4, 6)$ .

Solution.

Positivity and symmetry are immediate for all three: each is built from the quantities $∣ x_{i} - y_{i} ∣$ , which are non-negative and symmetric, and each vanishes exactly when every coordinate difference vanishes, that is when $x = y$ .
The triangle inequality for $d_{1}$ is coordinatewise: $∣ x_{i} - z_{i} ∣ \leq ∣ x_{i} - y_{i} ∣ + ∣ y_{i} - z_{i} ∣$ in $R$ , and summing over $i$ preserves the inequality.
For $d_{\infty}$ , fix the index $k$ achieving the maximum on the left. Then $∣ x_{k} - z_{k} ∣ \leq ∣ x_{k} - y_{k} ∣ + ∣ y_{k} - z_{k} ∣ \leq d_{\infty} (x, y) + d_{\infty} (y, z)$ , since each term is at most its own maximum.
For $d_{2}$ the coordinatewise argument fails and the Minkowski inequality of Normed and Inner Product Spaces is needed; it gives $∥ u + v ∥_{2} \leq ∥ u ∥_{2} + ∥ v ∥_{2}$ , and applying it to $u = x - y$ , $v = y - z$ gives the claim.
Numerically, with differences $(3, 4)$ : $d_{2} = 9 + 16 = 5$ , $d_{1} = 3 + 4 = 7$ , $d_{\infty} = max (3, 4) = 4$ .
The ordering $d_{\infty} \leq d_{2} \leq d_{1}$ seen here is general in $R^{n}$ , and it is the first hint that these three metrics, while numerically different, may be interchangeable for topological purposes. The section Equivalent metrics and the discrete metric makes that precise.

□

Example 7.5 (Metrics that are not about arrows in space). Show that each of the following is a metric: (a) the discrete metric $d (x, y) = 1$ for $x \neq = y$ and $0$ otherwise, on any set $X$ ; (b) the Hamming distance between binary strings of length $n$ , counting positions where they differ; (c) the sup metric $d_{\infty} (f, g) = sup_{t \in [0, 1]} ∣ f (t) - g (t) ∣$ on $C [0, 1]$ , the continuous real functions on $[0, 1]$ .

Solution.

(a) Positivity and symmetry are visible. For the triangle inequality, note the right side $d (x, y) + d (y, z)$ is $0$ only when $x = y$ and $y = z$ , hence when $x = z$ , in which case the left side is $0$ too. In every other case the right side is at least $1$ and the left side is at most $1$ .
(b) Hamming distance is $d_{1}$ restricted to ${0, 1}^{n}$ , since $∣ x_{i} - y_{i} ∣$ is $1$ exactly at a mismatching position. It inherits the axioms.
(c) The supremum is finite because a continuous function on a closed bounded interval is bounded, by the Extreme value theorem. It is zero exactly when $f = g$ pointwise. For the triangle inequality, fix $t$ : $∣ f (t) - h (t) ∣ \leq ∣ f (t) - g (t) ∣ + ∣ g (t) - h (t) ∣ \leq d_{\infty} (f, g) + d_{\infty} (g, h)$ , and taking the supremum over $t$ on the left preserves the bound because the right side does not depend on $t$ .
The point of (c) is that a function is now a single point of a metric space, and two functions are close when their graphs are uniformly close. Sequences of functions become sequences of points, and uniform convergence becomes convergence in a metric — which is what makes the whole theory of this chapter available to analysis of functions.

□

Remark. Dropping an axiom gives a named weaker object rather than nonsense. Allowing $d (x, y) = 0$ for distinct points gives a pseudometric (useful when you intend to identify points at distance zero). Dropping symmetry gives a quasimetric, of which "driving time between two addresses in a city with one-way streets" is the honest everyday example. Allowing $d = \infty$ gives an extended metric. All are studied; none is what "metric" means here.

Exercises for §7.1 →

7.2Balls, and the topology they generate

Once distances exist, the basic geometric object is the set of points within a given distance of a centre. Everything topological in this chapter is ultimately phrased in terms of these sets.

Definition 7.6 (Open and closed balls, spheres). For $x \in X$ and $r > 0$ , the open ball, closed ball and sphere of radius $r$ about $x$ are

B (x, r) = {y \in X : d (x, y) < r}, \overset{ˉ}{B} (x, r) = {y : d (x, y) \leq r}, S (x, r) = {y : d (x, y) = r} .

The word "ball" is a picture drawn from $R^{3}$ with the Euclidean metric, and the picture misleads more often than it helps. In $R^{2}$ with $d_{1}$ the unit ball is a diamond; with $d_{\infty}$ it is a square; in the discrete metric $B (x, 1) = {x}$ is a single point while $B (x, 2) = X$ is everything, so a ball can have empty interior in the naive sense or be the whole space, and there is nothing in between. In a subspace of $R$ such as $X = [0, 1]$ , the ball $B (0, \frac{1}{2})$ is the half-open interval $[0, \frac{1}{2})$ , which has an "edge" at $0$ only because the rest of $R$ is not there. Balls are defined by an inequality, not by a shape.

Figure 7.7. The unit ball

{y : d (0, y) \leq 1}

R^{2}

under three metrics: the taxicab diamond

d_{1}

, the Euclidean disc

d_{2}

, and the sup-metric square

d_{\infty}

. Each contains the previous, matching

d_{\infty} \leq d_{2} \leq d_{1}

Theorem 7.8 (Open balls are open). Let $(X, d)$ be a metric space, $x \in X$ and $r > 0$ . For every $y \in B (x, r)$ there is $ρ > 0$ with $B (y, ρ) \subseteq B (x, r)$ .

Proof. Let $y \in B (x, r)$ , so $d (x, y) < r$ , and set $ρ = r - d (x, y) > 0$ . Let $z \in B (y, ρ)$ , so $d (y, z) < ρ$ . By the triangle inequality,

d (x, z) \leq d (x, y) + d (y, z) < d (x, y) + (r - d (x, y)) = r,

so $z \in B (x, r)$ . As $z$ was arbitrary, $B (y, ρ) \subseteq B (x, r)$ .∎

This is the single most-used computation in the chapter, and it deserves to be understood rather than memorised: the radius you are allowed to use at $y$ is exactly the distance from $y$ to the edge, $r - d (x, y)$ , and the triangle inequality is what converts " $y$ is not at the edge" into "a whole ball around $y$ is inside".

Figure 7.9. Why an open ball is open: from

y

at distance

d (x, y)

from the centre, the ball of radius

ρ = r - d (x, y)

stays inside

B (x, r)

, since any

z

in it has

d (x, z) \leq d (x, y) + d (y, z) < r

Definition 7.10 (The metric topology). A set $U \subseteq X$ is open if for every $x \in U$ there exists $r > 0$ with $B (x, r) \subseteq U$ . The collection of all open sets is the topology induced by $d$ , written $τ_{d}$ .

With this language the theorem Open balls are open says precisely that every open ball belongs to $τ_{d}$ — which is why the name is not a tautology. The open sets are exactly the sets that are unions of open balls, and that reformulation is worth recording.

Proposition 7.11 (Open sets are unions of balls). $U \subseteq X$ is open if and only if $U$ is a union of open balls.

Proof. ( $\Rightarrow$ ) If $U$ is open, choose for each $x \in U$ a radius $r_{x} > 0$ with $B (x, r_{x}) \subseteq U$ . Then $⋃_{x \in U} B (x, r_{x}) \subseteq U$ , and the reverse inclusion holds because each $x$ lies in its own ball $B (x, r_{x})$ . So $U$ is that union.

( $\Leftarrow$ ) Suppose $U = ⋃_{α} B (x_{α}, r_{α})$ and let $x \in U$ . Then $x \in B (x_{α}, r_{α})$ for some $α$ , and by the theorem Open balls are open there is $ρ > 0$ with $B (x, ρ) \subseteq B (x_{α}, r_{α}) \subseteq U$ .∎

Pitfall. The closure of $B (x, r)$ need not equal $\overset{ˉ}{B} (x, r)$ . In the discrete metric on a set with at least two points, $B (x, 1) = {x}$ is already closed, so its closure is ${x}$ , while $\overset{ˉ}{B} (x, 1) = X$ . In $R^{n}$ with the Euclidean metric the two do coincide, which is exactly why the false statement survives so long unchallenged.

Exercises for §7.2 →

7.3Convergence, continuity and Cauchy sequences

Every definition in this section is the corresponding definition from $R$ with $∣ x - y ∣$ replaced by $d (x, y)$ . That is the whole idea, and the interest lies in which theorems survive the translation and which do not.

Definition 7.12 (Convergence in a metric space). A sequence $(x_{n})$ in $X$ converges to $x \in X$ if for every $ε > 0$ there is $N$ with $d (x_{n}, x) < ε$ for all $n \geq N$ ; equivalently, if the real sequence $d (x_{n}, x)$ converges to $0$ . We write $x_{n} \to x$ .

Proposition 7.13 (Limits are unique). A sequence in a metric space has at most one limit.

Proof. Suppose $x_{n} \to x$ and $x_{n} \to y$ . For any $ε > 0$ choose $N$ beyond which both $d (x_{n}, x) < ε /2$ and $d (x_{n}, y) < ε /2$ . Then for such $n$ ,

d (x, y) \leq d (x, x_{n}) + d (x_{n}, y) < ε .

So the non-negative number $d (x, y)$ is smaller than every positive $ε$ , forcing $d (x, y) = 0$ and hence $x = y$ by positivity.∎

Uniqueness of limits is exactly where the axiom " $d (x, y) = 0 \Rightarrow x = y$ " is spent. In a pseudometric space, where that implication is dropped, limits are unique only up to distance zero — which is the technical reason pseudometric spaces are usually quotiented before use.

Definition 7.14 (Continuity at a point). Let $(X, d_{X})$ and $(Y, d_{Y})$ be metric spaces. A map $f : X \to Y$ is continuous at $x_{0}$ if for every $ε > 0$ there is $δ > 0$ such that

d_{X} (x, x_{0}) < δ ⟹ d_{Y} (f (x), f (x_{0})) < ε .

It is continuous if it is continuous at every point, and uniformly continuous if $δ$ may be chosen depending on $ε$ alone.

Theorem 7.15 (Sequential characterisation of continuity). $f : X \to Y$ is continuous at $x_{0}$ if and only if $f (x_{n}) \to f (x_{0})$ in $Y$ for every sequence $x_{n} \to x_{0}$ in $X$ .

Proof. ( $\Rightarrow$ ) Suppose $f$ is continuous at $x_{0}$ and $x_{n} \to x_{0}$ . Given $ε > 0$ , pick $δ > 0$ from continuity, then $N$ with $d_{X} (x_{n}, x_{0}) < δ$ for $n \geq N$ . For those $n$ , $d_{Y} (f (x_{n}), f (x_{0})) < ε$ . Hence $f (x_{n}) \to f (x_{0})$ .

( $\Leftarrow$ ) We prove the contrapositive. If $f$ is not continuous at $x_{0}$ , there is some $ε_{0} > 0$ for which no $δ$ works. In particular $δ = 1/ n$ fails for each $n \in N$ , so there is a point $x_{n}$ with

d_{X} (x_{n}, x_{0}) < \frac{1}{n} and d_{Y} (f (x_{n}), f (x_{0})) \geq ε_{0} .

The first condition gives $x_{n} \to x_{0}$ ; the second says $f (x_{n}) \neq \to f (x_{0})$ . So the sequential condition fails as well.∎

The backward direction is the one that carries content, and its engine is the freedom to choose a countable sequence of candidate $δ$ 's, namely $1/ n$ . That is available because the metric takes real values; in a general topological space it is not, and the sequential characterisation of continuity genuinely fails there. Metric spaces are, in the standard terminology, first countable, and this proof is what that buys.

Definition 7.16 (Cauchy sequence). A sequence $(x_{n})$ in $X$ is Cauchy if for every $ε > 0$ there is $N$ such that $d (x_{m}, x_{n}) < ε$ for all $m, n \geq N$ .

Proposition 7.17 (Convergent implies Cauchy, and Cauchy implies bounded). Every convergent sequence is Cauchy, and every Cauchy sequence is bounded — that is, contained in some ball.

Proof. If $x_{n} \to x$ , given $ε > 0$ choose $N$ with $d (x_{n}, x) < ε /2$ for $n \geq N$ . For $m, n \geq N$ , $d (x_{m}, x_{n}) \leq d (x_{m}, x) + d (x, x_{n}) < ε$ .

For boundedness, take $ε = 1$ in the Cauchy condition and get $N$ with $d (x_{n}, x_{N}) < 1$ for all $n \geq N$ . Put $R = 1 + max {d (x_{1}, x_{N}), \dots, d (x_{N - 1}, x_{N})}$ , a maximum over finitely many numbers. Then $d (x_{n}, x_{N}) < R$ for every $n$ , so the whole sequence lies in $B (x_{N}, R)$ .∎

The converse of the first statement is false in general, and its failure is the subject of the completeness sections below: in $X = Q$ the decimal truncations of $2$ form a Cauchy sequence with no limit in $X$ . Notice what the difference is. Convergence mentions a limit point and so can fail because the space is missing that point; the Cauchy condition mentions only the sequence's own terms and so cannot detect the absence.

Example 7.18 (A continuous map and a sequence, in the sup metric). In $C [0, 1]$ with the sup metric let $f_{n} (t) = t^{n}$ and let $Φ : C [0, 1] \to R$ be $Φ (f) = \int_{0}^{1} f$ . Show $Φ$ is continuous, decide whether $(f_{n})$ converges in this metric, and compute $Φ (f_{n})$ .

Solution.

For $f, g \in C [0, 1]$ , $∣Φ (f) - Φ (g) ∣ = \int_{0}^{1} (f - g) \leq \int_{0}^{1} ∣ f - g ∣ \leq d_{\infty} (f, g)$ , since the integrand is bounded by the sup at every point and the interval has length $1$ .
So $δ = ε$ works for every $ε$ and every $f$ : $Φ$ is not merely continuous but uniformly continuous, indeed Lipschitz with constant $1$ .
Pointwise, $f_{n} (t) \to 0$ for $t < 1$ and $f_{n} (1) = 1$ , so the pointwise limit is discontinuous and cannot be the sup-metric limit, since that limit would have to be an element of $C [0, 1]$ and would have to agree with the pointwise limit.
Directly: $d_{\infty} (f_{n}, 0) = sup_{t \in [0, 1]} t^{n} = 1$ for every $n$ , so $(f_{n})$ does not converge to $0$ ; and $d_{\infty} (f_{n}, f_{m}) \geq ∣ f_{n} (t) - f_{m} (t) ∣$ at $t = (1/2)^{1/ n}$ shows the sequence is not Cauchy either. It converges to nothing.
Finally $Φ (f_{n}) = \int_{0}^{1} t^{n} d t = \frac{1}{n + 1}$ , which does tend to $0$ . Continuity of $Φ$ is not contradicted: $Φ$ carries convergent sequences to convergent ones, and says nothing about a sequence that fails to converge.

□

Exercises for §7.3 →

7.4Equivalent metrics and the discrete metric

Two different metrics on the same set may generate the same open sets, in which case every topological statement — convergence, continuity, compactness, connectedness — holds for one exactly when it holds for the other, even though the numerical distances differ.

Definition 7.19 (Topologically and strongly equivalent metrics). Metrics $d$ and $d^{'}$ on $X$ are topologically equivalent if $τ_{d} = τ_{d^{'}}$ . They are strongly (or Lipschitz) equivalent if there are constants $0 < c \leq C$ with

c d (x, y) \leq d^{'} (x, y) \leq C d (x, y) for all x, y \in X .

Proposition 7.20 (Strong equivalence implies topological equivalence). If $c d \leq d^{'} \leq C d$ with $c, C > 0$ , then $d$ and $d^{'}$ induce the same topology; the converse fails.

Proof. Let $U \in τ_{d}$ and $x \in U$ , so $B_{d} (x, r) \subseteq U$ for some $r > 0$ . If $d^{'} (x, y) < cr$ then $d (x, y) \leq d^{'} (x, y) / c < r$ , so $B_{d^{'}} (x, cr) \subseteq B_{d} (x, r) \subseteq U$ and $U \in τ_{d^{'}}$ . Symmetrically, if $d (x, y) < r / C$ then $d^{'} (x, y) \leq C d (x, y) < r$ , giving $B_{d} (x, r / C) \subseteq B_{d^{'}} (x, r)$ , so $τ_{d^{'}} \subseteq τ_{d}$ .

For the failure of the converse take $X = R$ , $d (x, y) = ∣ x - y ∣$ and $d^{'} (x, y) = min {∣ x - y ∣, 1}$ . Since $d^{'} = d$ whenever $d < 1$ , every $d$ -ball of radius under $1$ is a $d^{'}$ -ball and conversely, so the topologies agree; but $d^{'}$ is bounded by $1$ while $d$ is not, so no constant $C$ can satisfy $d \leq C^{- 1} d^{'}$ globally.∎

Corollary 7.21 (All $p$ -metrics on $R^{n}$ agree topologically). On $R^{n}$ the metrics $d_{1}$ , $d_{2}$ and $d_{\infty}$ are strongly equivalent, hence induce the same open sets, the same convergent sequences and the same continuous functions.

Proof. For any $u \in R^{n}$ , each $∣ u_{i} ∣$ is at most $max_{j} ∣ u_{j} ∣$ and at least nothing, so summing gives $∥ u ∥_{1} \leq n ∥ u ∥_{\infty}$ . Also $∥ u ∥_{\infty}^{2} \leq \sum u_{i}^{2} = ∥ u ∥_{2}^{2}$ , so $∥ u ∥_{\infty} \leq ∥ u ∥_{2}$ ; and $∥ u ∥_{2}^{2} = \sum u_{i}^{2} \leq (\sum ∣ u_{i} ∣)^{2} = ∥ u ∥_{1}^{2}$ since the cross terms are non-negative, so $∥ u ∥_{2} \leq ∥ u ∥_{1}$ . Chaining,

∥ u ∥_{\infty} \leq ∥ u ∥_{2} \leq ∥ u ∥_{1} \leq n ∥ u ∥_{\infty} .

Applying this to $u = x - y$ gives strong equivalence of each pair with constants depending only on $n$ , and the theorem Strong equivalence implies topological equivalence finishes.∎

The discrete metric is the standard source of counterexamples in this chapter, because it makes everything open and thereby breaks every theorem whose proof secretly used that balls shrink.

Proposition 7.22 (The discrete metric, catalogued). Let $X$ carry the discrete metric $d$ . Then every subset of $X$ is both open and closed; a sequence converges if and only if it is eventually constant; every map out of $X$ into any metric space is continuous; $(X, d)$ is complete; and $(X, d)$ is compact if and only if $X$ is finite.

Proof. For any $x$ , $B (x, \frac{1}{2}) = {x}$ , so every singleton is open and hence every set, as a union of singletons, is open; complements of open sets are then also open, so every set is closed too.

If $x_{n} \to x$ then eventually $d (x_{n}, x) < \frac{1}{2}$ , which in this metric forces $d (x_{n}, x) = 0$ , i.e. $x_{n} = x$ ; the converse is clear. Continuity of any $f$ follows from the theorem Sequential characterisation of continuity, since an eventually constant sequence has eventually constant image.

A Cauchy sequence satisfies $d (x_{m}, x_{n}) < \frac{1}{2}$ for large $m, n$ , hence is eventually constant, hence converges; so $X$ is complete. Finally ${{x} : x \in X}$ is an open cover with no proper subcover, so a finite subcover exists exactly when $X$ itself is finite; and a finite metric space is compact because any cover of it has a finite subcover trivially.∎

Example 7.23 (Bounded and closed but not compact). In an infinite set $X$ with the discrete metric, show that $X$ is closed and bounded but not compact, and reconcile this with the Heine–Borel theorem.

Solution.

$X$ is closed in itself, always and in any space, since its complement $\emptyset$ is open.
$X$ is bounded: $X = B (x_{0}, 2)$ for any chosen $x_{0}$ , because every distance is at most $1 < 2$ .
$X$ is not compact by the proposition The discrete metric, catalogued, since $X$ is infinite.
There is no contradiction, because the Heine–Borel theorem is a statement about $R^{n}$ with the Euclidean metric and not about metric spaces in general. Its proof will use the completeness of $R$ and the fact that a bounded set in $R^{n}$ sits inside a box that can be bisected — neither available here. "Closed and bounded implies compact" is a theorem about $R^{n}$ , not a definition of compactness, and this example is the standard reminder.

□

Exercises for §7.4 →

7.5Open sets: the three axioms they satisfy

The definition The metric topology declared which sets are open. The next theorem says that the family of open sets is closed under exactly two operations, and it is the whole reason the word "topology" exists: one may forget $d$ entirely and keep only this family.

Theorem 7.24 (The open sets form a topology). In a metric space $(X, d)$ :

$\emptyset$ and $X$ are open;
an arbitrary union of open sets is open;
the intersection of finitely many open sets is open.

Proof. (1) The condition on $\emptyset$ is vacuous — there is no point at which to check it. For $X$ , any radius works, since every ball is contained in $X$ .

(2) Let $U = ⋃_{α \in A} U_{α}$ with each $U_{α}$ open, and let $x \in U$ . Then $x \in U_{α_{0}}$ for some $α_{0}$ , so there is $r > 0$ with $B (x, r) \subseteq U_{α_{0}} \subseteq U$ .

(3) Let $U = U_{1} \cap \dots \cap U_{n}$ with each $U_{i}$ open and let $x \in U$ . For each $i$ pick $r_{i} > 0$ with $B (x, r_{i}) \subseteq U_{i}$ , and set $r = min {r_{1}, \dots, r_{n}}$ . This is a minimum of finitely many positive numbers, hence positive, and $B (x, r) \subseteq B (x, r_{i}) \subseteq U_{i}$ for every $i$ , so $B (x, r) \subseteq U$ .∎

The word "finitely" in (3) is not a limitation of the proof; it is a fact about the world. An infinite family supplies infinitely many radii, whose infimum can be $0$ , and then no ball survives.

Example 7.25 (An infinite intersection of open sets that is not open). In $R$ compute $⋂_{n = 1}^{\infty} (- \frac{1}{n}, \frac{1}{n})$ and $⋂_{n = 1}^{\infty} (0, 1 + \frac{1}{n})$ , and say which are open.

Solution.

A real $x$ lies in every $(- 1/ n, 1/ n)$ precisely when $∣ x ∣ < 1/ n$ for all $n$ , that is when $∣ x ∣ = 0$ , by the Archimedean property. So the first intersection is ${0}$ .
${0}$ is not open in $R$ : every ball $(- r, r)$ around $0$ contains $r /2 \neq = 0$ .
For the second, $x$ lies in every $(0, 1 + 1/ n)$ exactly when $0 < x$ and $x \leq 1$ , so the intersection is $(0, 1]$ , again not open — no ball about $1$ fits inside.
Both examples show the same mechanism: the sets shrink to a limit that includes its own boundary, and the minimum of the available radii degenerates to zero. The finiteness in the theorem The open sets form a topology is exactly what forbids that degeneration.

□

Remark. Openness is not intrinsic to a set; it is relative to the ambient space. The interval $[0, 1)$ is not open in $R$ , but it is open in the metric space $X = [0, 1]$ , where it equals $B (0, 1)$ . When two spaces are in play, say "open in $X$ " and mean it. This relative notion is the subspace topology: the open sets of $Y \subseteq X$ are exactly the sets $U \cap Y$ with $U$ open in $X$ .

Exercises for §7.5 →

7.6Closed sets and the sequential test

Definition 7.26 (Closed set). $F \subseteq X$ is closed if its complement $X ∖ F$ is open.

Theorem 7.27 (Sequential characterisation of closed sets). $F \subseteq X$ is closed if and only if the limit of every convergent sequence of points of $F$ lies in $F$ .

Proof. ( $\Rightarrow$ ) Let $F$ be closed, $x_{n} \in F$ with $x_{n} \to x$ , and suppose for contradiction $x \in / F$ . Then $x$ lies in the open set $X ∖ F$ , so $B (x, r) \subseteq X ∖ F$ for some $r > 0$ . But $d (x_{n}, x) < r$ for large $n$ , putting some $x_{n}$ in $X ∖ F$ — contradicting $x_{n} \in F$ .

( $\Leftarrow$ ) Suppose $F$ contains all its sequential limits and suppose $X ∖ F$ is not open. Then there is $x \in / F$ such that no ball about $x$ lies in $X ∖ F$ ; in particular for each $n$ the ball $B (x, 1/ n)$ meets $F$ , say at $x_{n}$ . Then $d (x_{n}, x) < 1/ n \to 0$ , so $x_{n} \to x$ with every $x_{n} \in F$ , and the hypothesis forces $x \in F$ — a contradiction. Hence $X ∖ F$ is open.∎

This is the workhorse criterion. To prove a set closed one almost never returns to complements; one takes a convergent sequence inside it and shows the limit stays. The proof of the backward direction again exploits the radii $1/ n$ , and again that is metric-specific.

Corollary 7.28 (Closed balls and spheres are closed). $\overset{ˉ}{B} (x, r)$ and $S (x, r)$ are closed in any metric space.

Proof. Let $y_{n} \in \overset{ˉ}{B} (x, r)$ with $y_{n} \to y$ . By the proposition Reverse triangle inequality, $∣ d (x, y_{n}) - d (x, y) ∣ \leq d (y_{n}, y) \to 0$ , so $d (x, y_{n}) \to d (x, y)$ . Each $d (x, y_{n}) \leq r$ , and a limit of a sequence of reals bounded by $r$ is bounded by $r$ , so $d (x, y) \leq r$ and $y \in \overset{ˉ}{B} (x, r)$ . Apply the theorem Sequential characterisation of closed sets. The same argument with $= r$ in place of $\leq r$ handles $S (x, r)$ .∎

Proposition 7.29 (De Morgan for closed sets). Arbitrary intersections and finite unions of closed sets are closed; $\emptyset$ and $X$ are closed.

Proof. Complement the theorem The open sets form a topology using De Morgan's laws: $X ∖ ⋂_{α} F_{α} = ⋃_{α} (X ∖ F_{α})$ is a union of open sets, hence open; and $X ∖ ⋃_{i = 1}^{n} F_{i} = ⋂_{i = 1}^{n} (X ∖ F_{i})$ is a finite intersection of open sets, hence open.∎

Pitfall. "Closed" is not "not open". In $R$ the set $[0, 1)$ is neither; the sets $\emptyset$ and $R$ are both; and in the discrete metric every set is both. A door is open or shut; a set is not a door.

Example 7.30 (An infinite union of closed sets that is not closed). Show $⋃_{n = 1}^{\infty} [\frac{1}{n}, 1] = (0, 1]$ in $R$ , and explain which hypothesis fails.

Solution.

Each $[1/ n, 1]$ is closed, and each is a subset of $(0, 1]$ , so the union is contained in $(0, 1]$ .
Conversely if $0 < x \leq 1$ then by the Archimedean property there is $n$ with $1/ n \leq x$ , so $x \in [1/ n, 1]$ .
The union is $(0, 1]$ , which is not closed: the sequence $1/ n$ lies in it and converges to $0 \in / (0, 1]$ .
The failing hypothesis is finiteness in the proposition De Morgan for closed sets: only finite unions of closed sets are guaranteed closed, mirroring the finite intersections of open sets exactly.

□

Exercises for §7.6 →

7.7Closure, interior and boundary

Given an arbitrary set, there is a largest open set inside it and a smallest closed set containing it. These two operations, and the difference between them, organise most of point-set topology.

Definition 7.31 (Interior, closure, boundary). For $A \subseteq X$ ,

A^{\circ} = ⋃ {U : U open, U \subseteq A}, \overset{ˉ}{A} = ⋂ {F : F closed, F \supseteq A},

and the boundary is $\partial A = \overset{ˉ}{A} ∖ A^{\circ}$ . By the theorem The open sets form a topology and the proposition De Morgan for closed sets, $A^{\circ}$ is open and $\overset{ˉ}{A}$ is closed; so $A^{\circ}$ is the largest open subset of $A$ and $\overset{ˉ}{A}$ the smallest closed superset.

Theorem 7.32 (Pointwise descriptions). For $A \subseteq X$ and $x \in X$ :

$x \in A^{\circ}$ if and only if $B (x, r) \subseteq A$ for some $r > 0$ ;
$x \in \overset{ˉ}{A}$ if and only if $B (x, r) \cap A \neq = \emptyset$ for every $r > 0$ ;
$x \in \overset{ˉ}{A}$ if and only if $x = lim a_{n}$ for some sequence $(a_{n})$ in $A$ ;
$x \in \partial A$ if and only if every ball about $x$ meets both $A$ and $X ∖ A$ .

Proof. (1) If $B (x, r) \subseteq A$ then $B (x, r)$ is an open subset of $A$ by the theorem Open balls are open, so it lies in the union defining $A^{\circ}$ and contains $x$ . Conversely if $x \in A^{\circ}$ then $x$ lies in some open $U \subseteq A$ , which supplies a ball.

(2) Suppose some ball $B (x, r)$ misses $A$ . Then $F = X ∖ B (x, r)$ is closed and contains $A$ , so $\overset{ˉ}{A} \subseteq F$ , and $x \in / F$ , hence $x \in / \overset{ˉ}{A}$ . Conversely suppose $x \in / \overset{ˉ}{A}$ . Then $x$ lies in the open set $X ∖ \overset{ˉ}{A}$ , which supplies a ball $B (x, r) \subseteq X ∖ \overset{ˉ}{A} \subseteq X ∖ A$ , missing $A$ .

(3) Given (2), if $x \in \overset{ˉ}{A}$ choose $a_{n} \in B (x, 1/ n) \cap A$ ; then $a_{n} \to x$ . Conversely if $a_{n} \to x$ with $a_{n} \in A$ , every ball about $x$ contains some $a_{n}$ , so (2) applies.

(4) $x \in \partial A$ means $x \in \overset{ˉ}{A}$ and $x \in / A^{\circ}$ . By (2) the first says every ball meets $A$ ; by (1) the second says no ball is contained in $A$ , i.e. every ball meets $X ∖ A$ .∎

Proposition 7.33 (Duality of interior and closure). For every $A \subseteq X$ , $\overline{X ∖ A} = X ∖ A^{\circ}$ and $(X ∖ A)^{\circ} = X ∖ \overset{ˉ}{A}$ .

Proof. By part (2) of the theorem Pointwise descriptions, $x \in \overline{X ∖ A}$ iff every ball about $x$ meets $X ∖ A$ , which by part (1) is exactly the failure of $x \in A^{\circ}$ . The second identity is the first applied to $X ∖ A$ in place of $A$ .∎

Example 7.34 (Closure, interior and boundary of $Q$ and of a disc). Compute $A^{\circ}$ , $\overset{ˉ}{A}$ and $\partial A$ for (a) $A = Q \subseteq R$ ; (b) $A = B (0, 1) \subseteq R^{2}$ Euclidean; (c) $A = {1/ n : n \in N} \subseteq R$ .

Solution.

(a) Every interval contains both rationals and irrationals, by density of each in $R$ . So every ball meets $Q$ , giving $\overset{ˉ}{Q} = R$ ; no ball lies inside $Q$ , giving $Q^{\circ} = \emptyset$ ; hence $\partial Q = R$ . A set can have empty interior and full closure — "thin" and "everywhere" are compatible.
(b) $A$ is open so $A^{\circ} = A$ . Its closure is the closed disc $\overset{ˉ}{B} (0, 1)$ : any $y$ with $∣ y ∣ = 1$ is the limit of $(1 - 1/ n) y \in A$ . So $\partial A$ is the unit circle, and $\partial A$ has empty interior.
(c) No ball lies in $A$ since $A$ is countable and balls are not, so $A^{\circ} = \emptyset$ . The only new limit point is $0$ , so $\overset{ˉ}{A} = A \cup {0}$ and $\partial A = A \cup {0}$ .
Note in (b) that $\partial A$ is "small" and in (a) that $\partial A$ is everything. Boundary means "touches both sides", not "thin edge".

□

Proposition 7.35 (Closure adds nothing the second time). $\overline{\overset{ˉ}{A}} = \overset{ˉ}{A}$ and $(A^{\circ})^{\circ} = A^{\circ}$ , and $A$ is closed iff $A = \overset{ˉ}{A}$ , open iff $A = A^{\circ}$ .

Proof. $\overset{ˉ}{A}$ is closed, and the smallest closed set containing a closed set is itself; likewise $A^{\circ}$ is open. If $A = \overset{ˉ}{A}$ then $A$ is closed as $\overset{ˉ}{A}$ is; conversely if $A$ is closed it is one of the sets intersected in the definition, so $\overset{ˉ}{A} \subseteq A \subseteq \overset{ˉ}{A}$ . The open case is dual.∎

Exercises for §7.7 →

7.8Limit points, isolated points, dense sets

The closure of $A$ consists of points of $A$ together with points approached by $A$ . Separating those two kinds is the business of this section.

Definition 7.36 (Limit point, isolated point, dense set). $x \in X$ is a limit point (or accumulation point) of $A$ if every ball $B (x, r)$ contains a point of $A$ other than $x$ . The set of limit points is the derived set $A^{'}$ . A point $a \in A$ that is not a limit point of $A$ is isolated: some ball meets $A$ only in $a$ . A set $D \subseteq X$ is dense if $\overset{ˉ}{D} = X$ , and $X$ is separable if it has a countable dense subset.

Proposition 7.37 (Closure splits into the set and its limit points). $\overset{ˉ}{A} = A \cup A^{'}$ , and consequently $A$ is closed if and only if $A^{'} \subseteq A$ .

Proof. If $x \in A$ then $x \in \overset{ˉ}{A}$ trivially, and if $x \in A^{'}$ every ball meets $A$ , so $x \in \overset{ˉ}{A}$ by the theorem Pointwise descriptions. Conversely let $x \in \overset{ˉ}{A}$ and $x \in / A$ ; every ball about $x$ meets $A$ , and the meeting point is not $x$ since $x \in / A$ , so $x \in A^{'}$ . The consequence follows from the proposition Closure adds nothing the second time: $A$ closed iff $A = \overset{ˉ}{A} = A \cup A^{'}$ iff $A^{'} \subseteq A$ .∎

Proposition 7.38 (A limit point is approached infinitely often). If $x$ is a limit point of $A$ , then every ball about $x$ contains infinitely many points of $A$ . Hence a finite set has no limit points.

Proof. Suppose some $B (x, r)$ met $A ∖ {x}$ in only finitely many points $a_{1}, \dots, a_{k}$ . Put $ρ = min_{i} d (x, a_{i}) > 0$ , a minimum of finitely many positive numbers. Then $B (x, ρ)$ contains no point of $A$ except possibly $x$ itself, contradicting that $x \in A^{'}$ .∎

Example 7.39 (Sorting the points of some familiar sets). For each set, find the limit points and the isolated points: (a) $A = {1/ n} \subseteq R$ ; (b) $A = Z \subseteq R$ ; (c) $A = Q \subseteq R$ ; (d) any $A$ in a discrete space.

Solution.

(a) $A^{'} = {0}$ and every point of $A$ is isolated: around $1/ n$ the ball of radius $\frac{1}{2} (\frac{1}{n} - \frac{1}{n + 1})$ meets $A$ only at $1/ n$ . So $A$ has one limit point, which is not in $A$ — hence $A$ is not closed.
(b) $Z^{'} = \emptyset$ ; every integer is isolated, since $B (n, \frac{1}{2}) \cap Z = {n}$ . A set with no limit points is closed by the proposition Closure splits into the set and its limit points, and indeed $Z$ is closed.
(c) $Q^{'} = R$ and no rational is isolated: every interval around a rational contains other rationals.
(d) In the discrete metric $B (x, \frac{1}{2}) = {x}$ , so no point is a limit point of anything: $A^{'} = \emptyset$ always, and every point of every set is isolated. This is the extreme case, and it matches the fact that every set there is closed.

□

Proposition 7.40 ( $R^{n}$ is separable). $Q^{n}$ is a countable dense subset of $R^{n}$ .

Proof. $Q^{n}$ is countable as a finite product of countable sets, by the results of Cardinality and Countability. Given $x \in R^{n}$ and $ε > 0$ , choose for each coordinate a rational $q_{i}$ with $∣ q_{i} - x_{i} ∣ < ε / n$ , possible by density of $Q$ in $R$ . Then $d_{2} (q, x)^{2} = \sum_{i} (q_{i} - x_{i})^{2} < n \cdot ε^{2} / n = ε^{2}$ , so $q \in B (x, ε)$ . Every ball meets $Q^{n}$ , so $\overline{Q^{n}} = R^{n}$ .∎

Separability is a smallness condition that most spaces of interest satisfy — $C [0, 1]$ is separable, by the Weierstrass approximation theorem, with the polynomials of rational coefficients as the countable dense set — and an uncountable discrete space is the standard space that is not.

Exercises for §7.8 →

7.9Compactness by open covers

Compactness is the property that lets a local hypothesis be upgraded to a global conclusion. The definition looks strange on first reading because it quantifies over all covers, and it is worth saying immediately what it is for: a statement true near each point of a compact set holds uniformly across the set, because finitely many neighbourhoods already do the job and a finite list has a minimum.

Intuition. Compactness is a finiteness licence. You are handed an infinite amount of local information — one neighbourhood per point, each guaranteeing something only nearby — and compactness says a finite sublist already covers everything. Finiteness is what lets you take a minimum of the $δ$ 's, a maximum of the bounds, a worst case over the list. Every proof in this section is that one move.

Definition 7.41 (Open cover, compactness). A family ${U_{α}}_{α \in A}$ of open sets is an open cover of $K \subseteq X$ if $K \subseteq ⋃_{α} U_{α}$ . The set $K$ is compact if every open cover of $K$ admits a finite subcover: there are $α_{1}, \dots, α_{n}$ with $K \subseteq U_{α_{1}} \cup \dots \cup U_{α_{n}}$ .

Two remarks on the logic, because misreading it is the usual first error. The definition demands a finite subcover for every cover; exhibiting one cover with a finite subcover proves nothing. And the subcover must be drawn from the given family, not replaced by some other finite family of open sets.

Proposition 7.42 (Compact implies closed and bounded). A compact subset $K$ of a metric space is closed and bounded.

Proof. Bounded. Fix $x_{0} \in X$ . The balls ${B (x_{0}, n)}_{n \in N}$ are open and cover $X$ , hence $K$ . A finite subcover is contained in the largest of its members, so $K \subseteq B (x_{0}, N)$ for some $N$ .

Closed. Let $y \in / K$ . For each $x \in K$ put $r_{x} = \frac{1}{2} d (x, y) > 0$ . The balls $B (x, r_{x})$ cover $K$ , so finitely many suffice: $K \subseteq ⋃_{i = 1}^{n} B (x_{i}, r_{x_{i}})$ . Set $ρ = min_{i} r_{x_{i}} > 0$ . If $z \in B (y, ρ)$ lay in $K$ , it would lie in some $B (x_{i}, r_{x_{i}})$ , and then

d (x_{i}, y) \leq d (x_{i}, z) + d (z, y) < r_{x_{i}} + ρ \leq 2 r_{x_{i}} = d (x_{i}, y),

a contradiction. So $B (y, ρ) \subseteq X ∖ K$ , and $X ∖ K$ is open.∎

The converse of this proposition is false in a general metric space — the example Bounded and closed but not compact settles that — and the two sections that follow identify the extra input that makes it true in $R^{n}$ and the correct general replacement.

Proposition 7.43 (A closed subset of a compact set is compact). If $K$ is compact and $F \subseteq K$ is closed in $X$ , then $F$ is compact.

Proof. Let ${U_{α}}$ be an open cover of $F$ . Adjoining the open set $V = X ∖ F$ gives an open cover of $K$ , since every point of $K$ is either in $F$ , hence in some $U_{α}$ , or outside $F$ , hence in $V$ . Extract a finite subcover of $K$ ; discard $V$ from it if present. The remaining finitely many $U_{α}$ still cover $F$ , because $V$ contains no point of $F$ .∎

Example 7.44 (A cover with no finite subcover). Show directly that $(0, 1]$ is not compact in $R$ , and that $[0, 1]$ is not covered by finitely many members of the same family.

Solution.

Take $U_{n} = (1/ n, 2)$ for $n \in N$ . Each is open, and their union is $(0, 2) \supseteq (0, 1]$ , since any $x > 0$ exceeds $1/ n$ for some $n$ .
Any finite subfamily $U_{n_{1}}, \dots, U_{n_{k}}$ has union $(1/ N, 2)$ where $N = max_{i} n_{i}$ , because the sets are nested increasing.
The point $\frac{1}{2 N} \in (0, 1]$ is missed. So no finite subfamily covers $(0, 1]$ , and $(0, 1]$ is not compact.
Consistency check with the proposition Compact implies closed and bounded: $(0, 1]$ is bounded but not closed, so the conclusion was unavailable anyway. The same family also fails to cover $[0, 1]$ at all — no $U_{n}$ contains $0$ — which is not a counterexample to compactness of $[0, 1]$ but a reminder that a "cover" must genuinely cover.

□

Exercises for §7.9 →

7.10The Heine–Borel theorem in $R^{n}$

Theorem 7.45 (Heine–Borel). A subset $K \subseteq R^{n}$ is compact if and only if it is closed and bounded.

Proof. ( $\Rightarrow$ ) This is the proposition Compact implies closed and bounded, valid in any metric space.

( $\Leftarrow$ ) By the proposition A closed subset of a compact set is compact it suffices to prove that a closed box $Q_{0} = [a_{1}, b_{1}] \times \dots \times [a_{n}, b_{n}]$ is compact, since a bounded $K$ lies in such a box and is closed in it.

Suppose some open cover ${U_{α}}$ of $Q_{0}$ has no finite subcover. Bisect each edge of $Q_{0}$ , splitting it into $2^{n}$ closed sub-boxes. If every sub-box had a finite subcover, their union — finitely many finite families — would be a finite subcover of $Q_{0}$ . So at least one sub-box $Q_{1}$ has none. Repeat, obtaining nested boxes

Q_{0} \supseteq Q_{1} \supseteq Q_{2} \supseteq \dots,

none admitting a finite subcover, with $diam (Q_{k}) = 2^{- k} diam (Q_{0}) \to 0$ .

For each coordinate $i$ , the $i$ -th edges form a nested sequence of closed intervals in $R$ , so by the Nested interval property — itself a consequence of the completeness axiom — their intersection is non-empty. Choosing one point in each coordinate gives $x \in ⋂_{k} Q_{k}$ .

Now $x \in Q_{0}$ , so $x \in U_{α_{0}}$ for some $α_{0}$ , and $U_{α_{0}}$ open gives $B (x, ε) \subseteq U_{α_{0}}$ . Choose $k$ with $diam (Q_{k}) < ε$ . Since $x \in Q_{k}$ , every point of $Q_{k}$ is within $ε$ of $x$ , so $Q_{k} \subseteq B (x, ε) \subseteq U_{α_{0}}$ . But then the single set $U_{α_{0}}$ is a finite subcover of $Q_{k}$ — contradicting the construction. Hence no such cover exists and $Q_{0}$ is compact.∎

Track where the hypotheses were spent. Boundedness put $K$ inside a box, which is what made bisection possible; closedness transferred compactness from the box down to $K$ ; and the completeness of $R$ produced the point $x$ in the nested intersection. Remove completeness and the theorem dies: in $Q$ , the set ${q \in Q : 2 \leq q^{2} \leq 3}$ is closed and bounded and not compact, because the nested boxes close in on an irrational that is simply not there.

Corollary 7.46 (Extreme value theorem). A continuous real-valued function on a non-empty compact set attains a maximum and a minimum.

Proof. By the theorem Continuous images of compact sets are compact below, $f (K) \subseteq R$ is compact, hence closed and bounded by Heine–Borel. Bounded and non-empty gives a finite supremum $M = sup f (K)$ ; by the theorem Pointwise descriptions, $M \in \overline{f (K)} = f (K)$ , so $M = f (x_{0})$ for some $x_{0} \in K$ . Apply the same to $- f$ for the minimum.∎

Example 7.47 (Deciding compactness in $R^{n}$ ). Which of these are compact in $R^{2}$ ? (a) the unit circle $S (0, 1)$ ; (b) the closed disc minus its centre; (c) ${(x, y) : x y = 1}$ ; (d) ${(x, y) : x^{2} + 4 y^{2} \leq 4}$ .

Solution.

(a) Closed as a sphere, by the corollary Closed balls and spheres are closed, and bounded inside $B (0, 2)$ : compact.
(b) Bounded, but not closed — the points $(1/ n, 0)$ lie in it and converge to the missing centre. Not compact.
(c) Closed, as the preimage of ${1}$ under the continuous map $(x, y) \mapsto x y$ , but unbounded, containing $(t, 1/ t)$ for all large $t$ . Not compact.
(d) A closed filled ellipse: closed as the preimage of $(- \infty, 4]$ under a continuous function, and bounded since $x^{2} \leq 4$ and $y^{2} \leq 1$ force $d_{2} \leq 5$ . Compact.
The recipe in $R^{n}$ is always the same two checks, and by Heine–Borel it is complete. Resist importing it into a general metric space.

□

Exercises for §7.10 →

7.11Sequential compactness and total boundedness

In a general metric space "closed and bounded" is too weak. The right strengthening of boundedness is that the space can be covered by finitely many balls of any prescribed radius.

Definition 7.48 (Sequential compactness, total boundedness). $K \subseteq X$ is sequentially compact if every sequence in $K$ has a subsequence converging to a point of $K$ . It is totally bounded if for every $ε > 0$ finitely many balls of radius $ε$ cover $K$ .

Totally bounded is strictly stronger than bounded: an infinite discrete space is bounded but cannot be covered by finitely many balls of radius $\frac{1}{2}$ , each of which is a single point. That gap is exactly what "closed and bounded" was missing.

Theorem 7.49 (Compactness equals sequential compactness in a metric space). For $K$ in a metric space, $K$ is compact if and only if $K$ is sequentially compact.

Proof. ( $\Rightarrow$ ) Let $K$ be compact and $(x_{n})$ a sequence in $K$ with no subsequential limit in $K$ . Then no $x \in K$ is a limit of a subsequence, so for each $x \in K$ there is $r_{x} > 0$ with $B (x, r_{x})$ containing $x_{n}$ for only finitely many indices $n$ — otherwise the indices with $x_{n} \in B (x, 1/ k)$ would be infinite for every $k$ and a subsequence converging to $x$ could be chosen. The balls $B (x, r_{x})$ cover $K$ ; take a finite subcover $B (x_{1}, r_{x_{1}}), \dots, B (x_{m}, r_{x_{m}})$ . Each contains only finitely many terms, so their union contains only finitely many — yet it contains all of them. Contradiction, since $N$ is infinite.

( $\Leftarrow$ ) Let $K$ be sequentially compact.

Step 1: $K$ is totally bounded. If not, there is $ε > 0$ such that no finite family of $ε$ -balls covers $K$ . Pick $x_{1} \in K$ ; having chosen $x_{1}, \dots, x_{k}$ , the balls $B (x_{i}, ε)$ do not cover $K$ , so pick $x_{k + 1}$ outside them. Then $d (x_{i}, x_{j}) \geq ε$ for $i \neq = j$ , so no subsequence is Cauchy, hence none converges — contradicting sequential compactness.

Step 2: every open cover has a Lebesgue number. Claim: for an open cover ${U_{α}}$ of $K$ there is $λ > 0$ such that every ball $B (x, λ)$ with $x \in K$ lies inside a single $U_{α}$ . If not, for each $n$ there is $x_{n} \in K$ with $B (x_{n}, 1/ n)$ contained in no $U_{α}$ . Pass to a subsequence $x_{n_{k}} \to x \in K$ . Then $x \in U_{α_{0}}$ for some $α_{0}$ , and $B (x, ε) \subseteq U_{α_{0}}$ for some $ε > 0$ . Choose $k$ with $d (x_{n_{k}}, x) < ε /2$ and $1/ n_{k} < ε /2$ . For $y \in B (x_{n_{k}}, 1/ n_{k})$ , $d (y, x) \leq d (y, x_{n_{k}}) + d (x_{n_{k}}, x) < ε$ , so $B (x_{n_{k}}, 1/ n_{k}) \subseteq U_{α_{0}}$ — contradiction.

Step 3: conclude. Given an open cover, take its Lebesgue number $λ$ and, by Step 1, cover $K$ by finitely many balls $B (y_{1}, λ), \dots, B (y_{m}, λ)$ with $y_{i} \in K$ . Each $B (y_{i}, λ)$ sits inside some $U_{α_{i}}$ , and then $U_{α_{1}}, \dots, U_{α_{m}}$ is a finite subcover.∎

Corollary 7.50 (Compact equals complete plus totally bounded). A metric space is compact if and only if it is complete and totally bounded.

Proof. If $X$ is compact it is totally bounded by Step 1 of the proof above, and complete: a Cauchy sequence has a convergent subsequence by the theorem Compactness equals sequential compactness in a metric space, and a Cauchy sequence with a convergent subsequence converges, since $d (x_{n}, x) \leq d (x_{n}, x_{n_{k}}) + d (x_{n_{k}}, x)$ makes both terms small. Conversely, given a sequence in a complete totally bounded space, cover by finitely many balls of radius $1/2$ ; one contains infinitely many terms. Inside it, cover by finitely many balls of radius $1/4$ , and so on. A diagonal choice produces a subsequence whose terms eventually lie within $2^{- k}$ of one another, hence Cauchy, hence convergent by completeness. So $X$ is sequentially compact, hence compact.∎

This corollary is the correct generalisation of Heine–Borel, and it explains Heine–Borel: in $R^{n}$ , completeness is automatic and bounded already implies totally bounded, because a bounded set fits in a box and a box is cut into finitely many small boxes. In $C [0, 1]$ neither simplification holds, and the closed unit ball there is famously not compact.

Exercises for §7.11 →

7.12What compactness buys

Theorem 7.51 (Continuous images of compact sets are compact). If $f : X \to Y$ is continuous and $K \subseteq X$ is compact, then $f (K)$ is compact.

Proof. Let ${V_{α}}$ be an open cover of $f (K)$ in $Y$ . For each $α$ put $U_{α} = f^{- 1} (V_{α})$ , which is open in $X$ : if $x \in U_{α}$ then $f (x) \in V_{α}$ , so $B (f (x), ε) \subseteq V_{α}$ for some $ε$ , and continuity supplies $δ > 0$ with $f (B (x, δ)) \subseteq B (f (x), ε) \subseteq V_{α}$ , i.e. $B (x, δ) \subseteq U_{α}$ .

The $U_{α}$ cover $K$ , since each $x \in K$ has $f (x)$ in some $V_{α}$ . Compactness yields $K \subseteq U_{α_{1}} \cup \dots \cup U_{α_{n}}$ , and applying $f$ ,

f (K) \subseteq f (U_{α_{1}}) \cup \dots \cup f (U_{α_{n}}) \subseteq V_{α_{1}} \cup \dots \cup V_{α_{n}} .

∎

Theorem 7.52 (Heine–Cantor: continuity on a compact set is uniform). A continuous map $f : K \to Y$ on a compact metric space $K$ is uniformly continuous.

Proof. Fix $ε > 0$ . For each $x \in K$ continuity gives $δ_{x} > 0$ with $d_{Y} (f (x), f (z)) < ε /2$ whenever $d (x, z) < δ_{x}$ . The balls $B (x, δ_{x} /2)$ cover $K$ ; take a finite subcover indexed by $x_{1}, \dots, x_{n}$ and put $δ = \frac{1}{2} min_{i} δ_{x_{i}} > 0$ .

Let $d (u, v) < δ$ . Then $u \in B (x_{i}, δ_{x_{i}} /2)$ for some $i$ , and $d (x_{i}, v) \leq d (x_{i}, u) + d (u, v) < δ_{x_{i}} /2 + δ \leq δ_{x_{i}}$ . So both $u$ and $v$ are within $δ_{x_{i}}$ of $x_{i}$ , whence

d_{Y} (f (u), f (v)) \leq d_{Y} (f (u), f (x_{i})) + d_{Y} (f (x_{i}), f (v)) < ε .

The $δ$ depends only on $ε$ .∎

Corollary 7.53 (A continuous bijection off a compact set is a homeomorphism). If $f : K \to Y$ is a continuous bijection and $K$ is compact, then $f^{- 1}$ is continuous.

Proof. It suffices that $f$ carry closed sets to closed sets, since $(f^{- 1})^{- 1} (F) = f (F)$ . Let $F \subseteq K$ be closed. Then $F$ is compact by the proposition A closed subset of a compact set is compact, so $f (F)$ is compact by the theorem Continuous images of compact sets are compact, hence closed by the proposition Compact implies closed and bounded.∎

Example 7.54 (Where compactness is doing the work). Show that $f (x) = x^{2}$ is uniformly continuous on $[0, 10]$ but not on $[0, \infty)$ , and find the largest $δ$ that works for $ε = 1$ on $[0, 10]$ .

Solution.

$[0, 10]$ is compact by Heine–Borel and $f$ is continuous, so uniform continuity is automatic by the theorem Heine–Cantor.
On $[0, \infty)$ take $u_{n} = n$ and $v_{n} = n + 1/ n$ . Then $d (u_{n}, v_{n}) = 1/ n \to 0$ but $∣ f (v_{n}) - f (u_{n}) ∣ = 2 + 1/ n^{2} > 2$ , so no $δ$ works for $ε = 2$ .
Quantitatively on $[0, 10]$ : $∣ u^{2} - v^{2} ∣ = ∣ u - v ∣ ∣ u + v ∣ \leq 20∣ u - v ∣$ , so $δ = ε /20$ suffices; for $ε = 1$ that gives $δ = 0.05$ .
The contrast is exactly the failure of compactness: on the unbounded ray the local Lipschitz constant $∣ u + v ∣$ is unbounded, and there is no finite subcover to take a minimum over.

□

Exercises for §7.12 →

7.13Completeness: definition and examples

The proposition Convergent implies Cauchy, and Cauchy implies bounded left one implication open. Spaces in which it closes are the ones in which analysis works.

Definition 7.55 (Complete metric space). $(X, d)$ is complete if every Cauchy sequence in $X$ converges to a point of $X$ .

Completeness is a property of the pair $(X, d)$ , not of the topology: the proposition Strong equivalence implies topological equivalence gave $R$ two topologically equivalent metrics, and the space $(0, 1)$ carries a metric equivalent to the usual one under which it is complete, even though $(0, 1)$ with $∣ x - y ∣$ is not. Completeness is a metric notion, and this is the standard warning against treating it as a topological one.

Theorem 7.56 ( $R$ is complete). Every Cauchy sequence of real numbers converges.

Proof. Let $(x_{n})$ be Cauchy. It is bounded, by the proposition Convergent implies Cauchy, and Cauchy implies bounded. By the Bolzano–Weierstrass theorem it has a convergent subsequence $x_{n_{k}} \to x$ . Given $ε > 0$ , choose $N$ with $d (x_{m}, x_{n}) < ε /2$ for $m, n \geq N$ , and choose $k$ with $n_{k} \geq N$ and $∣ x_{n_{k}} - x ∣ < ε /2$ . Then for every $n \geq N$ ,

∣ x_{n} - x ∣ \leq ∣ x_{n} - x_{n_{k}} ∣ + ∣ x_{n_{k}} - x ∣ < ε .

∎

Proposition 7.57 (Completeness passes to $R^{n}$ and to closed subsets). $R^{n}$ is complete, and a subset $F$ of a complete metric space $X$ is complete (as a space in its own right) if and only if $F$ is closed in $X$ .

Proof. For $R^{n}$ : if $(x^{(k)})$ is Cauchy then each coordinate sequence is Cauchy, since $∣ x_{i}^{(k)} - x_{i}^{(m)} ∣ \leq d_{2} (x^{(k)}, x^{(m)})$ . Each converges by the theorem $R$ is complete, to some $y_{i}$ , and then $d_{2} (x^{(k)}, y)^{2} = \sum_{i} (x_{i}^{(k)} - y_{i})^{2} \to 0$ as a finite sum of null sequences.

For the second claim. If $F$ is closed and $(x_{n}) \subseteq F$ is Cauchy, it converges in $X$ by completeness and its limit lies in $F$ by the theorem Sequential characterisation of closed sets. Conversely if $F$ is complete and $x_{n} \in F$ with $x_{n} \to x \in X$ , then $(x_{n})$ is Cauchy, so it converges in $F$ ; limits are unique by the proposition Limits are unique, so $x \in F$ and $F$ is closed.∎

Example 7.58 (Three incomplete spaces, and what is missing). Exhibit a non-convergent Cauchy sequence in (a) $Q$ ; (b) $(0, 1]$ with the usual metric; (c) $C [0, 1]$ with the $L^{1}$ metric $d (f, g) = \int_{0}^{1} ∣ f - g ∣$ .

Solution.

(a) Let $x_{n}$ be the decimal expansion of $2$ truncated to $n$ places. Then $∣ x_{m} - x_{n} ∣ \leq 1 0^{- m i n (m, n)}$ , so the sequence is Cauchy in $Q$ ; its only possible limit in $R$ is $2$ , which is irrational, so by uniqueness of limits it has no limit in $Q$ .
(b) $x_{n} = 1/ n$ is Cauchy and converges in $R$ to $0 \in / (0, 1]$ . By the proposition Completeness passes to $R^{n}$ and to closed subsets this had to happen: $(0, 1]$ is not closed in $R$ .
(c) Let $f_{n}$ be $0$ on $[0, \frac{1}{2}]$ , $1$ on $[\frac{1}{2} + \frac{1}{n}, 1]$ , linear between. Then $d (f_{n}, f_{m}) \leq \frac{1}{2} \frac{1}{n} - \frac{1}{m} \to 0$ , so the sequence is Cauchy, but any $L^{1}$ -limit would have to agree almost everywhere with the step function jumping at $\frac{1}{2}$ , which no continuous function does.
The moral of (c) is that the same set $C [0, 1]$ is complete in the sup metric (proved below) and incomplete in the $L^{1}$ metric. Completeness is about $d$ , not about $X$ .

□

Theorem 7.59 ( $C [0, 1]$ with the sup metric is complete). The space $C [0, 1]$ with $d_{\infty} (f, g) = sup_{t} ∣ f (t) - g (t) ∣$ is complete.

Proof. Let $(f_{n})$ be Cauchy. For each fixed $t$ , $∣ f_{n} (t) - f_{m} (t) ∣ \leq d_{\infty} (f_{n}, f_{m})$ , so $(f_{n} (t))$ is Cauchy in $R$ and converges; call the limit $f (t)$ .

The convergence is uniform: given $ε > 0$ take $N$ with $d_{\infty} (f_{n}, f_{m}) < ε$ for $n, m \geq N$ ; fixing $n \geq N$ and letting $m \to \infty$ in $∣ f_{n} (t) - f_{m} (t) ∣ < ε$ gives $∣ f_{n} (t) - f (t) ∣ \leq ε$ for every $t$ , hence $d_{\infty} (f_{n}, f) \leq ε$ .

Finally $f$ is continuous, by the theorem A uniform limit of continuous functions is continuous of Sequences and Series of Functions. So $f \in C [0, 1]$ and $f_{n} \to f$ in the metric.∎

Exercises for §7.13 →

7.14Banach spaces

Most metric spaces in analysis come from a norm, and the extra linear structure makes series available.

Definition 7.60 (Norm, normed space, Banach space). A norm on a real vector space $V$ is a map $∥ \cdot ∥ : V \to [0, \infty)$ with $∥ v ∥ = 0 ⟺ v = 0$ , $∥ λ v ∥ = ∣ λ ∣ ∥ v ∥$ , and $∥ u + v ∥ \leq ∥ u ∥ + ∥ v ∥$ . It induces the metric $d (u, v) = ∥ u - v ∥$ . A Banach space is a normed space complete in that metric.

Proposition 7.61 (The induced metric is a metric, and is translation invariant). $d (u, v) = ∥ u - v ∥$ is a metric satisfying $d (u + w, v + w) = d (u, v)$ and $d (λ u, λ v) = ∣ λ ∣ d (u, v)$ .

Proof. $d (u, v) = 0$ iff $∥ u - v ∥ = 0$ iff $u = v$ . Symmetry: $∥ v - u ∥ = ∥ (- 1) (u - v) ∥ = ∣ - 1∣ ∥ u - v ∥ = ∥ u - v ∥$ . Triangle: $∥ u - w ∥ = ∥ (u - v) + (v - w) ∥ \leq ∥ u - v ∥ + ∥ v - w ∥$ . The two invariances are immediate from $(u + w) - (v + w) = u - v$ and $λ u - λ v = λ (u - v)$ with homogeneity.∎

Translation invariance is the property a general metric lacks, and it is why in a normed space one may always reduce a question about the ball $B (x, r)$ to the same question about $B (0, 1)$ . The discrete metric on $R$ is not induced by any norm, since $d (2 \cdot 1, 2 \cdot 0) = 1 \neq = 2 = 2 d (1, 0)$ .

Theorem 7.62 (Completeness by absolutely convergent series). A normed space $V$ is complete if and only if every series $\sum_{k} v_{k}$ with $\sum_{k} ∥ v_{k} ∥ < \infty$ converges in $V$ .

Proof. ( $\Rightarrow$ ) Let $\sum ∥ v_{k} ∥ < \infty$ and $s_{n} = \sum_{k \leq n} v_{k}$ . For $m < n$ , $∥ s_{n} - s_{m} ∥ \leq \sum_{k = m + 1}^{n} ∥ v_{k} ∥$ , which is small for large $m$ because the tail of a convergent series of non-negative reals tends to $0$ . So $(s_{n})$ is Cauchy and converges.

( $\Leftarrow$ ) Let $(x_{n})$ be Cauchy. Choose $n_{1} < n_{2} < \dots$ with $∥ x_{m} - x_{n_{k}} ∥ < 2^{- k}$ for all $m \geq n_{k}$ . Put $v_{1} = x_{n_{1}}$ and $v_{k + 1} = x_{n_{k + 1}} - x_{n_{k}}$ , so $∥ v_{k + 1} ∥ < 2^{- k}$ and $\sum ∥ v_{k} ∥ < \infty$ . By hypothesis the series converges, and its $k$ -th partial sum telescopes to $x_{n_{k}}$ , so the subsequence converges. A Cauchy sequence with a convergent subsequence converges, as in the corollary Compact equals complete plus totally bounded.∎

Example 7.63 (Which of these are Banach?). Decide completeness for (a) $R^{n}$ with $∥ \cdot ∥_{2}$ ; (b) $C [0, 1]$ with $∥ f ∥_{\infty}$ ; (c) the polynomials $P \subseteq C [0, 1]$ with $∥ \cdot ∥_{\infty}$ ; (d) $ℓ^{\infty}$ , bounded real sequences with $∥ x ∥_{\infty} = sup_{k} ∣ x_{k} ∣$ .

Solution.

(a) Complete by the proposition Completeness passes to $R^{n}$ and to closed subsets.
(b) Complete by the theorem $C [0, 1]$ with the sup metric is complete.
(c) Not complete. The partial sums of $\sum_{k} t^{k} / k!$ are polynomials forming a Cauchy sequence in $∥ \cdot ∥_{\infty}$ whose limit $e^{t}$ is not a polynomial. Equivalently, $P$ is dense in $C [0, 1]$ by the Weierstrass approximation theorem and $P \neq = C [0, 1]$ , so $P$ is not closed and the proposition Completeness passes to $R^{n}$ and to closed subsets applies.
(d) Complete, by the argument of the theorem $C [0, 1]$ with the sup metric is complete with the index $k$ in place of the variable $t$ ; there is no continuity to check at the end, so the proof is shorter.

□

Exercises for §7.14 →

7.15Completion of a metric space

$Q$ is incomplete and $R$ repairs it. That repair is a general construction, and it works with no properties of $Q$ beyond being a metric space.

Definition 7.64 (Isometry and completion). A map $ι : X \to Y$ between metric spaces is an isometry if $d_{Y} (ι x, ι x^{'}) = d_{X} (x, x^{'})$ for all $x, x^{'}$ . A completion of $X$ is a complete metric space $\hat{X}$ together with an isometry $ι : X \to \hat{X}$ whose image is dense in $\hat{X}$ .

Theorem 7.65 (Every metric space has a completion, unique up to isometry). Every metric space $X$ admits a completion, and any two completions of $X$ are related by a surjective isometry fixing $X$ .

Proof. Construction. Let $C$ be the set of Cauchy sequences in $X$ and declare $(x_{n}) \sim (y_{n})$ when $d (x_{n}, y_{n}) \to 0$ . This is an equivalence relation, transitivity following from $d (x_{n}, z_{n}) \leq d (x_{n}, y_{n}) + d (y_{n}, z_{n})$ . Let $\hat{X} = C / \sim$ and set

\hat{d} ([(x_{n})], [(y_{n})]) = n \to \infty lim d (x_{n}, y_{n}) .

The limit exists because $∣ d (x_{n}, y_{n}) - d (x_{m}, y_{m}) ∣ \leq d (x_{n}, x_{m}) + d (y_{n}, y_{m})$ by two applications of the proposition Reverse triangle inequality, making the real sequence Cauchy; and it is unchanged by replacing either sequence with an equivalent one, by the same estimate. Positivity of $\hat{d}$ holds by the definition of $\sim$ , and symmetry and the triangle inequality pass to the limit.

Embedding. Send $x$ to the class of the constant sequence. Then $\hat{d} (ι x, ι x^{'}) = d (x, x^{'})$ , so $ι$ is an isometry. Its image is dense: given $[(x_{n})]$ and $ε > 0$ , choose $N$ with $d (x_{n}, x_{m}) < ε$ for $n, m \geq N$ ; then $\hat{d} ([(x_{n})], ι x_{N}) = lim_{m} d (x_{m}, x_{N}) \leq ε$ .

Completeness. Let $(ξ_{k})$ be Cauchy in $\hat{X}$ . By density pick $y_{k} \in X$ with $\hat{d} (ξ_{k}, ι y_{k}) < 1/ k$ . Then $(ι y_{k})$ is Cauchy, hence so is $(y_{k})$ in $X$ since $ι$ is an isometry, and $ξ = [(y_{k})]$ satisfies $\hat{d} (ξ_{k}, ξ) \leq \hat{d} (ξ_{k}, ι y_{k}) + \hat{d} (ι y_{k}, ξ) \to 0$ .

Uniqueness. If $ι_{1} : X \to Y_{1}$ and $ι_{2} : X \to Y_{2}$ are two completions, define $φ$ on the dense set $ι_{1} (X)$ by $φ (ι_{1} x) = ι_{2} x$ . It is an isometry there, so it is uniformly continuous and extends to all of $Y_{1}$ by taking limits of Cauchy sequences, the limits existing by completeness of $Y_{2}$ . The extension is still an isometry, since $d$ is continuous, and its image is a complete, hence closed, set containing the dense set $ι_{2} (X)$ , so it is all of $Y_{2}$ .∎

Applied to $Q$ this construction is the Cauchy-sequence construction of $R$ . Applied to $C [0, 1]$ with the $L^{1}$ metric it produces the Lebesgue space $L^{1} [0, 1]$ , which is the honest answer to why Lebesgue integration is needed: the completion exists abstractly, and Lebesgue theory identifies its elements as functions rather than as equivalence classes of sequences.

Remark. Completion never adds anything that was not already being approached. If $X$ is already complete, every Cauchy sequence converges, so every class contains a constant sequence and $ι$ is onto: $\hat{X} = X$ . The construction is idempotent, as any decent repair should be.

Exercises for §7.15 →

7.16Baire category: a first look

Completeness has a consequence that is not about limits of particular sequences at all, but about how a complete space can be decomposed.

Definition 7.66 (Nowhere dense). $A \subseteq X$ is nowhere dense if $\overline{A}$ has empty interior: $(\overset{ˉ}{A})^{\circ} = \emptyset$ . Equivalently, every ball contains a sub-ball missing $A$ .

The equivalence is worth spelling out, since it is the form used in proofs: $(\overset{ˉ}{A})^{\circ} = \emptyset$ says no ball is contained in $\overset{ˉ}{A}$ , so every ball $B$ meets $X ∖ \overset{ˉ}{A}$ , which is open, and therefore contains a ball disjoint from $\overset{ˉ}{A}$ and a fortiori from $A$ .

Theorem 7.67 (Baire category theorem, preliminary form). A non-empty complete metric space is not the union of countably many nowhere dense sets.

The full statement and its proof occupy the last movement of this chapter; the point of stating it here is that it is a theorem about completeness, provable from nothing else, and that it is the reason completeness matters beyond the ability to take limits.

Example 7.68 ( $Q$ is meagre in itself). Show that $Q$ is a countable union of nowhere dense subsets of $Q$ , and say what this proves.

Solution.

Enumerate $Q = {q_{1}, q_{2}, \dots}$ , possible since $Q$ is countable, and write $Q = ⋃_{k} {q_{k}}$ .
Each singleton ${q_{k}}$ is closed, and it has empty interior in $Q$ because every interval of rationals contains more than one rational. So each is nowhere dense in $Q$ .
By the theorem Baire category theorem, preliminary form, $Q$ with the usual metric therefore cannot be complete — which we knew independently from the example Three incomplete spaces, and what is missing, but now as a corollary of a structural theorem rather than by exhibiting $2$ .
Contrast $R$ : singletons are nowhere dense there too, so this argument shows $R$ is uncountable. That proof of uncountability uses no decimal expansions and no diagonal argument.

□

Exercises for §7.16 →

7.17Connectedness

"All one piece" is made precise by the impossibility of splitting, and the definition is phrased negatively for a reason: there is no positive way to say a set cannot be cut.

Definition 7.69 (Connected space, separation). A metric space $X$ is disconnected if there exist non-empty open sets $U, V$ with $U \cap V = \emptyset$ and $U \cup V = X$ ; such a pair is a separation. $X$ is connected if no separation exists. A subset $A \subseteq X$ is connected if it is connected as a space in the subspace metric.

Proposition 7.70 (Equivalent formulations). For a metric space $X$ the following are equivalent: (i) $X$ is connected; (ii) the only subsets of $X$ that are both open and closed are $\emptyset$ and $X$ ; (iii) every continuous $f : X \to {0, 1}$ , the latter discrete, is constant.

Proof. (i) $\Rightarrow$ (ii): if $U$ is open, closed and proper and non-empty, then $(U, X ∖ U)$ is a separation.

(ii) $\Rightarrow$ (iii): $f^{- 1} ({0})$ is open, since ${0}$ is open in the discrete space and preimages of open sets under continuous maps are open — proved inside the theorem Continuous images of compact sets are compact. Its complement $f^{- 1} ({1})$ is open for the same reason, so $f^{- 1} ({0})$ is also closed, hence $\emptyset$ or $X$ , and $f$ is constant.

(iii) $\Rightarrow$ (i): given a separation $(U, V)$ , the function equal to $0$ on $U$ and $1$ on $V$ is continuous — each preimage is $\emptyset$ , $U$ , $V$ or $X$ , all open — and non-constant, since both $U$ and $V$ are non-empty.∎

Theorem 7.71 (Continuous images of connected sets are connected). If $f : X \to Y$ is continuous and $X$ is connected, then $f (X)$ is connected.

Proof. Use criterion (iii) of the proposition Equivalent formulations. Let $g : f (X) \to {0, 1}$ be continuous. Then $g \circ f : X \to {0, 1}$ is continuous as a composition, hence constant since $X$ is connected. As $f$ is onto $f (X)$ , $g$ takes only that one value on $f (X)$ , so $g$ is constant and $f (X)$ is connected.∎

Proposition 7.72 (Unions with a common point). If ${A_{α}}$ are connected subsets of $X$ with $⋂_{α} A_{α} \neq = \emptyset$ , then $⋃_{α} A_{α}$ is connected.

Proof. Fix $p$ in the common intersection and let $f : ⋃ A_{α} \to {0, 1}$ be continuous. Its restriction to each $A_{α}$ is continuous, hence constant, and that constant equals $f (p)$ because $p \in A_{α}$ . So $f \equiv f (p)$ on the union, which is therefore connected by the proposition Equivalent formulations.∎

Exercises for §7.17 →

7.18Connected subsets of $R$ are exactly the intervals

Definition 7.73 (Interval). $I \subseteq R$ is an interval if $x, y \in I$ and $x < z < y$ imply $z \in I$ . This includes $\emptyset$ , singletons, and the unbounded and half-open cases.

Theorem 7.74 (Connected subsets of $R$ ). $I \subseteq R$ is connected if and only if $I$ is an interval.

Proof. ( $\Rightarrow$ ) Suppose $I$ is not an interval: there are $x < z < y$ with $x, y \in I$ and $z \in / I$ . Then $U = I \cap (- \infty, z)$ and $V = I \cap (z, \infty)$ are open in $I$ , disjoint, non-empty (they contain $x$ and $y$ ), and their union is $I$ because $z \in / I$ . That is a separation.

( $\Leftarrow$ ) Let $I$ be an interval and suppose $I = U ⊔ V$ is a separation. Pick $u \in U$ , $v \in V$ , and assume $u < v$ ; then $[u, v] \subseteq I$ . Let

s = sup {t \in [u, v] : t \in U},

which exists by the completeness axiom and lies in $[u, v] \subseteq I$ , so $s \in U$ or $s \in V$ .

If $s \in U$ , then $U$ open in $I$ gives an interval $(s - η, s + η) \cap I \subseteq U$ ; since $s \neq = v$ (as $v \in V$ ), points just to the right of $s$ lie in $[u, v] \cap U$ , contradicting that $s$ is an upper bound.

If $s \in V$ , then $V$ open gives $(s - η, s + η) \cap I \subseteq V$ , so no point of $U$ lies in $(s - η, s]$ ; but $s$ is a supremum of a set of points of $U$ , so some point of $U$ lies in $(s - η, s]$ . Contradiction either way, so no separation exists.∎

Corollary 7.75 (Intermediate value theorem). If $f : [a, b] \to R$ is continuous and $y$ lies between $f (a)$ and $f (b)$ , then $f (c) = y$ for some $c \in [a, b]$ .

Proof. $[a, b]$ is an interval, hence connected by the theorem Connected subsets of $R$ , so $f ([a, b])$ is connected by the theorem Continuous images of connected sets are connected, hence is an interval. An interval containing $f (a)$ and $f (b)$ contains everything between them, in particular $y$ .∎

That derivation is the reason connectedness is worth defining. The intermediate value theorem, proved directly, is a bisection argument special to $R$ ; proved this way it is the composition of two structural facts, and the same composition yields the analogous statement in any connected domain.

Example 7.76 (Connected or not?). Decide connectedness for (a) $Q \subseteq R$ ; (b) ${(x, y) \in R^{2} : x^{2} + y^{2} = 1}$ ; (c) $R^{2}$ minus a point; (d) $R$ minus a point.

Solution.

(a) Disconnected, badly: $U = Q \cap (- \infty, 2)$ and $V = Q \cap (2, \infty)$ separate it, and the same trick works around every irrational. In fact the only connected subsets of $Q$ are the singletons and $\emptyset$ — such a space is called totally disconnected.
(b) Connected: it is the image of the connected interval $[0, 2 π]$ under the continuous map $t \mapsto (cos t, sin t)$ , so the theorem Continuous images of connected sets are connected applies.
(c) Connected. Any two points can be joined by a path avoiding the removed point, so the section Path-connectedness implies connectedness gives the result.
(d) Disconnected: $R ∖ {0} = (- \infty, 0) \cup (0, \infty)$ , and by the theorem Connected subsets of $R$ it fails the interval test directly. Dimension matters: removing a point disconnects a line but not a plane.

□

Exercises for §7.18 →

7.19Path-connectedness, and why it is strictly stronger

Definition 7.77 (Path, path-connected). A path from $x$ to $y$ in $X$ is a continuous $γ : [0, 1] \to X$ with $γ (0) = x$ and $γ (1) = y$ . $X$ is path-connected if every pair of points is joined by a path.

Theorem 7.78 (Path-connected implies connected). Every path-connected metric space is connected.

Proof. Suppose $X$ is path-connected and non-empty, and fix $p \in X$ . For each $x \in X$ choose a path $γ_{x}$ from $p$ to $x$ ; its image $γ_{x} ([0, 1])$ is connected by the theorems Connected subsets of $R$ and Continuous images of connected sets are connected, being the continuous image of the interval $[0, 1]$ .

Every one of these images contains $p$ , so their intersection is non-empty, and their union is all of $X$ since $x \in γ_{x} ([0, 1])$ . By the proposition Unions with a common point, $X$ is connected.∎

The converse fails, and the standard counterexample is worth knowing precisely because it shows that "connected" is genuinely weaker than the intuitive picture of being able to walk from any point to any other.

Example 7.79 (The topologist's sine curve). Let $S = {(x, sin (1/ x)) : 0 < x \leq 1}$ and $T = S \cup ({0} \times [- 1, 1])$ . Show $T$ is connected but not path-connected.

Solution.

$S$ is connected, as the continuous image of $(0, 1]$ under $x \mapsto (x, sin (1/ x))$ .
$\overset{ˉ}{S} = T$ : any $(0, c)$ with $∣ c ∣ \leq 1$ is a limit of points of $S$ , since $sin (1/ x)$ takes the value $c$ at $x = 1/ (arcsin c + 2 πk)$ for every large integer $k$ , and those $x$ tend to $0$ .
A set squeezed between a connected set and its closure is connected: if $S \subseteq T \subseteq \overset{ˉ}{S}$ and $T = U ⊔ V$ were a separation, then $S$ connected forces $S$ inside one piece, say $U$ ; but then $V$ is a non-empty open subset of $T$ disjoint from $S$ , contradicting that every point of $T$ is in $\overset{ˉ}{S}$ . So $T$ is connected.
$T$ is not path-connected. Suppose $γ : [0, 1] \to T$ ran from $(0, 0)$ to $(1, sin 1)$ , and let $t_{0}$ be the supremum of times with first coordinate $0$ . On $(t_{0}, 1]$ the first coordinate is positive, and by continuity of $γ$ at $t_{0}$ the second coordinate would have to converge to $γ (t_{0})$ 's. But as $t ↓ t_{0}$ the first coordinate tends to $0$ while $sin (1/ x)$ oscillates through all of $[- 1, 1]$ infinitely often on every interval $(0, η)$ , so the second coordinate has no limit. Contradiction.
The two notions therefore differ, and the difference lives entirely at the limit segment: $T$ is the union of two path-connected pieces glued by closure rather than by any path.

□

Figure 7.80. The topologist's sine curve: the oscillating graph of

sin (1/ x)

(0, 1]

together with the vertical segment at

x = 0

that its closure adds. The set is connected — the segment is in the closure of the graph — but no path runs from the segment to the graph.

Remark. The implication does become an equivalence for open subsets of $R^{n}$ : in an open connected $U \subseteq R^{n}$ , the set of points reachable from a fixed $p$ by a path is both open and closed in $U$ — around any point a whole ball is reachable, balls being convex — hence is all of $U$ by criterion (ii) of the proposition Equivalent formulations. Every counterexample is therefore forced to be non-open, as the topologist's sine curve is.

Exercises for §7.19 →

7.20Components and quasicomponents

A space that is not connected still decomposes canonically into connected pieces.

Definition 7.81 (Connected component). The component of $x \in X$ is the union of all connected subsets of $X$ containing $x$ . The quasicomponent of $x$ is the intersection of all sets containing $x$ that are simultaneously open and closed.

Proposition 7.82 (Components partition the space and are closed). Each component is connected and closed, distinct components are disjoint, and the components cover $X$ .

Proof. The component $C_{x}$ is a union of connected sets all containing $x$ , hence connected by the proposition Unions with a common point, and it is maximal by construction. If $C_{x} \cap C_{y} \neq = \emptyset$ then $C_{x} \cup C_{y}$ is connected by the same proposition and contains both $x$ and $y$ , so maximality gives $C_{x} = C_{x} \cup C_{y} = C_{y}$ . Coverage holds since $x \in C_{x}$ .

Closedness: $\overset{ˉ}{C_{x}}$ is connected — the argument in step 3 of the example The topologist's sine curve applies verbatim to any set between a connected set and its closure — and contains $x$ , so $\overset{ˉ}{C_{x}} \subseteq C_{x}$ by maximality.∎

Proposition 7.83 (Components sit inside quasicomponents). The component of $x$ is contained in its quasicomponent, and the inclusion can be strict.

Proof. Let $A$ be open and closed with $x \in A$ . Then $A \cap C_{x}$ is open and closed in $C_{x}$ and contains $x$ , so by criterion (ii) of the proposition Equivalent formulations applied to the connected space $C_{x}$ , it equals $C_{x}$ ; that is, $C_{x} \subseteq A$ . Intersecting over all such $A$ gives $C_{x} \subseteq Q_{x}$ .

For strictness take $X = {0} \cup {1/ n : n \in N} \cup {(0, 2)}$ realised in $R^{2}$ as $X = ({0} \cup {1/ n}) \times {0, 1}$ together with nothing else: the component of $(0, 0)$ is the singleton ${(0, 0)}$ , since $X$ is totally disconnected, while any open-and-closed set containing $(0, 0)$ must contain $(1/ n, 0)$ for large $n$ and, by a connectedness-free separation argument, also $(0, 1)$ . So the quasicomponent is strictly larger.∎

Proposition 7.84 (In a compact space the two agree). If $X$ is compact, every quasicomponent is a component.

Proof. Given the inclusion already proved, it suffices to show $Q_{x}$ is connected. Suppose $Q_{x} = A ⊔ B$ with $A, B$ closed in $Q_{x}$ , disjoint, and $x \in A$ . As $Q_{x}$ is an intersection of closed sets it is closed, hence compact by the proposition A closed subset of a compact set is compact, so $A$ and $B$ are compact and can be separated by disjoint open sets $U \supseteq A$ , $V \supseteq B$ of $X$ , using the argument of the proposition Compact implies closed and bounded. The family of open-and-closed sets containing $x$ has intersection $Q_{x} \subseteq U \cup V$ ; by compactness finitely many of them, hence their intersection $A_{0}$ , satisfy $A_{0} \subseteq U \cup V$ . Then $A_{0} \cap U$ is open and closed — closed because its closure lies in $A_{0} \cap \overset{ˉ}{U}$ , which avoids $V$ and so lies in $A_{0} \cap U$ — and contains $x$ , so $Q_{x} \subseteq A_{0} \cap U$ , forcing $B = \emptyset$ .∎

Example 7.85 (Counting components). Find the components of (a) $R ∖ Z$ ; (b) ${1/ n : n \in N} \cup {0}$ ; (c) ${(x, y) : x^{2} - y^{2} = 1}$ .

Solution.

(a) The intervals $(n, n + 1)$ for $n \in Z$ : each is connected as an interval, and no larger connected subset exists because any set meeting two of them would contain an integer by the theorem Connected subsets of $R$ . Countably many components.
(b) Every point is its own component, so there are countably many — the space is totally disconnected. Note ${0}$ is a component that is not open in the space, so components need not be open.
(c) A hyperbola with two branches, $x \geq 1$ and $x \leq - 1$ , each the continuous image of $R$ under $t \mapsto (\pm cosh t, sinh t)$ and hence connected, and separated by the open sets $x > 0$ and $x < 0$ . Two components.

□

Exercises for §7.20 →

7.21The contraction mapping principle: statement

Everything in this chapter has been vocabulary. The next theorem is the first that produces something: it manufactures solutions to equations, and it is the reason completeness was worth isolating.

Intuition. A contraction is a map that shrinks every distance by at least a fixed factor. Photocopy a map of the room at 60% and drop it on the floor: exactly one point of the copy lies on top of the corresponding point of the room. Iterating the copy-and-drop shrinks the discrepancy by 40% each time, which is why the process converges geometrically and why it converges to the same place no matter where you start.

Definition 7.86 (Contraction). A map $T : X \to X$ on a metric space is a contraction with constant $q$ if there is $q \in [0, 1)$ with

d (T (x), T (y)) \leq q d (x, y) for all x, y \in X .

A point with $T (x) = x$ is a fixed point.

Proposition 7.87 (A contraction is uniformly continuous). Every contraction is uniformly continuous; indeed $δ = ε$ works for any $ε > 0$ .

Proof. If $d (x, y) < ε$ then $d (T x, T y) \leq q d (x, y) < qε \leq ε$ , since $q < 1$ . The choice of $δ$ did not depend on the point.∎

Theorem 7.88 (Banach fixed point theorem). Let $(X, d)$ be a non-empty complete metric space and $T : X \to X$ a contraction with constant $q < 1$ . Then $T$ has exactly one fixed point $x^{*}$ ; moreover, for any starting point $x_{0} \in X$ the iterates $x_{n + 1} = T (x_{n})$ converge to $x^{*}$ , with

d (x_{n}, x^{*}) \leq \frac{q ^{n}}{1 - q} d (x_{0}, x_{1}) and d (x_{n}, x^{*}) \leq \frac{q}{1 - q} d (x_{n - 1}, x_{n}) .

Three hypotheses, each indispensable, and each with a one-line counterexample. Completeness: $T (x) = x /2$ on $X = (0, 1]$ is a contraction with no fixed point, because the fixed point $0$ was removed. Strictness of $q < 1$ : the shift $T (x) = x + 1$ on $R$ satisfies $d (T x, T y) = d (x, y)$ exactly, and has no fixed point. Self-mapping: a contraction of $[0, 1]$ into $[2, 3]$ obviously fixes nothing, so $T$ must map $X$ into itself.

Pitfall. The condition $d (T x, T y) < d (x, y)$ for all $x \neq = y$ — strict but with no uniform $q$ — is not enough. On $X = [1, \infty)$ , complete, take $T (x) = x + 1/ x$ . Then $∣ T x - T y ∣ = ∣ x - y ∣ 1 - \frac{1}{x y} < ∣ x - y ∣$ for distinct $x, y \geq 1$ , yet $T (x) > x$ always, so there is no fixed point. What fails is uniformity: the effective factor $1 - 1/ (x y)$ approaches $1$ as $x, y$ grow, and no single $q < 1$ dominates it.

Exercises for §7.21 →

7.22Proof: existence, uniqueness and the rate

Proof. Uniqueness first, since it is one line and does not need completeness. If $T x^{*} = x^{*}$ and $T y^{*} = y^{*}$ then

d (x^{*}, y^{*}) = d (T x^{*}, T y^{*}) \leq q d (x^{*}, y^{*}),

so $(1 - q) d (x^{*}, y^{*}) \leq 0$ ; as $1 - q > 0$ this forces $d (x^{*}, y^{*}) = 0$ , hence $x^{*} = y^{*}$ .

The iterates contract geometrically. Fix $x_{0}$ and set $x_{n + 1} = T x_{n}$ . Applying the contraction property repeatedly,

d (x_{n}, x_{n + 1}) = d (T x_{n - 1}, T x_{n}) \leq q d (x_{n - 1}, x_{n}) \leq \dots \leq q^{n} d (x_{0}, x_{1}) .

The iterates are Cauchy. For $m > n$ , the triangle inequality along the chain $x_{n}, x_{n + 1}, \dots, x_{m}$ and the geometric bound give

d (x_{n}, x_{m}) \leq k = n \sum m - 1 d (x_{k}, x_{k + 1}) \leq d (x_{0}, x_{1}) k = n \sum m - 1 q^{k} \leq d (x_{0}, x_{1}) \frac{q ^{n}}{1 - q},

the last step summing the full geometric tail, which converges because $0 \leq q < 1$ . Since $q^{n} \to 0$ , the right-hand side is under any prescribed $ε$ for all large $n$ , uniformly in $m$ . So $(x_{n})$ is Cauchy.

Existence. By completeness $x_{n} \to x^{*}$ for some $x^{*} \in X$ . By the proposition A contraction is uniformly continuous and the theorem Sequential characterisation of continuity, $T x_{n} \to T x^{*}$ . But $T x_{n} = x_{n + 1}$ , a subsequence-shift of a sequence converging to $x^{*}$ , so $T x_{n} \to x^{*}$ as well. Limits are unique by the proposition Limits are unique, so $T x^{*} = x^{*}$ .

The rate. Let $m \to \infty$ in the Cauchy estimate with $n$ fixed. The left side tends to $d (x_{n}, x^{*})$ , because $d (x_{n}, \cdot)$ is continuous by the proposition Reverse triangle inequality, and the right side does not involve $m$ :

d (x_{n}, x^{*}) \leq \frac{q ^{n}}{1 - q} d (x_{0}, x_{1}) .

That is the a priori bound: before iterating at all, it says how many steps guarantee a given accuracy. Running the same argument from the starting point $x_{n - 1}$ instead of $x_{0}$ , so that the roles of $x_{0}, x_{1}$ are played by $x_{n - 1}, x_{n}$ and the index $n$ by $1$ , gives the a posteriori bound

d (x_{n}, x^{*}) \leq \frac{q}{1 - q} d (x_{n - 1}, x_{n}),

which uses the step actually just taken and is usually far sharper in practice.∎

Convergence at rate $q^{n}$ is linear (geometric): each iteration multiplies the error by roughly $q$ , so the number of correct digits grows linearly in $n$ , and the number of iterations needed for tolerance $ε$ is about $lo g (ε) / lo g (q)$ . Halving $q$ does not halve the work; it divides the iteration count by $lo g (1/ q)$ — which is why Newton's method, converging quadratically, is preferred when it is available, and why the contraction principle is valued for existence first and for computation second.

Figure 7.89. Cobweb iteration of

x_{n + 1} = cos (x_{n})

from

x_{0} = 0

. The iterates step between the curve and the line

y = x

, spiralling into the unique fixed point where the two meet.

Example 7.90 (Iterating to a prescribed tolerance). Let $T (x) = cos x$ on $X = [0, 1]$ . Verify the hypotheses, and use the a priori bound with $x_{0} = 0$ to find how many iterations guarantee an error below $1 0^{- 3}$ .

Solution.

$T$ maps $[0, 1]$ into $[cos 1, 1] \subseteq [0, 1]$ , and $[0, 1]$ is complete as a closed subset of $R$ , by the proposition Completeness passes to $R^{n}$ and to closed subsets.
By the mean value theorem, $∣ cos x - cos y ∣ = ∣ sin ξ ∣ ∣ x - y ∣$ for some $ξ$ between $x$ and $y$ , so on $[0, 1]$ the constant $q = sin 1 \approx 0.84147$ works.
With $x_{0} = 0$ , $x_{1} = cos 0 = 1$ , so $d (x_{0}, x_{1}) = 1$ and the a priori bound reads $d (x_{n}, x^{*}) \leq q^{n} / (1 - q) \approx 6.3080 q^{n}$ .
Solve $6.3080 q^{n} < 1 0^{- 3}$ : taking logarithms, $n > ln (6308.0) / ln (1/0.84147) = 8.7496/0.17260 \approx 50.69$ , so $n = 51$ suffices.
That is pessimistic, as a priori bounds always are — the true fixed point is $x^{*} \approx 0.739085$ and the iterates are within $1 0^{- 3}$ well before step $51$ — but it is a guarantee available before any computation is done, which is what an existence theorem is for.

□

Exercises for §7.22 →

7.23Applications: Picard–Lindelöf and others

The pattern is always the same: rewrite "solve this problem" as "find a fixed point of this map", choose a complete space in which the map contracts, and read off existence, uniqueness and an algorithm at once.

Theorem 7.91 (Picard–Lindelöf). Let $f (t, y)$ be continuous on the rectangle $R = [t_{0} - a, t_{0} + a] \times [y_{0} - b, y_{0} + b]$ , bounded there by $M$ , and Lipschitz in $y$ with constant $L$ . Then the initial value problem

y^{'} (t) = f (t, y (t)), y (t_{0}) = y_{0},

has a unique solution on $[t_{0} - h, t_{0} + h]$ for any $h$ with $h \leq a$ , $M h \leq b$ and $L h < 1$ .

Proof. By the fundamental theorem of calculus, a continuous $y$ solves the initial value problem on $I = [t_{0} - h, t_{0} + h]$ if and only if it satisfies the integral equation

y (t) = y_{0} + \int_{t_{0}}^{t} f (s, y (s)) d s .

Let $X = {y \in C (I) : ∥ y - y_{0} ∥_{\infty} \leq b}$ , a closed subset of $C (I)$ with the sup metric, hence complete by the theorem $C [0, 1]$ with the sup metric is complete and the proposition Completeness passes to $R^{n}$ and to closed subsets. Define $(T y) (t)$ to be the right-hand side above.

$T$ maps $X$ into $X$ : $∣ (T y) (t) - y_{0} ∣ \leq \int ∣ f ∣ \leq M ∣ t - t_{0} ∣ \leq M h \leq b$ , and $T y$ is continuous, indeed differentiable.

$T$ contracts: for $y, z \in X$ and $t \in I$ ,

(T y) (t) - (T z) (t) \leq \int_{t_{0}}^{t} f (s, y (s)) - f (s, z (s)) d s \leq L ∣ t - t_{0} ∣ ∥ y - z ∥_{\infty} \leq L h ∥ y - z ∥_{\infty} .

Taking the supremum over $t$ gives $d_{\infty} (T y, T z) \leq L h d_{\infty} (y, z)$ with $L h < 1$ .

The theorem Banach fixed point theorem now supplies a unique $y \in X$ with $T y = y$ , which is the unique solution.∎

The iterates $y_{n + 1} = T y_{n}$ starting from the constant function $y_{0}$ are the Picard iterates, and the fixed point theorem's rate estimate says they converge uniformly at the geometric rate $(L h)^{n}$ . Note also what the hypotheses buy: continuity of $f$ alone gives existence but not uniqueness — $y^{'} = y^{2/3}$ , $y (0) = 0$ has both $y \equiv 0$ and $y = t^{3} /27$ — and the Lipschitz condition is exactly what the contraction step needed.

Example 7.92 (Two more fixed-point arguments). (a) Solve $x = \frac{1}{4} (x + 3)$ by iteration from $x_{0} = 0$ and state the contraction constant. (b) Show that the linear system $x = A x + b$ has a unique solution whenever some induced matrix norm satisfies $∥ A ∥ < 1$ .

Solution.

(a) $T (x) = \frac{1}{4} x + \frac{3}{4}$ satisfies $∣ T x - T y ∣ = \frac{1}{4} ∣ x - y ∣$ , so $q = \frac{1}{4}$ on the complete space $R$ . The fixed point solves $x = \frac{1}{4} x + \frac{3}{4}$ , i.e. $\frac{3}{4} x = \frac{3}{4}$ , so $x^{*} = 1$ . Iterating from $0$ : $0.75, 0.9375, 0.984375, \dots$ , with error $4^{- n}$ .
(b) $T (x) = A x + b$ on $R^{n}$ , complete, satisfies $∥ T x - T y ∥ = ∥ A (x - y) ∥ \leq ∥ A ∥ ∥ x - y ∥$ , a contraction with $q = ∥ A ∥ < 1$ . So the fixed point exists and is unique, which says $(I - A) x = b$ is uniquely solvable, and the iteration $x_{k + 1} = A x_{k} + b$ converges — this is the Jacobi and Gauss–Seidel family of numerical methods, and $∥ A ∥ < 1$ is their convergence criterion.
Both instances show the division of labour: the algebra identifies $T$ , the metric space supplies completeness, and the theorem does the rest without any further thought.

□

Exercises for §7.23 →

7.25The Baire category theorem: two forms

Theorem 7.96 (Baire category theorem). Let $(X, d)$ be a non-empty complete metric space.

(Dense open form) If ${U_{n}}_{n \geq 1}$ are open and dense in $X$ , then $⋂_{n} U_{n}$ is dense in $X$ .
(Closed cover form) If $X = ⋃_{n} F_{n}$ with each $F_{n}$ closed, then some $F_{n}$ has non-empty interior.

Proposition 7.97 (The two forms are equivalent). Statements (1) and (2) above imply one another.

Proof. (1) $\Rightarrow$ (2): given closed $F_{n}$ covering $X$ , suppose every $F_{n}^{\circ} = \emptyset$ . Then $U_{n} = X ∖ F_{n}$ is open, and it is dense because its closure is $X ∖ F_{n}^{\circ} = X$ by the proposition Duality of interior and closure. By (1) the intersection $⋂ U_{n} = X ∖ ⋃ F_{n}$ is dense, in particular non-empty — contradicting that the $F_{n}$ cover $X$ .

(2) $\Rightarrow$ (1): let $U_{n}$ be open dense and let $B$ be any ball; we must show $B$ meets $⋂ U_{n}$ . The closed ball $\overset{ˉ}{B}^{'} \subseteq B$ of half the radius is complete, being closed in $X$ . If $\overset{ˉ}{B}^{'}$ missed $⋂ U_{n}$ then $\overset{ˉ}{B}^{'} = ⋃_{n} (\overset{ˉ}{B}^{'} ∖ U_{n})$ , a countable union of closed sets, each with empty interior because $U_{n}$ is dense. By (2) applied in the complete space $\overset{ˉ}{B}^{'}$ , that is impossible.∎

Form (2) is the one that sounds like a theorem about size: a complete space is "thick", and cannot be exhausted by countably many "thin" closed pieces. Form (1) is the one that is used: it says a countable list of generic conditions can be imposed simultaneously and still leave points satisfying all of them.

Exercises for §7.25 →

7.26Proof by nested balls

Proof. We prove form (1). Let ${U_{n}}$ be open and dense in the complete space $X$ , and let $W$ be an arbitrary non-empty open set; it suffices to produce a point of $W \cap ⋂_{n} U_{n}$ .

Step 1: start. $U_{1}$ is dense, so $U_{1} \cap W \neq = \emptyset$ , and it is open, so it contains a closed ball $\overset{ˉ}{B} (x_{1}, r_{1})$ with $0 < r_{1} < 1$ . (Choose an open ball inside the open set, then shrink its radius by half to get a closed ball inside.)

Step 2: descend. Suppose $\overset{ˉ}{B} (x_{n}, r_{n})$ has been chosen. Since $U_{n + 1}$ is dense and $B (x_{n}, r_{n})$ is open and non-empty, the set $U_{n + 1} \cap B (x_{n}, r_{n})$ is non-empty and open, so it contains a closed ball $\overset{ˉ}{B} (x_{n + 1}, r_{n + 1})$ with

0 < r_{n + 1} < \frac{1}{2} r_{n} .

This gives nested closed balls $\overset{ˉ}{B} (x_{1}, r_{1}) \supseteq \overset{ˉ}{B} (x_{2}, r_{2}) \supseteq \dots$ with $r_{n} < 2^{- (n - 1)} \to 0$ , and $\overset{ˉ}{B} (x_{n}, r_{n}) \subseteq U_{n}$ for every $n$ , and $\overset{ˉ}{B} (x_{1}, r_{1}) \subseteq W$ .

Step 3: the centres are Cauchy. For $m > n$ the point $x_{m}$ lies in $\overset{ˉ}{B} (x_{n}, r_{n})$ , so $d (x_{n}, x_{m}) \leq r_{n} < 2^{- (n - 1)}$ , which is under any $ε$ for large $n$ uniformly in $m$ .

Step 4: collect the limit. By completeness $x_{n} \to x$ for some $x \in X$ . Fix $n$ : all terms $x_{m}$ with $m \geq n$ lie in the closed set $\overset{ˉ}{B} (x_{n}, r_{n})$ , so the limit does too, by the theorem Sequential characterisation of closed sets. Hence

x \in n \geq 1 ⋂ \overset{ˉ}{B} (x_{n}, r_{n}) \subseteq W \cap n \geq 1 ⋂ U_{n} .

So every non-empty open $W$ meets $⋂ U_{n}$ , which is the definition of density.∎

Two details are load-bearing and are exactly where a careless version of this proof fails. The balls must be closed, so that Step 4 can capture the limit; nested open balls can have empty intersection even in $R$ . And the radii must be forced to zero, which is what makes the centres Cauchy — nested closed balls with radii bounded below can also have empty intersection in a general complete space, so neither condition is decorative.

Example 7.98 (Where the proof breaks without completeness). Run the construction in $X = Q$ with $U_{n} = Q ∖ {q_{n}}$ for an enumeration $(q_{n})$ of $Q$ , and locate the failure.

Solution.

Each $U_{n}$ is open in $Q$ , its complement being a single point, and dense, since removing one rational leaves the rest dense.
But $⋂_{n} U_{n} = Q ∖ {q_{1}, q_{2}, \dots} = \emptyset$ , which is not dense. So the conclusion of the theorem is false in $Q$ .
Tracing the proof: Steps 1–3 go through verbatim and produce a Cauchy sequence of centres with radii tending to zero. Step 4 is the one that fails — the limit exists in $R$ but is irrational, hence is not a point of $X$ .
This is the same missing point as in every other failure of completeness in this chapter, and it confirms that the Baire category theorem is a theorem about completeness and nothing else.

□

Exercises for §7.26 →

7.27Meagre, comeagre, and "generic"

Definition 7.99 (Meagre and comeagre). $A \subseteq X$ is meagre (of the first category) if it is a countable union of nowhere dense sets, and comeagre (residual) if its complement is meagre. A property is said to hold generically if the set of points where it holds is comeagre.

Proposition 7.100 (Baire, restated in this language). In a non-empty complete metric space, a comeagre set is dense; in particular $X$ is not meagre in itself, and a countable intersection of comeagre sets is comeagre.

Proof. Let $X ∖ A = ⋃_{n} N_{n}$ with each $N_{n}$ nowhere dense. Then $U_{n} = X ∖ \overset{ˉ}{N}_{n}$ is open, and dense because $\overset{ˉ}{U}_{n} = X ∖ (\overset{ˉ}{N}_{n})^{\circ} = X$ by the proposition Duality of interior and closure. Since $A \supseteq ⋂_{n} U_{n}$ , the theorem Baire category theorem makes $A$ dense. If $X$ were meagre in itself, $\emptyset$ would be comeagre and hence dense, which is false as $X \neq = \emptyset$ . The last claim holds because a countable union of countably many nowhere dense families is again countable.∎

Pitfall. Meagre is a topological smallness, not a measure-theoretic one, and the two are genuinely different — see the closing section. Also, meagre is not "small" in any everyday sense until completeness is assumed: every space is meagre in some superspace, and $Q$ is meagre in itself, which says nothing about $Q$ being small inside $R$ .

Example 7.101 (Comeagre sets in $R$ ). Show that the irrationals are comeagre in $R$ , and that the set of $x$ with unbounded partial quotients in its continued fraction is comeagre.

Solution.

$Q = ⋃_{n} {q_{n}}$ is a countable union of singletons, each closed with empty interior in $R$ , hence meagre. So $R ∖ Q$ is comeagre, and by the proposition Baire, restated in this language it is dense — which we knew, but now with the extra information that it is "generic".
For the second, let $A_{N}$ be the set of irrationals all of whose partial quotients are at most $N$ . Each $A_{N}$ is closed in the irrationals and has empty interior, since inside any interval one can choose a continued fraction with a large partial quotient. So $⋃_{N} A_{N}$ is meagre and its complement is comeagre.
The pattern is the one used throughout: to prove a property generic, write its failure set as a countable union of closed sets, then show each is nowhere dense by finding a nearby point with the property inside every ball.

□

Exercises for §7.27 →

7.28Applications: existence proofs for objects nobody constructs

Theorem 7.102 (Generic nowhere differentiability). In $C [0, 1]$ with the sup metric, the set of functions that are differentiable at at least one point is meagre. Hence a generic continuous function is differentiable nowhere, and in particular such functions exist.

Proof. For $n \in N$ let

E_{n} = {f \in C [0, 1] : \exists t \in [0, 1] with ∣ f (t + h) - f (t) ∣ \leq n ∣ h ∣ for all admissible h} .

If $f$ is differentiable at some $t$ , the difference quotients are bounded near $t$ and $f$ is bounded, so $f \in E_{n}$ for some $n$ ; thus the differentiable-somewhere functions lie in $⋃_{n} E_{n}$ .

$E_{n}$ is closed. Let $f_{k} \in E_{n}$ with witnesses $t_{k}$ and $f_{k} \to f$ uniformly. By compactness of $[0, 1]$ pass to a subsequence with $t_{k} \to t$ . The inequality $∣ f_{k} (t_{k} + h) - f_{k} (t_{k}) ∣ \leq n ∣ h ∣$ passes to the limit, uniform convergence and continuity of $f$ letting both arguments move, so $f \in E_{n}$ .

$E_{n}$ has empty interior. Given $f \in C [0, 1]$ and $ε > 0$ , the Weierstrass approximation theorem supplies a polynomial $p$ with $d_{\infty} (f, p) < ε /2$ . Let $g = p + \frac{ε}{2} ϕ$ , where $ϕ$ is a sawtooth of amplitude $1$ whose linear pieces have slope $\pm s$ with $s$ chosen so large that $\frac{ε}{2} s > n + max ∣ p^{'} ∣$ . Then $d_{\infty} (f, g) < ε$ while every difference quotient of $g$ over a short interval exceeds $n$ in absolute value, so $g \in / E_{n}$ . Hence every ball meets the complement of $E_{n}$ .

So each $E_{n}$ is closed and nowhere dense, $⋃ E_{n}$ is meagre, and $C [0, 1]$ is complete by the theorem $C [0, 1]$ with the sup metric is complete. The theorem Baire category theorem gives a comeagre, hence non-empty, set of nowhere differentiable functions.∎

Read what that argument did and did not do. It proves that nowhere differentiable continuous functions exist — indeed that they are the overwhelming majority — without exhibiting a single one. Weierstrass's explicit $\sum 2^{- n} cos (3^{n} π x)$ came first historically and is much harder; the category argument is three paragraphs and gives a stronger conclusion.

Corollary 7.103 (Generic transcendence, and a second application). The transcendental numbers are comeagre in $R$ , and a generic $x \in R$ is a Liouville number.

Proof. The algebraic numbers are countable, by Cardinality and Countability, so they form a countable union of singletons — closed with empty interior — and are therefore meagre. Their complement is comeagre. For the second claim, the Liouville numbers are $⋂_{n} ⋃_{p / q} (\frac{p}{q} - q^{- n}, \frac{p}{q} + q^{- n})$ , a countable intersection of open sets each dense because it contains all rationals' neighbourhoods; the theorem Baire category theorem makes the intersection comeagre.∎

Example 7.104 (Uniform boundedness from category). Let $F$ be a family of continuous functions on a complete space $X$ with $sup_{f \in F} ∣ f (x) ∣ < \infty$ for each $x$ . Show $F$ is uniformly bounded on some ball.

Solution.

Put $F_{n} = {x \in X : ∣ f (x) ∣ \leq n for all f \in F} = ⋂_{f \in F} f^{- 1} ([- n, n])$ , an intersection of closed sets, hence closed by the proposition De Morgan for closed sets.
The pointwise bound says every $x$ lies in some $F_{n}$ , so $X = ⋃_{n} F_{n}$ .
By form (2) of the theorem Baire category theorem, some $F_{N}$ has non-empty interior, so it contains a ball $B (x_{0}, r)$ .
On that ball every $f \in F$ is bounded by $N$ : a uniform bound extracted from purely pointwise hypotheses. This is the uniform boundedness principle of functional analysis, and category is its entire content.

□

Exercises for §7.28 →

7.29Category versus measure

Meagre sets and null sets are both notions of "negligible", and they share the formal properties: each is closed under subsets and countable unions, and each excludes the whole space when the space is $R$ . It is tempting to conclude they are two names for one idea. They are not, and the following example settles it.

Theorem 7.105 ( $R$ splits into a meagre set and a null set). There is a decomposition $R = M \cup N$ with $M$ meagre and $N$ of Lebesgue measure zero, and $M \cap N = \emptyset$ .

Proof. Enumerate the rationals as $(q_{k})$ . For each $n$ , let

U_{n} = k = 1 ⋃ \infty (q_{k} - \frac{1}{2 ^{k + n}}, q_{k} + \frac{1}{2 ^{k + n}}),

an open set containing $Q$ , hence dense, of Lebesgue measure at most $\sum_{k} 2^{- k - n + 1} = 2^{1 - n}$ .

Put $N = ⋂_{n} U_{n}$ . It is null, since its measure is at most $2^{1 - n}$ for every $n$ . And $M = R ∖ N = ⋃_{n} (R ∖ U_{n})$ is a countable union of closed sets, each with empty interior because $U_{n}$ is dense; so $M$ is meagre. The two are complementary by construction.∎

So $R$ is the union of a set that is topologically negligible and a set that is measure-theoretically negligible. Neither notion implies the other: $N$ is null but comeagre, $M$ is meagre but of full measure. A property that holds generically may fail almost everywhere, and conversely.

Remark. The two notions do share a great deal of structure — Oxtoby's classical treatment develops them in parallel columns, and there is a duality principle exchanging theorems about category for theorems about measure in a wide class of statements. The practical advice is simply to say which one is meant. "Almost every real number is normal" is a measure statement and true; "a generic real number is not normal" is a category statement and also true, because the non-normal numbers are comeagre. Both are correct, and reading either as the other is wrong.

Example 7.106 (Which notion of small?). Classify each subset of $R$ as meagre or not, and null or not: (a) $Q$ ; (b) the Cantor set $C$ ; (c) a fat Cantor set of measure $\frac{1}{2}$ ; (d) the set $N$ of the theorem above.

Solution.

(a) $Q$ is meagre, as a countable union of singletons, and null, as a countable set. Both notions agree here, which is why countable sets give no insight into the difference.
(b) $C$ is closed with empty interior — it contains no interval, since at stage $n$ it is covered by $2^{n}$ intervals of length $3^{- n}$ — so it is nowhere dense, hence meagre; and it is null, of measure $lim (2/3)^{n} = 0$ . Uncountable, and small in both senses.
(c) A fat Cantor set is nowhere dense by the same argument, hence meagre, but has measure $\frac{1}{2}$ and so is not null. Meagre does not imply null.
(d) $N$ is null but comeagre, hence very far from meagre. Null does not imply meagre. Parts (c) and (d) together show the two notions are logically independent.

□

Exercises for §7.29 →

Common Mistakes

Treating "closed and bounded" as the definition of compact. It is a theorem, Heine–Borel, and it is a theorem about $R^{n}$ only. In a general metric space the correct equivalent is complete and totally bounded, and an infinite discrete space is the standing counterexample.
Assuming $\overline{B (x, r)} = \overset{ˉ}{B} (x, r)$ . True in $R^{n}$ , false in general; in the discrete metric the closure of $B (x, 1) = {x}$ is ${x}$ while $\overset{ˉ}{B} (x, 1)$ is everything.
Intersecting infinitely many open sets and expecting an open set. $⋂_{n} (- 1/ n, 1/ n) = {0}$ . The finiteness in The open sets form a topology is where the minimum of the radii is guaranteed positive.
Saying a set is "not open, therefore closed". $[0, 1)$ is neither; $\emptyset$ and $X$ are both; in a discrete space everything is both.
Forgetting that openness and closedness are relative to the ambient space. $[0, 1)$ is open in $[0, 1]$ and not in $R$ . Always name the space.
Proving compactness by exhibiting one cover with a finite subcover. The definition quantifies over every cover; one cover proves nothing. To disprove compactness, one bad cover does suffice.
Applying the Banach fixed point theorem without checking that $T$ maps $X$ into $X$ , or that $X$ is complete. $T (x) = x /2$ on $(0, 1]$ contracts and has no fixed point.
Using $d (T x, T y) < d (x, y)$ in place of a uniform $q < 1$ . On $[1, \infty)$ , $T (x) = x + 1/ x$ satisfies the strict inequality everywhere and has no fixed point. The uniform constant is what makes the geometric series converge.
Confusing completeness with closedness. Completeness is a property of a space in its own right; a subset is complete exactly when it is closed in a complete ambient space. And completeness is not topological: $(0, 1)$ and $R$ are homeomorphic, but only one is complete in its usual metric.
Assuming connected implies path-connected. The topologist's sine curve is connected and not path-connected. The implication does hold for open subsets of $R^{n}$ .
Reading "meagre" as "measure zero". They are logically independent: a fat Cantor set is meagre and not null, and $R$ splits into a meagre set and a null set.
Quoting a result by number. Every statement in this chapter has a title; the numbers are computed at render time and shift when anything is inserted.

About the practice questions. They check that you can carry out this chapter's computations correctly, and each one is graded on a single answer. They are not proof exercises: working through them confirms the mechanics, not that you could prove the results yourself. For that, re-read the statements above and try to reconstruct their proofs with the page closed.

Practice this chapter

Introduction

7.1Metrics: the axioms and what they already force

7.2Balls, and the topology they generate

7.3Convergence, continuity and Cauchy sequences

7.4Equivalent metrics and the discrete metric

7.5Open sets: the three axioms they satisfy

7.6Closed sets and the sequential test

7.7Closure, interior and boundary

7.8Limit points, isolated points, dense sets

7.9Compactness by open covers

7.10The Heine–Borel theorem in Rn

7.11Sequential compactness and total boundedness

7.12What compactness buys

7.13Completeness: definition and examples

7.14Banach spaces

7.15Completion of a metric space

7.16Baire category: a first look

7.17Connectedness

7.18Connected subsets of R are exactly the intervals

7.19Path-connectedness, and why it is strictly stronger

7.20Components and quasicomponents

7.21The contraction mapping principle: statement

7.22Proof: existence, uniqueness and the rate

7.23Applications: Picard–Lindelöf and others

7.24Weakening the hypotheses, and partial converses

7.25The Baire category theorem: two forms

7.26Proof by nested balls

7.27Meagre, comeagre, and "generic"

7.28Applications: existence proofs for objects nobody constructs

7.29Category versus measure

7.10The Heine–Borel theorem in $R^{n}$

7.18Connected subsets of $R$ are exactly the intervals