Skip to main content

Section 2.4 Cauchy Sequences

Sometimes we can show that the terms of a sequence become arbitrarily close to one another even before we know what the limit should be. The next definition isolates that idea.

Subsection 2.4.1

A sequence \((x_n)\) is Cauchy sequence if for every \(\varepsilon>0\) there exists \(N\in\N\) such that
\begin{equation*} |x_n-x_m|<\varepsilon \quad\text{whenever } n,m\ge N. \end{equation*}
In other words, all sufficiently far terms of a Cauchy sequence lie close to one another.

Example 2.4.1.

The sequence \((1/n)\) is Cauchy. Indeed, if \(m,n\ge N\text{,}\) then
\begin{equation*} \left|\frac{1}{n}-\frac{1}{m}\right| \le \frac{1}{n}+\frac{1}{m} \le \frac{2}{N}. \end{equation*}
Therefore, once \(N\) is large enough that \(2/N<\varepsilon\text{,}\) we have \(|1/n-1/m|<\varepsilon\) for all \(m,n\ge N\text{.}\)

Example 2.4.2.

The sequence \(((-1)^n)\) is not Cauchy. If \(n\) is even, then \(|(-1)^n-(-1)^{n+1}|=2\text{.}\) So no tail of the sequence can have all of its terms within distance \(1\) of each other.

Proof.
Suppose \(x_n\to L\text{.}\) Let \(\varepsilon>0\text{.}\) Choose \(N\in\N\) such that \(|x_n-L|<\varepsilon/2\) for all \(n\ge N\text{.}\) Then whenever \(m,n\ge N\text{,}\) the triangle inequality gives
\begin{equation*} |x_n-x_m|\le |x_n-L|+|x_m-L|< \varepsilon. \end{equation*}
Hence \((x_n)\) is Cauchy.

Proof.
Let \((x_n)\) be Cauchy. Then for some \(N\in\N\text{,}\) \(|x_n-x_m|<1\) whenever \(m,n\ge N\text{.}\) In particular, for every \(n\ge N\text{,}\)
\begin{equation*} |x_n|\le |x_n-x_N|+|x_N|<1+|x_N|. \end{equation*}
Thus, \((x_n)\) is bounded by \(B:=\max\{|x_1|,\dots,|x_{N-1}|,|x_N|+1\}\)
The converse of Proposition 2.4.3 need not hold in an arbitrary ordered field.

Proof.
A Cauchy sequence \((x_n)\) is bounded (Proposition 2.4.4) hence, by the Bolzano-Weierstrass Theorem (Theorem 2.3.2) admits a convergent subsequence \((x_{n_k})\text{.}\) Let \(x_{n_k}\to L\text{.}\)
Let \(\varepsilon>0\text{.}\) Since \((x_n)\) is Cauchy, there exists \(N \in\N\) such that \(|x_n-x_m|<\varepsilon/2\) whenever \(m,n\ge N\text{.}\) Since \(x_{n_k}\to L\text{,}\) there exists \(K \in\N\) such that \(|x_{n_k}-L|<\varepsilon/2\) for every \(k\ge K\text{.}\)
For \(n,k \ge M:=\max\{N,K\}\text{,}\) because \((n_k)\) is strictly increasing, \(n_k \ge k \ge M \ge N\text{.}\) Thus,
\begin{equation*} |x_n-L| \le |x_n-x_{n_k}| + |x_{n_k}-L| < \frac{\varepsilon}{2}+\frac{\varepsilon}{2} = \varepsilon. \end{equation*}
This shows that \(x_n\to L\text{.}\)

Example 2.4.6.

The ordered field \(\Q\) is not sequentially complete. Let \(x_n\) be the decimal truncation of \(\sqrt{2}\) to \(n\) decimal places. Thus
\begin{equation*} x_1=1, \qquad x_2=1.4, \qquad x_3=1.41, \qquad x_4=1.414, \dots \end{equation*}
Then \(0\le \sqrt{2}-x_n < 10^{-n}\) for every \(n\text{.}\) Hence, for \(m,n\ge N\text{,}\)
\begin{equation*} |x_n-x_m| \le |\sqrt{2}-x_n| + |\sqrt{2}-x_m| < 2\cdot 10^{-N}. \end{equation*}
So \((x_n)\) is Cauchy. But it cannot converge in \(\Q\text{,}\) because as a real sequence it converges to \(\sqrt{2}\text{,}\) and \(\sqrt{2}\notin\Q\text{.}\) Thus \(\Q\) is not sequentially complete.
The completeness axiom and sequential completeness do not look alike at first. The completeness axiom is a statement about bounded sets, while sequential completeness is a statement about Cauchy sequences. The link is that one can try to locate the supremum of a nonempty set bounded above by repeatedly choosing a point of the set and an upper bound whose distance keeps shrinking. This produces Cauchy sequences from below and above, and their common limit turns out to be the desired supremum. Thus, for \(\R\text{,}\) the two formulations of completeness are equivalent.

