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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.