Saturday, September 09, 2006

Bolzano-Weierstrass Theorem

The Bolzano-Weierstrass Theorem is a very important theorem in the realm of analysis. It was first proved by Bernhard Bolzano but it became well known with the proof by Karl Weierstrass who did not know about Bolzano's proof. In light of this history, the proof gets its current name. I use it in my proof for the Cauchy Criterion which also an important theorem in analysis.

It says:

every bounded sequence has a convergent subsequence

To make heads or tails of this, it is necessary to offer some definitions of bounded sequence and convergent subsequence. Since this is one of the subtleties of analysis, I will attempt to provide a complete formal definition. Interspersed, I will provide some comments that will make the ideas clear even if you wish to skip some of the formalisms.

Let's start with sequence. This one is a tougher nut to crack, then it might seem. From one perspective, a "sequence" is just a set of numbers but from another perspective, this definition in itself is too limiting. For example, what about a sequence of points on a line?

To apply to all these domains, we will use an abstraction called a metric space and to define this, we must first define a metric.

Definition 1: metric

A metric is a binary function d(a,b) on a set X such that for any a,b,c ∈ X:

(a) d(a.b) is a real number.

(b) d(a,b) ≥ 0

(c) d(a,b) = 0 if and only if a = b

(d) d(a,b) = d(b,a)

(e) d(a,c) ≤ d(a,b) + d(b,c)

In other words, a metric is a distance function. For real numbers, the standard metric is an absolute subtraction. The distance between any two numbers x,y is abs(x - y).

Definition 2: Metric Space

A metric space is a pairing of a set X with a metric, that is, a distance function. Any element in X can be thought of as a point in the metric space.

From this perspective, all the number systems (integers, reals, rationals) are examples of metric spaces as are geometric coordinates (lines and planes).

Definition 3: Sequence

A sequence is a mapping from the set of natural numbers to the points of a given metric space.

In other words, there is a first element, a second element, a third element, etc.

For example:

the set of even numbers = {2, 4, 6, ...}

Definition 4: Bounded Sequence

A sequence an is bounded if there exists some number k such that abs(an) ≤ k for all elements in the sequence.

By this definition, a bounded sequence has both a least upper bound and a greatest lower bound.

OK, good. To continue on with formal definitions, we now need a definition of strictly increasing.

Definition 5: Strictly Increasing

A function f(x) is said to be strictly increasing if x is less than y implies f(x) is less than f(y).

I now use the definition of strictly increasing in the next definition.

Definition 6: Subsequence

If (an) is sequence, then a subsequence is (anr) where each nr is a strictly increasing sequence of natural numbers.

The main idea here is that if a sequence is a mapping of the set of natural numbers to points in a metric space. Then a subsequence is a mapping of a set of natural numbers to a subset of natural numbers to points in a metric space.

Here's an example. Let's say we have the sequence of natural numbers = (1,2,3,4,...)

In this case, we have a mapping from the set of natural numbers to the set of natural numbers. The first element is 1, the second element is 2, and so on. Remember, the set of natural numbers is a metric space, that is, they are a set combined with a distance function for any two elements from that set.

Now, let's say we have the sequence of odd numbers which is subsequence of the natural numbers so that we have (1,3,5,7,9,..)

This is a mapping from the natural numbers to the natural numbers to a metric space in the sense that the first element of the odd numbers, 1, maps to the first element of the sequence of integers which maps to 1. The second element of the odd numbers, 3, maps to the third element of the sequence of integers which maps to 3.

The main idea here is that a subsequence maintains the order of the sequence but deletes some of the elements. So, all subsequences are sequences in themselves but they also have a mapping to the elements of another sequence.

Definition 7: Convergent Sequence

A sequence (an) in the metric space (X,d(a,b)) is said to be convergent if there exists a point x ∈ X such that:

for every real number ε greater than 0, there exists a natural number N such that if n greater than N, d(an,x) is less than ε.

The notation for this is:

lim (sn) = x.

In other words, if we are talking about a sequence of real numbers where the distance function d(a,b) is just subtraction and the metric space is just the set of real numbers, then this says that for any convergent sequence, there is a limit for this sequence (which is a real number) such that we can pick a point in the sequence where all elements of the remaining elements of the sequence are arbitrarily close to the limit. In other words, the sequence is said to converge to this limit.

For the proof below, we also need:

Definition 8: Monotone Sequence

A sequence sn is monotonic if it meets one of the four following conditions:

(1) Monotonically Increasing: i greater than j → si greater than sj

(2) Monotonically Decreasing: i greater than j → si is less than sj

(3) Monotonically Nondecreasing: i greater than j → si ≥ sj

(4) Monotonically Nonincreasing: i greater than j → si ≤ sj

The main idea behind a monotone sequence is that it moves in a consistent direction. It is either gradually increasing, gradually decreasing, or just staying the same without ever regressing.

Now, with these definitions aside, we are ready to start on the proof of the Bolzano-Weierstrass Theorem. We will also need some lemmas to begin.

