8.4: Completeness and Compactness
- Page ID
- 6793
Cauchy sequences and completeness
Just like with sequences of real numbers we can define Cauchy sequences.
Let \((X,d)\) be a metric space. A sequence \(\{ x_n \}\) in \(X\) is a Cauchy sequence if for every \(\epsilon > 0\) there exists an \(M \in {\mathbb{N}}\) such that for all \(n \geq M\) and all \(k \geq M\) we have \[d(x_n, x_k) < \epsilon .\]
The definition is again simply a translation of the concept from the real numbers to metric spaces. So a sequence of real numbers is Cauchy in the sense of if and only if it is Cauchy in the sense above, provided we equip the real numbers with the standard metric \(d(x,y) = \left\lvert {x-y} \right\rvert\).
Let \((X,d)\) be a metric space. We say that \(X\) is complete or Cauchy-complete if every Cauchy sequence \(\{ x_n \}\) in \(X\) converges to an \(x \in X\).
The space \({\mathbb{R}}^n\) with the standard metric is a complete metric space.
For \({\mathbb{R}}= {\mathbb{R}}^1\) this was proved in .
Take \(n > 1\). Let \(\{ x^j \}_{j=1}^\infty\) be a Cauchy sequence in \({\mathbb{R}}^n\), where we write \(x^j = \bigl(x_1^j,x_2^j,\ldots,x_n^j\bigr) \in {\mathbb{R}}^n\). As the sequence is Cauchy, given \(\epsilon > 0\), there exists an \(M\) such that for all \(i,j \geq M\) we have \[d(x^i,x^j) < \epsilon.\]
Fix some \(k=1,2,\ldots,n\), for \(i,j \geq M\) we have \[\bigl\lvert x_k^i - x_k^j \bigr\rvert = \sqrt
Callstack:
at (Bookshelves/Analysis/Introduction_to_Real_Analysis_(Lebl)/08:_Metric_Spaces/8.04:_Completeness_and_Compactness), /content/body/div[1]/p[8]/span, line 1, column 1
Write \(x = (x_1,x_2,\ldots,x_n) \in {\mathbb{R}}^n\). By we have that \(\{ x^j \}\) converges to \(x \in {\mathbb{R}}^n\) and hence \({\mathbb{R}}^n\) is complete.
Compactness
Let \((X,d)\) be a metric space and \(K \subset X\). The set \(K\) is set to be compact if for any collection of open sets \(\{ U_{\lambda} \}_{\lambda \in I}\) such that \[K \subset \bigcup_{\lambda \in I} U_\lambda ,\] there exists a finite subset \(\{ \lambda_1, \lambda_2,\ldots,\lambda_k \} \subset I\) such that \[K \subset \bigcup_{j=1}^k U_{\lambda_j} .\]
A collection of open sets \(\{ U_{\lambda} \}_{\lambda \in I}\) as above is said to be a open cover of \(K\). So a way to say that \(K\) is compact is to say that every open cover of \(K\) has a finite subcover.
Let \((X,d)\) be a metric space. A compact set \(K \subset X\) is closed and bounded.
First, we prove that a compact set is bounded. Fix \(p \in X\). We have the open cover \[K \subset \bigcup_{n=1}^\infty B(p,n) = X .\] If \(K\) is compact, then there exists some set of indices \(n_1 < n_2 < \ldots < n_k\) such that \[K \subset \bigcup_{j=1}^k B(p,n_j) = B(p,n_k) .\] As \(K\) is contained in a ball, \(K\) is bounded.
Next, we show a set that is not closed is not compact. Suppose that \(\overline{K} \not= K\), that is, there is a point \(x \in \overline{K} \setminus K\). If \(y \not= x\), then for \(n\) with \(\nicefrac{1}{n} < d(x,y)\) we have \(y \notin C(x,\nicefrac{1}{n})\). Furthermore \(x \notin K\), so \[K \subset \bigcup_{n=1}^\infty C(x,\nicefrac{1}{n})^c .\] As a closed ball is closed, \(C(x,\nicefrac{1}{n})^c\) is open, and so we have an open cover. If we take any finite collection of indices \(n_1 < n_2 < \ldots < n_k\), then \[\bigcup_{j=1}^k C(x,\nicefrac{1}{n_j})^c = C(x,\nicefrac{1}{n_k})^c\] As \(x\) is in the closure, we have \(C(x,\nicefrac{1}{n_k}) \cap K \not= \emptyset\), so there is no finite subcover and \(K\) is not compact.
We prove below that in finite dimensional euclidean space every closed bounded set is compact. So closed bounded sets of \({\mathbb{R}}^n\) are examples of compact sets. It is not true that in every metric space, closed and bounded is equivalent to compact. There are many metric spaces where closed and bounded is not enough to give compactness, see for example .
A useful property of compact sets in a metric space is that every sequence has a convergent subsequence. Such sets are sometimes called sequentially compact. Let us prove that in the context of metric spaces, a set is compact if and only if it is sequentially compact.
[thm:mscompactisseqcpt] Let \((X,d)\) be a metric space. Then \(K \subset X\) is a compact set if and only if every sequence in \(K\) has a subsequence converging to a point in \(K\).
Let \(K \subset X\) be a set and \(\{ x_n \}\) a sequence in \(K\). Suppose that for each \(x \in K\), there is a ball \(B(x,\alpha_x)\) for some \(\alpha_x > 0\) such that \(x_n \in B(x,\alpha_x)\) for only finitely many \(n \in {\mathbb{N}}\). Then \[K \subset \bigcup_{x \in K} B(x,\alpha_x) .\] Any finite collection of these balls is going to contain only finitely many \(x_n\). Thus for any finite collection of such balls there is an \(x_n \in K\) that is not in the union. Therefore, \(K\) is not compact.
So if \(K\) is compact, then there exists an \(x \in K\) such that for any \(\delta > 0\), \(B(x,\delta)\) contains \(x_k\) for infinitely many \(k \in {\mathbb{N}}\). \(B(x,1)\) contains some \(x_k\) so let \(n_1 := k\). If \(n_{j-1}\) is defined, then there must exist a \(k > n_{j-1}\) such that \(x_k \in B(x,\nicefrac{1}{j})\), so define \(n_j := k\). Notice that \(d(x,x_{n_j}) < \nicefrac{1}{j}\). By , \(\lim\, x_{n_j} = x\).
For the other direction, suppose that every sequence in \(K\) has a subsequence converging in \(K\). Take an open cover \(\{ U_\lambda \}_{\lambda \in I}\) of \(K\). For every \(x \in K\), define \[\delta(x) := \sup \{ \delta \in (0,1) : B(x,\delta) \subset U_\lambda \text{ for some } \lambda \in I \} .\] As \(\{ U_\lambda \}\) is an open cover of \(K\), \(\delta(x) > 0\) for each \(x \in K\). By construction, for any positive \(\epsilon < \delta(x)\) there must exist a \(\lambda \in I\) such that \(B(x,\epsilon) \subset U_\lambda\).
Pick a \(\lambda_0 \in I\) and look at \(U_{\lambda_0}\). If \(K \subset U_{\lambda_0}\), we stop as we have found a finite subcover. Otherwise, there must be a point \(x_1 \in K \setminus U_{\lambda_0}\). There must exist some \(\lambda_1 \in I\) such that \(x_1 \in U_{\lambda_1}\) and in fact \(B\bigl(x_1,\frac{1}{2}\delta({x_1})\bigr) \subset U_{\lambda_1}\). We work inductively. Suppose that \(\lambda_{n-1}\) is defined. Either \(U_{\lambda_0} \cup U_{\lambda_1} \cup \cdots \cup U_{\lambda_{n-1}}\) is a finite cover of \(K\), in which case we stop, or there must be a point \(x_n \in K \setminus \bigl( U_{\lambda_1} \cup U_{\lambda_2} \cup \cdots \cup U_{\lambda_{n-1}}\bigr)\). In this case, there must be some \(\lambda_n \in I\) such that \(x_n \in U_{\lambda_n}\), and in fact \[B\bigl(x_n,\tfrac{1}{2}\delta(x_n)\bigr) \subset U_{\lambda_n}.\]
So either we obtained a finite subcover or we obtained an infinite sequence \(\{ x_n \}\) as above. For contradiction suppose that there was no finite subcover and we have the sequence \(\{ x_n \}\). Then there is a subsequence \(\{ x_{n_k} \}\) that converges, that is, \(x = \lim \, x_{n_k} \in K\). We take \(\lambda \in I\) such that \(B\bigl(x,\frac{1}{2}\delta(x)\bigr) \subset U_\lambda\). As the subsequence converges, there is a \(k\) such that \(d(x_{n_k},x) < \frac{1}{8}\delta(x)\). By the triangle inequality, \(B\bigl(x_{n_k},\frac{3}{8}\delta(x)\bigr) \subset B\bigl(x,\frac{1}{2}\delta(x)\bigr) \subset U_\lambda\). So \(\frac{3}{8}\delta(x) < \delta({x_{n_k}})\), which implies \[B\bigl(x_{n_k},\tfrac{3}{16}\delta(x)\bigr) \subset B\bigl(x_{n_k},\tfrac{1}{2}\delta(x_{n_k})\bigr) \subset U_{\lambda_{n_k}}.\] As \(\nicefrac{1}{8} < \nicefrac{3}{16}\), we have \(x \in B\bigl(x_{n_k},\frac{3}{16}\delta(x)\bigr)\), or \(x \in U_{\lambda_{n_k}}\). As \(\lim x_{n_j} = x\), for all \(j\) large enough we have \(x_{n_j} \in U_{\lambda_{n_k}}\) by . Let us fix one of those \(j\) such that \(j > k\). But by construction \(x_{n_j} \notin U_{\lambda_{n_k}}\) if \(j > k\), which is a contradiction.
By the Bolzano-Weierstrass theorem for sequences () we have that any bounded sequence has a convergent subsequence. Therefore any sequence in a closed interval \([a,b] \subset {\mathbb{R}}\) has a convergent subsequence. The limit must also be in \([a,b]\) as limits preserve non-strict inequalities. Hence a closed bounded interval \([a,b] \subset {\mathbb{R}}\) is compact.
Let \((X,d)\) be a metric space and let \(K \subset X\) be compact. Suppose that \(E \subset K\) is a closed set, then \(E\) is compact.
Let \(\{ x_n \}\) be a sequence in \(E\). It is also a sequence in \(K\). Therefore it has a convergent subsequence \(\{ x_{n_j} \}\) that converges to \(x \in K\). As \(E\) is closed the limit of a sequence in \(E\) is also in \(E\) and so \(x \in E\). Thus \(E\) must be compact.
[thm:msbw] A closed bounded subset \(K \subset {\mathbb{R}}^n\) is compact.
For \({\mathbb{R}}= {\mathbb{R}}^1\) if \(K \subset {\mathbb{R}}\) is closed and bounded, then any sequence \(\{ x_n \}\) in \(K\) is bounded, so it has a convergent subsequence by Bolzano-Weierstrass theorem for sequences (). As \(K\) is closed, the limit of the subsequence must be an element of \(K\). So \(K\) is compact.
Let us carry out the proof for \(n=2\) and leave arbitrary \(n\) as an exercise.
As \(K\) is bounded, there exists a set \(B=[a,b]\times[c,d] \subset {\mathbb{R}}^2\) such that \(K \subset B\). If we can show that \(B\) is compact, then \(K\), being a closed subset of a compact \(B\), is also compact.
Let \(\{ (x_k,y_k) \}_{k=1}^\infty\) be a sequence in \(B\). That is, \(a \leq x_k \leq b\) and \(c \leq y_k \leq d\) for all \(k\). A bounded sequence has a convergent subsequence so there is a subsequence \(\{ x_{k_j} \}_{j=1}^\infty\) that is convergent. The subsequence \(\{ y_{k_j} \}_{j=1}^\infty\) is also a bounded sequence so there exists a subsequence \(\{ y_{k_{j_i}} \}_{i=1}^\infty\) that is convergent. A subsequence of a convergent sequence is still convergent, so \(\{ x_{k_{j_i}} \}_{i=1}^\infty\) is convergent. Let \[x := \lim_{i\to\infty} x_{k_{j_i}} \qquad \text{and} \qquad y := \lim_{i\to\infty} y_{k_{j_i}} .\] By , \(\bigl\{ (x_{k_{j_i}},y_{k_{j_i}}) \bigr\}_{i=1}^\infty\) converges to \((x,y)\) as \(i\) goes to \(\infty\). Furthermore, as \(a \leq x_k \leq b\) and \(c \leq y_k \leq d\) for all \(k\), we know that \((x,y) \in B\).
Exercises
Let \((X,d)\) be a metric space and \(A\) a finite subset of \(X\). Show that \(A\) is compact.
Let \(A = \{ \nicefrac{1}{n} : n \in {\mathbb{N}}\} \subset {\mathbb{R}}\). a) Show that \(A\) is not compact directly using the definition. b) Show that \(A \cup \{ 0 \}\) is compact directly using the definition.
Let \((X,d)\) be a metric space with the discrete metric. a) Prove that \(X\) is complete. b) Prove that \(X\) is compact if and only if \(X\) is a finite set.
a) Show that the union of finitely many compact sets is a compact set. b) Find an example where the union of infinitely many compact sets is not compact.
Prove for arbitrary dimension. Hint: The trick is to use the correct notation.
Show that a compact set \(K\) is a complete metric space.
Let \(C([a,b])\) be the metric space as in . Show that \(C([a,b])\) is a complete metric space.
[exercise:msclbounnotcompt] Let \(C([0,1])\) be the metric space of . Let \(0\) denote the zero function. Then show that the closed ball \(C(0,1)\) is not compact (even though it is closed and bounded). Hints: Construct a sequence of distinct continuous functions \(\{ f_n \}\) such that \(d(f_n,0) = 1\) and \(d(f_n,f_k) = 1\) for all \(n \not= k\). Show that the set \(\{ f_n : n \in {\mathbb{N}}\} \subset C(0,1)\) is closed but not compact. See for inspiration.
Show that there exists a metric on \({\mathbb{R}}\) that makes \({\mathbb{R}}\) into a compact set.
Suppose that \((X,d)\) is complete and suppose we have a countably infinite collection of nonempty compact sets \(E_1 \supset E_2 \supset E_3 \supset \cdots\) then prove \(\bigcap_{j=1}^\infty E_j \not= \emptyset\).
Let \(C([0,1])\) be the metric space of . Let \(K\) be the set of \(f \in C([0,1])\) such that \(f\) is equal to a quadratic polynomial, i.e. \(f(x) = a+bx+cx^2\), and such that \(\left\lvert {f(x)} \right\rvert \leq 1\) for all \(x \in [0,1]\), that is \(f \in C(0,1)\). Show that \(K\) is compact.