# Cauchy sequences - can we control the rate at which elements “get closer”?

In Simon & Reed's book Methods of Modern Mathematical Physics, it is proven in chapter 1 (Theorem 1.12) that $L^1$ is complete (Riesz-Fisher theorem). The proof starts off as follows:

Let $f_n$ be a Cauchy sequence of functions in $L^1$. It is enough to show that some subsequence converges (this has been shown earlier) so we pass to a subsequence (labeled in the same way) with $\left|\left|f_n-f_{n+1}\right|\right|_1\leq 2^{-n}$.

This arouses my suspicion (although surely I will turn out to be wrong): Can we pick a subsequence such that $\left|\left|f_n-f_{n+1}\right|\right|_1\leq 2^{-n}$? This seems strange to me because it seems to say something about the rate of at which elements "get closer" under this norm (I should probably specify that $\left|\left| f\right|\right|_1=\int \left| f \right| dx$), rather than just saying that they do get arbitrarily close at some point. In particular, it seems to say that each progressive element is "twice as close".

The definition of a Cauchy sequence says that for each $\epsilon>0$ we can choose and $N$ such that $n,m>N$ implies $\left|\left| f_n-f_m\right|\right|_1=d(f_n,f_m)\leq\epsilon$, where $d(\cdot,\cdot)$ is the metric induced by the norm. This, to me, does not seem equivalent to saying that for any strictly positive $\epsilon(n)$ there is a subsequence such that $d(f_n,f_{n+1})\leq \epsilon(n)$. Am I mistaken?

-
I've deleted my comment as it gave a wrong direction, you may consider deleting yours as well. –  Ilya Jul 24 '14 at 18:26

## 4 Answers

The key to this observation in Reed and Simon is that we are choosing a subsequence by a particular process. And we can force this subsequence to obey a certain "rate of closeness." Here's how this works in general.

Let $(X,d)$ be an arbitrary metric space. Suppose that $\{x_n\}_{n=1}^\infty$ is a Cauchy sequence in $X$. First, choose an integer $n_1 \in \mathbb{N}$ so that $n, m \ge n_1$ implies $d(x_n, x_m) < \frac{1}{2}$. We have the ability to do this because $\{x_n\}$ is Cauchy.

Next, choose $n_2 \in \mathbb{N}$ so that $n, m \ge n_2$ implies $d(x_n, x_m) < \frac{1}{4} = \frac{1}{2^2}$ (again, we can do this because $\{x_n\}$ is Cauchy). In fact, we can go ahead and assume $n_2 > n_1$, since any integer $\tilde{n} > n_2$ also satisfies the property:

$$n,m \ge \tilde{n} \implies d(x_n, x_m) < \frac{1}{2}.$$

Now, we finish the argument by induction. Suppose we have chosen $n_1 < n_2 < \cdots < n_k$ with the property that

$$n,m \ge n_k \implies d(x_n,x_m) < \frac{1}{2^k}.$$

Notice in particular that this means $d(x_{n_i}, x_{n_{i+1}}) < \frac{1}{2^i}$ for $i = 1, \dots, k-1.$

Then, just as we did for the $n_2$ case, we pick $n_{k+1} > n_k$ so that $$n,m \ge n_{k+1} \implies d(x_n, x_m) < \frac{1}{2^{k+1}}.$$

And this implies $d(x_{n_k}, x_{n_{k+1}}) < \frac{1}{2^k}$. So in this way we construct a subsequence $\{x_{n_k}\}_{k=1}^\infty$ that satisfies the "rate of closeness" we desire.

This construction works for the example you give if we set $X = L^1$, $d(f, g) = \|f-g\|_1$. The potentially confusing part in Reed and Simon is the relabeling of the subsequence. Basically, Reed and Simon throw away the subscripts on the subsequence $\{x_{n_k}\}_{k=1}^\infty$ and just write the subsequence as $\{x_k\}_{k=1}^\infty$. And this is confusing because it makes the subsequence look just like the original sequence. But in fact they are now just using the subsequence.

