# Metric space is totally bounded iff every sequence has Cauchy subsequence

Prove that a metric space is totally bounded if and only if every sequence has a Cauchy subsequence.

I think I proved the Cauchy subsequence part:

Let $a_{0},a_{1}, a_{2}, a_{3}, a_{4},...\in X$ be a sequence.

For each $k$, let $F \subseteq X$ be a finite $\frac1k$-net.

Given $I \subseteq \Bbb N_{\ge0}$ and $k>1$ you find an infinite $J \subseteq I$ such that: $$\exists p\in F:\forall n\in J: d(x_n,p)<\frac1k$$

• I've edited your question to give it a meaningful title (please give some attention to this in the future), and to make your own work more readable. Please ensure that I didn't accidentally change what you originally wrote. – Lord_Farin Nov 7 '13 at 22:55

You have proved that totally bounded implies every sequence has Cauchy subsequence, so I will prove the other implication. This is a proof using the contrapositive, that is, not totally bounded implies that there is a sequence with no Cauchy subsequence.

Suppose that $X$ is not totally bounded. Then there is an $\epsilon>0$ such that for all finite sets of points $\{x_1,\ldots,x_n\}$ $$X\neq \bigcup_{k=1}^n B(x_k;\epsilon).$$ Now we construct a sequence that has no Cauchy subsequence. Start with a finite collection of points $\{x_1,\ldots,x_n\}$, as above. Then since $X\neq \bigcup_{k=1}^n B(x_k;\epsilon)$, there is a point $x_{n+1}\in X$ such that $x_{n+1}\notin \bigcup_{k=1}^n B(x_k;\epsilon)$. Moveover, $$X\neq \bigcup_{k=1}^{n+1} B(x_k;\epsilon)$$ because if it were equal, we would have a contradiction to our assumption. Wash, rinse, repeat this process to get a sequence $(x_k)_{k=1}^\infty$.

To check that this has no Cauchy subsequence, notice that for any two terms $x_n$ and $x_m$ in this sequence, if $m>n$ then $$x_m\notin \bigcup_{k=1}^{m-1} B(x_k;\epsilon).$$ In particular, $x_m\notin B(x_n;\epsilon)$, hence $d(x_m,x_n)\geq \epsilon$. Similarly if $n>m$. This shows that the terms of this sequence are at least $\epsilon$ in distance apart, hence no Cauchy subsequence can exist.

• "wash-rinse-repeat", loved it and the method +1 – Shobhit Oct 1 '17 at 19:21

The stated proof of implication totally bounded $\implies$ Cauchy subsequence is more like a sketch of the approach than a complete proof. Here is how it develops:

Suppose $(a_n)$ is a sequence in a totally bounded metric space $X$. For each $k$, choose a finite $(1/k)$-net in $X$ and call it $F_k$.

Let $J_0 = \mathbb{N}$ and construct infinite sets $J_0\supset J_1\supset J_2\supset J_3\supset\cdots$ inductively as follows. For every $n\in J_{k-1}$ there is $p\in F_k$ such that $d(x_n,p)<1/k$. Since $J_{k-1}$ is infinite while $F_k$ is finite, there exists $p\in F_k$ such that the set $J_k : = \{n\in \mathbb{N}:d(x_n, p)< 1/k\}$ is infinite.

Finally, define subsequence $a_{n_k}$ by letting $n_k$ be some element of $J_k$ that is greater than $n_{k-1}$. This is a Cauchy subsequence. Indeed, for any $\epsilon>0$ there exists $N$ such that $2/N<\epsilon$. For $j,k\ge N$ we have $n_j,n_k\in J_N$, hence there is $p\in F_N$ such that $$d(a_{n_k},p) < \frac{1}{N}, \quad d(a_{n_j},p) < \frac{1}{N}$$ Thus $d(a_{n_k}, a_{n_j}) < 2/N<\epsilon$ by the triangle inequality.