Heine-Borel Theorem

In today's blog, I present a proof of the Heine-Borel Theorem. This very important theorem is one of the major foundations of topology and calculus. I use this theorem in the proof of the Heine-Cantor Theorem.

Definition 1: open ball B

An open ball of radius ε centered at x₀ is a set of all points in the open interval (x₀ - ε, x₀ + ε).

NOTE: An open interval is an interval that does not include its own endpoints as part of the set.

Definition 2: Upper Bound

A point b is called the upper bound of a set of real numbers A if and only if x ≤ b for all x ∈ A.

Definition 3: Lower Bound

A point c is called the lower bound of a set of real numbers A if and only if c ≤ x for all x ∈ A.

Definition 4: Bounded

A set A is said to be bounded if and only if A has both an upper and lower bound.

Lemma 1: If K is a subset of the real numbers R and K is compact, then K is closed and bounded.

Proof:

(1) Assume that K is a subset of the real numbers and that K is compact. [See Definition 4, here for definition of compact]

(2) Since K is a subset of the real numbers R, then it has the open covering:

K is a subset of ∪ (k=1, ∞) (-k, k) [See Definition 1, here for definition of open covering]

(3) By the definition of compact, each open covering has a finite subcovering so that:

K is a subset of ∪ (k=1, n) (-k, k) [See Definition 3, here for definition of finite subcovering]

(4) But ∪ (k=1,n)(-k,k) is a subset of (-n,n) so k is bounded. [See Definition 4 for definition of bounded]

(5) Assume that K is not closed [See Definition 3, here for definition of closed]

(6) Then, there exists a boundary point x₀ for K which is not in K. [See Definition 1, here for definition of a boundary point, see Lemma 1, here for proof of the existence of x₀ not in K]

(7) For each point x ∈ K, there exists an open ball B_x centered at x and an open ball P_x that is centered at x₀ that do not intersect. [See Definition 1 above for definition of an open ball]

(8) Since there is an open ball B_x for all x ∈ K, ∪ (x ∈ K) B_x is a covering since:

K is a subset of ∪ (x ∈ K) B_x

(9) We have an open covering since the union of open sets is itself open. [See Lemma 3, here]

(10) By the definition of compactness, there must exist a finite subcover such that:

K is a subset of ∪ (k=1, n) B_xk [See Definition 4, here for definition of compact]

(11) We can also define an intersection based on the the n in step #10 and the set of open balls P_x:

Let P₀ = ∩ (k=1,n) P_xk

(12) P₀ is an open set since it is the intersection of a finite set of open sets. [See Lemma 4, here]

(13) But since each ball P_x does not intersect with the ball B_x, it follows that P₀ does not intersect with K [since ∪B_x is a covering of K]

(14) Since x₀ ∈ P₀, it follows that there exists a positive real ε such that (x₀ - ε, x₀ + ε) is a subset of P₀ [This follows from the definition of an open set, see Definition 1, here]

(15) But this is a contradiction since step #14 implies that there exists an ε such that (x0 - ε, x0 + ε) does not include a point from K but from the definition of a boundary point (see Definition 1, here), all such intervals include at least one point of K.

(16) Therefore we must reject our assumption in step #5 and conclude that K is closed.

QED

Definition 5: Neighborhood

Let x be an element of X. A subset N of X is called a neighborhood of x if there is a real number ε greater than 0 such that (x - ε, x + ε) is a subset of N.

Definition 6: Accumulation Point

A point x ∈ X is called an accumulation point of a set S if each neighborhood of x contains infinitely many distinct points of S.

Definition 7: Supremum

The supremum of a bounded set S of numbers is the least upper bound. [See Definition 2 above for definition of upper bound]

Lemma 2: Heine-Borel Lemma

An infinite bounded set possesses at least one accumulation point.

Proof:

(1) Let X be an infinite but bounded set. That is, X contains an infinite number of points. [See Definition 4 above for definition of bounded]

