Completeness & Compactness

Let $S \subseteq \mathbb{R}$ be nonempty. A number $M \in \mathbb{R}$ is an upper bound of $S$ if $s \leq M$ for all $s \in S$. The supremum (least upper bound) $\sup S$ is an upper bound of $S$ with the property that if $M$ is any other upper bound of $S$, then $\sup S \leq M$.

Dually, $m$ is a lower bound of $S$ if $m \leq s$ for all $s \in S$, and the infimum $\inf S$ is the greatest lower bound.

Every nonempty subset of $\mathbb{R}$ that is bounded above has a supremum in $\mathbb{R}$.

The following are equivalent:

(a) The LUB Property: Every nonempty subset of $\mathbb{R}$ bounded above has a supremum in $\mathbb{R}$.

(b) Monotone Convergence Theorem: Every bounded monotone sequence in $\mathbb{R}$ converges.

(c) Nested Interval Property: If $[a_1, b_1] \supseteq [a_2, b_2] \supseteq \cdots$ is a nested sequence of closed bounded intervals with $b_n - a_n \to 0$, then $\bigcap_{n=1}^{\infty} [a_n, b_n]$ contains exactly one point.

(d) Cauchy Completeness: Every Cauchy sequence in $\mathbb{R}$ converges to a point in $\mathbb{R}$.

We sketch the cycle of implications.

(a) ⟹ (b): Let $(a_n)$ be bounded and increasing. The set $\{a_n\}$ is bounded above, so $L = \sup\{a_n\}$ exists by the LUB property. For every $\varepsilon > 0$, the approximation property gives $a_N > L - \varepsilon$ for some $N$. Since $(a_n)$ is increasing, $a_n \geq a_N > L - \varepsilon$ for all $n \geq N$. And $a_n \leq L$ since $L$ is an upper bound. So $|a_n - L| < \varepsilon$ for all $n \geq N$. This was proved as Theorem 1 in Sequences, Limits & Convergence.

(b) ⟹ (c): The sequence $(a_n)$ is increasing and bounded above (by $b_1$), so $a_n \to a$ by MCT. Similarly $b_n \to b$ is decreasing and bounded below. Since $a_n \leq b_n$ for all $n$, we have $a \leq b$. If $b_n - a_n \to 0$, then $b = a$, and $\{a\} = \bigcap [a_n, b_n]$.

(c) ⟹ Bolzano-Weierstrass: Given a bounded sequence in $[a, b]$, repeatedly bisect: at least one half contains infinitely many terms. The Nested Interval Property guarantees the bisected intervals converge to a point, which is the limit of the extracted subsequence. This was the strategy behind Theorem 4 in Sequences, Limits & Convergence.

Bolzano-Weierstrass ⟹ (d): Every Cauchy sequence is bounded (proved in Sequences, Limits & Convergence, Theorem 5). Bolzano-Weierstrass gives a convergent subsequence $a_{n_k} \to L$. A Cauchy sequence with a convergent subsequence converges to the same limit: for $\varepsilon > 0$, choose $N$ so that $|a_m - a_n| < \varepsilon/2$ for $m, n \geq N$ and $|a_{n_k} - L| < \varepsilon/2$ for $n_k \geq N$. Then $|a_n - L| \leq |a_n - a_{n_k}| + |a_{n_k} - L| < \varepsilon$.

(d) ⟹ (a): Let $S$ be nonempty and bounded above. We construct a Cauchy sequence converging to $\sup S$. Start with any upper bound $b_0$ and any $s_0 \in S$. Bisect $[s_0, b_0]$: if the midpoint is an upper bound of $S$, take the left half; otherwise, the right half. This produces intervals of width $(b_0 - s_0)/2^n \to 0$, and the endpoints form Cauchy sequences. By Cauchy completeness, they converge to some $\alpha \in \mathbb{R}$, which we verify is $\sup S$.

