Totally bounded metric spaces
In the theory of Metric and Topological Spaces, it is standard that compactness and sequential compactness are equivalent for metric spaces. Also, a metric space is compact if and only if it is both complete and totally bounded.
I was just thinking about this again, and wondering about conditions which are equivalent to total boundedness for metric spaces (without assuming completeness). I realised (and this is presumably well known) that a metric space \(X\) is totally bounded if and only if the following condition holds:
(CS)\(\quad\)Every sequence in \(X\) has a Cauchy subsequence.This is a slightly weakened form of sequential compactness that I haven't seen before myself, but might be useful. I don't know a name for that condition, but it is equivalent to the completion being sequentially compact, which gives one approach to proving the equivalence: we can apply the standard result to the completion of \(X\). However, instead I want to look directly at the equivalence of (CS) and total boundedness, as that may give some more insight into the standard result.
In the usual proof that sequentially compact implies totally bounded, we note that if a metric space \((X,d)\) is not totally bounded, then \(X\) is non-empty and there is an \(\varepsilon>0\) such that there is no finite collection of \(\varepsilon\)-balls in \(X\) whose union is equal to \(X\). We can then choose inductively a sequence \((x_n)_{n=1}^\infty\) in \(X\) with the property that, for all \(n\in\mathbb{N}\), we have
\(\qquad\displaystyle x_{n+1} \in X \setminus \bigcup_{k=1}^n B(x_k,\varepsilon)\,.\)This sequence then has the property that, for all \(m,n \in \N\) with \(m \neq n\), we have
\(\qquad d(x_m,x_n) \geq \varepsilon\,.\)At this point we usually note that this sequence has no convergent subsequence, and so \(X\) is not sequentially compact. But in fact this sequence has no Cauchy subsequence, so we have proved the stronger fact that (CS) fails.
Thus if (CS) holds then \(X\) is totally bounded.
The usual proof that complete and totally bounded implies sequentially compact actually goes via the following argument.
Let \((X,d)\) be a totally bounded metric space and let \((x_n)_{n=1}^\infty\) be a sequence in \(X\). Then, for all \(\varepsilon>0\), there exists an \(\varepsilon\)-ball \(B\) in \(X\) such that infinitely many terms of the sequence lie in \(B\), i.e.
\((*)\qquad\)\(\{n \in \mathbb{N}:x_n \in B\,\}\) is an infinite set.
(This comes simply from writing \(X\) as a finite union of \(\varepsilon\)-balls, and noting that at least one of those balls must contain infinitely many terms of the sequence.)
Of course \((*)\) is the same as saying that the sequence \((x_n)\) has a subsequence which lies entirely in \(B\). Rewriting this, using 'vector' notation for infinite sequences, we obtain the following.
Let \((X,d)\) be a totally bounded metric space. Then, for all \(\varepsilon > 0\), we have:
(S)\(\qquad\) For every infinite sequence \(\mathbf{x}\) in \(X\), there exists an open \(\varepsilon\)-ball \(B\) in \(X\) such that some subsequence of \(\mathbf{x}\) lies entirely in \(B\).
We can then apply this result repeatedly, with \(\varepsilon=1,1/2, 1/3,\dots\), but each time (inductively) taking a subsequence of the previous subsequence. We need some good notation for this, and there are various approaches we can take.
Let \((X,d)\) be a totally bounded metric space and let \((x_n)_{n=1}^\infty\) be a sequence in \(X\).
Set \(\mathbf{x}^{(0)} = (x_n)_{n=1}^\infty\).
We choose inductively a sequence of open balls \(B_n\) and successive subsequences \(\mathbf{x}^{(n)}\) as follows.
Applying (S) with \(\varepsilon=1\), we choose an open ball \(B_1\) of radius \(1\) and a subsequence \(\mathbf{x}^{(1)}\) of \(\mathbf{x}^{(0)}\) such that \(\mathbf{x}^{(1)}\) lies entirely in \(B_1\). Then, for each \(m \in \N\), having chosen open balls \(B_1,B_2,...,B_m\) and subsequences \(\mathbf{x}^{(1)},\dots,\mathbf{x}^{(m)}\) we apply (S) to \(\mathbf{x}^{(m)}\) with \(\varepsilon=1/(m+1)\) and choose an open ball \(B_{m+1}\) of radius \(1/(m+1)\) and a subsequence \(\mathbf{x}^{(m+1)}\) of \(\mathbf{x}^{(m)}\) such that \(\mathbf{x}^{(m+1)}\) lies entirely inside \(B_{m+1}\).
We now take a 'diagonal subsequence' \((y_k)_{k=1}^\infty\) where, for each \(k \in \N\), \(y_k\) is the \(k\)-th term of the sequence \(\mathbf{x}^{(k)}\).
[This resembles part of Cantor's diagonal argument, but we don't change this diagonal term!]
This sequence \((y_k)\) is a subsequence of the original sequence, and it has the property that, for each \(N \in \N\) and all \(k \geq N\), \(y_k \in B_N\). It follows that \((y_k)\) is a Cauchy sequence, and so we have proven that \(X\) satisfies (CS).
Thus every totally bounded metric space satisfies (CS).
[In the usual proof, we would be assuming completeness in addition to total boundedness, so that the sequence \((y_n)\) would then be a convergent subsequence of \((x_n)\).]
Alternative: We could use the fact that every subset of a totally bounded metric space is also totally bounded. That allows us to choose inductively a sequence of open balls \(B_k\) of radius \(1/k\) with the property that, for all \(m \in \N\), infinitely many terms of the original sequence \((x_n)\) lie in the set \(Y_m\), where
\(\qquad\displaystyle Y_m=\bigcap_{k=1}^m B_k\).
We then simply choose natural numbers \(n_1<n_2<\dots\) so that , for each \(m \in \N\), we have \(x_{n_m} \in Y_m\). The subsequence \((x_{n_m})_{m=1}^\infty\) is then Cauchy in \(X\). That is maybe a bit easier than taking a diagonal subsequence (and looks like one of the standard proofs of the Bolzano-Weierstrass Theorem).
Of course the balls \(B_k\) we chose in our first version of the proof also work for the second version!
Updated:
From the arguments above, we see the following.
Let \((X,d)\) be a metric space. Then the following statements are equivalent.
(a) \(X\) is not totally bounded.
(b) There exists \(\varepsilon > 0\) and a sequence \((x_n)_{n=1}^\infty\) in \(X\) such that, for all \(m,n \in \mathbb{N}\) with \(m \neq n\), we have
\(\qquad d(x_m,x_n) \geq \varepsilon.\)
(c) There is a sequence \((x_n)_{n=1}^\infty\) in \(X\) such that \((x_n)\) has no Cauchy subsequence.
Now we saw that it was quite quick to prove that (a) implies (b) (though we did make infinitely many choices along the way), and (b) implies (c) is also easy.
(b) implies (a) is also quite easy because, given the \(\varepsilon\) and sequence from (b), it is impossible to cover \(X\) with finitely many open \(\varepsilon/2\) balls. (No such ball can contain more than one of the infinitely many points \(x_n\))
But is there a quick way to show that (c) implies (b)? Certainly for individual sequences \((x_n)\) we only have a one-way implication.
Let \((X,d)\) be a metric space, and let \((x_n)\) be a sequence in \(X\).
If there exists \(\varepsilon > 0\) such that, for all \(m,n \in \mathbb{N}\) with \(m \neq n\), we have
\(\qquad d(x_m,x_n) \geq \varepsilon\,,\)
then \((x_n)\) has no Cauchy subsequence.
However, the converse here is false, as you can see e.g. from the following sequence in \(\mathbb{R}\):
\(\qquad1,1.1,2,2.01,3,3.001,4,4.0001,\dots\)
(Or even the sequence \(1,1,2,2,3,3,4,4,\dots\), but somehow that feels like cheating!)
It would be good to have a simple condition on a single sequence that is equivalent to the sequence having no Cauchy subsequence. If we are allowed to work with the completion, we can sort of do it, because we know that \((x_n)\) has a Cauchy subsequence if and only if it has a subsequence which converges in the completion. Denoting closure of a set in the completion by \(\mathrm{clos}^*\), this tells us that \((x_n)\) has no Cauchy subsequence if and only if
\(\qquad \displaystyle\bigcap_{n\in \N} \mathrm{clos}^*\{x_n,x_{n+1},x_{n+2},\dots\} = \emptyset\,.\)
I feel like there should be some condition like: every subsequence \((y_n)\) of \((x_n)\) has a subsequence \((z_n)\) such that there exists \(\varepsilon>0\) with the property that ...
But that will take a bit more thought. I expect I am reinventing the wheel here!
Let me make an intial guess, but giving a made-up name to the \(\varepsilon\) condition above.
Let us say that a sequence \((x_n)\) is well-separated [or, see below, (more standard) uniformly separated] if there exists \(\varepsilon > 0\) such that, for all \(m,n \in \mathbb{N}\) with \(m \neq n\), we have
\(\qquad d(x_m,x_n) \geq \varepsilon\,.\)
The easy implication used above is that, if \((x_n)\) is well-separated, then \((x_n\)) has no Cauchy subsequence.
My current guess is that \((x_n)\) has no Cauchy subsequence if and only if every subsequence \((y_n)\) of \((x_n)\) has a well-separated subsequence \((z_n)\).
Aha! Some Googling of variations on this made-up terminology (eventually I found something for "uniformly separated") led me to
So, rebranding "well-separated" as "uniformly separated", my "conjecture" now is that \((x_n)\) has no Cauchy subsequence if and only if for every subsequence \((y_n)\) of \((x_n)\), \((y_n)\) has a uniformly separated subsequence \((z_n)\). I think that is probably right! (But to prove (c) implies (b) above it is enough to know that if a sequence has no Cauchy subsequence, then it has a uniformly separated subsequence, which is easier.)
Taking the contrapositive, my claim is that a sequence \((x_n)\) has a Cauchy subsequence if and only if it has a subsequence \((y_n)\) which has no uniformly separated subsequence. This looks very plausible, and is presumably well known!
I'll return to this in my next post when I've figured out the details.
Comments
Post a Comment