# Every sequence in $A$ has a Cauchy subsequence $\implies$ $A$ is totally bounded (Carothers, Theorem 7.5)

Theorem 7.5: A set $$A$$ is totally bounded iff every sequence in $$A$$ has a Cauchy subsequence.

The $$[\Rightarrow]$$ direction of the proof is easy, I have trouble understanding the $$[\Leftarrow]$$ direction.

First, here are the definitions/characterizations of totally bounded I know:

$$A\subset (M,d)$$ is said to be totally bounded if for all $$\epsilon>0$$, there exist finitely many points $$x_1,\ldots,x_n\in M$$ such that $$A\subset\bigcup_{i=1}^n B(x_i,\epsilon)$$. Equivalently, $$A\subset (M,d)$$ is said to be totally bounded if for all $$\epsilon>0$$, there exist finitely many points $$x_1,\ldots,x_n\in A$$ such that $$A\subset\bigcup_{i=1}^n B(x_i,\epsilon)$$.
Also, $$A$$ is totally bounded iff for all $$\epsilon>0$$, there are finitely many sets $$A_1,A_2,...,A_n\subset A$$ with $$\text{diam}(A_i) < \epsilon$$ for all $$1\le i\le n$$ such that $$A\subset \bigcup_{i=1}^n A_i$$.

I will reproduce the main parts of the proof of $$[\Leftarrow]$$ direction now.

Suppose $$A$$ is not totally bounded. Then there is some $$\epsilon > 0$$ such that $$A$$ cannot be covered by finitely many $$\epsilon$$-balls. Thus, by induction, we can find a sequence $$(x_n)$$ in $$A$$ such that $$d(x_n,x_m) \ge \epsilon$$ whenever $$m\ne n$$.

How? Where can I use induction? It is not obvious!

But then, $$(x_n)$$ has no Cauchy subsequence.

This makes sense! Once I have found an $$(x_n)$$ with the above properties, I know that it can't have a Cauchy subsequence. To see this, suppose it did - let $$(x_{n_k})$$ be the Cauchy subsequence of concern. Then we would want, $$\forall \epsilon > 0, \exists N\in \Bbb N$$ such that $$p,q\ge N \implies d(x_{n_p},x_{n_q}) < \epsilon$$. Sadly, we have $$d(x_{n_p},x_{n_q}) \ge \epsilon$$ for all $$p\ne q$$. Contradiction!

So, only the fact that such a $$(x_n)$$ exists bothers me - could I get some help in completing that part of the proof by induction or otherwise? Thanks!

It's really by recursion, not induction (which is a proof technique).

So we have $$\varepsilon >0$$ such that $$A$$ cannot be covered by finitely many balls of radius $$\varepsilon$$.

Let $$x_1 \in A$$ to start the recursion. Then $$A$$ is not a subset of $$B(x_1, \varepsilon)$$ by assumption. So pick $$x_2 \in A$$ such that $$x_2 \notin B(x_1, \varepsilon)$$. Note that this means that $$d(x_1,x_2) \ge \varepsilon$$.

Now suppose we have already points $$x_1, \ldots x_{m}$$ so that $$d(x_i, x_j) \ge \varepsilon$$ for all $$1\le i,j \le m, i \neq j$$. By the assumption on $$A$$ we have

$$A \nsubseteq \bigcup_{i=1}^m B(x_i, \varepsilon)$$

or $$A$$ would have been coverable by finitely many $$\varepsilon$$-balls. So pick $$x_{m+1} \in A$$ that is not in the union, and note that this means that $$d(x_{m+1}, x_i) \ge \varepsilon$$ for all $$1 \le i \le m$$.

So now we have $$m+1$$ many points $$x_1,\ldots, x_m, x_{m+1}$$ obeying $$d(x_i, x_j) \ge \varepsilon$$ for all $$i \neq j$$ so far. So we can do the recursion step going from $$m$$ to $$m+1$$ points, for every $$m$$.

So we have constructed a sequence $$(x_n)_n$$ by recursion, all of whose distances are $$\ge \varepsilon$$ between distinct indices.

The proof that it doesn't have a Cauchy subsequence is fine.

Suppose that $$A$$ is not totally bounded. Then, fix $$\varepsilon>0$$ such that, if $$a_1,\ldots,a_n\in A$$, then $$A\not\subset\bigcup_{i=1}^nB(a_i,\varepsilon)$$. Take $$x_1\in A$$. Since $$A\not\subset B(x_1,\varepsilon)$$, you can take $$x_2\in A\setminus B(x_1,\varepsilon)$$. Since $$A\not\subset B(x_1,\varepsilon)\cup B(x_2,\varepsilon)$$, there is some $$x_3\in A\setminus B(x_1,\varepsilon)\cup B(x_2,\varepsilon)$$. And so on… Then $$m\ne m\implies d(x_m,x_n)\geqslant\varepsilon$$.

Supposing, as in your quote, that $$A$$ is not totally bounded, and that $$\varepsilon$$ is a witness to this. Then we can construct a sequence as follows:

1. Start with any point $$x_0$$ in $$A$$. We know that $$A$$ is not in a $$\varepsilon$$ ball around $$x_0$$ (else it would be totally bounded), so there is some point $$x_1$$ in $$A \setminus B(x_0,\varepsilon)$$.
2. Repeat this process: after any finite number of steps $$k$$, we know that $$A$$ is not contained in $$\bigcup_{i=0}^k B(x_i,\varepsilon)$$, else it would be totally bounded, so we can choose $$x_{k+1}$$ to be any element of $$A\setminus \bigcup_{i=0}^k B(x_i,\varepsilon)$$, and we will have $$d(x_{k+1},x_i) > \varepsilon$$ for all $$i \leq k$$ by construction.

Since every point that we add is at least $$\varepsilon$$ from every previous point, all pairs of distinct points in our sequence are at least $$\varepsilon$$ apart from one another.