4.3 Compactness

A set is compact when every sequence in it has a subsequence converging inside it, or equivalently when every cover by open sets can be trimmed to finitely many. In R^n that means closed and bounded (Heine–Borel), in function spaces it does not, and compactness is exactly what makes continuous functions attain extremes and have one delta for the whole set.

In 1.3 two theorems were proved on the interval $[a, b]$ : a continuous function attains a maximum, and it is uniformly continuous. Both proofs went through the same step, Bolzano–Weierstrass: take a sequence of points of $[a, b]$ , extract a convergent subsequence, and observe that its limit is still in $[a, b]$ . The interval $(0, 1]$ fails this ( $\frac1n$ has no limit in the set) and so do both theorems. So the interval was not the point. The property that a set must have so that sequences have a limit inside it is called compactness. This chapter defines it for any metric space, in two ways that look different (subsequences, and covers by open sets), proves they agree, proves that in $\mathbb R^n$ it means closed and bounded, shows that this fails in spaces of functions, and then proves the two theorems of 1.3 again for every compact set.

Before you start

1.2: subsequences and the Bolzano–Weierstrass theorem. 4.2: convergence in a metric space, and that a set is closed iff it contains limits of its convergent sequences. 1.3: the extreme value theorem.

Quick checkThe sequence

1, -1, 1, -1, \dots

is bounded. Which is true?

Quick checkIs

(0, 1]

a closed subset of

\mathbb R

Quick checkDoes

f(x) = x

attain a maximum on the interval

(0, 1)

The picture: covers and finite subcovers

A cover of a set $K$ is a family of open sets whose union contains $K$ . In the picture the sets are open intervals drawn as blue bars, and $K$ is the black line. Slide $k$ to use only the first $k$ intervals and watch the uncovered points (red). Three things to do:

Start with $(0, 1]$ and the intervals $(\frac1n, 2)$ . Every point of $K$ is covered if you use all of them (given $x > 0$ pick $n$ with $\frac1n < x$ ). But for every $k$ there is a red gap $(0, \frac1k]$ . No finite part of the cover works.
Switch to $[0, 1]$ with the same intervals plus one around $0$ . Now the point $0$ is covered by the new interval, and the red gap disappears when $k$ reaches $12$ (the new set and $U_1, \dots, U_{11}$ ). Of those twelve, two already suffice: the new one and $(\frac1{11}, 2)$ .
Try the hand-made family. It is finite, so a finite subcover is automatic. The interesting case is an infinite family, and the claim of compactness is that for $[0, 1]$ some finite part of it always works.

Where this came from· Heine, Borel and a disputed name

Dirichlet was the first to prove that a continuous function on a closed interval is uniformly continuous. His proof, given in lectures in 1852 and published only in 1904, quietly used a finite subcover of an open cover. Heine, Weierstrass and Pincherle later used similar techniques, which is why Heine’s name is attached to the theorem even though his own result was about uniform continuity. Émile Borel stated and proved, in 1895, that any cover of a closed interval by countably many open intervals has a finite subcover. Pierre Cousin (1895), Henri Lebesgue (1898) and Arthur Schoenflies (1900) extended this to arbitrary covers, and the result is sometimes called the Borel–Lebesgue lemma. The problem they were solving was how to pass from “every point has a good neighbourhood” to “the whole set has a uniform bound”. A finite cover does that, because you can take a minimum of finitely many numbers. (The history here follows Raman-Sundström, “A Pedagogical History of Compactness”, American Mathematical Monthly, 2015.)

Where this came from· Fréchet and the two definitions

Maurice Fréchet’s 1906 thesis (the same one that began metric spaces, see 4.1) studied sets in which every sequence has a convergent subsequence, generalizing Bolzano–Weierstrass from the line to spaces of functions. The open-cover definition, which is the one topology uses, was formulated in the 1920s by Pavel Alexandroff and Pavel Urysohn (who called it “bicompact”). For metric spaces the two are equivalent, which is Theorem “Compact equals sequentially compact” below. In general topological spaces they differ, and the cover definition is the one that works.

The idea, in words

Why· Compact means: it behaves like a finite set

Finite sets are friendly. Every function on a finite set has a largest value. If every point has its own tolerance $\delta_p > 0$ , then there is one tolerance for the whole set, the smallest $\delta_p$ , and it is positive because a minimum of finitely many positive numbers is positive. Infinite sets lose both properties.

Compactness is the way an infinite set earns them back. It says the set can be handled by finitely many pieces at the scale you care about, whichever scale that is. Two statements express it:

Sequences. An infinite supply of points must pile up somewhere in the set: some subsequence converges to a point of the set. (A finite set has this, since some point repeats infinitely often.)
Covers. If every point of the set is given an open neighbourhood, finitely many of those neighbourhoods already cover the set. This is “take the minimum of finitely many tolerances” in disguise.

The set must be closed (no escape through an edge) and “not too spread out” (the interval $[0, 1]$ yes, the line $\mathbb R$ no). In $\mathbb R^n$ that is closed and bounded. In infinite dimensions “not too spread out” needs a sharper meaning, called total boundedness.

Definitions and theorems

Sequential compactness

Definition B

Sequentially compact

Let $K$ be a subset of a metric space $X$ . $K$ is sequentially compact if for every sequence $(x_n)$ with all $x_n \in K$ there are indices $n_1 < n_2 < \cdots$ and a point $x \in K$ with $x_{n_k} \to x$ . (The limit must be in $K$ .)

In one lineA set $K$ is sequentially compact if every sequence of points of $K$ has a subsequence that converges to a point of $K$ .

Why it existsIt is the property that Bolzano–Weierstrass gives for $[a, b]$ and that the proofs of the extreme value theorem and of uniform continuity in 1.3 used.

We use the following fact all the time: if $x_n \to x$ then every subsequence $x_{n_k} \to x$ too, because $n_k \ge k$ , so the terms after index $N$ of the subsequence are terms of the original after index $N$ .

Worked example

Which of these subsets of

\mathbb R

are sequentially compact:

[0, 1]

(0, 1]

\mathbb R

\{1, 2, 3\}

\mathbb Q \cap [0, 1]

\mathbb Z

Solution.

$[0, 1]$ is. A sequence in $[0, 1]$ is bounded, so Bolzano–Weierstrass gives a convergent subsequence, and $0 \le x_{n_k} \le 1$ passes to the limit, so the limit is in $[0, 1]$ . Boundedness gives the subsequence, closedness keeps the limit inside.
$(0, 1]$ is not. The sequence $\frac1n$ has every subsequence converging to $0$ , which is outside. One sequence all of whose subsequences fail is enough to disprove the property.
$\mathbb R$ is not. The sequence $x_n = n$ has no convergent subsequence, since a convergent sequence is bounded and every subsequence of $n$ is unbounded. Bounded fails.
$\{1, 2, 3\}$ is. Any sequence takes some value infinitely often; the subsequence at those positions is constant, hence convergent. Finite sets are always sequentially compact.
$\mathbb Q \cap [0, 1]$ is not. Take rationals $x_n \to \frac{\sqrt2}2$ (decimal truncations). Every subsequence converges to $\frac{\sqrt2}2$ , which is irrational, so outside the set. The set is bounded but not closed in $\mathbb R$ : it has holes.
$\mathbb Z$ is not. The sequence $n$ again. Unbounded.

Answer. Sequentially compact: $[0, 1]$ and $\{1, 2, 3\}$ . Not: the other four. $\blacksquare$ The pattern, closed and bounded, is the next theorem.

Definition B

Bounded set in a metric space

A subset $K$ of a metric space $X$ is bounded if there exist $p \in X$ and $R > 0$ with $d(x, p) < R$ for all $x \in K$ . (For $\mathbb R$ with $|x - y|$ this is the notion of bounded from 1.1.)

In one lineA set $K$ is bounded if it fits inside some ball: there are a point $p$ and a radius $R$ with $K \subseteq B(p, R)$ .

Why it existsIt is the replacement for 'between two numbers' in a space with no order, and it is the condition that fails for $\mathbb R$ and for $\mathbb Z$ .

Theorem B Rudin Thm 2.34 and Thm 3.6; Abbott Sec. 3.3

Sequentially compact sets are closed and bounded

If $K$ is a sequentially compact subset of a metric space $X$ , then $K$ is closed and bounded.

In one lineIn any metric space, a sequentially compact set is closed and bounded.

Why it is trueA sequence escaping through a missing limit point, or running off to infinity, has no subsequence that converges inside the set.

ProofRudin 2.34

The idea: Closed: a sequence in K converging to a point outside K would force all its subsequences to converge outside K. Bounded: an unbounded set yields a sequence moving ever farther from a base point, which cannot have a convergent subsequence.

Closed. Let

x_n \in K

and

x_n \to x \in X

. We show

x \in K

By the theorem in 4.2, a set is closed iff the limit of every convergent sequence of its points lies in the set. So take such a sequence.

Some subsequence

x_{n_k}

converges to a point

