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 is a bounded increasing sequence of reals, so
. Let
. We want to show that
. Assume
. By the definition of convergence, we need to produce some
such that for all
,
. Since
is the least upper bound of the sequence, there exists an
such that
, and since
is increasing, we know that for all
,
. Therefore for all
,
. This shows that
converges to
. 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 of reals, we consider two cases:
- Case 1: Every infinite subsequence of
contains a term that is strictly smaller than infinitely many later terms in the subsequence.
In this case, we build a strictly increasing subsequence .
Note that we can apply the assumption of Case 1 to itself. Thus there exists some
such that there exist infinitely many
such that
. Let
, and consider the subsequence
where
, and
is the
th term in
after
that is greater than
. This exists by the assumption.
Now we can apply the assumption of Case 1 to . Thus there exists some
such that there exist infinitely many
such that
. Since
is a subsequence of
, there exists an
such that
. We then let
, and let
be a subsequence of
such that
, and
is the
th term in
after
that is gerater tha
. Note that
is a subsequence of
.
We can continue in this fashion to construct a strictly increasing subsequence of .
- Case 2: Case 1 fails.
In other words, there exists a subsequence of
such that every term in
is at least as large as some later term in
. In this case, we can build a decreasing subsequence
.
Consider such a sequence . Let
. By the assumption of Case 2, there exists some
. Let
. By the assumption again, there exists some
. Let
. We can continue in this fashion to build a decreasing subsequence of
. Since
is a subsequence of
, we have that
is a decreasing subsequence of
. 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.
See also
This article is a stub. Help us out by expanding it.