Sequences and Completeness

The rational numbers have holes. The increasing sequence $1,1.4,1.41,1.414,\dots$ of decimal truncations of $\sqrt 2$ stays bounded and creeps upward forever, yet no rational number is its limit, because $\sqrt 2$ is irrational. The real numbers are built precisely to fill such holes, and the property that fills them is completeness. Every theorem in analysis that produces a number, whether from a limit, an integral, a derivative, or a fixed point, traces back to completeness, so it is the right place to begin. This post is the root of the analysis track, and it assumes only the ordered-field arithmetic of the reals.

#Completeness

A set $S\subseteq\R$ is bounded above when some real $b$ satisfies $x\le b$ for all $x\in S$, and such a $b$ is an upper bound. The least upper bound, or supremum, is the smallest upper bound. We take its existence as the defining axiom of the real numbers.

Definition1

The reals satisfy the least upper bound axiom. Every nonempty subset of $\R$ that is bounded above has a least upper bound $\sup S\in\R$, characterised by two properties. First, $x\le\sup S$ for every $x\in S$. Second, for every $\varepsilon>0$ there is an $x\in S$ with $x>\sup S-\varepsilon$.

The second property is the working form. It says no number below $\sup S$ is an upper bound, so points of $S$ come arbitrarily close to the supremum. The symmetric notion of the greatest lower bound, the infimum $\inf S$, exists for every nonempty set bounded below, by applying the axiom to $-S$. The rationals fail this axiom, since the set of rationals whose square is below $2$ is bounded above but has no rational least upper bound, and that single failure is the hole that completeness removes.

#Sequences and limits

A sequence is a function $n\mapsto a_n$ from $\N$ to $\R$. Convergence is the statement that the terms settle near a single number.

Definition2

The sequence $(a_n)$ converges to the limit $L$ when for every $\varepsilon>0$ there is an $N\in\N$ such that $\abs{a_n-L}<\varepsilon$ for all $n\ge N$. We write $a_n\to L$.

The number $\varepsilon$ is the tolerance and $N$ is how far out one must go to meet it. A limit, when it exists, is unique.

Theorem3

A convergent sequence has exactly one limit.

Proof

Suppose $a_n\to L$ and $a_n\to L'$. Fix $\varepsilon>0$. Choose $N_1$ with $\abs{a_n-L}<\varepsilon/2$ for $n\ge N_1$ and $N_2$ with $\abs{a_n-L'}<\varepsilon/2$ for $n\ge N_2$. For any $n\ge\max(N_1,N_2)$ the triangle inequality gives

$$\abs{L-L'}\le\abs{L-a_n}+\abs{a_n-L'}<\frac{\varepsilon}{2}+\frac{\varepsilon}{2}=\varepsilon. \tag{1}$$(1)

Since $\abs{L-L'}<\varepsilon$ for every $\varepsilon>0$, the nonnegative number $\abs{L-L'}$ is zero, so $L=L'$.

A sequence is bounded when the set of its terms is bounded above and below. Every convergent sequence is bounded, since all terms past some index lie within distance one of $L$, and the finitely many earlier terms are bounded on their own, and the converse fails, as $(-1)^n$ shows. Completeness is what repairs the converse for the monotone case.

#Monotone convergence

A sequence is increasing when $a_n\le a_{n+1}$ for all $n$, and decreasing when the inequality reverses. For monotone sequences boundedness alone forces convergence, and the limit is the supremum.

Theorem4

An increasing sequence that is bounded above converges to the supremum of its terms. A decreasing sequence bounded below converges to the infimum.

Proof

Let $(a_n)$ be increasing and bounded above, and set $L=\sup\{a_n\}$, which exists by Definition 1. Fix $\varepsilon>0$. By the second property of the supremum there is an index $N$ with $a_N>L-\varepsilon$. Since the sequence is increasing, $a_n\ge a_N>L-\varepsilon$ for every $n\ge N$, and since $L$ is an upper bound, $a_n\le L<L+\varepsilon$. Combining the two, $L-\varepsilon<a_n<L+\varepsilon$, that is $\abs{a_n-L}<\varepsilon$, for all $n\ge N$, so $a_n\to L$. The decreasing case follows by negation, applying the increasing case to $(-a_n)$.

This is the first theorem that turns the static axiom into a dynamic statement about limits. A bounded increasing sequence presses upward against a ceiling, and completeness guarantees that ceiling is a real number it converges to.

#Bolzano-Weierstrass

Boundedness alone, without monotonicity, does not give convergence, but it gives a convergent subsequence. A subsequence keeps the terms at a strictly increasing set of indices $n_1<n_2<\cdots$.

Theorem5

Every bounded sequence of reals has a convergent subsequence.

Proof

First, every sequence has a monotone subsequence. Call an index $m$ a peak when $a_m\ge a_n$ for all $n>m$. If there are infinitely many peaks $m_1<m_2<\cdots$, then $a_{m_1}\ge a_{m_2}\ge\cdots$ is a decreasing subsequence. If there are only finitely many peaks, let $N$ exceed them all, so no index $>N$ is a peak. Since $N$ is not a peak there is $n_1>N$ with $a_{n_1}>a_N$, and since each $n_j>N$ is again not a peak there is $n_{j+1}>n_j$ with $a_{n_{j+1}}>a_{n_j}$. The recursion never stalls because the not-a-peak property holds at every $n_j>N$, not just the first step, so induction yields a strictly increasing subsequence. Either way a monotone subsequence exists. It is bounded because the sequence is, so by Theorem 4 it converges.