y \in K

K

is sequentially compact.

But

x_{n_k} \to x

as well, so

y = x

and

x \in K

. So

K

is closed.

A subsequence of a sequence converging to

x

also converges to

x

, and limits in a metric space are unique (4.2).

For each

n

choose

x_n \in K

with

d(x_n, p) \ge n

Bounded: suppose not. Fix any

p \in X

. Not bounded means no ball

B(p, n)

contains

K

, for every

n

Suppose a subsequence converges to

y \in K

. Then

d(x_{n_k}, p)

is bounded.

A sequence

x_{n_k} \to y

is bounded:

d(x_{n_k}, p) \le d(x_{n_k}, y) + d(y, p)

, and

d(x_{n_k}, y) < 1

for large

k

, so the distances stay below

1 + d(y, p)

after some point.

That contradicts the choice of

x_n

. So no subsequence converges, which contradicts sequential compactness. Hence

K

is bounded.

\blacksquare

d(x_{n_k}, p) \ge n_k \ge k

is unbounded.

For the converse we need a statement about boxes. A box in $\mathbb R^n$ is $Q = [a_1, b_1] \times \cdots \times [a_n, b_n]$ . Every bounded set lies in some box.

Theorem B Rudin Thm 2.41 and Thm 3.6; Abbott Sec. 3.3

Bolzano–Weierstrass in R^n

Let $K \subseteq \mathbb R^n$ be closed and bounded (for any of the 1-, 2- or max-distances). Then $K$ is sequentially compact.

In one lineEvery closed bounded subset of $\mathbb R^n$ is sequentially compact: each sequence in it has a subsequence converging to a point of it.

Why it is truePass to a subsequence for the first coordinate, then a further subsequence for the second, and so on; after $n$ rounds every coordinate converges.

ProofRudin 2.41

The idea: Bounded in R^n means each coordinate is a bounded real sequence. Apply Bolzano–Weierstrass of 1.2 one coordinate at a time, always to the subsequence already found. Then the vector converges, because convergence is coordinatewise (4.2). The limit is in K since K is closed.

Let

x^{(m)}

be a sequence in

K

. Each coordinate sequence

(x^{(m)}_i)_m

lies in

[-R, R]

K

is bounded, so

\lVert x \rVert_2 \le R

for some

R

and all

x \in K

. Each coordinate is at most the 2-norm in absolute value (the comparison theorem of 4.1).

There is a subsequence along which the first coordinate converges.

Bolzano–Weierstrass in 1.2, for the first coordinate.

Take a further subsequence along which the second coordinate also converges. Continue through coordinate

n

A subsequence of a bounded sequence is bounded, so Bolzano–Weierstrass applies again, now to the second coordinate along the subsequence from the previous step. The first coordinate still converges along it, since subsequences of convergent sequences converge.

So some subsequence converges to a point

x \in \mathbb R^n

After

n

steps we have one subsequence

x^{(m_k)}

along which every coordinate converges. By the coordinatewise theorem of 4.2,

x^{(m_k)} \to x

\mathbb R^n

x \in K

\blacksquare

K

is closed, so by 4.2 the limit of a convergent sequence of its points lies in

K

Quick checkWhich of these subsets of

\mathbb R^2

is sequentially compact?

Open covers and compactness

Definition B

Open cover

Let $K$ be a subset of a metric space $X$ . An open cover of $K$ is a collection $\{U_\alpha\}$ of open sets of $X$ with $K \subseteq \bigcup_\alpha U_\alpha$ . A subcover is a sub-collection that still covers $K$ ; it is a finite subcover if it has finitely many sets.

In one lineAn open cover of a set $K$ is a collection of open sets of the space whose union contains $K$ . A finite subcover is a finite part of the collection that still covers $K$ .

Why it existsA cover is the data 'give every point an open neighbourhood'. Compactness asks that finitely many of those neighbourhoods are enough.

Definition B

Compact set

A subset $K$ of a metric space $X$ is compact if every open cover of $K$ has a finite subcover.

In one lineA set $K$ is compact if every open cover of $K$ has a finite subcover.

Why it existsIt is the cover version of 'behaves like a finite set': finitely many of any given neighbourhoods already reach every point.

One remark about the definition. If we asked for covers by sets open in $K$ itself (as in 4.4), we would get the same notion: a set open in $K$ has the form $K \cap W$ with $W$ open in $X$ (the lemma “Open sets inside a subset” in 4.4), and covers by the $K \cap W_\alpha$ correspond to covers by the $W_\alpha$ . So being compact is a property of $K$ as a metric space on its own. That lets us treat $K$ as the whole space in proofs.

Worked example

Show that

(0, 1]

is not compact by giving an open cover with no finite subcover. Then show

[0, 1]

is not defeated by the same family.

Solution.

The cover. Let $U_n = (\frac1n, 2)$ for $n = 1, 2, 3, \dots$ . Each is open. Open intervals are balls in $\mathbb R$ .
It covers $(0, 1]$ . Given $x \in (0, 1]$ , pick $n$ with $\frac1n < x$ (Archimedean property). Then $x \in U_n$ , as $x \le 1 < 2$ . Every point needs a set containing it.
No finite subcover. Any finitely many $U_{n_1}, \dots, U_{n_j}$ have union $U_N$ with $N = \max n_i$ (the sets increase with $n$ ), which is $(\frac1N, 2)$ . It misses the point $\frac1N \in (0, 1]$ . The sets are nested, so the union of finitely many is the biggest of them, and that one has a left end.
So $(0, 1]$ is not compact. Compactness requires a finite subcover for EVERY open cover. One bad cover is enough.
The same family on $[0, 1]$ . It does not cover $[0, 1]$ (the point $0$ is in no $U_n$ ), so add $U_0 = (-\varepsilon, \varepsilon)$ with $\varepsilon = 0.05$ . The sets $U_0$ and $U_N$ cover $[0, 1]$ once $\frac1N < \varepsilon$ , that is $N \ge 21$ . Points below $\varepsilon$ are in $U_0$ ; points from $\varepsilon$ up are above $\frac1N$ and below $2$ . For $N = 20$ , $\frac1{20} = 0.05$ exactly, and the point $0.05$ is in neither set.

Answer. $(0, 1]$ has the open cover $\{(\frac1n, 2)\}$ with no finite subcover, so it is not compact. Adding the one set $U_0$ around the missing point makes two sets suffice for $[0, 1]$ , and compactness says that something like this always happens for $[0, 1]$ . $\blacksquare$

Your answerCover

[0, 1]

U_0 = (-0.05, 0.05)

together with

U_n = (\frac1n, 2)

. What is the smallest

n

such that

\{U_0, U_n\}

already covers

[0, 1]

Worked example

Prove directly from the definition that

K = \{0\} \cup \{\frac1n : n \ge 1\}

is compact.

Solution.

Start with an arbitrary open cover. Let $\{U_\alpha\}$ be a family of open sets of $\mathbb R$ whose union contains $K$ . The definition says every open cover has a finite subcover, so we may not choose the cover. We are handed it.
Handle the troublemaker $0$ . Some member, call it $U_0$ , contains the point $0$ . It is open, so it contains an interval $(-r, r)$ for some $r > 0$ . Open means a ball around each of its points fits inside.
See what $U_0$ covers. Choose $N$ with $\frac1N < r$ (Archimedean property). Then $\frac1n \in (-r, r) \subseteq U_0$ for every $n \ge N$ . The tail of the sequence $\frac1n$ is squeezed toward $0$ , so all of it is swallowed by the one set around $0$ . Infinitely many points are handled by a single set.
Handle the finitely many points left over. The points $1, \frac12, \dots, \frac1{N-1}$ number finitely many. For each, pick one member of the cover containing it. One set per point, and there are only $N - 1$ points, so this uses at most $N - 1$ more sets.
Collect. $U_0$ together with those at most $N - 1$ sets is a finite subfamily, and it covers $K$ . It contains $0$ , the tail, and each leftover point.

Answer. Every open cover of $K$ has a finite subcover, so $K$ is compact. This is the standard shape of a direct proof: one set handles the accumulation point and an infinite tail, finitely many sets handle the rest. Compare $\{\frac1n\}$ without $0$ , where nothing handles the tail. $\blacksquare$

Two general facts, true in every metric space.

Theorem B Rudin Thm 2.34; Abbott Sec. 3.3

Compact sets are closed and bounded

If $K$ is a compact subset of a metric space $X$ , then $K$ is closed and bounded.

In one lineIn any metric space, every compact set is closed and bounded.

Why it is trueCover the set by balls that grow, or by the sets of points farther than $1/n$ from a point outside the set; a finite subcover forces a gap around that outside point.

ProofRudin 2.34

The idea: Bounded: the balls B(p, n) cover everything; finitely many suffice, so the biggest contains K. Closed: for a point q outside K, the open sets {x : d(x, q) > 1/n} cover K; a finite subcover gives a ball around q that misses K.

Bounded. By compactness finitely many of these balls cover