-
This is the cleanest answer (so far) in my opinion. Thank you for explaining. –  Danu Jul 24 '14 at 17:04
@Danu Please define "cleanliness". –  Did Jul 24 '14 at 17:13
@Did Making things as obvious as possible to me. In retrospect, clearest would have been a better term. I understand that your answer is much cleaner if you define "cleanliness" differently, and appreciate the time you took to write your (more general) answer, which I rewarded with a +1 after understand what exactly it meant (helped by other answer). –  Danu Jul 24 '14 at 17:16

We agree that the question is whether, for any strictly positive sequence $(\epsilon(n))$, there exists a subsequence $(f_{\varphi(n)})$ of $(f_n)$ such that $d(f_{\varphi(n)},f_{\varphi(n+1)})\leq \epsilon(n)$ for every $n$.

The answer is "yes". As you recall:

The definition of a Cauchy sequence says that for each $\epsilon>0$ we can choose and $N$ such that $n,m>N$ implies $d(f_n,f_m)\leq\epsilon$.

For each $n$, use the definition of a Cauchy sequence with $\epsilon=\epsilon(n)$, call $N(n)$ an integer $N$ such that the condition in the definition holds and let $\varphi(n)=\max\{N(k);k\leqslant n\}$. Then indeed, for every $n$, $d(f_{\varphi(n)},f_{\varphi(n+1)})\leq \epsilon(n)$ as desired.

-

Let $\varepsilon_1 = 2^{-2}$. Let $N_1$ be such that $n,m > N_1$ implies that $\Vert f_n - f_m \Vert_1 \le \varepsilon_1$.

Now, take some $k_1 > N_1$, and let $f_{k_1}$ be the first element in the subsequence.

Now, we can recursively define the sequence as follows:

Let $N_n, \varepsilon_n, k_n$ be given for some $n \ge 1$.

Define $\varepsilon_{n + 1} = \frac{\varepsilon_n}{2}$. (Alternately, take $\varepsilon_n = 2^{-n - 1}$ for all $n \ge 1$.)

Let ${\hat N}_{n + 1}$ be such that if $m,\ell > \hat N_{n + 1}$, then $\Vert f_m - f_\ell \Vert_1 < \varepsilon_{n + 1}$.

Define $N_{n + 1} = \max(k_n, \hat N_{n + 1})$.

Then, if $m,\ell > N_{n + 1}$, then $\Vert f_m - f_\ell \Vert_1 < \varepsilon_{n + 1}$, as $N_{n + 1} \ge \hat N_{n + 1}$. Moreover, both $m$ and $\ell$ are greater than $k_n$.

Now, we can take some $k_{n + 1} > N_{n + 1}$, and as both $k_{n + 1}$ and $k_n$ are greater than $N_{n}$, we have that $\Vert f_{k_n} - f_{k_{n + 1}} \Vert_1 < \varepsilon_n = 2^{-n - 1}$, and that $k_{n + 1} > N_{n + 1} \ge k_n$.

This therefore constructs a subsequence as desired.

-
Ah, I finally got it. I feel like a very nice pictorial representation of this could easily be made to make it all completely lucid, even trivial. –  Danu Jul 24 '14 at 17:01

This can be done. Let's start out with the original sequence $(f_n)$. Since we are assuming it is Cauchy, we know that for each $\epsilon >0$ there is a number $N$ for which $k,l>N$ yields $||f_k - f_l||_1 \leq \epsilon$. What we can do now is choose $\epsilon = 2^{-n}$ for any $n$ we wish. What we are guaranteed then is a cutoff $N_n$ for which $||f_k-f_l||<2^{-n}$ for any $k,l>N_n$. In particular, this works for $l=k+1$ if $k$ is chosen to be greater than $N_n$.

Given this, the subsequence you are speaking of is generated for each $n$ by referring to the definition of a Cauchy sequence and choosing a particular $k$ and $l$.

-