# Total boundedness, an equivalent expression

I'm trying to show that a metric space $(X,d)$ is totally bounded iff every sequence in $X$ has a Cauchy sub-sequence. This is a point that rose up the other day in another topic and it seemed like very nice thing to know.

The definition of total boundedness that I'm working with is that for every $\varepsilon >0$ there exists a finite collection $x_{1},...,x_{k}\in X$ so that $X=\cup_{n=1}^{k}B(x_{n},\varepsilon)$.

What I think I solved out so far is the proof from left to right, but I'm having trouble finishing the latter claim. Here's what I got from the first direction:

Suppose that $X$ is totally bounded and choose a sequence $(x_{n})_{n=1}^{\infty}$ of elements from $X$; we want to show that it has a Cauchy sub-sequence. Since $X$ is totally bounded there exists a collection $y_{1},...,y_{k_{1}}\in X$ such that $X=\cup_{n=1}^{k_{1}}B(y_{n},1)$, so there must exist an index $j_{1}\in\{1,...,k_{1}\}$ so that $x_{n}\in B(y_{j_{1}},1)=:A_{1}$ with infinitely many $n\in \mathbb{N}$. Total boundedness is hereditary so $A_{1}=\cup_{n=1}^{k_{2}}B(z_{n},\frac{1}{2})$ for some $z_{1},...,z_{k_{2}}\in A_{1}$. Again there exists $j_{2}\in \{1,...,k_{2}\}$ such that $x_{n}\in B(z_{j_{2}},\frac{1}{2})=:A_{2}$ for infinitely many $n\in \mathbb{N}$, and we will continue this process indefinitely. For each $i\in \mathbb{N}$ we find $A_{i}\subset X$ such that: $A_{i}=B(w_{i},\frac{1}{i})$ for some $w_{i}\in X$, $x_{n}\in A_{i}$ for infinitely many $n\in \mathbb{N}$ and $A_{i+1}\subset A_{i}$. For each $i\in \mathbb{N}$ we choose $x_{n_{i}}\in A_{i} \cap \{x_{n}\}_{n=1}^{\infty}$, which results a Cauchy sub-sequence $(x_{n_{i}})_{i=1}^{\infty}$. Adding few details and giving a more rigorous support for the last sentence, this should be fine?

I already tried several different things for the other direction, so I'd appreciate some fresh ideas there. Thanks for all the input in advance.

-
What about an indirect proof: Suppose $X$ is not totally bounded. This means there is an $\varepsilon>0$ such that there is no finite $\varepsilon$-net. Choose arbitrary $x_1$. Since $\{x_1\}$ is not an $\varepsilon$-net, there is $x_2$ such that $d(x_2,x_1)>\varepsilon$. Can you continue and construct a sequence $(x_n)$? Can you show that this sequence is not Cauchy? Can you show that no subsequence is Cauchy? – Martin Sleziak Jan 10 '12 at 22:23
Yeah, that seems to work. Continuing from there I would find $x_{3}$ so that $d(x_{3},x_{i})>\varepsilon$ for both $i\in \{1,2\}$, and for each $i\in \mathbb{N}$ I find $x_{i}\in X$ such that $d(x_{i},x_{j})> \varepsilon$ whenever $i\neq j$? This sequence can't be Cauchy, and the same property goes down to all of its sub-sequences. I think I can work from here, thanks alot! – T. Eskin Jan 10 '12 at 22:33

Your proof that $X$ totally bounded$\implies$ all sequences in $X$ have Cauchy sub-sequences looks fine (it should only take 1 line to verify that the sequence you've constructed is Cauchy). To get the other direction, assume that $X$ is not totally bounded, and so we have some $r>0$ such that no finite collection of open balls $B_r(x),x\in X$ covers $X$. Thus we can create a sequence $x_n,n\in\mathbb{N}$ which has no Cauchy sub-sequence by taking $$x_0\in X, x_1\in X\setminus B_r(x_0), x_2\in X\setminus (B_r(x_0)\cup B_r(x_1)),\ldots$$ which we are allowed to do because $B_r(x_0)\cup\cdots\cup B_r(x_n)\neq X$. To see that this has no Cauchy subsequence, observe that for any $m\geq n$ we have $x_m\notin B_r(x_n)$ so $d(x_m,x_n)\geq r$.