Internalizing tricks: the Heine-Borel theorem

I think that in analysis, the most important results are the tricks, not the theorems. I figure most analysts could prove any of the theorems in Rudin or Pugh at will, not because they have the results memorized, but because they know the tricks.

So it’s really important to internalize tricks! Here’s an example of how we could take apart a proof of the Heine-Borel theorem that every closed bounded set is compact, and internalize some of the tricks in it.

The proof we want to study is as follows.

Step 1. We first prove that [0, 1] is compact. Let (x_n) be a sequence in [0, 1] that we want to show has a convergent subsequence. Let x_{n_1} = x_1 and let I_1 = [0, 1].

Step 2. Suppose by induction that we are given I_1, \dots, I_J such that I_j is a subinterval of I_{j-1} of half length and there is a subsequence of (x_n) in I_j, and x_{n_j} \in I_j. By the pigeonhole principle, since there are infinitely many points of (x_n) in I_j, if we divide I_j into left and right closed subintervals of equal length, one of those two subintervals has infinitely many points of (x_n) as well. So let that subinterval be I_{J+1} and let (x_{n_{J+1}}) be the first point of (x_n) after x_{n_J} in I_{J+1}.

Step 3. After the induction completes we have a subsequence (x_{n_j}) of (x_n). By construction, x_{n_j} \in I_j and I_{j+1} is half of I_j, so |x_{n_j} - x_{n_{j+1}}| < 2^j. That implies that (x_{n_j}) is a Cauchy sequence, so it converges in \mathbf R, say x_{n_j} \to x.

Step 4. Since x is a limit of a sequence in [0, 1], and [0, 1] is closed, x \in [0, 1]. Therefore (x_n) has a convergent subsequence. So [0, 1] is compact.

Step 5. Now let K = [0, 1]^n be a box. We claim that K is compact. To see this, let $(x_n)$ be a sequence in K. If n = 1, then $(x_n)$ has a convergent subsequence.

Step 6. Suppose by induction that [0, 1]^{n-1} is compact. Then we can write x_n = (y_n, z_n) where y_n \in [0, 1]^{n-1}, z_n \in [0, 1]. So there is a convergent subsequence (y_{n_k}). Now (z_{n_k}) has a convergent subsequence (z_{n_{k_j}}), and then (x_{n_{k_j}}) is a convergent subsequence. So K is compact.

Step 7. Now let K be closed and bounded. So there is a box L = [-R, R]^n such that K \subseteq L. Without loss of generality, assume that R = 1.

Step 8. Since K is a closed subset of the compact set L, K is compact.

Let’s look at the tricks used at each stage:

Step 1. We want to show that an arbitrary closed and bounded set is compact. This sounds quite hard, as such sets can be nasty; however, it is often the case that if you can prove a special case of the theorem, the general theorem follows. Since [0, 1] is the prototypical example of a compact set, and is much nicer than e.g. Cantor dust in 26 dimensions, we first try to prove the Heine-Borel theorem on [0, 1].

Step 2. Here we use the informal principle that compactness is equivalent to path-finding in an infinite binary tree. That is, compactness requires us to make infinitely many choices, which is exactly the same thing as finding a path through an infinitely large tree, where we will have to choose whether to go left or right infinitely many times. Ideally every time we choose whether we go left or right, we will cut down on the complexity of the problem by half. Here the “complexity” is the size of the interval we’re looking at. This notion of “compactness” is ubiquitous in analysis, combinatorics, and logic. It is the deepest part of the proof of the Heine-Borel theorem, and is known as Koenig’s lemma.

Step 2 has another key idea to it. We need to make infinitely many choices, so we make infinitely many choices using induction. In general when traversing a graph, inducting on the length of the path so far will come in handy. If you don’t know which way to go, the pigeonhole principle and other nonconstructive tricks will also be highly useful here.

Step 3. Compactness gave us a subsequence, but we don’t know what the limit is. But to prove that a sequence converges without referring to an explicit limit, instead show that it is Cauchy. Actually, here we are forced to do this, because the argument of Step 2 could’ve been carried out over the rational numbers, yet the conclusion of the Heine-Borel theorem is false there. So this step could also be interpreted as make sure to use every hypothesis; here the hypothesis that we are working over the reals is key.

Step 4. Make sure to use every hypothesis; up to this point we’ve only used that [0, 1] is bounded, not closed.

Step 5. Here we again reason that if you can prove a special case of the theorem, the general theorem follows.

Step 6. Here n is an arbitrary natural number, so we prove a theorem about every natural number using induction. This is especially nice because the idea behind this proof was to build up the class of compact set iteratively, initializing with the unit interval; at every stage of this induction we also get a unit box.

This trick can be viewed as a special case of if you can prove a special case of the theorem, the general theorem follows: indeed, proving a theorem for every natural number would require infinitely many cases to be considered, but here there are just two, the base case and the inductive case. The inductive case was really easy, so the thing we are really interested in is the base case.

Step 7. Here we abstract away unnecessary parameters using symmetry. The parameter R is totally useless because topological notions don’t care about scaling. However, we do have a box, and it would be nice if it was a unit box because we just showed that unit boxes are compact. So we might as well forget about R and just assume it’s 1.

Step 8. Once again we make sure to use every hypothesis; the boundedness got us inside a box, so the closedness must be used to finish the proof.


2 thoughts on “Internalizing tricks: the Heine-Borel theorem

  1. Fascinating observation about compactness being about pathfinding on a tree. I suppose the Cantor set {0, 1}^N really is the prototypical compact set.


    1. I think this perspective is most popular in logic, because the Cantor set is the set of truth assignments. There’s a decent body of literature (that Ted Slaman and Java both frequently interact with, which is why I know about it) that use point-set topology, probability theory, and Fourier analysis to prove theorems in logic; when I took recursion theory that’s how Slaman proved the Godel completeness theorem. But this perspective is useful in soft analysis too; for example, I recently learned that because the Cantor set is compact, for every \sigma-algebra such that every infinite set of measurable sets has two measurable sets with nontrivial intersection, this is already true for some sufficiently large finite set of measurable sets.

      Now I wonder if for every compact space X (not metrizable) you can find a “big Cantor set” {0, 1}^\kappa, where \kappa is some uncountable set, that surjects onto X. It seems like Cantor sets are so fundamental to compactness that that has to be true.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s