$\newcommand{\Rr}{\mathbb{R}}$ $\newcommand{\Zz}{\mathbb{Z}}$ $\newcommand{\Nn}{\mathbb{N}}$ $\newcommand{\Qq}{\mathbb{Q}}$ $\newcommand{\ve}{\varepsilon}$ $\newcommand{\dp}[2]{\langle #1, #2\rangle}$ $\newcommand{\va}{\mathbf{a}}$ $\newcommand{\vb}{\mathbf{b}}$ $\newcommand{\vc}{\mathbf{c}}$ $\newcommand{\vx}{\mathbf{x}}$ $\newcommand{\vy}{\mathbf{y}}$ $\newcommand{\vz}{\mathbf{z}}$ $\newcommand{\norm}[1]{\left\| #1 \right\|}$

Cauchy Sequences¶

Read Section 2.4. Check your understanding against the following questions:

  • What is a Cauchy sequence? Give examples.
  • What means by an ordered field is complete?

Proposition. A convergent sequence is Cauchy.

Proof. Suppose $(x_n)$ is a convergent sequence. Let $L$ be its limit. Then for any $\varepsilon >0$, then exists $N \in \mathbb{N}$ such that $|x_k-L| < \varepsilon/2$ for any $k \ge N$. Thus, if both $n,m \ge N$, then $|x_n-x_m| \le |x_n-L| + |x_m -L| < \varepsilon/2 + \varepsilon/2 = \varepsilon$.

Lemma. A Cauchy sequence is bounded.

Proof. Suppose $(x_n)$ is Cauchy. Then there exists $N$, such that $|x_n -x_m| < 1$ for any $n, m \ge N$. In particular, $|x_n -X_N| M 1$ and hence $|x_n| < |x_N|+1$ for all $n \ge N$. So, the sequence is bounded by the maximum of $\{|x_1|,\ldots, |x_{N-1}|, |x_N|+1\}$.

Theorem (Completeness of $\mathbb{R}$). Every Cauchy sequence of real numbers converges.

Proof. Let $(x_n)$ be a Cauchy sequence of real numbers. By the lemma above $(x_n)$ is bounded and so, by the Bozanlo-Weierstrass theorem, it has a convergent subsequence $(x_{n_k})$. Let $L$ be its limit.

Then for any $\varepsilon > 0$, there exist $N_1,N_2 \in \mathbb{N}$, so that whenever $n,m \ge N_1$, $|x_n-x_m| < \varepsilon/2$ and whenever $k \ge N_2$, $|x_{n_k}-L|<\varepsilon/2$. Let $N = \max\{N_1,N_2\}$. So, for any $n \ge N$, take $m = n_N$ and $k = N$ then $m \ge N \ge N_1$ and $k \ge N \ge N_2$. Thus,

$$|x_n-L| \le |x_n- x_{n_N}| + |x_{n_N}-L| < \varepsilon.$$

This shows that $(x_n)$ is convergent.

Remarks.

  • Completeness of $\mathbb{R}$ is equivalent to $\mathbb{R}$ having the least-upper-bound property.

  • The importance of completeness is that we can show that some real sequences converge with out knowning explicitly the limit.

  • A metric space is complete if every Cauchy sequence converges.

Relation with the l.u.b. property of $\Rr$.¶

We have show that

The l.u.b property of $\Rr \implies$ Bolzano-Weierstrass theorem $\implies$ every Cauchy sequence is convergent (Completeness of $\Rr$)

In fact, they are all equivalent:

Theorem. Completeness of $\Rr$ implies $\Rr$ has the l.u.b. property.

Proof. The $A$ be a non-empty subset of $\Rr$ that is bounded above. So, $B$ the set of upper bounds of $A$ is also non-empty. If $s \in A \cap B$, then clearly $s = \sup A$. Thus, WLOG let us assume $A$ and $B$ are disjoint.

We are going to construct, by induction, a Cauchy sequence $(a_n)$ in $A$ and a Cauchy sequence $(b_n)$ in $B$ with the following properties

  1. $(a_n)$ is increasing and $(b_n)$ is decreasing.
  2. $a_n \le b_n$ for all $n$.
  3. $b_n-a_n \le \dfrac{b_1-a_1}{2^{n-1}}$

To start, pick any $a_1 \in A$ and $b_1 \in B$. Since $b_1$ is an upper bound of $A$, $a_1 \le b_1$.

Suppose for some $k \ge 1$, $a_i$ in $A$ and $b_i \in B$ $(1 \le i \le k)$ have been choosen so that

$$a_1 \le a_2 \le \cdots \le a_k \le b_k \le \cdots \le b_2 \le b_1$$

and $b_i - a_i \le \dfrac{1}{2^{i-1}}(b_1-a_1) \qquad (*)$.

We choose $a_{k+1} \in A$ and $b_{k+1} \in B$ as follows: Let $m = (b_k+a_k)/2$ which is the mid-point between $a_k$ and $b_k$.

Case 1. $m \in B$. Take $b_{k+1} = m$ and $a_{k+1} = a_k$.

Case 2. $m \notin B$. Then there exists some $a_{k+1} \in A$ so that $m < a_{k+1}$. And we take $b_{k+1}$ to be $b_k$.

In either case, we have $a_{k} \le a_{k+1} \le b_{k+1} \le b_k$ and by $(*)$ $$ b_{k+1} -a_{k+1} \le \frac{1}{2}(b_k-a_k) \le \frac{1}{2}\frac{1}{2^{k-1}}(b_1-a_1) = \frac{1}{2^k}(b_1-a_1) $$

So by induction, we constructed two sequences (one in $A$ and the other in $B$) both satisfying conditions (1), (2) and (3). We now contend that the two constructed sequences are Cauchy.

For any $m \le n$, since $a_m \le a_n \le b_n \le b_m$, so

$$0 \le |b_n -b_m|, |a_n-a_m| \le (b_m -a_m) \to 0 \qquad \text{as}\ m \to \infty.$$

This shows $(a_n)$ and $(b_n)$ are both Cauchy.

So by completeness of $\Rr$, both sequences are convergent, say $a_n \to a$ and $b_n \to b$. Since $(b_n)$ is decreasing, $b \le b_n$ for each $n$. Likewise, $a_n \le a$ for each $n$.

Since $0 \le |b-a| \le b_n-a_n \le \dfrac{1}{2^{n-1}}(b_1-a_1)$ for each $n$. Letting $n \to \infty$, we conclude that $b=a$. Let $s$ be the common value. We now argue that $s = \sup A$.

First, $s \in B$. If not, then $b < a_0$ for some $a_0 \in A$. But since $b_n \downarrow s$, $b \le b_n < a_0$ for some $n$. This contradicts that fact that $b_n \in B$ is an upper bound of $A$,

Next, suppose $s' \lt s$. Since $a_n \uparrow s$, $s' < a_n \le s$ for some $n$ so $s'$ cannot be an upper bound of $A$.

Putting these together, we show that $s = \sup A$ and the proof is completed.