Chair for Mathematical Information Science

Thomas Allard
Sternwartstrasse 7
CH-8092 Zürich

Mathematics of Information
Spring semester 2022

Notes on compact sets

Throughout the notes, (X , d) will denote a metric space. These notes are partly based on the
notes [1].

Definitions
Definition 1 (Open cover). Given an index set I and a subset C of X , a family {Oi }i∈I of open
sets Oi ⊆ X is said to be an open cover of C if
[
C⊆ Oi .
i∈I

The family {Oj }j∈J is said to be a finite subcover of {Oi }i∈I if it is a cover of C and contains
a finite number of open sets, i.e., C ⊆ j∈J Oj and J ⊆ I is finite.
S

Definition 2 (Compactness). A subset C of X is said to be compact if every open cover of C

admits a finite subcover.

Definition 3 (Sequential compactness). A subset C of X is said to be sequentially compact if

every sequence {xn }n∈N ⊆ C admits a converging subsequence.

Equivalence of the notions of compactness

We have defined two distinct notions of compactness. It turns out that in a metric space, these
two notions are equivalent and relate to the notion of covering numbers seen in class.

Lemma 1. The following are equivalent:

a) The set C ⊆ X is compact;

b) The set C ⊆ X is sequentially compact;

c) The set C ⊆ X is complete and, for every ε > 0, the ε-covering number of C is finite.

Remark 1. One often encounters the denomination ‘totally bounded’ for a set which, for every
ε > 0, has a finite ε-covering number.

Remark 2. In the lecture, we defined the covering number only for compact sets. The impli-
cation ‘a) =⇒ c)’ in Lemma 1 ensures that the covering number a compact set is well defined
and finite.
Proof. We prove that compactness is equivalent to sequential compactness, which in turn is
equivalent to being complete and totally bounded.
‘a) =⇒ b)’: Assume by contradiction that C is compact but not sequentially compact and
take {xn }n∈N a sequence which admits no converging subsequence. Consider the family

{O ⊆ C | O is open and contains at most a finite number of elements of {xn }n∈N } .

