The Bolzano-Weierstrass Theorem states that any bounded sequence of real numbers has a convergent subsequence.

The proof of this theorem is as follows. The Monotone convergence axiom states that any bounded monotonic sequence of real numbers converges, so it only needs to be shown that any sequence of real numbers has a monotonic subsequence.

Let (a_n) be a sequence of real numbers. Say that k is a maximal index if a_k>=a_l for all l>=k. Then there are two possibilities:

• There are infinitely many maximal indices k₁<k₂<k₃<...
  Then a_{k_1}>=a_{k_2}>=a_{k_3}>... so (a_n) has a decreasing subsequence.
• There are finitely many maximal indices. Let b be an upper bound for the set of maximal indices. Then if n>b, n isn't a maximal index. It can be shown by induction that there exists an increasing subsequence (a_{k_j}). Let k₁=b+1. k₁ isn't a maximal index, so there exists k₂>k₁ with a_{k_2}>a_{k_1}. Now, suppose we have found k_j. k_j isn't a maximal index, so there exists k_j+1>k_j with a_{k_j+1}>a_{k_j}. So one can find an increasing subsequence.

So in either case, there is a monotonic subsequence.

QED, as they don't say.

Theorem: Each bounded real sequence has a convergent subsequence.

Let {a_n} be a bounded real sequence. Then there is a real M such that for each n,a_n is in [-M,M ], which is Heine-Borel compact. Let E be the set of points in {a_n}. Then E is either finite or infinite.

Suppose E is finite. Label the points p₁,...,p_k and associate with each p_j the set E_j={n: a_n=p_j }. The E_j form a partition of the positive integers. So one of the E_j must be countable. Label its elements as a strictly increasing sequence {n_k}. Thus {a_{n_k} } is a convergent subsequence of {a_n}.

Suppose E is infinite. Because it is an infinite subset of the compact set [-M,M ], E has a limit point A in [-M,M ]. So each neighborhood of A contains a countable subset of E; in other words, each neighborhood of A contains countably many terms of {a_n}. Thus there is a convergent subsequence of {a_n}.

Every infinite subset of (0,1) has a limit point

(mathematics, topology)

Theorem:Every infinite subset V of (0,1) has a limit point. (Equivalently, every infinite set of points in (0,1) contains a sequence converging to a point not in the sequence, though perhaps in the set )

Proof: It is sufficient to show that some subset of V has a limit point. Assume the contrary. Let V₀=V and form a sequence according to the following rule:
V_n+1=V_n - lub(V_n) (lub indicates the least upper bound)

Observe that for all i:

1. lub(V_i) exists because V_i is bounded above by 1.
2. V_i is non-empty because V₀ is infinite and only a single point is removed at each step.
3. lub(V_i) ∈ V_i. Otherwise, it would be a limit point of V_i, a contradiction.
4. lub(V_i+1) < lub(V_i). Since V_i+1 ⊂ V_i, ∀v∈V_i+1, v < lub(V_i). (The inequality is strict because V_i+1=V_i-lub(V_i)). Therefore, by (3), lub(V_i+1) < lub(V_i).

Now, consider the following two cases:

There exists a j such that V_j=V_j+1

Since V_j = V_j+1 = V_j - lub(V_j), lub(V_j) ∉ V_j, contradicting (3).

For all j, V_j ≠ V_j+1

Form the set A={lub(V_j)}. A is itself a subset of (0,1) bounded below by 0, and thus has a greatest lower bound. Let a=glb(A). If a ∉ A, a is a limit point of A, a contradiction. If a ∈ A, a=lub(V_k) for some k. However, by (4), V_k+1 < a, a contradiction. QED

The Bolzano-Weierstraß Theorem is part of a holy trinity of basic real analysis theorems, each proved by either of the other two. MacTutor (1) describes Bernhard Bolzano as a philosopher-mathematician whose main concern was separating analysis from the concept of the infinitesimal. This also happened to be the goal of every other 18th and 19th century analyst, so it is no surprise that Karl Weierstrass independently proved this theorem. Weierstraß has several other useful theorems, so many of his carry more than one name.

