Compactness and Heine-Borel

Compactness Implies Sequential Compactness Let \(\{x_n\}_{n=1}^\infty\) be a sequence in a compact metric space \((X,d)\). Let \(E \subset X\) be the set of values of the sequence, i.e., \(E := \{y \in X \ : y = x_n \text{ for some } n\}\). If \(z\) is any point in \(X\), we may assume that there is some radius \(r > 0\) such that \(B_r(z)\setminus\{z\}\) contains no points of \(E\) (otherwise we may build a subsequence \(\{x_{n_k}\}_{k=1}^\infty\) such that \(d(x_{n_k},z) < d(x_{n_{k-1}},z)/2\) for each \(k\), which will clearly converge because the distance to \(z\) decays at least exponentially in \(k\); note also that if we were forced to take \(n_k < n_{k-1}\), then \(B_r(z) \setminus \{z\}\) would not intersect \(E\) when \(r < \frac{1}{2} \min \{d(z,x_1),\ldots,d(z,x_{n_{k-1}})\}\)). We can also assume that \(E\) is infinite, since finiteness of \(E\) implies that there is a constant (and therefore convergent) subsequence of \(\{x_n\}_{n=1}^\infty\). But we can now see that \(X\) must be covered by balls \(B_r(z)\) which contain either zero or one points of \(E\) (depending on whether \(z \not \in E\) or \(z \in E\)). The existence of a finite subcover implies that \(E\) must be finite, which is a contradiction.

Sequential Compactness Implies Compactness Let \(\tilde r(x) := 1/n\) for the smallest \(n\) such that \(1/n \leq r(x)/2\) and let \(\tilde \epsilon_0\) be the threshold such that every ball \(B_{\tilde r(x)}(x)\) of radius less than \(\tilde \epsilon_0\) is contained a ball \(B_{\tilde r(z)}(z)\) of radius at least \(\tilde \epsilon_0\).

Let \({\mathcal{C}}_1\) be a maximal collection of \(1\)-separated points \(x\) for which \(\tilde r(x) = 1\). Next let \({\mathcal{C}}_2\) be a maximal collection of \(1/2\)-separated points \(x\) such that \(\tilde r(x) = 1/2\) and \({\mathcal {C}}_1 \cup {\mathcal {C}}_2\) is also \(1/2\)-separated. Proceed similarly: Let \({\mathcal{C}}_n\) be a maximal collection of \(1/n\)-separated points \(x\) such that \(\tilde r(x) = 1/n\) and \(\bigcup_{j=1}^n {\mathcal{C}}_j\) is \(1/n\)-separated. Continue in this way for all \(n \leq N_0\), where \(N_0\) is the smallest integer such that \(1/N_0 < \epsilon_0\).

