# A metric space is compact iff it is complete and totally bounded

I'm looking at this theorem from Marsden's Elementary Classical Analysis, but there's a part of the proof that I don't understand. First I'll state the proof of the direction that if it is complete and totally bounded then it is compact. The bold parts of the proof are what I don't understand.

Proof:

Assume that $M$ is complete and totally bounded. Then it is enough to show that $M$ is sequentially compact. Let $y_k$ be a sequence in $M$. We can assume that the $y_k$ are all distinct, for if $y_k$ has infinitely many repetitions, there is a trivally convergent subsequence, and if there are finite repetitions, we may delete them. Given an integer $N$, cover $M$ with finitely many balls, $B(x_{L1},1/N),...,B(x_{LN}, 1/N)$. An infinite number of the $y_k$ lie in one of these balls. Start with $N = 1$. Write $M = B(x_{L1}, 1) \bigcup ... \bigcup B(x_{LN},1)$, and so we can select a subsequence of $y_k$ lying entirely in one of these balls. Repeat for $N = 2$, getting a further subsequence lying in a fixed ball of radius 1/2, and so on. Now choose the "diagonal" subsequence, the first member from the first sequence, the second from the second, and so on. This sequence is Cauchy and since $M$ is complete, it converges. QED.

First, what does it mean that we can delete the finite repetitions?

Next, how can we guarantee that when we take subsequences in such fashion, and then take a diagonal subsequence, the indices of the diagonal subsequence are strictly increasing. That is, say we choose $y_{11}$ from the first subsequence and $y_{22}$ and so on. How are we sure that the index $nn$ is in strictly increasing order when the index is considered to be taken from the original sequence $y_k$.

Finally, how is this "diagonal" subsequence Cauchy?

Can anyone clarify these points to me? Thank you.

It may not be completely clear upon quick reading, but we are taking subsequences of subsequences, not of the original sequence. That is, we start with $\mathbf y = y_1,y_2,\ldots$, then pick a subsequence $\mathbf y_1 = y_{11},y_{12},y_{13},\ldots$ that lives in a single $1$-ball. Then pick a subsequence $\mathbf y_2= y_{21},y_{22},y_{23},\ldots$ of the sequence $\mathbf y_1$. Then pick a subsequence $\mathbf y_3= y_{31},y_{32},y_{33},\ldots$ of the sequence $\mathbf y_3$. And so on. The diagonal sequence then has the following properties:
• If $y_{n,n}=y_k$ and $y_{n+1,n+1}=y_l$ of the original sequence, then $l>k$ because $y_{n+1,n+1}$ is the $(n+1)$st term of a subsequence of $\mathbf y_n$, i.e. $y_{n+1,n+1}=y_{n,n+1+r}$ for some $r\ge 0$.
• Given $N$, there exists a ball $B(x,\frac1N)$ such that $y_{n,n}\in B(x,\frac1N)$ for all $n\ge N$. This is so because all these $y_{n,n}$ are already in the sequence $\mathbf y_N$.