ACE 328/Chapter 6

Completeness and Cauchy Sequences

Cauchy sequences capture the intuitive notion of "eventually close" without requiring a limit. Complete spaces are those in which every Cauchy sequence converges.

Completeness is the property that distinguishes the real numbers from the rationals: every Cauchy sequence converges. It is the property that underlies fixed-point theorems, the construction of solutions to differential equations, and the Baire Category Theorem — an astonishingly powerful tool that, among other things, tells us that a "typical" continuous function on $[a, b]$ is nowhere differentiable. This chapter develops completeness systematically: definition and first examples, the Banach fixed-point (contraction mapping) theorem with its proof and applications, Cantor's intersection theorem, a brief discussion of metric completions, and the Baire Category Theorem.

Cauchy Sequences

We begin by recalling the definition of a Cauchy sequence and its basic properties.

DefinitionCauchy Sequence

A sequence $(x_n)_{n \geq 1}$ in a metric space $(X, d)$ is a Cauchy sequence if for every $\varepsilon > 0$ there exists $N \geq 1$ such that $d(x_n, x_m) < \varepsilon \quad \text{for all } n, m \geq N.$

Remark.

Intuition: A Cauchy sequence is one whose terms cluster together: beyond some index, all pairs of terms are arbitrarily close. The notion is "internal" — it uses only the sequence itself, without reference to a candidate limit. This makes it powerful: we can check whether a sequence should converge without knowing its limit in advance.

TheoremEvery Convergent Sequence is Cauchy

Let $(X, d)$ be a metric space. If $x_n \to x$ , then $(x_n)$ is Cauchy.

TheoremCauchy Sequences are Bounded

Every Cauchy sequence in a metric space is bounded.

The converse of "convergent implies Cauchy" is not true in every metric space — it is the content of the following definition.

Complete Metric Spaces

DefinitionComplete Metric Space

A metric space $(X, d)$ is complete if every Cauchy sequence in $X$ converges to a point of $X$ .

Remark.

Intuition: Completeness is the absence of "holes." If a sequence bunches up, there is actually a point inside the space where it bunches. Non-complete spaces have a ghost limit just outside; completion (discussed below) fills in these ghosts.

Examples and Non-Examples

TheoremThe Real Line is Complete

The real line $\mathbb{R}$ with the Euclidean metric is complete.

TheoremEuclidean Space is Complete

Euclidean space $\mathbb{R}^d$ is complete.

ExampleThe Rationals are Not Complete

The rationals $\mathbb{Q}$ with the standard metric $d(x, y) = |x - y|$ form a metric space that is not complete. For example, the sequence $a_n = \left(1 + \frac{1}{n}\right)^n \in \mathbb{Q}$ is Cauchy (it is convergent in $\mathbb{R}$ , hence Cauchy there, hence Cauchy in $\mathbb{Q}$ ), but its would-be limit $e$ is irrational, so the sequence does not converge in $\mathbb{Q}$ .

ExampleOpen Intervals are Not Complete

The space $X = (0, 1)$ with $d(x, y) = |x - y|$ is not complete: $a_n = 1/n$ is Cauchy but its limit $0$ is not in $X$ . This illustrates that completeness depends on both the underlying set and the metric. Removing the endpoints creates "holes."

TheoremA Closed Subset of a Complete Metric Space is Complete

Let $(X, d)$ be complete and $F \subseteq X$ closed. Then $(F, d|_F)$ is complete.

TheoremA Complete Subspace is Closed

Let $(X, d)$ be a metric space and $Y \subseteq X$ a subset such that $(Y, d|_Y)$ is complete. Then $Y$ is closed in $X$ .

The Space of Continuous Functions

One of the most useful examples of a complete metric space is the space of continuous functions with the sup norm.

TheoremThe Space of Continuous Functions is Complete

Let $C([a,b]) = \{f : [a,b] \to \mathbb{R} : f \text{ is continuous}\}$ with the sup metric $d_\infty(f, g) = \|f - g\|_\infty = \sup_{x \in [a,b]} |f(x) - g(x)|.$ Then $(C([a,b]), d_\infty)$ is a complete metric space.

Remark.

Intuition: Convergence in the sup metric is uniform convergence: $f_n \to f$ iff $\sup_x |f_n(x) - f(x)| \to 0$ . The theorem says that a uniformly Cauchy sequence of continuous functions has a continuous limit. This is why the sup norm is such a useful tool in analysis: completeness gives us a stable playground for approximations.

The Banach Fixed-Point Theorem

