A Short Introduction to Metric Spaces
Section 5: Completeness
We have seen that every compact subset of a metric space is closed and bounded. However, we have noted that not every closed, bounded set is compact. Exercise 4.6 showed that in fact every compact set is "totally bounded." In this section, we look at a complete characterization of compact sets: A set is compact if and only if it is "complete" and totally bounded. Some of the proofs, which can get somewhat complicated, will be omitted.
To define completeness, we need to introduce Cauchy sequences. A sequence has a limit if its terms get close to some point. A sequence is Cauchy is its terms "get close to each other." A metric space is complete if every Cauchy sequence has a limit. The idea is that a Cauchy sequence looks like it should be converging to something, and a space is complete if there is always something there for it to converge to.
Definition 5.1: Let $(M,d)$ be a metric space. A sequence, $\{x_i\}_{i=1}^\infty,$ of elements of $M$ is said to be a Cauchy sequence if and only if for any $\varepsilon>0,$ there is an integer $N$ such that if $n$ and $m$ are integers greater than or equal to $N,$ then $d(x_n,x_m)<\varepsilon.$
Theorem 5.1: Any convergent sequence in any metric space is a Cauchy sequence.
Proof: Let $\seq x$ be an infinite sequence in a metric space $(M,d),$ and suppose that $\seq x$ converges to $z.$ Let $\varepsilon>0.$ There is an integer $N$ such that for every $i\ge N,$ $d(x_i,z)<\frac{\varepsilon}{2}.$ But then, for every $n,m\ge N,$ $d(x_n,x_m)\le d(x_n,z)+d(z,x_m) < \frac{\varepsilon}{2}+\frac{\varepsilon}{2}=\varepsilon.$ This proves that $\seq x$ is Cauchy. ∎
Definition 5.3: A metric space $(M,d)$ is said to be complete if and only if every Cauchy sequence of elements of $M$ converges to an element of $M.$
A major example of complete metric space is $\R,$ with its usual metric. Our proof uses the least upper bound axiom.
Theorem 5.2: The metric space $(\R,d)$ is complete.
Proof: Let $\seq x$ be a Cauchy sequence in $\R.$ We must show that $\seq x$ is convergent. Define $X=\{z\in \R\,|\,(-\infty,z)$ contains $x_i$ for only finitely many $i\,\}.$ The set $X$ is non-empty and bounded. To see this, let $N$ be an integer such that $|x_n-x_m|<1$ for all $n,m\ge N.$ Then there are only finitely many $i$ such that the distance from $x_i$ to $x_N$ is greater than 1. It follows that $x_N-1\in X$ and $x_N+1$ is an upper bound for $X.$ By the least upper bound axiom, $X$ has a least upper bound. Let $\lambda$ be the least upper bound of X. We will show that $\seq x$ converges to $\lambda.$
Let $\varepsilon>0.$ We first show that the interval $\big(\lambda-\frac{\varepsilon}{2},\lambda+\frac{\varepsilon}{2}\big)$ contains $x_i$ for infinitely many $i.$ In fact, $\big(-\infty,\lambda-\frac{\varepsilon}{2}\big]$ contains $x_i$ for only finitely many $i$ (since otherwise, $\lambda-\frac{\varepsilon}{2}$ would be an upper bound for $X,$ contradicting the fact that $\lambda$ is the least upper bound). And $\big(-\infty,\lambda+\frac{\varepsilon}{2}\big)$ contains $x_i$ for infinitely many $i$ (since otherwise, $\lambda+\frac{\varepsilon}{2}$ would be an element of $X,$ contradicting the fact that $\lambda$ is an upper bound for $X$). If follows that $\big(\lambda-\frac{\varepsilon}{2},\lambda+\frac{\varepsilon}{2}\big),$ which is $\big(-\infty,\lambda+\frac{\varepsilon}{2}\big)\smallsetminus \big(-\infty,\lambda-\frac{\varepsilon}{2}\big],$ contains $x_i$ for infinitely many $i.$
Now, choose an integer $N_1$ such that $|x_n-x_m|<\frac{\varepsilon}{2}$ for all $n,m\ge N_1.$ Since $\big(\lambda-\frac{\varepsilon}{2},\lambda+\frac{\varepsilon}{2}\big)$ contains $x_i$ for infinitely many $i,$ there must be some $N_2\ge N_1$ such that $x_{N_2}\in \big(\lambda-\frac{\varepsilon}{2},\lambda+\frac{\varepsilon}{2}\big),$ that is, $|x_{N_2}-\lambda|<\frac{\varepsilon}{2}.$ Then for any $n\ge N_2,$ we have $|x_n-\lambda| \le |x_n-x_{N_2}|+|x_{N_2}-\lambda|$ $< \frac{\varepsilon}{2} + \frac{\varepsilon}{2} = \varepsilon.$ This proves that $\seq x$ converges to $\lambda.$ ∎
A closed subset of a complete metric space is itself complete, when considered as a subspace using the same metric, and conversely. Note that this means, for example, that a closed interval in $\R$ is a complete metric space.
Theorem 5.3: Let $(M,d)$ be a complete metric space, and let $X$ be a subset of $M.$ The subspace $(X,d)$ is a complete metric space if and only if $X$ is a closed subset of $M.$
Proof: Note that, since the distance measure in the subspace $X$ is the same as the distance measure in $M,$ a sequence of points of $X$ is Cauchy in $(X,d)$ if and only if it is Cauchy in $(M,d)$.
Suppose that $X$ is complete. By Theorem 1.4, we can show that $X$ is closed by showing that it contains all of its accumulation points. Let $z$ be an accumulation point of $X$. For $n=1,2,3,\dots,$ there is an $x_n\in B_{1/n}(z)\cap X$. The sequence $\seq x$ converges to $z.$ By Theorem 5.1, it is a Cauchy sequence. Since $X$ is complete, it must converge to an element of $X.$ So, $z\in X.$.
Conversely, suppose that $X$ is closed. Let $\seq x$ be a Cauchy sequence of points of $X.$ We must show that $\seq x$ converges to a point in $X.$ Since $M$ is complete, $\seq x$ converges to a point $z$ in $M$. Since $z$ is a limit of a sequence of points in $X,$ $z$ is an accumulation point of $X.$ And then, since $X$ is closed, $z\in X.$ ∎
We now turn to the relationship between completeness and compactness. These two concepts are not the same; for example, $\R$ is complete but not compact. However, it is true that any compact metric space is complete.
Theorem 5.4: Let $(K,d)$ be a compact metric space. Then $(K,d)$ is a complete metric space.
Proof: Suppose $(K,d)$ is compact. Let $\{x_n\}_{n=1}^\infty$ be a Cauchy sequence in $K.$ We show that $\{x_n\}_{n=1}^\infty$ converges, thus proving $K$ is complete. By Theorem 4.6, this sequence has a subsequence that converges to some element $z$ in $K.$ By Exercise 5.2, the sequence itself must converge to $z$. ∎
We can get a full characterization of compactness by adding an additional property to completeness. Exercise 4.6 showed that every compact metric space is "totally bounded." In fact, a metric space is compact if and only if it is both complete and totally bounded. We start with the formal definition of totally bounded, followed by a statement of the theorem that compactness is equivalent to being complete and totally bounded. We will not prove the theorem.
Definition 5.4 A metric space $(M,d)$ is said to be totally bounded if for every $\varepsilon>0,$ there is a finite subset $\{x_1,x_2,\dots,x_n\}$ of $M$ (for some $n$) such that $\{B_\varepsilon(x_1),B_\varepsilon(x_2),\dots,B_\varepsilon(x_n)\}$ is an open cover of $M.$
Theorem 5.5: A metric space is compact if and only if it is both complete and totally bounded.
As noted in Section 4, every closed, bounded subset of $\R$ is compact. We can now see that this is true because every closed subset of $\R$ is complete, and every bounded subset of $\R$ is totally bounded, as is shown by the following theorem:
Theorem 5.6: Every bounded subset of $\R$ is totally bounded.
Proof: Let $X$ be a bounded subset of $\R.$ Let $\varepsilon>0.$ Then $X\subseteq [a,b]$ for some closed, bounded interval $[a,b].$ The interval $[a,b]$ can be covered with a finite number of open subintervals of length $\varepsilon,$ and those subintervals will also cover $X.$ ∎
Accepting our new characterization of compactness as true, we are in a position to prove the converse of Theorem 4.5. That is, a metric space is compact if every infinite subset has an accumulation point. We can also add another equivalent condition that uses sequences, as well as the condition from Theorem 5.5:
Theorem 5.7: Let $(M,d)$ be a metric space. The following statements are equivalent:
- $M$ is compact. (That is, every open cover of $M$ has a finite subcover.)
- Every infinite subset of $M$ has an accumulation point.
- Every infinite sequence in $M$ has a convergent subsequence.
- M is complete and totally bounded.
Proof: The implication $(1)\Rightarrow(2)$ is Theorem 4.5, while $(1)\Rightarrow(3)$ was proved as Theorem 4.6, and $(1)\Leftrightarrow(4)$ is Theorem 5.5.
To prove $(3)\Rightarrow(4),$ suppose that every infinite sequence in $M$ has a convergent subsequence. To show $M$ is complete, let $\{x_i\}_{i=1}^\infty$ be a Cauchy sequence in $M.$ By the assumption, it has a convergent subsequence. By Exercise 5.2, $\{x_i\}_{i=1}^\infty$ is also convergent, to the same limit. So, $M$ is complete. We use proof by contradiction to show that $M$ is totally bounded. Suppose that $M$ is not totally bounded. Then there is an $\varepsilon>0$ such that $M$ cannot be covered by a finite number of open balls of radius $\varepsilon.$ Let $x_1\in M.$ Since $M$ is not covered by $B_\varepsilon(x_1),$ there is an $x_2\in M$ such that $d(x_2,x_1)\ge\varepsilon.$ Since $B_\varepsilon(x_1)$ and $B_\varepsilon(x_2)$ do not cover $M,$ there is an $x_3\in M$ such that $d(x_3,x_1)\ge\varepsilon$ and $d(x_3,x_2)\ge\varepsilon.$ Since $B_\varepsilon(x_1)$, $B_\varepsilon(x_2)$, and $B_\varepsilon(x_3)$ do not cover $M,$ there is an $x_4\in M$ such that $d(x_4,x_1)\ge\varepsilon$, $d(x_4,x_2)\ge\varepsilon$ and $d(x_4,x_3)\ge\varepsilon.$ Continuing in this way, we get a sequence $\{x_n\}_{n=1}^\infty$ such that the distance between each $x_n$ and any one of $x_1,x_2,\dots,x_{n-1}$ is greater than or equal to $\varepsilon.$ But no subsequence of such a sequence can be convergent, contradicting the assumption.
To complete the proof, we can show that $(2)\Rightarrow(3).$ But that is left as Exercise 5.3 ∎
We finish by looking briefly at something that can be done with Cauchy sequences in metric spaces that are not necessarily complete. Let $(M,d)$ be any metric space. Start with the set $\mathscr C(M)$ whose elements are all the Cauchy sequences in $M.$ Define a relation, $\sim,$ on $\mathscr C(M)$ by $\{a_i\}_{i=1}^\infty \sim \{b_i\}_{i=1}^\infty$ if and only if $\displaystyle \lim_{i\to\infty}d(a_i,b_i)=0.$ This relation is an equivalence relation on $\mathscr C(M).$ (The proof is left as Exercise 5.5.) Now, consider the set $\mathscr C[M]$ of equivalence classes in $\mathscr C(M)$ under that relation. We can define a metric $\partial$ on $\mathscr C[M]$ by $\partial\big(\big[\{x_i\}_{i=1}^\infty\big],\big[\{y_i\}_{i=1}^\infty\big]\big) =\displaystyle\lim_{i\to\infty}d(x_i,y_i).$ (The long proof that $\partial$ is well-defined and is a metric is left as Exercise 5.6, if you want to tackle it.) This gives us a new metric space, $(\mathscr C[M],\partial).$
We can define a function $f\colon M\to \mathscr C[M]$ by letting $f(x)$ be the equivalence class of the constant sequence in which every term is $x$; that is, $f(x)=\big[\{x\}_{i=1}^\infty\big].$ This function has the property that $\partial(f(x),f(y))=d(x,y).$ It is clearly continuous and one-to-one, and it allows us to identify the metric space $(M,d)$ with the subspace $f(M)$ of $(\mathscr C[M],\partial).$
Things get even more complicated after that, so I won't go into any further details here. However, it can be shown that $(\mathscr C[M],\partial)$ is a complete metric space and that $f(M)$ is dense in $\mathscr C[M].$ And if the metric space $(M,d)$ is already complete, then $(\mathscr C[M],\partial)$ is essentially just a copy of $M,$ since in that case the function $f$ is an isometry — a bijection that preserves distance. The space $(\mathscr C[M],\partial)$ is said to be the completion of $(M,d).$
If we start with the rational numbers, $\Q,$ with their usual metric, it turns out that $\mathscr C[\Q]$ is isometric with $\R.$ This means that it is possible to define $\R$ as the completion of $\Q,$ that is, as a set of equivalence classes of Cauchy sequences of rational numbers.
Exercises
Exercise 5.1 Consider the open interval $I=(0,1)$ as a subspace of $(\R,d).$ Show that $\big\{\frac1n\big\}_{n=1}^\infty$ is a Cauchy sequence in $I$ that does not converge (to a point in $I$). Consider the rational numbers $\Q$ as a subspace of $(\R,d).$ Find a Cauchy sequence in $\Q$ that does not converge (to a point in $\Q$). (This exercise shows that $I$ and $\Q$ are not complete metric spaces.)
Exercise 5.2 Suppose that $\{x_n\}_{n=1}^\infty$ is a Cauchy sequence in some metric space $(M,d),$ and suppose that the sequence has a subsequence that converges to $z\in M.$ Show that $\{x_n\}_{n=1}^\infty$ converges to $z.$
Exercise 5.3 Complete the proof of Theorem 5.7 by proving that if every infinite subset of a metric space has an accumulation point, then every infinite sequence in that metric space has a convergent subsequence. Hint: Consider two cases: the sequence contains only finitely many different terms, and the sequence contains an infinite number of different terms.
Exercise 5.6 Let $(M,d)$ be a metric space. A function $f\colon M\to M$ is said to be a contraction if there is a number $r$ with $0\le r<1$ such that for any $x\in M$ and $y\in M,$ $d(f(x),f(y))\le r\cdot d(x,y).$
- Show that any contraction is continuous.
- Let $f$ be a contraction on a metric space $(M,d),$ and let $x\in M.$ Show that the sequence $\{x,f(x),f(f(x)),f(f(f(x))),\dots,f^{\circ n}(x),\dots\}$ is Cauchy, where $f^{\circ n}$ is the composition of $f$ with itself $n$ times. Outline of proof: Start by showing by induction that $d(f^{\circ (i+1)}(x),f^{\circ i}(x)) \le r^i\cdot d(f(x),x).$ Next, use the triangle inequality to show that for $n>m$, $d(f^{\circ n}(x),f^{\circ m}(x)) \le \big(\sum_{i=m}^{n-1} r^i\big)\cdot d(f(x),x)$. Next, note that if $0<r<1$ and $n> m,$ then $\sum_{i=m}^{n-1} r^i =r^m\cdot\sum_{k=0}^{n-m-1}r^k$ $< r^m\cdot\sum_{k=0}^\infty r^k = r^m\cdot\frac{1}{1-r},$ and use that fact to get $d(f^{\circ n}(x),f^{\circ m}(x)) < \frac{d(f(x),x)}{1-r}r^m.$ Finally, use this inequality to show that the sequence is Cauchy.
- Suppose $(M,d)$ is a complete metric space and $f\colon M\to M$ is a contraction. Let $x\in M.$ Part (b) then implies that $\displaystyle \lim_{n\to\infty}f^{\circ n}(x)$ exists. Let $z=\displaystyle \lim_{n\to\infty}f^{\circ n}(x).$ Show $z$ is a fixed point of $f,$ that is, $f(z)=z.$
- Suppose $(M,d)$ is a non-empty complete metric space and $f\colon M\to M$ is a contraction. Show that $f$ has a unique fixed point and that for every $x\in M,$ the sequence $\{f^{\circ n}(x)\}_{n=0}^\infty$ converges to that fixed point. This is the Contraction Theorem for complete metric spaces.
Exercise 5.5 Let $(M,d)$ be metric space. Show that the relation $\sim$ on $\mathscr C(M)$ is an equivalence relation.
Exercise 5.6 Show that $\partial$ is a well-defined function on $\mathscr C[M]\times \mathscr C[M].$ That is, show that if $\{a_i\}_{i=1}^\infty \sim\{b_i\}_{i=1}^\infty$ and $\{x_i\}_{i=1}^\infty\sim\{y_i\}_{i=1}^\infty,$ then $\partial\big(\big[\{a_i\}_{i=1}^\infty\big],\big[\{x_i\}_{i=1}^\infty\big]\big) = \partial\big(\big[\{b_i\}_{i=1}^\infty\big],\big[\{y_i\}_{i=1}^\infty\big]\big).$ Then show $\partial$ is a metric. [This is a long and non-trivial exercise!]