We say that a metric space $M$ is totally bounded if for every $\epsilon>0$, there exist $x_1,\ldots,x_n\in M$ such that $M=B_\epsilon(x_1)\cup\ldots\cup B_\epsilon(x_n)$.

A metric space in which every sequence has a Cauchy subsequence is said to be conditionally compact. Prove that a metric space $M$ is conditionally compact if and only if $M$ is totally bounded.

So suppose $M$ is totally bounded, and given a sequence $y_1,y_2,\ldots$ in $M$. I want to find a Cauchy subsequence. For any $\epsilon$, I can find $x_1,\ldots,x_n\in M$ such that $M=B_\epsilon(x_1)\cup\ldots\cup B_\epsilon(x_n)$. So some ball contains infinitely many points $y_i$. Those points are within $2\epsilon$ of each other. But this still doesn't give me a Cauchy subsequence, because as $\epsilon$ decreases, the balls can change...

  • $\begingroup$ But if $S$ is the set of points you just found, for $\epsilon'<\epsilon$ one of the balls will contain infinitely many points of $S$, and so on. $\endgroup$ – Seirios Jun 20 '13 at 20:52
  • $\begingroup$ Minor nitpick: First you talk about a sequence $(x_n)$ in $M$, then you say you can find points $x_1,\dotsc,x_n \in M$. But the latter $x_i$ are not elements of the sequence. You should be careful and try not to accidentally reuse symbols like that. $\endgroup$ – kahen Jun 20 '13 at 21:02
  • $\begingroup$ @Seirios I see. So choose one point from $S$. Then for $\epsilon/2$, one of the balls $S'$ of radius $\epsilon/2$ contains infinitely many points of $S$. Choose one point from $S'$. Then for $\epsilon/4$, one of the balls $S''$ of radius $\epsilon/4$ contains infinitely many points of $S'$. Choose one point from $S''$, and so on. $\endgroup$ – PJ Miller Jun 20 '13 at 21:07
  • $\begingroup$ @kahen Ok I'll edit. $\endgroup$ – PJ Miller Jun 20 '13 at 21:07

HINT: Let $\langle x_k:k\in\Bbb N\rangle$ be any sequence in $M$, and suppose that $n\in\Bbb Z^+$. There is a finite $F\subseteq M$ such that $M=\bigcup_{x\in F}B\left(x,\frac1n\right)$, so there is a $y_n\in M$ such that $\left\{k\in\Bbb N:x_k\in B\left(y_n,\frac1{2n}\right)\right\}$ is infinite. Use this observation, which you’ve already made, in the following way.

Start with any sequence $\sigma_0=\langle x_k:k\in\Bbb N\rangle$. There are a $y_1\in M$ and an infinite $A_1\subseteq\Bbb N$ such that $d(x_k,y_1)<\frac12$ for each $k\in A_1$. Let $\ell_1=\min A_1$, let $A_1'=A_1\setminus\{\ell_1\}$, and let $\sigma_1$ be the subsequence $\langle x_k:k\in A_1'\rangle$. Note that $d(x_i,x_j)<1$ for all $i,j\in A_1$.

Now repeat the process with $\sigma_1$: there are a $y_2\in M$ and in infinite $A_2\subseteq A_1'$ such that $d(x_k,y_2),\frac14$ for each $k\in A_2$. Let $\ell_2=\min A_2$, let $A_2'=A_2\setminus\{\ell_2\}$, and let $\sigma_2$ be the subsequence $\langle x_k:k\in A_2'\rangle$ of $\sigma_1$. Note that $\ell_2>\ell_1$ and $d(x_i,x_j)<\frac12$ for all $i,j\in A_2$.

You should now be able to repeat the construction of the previous paragraph in general, going from a sequence $\sigma_i=\langle x_k:k\in A_i'\rangle$ to a subsequence $\sigma_{i+1}=\langle x_k:k\in A_{i+1}'\rangle$. Along the way you’ll construct a strictly increasing sequence $\langle\ell_i:i\in\Bbb Z^+\rangle$ of natural numbers $\ell_i=\min A_i$. Show that $\langle x_{\ell_i}:i\in\Bbb Z^+\rangle$ is a Cauchy subsequence of $\sigma_0$.

This is an example of a fairly common kind of recursive construction, starting with a sequence, producing a sequence of subsequences that have nicer and nicer properties, and then ‘diagonalizing’ to get a single subsequence that combines the nice properties of the original family of subsequences.

And I see that while I was typing, PJ Miller has given a fine argument for the other direction.


The backward direction is proved in the comment. Here's the forward direction:

Suppose $M$ is conditionally compact. Fix $\epsilon$. Every sequence has a Cauchy subsequence. Choose $x_1\in M$. If $B_\epsilon(x_1)$ doesn't cover $M$, choose $x_2$ in $M-B_\epsilon(x_1)$. Note that $d(x_2,x_1)\ge\epsilon$. If $B_\epsilon(x_1)\cup B_\epsilon(x_2)$ doesn't cover $M$, choose $x_3$ in $M-B_\epsilon(x_1)-B_\epsilon(x_2)$. Note that $d(x_3,x_1),d(x_3,x_2)\ge\epsilon$. If this process doesn't terminate, we get a sequence $x_1,x_2,\ldots$ such that $d(x_i,x_j)\ge\epsilon$ for all $i,j$. This sequence clearly has no Cauchy subsequence.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.