(2) Let a,b be the bounds of X so that X is a subset of [a,b] and a is less than b.

(3) Let m = (a + b)/2

(4) We now can divide up [a,b] into [a,m] and [m,b]

(5) Since [a,b] contains an infinite number of points, either [a,m] or [m,b] must contain an infinite number of points.

(6) Let us select select one of these closed intervals and label its left endpoint a₁ and its right endpoint b₁. So that we have [a₁, b₁] with an infinite number of points.

(7) Let m₁ = (a₁ + b₁)/2.

(8) We can now divide up [a₁,b₁] into [a₁,m₁] and [m₁,b₁]

(9) We can follow the same process as step #6 and define an interval [a₂,b₂] that contains an infinite number of points.

(10) We can repeat this same process to get an a set of intervals [a_i,b_i] where i can be any arbitrary natural number and [a_i,b_i] contains an infinite number of points.

(11) It should also be clear that for each i, a_i ≤ a_i+1 and b_i+1 ≤ b_i. It should also be clear that each a_i ≤ b_i

(12) Putting this together gives us:

a ≤ a₁ ≤ a₂ ≤ ... a_i ≤ b_i ≤ ... b₂ ≤ b₁ ≤ b

(13) So that we have monotonic nondecreasing sequence a_i and a monotonic nonincreasing sequence b_i. [See Definition 8, here for definition of a monotonic sequences]

(14) Let a point c be the supremum for a_i [See definition 7 above for definition of supremum]

(15) Let ε be any positive real number.

(16) It is clear that for each i, b_i+1 - a_i+1 = (1/2)[b_i - a_i]

(17) In fact, b₁ - a₁ = [1/(2¹)][b - a], b₂ - a₂ = [1/(2²)][b - a] and so on so that b_i - a_i = [1/(2ⁱ)][b - a]

(18) Since i can be arbitrarily any number, it follows that there exists a natural number i such that 1/(2ⁱ) ≤ 1/n is less than ε/[b-a] [See Theorem 2, here]

(19) It therefore follows that for there exists a natural number i such that [a_i,b_i] contains an infinite number of points and [a_i,b_i] is a subset of the neighborhood [c - ε, c + ε] since:

1/(2ⁱ) ≤ 1/n is less than ε/[b-a] → 1/(2ⁱ)[b-a] is less than ε

(20) This means that c is an accumulation point. [See definition 6 above for definition of accumulation point]

QED

Lemma 3: The number of open balls with rational radii centered at rationals is countable.

Proof:

(1) The total number of rationals is countable. [See Theorem 3, here]

(2) The set of rational numbers that have open balls centered on them is a subset of all the rationals, so it is also countable.