For any \(x\), if \(\tilde r(x) < \tilde \epsilon_0\), then \(B_{\tilde r(x)}(x)\) is contained in some \(B_{\tilde r(x')}(x')\) for \(r(x') \geq \tilde \epsilon_0 \geq 1/N_0\). Moreover, if any ball \(B_{\tilde r(x')}(x')\) with \(r(x') \geq 1/N_0\) does not have \(x' \in {\mathcal{C}}_j\) for the appropriate \(j\), it must be because there is a point \(x''\) which does belong to one of those \({\mathcal{C}}_j\) which is too close to \(x'\), i.e., \(r(x'') \geq r(x')\), \(d(x'',x') < r(x')\) and \(x'' \in C_j\) for the relevant \(j\). Any point \(y \in B_{\tilde r(x')}(x')\) satisfies

In other words, \(B_{\tilde r(x')}(x') \subset B_{2 \tilde r(x'')} (x'')\). Because \(2 \tilde r(x'') \leq r(x)\), it follows that \(B_{\tilde r(x')}(x') \subset B_{r(x'')}(x'')\) for some \(x''\) belonging to one of the finite sets \({\mathcal{C}}_1,\ldots,{\mathcal{C}}_{N_0}\). Thus the finite subcollection

must cover every ball \(B_{\tilde r(x)}(x)\), and therefore must cover \(X\) itself.

\([\Rightarrow]\) Suppose that \((X,d)\) is compact but not complete. By the notes on completeness, there must be a Cauchy sequence \(\{x_n\}_{n=1}^\infty\) in \(X\) for which every \(x \in X\) has a ball \(B_\epsilon(x)\) containing \(x_n\) for only finitely many values of \(n\). By compactness, \(X\) may be covered by finitely many such balls, but then only finitely many values of \(n\) could have \(x_n\) belonging to the union of these balls (which would be all of \(X\) and consequently contain \(x_n\) for all values of \(n\)).

To see that it must be close to finite, fix \(\epsilon > 0\) and cover \(X\) by balls \(B_\epsilon(x)\) for each \(x \in X\). Compactness implies the existence of a finite subcover satisfying exactly the required properties.

\([\Leftarrow]\) Let \(\{x_n\}_{n=1}^\infty\) be a sequence in \(X\). We will show that it must have a convergent subsequence. For each positive integer \(j\), let \(S_j\) be a finite subset of \(X\) such that every element of \(X\) is within distance strictly less than \(2^{-j}\) to some point in \(S_j\).

Because \(S_1\) is finite, there must be \(y_1 \in S_1\) such that \(d(x_n,y_1) < 1/2\) for infinitely many values of \(n\). Let \(n_1\) be the smallest such value of \(n\). By induction, suppose that there are points \(y_1,\ldots,y_j\) in \(S_1,\ldots,S_j\) such that infinitely many values of \(n\) (call the set of such \(n\)'s \(I_j\)) have \(d(x_n,y_k) < 2^{-k}\) for each \(k = 1,\ldots,j\). Let \(n_j\) be the smallest such value of \(n \in I_j\) which is greater than \(n_{j-1}\). Because \(S_{j+1}\) is finite and \(I_j\) is infinite, there must be some \(y_{j+1} \in S_{j+1}\) such that infinitely many \(n\) in \(I_j\) have \(d(x_n,y_{j+1}) < 2^{-j-1}\). In particular, there is some \(n_{j+1}\) strictly greater than \(n_j\) which belongs to this desired set \(I_{j+1}\) of indices.

The subsequence \(\{x_{n_j}\}_{j=1}^\infty\) must be Cauchy, because

when \(k \geq j\). In particular, for any \(\epsilon > 0\), if \(2^{-N+1} < \epsilon\) and \(j,k \geq \epsilon\), then \(d(x_{n_j},x_{n_k}) < \epsilon\). Because \(X\) is complete, the subsequence \(\{x_{n_j}\}_{j=1}^\infty\) must converge to some point of \(X\), which is exactly what is required to see that \(X\) is sequentially compact.

\([\Rightarrow]\) Fix any \(\epsilon > 0\). From general metric space theory, we know that \(E\) must be closed and bounded. The set \(U_P := \{ u \ : \ ||u - P u|| < \epsilon \}\) is open for any orthogonal projection \(P\). The zero vector belongs to each \(U_P\), and for any \(x \in H\) which is nonzero, it belongs to \(U_P\) when \(P\) is the one-dimensional projection onto the vector subspace spanned by \(x\). If \(E \subset H\) is compact, then, it must be contained in a finite union of sets \(U_{P_1},\ldots,U_{P_N}\) for orthogonal projections \(P_j\) onto 1D subspaces spanned by vectors \(v_1,\ldots,v_N\). Let \(P\) be orthogonal projection onto the span of \(\{v_1,\ldots,v_N\}\). Since \(P x\) is the vector \(z\) in the span which minimizes \(||x - z||\), it follows that \(||x - P x|| \leq ||x - P_j x||\) for each \(j = 1,\ldots,N\) (because \(P_j x\) also belongs to the span). Now every \(x \in E\) has \(||x - P_j x|| < \epsilon\) for some \(j \in \{1,\ldots,N\}\), so \(||x - Px|| < \epsilon\) for all \(x \in E\).

\([\Leftarrow]\) Since \(E\) is closed and \(H\) is complete, \(E\) is also complete. Let \(P\) be orthogonal projection onto some finite-dimensional subspace \(M\) of \(H\) such that \(||x - Px|| < \epsilon/4\) for each \(x \in E\). Because \(||Px|| \leq ||x||\) and \(E\) is bounded, \(PE\) is also a bounded subset of \(M\). Let \(e_1,\ldots,e_N\) be an orthonormal basis of \(M\). Every \(y \in P E\) equals \(\sum_{j=1}^N c_j e_j\) for some coefficients \(c_j\) with \(||y||^2 = \sum_{j=1}^N |c_j|^2\). The map \(y \mapsto (c_1,\ldots,c_N)\) is in particular an isometry between \(M\) and \({\mathbb R}^N\) or \({\mathbb C}^N\) (depending on the field used). In \({\mathbb R}^N\) and \({\mathbb C}^N\), every bounded set may be covered by finitely many balls of radius \(\epsilon/4\) (because every bounded set is contained in a compact set). This means that there are finitely many points \(y_1,\ldots,y_{N'}\) in \(M\) such that every \(x \in E\) has some \(k\) for which \(||P x - y_k|| < \epsilon/4\). Without loss of generality (reducing the number of \(y_k\)'s if necessary), for each \(k=1,\ldots,N'\), it may be assumed that there is some \(x_k\) such that \(||P x_k - y_k|| < \epsilon/4\). Then any other \(x\) with \(||P x-y_k|| < \epsilon/4\) has

Thus \(E\) is contained in the union of \(B_\epsilon(x_1) \cup \cdots \cup B_\epsilon(x_{N'})\), meaning that \(E\) is close to finite.

Let \(\{f_n\}_{n=1}^\infty\) be a uniform Cauchy sequence of elements in the uniform closure of \(\mathcal F\). Without loss of generality, for each \(n\), there is some \(g_n \in \mathcal F\) such that \(d_Y(f_n(x),g_n(x)) < 2^{-n}\) for all \(x \in X\). This forces \(\{g_n\}_{n=1}^\infty\) to be a uniform Cauchy sequence as well. Because the closure of \(\{ f(x) \ : \ f \in \mathcal F\}\) is compact in \(Y\) for each \(X\), it is complete and \(g_n(x)\) must have a pointwise limit at each \(x \in X\). By the usual \(\epsilon/3\) argument, the limit must be continuous. If the limit is called \(g\), then

and the right-hand side tends to zero uniformly in \(X\) as \(n \rightarrow \infty\). Thus the Cauchy sequence \(\{f_n\}_{n=1}^\infty\) converges uniformly in \(C(X,Y)\), and the limit function \(g\) must belong to the closure of \(\mathcal F\) because it's closed.

It suffices to show that the closure of \(\mathcal F\) is close to finite. Let \(\delta\) be such that \(d_X(x,x') < \delta\) implies \(d_Y(f(x),f(x')) < \epsilon/4\) for each \(f \in \mathcal F\), and let \(x_1,\ldots,x_N\) be points in \(X\) such that \(X = \bigcup_{i=1}^N B_{\delta}(x_i)\) (which exist by compactness). Since the Cartesian products of the closures of the sets \(\{f(x_i) \ : f \in \mathcal F\}\) for \(i=1,\ldots,N\) is compact, there must exist finitely many tuples \((y_1,\ldots,y_N)\) in \(Y^N\) such that every \(f\) admits some such tuple \((y_1,\ldots,y_N)\) such that \(d_Y (f(x_i),y_i) < \epsilon/4\) for each \(i\). As above, it may be assumed that for a given tuple \((y_1,\ldots,y_N)\), there is at least one \(f \in \mathcal F\). If \(g\) is any other such element of \(\mathcal F\), then every \(x \in X\) admits some \(x_i\) for which

This yields a finite list of functions \(f \in \mathcal F\) such that every \(g\) in \(\mathcal F\) is uniformly less than distance \(\epsilon\) to one of the \(f\)'s. After taking the closure, no element \(\tilde g\) in the closure of \(\mathcal F\) can be strictly greater than distance \(\epsilon\) to each of the \(f\)'s. Aside from the fact that the distance inequality is not strict (which can be fixed in the usual way by replacing \(\epsilon\) by a small factor times \(\epsilon\) at the beginning of the argument), this is exactly what is necessary to see that the closure of \(\mathcal F\) is close to finite.