8.4: Completeness and Compactness
( \newcommand{\kernel}{\mathrm{null}\,}\)
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 {xn} in X is a Cauchy sequence if for every ϵ>0 there exists an M∈N such that for all n≥M and all k≥M we have d(xn,xk)<ϵ.
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)=|x−y|.
Let (X,d) be a metric space. We say that X is complete or Cauchy-complete if every Cauchy sequence {xn} in X converges to an x∈X.
The space Rn with the standard metric is a complete metric space.
For R=R1 this was proved in .
Take n>1. Let {xj}∞j=1 be a Cauchy sequence in Rn, where we write xj=(xj1,xj2,…,xjn)∈Rn. As the sequence is Cauchy, given ϵ>0, there exists an M such that for all i,j≥M we have d(xi,xj)<ϵ.
Fix some k=1,2,…,n, for i,j≥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=(x1,x2,…,xn)∈Rn. By we have that {xj} converges to x∈Rn and hence Rn is complete.
Compactness
Let (X,d) be a metric space and K⊂X. The set K is set to be compact if for any collection of open sets {Uλ}λ∈I such that K⊂⋃λ∈IUλ, there exists a finite subset {λ1,λ2,…,λk}⊂I such that K⊂k⋃j=1Uλj.
A collection of open sets {Uλ}λ∈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⊂X is closed and bounded.
First, we prove that a compact set is bounded. Fix p∈X. We have the open cover K⊂∞⋃n=1B(p,n)=X. If K is compact, then there exists some set of indices n1<n2<…<nk such that K⊂k⋃j=1B(p,nj)=B(p,nk). As K is contained in a ball, K is bounded.
Next, we show a set that is not closed is not compact. Suppose that ¯K≠K, that is, there is a point x∈¯K∖K. If y≠x, then for n with \nicefrac1n<d(x,y) we have y∉C(x,\nicefrac1n). Furthermore x∉K, so K⊂∞⋃n=1C(x,\nicefrac1n)c. As a closed ball is closed, C(x,\nicefrac1n)c is open, and so we have an open cover. If we take any finite collection of indices n1<n2<…<nk, then k⋃j=1C(x,\nicefrac1nj)c=C(x,\nicefrac1nk)c As x is in the closure, we have C(x,\nicefrac1nk)∩K≠∅, 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 Rn 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⊂X is a compact set if and only if every sequence in K has a subsequence converging to a point in K.
Let K⊂X be a set and {xn} a sequence in K. Suppose that for each x∈K, there is a ball B(x,αx) for some αx>0 such that xn∈B(x,αx) for only finitely many n∈N. Then K⊂⋃x∈KB(x,αx). Any finite collection of these balls is going to contain only finitely many xn. Thus for any finite collection of such balls there is an xn∈K that is not in the union. Therefore, K is not compact.
So if K is compact, then there exists an x∈K such that for any δ>0, B(x,δ) contains xk for infinitely many k∈N. B(x,1) contains some xk so let n1:=k. If nj−1 is defined, then there must exist a k>nj−1 such that xk∈B(x,\nicefrac1j), so define nj:=k. Notice that d(x,xnj)<\nicefrac1j. By , limxnj=x.
For the other direction, suppose that every sequence in K has a subsequence converging in K. Take an open cover {Uλ}λ∈I of K. For every x∈K, define δ(x):=sup{δ∈(0,1):B(x,δ)⊂Uλ for some λ∈I}. As {Uλ} is an open cover of K, δ(x)>0 for each x∈K. By construction, for any positive ϵ<δ(x) there must exist a λ∈I such that B(x,ϵ)⊂Uλ.
Pick a λ0∈I and look at Uλ0. If K⊂Uλ0, we stop as we have found a finite subcover. Otherwise, there must be a point x1∈K∖Uλ0. There must exist some λ1∈I such that x1∈Uλ1 and in fact B(x1,12δ(x1))⊂Uλ1. We work inductively. Suppose that λn−1 is defined. Either Uλ0∪Uλ1∪⋯∪Uλn−1 is a finite cover of K, in which case we stop, or there must be a point xn∈K∖(Uλ1∪Uλ2∪⋯∪Uλn−1). In this case, there must be some λn∈I such that xn∈Uλn, and in fact B(xn,12δ(xn))⊂Uλn.
So either we obtained a finite subcover or we obtained an infinite sequence {xn} as above. For contradiction suppose that there was no finite subcover and we have the sequence {xn}. Then there is a subsequence {xnk} that converges, that is, x=limxnk∈K. We take λ∈I such that B(x,12δ(x))⊂Uλ. As the subsequence converges, there is a k such that d(xnk,x)<18δ(x). By the triangle inequality, B(xnk,38δ(x))⊂B(x,12δ(x))⊂Uλ. So 38δ(x)<δ(xnk), which implies B(xnk,316δ(x))⊂B(xnk,12δ(xnk))⊂Uλnk. As \nicefrac18<\nicefrac316, we have x∈B(xnk,316δ(x)), or x∈Uλnk. As limxnj=x, for all j large enough we have xnj∈Uλnk by . Let us fix one of those j such that j>k. But by construction xnj∉Uλnk 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]⊂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]⊂R is compact.
Let (X,d) be a metric space and let K⊂X be compact. Suppose that E⊂K is a closed set, then E is compact.
Let {xn} be a sequence in E. It is also a sequence in K. Therefore it has a convergent subsequence {xnj} that converges to x∈K. As E is closed the limit of a sequence in E is also in E and so x∈E. Thus E must be compact.
[thm:msbw] A closed bounded subset K⊂Rn is compact.
For R=R1 if K⊂R is closed and bounded, then any sequence {xn} 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]×[c,d]⊂R2 such that K⊂B. If we can show that B is compact, then K, being a closed subset of a compact B, is also compact.
Let {(xk,yk)}∞k=1 be a sequence in B. That is, a≤xk≤b and c≤yk≤d for all k. A bounded sequence has a convergent subsequence so there is a subsequence {xkj}∞j=1 that is convergent. The subsequence {ykj}∞j=1 is also a bounded sequence so there exists a subsequence {ykji}∞i=1 that is convergent. A subsequence of a convergent sequence is still convergent, so {xkji}∞i=1 is convergent. Let x:=limi→∞xkjiandy:=limi→∞ykji. By , {(xkji,ykji)}∞i=1 converges to (x,y) as i goes to ∞. Furthermore, as a≤xk≤b and c≤yk≤d for all k, we know that (x,y)∈B.
Exercises
Let (X,d) be a metric space and A a finite subset of X. Show that A is compact.
Let A={\nicefrac1n:n∈N}⊂R. a) Show that A is not compact directly using the definition. b) Show that A∪{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 {fn} such that d(fn,0)=1 and d(fn,fk)=1 for all n≠k. Show that the set {fn:n∈N}⊂C(0,1) is closed but not compact. See for inspiration.
Show that there exists a metric on R that makes R into a compact set.
Suppose that (X,d) is complete and suppose we have a countably infinite collection of nonempty compact sets E1⊃E2⊃E3⊃⋯ then prove ⋂∞j=1Ej≠∅.
Let C([0,1]) be the metric space of . Let K be the set of f∈C([0,1]) such that f is equal to a quadratic polynomial, i.e. f(x)=a+bx+cx2, and such that |f(x)|≤1 for all x∈[0,1], that is f∈C(0,1). Show that K is compact.