The theorem is the workhorse of compactness. It says the terms of a bounded sequence cannot stay uniformly separated, since some subsequence must cluster at a limit, and that clustering is exactly what later arguments extract a useful number from.

#Cauchy sequences

The definition of a limit names the limit $L$ in advance. The Cauchy criterion tests convergence without knowing the limit, by asking whether the terms bunch together.

Definition6

The sequence $(a_n)$ is Cauchy when for every $\varepsilon>0$ there is an $N$ such that $\abs{a_m-a_n}<\varepsilon$ for all $m,n\ge N$.

Theorem7

A sequence of reals converges if and only if it is Cauchy.

Proof

Suppose $a_n\to L$. Given $\varepsilon>0$ choose $N$ with $\abs{a_n-L}<\varepsilon/2$ for $n\ge N$. Then for $m,n\ge N$, $\abs{a_m-a_n}\le\abs{a_m-L}+\abs{L-a_n}<\varepsilon$, so the sequence is Cauchy. Conversely suppose $(a_n)$ is Cauchy. Taking $\varepsilon=1$ gives an $N$ with $\abs{a_n-a_N}<1$ for $n\ge N$, so the sequence is bounded by the larger of $\max_{k<N}\abs{a_k}$ and $\abs{a_N}+1$, the empty max being omitted when $N$ is the first index. By Theorem 5 some subsequence converges, $a_{n_k}\to L$. Fix $\varepsilon>0$, take $N$ from the Cauchy property with tolerance $\varepsilon/2$, and take $k$ large enough that $n_k\ge N$ and $\abs{a_{n_k}-L}<\varepsilon/2$. Then for every $n\ge N$,

$$\abs{a_n-L}\le\abs{a_n-a_{n_k}}+\abs{a_{n_k}-L}<\frac{\varepsilon}{2}+\frac{\varepsilon}{2}=\varepsilon, \tag{2}$$(2)

so $a_n\to L$.

The forward direction holds in any metric space. The converse is where completeness enters, through the Bolzano-Weierstrass step, and a space in which every Cauchy sequence converges is called complete. The reals are complete, the rationals are not, and the Cauchy criterion is the form of completeness that generalises, since it never mentions order or suprema.

#The four faces of completeness

The statements above are not independent improvements. Each implies the others, so completeness has one content and several forms, and a development of analysis may take any one as the axiom and derive the rest.

Form	Statement
Least upper bound	Every nonempty set bounded above has a supremum in $\R$
Monotone convergence	Every bounded monotone sequence converges
Bolzano-Weierstrass	Every bounded sequence has a convergent subsequence
Cauchy criterion	Every Cauchy sequence converges

We proved the chain from the least upper bound axiom downward, supremum to monotone convergence to Bolzano-Weierstrass to the Cauchy criterion. One ingredient deserves explicit mention before the cycle closes. The Archimedean property, that for every real $x$ there is a natural number exceeding it, follows from the least upper bound axiom, since if $\N$ were bounded above it would have a supremum $s$, and then $s-1$ would fail to be an upper bound, giving a natural $n>s-1$ and hence $n+1>s$, a contradiction. The Archimedean property is what makes $1/n\to 0$ and $2^{-n}\to 0$, the limits used throughout.

The Cauchy criterion now recovers the supremum by bisection. Given a nonempty set $S$ bounded above, take an interval $[l_0,r_0]$ whose right endpoint is an upper bound of $S$ and whose left endpoint is not, and halve it repeatedly, always keeping the right endpoint $r_k$ an upper bound of $S$ and the left endpoint $l_k$ not one. The interval length is $r_k-l_k=(r_0-l_0)2^{-k}$, and $r_k-l_k\to 0$ because $2^{-k}\to 0$, which is exactly the Archimedean property ($2^k>k$ exceeds $1/\varepsilon$ for large $k$). This is the one step where the separately assumed Archimedean hypothesis is consumed. The endpoint sequences are therefore Cauchy and converge to a common limit $L$. That $L$ is an upper bound follows because each $x\in S$ satisfies $x\le r_k$ for all $k$ and $r_k\to L$, so $x\le L$. No smaller number is an upper bound, since for any $c<L$ the increasing $l_k\to L$ gives a $k$ with $l_k>c$, and as $l_k$ is not an upper bound some $x\in S$ has $x>l_k>c$. Hence $L=\sup S$. All four statements are therefore equivalent over the ordered field with the Archimedean property, and a development may take any one of them as its axiom.

Everything later stands on this. The monotone convergence theorem for sequences is the seed of the monotone convergence theorem for integrals, the Cauchy criterion is the completeness that makes Banach and Hilbert spaces work, and the Bolzano-Weierstrass theorem is the compactness behind the existence of maxima, fixed points, and the spectral decompositions that later posts depend on. Completeness is not one theorem among many. It is the assumption that lets a limit denote a number.