K

For any fixed

p \in X

the open balls

B(p, n)

n = 1, 2, \dots

, cover all of

X

, so cover

K

K \subseteq B(p, N)

for some

N

K

is bounded.

The balls increase with

n

, so the union of finitely many is the largest of them.

Closed. Let

q \in X \setminus K

and

U_n = \{x \in X : d(x, q) > \frac1n\}

To show

K

is closed we show its complement is open: take a point

q \notin K

and find a ball around

q

that misses

K

Each

U_n

is open.

d(x, q) > \frac1n

put

s = d(x, q) - \frac1n

. For

y \in B(x, s)

the triangle inequality gives

d(y, q) \ge d(x, q) - d(x, y) > \frac1n

The sets

U_n

cover

K

x \in K

then

x \ne q

, so

d(x, q) > 0

by (M1), and

d(x, q) > \frac1n

for

n

large.

K \subseteq U_N

: every point of

K

is farther than

\frac1N

from

q

Compactness gives a finite subcover. The sets increase with

n

, so one set

U_N

already contains

K

Hence

B(q, \frac1N) \subseteq X \setminus K

, so

X \setminus K

is open and

K

is closed.

\blacksquare

That says no point of

K

is in

B(q, \frac1N)

Lemma B Rudin Thm 2.35

Closed subsets of compact sets are compact

Let $Q$ be a compact subset of a metric space $X$ , and let $F \subseteq Q$ be closed in $X$ . Then $F$ is compact.

In one lineIf $Q$ is compact and $F \subseteq Q$ is closed, then $F$ is compact.

Why it is trueCover $F$ and also the complement of $F$ , which is open; the finite subcover of $Q$ restricts to a finite subcover of $F$ .

ProofRudin 2.35

The idea: Given an open cover of F, add the open set X minus F. The result covers Q, so finitely many of its sets cover Q; drop X minus F.

Let

\{U_\alpha\}

be an open cover of

F

Start with an arbitrary open cover of

F

Then

\{U_\alpha\} \cup \{X \setminus F\}

is an open cover of

Q

F

is closed, so

X \setminus F

is open. Every point of

Q

is in

F

(so in some

U_\alpha

) or not in

F