A fixed point of a map $T : X \to X$ is a point $x$ with $T(x) = x$ . The Banach theorem (also known as the contraction mapping principle) is one of the most-applied theorems in all of analysis: it guarantees existence AND uniqueness of a fixed point, and gives an explicit iterative construction with exponential error decay.

DefinitionContraction

Let $(X, d)$ be a metric space. A map $T : X \to X$ is a contraction if there exists $K \in [0, 1)$ such that $d(T(x), T(y)) \leq K \, d(x, y) \quad \text{for all } x, y \in X.$ The number $K$ is called a contraction constant.

Remark.

Intuition: A contraction strictly shrinks distances by a uniform factor $K < 1$ . In particular, it is Lipschitz (hence continuous and uniformly continuous). The strictness of $K < 1$ is essential — with $K = 1$ , the map $x \mapsto x + 1$ on $\mathbb{R}$ shrinks nothing and has no fixed point.

TheoremBanach Fixed-Point Theorem (Contraction Mapping Principle)

Let $(X, d)$ be a nonempty complete metric space and $T : X \to X$ a contraction with contraction constant $K \in [0, 1)$ . Then:

(i) $T$ has a unique fixed point $x^* \in X$ .

(ii) For any initial point $x_0 \in X$ , the iterates $x_{n+1} = T(x_n)$ converge to $x^*$ .

(iii) We have the explicit error bound $d(x_n, x^*) \leq \frac{K^n}{1 - K} d(x_0, x_1) \quad \text{for all } n \geq 0.$

Remark.

Intuition: Pick any starting point, apply $T$ repeatedly, and the iterates converge exponentially to the unique fixed point — no matter what starting point you chose. The rate $K^n$ gives explicit quantitative control. This theorem powers proofs of the implicit function theorem, the Picard-Lindelof theorem for ODEs, and many numerical iteration schemes.

ExampleNewton-Type Iteration for the Square Root of Two

Define $T : [1, 2] \to [1, 2]$ by $T(x) = \frac{1}{2}\left(x + \frac{2}{x}\right)$ . Calculus shows $T$ maps $[1, 2]$ into itself and $|T'(x)| = \left|\frac{1}{2} - \frac{1}{x^2}\right| \leq \frac{1}{2} \quad \text{on } [1, 2],$ so $T$ is a contraction with constant $K = 1/2$ (by the mean value theorem). Since $[1, 2]$ is closed in $\mathbb{R}$ , it is complete. By Banach, there is a unique fixed point $x^* \in [1, 2]$ ; solving $T(x^*) = x^*$ gives $x^* = \sqrt{2}$ . Starting from $x_0 = 1$ produces the familiar Babylonian iteration converging rapidly to $\sqrt{2}$ .

Cantor's Intersection Theorem

Another consequence of completeness: nested closed "small" sets have a nonempty intersection.

DefinitionDiameter

The diameter of a nonempty subset $A$ of a metric space is $\mathrm{diam}(A) = \sup \{d(x, y) : x, y \in A\} \in [0, \infty].$

TheoremCantor's Intersection Theorem

Let $(X, d)$ be a complete metric space and let $F_1 \supseteq F_2 \supseteq F_3 \supseteq \cdots$ be a decreasing sequence of nonempty closed subsets with $\mathrm{diam}(F_n) \to 0$ . Then $\bigcap_{n=1}^{\infty} F_n$ consists of exactly one point.

Remark.

Intuition: Completeness guarantees that shrinking nested closed sets capture a unique point. Dropping any of the hypotheses kills the theorem: without completeness (e.g., in $\mathbb{Q}$ ) the intersection can be empty; without $\mathrm{diam}(F_n) \to 0$ (take $F_n = [n, \infty)$ in $\mathbb{R}$ ) the intersection can be empty; without closedness (take $F_n = (0, 1/n)$ ) the intersection can be empty.

Completion of a Metric Space (Brief)

Every metric space can be embedded in a canonical complete one — its "completion" — which fills in the missing limit points of Cauchy sequences. The standard construction of $\mathbb{R}$ from $\mathbb{Q}$ is one instance.

TheoremExistence of Completion (sketch)

Let $(X, d)$ be a metric space. There exists a complete metric space $(\widetilde{X}, \widetilde{d})$ and an isometric embedding $\iota : X \to \widetilde{X}$ such that $\iota(X)$ is dense in $\widetilde{X}$ . The pair $(\widetilde{X}, \iota)$ is unique up to isometry and is called the completion of $X$ .

Remark.

