A Simpler Proof of the Bolzano-Weierstrass Theorem

A while back I posted a long proof of the Bolzano-Weierstrass theorem -- also known as the "sequential compactness theorem" -- which basically says every sequence that's bounded has a subsequence within it that converges. Here's a much shorter and simpler version of it.

First we'll prove a lemma that shows for any sequence we can always find a monotone subsequence -- that is, a subsequence that's always increasing or decreasing.

Lemma. Every sequence has a monotone subsequence.

Proof. Let spacer be a sequence. Define a "peak" of spacer as an element such that spacer for all spacer . That is spacer is a peak if forever after that point going forward, there is no other element of the sequence that is greater than spacer . Intuitively, think of shining a flashlight from the right onto the "mountain range" of a sequence's plotted elements. If the light hits an element, that element is a peak.

If spacer has infinitely many peaks, then collect those peaks into a subsequence spacer . This is a monotone decreasing subsequence, as required.

If spacer has finitely many peaks, take n to be the position of the last peak. Then we know spacer is not a peak. So there exists an n_1" target="_blank">spacer n_1" title="\inline n_2 > n_1" /> such that a_{n_1 @plus; 1}" target="_blank">spacer a_{n_1 + 1}" title="\inline a_{n_2} > a_{n_1 + 1}" />. Call this point spacer . We also know that spacer is not a peak either. So there also exists an n_2" target="_blank">spacer n_2" title="\inline n_3 > n_2" /> such that a_{n_2}" target="_blank">spacer a_{n_2}" title="\inline a_{n_3} > a_{n_2}" />. Call this point spacer .

Continuing, we can create a subsequence spacer that is monotone increasing. In either case -- if our sequence has infinite or finitely many peaks -- we can always find a monotone subsequence, as required. spacer

Now that we've proved the above lemma, the proof of the Bolzano-Weierstrass theorem follows easily.

Theorem (Bolzano-Weierstrass).Every bounded sequence has a convergent subsequence.

Proof. By the previous lemma, every sequence has a monotone subsequence. Call this spacer . Since spacer is bounded by assumption, then the subsequence spacer is also bounded. So by the monotone convergence theorem, since spacer is monotone and bounded, it converges. So every bounded sequence has a convergent subsequence, completing the proof. spacer

Posted by Andrew on Tuesday July 20, 2010 | Feedback?



* * *




Related searches:
sequence monotone theorem bounded bolzano
gipoco.com is neither affiliated with the authors of this page nor responsible for its contents. This is a safe-cache copy of the original web site.