Section 4.3 Compactness
Definition 4.13.
Let \(S\) be a subset of a metric space \((X,d)\text{.}\) A collection \(\set{U_\lambda}{\lambda \in \Lambda}\) of open sets in \(X\) is called an open cover of \(S\) if \(S \subseteq \bigcup_{\lambda \in \Lambda} U_\lambda\text{.}\) If \(M \subseteq \Lambda\) and \(S \subseteq \bigcup_{\mu \in M} U_\mu\text{,}\) then \(\set{U_\mu}{\mu \in
M}\) is called a subcover of \(\set{U_\lambda}{\lambda
\in \Lambda}\text{.}\)
Warning 4.14.
Note that the term open cover refers to the collection of open sets \(\set{U_\lambda}{\lambda\in\Lambda}\) and not to their union \(\bigcup_{\lambda \in \Lambda} U_\lambda\text{,}\) which is a subset of \(X\text{.}\)
Remark 4.15.
The index set \(\Lambda\) has no other purpose than to label the sets \(U_\lambda\text{,}\) and we can replace it with any other set of the same size. In particular, for a finite open cover, we can always write \(\{U_1, \dotsc, U_N\}\) for some \(N \in \N \cup \{0\}\text{.}\)
Definition 4.16.
A subset \(K\) of a metric space \((X,d)\) is called compact if every open cover of \(K\) has a finite subcover. If \(K=X\) is compact, we say that the metric space \((X,d)\) is compact.
Example 4.17.
Consider \(S=(0,1)\) as a subset of \(X=\R\) with the Euclidean metric. Then for any \(n \in \N\) the subset \(U_n = (1/n,1) \subset X\) is open. Since \(S \subseteq \bigcup_{n \in \N}
U_n\text{,}\) \(\{U_n : n \in \N\}\) is an open cover of \(X\text{.}\) It has many infinite subcovers, for instance \(\{U_{2k} : k \in \N\}\text{.}\) But one can check that there are no finite subcovers, and hence that \(S\) is not compact subset.
Example 4.18.
Let \(X\) be an arbitrary set equipped with the discrete metric.
Suppose first that \(X\) is finite. Let \(\set{U_\lambda}{\lambda \in \Lambda}\) be an open cover of \(X\text{.}\) Then for every \(x \in X\text{,}\) there exists \(\lambda_x \in \Lambda\) with \(x \in U_{\lambda_x}\text{.}\) Then \(\set{U_{\lambda_x}}{x \in X}\) is a finite subcover. Thus \(X\) is compact.
Now suppose that \(X\) is infinite. Then we consider the open cover \(\set{U_x}{x \in X}\) of \(X\) with \(U_x = \{x\}\) for every \(x \in X\text{.}\) Clearly, any finite subcollection \(\{U_{x_1,} \dotsc, U_{x_N}\}\) satisfies
\begin{equation*}
\bigcup_{n=1}^N U_{x_n} = \{x_1, \dotsc, x_n\} \ne X.
\end{equation*}
So \(X\) is not compact in this case.
Lemma 4.19. Compactness and metric subspaces.
A subset \(K\) of a metric space \((X,d)\) is compact if and only if the associated metric subspace \((K,d')\) is compact.
Proof.
Theorem 4.20.
If a metric space is complete and totally bounded, then it is compact.
Proof.
Suppose that \((X,d)\) is complete and totally bounded. Assume, by way of contradiction, that it is not compact. Then there exists an open cover \(\set{U_\lambda}{\lambda \in \Lambda}\) that does not have a finite subcover.
Define \(r_n = 1/2^n\) for \(n \in \N\text{.}\) Since \(X\) is totally bounded, there exists a finite set \(E_1 \subseteq X\) such that
\begin{equation*}
X \subseteq \bigcup_{x \in E_1} B_{r_1}(x).
\end{equation*}
Since \(E_1\) is finite, there exists at least one point \(x_1 \in E_1\) such that no finite subcollection of \(\set{U_\lambda}{\lambda \in \Lambda}\) covers \(B_{r_1}(x_1)\text{.}\) (If we had a finite subcollection covering \(B_{r_1}(x)\) for every \(x \in E_1\text{,}\) then the union of all of them would give a finite subcover of \(X\text{.}\))
By Lemma 4.11, the set \(B_{r_1}(x_1)\) is totally bounded, too. Hence there exists a finite set \(E_2 \subseteq B_{r_1}(x_1)\) such that
\begin{equation*}
B_{r_1}(x_1) \subseteq\bigcup_{x \in E_2} B_{r_2}(x).
\end{equation*}
Furthermore, there exists at least one point \(x_2 \in E_2\) such that no finite subcollection of \(\set{U_\lambda}{\lambda \in \Lambda}\) covers \(B_{r_2}(x_2)\text{.}\)
We can continue this construction with \(r_3, r_4, \dotsc\text{,}\) and we obtain a sequence \((x_n)_{n \in \N}\) in \(X\) such that \(x_{n + 1} \in B_{r_n}(x_n)\) and \(B_{r_n}(x_n)\) is not covered by any finite subcollection of \(\set{U_\lambda}{\lambda \in \Lambda}\) for every \(n \in \N\text{.}\)
We claim that \((x_n)_{n \in N}\) is a Cauchy sequence. In order to verify this, let \(m, n \in \N\) with \(n \gt m\text{.}\) Then
\begin{align*}
d(x_m, x_n)
\amp\le d(x_m, x_{m + 1}) + \cdots + d(x_{n - 1}, x_n) \\
\amp\le \sum_{k = m}^\infty r_k
= \sum_{k = m}^\infty \frac{1}{2^k}
= \frac{1}{2^{m - 1}}.
\end{align*}
Thus \(d(x_m, x_n) \to 0\) as \(m, n \to \infty\text{,}\) which means that we have a Cauchy sequence. As \(X\) is complete, it follows that there exists a limit \(x_0 = \lim_{n \to \infty} x_n\text{.}\)
Since \(\set{U_\lambda}{\lambda \in \Lambda}\) is a cover of \(X\text{,}\) there exists \(\lambda_0 \in \Lambda\) such that \(x_0 \in U_{\lambda_0}\text{.}\) Since \(U_{\lambda_0}\) is open, there exists \(s \gt 0\) such that \(B_s(x_0) \subseteq U_{\lambda_0}\text{.}\) Now choose \(N \in \N\) so large that \(d(x_N, x_0) \lt s/2\) and \(r_N \lt s/2\text{.}\) Then \(B_{r_N}(x_N) \subseteq B_s(x_0) \subseteq U_{\lambda_0}\text{.}\) But that means that \(B_{r_N}(x_N)\) is covered by a single element of \(\set{U_\lambda}{\lambda \in \Lambda}\text{,}\) contradicting the previous statement that no finite subcollection will cover it. This concludes the proof.
Theorem 4.21.
If a subset of a metric space is compact, then it is sequentially compact.
Proof.
Let \(K\) be a compact subset of a metric space \((X,d)\text{.}\) Assume for contradiction that there exists a sequence \((x_n)_{n \in \N}\) in \(K\) that has no subsequence converging to a limit in \(K\text{.}\) In other words, every \(y \in K\) is not the limit of any subsequence of \((x_n)_{n \in \N}\text{.}\) According to Exercise 1.3.6, this means that for every \(y \in K\) there exists \(r_y \gt 0\) with
\begin{equation*}
B_{r_y}(y) \cap \set{x_n}{n \in \N} \subseteq\{y\}.
\end{equation*}
Now the collection \(\set{B_{r_y}(y)}{y \in K}\) is an open cover of \(K\text{.}\) Since \(K\) is compact, there exist \(y_1, \dotsc, y_I \in X\) with
\begin{equation*}
K \subseteq \bigcup_{i = 1}^I B_{r_{y_i}}(y_i).
\end{equation*}
Hence
\begin{equation*}
\set{x_n}{n \in \N} \subseteq\bigcup_{i = 1}^I B_{r_{y_i}}(y_i) \cap \set{x_n}{n \in \N} \subseteq\{y_1, \dotsc, y_I\}.
\end{equation*}
Therefore, we actually have a sequence in the finite subspace \(\{y_1,
\dotsc, y_I\}\) of \(K\text{.}\) But clearly every finite metric space is sequentially compact, and we conclude that \((x_n)_{n \in \N}\) does have a subsequence converging to a limit in \(K\text{,}\) in contradiction to the assumption.
We now summarise some of the results on compactness.
Theorem 4.22.
Let \((X,d)\) be a metric space and let \(K \subseteq X\text{.}\) Then the following are equivalent.
- \(K\) is compact.
- \(K\) is totally bounded and the metric subspace \((K,d')\) is complete.
- \(K\) is sequentially compact.
Proof.
Theorem 4.21 states that (i) implies (iii). It follows from Lemma 4.3, Theorem 4.4 and Theorem 4.10 that (iii) implies (ii). Finally, Theorem 4.20 states that (ii) implies (i), where here we also use Lemma 4.19.
Remark 4.23.
It may seem silly to have different names for concepts that are equivalent. However, while they are equivalent for metric spaces, the two notions of compactness can also be defined in different contexts, and then they are no longer equivalent.
Since compactness and sequential compactness are equivalent, we can also restate some of the results from the previous sections.
Corollary 4.24.
Every compact subset of a metric space is bounded.
Proof.
Combine Theorem 4.22 with Lemma 4.9.
Corollary 4.25.
Suppose that \((X,d)\) is a compact metric space and \(Y \subset X\text{.}\) If \(Y \subset X\) is closed, then it is compact.
Proof.
Combine Theorem 4.22 with Theorem 4.6.
Exercises Exercises
1. (PS9) Direct proof of non-compactness.
Let \(S\) be the unit ball \(B_1(0)\) as a subset of the metric space \(\R^2\) with the usual Euclidean metric. Directly prove that \(S\) is not compact. That is, find an open cover \(\set{U_\lambda}{\lambda \in \Lambda}\) of \(S\) which has no finite subcovers.
Hint.
If you’re feeling stuck, examples from the lectures, lecture notes and problems classes may be useful inspiration.
2. Compactness and metric subspaces.
Let \(Y\) be a subset of a metric space \((X,d)\text{.}\) Show that \(Y\) is compact if and only the metric subspace \((Y,d')\) is compact.
Hint.
Use Exercise 1.2.2.
3. (PS9) Continuity on compact spaces.
Let \((X, d_X)\) and \((Y, d_Y)\) be a metric spaces and \(f \maps X \to Y\) a continuous map. Show that \(f\) is uniformly continuous if \(X\) is compact.
Hint 1.
This is relatively big hint. The official solution uses Definition 4.16 directly. The general idea is to construct an open cover in the following way. Fix \(\varepsilon \gt 0\text{.}\) Since \(f\) is continuous, for all \(x \in X\) there exists a \(\delta(x) \gt 0\) such that \(d_X(x,x') \lt \delta(x)\) implies that \(d_Y(f(x),f(x')) \lt \varepsilon\text{.}\) Then the set of all balls of the form \(B_{\delta(x)}(x)\) forms an open cover of \(X\text{,}\) and so using compactness we can find a finite subcover.
This is only the general idea, though, and you will likely find that you need to do things like fiddle around with \(\varepsilon\) versus \(\varepsilon/2\text{,}\) and also with the radii of the balls in the open cover.
Hint 2.
Alternatively, thanks to Theorem 4.22, we can argue instead using sequential continuity. For this, you will want to write down what it would mean for \(f\) not to be uniformly continuous, and then use that to construct sequences with a certain property. Sequential compactness will let you find convergent subsequences, which will then lead to a contradiction with the (pointwise) continuity of \(f\text{.}\)
4. (PS9) Images of compact sets.
Let \((X,d_X)\) and \((Y,d_Y)\) be metric spaces and suppose \(f\maps
X \to Y\) is continuous.
(a)
Suppose \((X,d_X)\) is sequentially compact. Prove using the definition of sequential compactness that the image \(f(X)\) is sequentially compact.
Hint.
Given a sequence in \(f(X)\text{,}\) relate it to a sequence in \(X\text{,}\) and then use sequential compactness.
(b)
Suppose \(U \subseteq Y\) is open in \(Y\text{.}\) Show that the preimage \(f^{-1}(U)\) is open in \(X\text{.}\)
Hint.
Look at the definition of continuity (Definition 1.42) and rewrite the relevant inequalities in terms of points being in certain balls.
(c)
Suppose \((X,d_X)\) is compact. Prove using the definition of compactness that \(f(X)\) is compact.
Hint.
Part b is useful here.
5. (PS8) A closed and bounded set which is not compact.
Consider the sequence \(\seq fn\) in \(C^0([0,\pi])\) defined by
\begin{equation*}
f_n(t) = \sin(2^n t) \text{,}
\end{equation*}
together with the corresponding subset
\begin{equation*}
F = \set{f_n}{n \in \N} \subset C^0([0,\pi]) \text{.}
\end{equation*}
(a)
Show that \(F\) is a bounded subset of \(C^0([0,\pi])\text{.}\)
(b)
Show that
\begin{gather}
\n{f_n-f_m}_{C^0([0,\pi])}
\ge 1 \text{ if } n \ne m\text{.}\tag{✶}
\end{gather}
Hint.
To get some intuition, draw graphs for small values of \(n\) and \(m\text{.}\) Since you only need a lower bound, it suffices to find a point \(t \in [0,\pi]\) where \(\abs{f_n(t)-f_m(t)} \ge 1\text{.}\)
(c)
Use (✶) to show that \(\seq fn\) has no convergent subsequences.
Hint.
Theorem 1.37 is useful.
(d)
Use (✶) to show that \(F\) is not totally bounded.
Hint 1.
Suppose that \(r \in (0,1)\) and let \(f \in F\text{.}\) What can you say about the open ball \(B_r(f)\text{?}\)
Hint 2.
(e)
Use (✶) to find an open cover of \(F\) with no finite subcover.
Hint.
Same hints as for the previous part.
(f)
Use Theorem 1.35 to show that \(F\) is closed.
Hint.
Once again, (✶) is useful.
