Compactness, extreme values and uniform continuity

A continuous function on an open interval can misbehave badly: \(\frac{1}{x}\) on \((0, 1)\) is unbounded, and \(x\) on \((0, 1)\) is bounded but never reaches its supremum. On a closed bounded interval neither failure can occur. The property of \([a, b]\) responsible is compactness, which in the real line follows from the Bolzano–Weierstrass theorem. This lesson defines closed and compact sets, proves the extreme value theorem, introduces uniform continuity, and proves the Heine–Cantor theorem that continuous functions on compact sets are uniformly continuous. These results are the engine behind the mean value theorem in lesson 10 and the integrability of continuous functions in lesson 12.

Closed sets

Definition. A set \(K \subseteq \mathbb{R}\) is closed if it contains all its limit points; equivalently, whenever \((x_n)\) is a sequence in \(K\) with \(x_n \to x\), the limit \(x\) is in \(K\).

Closed intervals \([a, b]\) are closed: if \(a \le x_n \le b\) and \(x_n \to x\), then \(a \le x \le b\) by the order limit theorem of lesson 4. Open intervals are not: \(\frac{1}{n} \in (0, 1)\) converges to \(0 \notin (0, 1)\). The sets \(\mathbb{R}\), \(\mathbb{Z}\), finite sets and \(\{0\} \cup \{\frac{1}{n} : n \ge 1\}\) are closed; \(\mathbb{Q}\) is not, since rational sequences can converge to \(\sqrt{2}\).

Closed and open are not opposites. A set is closed exactly when its complement is open, in the sense of lesson 8, but most sets, such as \([0, 1)\) or \(\mathbb{Q}\), are neither, and \(\mathbb{R}\) and the empty set are both.

Compact sets

Definition. A set \(K \subseteq \mathbb{R}\) is (sequentially) compact if every sequence in \(K\) has a subsequence that converges to a point of \(K\).

Theorem. A subset of \(\mathbb{R}\) is compact if and only if it is closed and bounded.

Proof. Suppose \(K\) is closed and bounded, and let \((x_n)\) be a sequence in \(K\). It is bounded, so by Bolzano–Weierstrass it has a convergent subsequence, whose limit lies in \(K\) because \(K\) is closed. Conversely suppose \(K\) is compact. If \(K\) were unbounded, we could choose \(x_n \in K\) with \(|x_n| > n\); no subsequence of this sequence is bounded, so none converges. If \(K\) were not closed, some sequence in \(K\) would converge to a point \(x \notin K\); every subsequence also converges to \(x\), so no subsequence has a limit in \(K\). \(\blacksquare\)

So \([a, b]\) is compact, while \((0, 1)\), \([0, \infty)\) and \(\mathbb{Q} \cap [0, 1]\) are not. In MATH-341 compactness is defined instead by open covers, every cover by open sets having a finite subcover. In \(\mathbb{R}\) and \(\mathbb{R}^n\) the two definitions agree; the equivalence of the cover form with closed and bounded is the Heine–Borel theorem.

Continuous images of compact sets

Theorem. If \(f: K \to \mathbb{R}\) is continuous and \(K\) is compact, then \(f(K)\) is compact.

Proof. Let \((y_n)\) be a sequence in \(f(K)\), say \(y_n = f(x_n)\) with \(x_n \in K\). By compactness some subsequence \(x_{n_k} \to x \in K\). By sequential continuity \(y_{n_k} = f(x_{n_k}) \to f(x) \in f(K)\). \(\blacksquare\)

Theorem (extreme value theorem). A continuous function on a non-empty compact set, in particular on \([a, b]\), is bounded and attains its maximum and minimum: there are \(p, q \in K\) with \(f(q) \le f(x) \le f(p)\) for every \(x \in K\).

Proof. \(f(K)\) is compact, hence bounded, so \(M = \sup f(K)\) exists. For each \(n\) there is a value of \(f\) within \(\frac{1}{n}\) of \(M\), so there is a sequence in \(f(K)\) converging to \(M\). Since \(f(K)\) is closed, \(M \in f(K)\), that is \(M = f(p)\) for some \(p\). The minimum is similar. \(\blacksquare\)

