## 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 $\inline (a_n)_{n\in \mathbb{N}}$ be a sequence. Define a "peak" of $\inline a_n$ as an element such that $\inline a_n \geq a_m$ for all $\inline m \geq n$. That is $\inline a_n$ is a peak if forever after that point going forward, there is no other element of the sequence that is greater than $\inline a_n$. 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 $\inline (a_n)_{n \in \mathbb{N}}$ has infinitely many peaks, then collect those peaks into a subsequence $\inline (a_{n_{k}})_{k \in \mathbb{N}}$. This is a monotone decreasing subsequence, as required.

If $\inline (a_n)_{n \in \mathbb{N}}$ has finitely many peaks, take n to be the position of the last peak. Then we know $\inline a_{n+1}$ is not a peak. So there exists an $\inline n_2 > n_1$ such that $\inline a_{n_2} > a_{n_1 + 1}$. Call this point $\inline a_{N_1}$. We also know that $\inline a_{n_2}$ is not a peak either. So there also exists an $\inline n_3 > n_2$ such that $\inline a_{n_3} > a_{n_2}$. Call this point $\inline a_{N_2}$.

Continuing, we can create a subsequence $\inline a_{N_1} < a_{N_2} < ... < a_{N_k}$ 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. $\inline \square$

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 $\inline (a_{n_k})_{k \in \mathbb{N}}$. Since $\inline a_n$ is bounded by assumption, then the subsequence $\inline a_{n_k}$ is also bounded. So by the monotone convergence theorem, since $\inline a_{n_k}$ is monotone and bounded, it converges. So every bounded sequence has a convergent subsequence, completing the proof. $\inline \square$

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

* * *