The theorem itself is subtle and not as obvious as other theorems in real analysis. "Every bounded sequence has a convergent subsequence." Another equivalent formulation of the theorem says, "Every bounded sequence has an accumulation point." Just as the concept of convergence can be extended to other settings other than the real numbers, the Bolzano-Weierstraß Theorem can be extended to more general settings as well. First, we'll prove the theorem. Then we'll make some remarks about its dependencies and how to go about extending it.

There are several equivalent proofs of Bolzano-Weierstraß Theorem (see other writeups in this node), and several equivalent statements (ditto). The proof that these statements are equivalent typically falls from translating the terms of one statement into the other. It's my hope that this presentation of the theorem will be most accessible, but doing this has unfortunately made it quite long. "If the measure of a node were the time it took to understand it, there would be many small nodes that were actually quite large, and many large nodes that were actually quite small."

Theorem: Every bounded sequence has a convergent subsequence.

Outline:

This is one beast of a proof. Most people have at least six years of post-primary education before encountering it; sane people learn it during their senior undergraduate year.

1. Establish some definitions.
2. Begin constructing a sequence of nested intervals, each containing the tail end of the sequence, and at the same time construct the indices of the subsequence.
3. Repeat forever.
4. Invoke Cantor's Intersection Theorem (aka the Nested Intervals Theorem) on the sequence of nested intervals to obtain the accumulation point.
5. Prove the accumulation point is the limit of the subsequence.

Motivations:

Constructing subsequences from other sequences is a fairly natural thing to do. Take, for instance, the sequence {1/n}. We already know it converges to zero. As well, the subsequence {1/2n} (which looks like 1/2, 1/4, 1/6, ...) converges to zero.

There are also subsequences that don't actually converge to any certain number. One of the more obvious ones is the sequence {sin n}. It oscillates between 1 and -1, but never 'settles down'. Regardless, according to Bolzano-Weierstraß, it has a convergent subsequence. After the proof, I'll construct the beginning of such a sequence.

Proof: Adapted from (2)

Opening Deliberations

There are essentially three math-heavy words in the statement of the theorem: subsequence, bounded sequence, and convergence.

To make a subsequence from a given sequence, we have to construct another sequence of indices. This sequence of indices has to be strictly increasing; otherwise finding accumulation points would be trivial. You could choose, for example, the sequence {1, 1, 1, 1,...} and then the 'subsequence' would converge to whatever the first element of the sequence was.

A bounded sequence is a sequence which never strays from a particular segment of the real line. It is bounded below by one number, and bounded above by another.

Finally, a sequence an converges to a if and only if (∀ε>0)(∃M(ε))(∀n>M)(|an-a|<ε). This is the epsilion definition of a limit, popular with rigorous analysis. If you prefer English: "For any given ε greater than zero, one could find a number M such that the limit of the sequence is within ε distance away from the tail of the sequence, starting from M." If you prefer (slightly more) real English: "The farther down the sequence you go, the closer you get to the limit of the sequence," but that sounds awfully circular.

Bifurcation, or: Nailing Down a Fly by its Wings

Assume we are given a bounded sequence an. Because the sequence is bounded, the set {an} will be contained within an interval. Let this interval be called [c1, d1]. Also, let the beginning of our index sequence be n1 = 1. This means the first element of the subsequence, an1 = a1.

Now, slice this interval in half about its midpoint. There are essentially two possiblities:

1. The part of the sequence within one half is infinite, and the other is finite. Let the second interval [c2, d2] be the interval containing the infinite part.
2. Both parts of the sequence within both halves are infinite. Take either interval and make it [c2, d2].

Notice that, whichever possiblity holds, we have an interval containing the rest of the sequence. Take n2 > n1, such that an2 is in [c2, d2]. Note that this is possible because the tail within the second interval is infinite; we can travel as far down the sequence as necessary to find an index greater than the previous one.

