May 12th, 2021

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 是中国的数理逻辑的一位重要奠基人莫绍揆的导师,莫绍揆又是中国操作系统之父孙钟秀的在南京大学的老师。有意思的是我今年还是去年得知世界第一个称的上有操作系统的计算机源于英国,而非美国。孙钟秀却60年代到英国的一家公司进行了交流,大约文革开始的时候回国,然后几年的时间中国也搞出了操作系统了。