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”

James Leng says:

December 14, 2020 at 8:09 am

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

LikeLike

1. Aidan Backus says:
  
  December 14, 2020 at 3:58 pm
  
  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.
  
  LikeLike

Internalizing tricks: the Heine-Borel theorem

Published by Aidan Backus

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

Leave a Reply Cancel reply

Share this:

Like this:

Related

Published by Aidan Backus

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

Leave a Reply Cancel reply