Bolzano-Weierstrass Theorem

Statement

Every bounded sequence of reals contains a convergent subsequence.

Proof

Lemma 1: A bounded increasing sequence of reals converges to its least upper bound.

Proof: Suppose $(p_n)$ is a bounded increasing sequence of reals, so $p_1\leq p_2\leq p_3\leq\cdots$ . Let $p=\sup(\{p_1,p_2,p_3,\ldots\})$ . We want to show that $(p_n)\rightarrow p$ . Assume $\epsilon>0$ . By the definition of convergence, we need to produce some $n\in\mathbb{N}$ such that for all $m\geq n$ , $|p_m-p|<\epsilon$ . Since $p$ is the least upper bound of the sequence, there exists an $n\in\mathbb{N}$ such that $p_n>p-\epsilon$ , and since $(p_n)$ is increasing, we know that for all $m\geq n$ , $p_m\geq p_n>p-\epsilon$ . Therefore for all $m\geq n$ , $|p_m-p|<\epsilon$ . This shows that $(p_n)$ converges to $p$ . This completes the proof of Lemma 1.

We can prove analogously that a bounded decreasing sequence of reals converges to its greatest lower bound.

Lemma 2: Every sequence of reals has a monotone subsequence.

Proof: Given a sequence $(p_n)$ of reals, we consider two cases:

Case 1: Every infinite subsequence of $(p_n)$ contains a term that is strictly smaller than infinitely many later terms in the subsequence.

In this case, we build a strictly increasing subsequence $(i_n)$ .

Note that we can apply the assumption of Case 1 to $(p_n)$ itself. Thus there exists some $p_a$ such that there exist infinitely many $b>a$ such that $p_b>p_a$ . Let $i_1=p_a$ , and consider the subsequence $(q_n)$ where $q_1=p_a$ , and $q_k$ is the $k-1$ th term in $(p_n)$ after $p_a$ that is greater than $p_a$ . This exists by the assumption.

Now we can apply the assumption of Case 1 to $(q_n)$ . Thus there exists some $q_c$ such that there exist infinitely many $d>c$ such that $q_d>q_c$ . Since $(q_n)$ is a subsequence of $(p_n)$ , there exists an $e\in\mathbb{N}$ such that $p_e=q_c$ . We then let $i_2=p_e$ , and let $(r_n)$ be a subsequence of $(q_n)$ such that $r_1=q_c$ , and $r_k$ is the $k-1$ th term in $(q_n)$ after $q_c$ that is gerater tha $q_c$ . Note that $(r_n)$ is a subsequence of $(p_n)$ .

We can continue in this fashion to construct a strictly increasing subsequence of $(p_n)$ .

Case 2: Case 1 fails.

In other words, there exists a subsequence $(q_n)$ of $(p_n)$ such that every term in $(q_n)$ is at least as large as some later term in $(q_n)$ . In this case, we can build a decreasing subsequence $(d_n)$ .

Consider such a sequence $(q_n)$ . Let $d_1=q_1$ . By the assumption of Case 2, there exists some $q_a\leq q_1$ . Let $d_2=q_a$ . By the assumption again, there exists some $q_a\leq q_b$ . Let $d_3=q_b$ . We can continue in this fashion to build a decreasing subsequence of $(q_n)$ . Since $(q_n)$ is a subsequence of $(p_n)$ , we have that $(d_n)$ is a decreasing subsequence of $(p_n)$ . This completes the proof of Lemma 2.

The Bolzano-Weierstrass Theorem follows immediately: every bounded sequence of reals contains some monotone subsequence by Lemma 2, which is in turn bounded. This subsequence is convergent by Lemma 1, which completes the proof.

Page

Toolbox

Search

Bolzano-Weierstrass Theorem

Statement

Proof

See also