Each hypothesis is needed. On \((0, 1]\), \(\frac{1}{x}\) is continuous and unbounded. On \([0, \infty)\), \(\frac{x}{1 + x}\) is bounded with supremum 1 never attained. On \([-1, 1]\), the function equal to \(\frac{1}{x}\) for \(x \ne 0\) and to 0 at 0 is unbounded, which is possible only because it is discontinuous at 0. Combined with the intermediate value theorem, the extreme value theorem says the image of \([a, b]\) under a continuous function is a closed bounded interval \([m, M]\).

Uniform continuity

In lesson 8 the \(\delta\) for \(\sqrt{x}\) at \(c\) was \(\varepsilon\sqrt{c}\), which shrinks as \(c \to 0\). For \(\frac{1}{x}\) on \((0, 1)\) the situation is worse: near 0 the graph is so steep that \(\delta\) must shrink to 0. Uniform continuity asks for a single \(\delta\) that works at every point at once.

Definition. \(f: A \to \mathbb{R}\) is uniformly continuous on \(A\) if for every \(\varepsilon > 0\) there is \(\delta > 0\) such that \(|f(x) - f(y)| < \varepsilon\) for all \(x, y \in A\) with \(|x - y| < \delta\).

The difference from continuity is the order of quantifiers. Continuity: for every \(c\) and every \(\varepsilon\) there is \(\delta\), which may depend on \(c\). Uniform continuity: for every \(\varepsilon\) there is \(\delta\) that works for every \(c\).

Functions satisfying \(|f(x) - f(y)| \le K|x - y|\) for a constant \(K\) are called Lipschitz, after Rudolf Lipschitz; they are uniformly continuous with \(\delta = \frac{\varepsilon}{K}\). Example (b) shows that \(x^2\) is Lipschitz on any bounded interval. The function \(\sqrt{x}\) on \([0, 1]\) is uniformly continuous but not Lipschitz, since \(\frac{\sqrt{x}}{x} \to \infty\) as \(x \to 0\).

The Heine–Cantor theorem

Theorem. A continuous function on a compact set is uniformly continuous.

Proof. Suppose \(f\) is continuous on compact \(K\) but not uniformly continuous. Negating the definition, there is \(\varepsilon_0 > 0\) such that for every \(n\) there are \(x_n, y_n \in K\) with \(|x_n - y_n| < \frac{1}{n}\) but \(|f(x_n) - f(y_n)| \ge \varepsilon_0\). By compactness some subsequence \(x_{n_k} \to z \in K\). Then \(y_{n_k} \to z\) as well, since \(|y_{n_k} - z| \le |y_{n_k} - x_{n_k}| + |x_{n_k} - z|\). By continuity at \(z\), both \(f(x_{n_k})\) and \(f(y_{n_k})\) tend to \(f(z)\), so their difference tends to 0, contradicting \(|f(x_{n_k}) - f(y_{n_k})| \ge \varepsilon_0\). \(\blacksquare\)

Heine published the result in 1872, and it was implicit in Dirichlet's lectures of 1854; Cantor's name is attached because Heine credited ideas from him. The theorem is exactly what is needed to show that continuous functions are Riemann integrable: on a fine enough partition of \([a, b]\), the function varies by less than \(\varepsilon\) on every subinterval simultaneously.

import math

def best_delta(f, a, b, eps, grid=20000):
    """Largest delta (found by bisection) with |f(x + delta) - f(x)| < eps at every grid point x.
    For the monotone functions below, pairs exactly delta apart are the worst case."""
    def ok(d):
        h = (b - d - a) / grid
        return all(abs(f(a + i * h + d) - f(a + i * h)) < eps for i in range(grid + 1))
    lo, hi = 0.0, b - a
    for _ in range(50):
        mid = (lo + hi) / 2
        lo, hi = (mid, hi) if ok(mid) else (lo, mid)
    return lo