(so in

X \setminus F

A finite part of it covers

Q

, hence covers

F

Q

is compact.

Remove

X \setminus F

if it is among the sets. What remains is finitely many

U_\alpha

covering

F

\blacksquare

X \setminus F

contains no point of

F

, so it is not needed to cover

F

The Heine–Borel theorem

Theorem B Rudin Thm 2.40 and 2.41; Abbott Sec. 3.3

Heine–Borel theorem

A subset $K \subseteq \mathbb R^n$ (with the 1-, 2- or max-distance) is compact if and only if it is closed and bounded.

In one lineA subset of $\mathbb R^n$ is compact if and only if it is closed and bounded.

Why it is true'Compact implies closed and bounded' holds in every metric space. For the converse, keep halving a box that has no finite subcover; the nested boxes shrink to a point, and the open set covering that point also covers a small box, a contradiction.

Why· The picture behind the proof

Imagine the box $Q$ and an open cover of it with no finite subcover. Cut $Q$ into $2^n$ equal sub-boxes (in the plane, four quarters). If each quarter had a finite subcover, so would $Q$ . So some quarter has none. Cut that quarter into four, and again some quarter has none. The nested squares shrink to a single point $x$ . That point is in one set $U$ of the cover. Because $U$ is open, a small disc around $x$ fits in $U$ , and when the squares are small enough one of them fits inside this disc. That square is covered by the single set $U$ . It was supposed to have no finite subcover. In the cover visualizer above this is the situation near $0$ for $(0, 1]$ : the nested intervals shrink toward a point which is not in the set, so the argument has nothing to land on. Closedness is what lets the point exist.

ProofRudin 2.40 and 2.41

The idea: (⇒) is the general theorem. (⇐) First prove that every box is compact by the halving argument; then a closed bounded set is a closed subset of a box, hence compact.

(

\Rightarrow

) A compact

K

is closed and bounded.

The general theorem that compact sets are closed and bounded, in the metric space

\mathbb R^n

Halve every side of

Q_0

. This cuts

Q_0

into

2^n

sub-boxes whose union is

Q_0

(

\Leftarrow

), part 1: boxes are compact. By contradiction: suppose a box

Q_0

has an open cover

\mathcal U

with no finite subcover.

So at least one sub-box has no finite subcover. Call it

Q_1

If all

2^n

sub-boxes had a finite subcover from

\mathcal U

, the union of those finitely many finite subcovers would be a finite subcover of

Q_0

We get nested boxes

Q_0 \supseteq Q_1 \supseteq Q_2 \supseteq \cdots

, none having a finite subcover from

\mathcal U

, with

\operatorname{diam} Q_k = 2^{-k} \operatorname{diam} Q_0

The same argument applied to

Q_1

, then

Q_2

, and so on (we choose one each time, an infinite repeated choice).

Pick

x_k \in Q_k

for each

k

. The sequence

(x_k)

is Cauchy.

For

m \ge k

both

x_k

and

x_m

lie in

Q_k

(the boxes are nested), so

d(x_k, x_m) \le \operatorname{diam} Q_k \to 0

x_k \to x

for some

x \in \mathbb R^n

\mathbb R^n

is complete (4.2).

Hence

x \in Q_k

for every

k

, in particular

x \in Q_0

For a fixed

k

, the points

x_m

with

m \ge k

lie in

Q_k

and converge to

x

. A box is closed (its defining inequalities pass to limits coordinatewise), so

x \in Q_k

Some

U \in \mathcal U

contains

x

\mathcal U

covers

Q_0

There is

r > 0

with

B(x, r) \subseteq U

U

is open.

Then

Q_k \subseteq B(x, r) \subseteq U

: the single set

U

is a finite subcover of

Q_k

. This contradicts the choice of

Q_k

. So every box is compact.

Choose

k

with

\operatorname{diam} Q_k < r

. Every point

y \in Q_k

has

d(y, x) \le \operatorname{diam} Q_k < r

since

x \in Q_k

too.

Let

K

be closed and bounded. Then

K \subseteq [-R, R]^n

, a box.

(

\Leftarrow

), part 2: a closed bounded set sits inside a box. If

\lVert x \rVert_2 \le R

K

then every coordinate is in

[-R, R]

K

is a closed subset of a compact box, so

K

is compact.

\blacksquare

The lemma on closed subsets of compact sets.

Proof workshopRebuild the halving argument: every box is compact

Tap the lines in the order a proof would write them. Each line can only use what is already above it.

Worked example

Which of these subsets of

\mathbb R^2

\mathbb R^3

are compact: the closed triangle

\{x, y \ge 0,\ x + y \le 1\}

, the sphere

\{x^2 + y^2 + z^2 = 1\}

, the hyperbola

\{xy = 1\}

, the open disc

\{x^2 + y^2 < 1\}

, the set

\{(x, y) : y = \sin\frac1x,\ 0 < x \le 1\}

Solution.

Closed triangle. Defined by non-strict inequalities of continuous functions, so closed. It lies in $[0, 1]^2$ , so bounded. By Heine–Borel it is compact. A set defined by $\ge$ , $\le$ and $=$ on continuous functions is closed: limits of points satisfying them still satisfy them.
Sphere. Closed because $x_k \to x$ with $\lVert x_k \rVert_2 = 1$ forces $\lVert x \rVert_2 = 1$ (the norm is continuous: $|\lVert x_k \rVert - \lVert x \rVert| \le \lVert x_k - x \rVert$ , the reverse triangle inequality). Bounded since every coordinate has absolute value at most $1$ . Compact. This sphere is the set where continuous-function arguments will find maxima and minima; it is used again in 4.5.
Hyperbola $xy = 1$ . Closed (an equation in continuous functions) but unbounded, since $(n, \frac1n)$ lies on it. Not compact. Heine–Borel needs both properties.
Open disc. Bounded, not closed (the boundary circle is missing). Not compact. The sequence $(1 - \frac1n, 0)$ approaches a point outside the set.
The graph of $\sin\frac1x$ on $(0, 1]$ . Bounded, but not closed: $(\frac{1}{n\pi}, 0)$ lies on it and tends to $(0, 0)$ , which is not on it. Not compact. This is the set $G$ of the topologist’s sine curve in 4.4; adding the missing segment makes it closed, bounded and compact.

Answer. Compact: the triangle and the sphere. Not compact: the other three. $\blacksquare$

Compact and sequentially compact are the same in a metric space

In $\mathbb R^n$ we proved that closed and bounded gives sequential compactness and also gives compactness. In a general metric space the two properties still agree, which we now prove. The proof needs a measure of “how finely do I need to look”. It is called total boundedness.

Definition B

Totally bounded

A metric space $K$ (or a subset with the inherited distance) is totally bounded if for every $\varepsilon > 0$ there are finitely many points $p_1, \dots, p_m \in K$ with $K = B(p_1, \varepsilon) \cup \dots \cup B(p_m, \varepsilon)$ .

In one lineA metric space is totally bounded if for every $\varepsilon > 0$ it can be covered by finitely many balls of radius $\varepsilon$ .

Why it existsBounded says one big ball is enough. Totally bounded says finitely many small balls are enough at every scale, which is the property 'not too spread out' that compactness needs.

A totally bounded set is bounded: take $\varepsilon = 1$ , then one big ball around $p_1$ of radius $1 + \max_i d(p_1, p_i)$ contains all the small ones. The converse fails: the closed unit ball of an infinite-dimensional space is bounded but, as we show, not totally bounded. Boundedness in $\mathbb R^n$ does imply total boundedness (cut a box into small cubes).

Lemma B standard; Munkres Thm 45.1

Sequentially compact implies totally bounded

If a metric space $K$ is sequentially compact, then it is totally bounded.

In one lineA sequentially compact metric space can be covered by finitely many balls of any given radius.

Why it is trueIf it could not, you could pick points one after another, each at distance at least $\varepsilon$ from all earlier ones, and that sequence has no Cauchy subsequence.

Proofstandard

The idea: Suppose some radius ε is not enough. Pick points greedily, each outside the balls of the earlier ones. All pairs are at least ε apart, so no subsequence is Cauchy, hence none converges.

Pick any

x_1 \in K

Contrapositive. Suppose, for some

\varepsilon > 0

, no finite set of balls of radius

\varepsilon

covers

K

Pick

x_2 \in K \setminus B(x_1, \varepsilon)

B(x_1, \varepsilon)

alone does not cover

K

by the assumption.

Having chosen

x_1, \dots, x_j

, pick

x_{j+1} \in K \setminus \bigl(B(x_1, \varepsilon) \cup \dots \cup B(x_j, \varepsilon)\bigr)

Finitely many balls never cover

K

, so there is always a point outside

B(x_1, \varepsilon) \cup \dots \cup B(x_j, \varepsilon)

Then

d(x_i, x_j) \ge \varepsilon

for all

i \ne j

Each point is outside the earlier balls, so its distance to each earlier point is at least

\varepsilon

So no subsequence of

(x_j)

converges, contradicting sequential compactness.

\blacksquare

A convergent sequence is Cauchy (4.2). A subsequence with all pairwise distances at least

\varepsilon

is not Cauchy for the tolerance

\varepsilon

The next lemma gives the one tolerance that works for a whole cover.

Lemma B Munkres Lemma 27.5

Lebesgue number lemma

Let $K$ be a sequentially compact metric space and $\{U_\alpha\}$ a cover of $K$ by open sets of $K$ . Then there is $\lambda > 0$ (a Lebesgue number of the cover) such that for every $x \in K$ the ball $B(x, \lambda)$ is contained in some $U_\alpha$ .

In one lineIf $K$ is sequentially compact and $\{U_\alpha\}$ is an open cover of $K$ , there is a number $\lambda > 0$ such that every ball $B(x, \lambda)$ with $x \in K$ lies inside a single $U_\alpha$ .

Why it is trueIf no such $\lambda$ existed, there would be points whose $\frac1n$ -balls escape every set; a subsequence of them converges to a point of some $U_\alpha$ , and the balls around it eventually fit inside that set.

ProofMunkres 27.5

The idea: Contradiction: for λ = 1/n pick a bad centre x_n. A convergent subsequence tends to a point x lying in some U; a ball around x fits inside U, and for large k the bad ball around x_{n_k} fits inside it too.

For each

n

choose

x_n \in K

such that

B(x_n, \frac1n)

is contained in no

U_\alpha

Assume the opposite: for every

\lambda > 0

there is a centre whose

\lambda

-ball fits in no

U_\alpha

. Use

\lambda = \frac1n

A subsequence

x_{n_k} \to x

for some

x \in K

K

is sequentially compact.

Some

U_\beta

contains

x

, and

B(x, r) \subseteq U_\beta

for some

r > 0

\{U_\alpha\}

covers

K

and each

U_\alpha

is open.

Choose

k

with

d(x_{n_k}, x) < \frac r2

and

\frac1{n_k} < \frac r2

Convergence

x_{n_k} \to x

and

\frac1{n_k} \to 0

: both are below

\frac r2

for large

k

y \in B(x_{n_k}, \frac1{n_k})

then

y \in B(x, r) \subseteq U_\beta

Triangle inequality:

d(y, x) \le d(y, x_{n_k}) + d(x_{n_k}, x) < \frac r2 + \frac r2 = r

B(x_{n_k}, \frac1{n_k}) \subseteq U_\beta

, a contradiction.

\blacksquare

That is exactly what we assumed was impossible for the centre

x_{n_k}

Theorem B Rudin Thm 2.37 and 3.6; Munkres Thm 28.2

Compact equals sequentially compact

A subset $K$ of a metric space is compact if and only if it is sequentially compact.

In one lineIn a metric space, a set is compact if and only if it is sequentially compact.

Why it is trueCompact to sequential: a sequence with no convergent subsequence gives each point a ball containing only finitely many terms, and finitely many such balls cannot hold infinitely many terms. Sequential to compact: totally bounded gives finitely many balls of radius equal to a Lebesgue number, and each of those balls sits inside one set of the cover.

ProofMunkres 28.2

The idea: (⇒) Contrapositive with balls that catch only finitely many terms. (⇐) Take a Lebesgue number λ, cover K by finitely many λ-balls using total boundedness, and put each ball inside one set of the cover.

Let

p \in K

. If every ball

B(p, \frac1j)

contained

x_n

for infinitely many

n

, we could pick

n_1 < n_2 < \cdots

with

x_{n_j} \in B(p, \frac1j)

(

\Rightarrow

) Suppose

K

is compact and

(x_n)

is a sequence in

K

with no subsequence converging to a point of

K

Then

x_{n_j} \to p

, contrary to the assumption. So some ball

B(p, r_p)

contains

x_n

for only finitely many indices

n

That subsequence has

d(x_{n_j}, p) < \frac1j \to 0

Say

B(p_1, r_{p_1}), \dots, B(p_m, r_{p_m})

cover

K

The balls

B(p, r_p)

for

p \in K

are open and cover

K

. By compactness finitely many of them cover

K

But there are infinitely many indices

n

, a contradiction. So every sequence in

K

has a subsequence converging in

K

K

is sequentially compact.

Every

x_n

lies in

K

, so in one of these

m

balls, and each ball holds

x_n

for only finitely many

n

. Finitely many balls, each with finitely many indices, give finitely many indices in total.

By the Lebesgue number lemma there is

\lambda > 0

such that every ball

B(x, \lambda)

x \in K

, lies in some

U_\alpha

(

\Leftarrow

) Suppose

K

is sequentially compact, and let

\{U_\alpha\}

be an open cover of

K

(by open sets of

K

, equivalent to the definition, by the remark above).

There are

p_1, \dots, p_m \in K

with

K = B(p_1, \lambda) \cup \dots \cup B(p_m, \lambda)

Sequentially compact implies totally bounded. Take

\varepsilon = \lambda

For each

i

choose

\alpha_i

with

B(p_i, \lambda) \subseteq U_{\alpha_i}

Each centre

p_i

is a point of

K

, so the Lebesgue property applies to the ball around it.

Then

K \subseteq U_{\alpha_1} \cup \dots \cup U_{\alpha_m}

: a finite subcover. So

K

is compact.

\blacksquare

The balls cover

K

and each lies in its set.

Proof workshopPick the reason for each line of 'sequentially compact implies compact'

Each line of the proof is shown in order. Choose the reason that justifies it, then press Check.

Let $\{U_\alpha\}$ be an open cover of the sequentially compact set $K$ .
There is $\lambda > 0$ such that every ball $B(x, \lambda)$ lies in a single $U_\alpha$ .
There are $p_1, \dots, p_m \in K$ whose $\lambda$ -balls cover $K$ .
For each $i$ , $B(p_i, \lambda) \subseteq U_{\alpha_i}$ for some $\alpha_i$ .
So $K \subseteq U_{\alpha_1} \cup \dots \cup U_{\alpha_m}$ .

In the picture: the Lebesgue number is the width of the narrowest “room” a point has inside the sets of the cover. For $[0, 1]$ with the family $\{U_0, U_n\}$ of the first visualizer (where $U_0 = (-0.1, 0.1)$ ) the room is at least $0.05$ everywhere: a point $x$ with $0 \le x \le 0.1$ has room $0.1 - x$ inside $U_0$ and nearly $x$ inside some $U_n$ , and the worse of the two bests, at $x = 0.05$ , is $0.05$ . For $(0, 1]$ with $(\frac1n, 2)$ the room of the point $x$ is about $x$ , which tends to $0$ as $x \to 0$ : there is no Lebesgue number, and no finite subcover.

Quick checkWhich of these metric spaces (with the distance

|x - y|

) is totally bounded?

Worked example

How many open intervals of length

0.1

are needed to cover

[0, 1]

Solution.

Eleven are enough. Take the intervals of radius $0.05$ around the centres $c_j = 0.04 + 0.095\,j$ for $j = 0, 1, \dots, 10$ . The first reaches down to $c_0 - 0.05 = -0.01 < 0$ , the last up to $c_{10} + 0.05 = 1.04 > 1$ , and neighbouring centres are $0.095 < 0.1$ apart, so neighbouring intervals overlap. Two open intervals of length $0.1$ overlap exactly when their centres are less than $0.1$ apart, and overlapping intervals leave no point between them uncovered.
Ten are not enough. Suppose ten open intervals of length $0.1$ cover $[0, 1]$ . Their union $U$ is open and contains $0$ and $1$ , so it contains small intervals around both, and so contains an interval $(-\eta, 1 + \eta)$ of length $1 + 2\eta > 1$ . But the total length of ten intervals of length $0.1$ is $1$ , and a union of intervals cannot contain an interval longer than the sum of their lengths. Open intervals cannot touch end to end: the touching point would be missing. Overlap costs length, and there is no spare length. This is the same reason that $[0, 1]$ cannot be split into open pieces (4.4).
Conclude. The least number is $11$ . This is a count of the balls in a finite cover at scale $\varepsilon = 0.05$ , which is what total boundedness asks for at each scale.

Answer. $11$ . $\blacksquare$

Your answerWhat is the least number of open intervals of length

0.1

that cover

[0, 1]

Theorem B Munkres Thm 45.1

Compact equals complete and totally bounded

A metric space $K$ is compact if and only if it is complete and totally bounded.

In one lineA metric space is compact if and only if it is complete and totally bounded.

Why it is trueCompact means every sequence has a convergent subsequence. A Cauchy sequence with a convergent subsequence converges, so compact spaces are complete. Conversely, total boundedness lets you pick a nested sequence of small balls, which yields a Cauchy subsequence that completeness converts into a limit.

ProofMunkres 45.1

The idea: (⇒) Sequentially compact implies totally bounded, and a Cauchy sequence with a convergent subsequence converges. (⇐) From any sequence, use total boundedness repeatedly to pick nested infinite subsequences, each inside a ball of radius 1/k; the diagonal subsequence is Cauchy.

(

\Rightarrow

)

K

is totally bounded.

By the equivalence theorem, compact means sequentially compact. The lemma above gives totally bounded.

A Cauchy sequence in

K

has a convergent subsequence, hence converges to the same limit. So

K

is complete.

Let

(x_n)

be Cauchy with a subsequence

x_{n_k} \to x

. Given

\varepsilon

, choose

N

with

d(x_m, x_n) < \frac\varepsilon2

for

m, n > N

and

k

with

n_k > N

and

d(x_{n_k}, x) < \frac\varepsilon2

. For

n > N

d(x_n, x) \le d(x_n, x_{n_k}) + d(x_{n_k}, x) < \varepsilon

One of those balls contains

x_n

for infinitely many

n

. Let

S_1

be the subsequence of those terms.

(

\Leftarrow

) Let

K

be complete and totally bounded, and

(x_n)

any sequence. Finitely many balls of radius

1

cover

K

Let

S_2 \subseteq S_1

be the terms lying in one ball of radius

\frac12

. Continue:

S_k \subseteq S_{k-1}

lies in a ball of radius

\frac1k

Finitely many balls of radius

\frac12

cover

K

, hence cover the terms of

S_1

; by the same pigeonhole one of them contains infinitely many terms of

S_1

The sequence

(y_k)

is a subsequence of

(x_n)

and is Cauchy.

The diagonal: let

y_k

be the

k

-th term of

S_k

, chosen with strictly increasing original indices. For

m \ge k

both

y_k

and

y_m

lie in

S_k

, inside one ball of radius

\frac1k

, so

d(y_k, y_m) < \frac2k

by the triangle inequality.

y_k

converges in

K

. Every sequence has a convergent subsequence:

K

is sequentially compact, hence compact.

\blacksquare

K

is complete.

Worked example

Decide whether each metric space is complete, totally bounded and compact: (a)

[0, 1]

, (b)

(0, 1)

, (c)

\mathbb Z

, all with the distance

|x - y|

, and (d) an infinite set with the discrete metric.

Solution.

(a) $[0, 1]$ . It is closed in the complete space $\mathbb R$ , so it is complete. Intervals of radius $\varepsilon$ around $0, \varepsilon, 2\varepsilon, \dots$ (about $\frac1\varepsilon$ of them) cover it, so it is totally bounded. Hence compact. The theorem: compact means complete and totally bounded.
(b) $(0, 1)$ . Totally bounded, by the same count of intervals. Not complete: $\frac1n$ is Cauchy and has no limit in $(0, 1)$ . So not compact. One of the two properties is missing. Totally bounded alone is not enough.
(c) $\mathbb Z$ . Complete: a Cauchy sequence of integers is eventually constant, because after some point the terms are less than $\frac12$ apart, hence equal. Not totally bounded: balls of radius $\frac12$ are single points, and $\mathbb Z$ is infinite. So not compact. Here the missing property is total boundedness.
(d) A discrete infinite set. Complete for the same reason as $\mathbb Z$ (a Cauchy sequence is eventually constant), and not totally bounded for the same reason (balls of radius $\frac12$ are single points). So not compact. The sets $\{x\}$ are open and cover the space, and no finite part does, which is the cover form of the same failure.

Answer. Only $[0, 1]$ is compact. (b) fails completeness; (c) and (d) fail total boundedness. $\blacksquare$

This is why $\mathbb R^n$ obeys Heine–Borel. A closed subset of $\mathbb R^n$ is complete (4.2), and a bounded subset of $\mathbb R^n$ is totally bounded, so a closed bounded set is complete and totally bounded. It also explains the failure below: the closed unit ball of a function space is complete and bounded, and not totally bounded.

Closed and bounded is not enough in function spaces

Proposition B standard

The unit ball of C[0,1] is closed and bounded but not compact

Let $B = \{f \in C[0, 1] : d_\infty(f, 0) \le 1\}$ be the closed unit ball of $C[0, 1]$ with the sup metric. Then $B$ is closed and bounded, but not compact.

In one lineIn $C[0, 1]$ with the sup metric, the closed unit ball $\{f : \max|f| \le 1\}$ is closed and bounded and has a sequence with no convergent subsequence, so it is not compact.

Why it is trueTent functions with disjoint supports are all at distance exactly 1 from each other, so no subsequence is Cauchy, let alone convergent.

Proofstandard

The idea: Build functions f_n that are zero except on disjoint little intervals, with a peak of height 1 on each. Any two are at sup distance exactly 1, so no subsequence is Cauchy.

B

is bounded and closed.

The ball

B(0, 2)

contains it. Closed: it is a closed ball, and closed balls are closed (the problem at the end of 4.1; the complement is open by the triangle inequality argument).

Let

c_n = \frac12(\frac1n + \frac1{n+1})

h_n = \frac12(\frac1n - \frac1{n+1})

and

f_n(x) = \max\bigl(0, 1 - |x - c_n|/h_n\bigr)

Tent of height

1

and half-width

h_n

, centred at the midpoint

c_n

of the interval

[\frac1{n+1}, \frac1n]

. For

n = 1

the interval is

[\frac12, 1]

and the centre is

\frac34

For

n \ne m

the functions

f_n

and

f_m

are never non-zero at the same point.

Each

f_n

is continuous with values in

[0, 1]

, so

f_n \in B

. It is non-zero only on the open interval

(\frac1{n+1}, \frac1n)

, and these open intervals are pairwise disjoint.

Hence

d_\infty(f_n, f_m) = 1

for all

n \ne m

x = c_n

f_n(c_n) = 1

and

f_m(c_n) = 0

. Everywhere else at most one of them is non-zero, and values lie in

[0, 1]

, so

|f_n - f_m| \le 1

No subsequence of

(f_n)

converges. So

B

is not sequentially compact, hence not compact.

\blacksquare

A convergent sequence is Cauchy (4.2). A subsequence of

(f_n)

has all pairwise distances equal to

1

, so for

\varepsilon = \frac12

it is not Cauchy.

The unit ball here is closed, bounded and even complete (4.2 shows $C[0, 1]$ is complete and the ball is a closed subset). What fails is total boundedness: no finite set of functions is within $\frac12$ of all the tents. The space has infinitely many independent directions, the way $\mathbb R^n$ has $n$ , and a ball in each direction is needed.

Quick checkThe closed unit ball of

C[0, 1]

with the sup metric is closed, bounded and complete. Why is it not compact?

A computation in this space, to get used to the sup metric:

Your answerIn

C[0, 1]

with the sup metric, what is

d_\infty(x^n, x^{2n})

for any

n \ge 1

? (Hint: the gap is

x^n - x^{2n}

; put

u = x^n

Compactness at work

A few statements about continuous maps before the three theorems. A map $f : X \to Y$ between metric spaces is continuous at $a$ if for every $\varepsilon > 0$ there is $\delta > 0$ with $d_Y(f(x), f(a)) < \varepsilon$ whenever $d_X(x, a) < \delta$ (the definition of 1.3 with two distances; 4.5 names and studies it).

Lemma B Abbott Thm 4.3.2; Rudin Thm 4.2

Continuous maps send convergent sequences to convergent sequences

Let $f : X \to Y$ be continuous at $a$ and $x_n \to a$ in $X$ . Then $f(x_n) \to f(a)$ in $Y$ .

In one lineIf $f$ is continuous at $a$ and $x_n \to a$ , then $f(x_n) \to f(a)$ .

Why it is trueContinuity turns the target tolerance into an input tolerance, and convergence of $x_n$ makes the inputs fall inside it eventually.

ProofAbbott 4.3.2

The idea: The same two-step proof as the sequential criterion in 1.3, with distances.

Let

\varepsilon > 0

Arbitrary output tolerance.

Choose

\delta > 0

with

d_Y(f(x), f(a)) < \varepsilon

whenever

d_X(x, a) < \delta

Continuity of

f

a

Choose

N

with

d_X(x_n, a) < \delta

for

n > N

x_n \to a

with tolerance

\delta

For

n > N

d_Y(f(x_n), f(a)) < \varepsilon

\blacksquare

Combine the two choices.

Theorem B Rudin Thm 4.14; Abbott Thm 4.4.1

Continuous image of a compact set is compact

If $K$ is a compact metric space and $f : K \to Y$ is continuous, then $f(K)$ is a compact subset of $Y$ .

In one lineIf $K$ is compact and $f : K \to Y$ is continuous, then $f(K)$ is compact.

Why it is trueA sequence in the image comes from a sequence in $K$ ; a convergent subsequence there is carried by continuity to a convergent subsequence of the image.

ProofRudin 4.14

The idea: Use sequential compactness on both ends: lift a sequence of the image to K, extract a convergent subsequence there, and push it forward.

Let

(y_n)

be a sequence in

f(K)

. Each

y_n = f(x_n)

for some

x_n \in K

By the equivalence theorem, compact means sequentially compact, so we may check that.

Some subsequence

x_{n_k} \to x \in K

K

is sequentially compact.

y_{n_k} = f(x_{n_k}) \to f(x)

, and

f(x) \in f(K)

The lemma on convergent sequences.

f(K)

is sequentially compact, hence compact.

\blacksquare

Every sequence in

f(K)

has a subsequence converging in

f(K)

Theorem B Rudin Thm 4.16; Abbott Thm 4.4.2; Apostol Sec. 9.9

Extreme value theorem on a compact set

Let $K$ be a non-empty compact metric space and $f : K \to \mathbb R$ continuous. Then there are $c, d \in K$ with $f(c) \le f(x) \le f(d)$ for all $x \in K$ .

In one lineA continuous real function on a non-empty compact set attains a maximum and a minimum.

Why it is trueThe image is a compact subset of the line, so closed and bounded; a non-empty closed bounded set of reals contains its supremum and infimum.

ProofRudin 4.16

The idea: f(K) is compact in R, so bounded; its supremum M exists; M is a limit of values of f, and a closed set contains its limits, so M is a value.

f(K)

is a compact subset of

\mathbb R

The theorem on continuous images.

f(K)

is closed and bounded, and non-empty.

Compact sets are closed and bounded.

Let

M = \sup f(K)

Bounded above and non-empty, so the supremum exists (completeness axiom, 1.1).

There are

y_n \in f(K)

with

M - \frac1n < y_n \le M

, so

y_n \to M

Approximation property of the supremum: for each

n

there is a value within

\frac1n

M

M \in f(K)

M = f(d)

for some

d \in K

A closed set contains the limit of every convergent sequence of its points (4.2).

Hence

f(d)

is the maximum and a minimum

f(c)

exists.

\blacksquare

The same argument for

-f

gives the minimum.

This is the extreme value theorem of 1.3, with the interval $[a, b]$ replaced by any compact metric space. Its three ingredients are the three facts proved above: the image is compact, compact sets of $\mathbb R$ are closed and bounded, and closed sets contain their supremum.

Worked example

Show that

f(x, y) = x + 2y

attains a maximum on the circle

x^2 + y^2 = 1

, and find it.

Solution.

The circle is compact. It is closed (the sphere argument above) and bounded, so compact by Heine–Borel. Heine–Borel in $\mathbb R^2$ .
$f$ is continuous. It is a sum of coordinate functions with constant factors; $|f(p) - f(q)| \le |p_1 - q_1| + 2|p_2 - q_2| \le 3 \lVert p - q \rVert_2$ . The inequality gives $\delta = \varepsilon/3$ .
So a maximum exists. By the extreme value theorem on a compact set. It does not tell where; it promises that a search for the maximum has a target.
Find it. By Cauchy–Schwarz (2.9), $x + 2y = (x, y) \cdot (1, 2) \le \lVert (x, y) \rVert\,\lVert (1, 2) \rVert = \sqrt5$ , with equality when $(x, y)$ is parallel to $(1, 2)$ : $(x, y) = \frac1{\sqrt5}(1, 2)$ . Equality in Cauchy–Schwarz holds for parallel vectors, and this point is on the circle.

Answer. The maximum is $\sqrt5 \approx 2.236$ , attained at $(\frac1{\sqrt5}, \frac2{\sqrt5})$ . $\blacksquare$

Your answerWhat is the maximum value of

x + 2y

on the circle

x^2 + y^2 = 1

Theorem B Rudin Thm 4.19; Abbott Thm 4.4.7

Continuous on a compact set implies uniformly continuous

Let $K$ be a compact metric space and $f : K \to Y$ continuous. Then for every $\varepsilon > 0$ there is $\delta > 0$ with $d_Y(f(x), f(y)) < \varepsilon$ whenever $d_K(x, y) < \delta$ . (This is uniform continuity as defined in 1.3, with the two distances.)

In one lineA continuous map from a compact metric space to any metric space is uniformly continuous: one $\delta$ works for the whole set.

Why it is trueEvery point has its own tolerance; the Lebesgue number of the cover by those tolerance-balls is a single tolerance that serves everywhere.

ProofRudin 4.19

The idea: Give each point p the δ_p that works for ε/2 at p. The balls B(p, δ_p) cover K. A Lebesgue number λ of this cover is the δ: two points within λ of each other lie in one ball B(p, δ_p), so their images are both within ε/2 of f(p).

Let

\varepsilon > 0

. For each

p \in K

choose

\delta_p > 0

with

d_Y(f(x), f(p)) < \frac\varepsilon2

whenever

d_K(x, p) < \delta_p

Arbitrary tolerance. For each point we use continuity with half of it, to get two images close through a common centre.

The balls

B(p, \delta_p)

p \in K

, form an open cover of

K

Each point

p

lies in its own ball.

Let

\lambda > 0

be a Lebesgue number: every ball

B(x, \lambda)

lies in some

B(p, \delta_p)

K

is compact, hence sequentially compact; the Lebesgue number lemma applies.

d_Y(f(x), f(p)) < \frac\varepsilon2

and

d_Y(f(y), f(p)) < \frac\varepsilon2

Take

\delta = \lambda

. Let

d_K(x, y) < \lambda

, so

y \in B(x, \lambda)

. Choose

p

with

B(x, \lambda) \subseteq B(p, \delta_p)

. Then both

x

and

y

are within

\delta_p

p

d_Y(f(x), f(y)) \le d_Y(f(x), f(p)) + d_Y(f(p), f(y)) < \varepsilon

\blacksquare

Triangle inequality in

Y

, through

f(p)

The proof in 1.3 used sequences instead, and found a convergent subsequence of “bad pairs”. The Lebesgue number is the same device: in the picture it is the minimum of the infinitely many local tolerances, and compactness keeps that minimum positive.

Worked example

For

f(x) = x^2

[0, 3]

and

\varepsilon = 0.03

, find a

\delta

that works at every point at once.

Solution.

The set is compact. $[0, 3]$ is closed and bounded. Heine–Borel, so the theorem promises a uniform $\delta$ exists.
Find the size of the slope. For $x, y \in [0, 3]$ , $|x^2 - y^2| = |x - y|\,|x + y| \le 6\,|x - y|$ . $|x + y| \le 6$ on $[0, 3]$ , the bound on how steep the graph can get.
Choose $\delta$ . We want $6\delta \le \varepsilon = 0.03$ , so $\delta = 0.005 = \frac1{200}$ . Then $|x - y| < \delta$ implies $|x^2 - y^2| < 6\delta = 0.03$ for every pair of points in the interval.

Answer. $\delta = \frac1{200}$ works everywhere on $[0, 3]$ . On $\mathbb R$ no such $\delta$ exists (1.3). $\blacksquare$

Your answerFor

f(x) = x^2

[0, 3]

the bound

|x^2 - y^2| \le 6|x - y|

holds. For

\varepsilon = 0.03

, what is

\delta = \varepsilon / 6

Quick checkWhich of these functions is uniformly continuous on its domain?

Where it is used

Used inside maths· Inside maths: why the earlier chapters worked, and what comes next

Every proof in 1.3 that said “take a convergent subsequence” was using compactness of $[a, b]$ . Chapter 1.5 needs uniform continuity to show that a continuous function is integrable; that is the compact-set theorem above. In 4.5 the compactness of the unit sphere of $\mathbb R^n$ proves that all norms on $\mathbb R^n$ are equivalent, the fact that 4.1 stated without proof. In Unit 5, a function of several variables on a closed bounded region has a maximum and a minimum by the theorem above; critical-point methods then find them. Later courses use the stronger statements named here without proof: the Arzelà–Ascoli theorem says which subsets of $C[0, 1]$ are compact (the extra condition is that the functions do not oscillate faster and faster), and Tychonoff’s theorem says a product of compact spaces is compact (B, named only). A continuous bijection from a compact space onto another metric space is automatically a homeomorphism, shown in 4.5.

Used in the real world· Machine learning: when does a minimizer of the loss exist?

Training a model means minimizing a continuous loss $L(w)$ over weights $w$ . The extreme value theorem says a minimizer exists on a compact set. Take logistic regression on two points: $x = 1$ with label $+1$ , and $x = -1$ with label $-1$ , one weight $w$ . The loss is $L(w) = 2\log(1 + e^{-w})$ . It is continuous and decreasing, with infimum $0$ approached as $w \to \infty$ but never reached: on the unbounded set $\mathbb R$ the minimum does not exist. Gradient descent on separable data of this kind makes the weights grow without bound, like $\log t$ after $t$ steps (Soudry and co-authors, 2018). Constrain $|w| \le B$ , a compact interval, and the minimum exists, at $w = B$ : with $B = 5$ it is $2\log(1 + e^{-5}) \approx 0.0134$ . Weight decay, norm clipping and constraint balls all restore compactness in finite dimensions. In infinite-dimensional function spaces the closed ball is not compact (the tent functions above), so minimizers over all functions need extra structure, such as equicontinuity in Arzelà–Ascoli.

Your answerLogistic loss on the two points above is

L(w) = 2\log(1 + e^{-w})

. What is its minimum over the compact set

|w| \le 5

, as a decimal?

Python labFind a finite subcover, and see the Lebesgue number

import random
random.seed(3)

def make_cover():
    sets, x = [], -0.05
    while x < 1.05:
        w = random.uniform(0.05, 0.3)
        sets.append((x - random.uniform(0, 0.05), x + w))
        x += w * random.uniform(0.3, 0.9)      # change 0.9 to 2.0 to open gaps
    random.shuffle(sets)
    return sets

def room(x, S):          # how far a ball around x can grow and stay inside one set
    return max(min(x - l, r - x) for l, r in S if l < x < r)

sets = make_cover()
grid = [i / 2000 for i in range(2001)]
assert all(any(l < x < r for l, r in sets) for x in grid), "not a cover"
lam = min(room(x, sets) for x in grid)
print("sets in the cover:", len(sets), "  Lebesgue number about", round(lam, 4))

chosen, x = [], 0.0                              # greedy finite subcover
while x <= 1:
    options = [s for s in sets if s[0] < x < s[1]]
    best = max(options, key=lambda s: s[1])
    chosen.append(best)
    x = best[1]
print("a finite subcover uses", len(chosen), "sets")

inf_cover = [(1 / n, 2) for n in range(1, 10001)]
for x in [0.5, 0.1, 0.01, 0.001]:
    print("(0,1] cover: x =", x, " room =", round(room(x, inf_cover), 5))

Try this. Run it as is. The Lebesgue number is the smallest 'room' any point of [0, 1] has inside the sets of the cover, and it is positive. The last four lines show the same quantity for the cover (1/n, 2) of (0, 1]: the room at the point x is about x, which shrinks to 0, so there is no Lebesgue number and no finite subcover. Now change the 0.9 in the step to 2.0, so that neighbouring intervals can stop overlapping. The assertion fails (some grid point is uncovered): a family with gaps is not a cover.

Traps

Watch out· Closed and bounded is compact only in R^n

Heine–Borel is a theorem about $\mathbb R^n$ . In $C[0, 1]$ , in the space of bounded sequences and in every infinite-dimensional normed space, the closed unit ball is closed and bounded and not compact. The right general statement is “complete and totally bounded”. If a problem is set in a function space, do not quote Heine–Borel.

Watch out· Sequentially compact means the limit is INSIDE the set

$(0, 1]$ has plenty of convergent subsequences. $\frac1n$ converges, in $\mathbb R$ . What fails is that the limit is in $(0, 1]$ . The definition says “a subsequence that converges to a point of $K$ ”. Dropping “of $K$ ” turns it into boundedness.

Watch out· To show NOT compact, exhibit one cover, not 'many covers'

Compact means EVERY open cover has a finite subcover. To prove a set is not compact you give one cover with no finite subcover (like $\{(\frac1n, 2)\}$ for $(0, 1]$ ). To prove a set is compact you cannot check covers one at a time. You use Heine–Borel, or sequences, or a continuous image of a compact set.

Watch out· A cover that is already finite proves nothing

The one-set family $\{\mathbb R\}$ covers every subset of the line, and it is finite. That shows nothing about compactness. The definition quantifies over ALL open covers: you are handed a family, possibly infinite and chosen to be awkward, and must find finitely many of its members that still cover. A cover that thins out near an edge, like the sets $(\frac1n, 2)$ for $(0, 1]$ , is the dangerous kind.

Watch out· Compactness is not preserved by taking preimages

The continuous image of a compact set is compact. The preimage of a compact set need not be. Take $f(x) = 0$ for all $x \in \mathbb R$ and the compact set $\{0\}$ : its preimage is all of $\mathbb R$ , which is not compact. Only images behave.

Problems

check

Decide whether each is compact: (a) $[0, 1] \times [2, 5] \subset \mathbb R^2$ . (b) $\{(x, y) : x^2 + y^2 \le 1\} \setminus \{(0, 0)\}$ . (c) $\{1/n : n \ge 1\} \cup \{0\}$ . (d) $\{1/n : n \ge 1\}$ .

Solution

(a) Closed bounded box: compact. (b) The closed disc with the centre removed is not closed ( $(\frac1n, 0) \to (0, 0)$ , which is outside). Not compact. (c) Closed (it contains the limit $0$ of $\frac1n$ ) and bounded: compact. (d) Not closed ( $0$ is a limit point outside): not compact.

check

Write an open cover of $(0, \infty)$ with no finite subcover. Is the set $(0, \infty)$ compact?

Solution

$U_n = (\frac1n, n)$ . Each $x > 0$ is in $U_n$ for $n$ large. A finite subfamily has union $U_N$ , which misses small and large numbers. So $(0, \infty)$ is not compact.

check

True or false: every finite subset of a metric space is compact.

Solution

True. Given an open cover, choose for each of the finitely many points one set containing it. Those finitely many sets cover the set.

check

A continuous function $f$ on $(0, 1)$ is bounded. Does $f$ attain a maximum? Give an example either way.

Solution

Not necessarily. $f(x) = x$ is bounded by $1$ and takes all values below $1$ but never reaches it. On the other hand $f(x) = \sin(\pi x)$ attains $1$ at $x = \frac12$ . The extreme value theorem needs a compact domain; bounded values are not enough.

use

Show that the closed ball $\{x \in \mathbb R^n : \lVert x - c \rVert_2 \le r\}$ is compact, and that the sphere $\{\lVert x - c \rVert_2 = r\}$ is compact.

Solution

Bounded: every point is within $r$ of $c$ . Closed: if $x_k \to x$ and $\lVert x_k - c \rVert \le r$ then $\lVert x - c \rVert \le r$ , since $|\lVert x_k - c \rVert - \lVert x - c \rVert| \le \lVert x_k - x \rVert \to 0$ . The same argument with equality gives the sphere. Heine–Borel applies to both.

use

Let $K \subset \mathbb R^2$ be the compact set $\{x^2 + y^2 \le 4\}$ and $f(x, y) = x^2 - y$ . Explain why $f$ has a maximum and a minimum on $K$ , and find them.

Solution

$K$ is a closed disc, compact, $f$ is continuous, so extremes exist. Interior critical point: $\nabla f = (2x, -1) \ne 0$ , so none. On the boundary $x = 2\cos t$ , $y = 2\sin t$ : $f = 4\cos^2 t - 2\sin t = 4 - 4\sin^2 t - 2\sin t$ . Put $s = \sin t \in [-1, 1]$ : $4 - 4s^2 - 2s$ , with vertex at $s = -\frac14$ giving $4 - \frac14 + \frac12 = 4.25$ . At $s = 1$ : $-2$ ; at $s = -1$ : $2$ . Maximum $4.25$ , minimum $-2$ (at $(0, 2)$ ).

use

Is $f(x) = \sqrt x$ uniformly continuous on $[0, 1]$ ? What is a $\delta$ for $\varepsilon = 0.1$ that works everywhere?

Solution

Yes: continuous on the compact $[0, 1]$ . For explicit $\delta$ use $|\sqrt x - \sqrt y| \le \sqrt{|x - y|}$ . So $\delta = \varepsilon^2 = 0.01$ works: $|x - y| < 0.01$ gives $|\sqrt x - \sqrt y| < 0.1$ . (The derivative is unbounded near $0$ , so $\delta$ cannot be proportional to $\varepsilon$ .)

use

For the discrete metric on a set $X$ , which subsets of $X$ are compact?

Solution

Exactly the finite ones. A finite set is compact (an earlier check problem). If $K \subseteq X$ is infinite, the sets $\{x\}$ for $x \in K$ are open (the ball of radius $\frac12$ around $x$ is $\{x\}$ ) and cover $K$ , and removing any one of them leaves its point uncovered, so no finite subfamily covers $K$ . Equivalently, $K$ is complete but not totally bounded, as in part (d) of the example above.

prove

Prove that a finite union of compact sets is compact.

Solution

Plan. Cover the union, then take a finite subcover for each piece.

Let $K_1, \dots, K_m$ be compact and $\{U_\alpha\}$ an open cover of $K_1 \cup \dots \cup K_m$ . It also covers each $K_i$ , so finitely many $U_\alpha$ cover $K_i$ . Collect these finite subfamilies: finitely many sets in total cover the union. $\blacksquare$

proveRudin Thm 2.35 style; new

Prove that if $K$ is compact and $F$ is closed then $K \cap F$ is compact.

Solution

Plan. It is a closed subset of the compact set $K$ .

$K \cap F \subseteq K$ , and it is closed because an intersection of closed sets is closed (4.1). By the lemma on closed subsets of compact sets, it is compact. $\blacksquare$

prove

Prove: if $K$ is a compact subset of a metric space and $p$ is a point outside $K$ , there is a point $q \in K$ with $d(p, q) \le d(p, x)$ for all $x \in K$ (a nearest point).

Solution

Plan. The distance to $p$ is a continuous function on a compact set.

$h(x) = d(p, x)$ is continuous on $K$ because $|h(x) - h(y)| \le d(x, y)$ (reverse triangle inequality), so $\delta = \varepsilon$ works. $K$ is compact, and non-empty (it must be, for a nearest point to exist), so by the extreme value theorem $h$ attains its minimum at some $q \in K$ . $\blacksquare$

prove

Prove: if $K_1 \supseteq K_2 \supseteq \cdots$ is a nested sequence of non-empty compact sets, then $\bigcap_n K_n \ne \varnothing$ .

Solution

Plan. Pick a point in each set, take a convergent subsequence, and show the limit is in every $K_n$ .

Choose $x_n \in K_n$ . All $x_n \in K_1$ , which is sequentially compact, so a subsequence $x_{n_k} \to x \in K_1$ . For a fixed $m$ , the terms $x_{n_k}$ with $n_k \ge m$ lie in $K_m$ (nested), and $K_m$ is closed (compact sets are closed), so the limit $x \in K_m$ . This holds for every $m$ , so $x \in \bigcap K_m$ . $\blacksquare$ (This is the compact version of the nested interval theorem. The halving argument in Heine–Borel used the same idea, with completeness of $\mathbb R^n$ finding the common point.)

prove

Prove that a continuous bijection $f : K \to Y$ from a compact metric space onto a metric space has a continuous inverse. (Hint: argue with sequences and a convergent subsequence.)

Solution

Plan. Argue by contradiction with sequences: if the inverse is not continuous, a bad sequence in $K$ has a convergent subsequence, and pushing it forward with $f$ gives a contradiction. (4.5 proves the same fact with closed sets.)

Let $g = f^{-1}$ and suppose $y_n \to y$ in $Y$ but $g(y_n) \not\to g(y)$ . Here we use the sequence form of continuity, 4.5. Then for some $\varepsilon > 0$ there is a subsequence with $d(g(y_{n_k}), g(y)) \ge \varepsilon$ . The points $x_k = g(y_{n_k})$ lie in the compact $K$ , so a further subsequence converges to some $x \in K$ , with $d(x, g(y)) \ge \varepsilon$ . By continuity, $f(x_k) \to f(x)$ , but $f(x_k) = y_{n_k} \to y$ , so $f(x) = y$ by uniqueness of limits, so $x = g(y)$ by injectivity, a contradiction with $d(x, g(y)) \ge \varepsilon$ . $\blacksquare$

stretch

Prove that the set $K = \{f \in C[0, 1] : |f(x) - f(y)| \le |x - y| \text{ and } f(0) = 0\}$ is totally bounded in the sup metric. (This is the Arzelà–Ascoli idea. $K$ is also closed, so it is compact.)

Solution

Plan. Round the function values on a grid; the Lipschitz condition forces each function to be close to a rounded step version of itself.

Fix $\varepsilon > 0$ and choose $N$ with $\frac1N < \frac\varepsilon4$ . Grid points $x_j = \frac jN$ . For $f \in K$ , $|f(x_j)| \le x_j \le 1$ . Round each $f(x_j)$ to the nearest multiple of $\frac\varepsilon4$ : finitely many possible rounded vectors $(r_1, \dots, r_N)$ . Two functions $f, g \in K$ with the same rounded vector satisfy $|f(x_j) - g(x_j)| \le \frac\varepsilon4$ at every grid point. For any $x$ , pick the nearest grid point $x_j$ with $|x - x_j| \le \frac1N < \frac\varepsilon4$ : $|f(x) - g(x)| \le |f(x) - f(x_j)| + |f(x_j) - g(x_j)| + |g(x_j) - g(x)| < \frac\varepsilon4 + \frac\varepsilon4 + \frac\varepsilon4 < \varepsilon$ . So the functions of $K$ fall into finitely many classes, each of diameter below $\varepsilon$ in $d_\infty$ ; picking one function from each class gives finitely many balls of radius $\varepsilon$ covering $K$ . $\blacksquare$

stretch

Prove that a compact metric space $K$ has a countable dense subset: a countable set $D \subseteq K$ such that every ball $B(x, r)$ with $x \in K$ contains a point of $D$ .

Solution

Plan. Total boundedness at the scales $\frac1n$ gives finitely many centres at each scale. Collect all the centres.

For each $n$ , total boundedness gives a finite set $D_n \subseteq K$ with $K = \bigcup_{p \in D_n} B(p, \frac1n)$ . Let $D = \bigcup_n D_n$ , a countable union of finite sets, so countable. Given $x \in K$ and $r > 0$ , choose $n$ with $\frac1n < r$ . Then $x \in B(p, \frac1n)$ for some $p \in D_n$ , so $d(x, p) < \frac1n < r$ , that is $p \in B(x, r) \cap D$ . $\blacksquare$

Summary

A set is sequentially compact if every sequence in it has a subsequence converging to a point of the set. It is compact if every open cover has a finite subcover. In a metric space these two are the same.
Compact sets are closed and bounded in every metric space. In $\mathbb R^n$ the converse holds as well: this is Heine–Borel, proved by halving a box that has no finite subcover until the boxes shrink to a point covered by one open set.
In a function space the closed unit ball is closed and bounded and not compact (tent functions at distance 1 from each other). The general statement is: compact means complete and totally bounded.
The proof that sequentially compact implies compact uses a Lebesgue number: one radius such that every ball of that radius sits inside a single set of the cover.
A continuous map sends compact sets to compact sets. Hence a continuous real function on a compact set attains its maximum and minimum, and a continuous map on a compact set is uniformly continuous.
Compactness is how an infinite set earns the good properties of a finite one: finite sets have a largest value and a smallest tolerance.
In machine learning, a minimizer of a continuous loss exists on a compact weight set. Logistic loss on separable data has infimum 0 on the whole line and no minimizer.

The picture: covers and finite subcovers

The idea, in words

Definitions and theorems

Sequential compactness

Sequentially compact

Bounded set in a metric space

Sequentially compact sets are closed and bounded

Bolzano–Weierstrass in R^n

Open covers and compactness

Open cover

Compact set

Compact sets are closed and bounded

Closed subsets of compact sets are compact

The Heine–Borel theorem

Heine–Borel theorem

Compact and sequentially compact are the same in a metric space

Totally bounded

Sequentially compact implies totally bounded

Lebesgue number lemma

Compact equals sequentially compact

Compact equals complete and totally bounded

Closed and bounded is not enough in function spaces

The unit ball of C[0,1] is closed and bounded but not compact

Compactness at work

Continuous maps send convergent sequences to convergent sequences

Continuous image of a compact set is compact

Extreme value theorem on a compact set

Continuous on a compact set implies uniformly continuous

Where it is used

Traps

Problems

Summary

Where this sits

Comes from

Leads to

Same idea elsewhere