In machine learning, completeness ensures that iterative algorithms have a limit. When gradient descent produces a Cauchy sequence of parameters $\theta_t$ — meaning the updates $\|\theta_{t+1} - \theta_t\|$ get arbitrarily small — completeness guarantees convergence to some $\theta^* \in \mathbb{R}^d$. Without completeness, the “limit” might not exist, like $\sqrt{2}$ in $\mathbb{Q}$.

If $[a_1, b_1] \supseteq [a_2, b_2] \supseteq \cdots$ is a nested sequence of closed, bounded intervals, then $\bigcap_{n=1}^{\infty} [a_n, b_n] \neq \emptyset$. If additionally $b_n - a_n \to 0$, then the intersection contains exactly one point.

Let $a = \sup\{a_n\}$, which exists by the LUB property since the $a_n$ are bounded above by $b_1$. Let $b = \inf\{b_n\}$, which exists since the $b_n$ are bounded below by $a_1$.

We claim $a \leq b$. For any $n, m$, the nesting gives $a_n \leq b_m$ (if $n \leq m$, then $a_n \leq a_m \leq b_m$; if $m \leq n$, then $a_n \leq b_n \leq b_m$). So every $b_m$ is an upper bound for $\{a_n\}$, hence $a = \sup\{a_n\} \leq b_m$ for all $m$, hence $a \leq \inf\{b_m\} = b$.

Now $a \in [a_n, b_n]$ for all $n$ (because $a_n \leq a$ and $a \leq b \leq b_n$), so $a \in \bigcap [a_n, b_n] \neq \emptyset$.

If $b_n - a_n \to 0$, then $0 \leq b - a \leq b_n - a_n \to 0$, so $b = a$ and the intersection is $\{a\}$.

The Nested Interval Property is the theoretical backbone of bisection-based algorithms. Every time you halve a search interval and keep the half containing your target, you are applying the NIP. Binary search, the bisection root-finding method from Epsilon-Delta & Continuity, and branch-and-bound optimization algorithms are all NIP in action. The visualization above lets you see this convergence directly — watch the interval width shrink exponentially while the endpoints close in on the target.

A set $S \subseteq \mathbb{R}$ is open if for every $x \in S$, there exists $r > 0$ such that the open ball $(x - r, x + r) \subseteq S$. In other words, every point of $S$ has a “buffer zone” of neighboring points that also belong to $S$.

A set $S \subseteq \mathbb{R}$ is closed if its complement $\mathbb{R} \setminus S$ is open. Equivalently, $S$ is closed if and only if it contains all its limit points: whenever $(x_n)$ is a sequence in $S$ with $x_n \to L$, then $L \in S$.

The sequential characterization is often more useful: a closed set is one that “keeps its limits.”

(a) Arbitrary unions of open sets are open.

(b) Finite intersections of open sets are open.

(c) Arbitrary intersections of closed sets are closed.

(d) Finite unions of closed sets are closed.

(a): If $x \in \bigcup_\alpha S_\alpha$, then $x \in S_\beta$ for some $\beta$. Since $S_\beta$ is open, there exists $r > 0$ with $(x - r, x + r) \subseteq S_\beta \subseteq \bigcup_\alpha S_\alpha$.

(b): If $x \in \bigcap_{i=1}^n S_i$, then for each $i$, there exists $r_i > 0$ with $(x - r_i, x + r_i) \subseteq S_i$. Take $r = \min(r_1, \ldots, r_n) > 0$ (this is where finiteness is essential — an infinite minimum of positive numbers could be zero). Then $(x - r, x + r) \subseteq \bigcap_{i=1}^n S_i$.

(c)–(d): Follow from (a)–(b) by De Morgan’s laws: $\mathbb{R} \setminus \bigcap_\alpha S_\alpha = \bigcup_\alpha (\mathbb{R} \setminus S_\alpha)$ and $\mathbb{R} \setminus \bigcup_{i=1}^n S_i = \bigcap_{i=1}^n (\mathbb{R} \setminus S_i)$.

For $S \subseteq \mathbb{R}$:

