### Proving the Heine-Borel theorem

Originally published at 狗和留美者不得入内. You can comment here or there.

I finally proved this on my own for the first time, though I admit that I read it once over a month ago, superficially following it while afterwards sort of struggling to re-construct it. Partly through this, I realized that my point-set topology foundation was insufficient, after which I wrote [1] and [2].

**Definition 1** For a topological space on , a subset is compact iff every open cover of it has a finite subcover.

**Bolzano-Weierstrass Theorem** Every sequence in a closed, bounded subset of has a convergent subsequence.

*Proof*: I’ve proved this myself for , by bisecting intervals and using the nested interval theorem in some unreleased notes. The result is easily generalizable to .

On , which is a metric space for which the metric is given by

we shall use the topology generated by sets of the form , where is the Euclidean norm associated with the metric. We call these rational open balls, centered at with radius and denote via .

**Heine-Borel Theorem** Closed and bounded in is equivalent to compact.

*Proof*: Assume is compact, which means that every open cover of it has a finite subcover. Apply this to any arbitrary covering of by rational open balls, and since a finite subcover exists, the subcover is bounded. Suppose by contradiction that is not closed. Then there exists a sequence in converging to a point . At every point in the sequence, we can take an open ball containing it but not . At every point not covered after this, we cover it with an open ball that does not contain to obtain an open cover of . Because no element of the cover contains , by the fact that Hausdorff, it is apparent there is no element in the cover that contains infinitely many points in the sequence converging to . Thus any finite subset of the cover, contains only a finite number of elements in that sequence, which means there is no finite subcover. This means that a compact subset of must be closed.

Now assume is closed and bounded in . With for the rational point and radius a countable sequence, we have a sequence of all rational open balls, This sequence of sets obviously covers . Suppose by contradiction that there is no finite subcover here. Then for all , there exists such that By the Bolzano-Weierstrass theorem, has a convergent subsequence that converges to a value , since is closed. No can contain , because if did for some , then each element of the convergent subsequence past some point would be contained by the union of balls corresponding to it as given in , a contradiction. Because covers though, every has a smallest natural number such that . But this contradicts that is not contained by any of the s. Thus, closed and bounded implies that the covering by all rational open balls has a finite subcover. For any open cover, every element in the cover is equal to some union of rational open balls. Every open cover corresponds in this way to a covering by a collection of rational open balls , each of which is contained in some element of the original open cover . That covering by rational open balls we’ve already established has a subcover. Since every element in this subcover is contained by some element of , is also guaranteed to have an open cover.

As a side note, I am feeling somewhat enticed into mathematical logic and computability theory. At the same time, I fear that maybe I am wasting too much time on something as impractical as pure math that in addition to impracticality has already mostly reached its bottleneck. Maybe instead I should be learning or doing some more practical things. My original plan was to prove Alexander subbase theorem and Tychonoff’s theorem on my own, and of course, before I do that, I should prove Heine-Borel theorem on my own, which I just did. However, a short diversion into Cantorian set theory (see [3]) brought me to read casually about mathematical logic related matters. I finally learned the difference between propositional logic (no quantifiers), predicate calculus or first-order logic (quantifiers over sets), and higher-order logic (quantifers over sets and functions), which I don’t think I will ever forget. As for the word “predicate”, its etymology is prae = before, dicare = to dictate; this makes sense since the predicate of a sentence in essence gives a verdict of true or false for something. One can interpret “predicated upon”, which means “based upon”, as making a verdict based upon something.

I was reminded of the halting problem, the proof of which I’ve read before but could never remember. I also saw the names of Russell, Skolem, Lowenheim, Tarski, Godel, Turing, Church, and I thought how great it would be if I could actually understand some of their work. I was also reminded of the Chinese (and later naturalized American) logician Hao Wang, who was actually the advisor of Stephen Cook, the man celebrated for the Cook-Levin theorem. He studied at 西南联大 during World War II, like Steve Hsu’s father. Interestingly, Tarski had a Chinese student named Chen Chung Chang (张晨钟), who was born in 1927, who as a professor at UCLA wrote the standard textbook on model theory with Jerome H. Keisler, another student of Tarski. That the Polish Tarski later became a professor at Berkeley also reminded me of Thomas Scanlon, a 1970s born model theorist at the same institution. Another logician I stumbled upon was Paul Bernays.

这个 Bernays 是中国的数理逻辑的一位重要奠基人莫绍揆的导师，莫绍揆又是中国操作系统之父孙钟秀的在南京大学的老师。有意思的是我今年还是去年得知世界第一个称的上有操作系统的计算

**References**