Construction sketch. Consider the set of all Cauchy sequences in $X$ . Define an equivalence relation $(x_n) \sim (y_n)$ iff $d(x_n, y_n) \to 0$ . Let $\widetilde{X}$ be the set of equivalence classes, with distance $\widetilde{d}([x_n], [y_n]) = \lim_n d(x_n, y_n)$ . Embed $X$ into $\widetilde{X}$ by $\iota(x) = [(x, x, x, \dots)]$ . The details of checking that $\widetilde{d}$ is a well-defined metric, that $\widetilde{X}$ is complete, and that $\iota(X)$ is dense are routine but tedious.

The completion of $\mathbb{Q}$ is $\mathbb{R}$ ; the completion of an open interval with the usual metric is its closure.

The Baire Category Theorem

The Baire Category Theorem is one of the deepest consequences of completeness, with applications throughout analysis. We begin with the underlying notion of "topologically small" sets.

DefinitionNowhere Dense, Meagre, Comeagre

Let $(X, \tau)$ be a topological space. A set $S \subseteq X$ is:

nowhere dense if $\mathrm{int}(\overline{S}) = \emptyset$ , equivalently, every nonempty open set contains a nonempty open subset disjoint from $S$ ;
meagre (or of first category) if $S$ is a countable union of nowhere dense sets;
non-meagre (or of second category) if $S$ is not meagre;
comeagre (or residual) if $X \setminus S$ is meagre, equivalently, $S$ contains a countable intersection of open dense sets.

Remark.

Intuition: "Meagre" is the topological analogue of "negligible." A nowhere dense set has empty interior even after closing, so it cannot fill up any piece of the space. A meagre set is a countable pile of such small sets. Comeagre sets are their complements — topologically "large." Baire's theorem says that in a complete metric space, these two notions do not contradict each other and, moreover, comeagre sets are genuinely big.

ExampleNowhere Dense and Meagre Sets on the Real Line

(1) $\mathbb{Z}$ is nowhere dense in $\mathbb{R}$ : $\overline{\mathbb{Z}} = \mathbb{Z}$ , and between any two integers lies a nonempty open interval disjoint from $\mathbb{Z}$ .

(2) The set $\{1/n : n \in \mathbb{N}\}$ is nowhere dense: its closure is $\{0\} \cup \{1/n\}$ , which contains no interval.

(3) $\mathbb{Q}$ is NOT nowhere dense: $\overline{\mathbb{Q}} = \mathbb{R}$ . But $\mathbb{Q}$ IS meagre — it is a countable union $\bigcup_{q \in \mathbb{Q}} \{q\}$ of singletons, each of which is nowhere dense.

(4) $\mathbb{R} \setminus \mathbb{Q}$ is comeagre (its complement $\mathbb{Q}$ is meagre). By Baire's theorem below, the irrationals are non-meagre.

TheoremBaire Category Theorem

Let $(X, d)$ be a nonempty complete metric space. Then:

(i) Every comeagre subset of $X$ is dense in $X$ .

(ii) $X$ is not meagre in itself.

Equivalently: $X$ cannot be written as a countable union of nowhere dense sets, and the intersection of countably many open dense subsets of $X$ is dense.

Remark.

Intuition: Completeness forces comeagre sets to be dense — you cannot hide a comeagre set in a small pocket of a complete space. The striking consequence is that many "generic" properties (what a typical element of $X$ looks like) can be proven by exhibiting a comeagre set of objects with that property. Baire's theorem guarantees that this comeagre set is nonempty, and in fact dense.

CorollaryMeagre and Comeagre are Disjoint in Complete Metric Spaces

In a nonempty complete metric space, no subset is simultaneously meagre and comeagre.

Applications of Baire

CorollaryThe Irrationals are Non-meagre

$\mathbb{R} \setminus \mathbb{Q}$ is non-meagre in $\mathbb{R}$ .

CorollaryNo Function is Continuous Exactly on the Rationals

There is no function $f : \mathbb{R} \to \mathbb{R}$ whose set of continuity points equals $\mathbb{Q}$ .

TheoremNowhere Differentiable Continuous Functions are Generic (Statement)

Let $C = C([a,b])$ with the sup metric. The set of functions $f \in C$ that are nowhere differentiable is comeagre in $C$ . Consequently, "most" continuous functions are nowhere differentiable. The same holds for the set of functions that are not monotonic on any subinterval.

Remark.

The full proof uses Baire's theorem: one exhibits the nowhere differentiable functions as the complement of a meagre set built from open dense approximations using the Weierstrass approximation theorem (polynomials are dense in $C$ ) and a sawtooth perturbation. Since $C$ is complete, the comeagre set is dense — in particular, nonempty — so such functions exist. The existence of even one nowhere differentiable continuous function was once shocking; Baire's theorem tells us the shocking objects are the norm, not the exception. The first explicit nowhere differentiable continuous function was constructed by Karl Weierstrass in 1872.