Then this family is an open cover of C. Indeed, for every x ∈ C, since no subsequence of {xn }n∈N
converges to x, there exists an open neighborhood O of x which contains at most finitely many
elements of {xn }n∈N . By compactness of C, it can then be covered by finitely many open sets O,
which each contain at most finitely many elements of {xn }n∈N . We have reached a contradiction.
‘b) =⇒ a)’: Let’s take C to be sequentially compact. Let {Oi }i∈I be an open cover of C.
We first prove that there exists δ > 0 such that, for every x ∈ C, there exists i ∈ I satisfying
B(x, δ) ⊆ Oi . We argue by contradiction, that is, we suppose that we can find a sequence {xn }n∈N
in C such that B(xn , 1/n) is not contained in any Oi . By sequential compactness, {xn }n∈N admits
a subsequence which converges to some x ∈ C. Because {Oi }i∈I covers C, there exists i ∈ I such
that x ∈ Oi , and, since Oi is open, there exists ε > 0 such that B(x, ε) ⊆ Oi . Since {xn }n∈N has
a subsequence converging to x, there exists n ∈ N such that B(xn , 1/n) ⊆ B(x, ε) ⊆ Oi , which
is in contradiction with the construction of {xn }n∈N .
We have proven that there exists δ > 0 such that, for every x ∈ C, there exists i ∈ I satisfying
B(x, δ) ⊆ Oi . Assume, again by way of contradiction, that there is no finite subcover of {Oi }i∈I .
Then, one can construct a sequence {xn }n∈N in C such that xp ∈ / B(xq , δ) for all p 6= q, otherwise
C could be covered by a finite number of balls of radius δ and a fortiori by a finite number
open sets Oi containing these balls (which, we have proven above, exist). The sequence {xn }n∈N
admits a convergent subsequence by sequential compactness of C, but also satisfies d(xp , xq ) ≥ δ
for all p 6= q by construction, which yields a contradiction and concludes the proof.
‘b) =⇒ c)’: Let’s take C to be sequentially compact and {xn }n∈N a Cauchy sequence in C.
By sequential compactness, {xn }n∈N has a converging subsequence. Since {xn }n∈N is Cauchy
and has a converging subsequence, it is convergent in C and therefore C is complete.
Given ε > 0, the family
{B(x, ε) | x ∈ C}
is an open cover of C. We have already proven that sequential compactness implies compactness.
One can thus find a finite subcover to {B(x, ε) | x ∈ C}. The cardinality of a minimal such
subcover is, by definition, the ε-covering number of C, which is therefore finite.
‘c) =⇒ b)’: Let’s assume that C is complete and has finite (1/m)-covering number for every
integer m ≥ 1. We consider a sequence {xn }n∈N in C and want to show that it admits a
(1) (1)
converging subsequence. Let {y1 , . . . , yN1 } be a 1-covering of C, then, by finiteness of the
(1)
covering, one can extract a subsequence {xn }n∈N of {xn }n∈N such that all its elements are in
(1) (m) (m−1)
B(y` , 1) for some 1 ≤ ` ≤ N1 . Likewise, one can find a subsequence {xn }n∈N of {xn }n∈N
(m) (m) (m)
such that all its elements are contained in B(y` , 1/m), where {y1 , . . . , yNm } is a (1/m)-
(k)
covering of C and 1 ≤ ` ≤ Nm . The sequence {xk }k∈N is therefore a Cauchy sequence. By
completeness of C, it is a converging subsequence of {xn }n∈N , which completes the proof.

Examples
Corollary 1 (Finite metric space). A metric space (X , d) containing a finite number of elements
is compact.
Proof. Since X is finite, for any sequence {xn }n∈N ⊆ X there must exists a point x ∈ X such
that {xn }n∈N passes infinitely many times through x. Writing {nk }k∈N the indices for which
xnk = x, we have constructed a subsequence {xnk }k∈N which converges (to x). Therefore X is
sequentially compact. From the implication ‘b) =⇒ a)’ in Lemma 1, the set X is compact.

Example 1. Given n ∈ N, let the Hamming cube be defined as

Hn := {0, 1}n ,

and let

d : Hn × Hn → R+
(x, y) 7→ #{i ∈ {1, . . . , n} | xi 6= yi }

be a metric on Hn . Then Hn is finite and therefore compact. From the implication ‘a) =⇒ c)’
in Lemma 1, the set Hn has a finite covering number. We refer the reader to [Problem 4, Exam
Winter 2021/2022] for an estimation of this covering number.

Corollary 2 (Closed bounded sets in Rn ). A closed bounded subset C of Rn equipped with the
Euclidean norm k · k2 is compact.

Remark 3. Since Rn is a finite dimensional vector space, all the norms on Rn are equivalent.
Therefore, the result above generalizes readily to Rn equipped with any norm k · k.

Proof. Consider a Cauchy sequence {xn }n∈N ⊆ C. It converges to some x ∈ Rn by completeness

of Rn . Since C is closed, x ∈ C which proves that C is complete.
Fix ε > 0. Since C is bounded, it is included in the cube [−R, R]n . From the lecture, we
know that the ε-covering number of this cube is finite. To show that it implies that C is totally
bounded, we make the following observation. Since the ε-covering number of the cube is finite,
there exist x1 , . . . , xN ∈ Rn such that [−R, R]n ⊆ ∪Ni=1 B(xi , ε/2). Then, for every i ∈ {1, . . . , N }
such that C ∪ B(xi , ε/2) 6= ∅, choose ci ∈ C ∪ B(xi , ε/2). It follows from B(xi , ε/2) ⊂ B(ci , ε) that
C ⊆ ∪i B(ci , ε). The set C is thus totally bounded.
C is complete and totally bounded, therefore, from the implication ‘c) =⇒ a)’ in Lemma 1,
C is compact.

References
[1] Giada Franz. Equivalent Notions of Compactness.