Compactness (2) - The Heine-Borel Theorem

In my previous post, I introduced the concept of compactness and a few basic properties of compact spaces. Of particular importance was the result that the continuous image of a compact space is compact, as well as the fact that compact subsets of metric spaces must be closed and bounded.

In this post, I will prove a series of seemingly random conjectures about compactness. However, each of them will be required in order to prove the main result of this post: The Heine-Borel Theorem. This theorem completely characterizes compact sets in euclidean space, telling us that for any dimension $n$, a subset of $\R^n$ is compact if and only if it is closed and bounded. One direction is a corollary of the result I mentioned above, since $\R^n$ is a metric space. Proving the other direction, that a closed and bounded subset of $\R^n$ is necessarily compact, takes rather more machinery.

Something else to note is that the ideas behind some of the proofs here are not simple to come up with. I come up with most of the proofs on this blog myself. However, I needed to consult a reference for at least two of the proofs below as the methods of proof were not at all obvious to me. This is all to say, if the proofs below seem complicated to you then that is totally normal and you should not let that scare you off.

With all that exposition out of the way, here's the first result we will need. We will not use it directly in our proof of the Heine-Borel Theorem, but we'll need it for the proof that closed intervals are compact, which we will use to show that higher dimensional cubes are compact, which we will need in order to prove the Heine-Borel Theorem. Yes, we are dealing with a lot of layers here.

Lemma. If $X$ is a topological space which is not compact, then any finite collection of sets $\set{A_i}_{i=1}^n$ whose union is $X$ must contain at least one set which is not compact.

Proof. We give a proof by contraposition. Suppose there exists such a finite decomposition $\set{A_i}_{i=1}^n$ of $X$ such that $A_i$ is compact for every $i$. We need to show that $X$ is compact. To this end, choose any open cover $\set{U_j}_{j\in J}$ of $X$. Since each set $A_i$ in the decomposition is a subset of $X$, certainly $\set{U_j}_{j\in J}$ is an open cover of every $A_i$. Thus, for any $i\in \set{1,\ldots, n}$ there is a finite subcover $\set{U^i_{j_k}}_{k=1}^{m_i}$ of $A_i$. Note that these subcovers are potentially all different and depend on $i$, as does the number $m_i$ of sets that comprise each subcover. So for each $i\in \set{1,\ldots, n}$, we have that

$$A_i \subseteq \bigcup_{k=1}^{m_i} U^i_{j_k}.$$

It follows that

$$\begin{align}
X &= \bigcup_{i=1}^{n} A_i \\
&\subseteq \bigcup_{i=1}^{n} \bigcup_{k=1}^{m_i} U^i_{j_k}
\end{align}$$

which is a finite union of open sets. Thus,

$$\bset{U^i_{j_k} \mid i \in \set{1, \ldots, n}, k\in \set{1, \ldots, m_i}}$$

is a finite subcover of $X$, and thus $X$ is compact.

We will also need the following theorem in order to show that closed intervals are compact. Note that I use the notation $\len{I}$ to denote the length of an interval. That is, if $I=[a,b]$, then $\len{I} = b-a$.

Nested Interval Theorem. Let $\set{I_j}_{j=0}^\infty$ be a sequence of closed intervals in $\R$ for which

$$I_0 \supseteq I_1 \supseteq I_2 \cdots$$

and

$$\lim_{j\to\infty} \len{I_j} = 0.$$

That is, a nested sequence of intervals whose lengths converge to zero. Then there exists precisely one point $p \in \bigcap_{j=0}^\infty I_j$.

Proof. For each natural number $j$, denote $I_j = [a_j, b_j]$. Then $a_j \le a_{j+1}$ and $b_j \ge b_{j+1}$ for each $j$, since our intervals form a nested sequence. Furthermore, for any $j$, we have that $a_j\le b_k$ for every $k$ and thus the set $\set{a_j}_{j=0}^\infty$ is bounded above. Similarly, for any $j$, we have that $b_j\ge a_k$ for every $k$ and thus the set $\set{b_j}_{j=0}^\infty$ is bounded below. It follows from the Least Upper Bound Property of the real numbers that $\set{a_j}_{j=0}^\infty$ has a supremum and $\set{b_j}_{j=0}^\infty$ has an infimum. Let

$$\begin{align}
A &= \sup\set{a_j}_{j=0}^\infty \\
B &= \inf\set{b_j}_{j=0}^\infty.
\end{align}$$

Certainly $A \le B$ since $a_j \le b_j$ for all $j$. It follows that for any $j$, we have that $a_j \le A \le B \le b_j$, and so $[A, B]\subseteq [a_j, b_j]$. Thus