The Weierstrass Approximation Theorem

A central density result that plays a role in the proof of the previous theorem and many others.

TheoremWeierstrass Approximation Theorem

The set of polynomials is dense in $C([a, b])$ with the sup metric. Equivalently: for every $f \in C([a, b])$ and every $\varepsilon > 0$ there exists a polynomial $p$ such that $\max_{a \leq x \leq b} |f(x) - p(x)| < \varepsilon.$

Remark.

Intuition: Continuous functions on a closed bounded interval, no matter how complicated, can be approximated arbitrarily well in the sup norm by polynomials. This is striking because polynomials are extremely rigid (analytic, infinitely differentiable, determined by finitely many coefficients) yet they fill out the entire space of continuous functions.

Remark.

Probabilistic interpretation: The Bernstein polynomial $p_n(x)$ equals $\mathbb{E}[f(X_n / n)]$ where $X_n \sim \mathrm{Binomial}(n, x)$ . The law of large numbers says $X_n / n \to x$ in probability, and continuity of $f$ then yields $p_n(x) \to f(x)$ . Bernstein's proof packages this probabilistic intuition into an elementary inequality argument.

Nowhere Differentiable Functions: Detailed Construction

We now sketch the full proof that nowhere differentiable, nowhere monotonic functions form a comeagre set in $C([a, b])$ .

For each $n \geq 1$ , define

$R_n = \{f \in C^0 : \forall x \in [a, b - 1/n], \, \exists h > 0 \text{ such that } |(f(x + h) - f(x))/h| > n\}$ ,
$L_n = \{f \in C^0 : \forall x \in [a + 1/n, b], \, \exists h < 0 \text{ such that } |(f(x + h) - f(x))/h| > n\}$ ,
$G_n = \{f \in C^0 : \forall c \in [a, b - 1/n], \, f \text{ is not monotonic on } [c, c + 1/n]\}$ .

Functions in $\bigcap_{n \geq 1} (R_n \cap L_n)$ are nowhere differentiable; functions in $\bigcap_{n \geq 1} G_n$ are nowhere monotonic. The strategy is:

Claim 1: Each $R_n$ , $L_n$ , $G_n$ is dense in $C^0$ .

It suffices to show their closures contain the polynomials, since polynomials are dense by Weierstrass. Given a polynomial $p$ and $\varepsilon > 0$ , let $m = \max_{[a, b]} |p'(x)|$ and consider a sawtooth function $\sigma : [a, b] \to \mathbb{R}$ of amplitude less than $\varepsilon$ with slopes alternating between $> n + m$ and $< -(n + m)$ , with period less than $1/(2n)$ . The function $f = p + \sigma$ satisfies $\|f - p\| < \varepsilon$ and has rightward slopes greater than $n$ at every point of $[a, b - 1/n]$ , so $f \in R_n$ . A similar construction handles $L_n$ and $G_n$ .

Claim 2: Each $R_n$ , $L_n$ , $G_n$ is open in $C^0$ .

The arguments use compactness of $[a, b - 1/n]$ to cover by finitely many neighbourhoods. We sketch $R_n$ : given $f \in R_n$ , for each $x \in [a, b - 1/n]$ pick $h(x) > 0$ with $|(f(x + h(x)) - f(x))/h(x)| > n$ . By continuity there is a neighbourhood $U(x)$ of $x$ and $\nu(x) > 0$ such that for all $y \in \overline{U(x)}$ , $|(f(y + h(x)) - f(y))/h(x)| > n + \nu(x)$ . By compactness, finitely many such neighbourhoods $U(x_1), \ldots, U(x_N)$ cover $[a, b - 1/n]$ . With careful estimates (using the reverse triangle inequality), one shows that any $g$ with $\|f - g\|_\infty < \delta := \min_i (h(x_i) \nu(x_i)) / 4$ also belongs to $R_n$ .

The argument for $G_n$ instead shows $G_n^c$ is closed: if $(f_k) \subseteq G_n^c$ and $f_k \to f$ uniformly, then each $f_k$ is monotonic on some interval $I_k$ of length $1/n$ . By Bolzano-Weierstrass on the endpoints, a subsequence of intervals $I_{k_\ell}$ converges to a limit interval $I$ of length $1/n$ ; uniform convergence then forces $f$ to be monotonic on $I$ , so $f \in G_n^c$ .

