Conditional compactness iff totally bounded

Question

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

Answer 1

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.

Answer 2

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.