# Conditional compactness iff totally bounded

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...

• 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. – Seirios Jun 20 '13 at 20:52
• 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. – kahen Jun 20 '13 at 21:02
• @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. – PJ Miller Jun 20 '13 at 21:07
• @kahen Ok I'll edit. – 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.