(3) Since each open ball has rational radii, there is again a countable number of possible radii for each location. [by step #1 again]

(4) This means that the total number open balls with rational radii in on a rational = Q x Q. Since Q is countable, it follows that QxQ is also countable. [See Corollary 2.1, here]

QED

Postulate 1: Axiom of Choice

For any given collection Ω of nonempty subsets of a set X, there exists a function f : Ω → X such that for each S ∈ Ω, we have f(S) ∈ S.

In other words, it is possible to select an item from a list of items. This is one of those postulates that has raised lots of controversy because it is intuitively obvious but surprisingly involves a large number of subtleties. See here for an introduction to the topic.

Lemma 4: Lindelof Principle

Any infinite open cover has a countable subcover

Proof:

(1) Let { O_α } be an open covering for a set K such that each O_α is an open set and K is a subset of ∪ (α) O_α [See Definition 1, here for definition of open covering]

(2) For any point x ∈ O_α, there exists an open interval I_αβ such that it is centered at a rational point and it has a rational radius that lies wholly within O_α [We can do this since there is a rational number between any two real numbers, see Corollary 2.1, here, see Definition 1, here for definition of open set.]

(3) We thus have defined another open covering:

K is a subset of ∪ (α,β) I_αβ

(4) Now, from Lemma 3 above, we know that the number of open balls with rational radii centered at rationals is countable so that we can order the intervals I_αβ to get:

K is a subset of ∪ (n=1,∞) I_n where for each I_αβ there exists an n such that I_αβ = I_n

(5) Now, we can use the Axiom of Choice (see Postulate 1 above), for each I_n, to select an O_α that is a subset of I_n which we can label O_n. In this way, we can obtain the following countable subcover:

K is a subset of ∪(k=1,∞) O_k

QED

Heine-Borel Theorem: The compact sets of the real numbers R are exactly the sets that are both closed and bounded.

Proof:

(1) Using Lemma 1 above, we know that a compact set is closed and bounded. So to establish this theorem, we need to show that a closed and bound subset of the real numbers R is compact.

[See Definition 4, here, for definition of compact; see Definition 4 above for definition of bounded; see Definition 3, here, for closed set.]

(2) Let K be a closed and bounded subset of the real numbers R.

(3) Let { O_α } be an open covering for a set K such that each O_α is an open set and K is a subset of ∪ (α) O_α

(4) Using the Lindelof principle (see Lemma 4 above), we know that we can order { O_α } into an infinitely countable set such that:

K is a subset of ∪ (k=1, ∞) O_k

(5) Assume that no finite subcover for ∪ (k=1, ∞) O_k exists.

(6) Then, so long as we list a finite number of open sets, there must exist at least one point x_n which is an element of K but not an element of this union.

x_n ∉ ∪ (k=1,n) O_k

(7) From this it is possible to construct a set X which consists of an infinite number of distinct points x_n

(a) Let us start with O₁. We know that there is at least one point x₀ ∉ O₁

(b) Now, from step #4, we know that there exists k₁ such that x_n ∈ O_k1. Clearly, there must be a distinct x₁ that is not in the union of O_k and O₁.

(c) We can repeat this process to get as many distinct points as we wish. This means that if X is the set of all these points, X is an infinite set.

(d) Further, we know that each of these x_n elements that make up X have an index based on the ordering in step #4. That is, x₁ is not in O₁, x₂ is not in ∪ {O₁, O₂}, x₃ is not in ∪ {O₁, O₂, O₃ }, etc.

(8) Since K is bounded and X is a subset of K (that is, each x_n ∈ X → x_n ∈ K), it follows that X is also bounded.

(a) Since K is bounded, there exists an upper bound b and a lower bound c such that for all x ∈ K, c ≤ x ≤ b.

(b) Clearly, all x ∈ X are also in K, so b and c are also the upper and lower bound for X.

(9) From the Heine-Borel Lemma above [See Lemma 2 above], we know that there must exist at least one accumulation point c ∈ X.

(10) By the definition of accumulation points (see definition 6 above), every open neighborhood of c contains infinitely many points of X.

(11) Since X is a subset of K, c ∈ K.

(12) So, using step #4, there must be some O_N such that c ∈ O_N.

(13) Since O_N is an open set, then there exists a positive real ε such that:
(c - ε, c + ε) is a subset of O_N.

(14) Since c is an accumulation point, (c - ε, c + ε) contains an infinite number of points in X which means that O_N contains an infinite set of x_n points.

(15) But this contradicts step #6 since:

(a) If O_N contains an infinite number of elements of the form x_n, then it must contain more than N of these elements.

(b) Since each x_n is indexed, this means that at least one element in O_N must be indexed greater than N.

(c) But this is a contradiction since by definition in step #6, O_N cannot contain any x_n with an index such that n is greater than N.

(16) Thus, we reject our assumption in step #5 and conclude that K is compact, that is, for every open covering of K, there is a finite subcovering.

QED

References

• "The Heine-Borel Theorem", Mathematical Physics and Mathematics
• Bert Mendelson, Introduction to Topology, Dover Edition, 1990
• Charles R. MacCluer, Honors Calculus, Princeton University Press, 2006