If you followed that, you'll have no trouble repeating the subdivision of [c2, d2] into halves, finding the proper half, and obtaining a yet greater third index. Now do it again. And again. And again... forever.

Hmmm. How do we know we can repeat this process infinitely? One way is to resort to a proof by induction to show the existence of a tail to the sequence no matter how great an index one chooses to start from. Another way is to repeat the process several times and convince yourself that this selection process can't terminate.

Infinite Bifurcation into Infinite Nested Intervals (IBINI)

After performing a countably infinite number of steps, we have:

1. A sequence of closed, nested, and bounded intervals, [cn, dn].
2. A subsequence ank such that the kth element of the subsequence is in the kth interval.

Now, our sequence of intervals fulfills the criteria of Cantor's Intersection Theorem, which says: "If a sequence of nested, closed intervals is bounded, then there is a real number contained in every interval." We invoke the intersection theorem on the system mentioned in one to find a, which we will soon prove to be the accumulation point of the sequence.

Measuring the Finishing Touches

Since ank and a are both contained in every interval, it stands to reason that the distance between the two, (|ank - a|), is less than or equal to the length of the interval, dk - ck. The length of the first interval is d1 - c1, and every other interval is half as long as the previous one (since that's the way we constructed it).

In general, dk - ck = 2-k+1(d1 - c1). Now, you can prove this new sequence of lengths converges to zero straight from the definition (annoying and trivial), or just recognize that as k grows large, 2^-k+1 will grow very small, and the whole thing eventually converges to zero.

Either way, knowing |ank - a| ≤ 2-k+1(d1 - c1) allows us to use the same ε and M that caused the right sequence to converge to zero to prove that the left hand side converges to a.

Therefore, given any arbitrary sequence, it is possible to construct a convergent subsequence.

Application

Bolzano-Weierstraß is a constructive proof, meaning that it actually yields a numerical result. Consider the sequence sin n. We know that this sequence is bounded within the interval [-1, 1]; this means we can find a subsequence that converges to something in this interval.

1. [-1, 1]: sin 1 is approximately 0.841....
2. [0, 1]: sin 2 is about 0.909....
3. [0.5, 1]: sin 8 is about 0.989....
4. [0.75, 1]: sin 14 is about 0.991....

And so on. {1, 2, 8, 14,...} is the start of a sequence which indexes a convergent subsequence of sin n. In this circumstance, the calculations seem to point towards 1 being an accumulation point. Of course, sequences can have more than one accumulation point; in fact, every point within this interval is an accumulation point for sin n.

Criticisms of Bolzano-Weierstraß

Without a doubt, this theorem is not as intuitive as most of the results of real analysis. The completeness axiom or archimedean principle are much easier to believe than it. Most of the problem comes from the infinite number of steps that would be required to actually construct the subsequence — even though constructivists permit countably infinite steps in proofs, it still makes one nervous.

However, if you can get beyond the infinite recursion, this proof has some nice aspects. It doesn't require a one-shot definition (such as "maximal peak") and hides the use of the Heine-Borel Theorem and any need for one to understand compactness. Cantor's Intersection Theorem is easy enough to prove in the setting of the real numbers through the application of the completeness axiom. Any other proof that would require less background would probably require more handwaving.

Any one of the three theories — Heine-Borel, Cantor's, or Bolzano-Weierstraß — contains enough information to prove the other two (3), making them all equivalent statements. They make the real numbers an interesting environment to do calculus in.

---

(1) http://www-groups.dcs.st-and.ac.uk/~history/Mathematicians/Bolzano.html, MacTutor's History of the Mathematicians.
(2) Bartle & Sherbert, Introduction to Real Analysis, 3rd edition.
(3) Eric W. Weisstein et al., Bolzano-Weierstrass Theorem, Mathworld.
Also http://en.wikipedia.org/wiki/Bolzano-Weierstrass_theorem for the Wikipedia Mathematics version.