• The interior $\mathrm{int}(S)$ is the largest open set contained in $S$: the set of all $x \in S$ for which some $(x - r, x + r) \subseteq S$.
• The closure $\overline{S}$ is the smallest closed set containing $S$: equivalently, $S$ together with all its limit points.
• The boundary $\partial S = \overline{S} \setminus \mathrm{int}(S)$: the set of points where every neighborhood meets both $S$ and $\mathbb{R} \setminus S$.

For $S = [0, 1)$:

• $\mathrm{int}(S) = (0, 1)$ — the point $0$ has no neighborhood contained in $S$ (every $(- r, r)$ contains negative numbers not in $S$).
• $\overline{S} = [0, 1]$ — the point $1$ is a limit point of $S$ (the sequence $1 - 1/n \to 1$) but $1 \notin S$.
• $\partial S = \{0, 1\}$.

The set $S = [0, 1)$ is neither open (0 is a boundary point in $S$ with no interior buffer) nor closed (1 is a limit point not in $S$).

A set $K \subseteq \mathbb{R}$ is sequentially compact if every sequence $(x_n)$ in $K$ has a subsequence $(x_{n_k})$ that converges to a point $L \in K$.

The key requirement is that the limit $L$ belongs to $K$ — not just that a convergent subsequence exists, but that the subsequence converges to a point inside the set.

A subset $K \subseteq \mathbb{R}$ is sequentially compact if and only if $K$ is closed and bounded.

(⟸) Closed + bounded implies compact: If $K$ is bounded, then $K \subseteq [-M, M]$ for some $M$. By the Bolzano-Weierstrass Theorem, any sequence $(x_n)$ in $K$ has a convergent subsequence $x_{n_k} \to L$. If $K$ is closed, then $L \in K$ (closed sets contain their limit points). So $K$ is sequentially compact.

(⟹) Compact implies closed: Suppose $K$ is not closed. Then there exists a sequence $(x_n)$ in $K$ with $x_n \to L$ and $L \notin K$. Every subsequence of $(x_n)$ also converges to $L$ (a fact from Sequences, Limits & Convergence). Since $L \notin K$, no subsequence converges to a point in $K$ — contradicting sequential compactness.

(⟹) Compact implies bounded: Suppose $K$ is unbounded. Then for each $n$, there exists $x_n \in K$ with $|x_n| > n$. The sequence $(x_n)$ has $|x_n| \to \infty$, so no subsequence can converge (convergent sequences are bounded). This contradicts sequential compactness.

The characterization “closed + bounded ⟺ compact” is specific to $\mathbb{R}^n$ — this is the Heine-Borel theorem we prove in the next section. In general metric spaces, compactness is a strictly stronger property than “closed + bounded.” For example, in the space of continuous functions $C([0,1])$ with the supremum norm, the closed unit ball $\{f : \|f\|_\infty \leq 1\}$ is closed and bounded but not compact — you can find a sequence of functions in it with no convergent subsequence. This distinction matters when working with function spaces in ML, and we develop it in Metric Spaces & Topology, where we prove that the sequence $f_n(x) = \sin(n\pi x)$ has all pairwise sup-norm distances $\geq 1$, so no subsequence is Cauchy and no subsequence converges uniformly.

An open cover of $K \subseteq \mathbb{R}$ is a collection $\{U_\alpha\}_{\alpha \in A}$ of open sets such that $K \subseteq \bigcup_{\alpha \in A} U_\alpha$. That is, every point of $K$ belongs to at least one of the $U_\alpha$.

A subcover is a subcollection that still covers $K$. A finite subcover is a subcover with finitely many sets.

A set $K$ is compact if every open cover of $K$ has a finite subcover: for any collection of open sets $\{U_\alpha\}$ covering $K$, there exist finitely many $U_{\alpha_1}, \ldots, U_{\alpha_n}$ such that $K \subseteq U_{\alpha_1} \cup \cdots \cup U_{\alpha_n}$.

A subset $K \subseteq \mathbb{R}^n$ is compact (every open cover has a finite subcover) if and only if $K$ is closed and bounded.

In $\mathbb{R}$, this means the compact sets are precisely the closed, bounded intervals $[a, b]$ and their closed subsets.

