The Idea Shop: Walking Through the Bolzano-Weierstrass Theorem

Walking Through the Bolzano-Weierstrass Theorem

(Note: see here for a simpler version of this proof.)

Economic theory relies pretty heavily on a handful of mathematical proofs. One of the most important for proving the existence of equilibria is the Bolzano-Weierstrass theorem.

In this post I'll give a basic explanation of the Bolzano-Weierstrass theorem, and walk you through a simple proof of it.

Some Background
Bolzano-Weierstrass is a theorem about sequences of real numbers. Sequences can either be convergent -- that is, they can approach some long-run value -- or they can be divergent and blow up to infinity. For many equilibrium concepts, it's necessary to show that a given sequence is convergent and stays within some reasonable set of values as we move far out along the sequence in the long run.

Bolzano-Weierstrass basically says that we'll always end up with a convergent subsequence if we start with the right kind of sequence to begin with. Specifically, it says that if we start with a closed and bounded sequence -- that is, if our sequence is finite and contains its own endpoints -- then it's guaranteed to have a subsequence that converges. Often that means the equilibrium we're interested in actually exists, which is a good thing.

In the rest of this post, I'll walk through a typical proof of the theorem. Different variations on this basic proof are used pretty widely in the more mathematical branches of economics such as game theory and general equibrium theory.

Proving the Theorem
Here's the formal statement of the Bolzano-Weierstrass theorem: Every closed and bounded real sequence has a convergent subsequence.

Proof. Let be a bounded real sequence. Then there exists a closed interval [c, d] such that for all positive integers n -- that is, for all .

Now divide the interval [c,d] into the following two intervals:

Since the sequence is bounded, infinitely many terms of it are contained in the original interval [c,d]. Now that we've split that interval in two, one of those two intervals must contain for infinitely many positive integers n. Call this interval .

Now repeat this step, dividing into the following:

Similarly, one of these intervals must also contain for infinitely many positive integers n. Call this . Continuing this process, we get a sequence of intervals such that

where each of these intervals contains for infinitely many positive integers n, and the width of each of the k intervals is given by

Now pick a positive integer such that . Since the next interval contains for infinitely many positive integers n, we can now choose an n_1" target="_blank"> n_1" title="\inline n_2>n_1" /> such that . Continuing this process, we can obtain elements such that

and

This means the newly created sequence is a subsequence of . So we've established that every bounded real sequence has a subsequence. The next step is to go further and show that this subsequence actually converges.

To see why this subsequence converges, consider the illustration below. It shows the original interval [c, d] at the top, with the subsequent intervals [c1, d1], [c2, d2], ...] we created by repeatedly dividing it below.

Note that each interval is half the length of the previous interval, and that the boundaries of each interval are always moving inward or staying the same -- they're never moving outward. That is, the sequence of lower bounds is always moving inward as k grows. Similarly, the sequence of upper bounds is always pushing inward as k grows. That means both the lower and upper bounds are monotone and bounded. And that guarantees they are both convergent.

Let's label the value that the lower bounds converge to as . Similarly, let's label the value the upper bounds converge to as . Using our equation for the width of each interval from above, we know that

Taking the limit of both sides, we see that

So this shows that both the upper and lower bounds converge to the same value of L = M.

We saw above that , so that means for all k. But since and converge to the same limit of L = M, by the so-called "squeeze theorem" we know that must also converge to the same limit of L = M.

That shows that every closed and bounded real sequence -- that is, every sequence defined on a compact set -- has a subsequence , and that this subsequence is convergent. And that completes the proof.

For more on Bolzano-Weierstrass, check out the Wiki article here.

Posted by Andrew on Monday May 11, 2009 | Feedback?

* * *