Proof.
Let \(A\subseteq \R\) be non-empty and bounded above. Let \(B\) be the set of all upper bounds of \(A\text{.}\) Then \(B\) is non-empty. Choose \(a_1\in A\) and \(b_1\in B\text{,}\) so in particular, \(a_1 \le b_1\text{.}\)
We will construct, by induction, sequences \((a_n)\) in \(A\) and \((b_n)\) in \(B\) such that
  1. \((a_n)\) is increasing and \((b_n)\) is decreasing.
  2. \(0 \le b_n-a_n \le \frac{b_1-a_1}{2^{n-1}} \) for all \(n \in \N\text{.}\)
Suppose for some \(k \ge 1\text{,}\) \(a_i \in A\) and \(b_i \in B\) (\(1 \le i \le k\)) have been chosen such that
\begin{equation} a_1 \le a_2 \le \ldots \le a_k \le b_k \le \ldots \le b_2 \le b_1\tag{2.4.1} \end{equation}
and \(b_i - a_i \le (b_1-a_1)/2^{i-1}\text{.}\) We choose \(a_{k+1} \in A\) and \(b_{k+1} \in B\) as follows. Let \(m:=\frac{a_k+b_k}{2}\text{.}\) Then:
  1. \(m \in B\text{,}\) take \(b_{k+1} = m\) and \(a_{k+1} =a_k\text{.}\)
  2. If \(m \notin B\text{,}\) then we choose an element of \(A\) that is larger than \(m\) to be \(a_{k+1}\) and keep \(b_{k+1}=b_k\text{.}\)
In either case, \(a_k \le a_{k+1} \le b_{k+1} \le b_k\) and by (2.4.1)
\begin{equation*} b_{k+1} - a_{k+1} \le \frac{1}{2}(b_k - a_k) \le \frac{1}{2^{k}}(b_1 - a_1). \end{equation*}
So by induction, we have constructed sequences \((a_n)\) in \(A\) and \((b_n)\) in \(B\) with the required properties.
Next, we argue that both sequences are Cauchy. For any \(n,m\) with \(n \ge m\text{,}\) \(a_m \le a_n \le b_n \le b_m \text{.}\) Hence,
\begin{equation*} 0 \le |a_n - a_m|, |b_n-b_m| \le b_m - a_m \le \frac{1}{2^{m-1}}(b_1 - a_1). \end{equation*}
Since \((b_1-a_1)/2^{m-1} \to 0\) as \(m \to \infty\text{,}\) both \((a_n)\) and \((b_n)\) are Cauchy and hence convergent by the sequential completeness of \(\R\text{.}\) Let \(a\) and \(b\) be their limits, respectively.
We claim that \(a=b\text{.}\) Fix any \(m \in \N\text{,}\) since \(a_n \le b_m\) for any \(n\text{,}\) so \(a \le b_m\text{.}\) Since \(m\) is arbitrary, we have \(a \le b\) and
\begin{equation*} b-a \le b_n -a_n \le (b_1-a_1)/2^{n-1} \end{equation*}
for any \(n\text{.}\) Letting \(n \to \infty\text{,}\) we conclude that \(a = b\text{.}\)
We now contend that the common limit, say \(s\text{,}\) of \((a_n)\) and \((b_n)\) is the supremum of \(A\text{.}\) First, \(s\) must be an upper bound of \(A\text{.}\) If not, then \(s \lt a_0\) for some \(a_0 \in A\text{.}\) But since \(s\) is the limit of \((b_n)\text{,}\) we have \(b_{n_0} \lt a_0\) for some \(n_0\text{,}\) contradicting the fact that \(b_{n_0} \in B\) is an upper bound of \(A\text{.}\) Next, we argue that any \(s' \lt s\) is not an upper bound of \(A\text{.}\) Otherwise \(a_n \le s'\) for each \(n\) and so \(a_n \to s \le s'\text{,}\) a contradiction. Putting these together shows that \(s = \sup A\text{,}\) and the proof is complete.
PrevTopNext