Lemma 1: All bounded monotone sequences converge.

Proof:

(1) Assume that S is a bounded nondecreasing sequence = s1, ..., sn. (We will be able to make an analogous argument for bounded nonincreasing sequences so we only need to prove this one case)

(2) Let b = sup S

NOTE: sup S means the supremum for the sequence S which is the least upper bound for the sequence S. We know that this exists since S is bounded.

For nonincreasing sequences, we would let b = inf(S) where inf(S) is the infimum for the sequence S which is the greatest lower bound for the sequence S.

(3) Let ε be any positive number.

(4) Then, there is some N such that sN is greater than b - ε

We know that this exists otherwise b would not be the least upper bound since b - ε is less than b. We can make an analogous argument using the greatest lower bound for a bounded nonincreasing sequence.

(5) Since S is nondecreasing, for all n ≥ N, sn is greater than b - ε. [See Definition of monotone sequence above]

(6) S is also bounded by b so we have:

b is greater than sn which is greater than b - ε

(7) But this implies that abs(sn - b) is less than ε since:

if we subtract b from all sides then we get:

0 is greater than sn - b which is greater than

Since ε is greater than 0, we have:

sn - b is between and .

(8) So, by the definition of a convergent sequence, we have:

lim(sn) = b.

QED

Lemma 2: Every sequence has a monotonic subsequence

Proof:

(1) Let us call a term si in a sequence S dominant if it is greater than all the terms that follow it.

(2) It is clear that each sequence either has a finite number of dominant terms or an infinite number of dominant terms.

(3) Let us start by handling the case where a sequence S has an infinite number of dominant terms.

(4) We can now form a subsequence that only includes these dominant terms. [See definition of subsequence above]

(5) Then for every Snk that makes up the subsequence, Snk is greater than Snk+1 which means that the subsequence is monotonic decreasing sequence. [See definition of monotone sequence above]

(6) Now, let's handle the case where there is a finite number of dominant terms.

(7) Let's label the first term after the last dominant term (since there are only a finite number of them), n1. If there aren't any dominant terms, then let's label the first term in the sequence n1.

(8) Now since n1 is not dominant, there must be another term in the sequence which is greater than n1. We can call this next term n2. But n2 is not dominant so there must be an n3 and so on.

(9) We now have constructed a nondecreasing monotone subsequence. [See definition of monotone sequence above]

QED

Theorem: Bolzano-Weierstrass Theorem

Every bounded sequence has a convergent subsequence

Proof:

(1) Let (sn) be a bounded sequence.

(2) By Lemma 2 above, we know that it has a monotonic subsequence.

(3) By Lemma 1 above, the monotonic subsequence converges.

QED

References

10 comments :

Anonymous said...

This post was helpful, quite helpful.
Thanks :-)

John Armstrong said...

Your lemma 2 only works for sequences where we have an order on the range, like sequences of real numbers. How can you make the theorem work in, say, the plane?

Larry Freeman said...

Hi John,

Thanks very much for your question.

I would be very interested in better understanding your comment in more detail.

I view a plane as a mapping of the complex numbers to an x and y axis such that each complex number is x + iy.

From this perspective, both x,y are sequences of real numbers.

Cheers,

-Larry

Anonymous said...

WOW. What an awesome post. It gives you the complete structure behind the theorem. Thanks a lot.

Anonymous said...

In the proof of lemma 2,

(8) Now since n1 is not dominant, there must be another term in the sequence which is greater than n1. We can call this next term n2. But n2 is not dominant so there must be an n3 and so on.

"greater than" might be replaced by "greater than or equal to"

Anonymous said...

The a_n's are members of a generic set in a metric space right? So what does abs(a_n) mean in that context?

Unknown said...

I found your post well-structured and lucid.
I just have a small doubt. In some texts, Bolzano Wierstrass theorem is stated as "Every infinite bounded subset of R (or Rn) has a limit point". I was just wondering if the two statements of the theorem are related in any way. Are they equivalent? Is one a stronger statement or generalization of the other? Or is this just a different theorem by the same duo? Thanks.

Larry Freeman said...

Hi Anonymous,

A metric is a mapping to a real number.

abs(a_n) therefore means an absolute value of the metric used.

-Larry

Larry Freeman said...

Hi Bharat Ram,

Thanks for your question.

The different wording comes from the ambiguities relating to the concept of a "limit."

I have found that limit theory is very interesting when it comes to analysis of derivatives. This is what I was originally taught when I took calculus in college.

Recent textbooks have used topology and metric spaces as the a foundation for calculus.

When researching the topic for my blog, I decided to base it on metric spaces.

I hope that this answers your question.

-Larry

Unknown said...

This proof of Bolzano Wierestrass is wholesome, fantastic and highly interesting.
It was done in a systematic but simple manner, in such a way that even if a novice in mathematics reads it, he/she 'll comprehend.
It was a good job. BRAVO!