$$[A, B] \subseteq \bigcap_{j=0}^\infty I_j.$$

Since the lengths of our intervals converge to zero,

$$\begin{align}
\lim_{j\to\infty} \len{I_j} &= \lim_{j\to\infty} (b_j-a_j) \\
&= \lim_{j\to\infty} b_j - \lim_{j\to\infty} a_j \\
& = 0,
\end{align}$$

and so it follows that

$$\lim_{j\to\infty} a_j = \lim_{j\to\infty} b_j.$$

Since $\set{a_j}_{j=0}^\infty$ is monotonically increasing and $\set{b_j}_{j=0}^\infty$ is monotonically decreasing,

$$\begin{align}
\lim_{j\to\infty} a_j &= \sup\set{a_j}_{j=0}^\infty \\
\lim_{j\to\infty} b_j &= \inf\set{b_j}_{j=0}^\infty.
\end{align}$$

Thus, $A=B$. For any point $q\ne A$, it is easy to see that there exists an interval $I_j = [a_j, b_j]$ with $q\notin I_j$, so $q$ is not in the intersection. This completes the proof.

We are now in a position to prove that closed intervals in $\R$ are compact.

Theorem. Every closed interval $[a, b] \subseteq \R$ is compact in the standard topology.

Proof. It suffices to show that $I_0 = [0, 1]$ is compact, since the general result follows from the fact that every closed interval is a homeomorphic image of this one.

We give a proof by contradiction, supposing that $I_0$ is not compact. Then there must exist an open cover $\set{U_i}_{i\in I}$ of $I_0$ which possesses no finite subcover.

We begin by decomposing our interval $I_0$ into two closed intervals, $[0, \frac{1}{2}]$ and $[\frac{1}{2}, 1]$. Certainly the union of these two intervals is $I_0$, and so from the above lemma it follows that at least one of them is not compact — we'll denote that interval by $I_1$. Repeating the process, we can split $I_1$ into two closed intervals of equal length which union to $I_1$. At least one of these intervals is not compact — denote it by $I_2$. In this manner, we obtain a sequence $\set{I_j}_{j=0}^\infty$ of non-compact nested intervals whose lengths are given by

$$\len{I_j}=\frac{1}{2^j}.$$

These lengths certainly converge to zero, and so from the Nested Interval Theorem it follows that there exists precisely one point $p\in\bigcap_{j=0}^\infty I_j$. Certainly this implies that $p\in I_0$, and so $p\in U_i$ for some $i\in I$, since these sets cover $I_0$. Since $U_i$ is an open set, there must exist an open interval containing p which is itself contained in $U_i$. That is, there exists $\epsilon>0$ for which $(p-\epsilon, p+\epsilon)\subseteq U_i$. From the archimedean property of the real numbers, there exists a natural number $N\in\N$ with $\frac{1}{2^N} < \epsilon$. But this means that $p\in I_N \subseteq (p-\epsilon, p+\epsilon) \subseteq U_i$, implying that $U_i$ covers the interval $I_N$. But this is a contradiction, since $I_N$ is not compact.

We have shown that closed intervals are compact. This is a large step toward proving the Heine-Borel Theorem. Let's forge ahead.

Theorem. Any closed subset of a compact space is compact.

Proof. Let $X$ denote a compact topological space and suppose $A\subseteq X$ is closed. Choose any open cover $\set{U_i}_{i\in I}$ of $A$. By definition,

$$A \subseteq \bigcup_{i\in I} U_i.$$

Furthermore, $X-A$ is open since $A$ is closed. It follows then that

$$X \subseteq (X-A) \cup \bigcup_{i\in I} U_i.$$

That is, $(X-A) \cup \set{U_i}_{i\in I}$ is an open cover of $X$. Since $X$ is compact, there is a finite subcover $(X-A) \cup \set{U_{i_j}}_{j=1}^n$ of $X$. But then $\set{U_{i_j}}_{j=1}^n$ is a finite subcover of $A$, and so $A$ is compact.

There is one more major result we must prove. This is that the cartesian product of compact spaces is compact. For our purposes, we only need to establish that this holds for finite products. However, the result is actually true for arbitrary products and is called Tychonoff's theorem. Some would argue that this is the most important result in point-set topology. I personally prefer theorems with more hilarious names.

Tychonoff's Theorem (Finite Case). If $\set{X_i}_{i=1}^n$ is a finite collection of compact topological spaces then their product $\prod_{i=1}^n X_i$ is compact.

Proof. It suffices to show that the product of two compact is compact, since the result then follows from a simple inductive argument (the details of which I will not bother with).

