Finite Covers at Finer and Finer Scales
A finite cover by small balls guarantees that infinitely many terms of a sequence must gather in at least one of those balls. Total boundedness lets us repeat this choice at arbitrarily small scales. The important point is to make each new choice from the indices retained at the preceding scale. This gives nested infinite index sets, from which we can select a subsequence whose terms become arbitrarily close to one another.
Throughout, \((X,d)\) is a metric space. For \(p\in X\) and \(r>0\), write \(B(p,r)=\{x\in X:d(x,p)<r\}\). A sequence \((x_n)\) in \(X\) is Cauchy if for every \(\varepsilon>0\) there is \(N\in\mathbb{N}\) such that \(d(x_m,x_n)<\varepsilon\) whenever \(m,n\ge N\).
The radii in this definition can be chosen as small as needed, but the number of balls is allowed to depend on the radius. A single finite cover at one fixed radius is not enough for the construction: the successive choices must control distances at arbitrarily small scales.
The Nested-Index Construction
Proof. If \(X\) is empty, there is no sequence in \(X\) indexed by \(\mathbb{N}\), so the assertion is vacuous. Now suppose \((x_n)\) is a sequence in \(X\). Set \(N_0=\mathbb{N}\). We construct infinite sets of indices \(N_k\) and points \(p_k\in X\) so that \(N_k\subseteq N_{k-1}\) and \(x_n\in B(p_k,2^{-k})\) for every \(n\in N_k\).
Suppose \(N_{k-1}\) has been chosen and is infinite. By total boundedness, finitely many balls of radius \(2^{-k}\) cover \(X\). For each ball, consider the indices \(n\in N_{k-1}\) whose terms lie in it. If each ball contained terms for only finitely many such indices, the finite union of those finite index sets would be finite. That would contradict the infinitude of \(N_{k-1}\). Thus some ball \(B(p_k,2^{-k})\) contains \(x_n\) for infinitely many \(n\in N_{k-1}\). Let \(N_k\) be precisely those indices. This gives an infinite \(N_k\subseteq N_{k-1}\), as required.
Next choose indices \(n_k\in N_k\) recursively so that \(n_k>n_{k-1}\), starting with any \(n_1\in N_1\). This is possible at each stage because an infinite subset of \(\mathbb{N}\) cannot be contained in the finite set of indices at most \(n_{k-1}\). The terms \((x_{n_k})\) form a subsequence. If \(m\ge k\), then \(n_m\in N_m\subseteq N_k\); also \(n_k\in N_k\). Both \(x_{n_m}\) and \(x_{n_k}\) therefore lie in \(B(p_k,2^{-k})\). The triangle inequality gives \(d(x_{n_m},x_{n_k})\le d(x_{n_m},p_k)+d(p_k,x_{n_k})<2^{-k}+2^{-k}=2^{1-k}\).
Given \(\varepsilon>0\), choose \(K\) with \(2^{1-K}<\varepsilon\). Such a \(K\) exists because \(2^{1-k}\) tends to zero. For \(m,n\ge K\), apply the preceding bound with \(k=K\) to the later of \(m,n\) and to the earlier one. It gives \(d(x_{n_m},x_{n_n})<2^{1-K}<\varepsilon\). Hence \((x_{n_k})\) is Cauchy. \(\square\)
The proof makes two distinct choices. At each scale, it keeps an infinite set of indices inside one ball; afterward, it chooses one increasing index from each nested set. The second choice ensures that all sufficiently late selected terms lie together in every ball chosen at an earlier scale.
Worked Example: A Sequence in a Finite Metric Space
Let \(X=\{a,b,c\}\) with the discrete metric \(d(x,y)=0\) when \(x=y\) and \(d(x,y)=1\) when \(x\ne y\). This space is totally bounded: for any \(\varepsilon>0\), the three balls of radius \(\min(\varepsilon/2,1/2)\), centered at \(a,b,c\), cover \(X\). Each such ball is the singleton containing its center, since the radius is positive and at most \(1/2<1\).
Consider the sequence \(x_1=a,x_2=b,x_3=c,x_4=a,x_5=b,x_6=c,\ldots\), so \(x_{3j-2}=a\) for every \(j\in\mathbb{N}\). At every construction stage \(k\), the ball \(B(a,2^{-k})\) is \(\{a\}\). Its index set within the preceding set is \(N_k=\{1,4,7,\ldots\}\), which is infinite; starting with \(N_0=\mathbb{N}\), these choices give the same \(N_k\) at every stage. Choose \(n_k=3k-2\). Then \(n_{k+1}-n_k=3>0\), and \(x_{n_k}=a\) for every \(k\). The selected subsequence is constant, so every pair of its terms has distance \(0\), which is less than every \(\varepsilon>0\).
Check: \(n_1=1,n_2=4,n_3=7\) are increasing indices in the chosen set, and the corresponding terms are \(a,a,a\). This is the nested-index procedure in a case where the small balls are singletons.
Worked Example: Shrinking Balls in the Unit Interval
Give \(X=[0,1]\) the metric \(d(x,y)=|x-y|\), inherited from \(\mathbb{R}\). This space is totally bounded. Given \(\varepsilon>0\), choose \(M\in\mathbb{N}\) with \(1/M<\varepsilon\). The finitely many centers \(j/M\), for integers \(j=0,\ldots,M\), lie in \([0,1]\). For any \(x\in[0,1]\), take \(j=\lfloor Mx\rfloor\), where \(\lfloor Mx\rfloor\) is the greatest integer at most \(Mx\). Then \(0\le j\le M\) and \(0\le x-j/M<1/M<\varepsilon\), so \(x\in B(j/M,\varepsilon)\).
Now take \(x_n=1/2+1/(n+2)\). For each \(n\ge1\), \(0<1/(n+2)\le1/3\), so \(1/2<x_n\le5/6<1\); thus \(x_n\in X\). At stage \(k\), choose the ball \(B(1/2,2^{-k})\). Define \(N_k=\{n\in\mathbb{N}:n\ge 2^k-1\}\). These sets are infinite, and \(N_k\subseteq N_{k-1}\) for \(k\ge2\). If \(n\in N_k\), then \(n+2\ge2^k+1>2^k\), so \(|x_n-1/2|=1/(n+2)<2^{-k}\). Thus all terms indexed by \(N_k\) lie in the chosen ball.
Choose \(n_k=2^k\). This is increasing, and \(2^k\ge2^k-1\), so \(n_k\in N_k\). The selected terms are \(x_{n_k}=1/2+1/(2^k+2)\). For \(m\ge k\), both \(x_{n_m}\) and \(x_{n_k}\) lie in \(B(1/2,2^{-k})\), and therefore their distance is less than \(2^{1-k}\). Given \(\varepsilon>0\), choose \(K\) with \(2^{1-K}<\varepsilon\); then for \(m,n\ge K\), \(d(x_{n_m},x_{n_n})<\varepsilon\).
Check: At \(k=2\), \(N_2=\{n:n\ge3\}\), and \(n_2=4\in N_2\). The selected term is \(x_4=1/2+1/6=2/3\), whose distance from the ball center \(1/2\) is \(1/6<1/4=2^{-2}\).
A Cauchy Subsequence Need Not Converge in the Space
The construction proves a Cauchy conclusion, not a convergence conclusion. Convergence requires a limit in \(X\); total boundedness alone does not guarantee one. The next example checks this distinction in a totally bounded space.
Worked Example: A Cauchy Subsequence in an Incomplete Space
Let \(X=\mathbb{Q}\cap(0,1)\), with the metric inherited from \(\mathbb{R}\). This space is totally bounded. Given \(\varepsilon>0\), choose an integer \(M\ge2\) with \(1/M<\varepsilon\). Use the rational centers \(j/M\) for \(j=1,\ldots,M-1\), all of which belong to \(X\). For \(x\in X\), if \(Mx<1\), then \(0<x<1/M\), so \(|x-1/M|<1/M\). Otherwise let \(j=\lfloor Mx\rfloor\). Then \(1\le j\le M-1\) and \(0\le x-j/M<1/M\). In either case \(x\) lies in a ball of radius \(1/M<\varepsilon\) centered in \(X\).
Consider \(x_n=n/(n+1)\), which is rational and satisfies \(0<n/(n+1)<1\) for every \(n\ge1\). At stage \(k\), take \(p_k=x_{2^k}=2^k/(2^k+1)\) and \(N_k=\{n:n\ge2^k\}\). These are nested infinite index sets. If \(n\in N_k\), then \(|x_n-p_k|=(n-2^k)/((n+1)(2^k+1))<1/(2^k+1)<2^{-k}\). The first strict inequality follows from \(n-2^k<n+1\); the second follows from \(2^k+1>2^k\). Hence the terms indexed by \(N_k\) lie in \(B(p_k,2^{-k})\). Choosing \(n_k=2^k\in N_k\) gives the subsequence \(x_{2^k}\), which is Cauchy by the nested-ball argument.
But \(x_{2^k}=1-1/(2^k+1)\), so these terms converge to \(1\) in \(\mathbb{R}\), and \(1\notin X\). They cannot converge to any \(q\in X\): if they did, the triangle inequality would give \(|q-1|\le |q-x_{2^k}|+|x_{2^k}-1|\), whose right side tends to \(0\), forcing \(q=1\). Thus this Cauchy subsequence has no limit in \(X\).
Check: At \(k=1\), \(p_1=x_2=2/3\), and \(N_1=\{n:n\ge2\}\). For \(n=3\), \(x_3=3/4\) and \(|x_3-p_1|=|3/4-2/3|=1/12<1/2=2^{-1}\), as required.
Common Pitfall: A Ball Has Twice Its Radius as a Distance Bound
If two points lie in \(B(p,r)\), the triangle inequality gives \(d(x,y)\le d(x,p)+d(p,y)<2r\), not necessarily \(d(x,y)<r\). For a concrete calculation in \(\mathbb{R}\), both \(0.3\) and \(0.7\) lie in \(B(0.5,0.25)\), since \(|0.3-0.5|=0.2<0.25\) and \(|0.7-0.5|=0.2<0.25\). Their distance is \(|0.7-0.3|=0.4\), which is greater than \(0.25\). The correct bound is \(0.4<2(0.25)=0.5\). This is why the proof chooses radii \(2^{-k}\) and then uses the pairwise bound \(2^{1-k}\), choosing \(k\) so that this latter quantity is below the desired \(\varepsilon\).
The method is useful because it extracts a definite Cauchy subsequence using only finite covers at each scale. It does not assume that the original sequence converges, and it does not require a limit point to be in the space. To conclude that a Cauchy sequence converges in \(X\), one needs completeness as an additional hypothesis; that is a separate step.
Check Your Understanding
For each question, keep track of which indices are retained and which distance bound follows from the chosen ball.
- In the nested-index proof, why must at least one ball in the finite cover contain terms with infinitely many indices from \(N_{k-1}\)?
- If the balls at stage \(k\) have radius \(3^{-k}\), what pairwise distance bound follows for two terms in the same chosen ball?
- For the sequence \(x_n=1/2+1/(n+2)\), verify that \(n_k=2^k\) belongs to \(N_k=\{n:n\ge2^k-1\}\) and that the selected indices increase.
- Why does the theorem guarantee a Cauchy subsequence but not, by itself, a convergent subsequence in \(X\)?
- In the discrete metric on a finite set, why can a ball of radius \(1/2\) contain only its center?