We prove the theorem for $\mathbb{R}$; the $\mathbb{R}^n$ case follows by the same argument applied coordinate-wise.

(⟸) Closed and bounded implies compact: Suppose $K = [a, b]$ and let $\{U_\alpha\}$ be any open cover. Define

$S = \{x \in [a, b] : [a, x] \text{ can be covered by finitely many } U_\alpha\}.$

$S$ is nonempty: $a \in U_\beta$ for some $\beta$, and since $U_\beta$ is open, some interval $[a, a + r) \subseteq U_\beta$, so $a \in S$.

$S$ is bounded above by $b$. Let $c = \sup S$, which exists by the completeness of $\mathbb{R}$. We claim $c = b$.

Since $c \in [a, b]$ and $\{U_\alpha\}$ covers $[a, b]$, there exists $U_\gamma$ with $c \in U_\gamma$. Since $U_\gamma$ is open, there exists $\delta > 0$ with $(c - \delta, c + \delta) \subseteq U_\gamma$.

Since $c = \sup S$, there exists $x \in S$ with $x > c - \delta$. Then $[a, x]$ is covered by finitely many $U_\alpha$, and $[x, \min(c + \delta, b)] \subseteq U_\gamma$. So $[a, \min(c + \delta, b)]$ is covered by finitely many $U_\alpha$.

If $c < b$, then $\min(c + \delta, b) > c$, contradicting $c = \sup S$. Therefore $c = b$, and $[a, b]$ has a finite subcover.

(⟹) Compact implies bounded: Cover $K$ by $\{(-n, n) : n \in \mathbb{N}\}$. A finite subcover gives $K \subseteq (-N, N)$ for some $N$, so $K$ is bounded.

(⟹) Compact implies closed: Suppose $x \notin K$. For each $y \in K$, let $r_y = |x - y|/2 > 0$. The intervals $(y - r_y, y + r_y)$ cover $K$. Extract a finite subcover: $K \subseteq \bigcup_{i=1}^n (y_i - r_{y_i}, y_i + r_{y_i})$. Let $r = \min(r_{y_1}, \ldots, r_{y_n}) > 0$. Then $(x - r, x + r) \cap K = \emptyset$, so $x$ is an interior point of $\mathbb{R} \setminus K$. Since every point of $\mathbb{R} \setminus K$ is interior, $\mathbb{R} \setminus K$ is open, hence $K$ is closed.

Consider the open cover $\{(1/n, 1) : n \geq 2\}$ of the open interval $(0, 1)$. Each point $x \in (0, 1)$ lies in $(1/n, 1)$ for $n > 1/x$, so this is indeed an open cover.

But no finite subcollection works. If we select $(1/n_1, 1), \ldots, (1/n_k, 1)$, the union is $(1/N, 1)$ where $N = \max(n_1, \ldots, n_k)$, which misses points in $(0, 1/N]$. This proves $(0, 1)$ is not compact.

Contrast with $[0, 1]$: any open cover must include some $U_\alpha$ containing $0$ and some $U_\beta$ containing $1$, and the Heine-Borel proof guarantees a finite subcover exists.

If $f: K \to \mathbb{R}$ is continuous and $K$ is compact, then $f(K) = \{f(x) : x \in K\}$ is compact.

Let $(y_n)$ be a sequence in $f(K)$. Then $y_n = f(x_n)$ for some $x_n \in K$. By compactness of $K$, there exists a subsequence $x_{n_k} \to x^* \in K$. By continuity of $f$, $f(x_{n_k}) \to f(x^*) \in f(K)$.

So every sequence in $f(K)$ has a subsequence converging to a point in $f(K)$. Therefore $f(K)$ is compact.

If $f: K \to \mathbb{R}$ is continuous and $K$ is compact, then $f$ attains its maximum and minimum on $K$: there exist $x_{\max}, x_{\min} \in K$ with $f(x_{\min}) \leq f(x) \leq f(x_{\max})$ for all $x \in K$.