Putting it together. Each $R_n$ , $L_n$ , $G_n$ is open and dense, hence so is each intersection $R_n \cap L_n \cap G_n$ . Their countable intersection $\bigcap_n (R_n \cap L_n \cap G_n)$ is comeagre in $C^0$ . Since $C^0$ is complete, this set is non-meagre by Baire (ii) — in particular nonempty and dense. Functions in this intersection are nowhere differentiable and nowhere monotonic.

Remark.

The "shocking" examples of nowhere differentiable continuous functions are not exceptional — they are topologically generic. Any function you encounter in calculus (polynomials, $\sin$ , $\cos$ , $e^x$ ) is part of a meagre set of "highly atypical" functions from the topological viewpoint.

Diophantine and Liouville Numbers

Another striking application of the Baire Category Theorem produces a comeagre set of "Diophantine" numbers and shows that the much smaller (but nonempty!) complement consists of remarkably well-approximable irrationals.

DefinitionDiophantine and Liouville Numbers

For $\tau, \gamma > 0$ , $q \in \mathbb{Z}_{\geq 1}$ , and $p \in \mathbb{Z}$ , define the closed set $D(\tau, \gamma, q, p) = \left\{x \in \mathbb{R} : \left| x - \frac{p}{q} \right| \geq \gamma q^{-\tau} \right\}.$ Then define the closed sets $D(\tau, \gamma) = \bigcap_{q \geq 1, \, p \in \mathbb{Z}} D(\tau, \gamma, q, p), \qquad D(\tau) = \bigcup_{\gamma > 0} D(\tau, \gamma) = \bigcup_{n \geq 1} D(\tau, 1/n),$ and finally $D = \bigcup_{\tau > 0} D(\tau) = \bigcup_{m \geq 1} D(m).$ Elements of $D$ are called Diophantine numbers. The set $\mathcal{L} = D^c \setminus \mathbb{Q}$ consists of the Liouville numbers: irrationals $x$ such that for every $m \geq 1$ there exist integers $q \geq 1$ and $p$ with $0 < \left| x - \frac{p}{q} \right| < \frac{1}{q^m}.$ (That is, $x$ can be approximated by rationals to arbitrarily high polynomial order in the denominator.)

Remark.

Intuition: Diophantine numbers are "badly approximable" by rationals — there is some lower bound on how close a rational $p/q$ can be in terms of $q^\tau$ . Liouville numbers are the opposite extreme: they admit super-fast rational approximations. Liouville proved in 1844 that all Liouville numbers are transcendental. A concrete example is $x = \sum_{k=1}^{\infty} 10^{-k!} = 0.110001000000000000000001\ldots$

TheoremThe Diophantine Set is Meagre; the Liouville Set is Comeagre

The set of Diophantine numbers $D$ is meagre in $\mathbb{R}$ , while $D^c$ is comeagre. Moreover $D^c$ is uncountable, and even $\mathcal{L} = D^c \setminus \mathbb{Q}$ is comeagre.

Remark.

Topological vs measure-theoretic largeness disagree! From the topological viewpoint, $D^c$ (which contains the Liouville numbers) is "large" (comeagre) and $D$ is "small" (meagre). But from the measure-theoretic viewpoint (Lebesgue measure on $\mathbb{R}$ ), it is the opposite: $D^c$ has measure zero and $D$ has full measure. In summary, $\mathbb{R} = D \cup \mathcal{L} \cup \mathbb{Q}$ is a disjoint union with:

$D$ : full measure, but meagre;
$\mathcal{L}$ : measure zero, but comeagre;
$\mathbb{Q}$ : measure zero and meagre.

This contrast between topological smallness ("meagre") and measure-theoretic smallness ("null") will reappear in the integration chapter.

ExampleConcrete Liouville Number

The number $x = \sum_{k=1}^{\infty} 10^{-k!} = \frac{1}{10^1} + \frac{1}{10^2} + \frac{1}{10^6} + \frac{1}{10^{24}} + \frac{1}{10^{120}} + \cdots = 0.\underbrace{11000100000000000000000\overbrace{1}^{24!}\ldots}_{\text{1's at positions }k!}$ is a Liouville number: take $q = 10^{m!}$ and $p = q \sum_{k=1}^{m} 10^{-k!}$ (an integer); then $|x - p/q| < 2 \cdot 10^{-(m+1)!} \ll 1/q^m$ for $m$ large.

By Liouville's 1844 theorem, $x$ is transcendental. Other notable Diophantine numbers include $\pi$ , $e$ , $\ln 2$ , $\sqrt{2}$ , and $\sqrt[3]{2}$ .