Friday, September 15, 2006

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 x0 is a set of all points in the open interval (x0 - ε, x0 + ε).

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 x0 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 x0 not in K]

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

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

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

(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) Bxk [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 Px:

Let P0 = ∩ (k=1,n) Pxk

(12) P0 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 Px does not intersect with the ball Bx, it follows that P0 does not intersect with K [since ∪Bx is a covering of K]

(14) Since x0 ∈ P0, it follows that there exists a positive real ε such that (x0 - ε, x0 + ε) is a subset of P0 [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 a1 and its right endpoint b1. So that we have [a1, b1] with an infinite number of points.

(7) Let m1 = (a1 + b1)/2.

(8) We can now divide up [a1,b1] into [a1,m1] and [m1,b1]

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

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

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

(12) Putting this together gives us:

a ≤ a1 ≤ a2 ≤ ... ai ≤ bi ≤ ... b2 ≤ b1 ≤ b

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

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

(15) Let ε be any positive real number.

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

(17) In fact, b1 - a1 = [1/(21)][b - a], b2 - a2 = [1/(22)][b - a] and so on so that bi - ai = [1/(2i)][b - a]

(18) Since i can be arbitrarily any number, it follows that there exists a natural number i such that 1/(2i) ≤ 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 [ai,bi] contains an infinite number of points and [ai,bi] is a subset of the neighborhood [c - ε, c + ε] since:

1/(2i) ≤ 1/n is less than ε/[b-a] → 1/(2i)[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,∞) In where for each Iαβ there exists an n such that Iαβ = In

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

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

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, ∞) Ok

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

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

xn ∉ ∪ (k=1,n) Ok

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

(a) Let us start with O1. We know that there is at least one point x0 ∉ O1

(b) Now, from step #4, we know that there exists k1 such that xn ∈ Ok1. Clearly, there must be a distinct x1 that is not in the union of Ok and O1.

(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 xn elements that make up X have an index based on the ordering in step #4. That is, x1 is not in O1, x2 is not in ∪ {O1, O2}, x3 is not in ∪ {O1, O2, O3 }, etc.

(8) Since K is bounded and X is a subset of K (that is, each xn ∈ X → xn ∈ 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 ON such that c ∈ ON.

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

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

(15) But this contradicts step #6 since:

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

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

(c) But this is a contradiction since by definition in step #6, ON cannot contain any xn 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