By Lemma 1, $f(K)$ is compact, hence closed and bounded by Heine-Borel. Since $f(K)$ is bounded, $M = \sup f(K)$ exists. Since $f(K)$ is closed and $M$ is a limit point of $f(K)$ (by the approximation property of the supremum: there exist $y_n \in f(K)$ with $y_n \to M$), we have $M \in f(K)$. So $M = f(x_{\max})$ for some $x_{\max} \in K$.

The argument for the minimum is identical with $\inf$ replacing $\sup$.

Compare this with the proof in Epsilon-Delta & Continuity (Theorem 4): the compactness proof is cleaner because it identifies the essential structural ingredient. The continuous image of a compact set is compact — that is the entire story.

If $f: K \to \mathbb{R}$ is continuous and $K$ is compact, then $f$ is uniformly continuous on $K$: for every $\varepsilon > 0$, there exists $\delta > 0$ such that $|x - y| < \delta \implies |f(x) - f(y)| < \varepsilon$ for all $x, y \in K$.

Suppose $f$ is not uniformly continuous. Then there exists $\varepsilon > 0$ such that for every $\delta = 1/n$, there exist $x_n, y_n \in K$ with $|x_n - y_n| < 1/n$ but $|f(x_n) - f(y_n)| \geq \varepsilon$.

By compactness of $K$, the sequence $(x_n)$ has a subsequence $x_{n_k} \to x^* \in K$. Since $|x_{n_k} - y_{n_k}| < 1/n_k \to 0$, we also have $y_{n_k} \to x^*$.

By continuity of $f$ at $x^*$: $f(x_{n_k}) \to f(x^*) \quad \text{and} \quad f(y_{n_k}) \to f(x^*),$ so $|f(x_{n_k}) - f(y_{n_k})| \to 0$. But $|f(x_{n_k}) - f(y_{n_k})| \geq \varepsilon > 0$ for all $k$ — contradiction.

The Heine-Cantor proof by contradiction is a paradigm for compactness arguments: assume the negation, extract a sequence, use compactness to get a convergent subsequence, and reach a contradiction via continuity. This pattern — sometimes called the “compactness argument” — appears throughout analysis and optimization theory. Whenever you see a proof that constructs a sequence and extracts a convergent subsequence, compactness is at work.

A function $f: \mathbb{R}^d \to \mathbb{R}$ is coercive if $\lim_{\|x\| \to \infty} f(x) = +\infty$. Equivalently, for every $c \in \mathbb{R}$, the sublevel set $\{x \in \mathbb{R}^d : f(x) \leq c\}$ is bounded.

If $f: \mathbb{R}^d \to \mathbb{R}$ is continuous and coercive, then $f$ attains its minimum: there exists $x^* \in \mathbb{R}^d$ with $f(x^*) = \inf_{x \in \mathbb{R}^d} f(x)$.

Let $m = \inf_{x \in \mathbb{R}^d} f(x)$. Choose a minimizing sequence $(x_n)$ with $f(x_n) \to m$.

Since $f(x_n) \to m$, we have $f(x_n) \leq m + 1$ for all sufficiently large $n$. The sublevel set $S = \{x : f(x) \leq m + 1\}$ is:

• Bounded, by coercivity of $f$.
• Closed, by continuity of $f$ (preimage of the closed set $(-\infty, m + 1]$).

So $S$ is compact by the Heine-Borel theorem, and the tail of $(x_n)$ lies in $S$. By compactness, extract a subsequence $x_{n_k} \to x^* \in S$. By continuity, $f(x^*) = \lim f(x_{n_k}) = m$.

Coercivity is why $L_2$ regularization guarantees a unique minimizer for convex losses. The regularized loss $\mathcal{L}(\theta) + \lambda\|\theta\|_2^2$ is coercive for any $\lambda > 0$: the quadratic penalty dominates as $\|\theta\| \to \infty$, regardless of what $\mathcal{L}$ does. The sublevel sets are compact (closed and bounded), so the Weierstrass theorem guarantees a minimizer exists. Without regularization, the loss might decrease asymptotically — approaching its infimum along a sequence $\theta_n$ with $\|\theta_n\| \to \infty$ — without ever being attained.