Lecture 11 - Compactness

Definition
A collection of open sets {G↵ }↵2A is a cover of a set S if S ⇢ [↵2A G↵ .

Examples
(1) I1 = (0, 2), I2 = (3, 5) is a cover for (0, 1) or {1, 4} but not a cover for [0, 1)
or {10, 12}.
(2) In = (n 1/3, n + 1/3), n 2 N. This is a cover for N, (0.9, 1.1) but not for
Z, R, {1/2}.
Definition
Suppose {G↵ }↵2A is a cover of a set S. If there are ↵1 , . . . , ↵m 2 A such that
the subcollection {G↵1 , . . . , G↵m } is also a cover of S, i.e., S ⇢ [m
i=1 G↵i , we say
that this cover has a finite subcover {G↵1 , . . . , G↵m }.

Examples
(1) In = ( 1 + 1/n, 1 1/n), n 2, is a cover of the sets S below:
(a) S = [ 3/5, 3/5], for which there exists a finite subcover e.g. {I3 } or {I4 } or
{I2 , I3 , I4 } (but not I2 alone).
(b) S = (0, 1), for which there is no finite subcover.
(2) In = (n 1/3, n + 1/3), n 2 N, is a cover of the sets S below:
(a) S = (1.9, 2.1) [ {6}, for which there exists a finite subcover e.g. {I2 , I6 } or
{I2 , I6 , I9 }.
(b) S = N, which has no finite subcover.
Definition
A set S is compact if every cover of S has a finite subcover.

Examples
(1) (a) [ 3/5, 3/5] is compact in R - will be proved later.
(b) (0, 1) is not compact in R, or in (0, 1) (counterexample above).
(2) (a) (1.9, 2.1) [ {6} is not compact in R - easy to produce a counterexample as for
(1)(b).
(b) N is not compact in R (counterexample above).
(3) In a discrete metric space a set is compact if and only if it is finite.
Lemma
A closed subset of a compact set is compact.

Proof:
Suppose S ⇢ K, where S is closed and K is compact.
Let {G↵ }↵2A be a cover of S.
Since S is closed X\S is open. Hence {X\S} [ {G↵ }↵2A is a cover for K.
Since K is compact it has a finite subcover {X\S} [ {G↵i }ki=1 .
Since S ⇢ K, {X\S} [ {G↵i }ki=1 is also a cover for S.
But since none of the points of S are covered by X\S it can be dropped.
Hence we have found a finite subcover {G↵i }ki=1 for S.
 Lecture 12 - Boundedness

Definition
A set S is bounded if diam S = sup{d(x, y) : x, y 2 S} < 1.

Examples
(1) (R, | · |), diam([a, b]) = diam((a, b)) = diam((a, b]) = diam([a, b)) = b a, all
bounded sets; diam([a, 1)) = ((a, 1)) = 1, both unbounded sets.
(2) A discrete space: all sets are bounded.
(3) If (X, k · k) is a normed vector space then S ⇢ X is bounded if and only if
supx2S kxk is finite. (Exercise - prove this!)
Theorem
If S is compact then it is closed and bounded.

Proof:
Let S be a compact set.
To prove S is closed, we show that S has no limit points in X \ S.
Let x 2 X \ S be arbitrary.
Let Gn = X\B(x, 1/n). Since {Gn }n2N covers X\{x} it also covers S.
Since S is compact there is a finite subcover {Gni }m
i=1 . Let
N = max{ni : 1  i  m}.
We have S ⇢ [m o
i=1 Gni = GN = X\B(x, 1/N ) and so the ball B (x, 1/N )
contains no points of S.
Hence x is not a limit point of S, so S is closed.
To prove that S is bounded take any x 2 X and consider {B (x, n)}n2N , which
covers X and hence S too.
Since S is compact it has a finite subcover {B (x, ni )}i1m . Let
N = max{ni : 1  i  m}.
Then S ⇢ B o (x, N ) and for each y, z 2 S we have
d(y, z)  d(y, x) + d(x, z)  2N implying that diam S  2N < 1.
Theorem (1)
In the Euclidean metric space Rn , a set S is compact if and only if it is closed and
bounded.

To prove this theorem we need some preparation.

We call sets of the form R = [a(1) , b(1) ] ⇥ · · · ⇥ [a(n) , b(n) ] rectangles in Rn .

Lemma
Let (Ri )i2N be a decreasing sequence of nested rectangles, i.e., Ri+1 ⇢ Ri for all
i 2 N. Then \i2N Ri 6= ;.

Proof:
i , bi ] ⇥ · · · ⇥ [ai , bi ] for each i 2 N. Proceeding coordinate-wise,
Let Ri = [a(1) (1) (n) (n)

we note that for each k 2 {1, . . . , n} we have that

(k) (k) (k) (k) (k) (k) (k)
a1  a2  a3 · · ·  b3  b2  b1 , so (ai )i2N is an increasing sequence
(k)
that is bounded above, converging to some a(k) ; and (bi )i2N is a decreasing
sequence that is bounded below, converging to some b(k) ; and moreover
a(k)  b(k) . Hence
6 [a(1) , b(1) ] ⇥ · · · ⇥ [a(n) , b(n) ] ⇢ \i2N Ri .
;=
Lemma (Heine-Borel Lemma)
In the Euclidean metric space Rn , every rectangle is compact.

(Note that this shows in particular that [a, b] ⇢ R is compact!)

Proof:
Let R be a rectangle. Let {G↵ }↵2A be a cover of R. Suppose it has no finite
subcover.
Let R1 = R and = diam R. Split R1 into 2n equal rectangles of diameter /2.
At least one of them has no finite subcover — denote it by R2 .
Split R2 into 2n equal rectangles of diameter /22 . At least one of them has no
finite subcover — denote it by R3 .
Continuing this process we get a sequence (Ri ) of nested rectangles. By the
previous lemma there is x 2 Ri for all i.
The point x is covered by some G↵ . Since G↵ is open there is B o (x, r) ⇢ G↵ .
For each i we have x 2 Ri and diam(Ri ) = /2i 1 , so Ri ⇢ B(x, /2i 1 ). Hence
Ri ⇢ B o (x, r) whenever /2i 1 < r, that is, for all i large enough (specifically, for
i > 1 + log2 ( /r)). Pick one such Ri .
Ri is then covered by G↵ which contradicts our choice of Ri (a rectangle that has
no finite subcover).
We can now give a proof of Theorem (1).
Proof: (of Theorem (1))
We only need to show that every closed and bounded set S in Rn is compact.
Since S is bounded it is contained in some rectangle R.
S is closed and R is compact hence S is compact.

Remarks
Does Theorem (1) extend to more general metric spaces?
True in Rn with any norm
Not true in general: in 1-dimensional normed spaces the closed unit ball is
never compact (see examples later).
 Lecture 13 - Compactness in more general metric
spaces

How can we understand compactness in more general metric spaces (other than in
the Euclidean space Rn )?

Definition
A set S is sequentially compact if every sequence of points in S has a
subsequence converging to a point in S.

Examples
(1) [0, 1] is sequentially compact by Bolzano-Weierstrass.
(Recall - B-W says every bounded sequence in R has a convergent
subsequence. And [0, 1] is closed so contains all its limit points.)
(2) A set in a discrete space is sequentially compact if and only if it is finite.

Theorem
In any metric space, a set is compact if and only if it is sequentially compact.
Proof: (Part 1: compact ) sequentially compact)
Suppose S is compact.
Suppose (xn )n2N is a sequence of points in S which has no convergent
subsequence to a point in S.
Denote A = {xn : n 2 N} ⇢ S.
No point of S is a limit point of A. (If x 2 S is a limit point of A then there
exists a sequence of points of A distinct from x converging to x. But this would
imply the existence of a subsequence of (xn ) converging to x, a contradiction.)
Hence, for any y 2 S, there is r(y) > 0 such that B o (y, r(y)) contains no points
from A except perhaps y.
Consider the collection of sets {B o (y, r(y))}y2S . It is a cover of S.
Since S is compact there is a finite subcover {B o (yi , r(yi ))}m
i=1 .
Hence A ⇢ S ⇢ [m o
i=1 B (yi , r(yi )).
Since each ball contains at most one point of A and there are m of them, A has
at most m points: {y1 , . . . , ym }.
Hence the sequence (xn ) takes at least one of the values {y1 , . . . , ym } infinitely
many times.
This gives a subsequence converging to that value. Contradiction.

For proof of part 2 (“sequentially compact ) compact”) see next two lectures.
Remark
The above theorem is not in general true in topological spaces (which are more
general than metric spaces - see later in the course).

Example
Using this theorem we can give an example of a normed space in which the closed
unit ball is not compact.
Let `1 be the vector space of bounded real sequences with the norm

k(xn )k1 = sup |xn |.

n2N

Given k, let ek 2 `1 be the sequence that is zero except that its k-th value is 1.
(So e1 = 1, 0, 0, . . ., e2 = 0, 1, 0, 0, . . ., e3 = 0, 0, 1, 0, 0, . . . etc.)
Since kek k1 = 1 all ek belong to the unit ball around the zero sequence.
However, since kek em k1 = 1 whenever k 6= m the sequence (ek ) has no
convergent subsequence.
Hence the closed unit ball is not sequentially compact and hence not compact.