Suppose then that $X_1$ and $X_2$ are compact spaces, and let $\set{U_i}_{i\in I}$ be any open cover of $X_1\times X_2$. Choose any point $a\in X_1$ and define $f:X_2\to X_1\times X_2$ by $f(b)=(a,b)$. We first aim to show that $f$ is continuous. For any open set $V\in X_1\times X_2$, we know that $V$ is a union of basis elements in the product topology. That is, $V=\bigcup_{j\in J}A_j\times B_j$ where each $A_j$ is open in $X_1$ and each $B_j$ is open in $X_2$. Thus, from our definition of $f$,

$$\begin{align}
f^{-1}[V] &= f^{-1}\Big[\bigcup_{j\in J}A_j\times B_j\Big] \\
&= \bigcup_{j\in J} f^{-1}[A_j\times B_j] \\
&= \bigcup_{j\in J} B_j
\end{align}$$

is open in $X_2$ and thus $f$ is continuous. It follows that $f[X_2] = \set{a}\times X_2$ is compact, as it is the continuous image of the compact set $X_2$. Since $\set{U_I}_{i\in I}$ covers $X_1\times X_2$, it certainly covers $\set{a}\times X_2$ and so it has a finite subcover $\set{U_{i_j}}_{j=1}^n$ for $\set{a}\times X_2$. The dependency of this subcover on our choice of point $a$ is not explicitly shown.

Define $V_a = \bset{x\in X_1 \mid \set{x}\times X_2 \subseteq \bigcup_{j=1}^n U_{i_j}}$. Then certainly $a\in V_a$. Additionally, $V_a$ is open in $X_1$ and $V_a\times X_2$ is covered by finitely many of the open sets in our original open cover $\set{U_i}_{i\in I}$.

Since $V_a$ is open for any $a\in X_1$, it follows that $\set{V_a\mid a\in X_1}$ is an open cover for $X_1$. Since $X_1$ is compact, this cover has a finite subcover and thus there exists finitely many points $\set{a_k}_{k=1}^m$ in $X_1$ for which $X_1=\bigcup_{k=1}^m V_{a_k}$. But then $X_1\times X_2= \bigcup_{k=1}^m (V_{a_k}\times X_2)$ and so it is a finite union of compact sets and thus compact.

We have nearly everything we need. The following corollary gives us the final piece of machinery that we require in order to prove the Heine-Borel Theorem:

Corollary. If $\set{I_j}_{j=1}^n$ is a finite collection of closed intervals, the closed hyperrectangle $C=\prod_{j=1}^n I_j$ is a compact set.

Proof. Since each closed interval is compact, $C$ is the finite product of compact sets and thus compact.

I'm running out of brainpower, so here's the main result. Now that we have everything we need, it's actually quite easy to prove!

Heine-Borel Theorem. Let $\R^n$ denote $n$-dimensional euclidean space with the standard topology. Then a subset $A\subseteq R^n$ is compact if and only if it is closed and bounded.

Proof. We prove the easy direction first. Suppose $A$ is compact. Then from the main result of my last post, since $\R^n$ is a metric space, $A$ is closed and bounded.

Suppose next that $A$ is closed and bounded. Then since it is bounded, there exists an open ball $B$ containing $A$. Let $r$ denote the radius of the ball $B$. Then $A$ is also contained in a closed hypercube $C$ with side lengths $2r$ (I will not explictly prove this but it is visually obvious and easy enough to show for yourself). Since $C$ is a closed hypercube, it is compact. Thus $A$ is a closed subset of a compact space and thus $A$ is compact, completing the proof.

This may all seem ridiculous at first glance. After all, if compactness is equivalent to being closed and bounded, then why do we need it at all? The answer is that this is only true for euclidean spaces. Even for arbitrary metric spaces, the characterization of compact sets is a bit more complicated. For general topological spaces, the definition we have given for compactness in terms of open covers having finite subcovers is as simple as we can get. However, the Heine-Borel Theorem gives us an important result, even for general spaces:

Extreme Value Theorem. Let $X$ be a compact topological space. Then any continuous function $f:X\to\R$ attains maximum and minimum values.

Proof. Since $f[X]$ is the image of a compact set, it is compact. Since $f[X]$ is a compact subset of $\R$, the Heine-Borel Theorem tells us that it is closed and bounded. Since it is bounded, it possesses an infimum and supremum. Since it is closed, it contains them (they are limit points of $f[X]$ and a closed set contains all of its limit points). Thus, $f$ attains its maximum and minimum values.

This means that real-valued functions defined on compact sets cannot blow up to infinity or exhibit strange asymptotic behavior. This result is used all the time in calculus, analysis and differential geometry, as we shall soon see!