Finding a special subsequence of any Cauchy sequence

Question

Let $(X,d)$ be a metric space and let $(x_n)$ be a Cauchy sequence in $X$. Let $(\epsilon_n)$ be a sequence of real numbers and decrease to $0$. Show that there is a subsequence $(x_{n_k})$ of $(x_n)$ such that: $$d(x_{n_j},x_{n_k})<\epsilon_{\min\{j,k\}}\:\:\: j,k=1,2,\dots$$

I'm not sure about my solution. Each time I try to find a subsequence, it just makes me more confused. Here is my solution.

Since $(x_n)$ is Cauchy, so for $\epsilon_1$ there is an integer $N_1\in\mathbb{N}$, such that for any $j,m\geq N_1$, we have $d(x_m,x_j)<\epsilon_1.$

Now define a subsequence $(x_{n_k})$ of $(x_n)$ such that: $x_{n_1}=x_{N_1},\: x_{n_2}=x_{N_1+1}$ and so on. Obviously, the subsequence $(x_{n_k})$ is Cauchy.

Similarly, for $\epsilon_2$, there is an integer $N_2$ such that for any $m,j\geq N_2$, we have $d(x_{n_m},x_{n_j})<\epsilon_2.$

Without loss of generality, let $(x_{n})=(x_{n_k})$. Define the subsequence $(x_{n_k})$ of $(x_{n})$ such that $x_{n_1}=x_{N_2}, \: x_{n_2}=x_{N_2+1}$.

Hence, $d(x_{n_1},x_{n_2})<\epsilon_2<\epsilon_1$ and also, $d(x_{n_2},x_{n_3})<\epsilon_2$.

Continuing this method $n'$ times, for $\epsilon_{n'}$, there is an integer $N_{n'}$ such that for any $m,j\geq N_{n'}$, we have $d(x_{m},x_{j})<\epsilon_{n'}$.
Now define seubsequence $(x_{n_k})$ of $(x_n)$ such that: $x_{n_1}=x_{N_{n'}},\: x_{n_2}=x_{N_{n'}+1}$ and so on. Now for the subsequence $(x_{n_k})$ we have: $$d(x_{n_j},x_{n_k})<\epsilon_{n'}<\epsilon_{\min\{j,k\}}\:\:\: j,k=1,2,\dots,n' $$

Answer 1

I think that your way of thinking is correct, but it may also help conceptually to think of these sequences as sets of points which you can manipulate all at once:

We have our original Cauchy sequence $S = \{x_1, x_2, x_3,\ldots\}$ and a decreasing sequence $E$ of positive numbers $\epsilon_1 > \epsilon_2 > \epsilon_3 > \ldots$ which converges monotonically toward zero.

Because the sequence $S$ is Cauchy, we know that for every $\epsilon_i \in E$, there exists an integer $N_i$ so that all of the terms in the tail of $S$ are within $\epsilon_i$ of each other (i.e. for all $x_a,x_b$ with $a,b>N_i$, we have $d(x_a,x_b)<\epsilon_i$.)

The first trick is to notice that we can choose the $N_i$ so that they form an increasing sequence $N_1 < N_2 < N_3 < \ldots$. (Intuitively, this is because if we have some $N_i$, we may freely increase its value as much as we like without affecting the $\epsilon_i$ property.)

Now let us define $S_i$ to refer to the tail of the sequence $S$ starting at term $N_i$:

$$S_i \equiv \{x_n \in S : n > N_i\}\qquad\text{for }i=1,2,3,\ldots$$

The $S_i$ sets have two important properties:

• Because the $N_i$ are increasing, the $S_i$ are nested: $S_1 \supseteq S_2 \supseteq S_3 \supseteq \ldots$.
• Because $S$ is Cauchy, every $S_i$ is nonempty, and every pair of points in $S_i$ is within $\epsilon_i$ of each other. (In fact, every $S_i$ contains infinitely many points!)

Now the construction is essentially finished:

1. Pick any $y_1 \in S_1$ for the first term in the subsequence.
2. You could pick $y_2 \in S_2$, but you must ensure that it comes after $y_1$ in the original sequence. Therefore, choose $y_2$ from $S_2$ excluding the finitely many points that came before $y_1$ in the original sequence.^[1]
3. Similarly, we can pick each successive term $y_{i+1}$ from the set $S_{i+1}$, excluding the finitely many terms that came before $y_i$ in the original sequence.

It will always be possible to pick the $y_i$ because each $S_i$ contains infinitely many points ($S$ is Cauchy), and because we are only ever excluding finitely many of them in the $i$th step.

---

^[1] A technicality about this exclusion process: of course sequences may contain the same point more than once. If for the $i$th term in our subsequence, we pick the $j$th term $x_j$ of the original sequence, this exclusion process only ensures that the $(i+1)$th term in our subsequence comes later ($x_k$ for some $k>j$). Hence, we are not excluding points in $X$, only terms from the sequence $S$.

Answer 2

Take a point $x_{1, 1}$ such that the open ball $B(x_{1, 1}, \varepsilon_1)$ contains infinitely many points. Denote the subsequence of points of $(x_n)$ in this ball by $(x_{1, k})$. In particular, we may re-order the sequence so that the sequential order of terms in $(x_n)$ is preserved in $(x_{1, k})$.

Now, there is a point $x_{2, 1}$ such that the intersection $B(x_{1, 1}, \varepsilon_1) \cap B(x_{2, 1}, \varepsilon_2)$ contains infinitely many points. Denote this subsequence of points by $(x_{2, k})$ with the same ordering conditino as before. Indeed, $(x_{2, k})$ is clearly a subsequence of $(x_{1, k})$.

Continue this process. Taking the sequence $(x_{j, 1}) := (x_{n_j})$ works.