eps = 0.1
for name, f, a, b in [("x^2 on [0, 5]", lambda x: x * x, 0, 5),
                      ("sqrt(x) on [0, 1]", math.sqrt, 0, 1),
                      ("1/x on [0.1, 1]", lambda x: 1 / x, 0.1, 1),
                      ("1/x on [0.01, 1]", lambda x: 1 / x, 0.01, 1),
                      ("1/x on [0.001, 1]", lambda x: 1 / x, 0.001, 1)]:
    print(f"{name:<20} eps = {eps}: one delta for the whole interval is about {best_delta(f, a, b, eps):.3g}")

x^2 on [0, 5]        eps = 0.1: one delta for the whole interval is about 0.01
sqrt(x) on [0, 1]    eps = 0.1: one delta for the whole interval is about 0.01
1/x on [0.1, 1]      eps = 0.1: one delta for the whole interval is about 0.00101
1/x on [0.01, 1]     eps = 0.1: one delta for the whole interval is about 1e-05
1/x on [0.001, 1]    eps = 0.1: one delta for the whole interval is about 1e-07

The output for \(\frac{1}{x}\) shows the failure of uniform continuity on \((0, 1)\) numerically: on \([t, 1]\) the best \(\delta\) for \(\varepsilon = 0.1\) is about \(0.1t^2\), which tends to 0 with \(t\). Each \([t, 1]\) is compact, so a single \(\delta\) exists there, as Heine–Cantor promises, but no single \(\delta\) serves the whole open interval.

Extending continuous functions

Uniform continuity has a useful consequence: a uniformly continuous function maps Cauchy sequences to Cauchy sequences. If \(|x_m - x_n| < \delta\) for \(m, n \ge N\), then \(|f(x_m) - f(x_n)| < \varepsilon\) for the same \(m, n\). It follows that a uniformly continuous function on \((a, b)\) has limits at both endpoints and so extends continuously to \([a, b]\). The function \(\sin\frac{1}{x}\) on \((0, 1)\) has no limit at 0, so it cannot be uniformly continuous there, even though it is bounded.

The same idea shows how a function defined only on \(\mathbb{Q}\) can be extended to \(\mathbb{R}\). If \(f: \mathbb{Q} \to \mathbb{R}\) is uniformly continuous on bounded sets, define \(F(x) = \lim f(q_n)\) for any rational sequence \(q_n \to x\). The limit exists because \((f(q_n))\) is Cauchy, and it does not depend on the sequence chosen. This is one way to define \(2^x\) for irrational \(x\) from its values at rationals.

A second proof of boundedness

The boundedness half of the extreme value theorem can also be proved by bisection, which shows clearly where completeness enters. Suppose \(f\) is continuous on \([a, b]\) but unbounded. Bisect the interval; \(f\) is unbounded on at least one half, so keep that half. Repeating gives nested closed intervals \(I_1 \supseteq I_2 \supseteq \dots\) with lengths \(\frac{b - a}{2^n}\), on each of which \(f\) is unbounded. By the nested interval property they share a point \(c\). Continuity at \(c\) with \(\varepsilon = 1\) gives \(\delta > 0\) with \(|f(x)| < |f(c)| + 1\) for \(|x - c| < \delta\). But once \(\frac{b - a}{2^n} < \delta\), the whole interval \(I_n\) lies within \(\delta\) of \(c\), so \(f\) is bounded on \(I_n\), a contradiction.

The argument has a pattern that recurs throughout analysis: a property that holds near every point, here local boundedness, is upgraded to a property of the whole interval. Compactness is precisely what makes local information global. Uniform continuity is another instance: continuity gives a \(\delta\) near each point, and compactness lets one \(\delta\) serve everywhere.

Compactness beyond the line

In \(\mathbb{R}^n\) compact sets are again the closed bounded ones, and the extreme value theorem holds for continuous functions of several variables; this is why a continuous function on a closed disc attains a maximum, a fact used constantly in optimization. In infinite-dimensional spaces closed and bounded is no longer enough. The closed unit ball of a space of functions is not compact, and much of functional analysis is about recovering compactness in weaker forms. The sequence definition used in this lesson is the one that generalizes most directly.