## 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 $\inline \left \{ a_{n} \right \}$ be a bounded real sequence. Then there exists a closed interval [c, d] such that $\inline \left \{ a_{n} \right \}\in [c,d]$ for all positive integers n -- that is, for all $\inline n\in \mathbb{Z^{+}}$.

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

$\left [c,\frac{c+d}{2} \right ], \left[\frac{c+d}{2},d\right]$

Since the sequence $\inline \left\{a_{n} \right\}$ 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 $\inline a_{n}$ for infinitely many positive integers n. Call this interval $\inline [c_{1},d_{1}]$.

Now repeat this step, dividing $\inline [c_{1},d_{1}]$ into the following:

$\left [c_{1},\frac{c_{1}+d_{1}}{2} \right ], \left[\frac{c_{1}+d_{1}}{2},d_{1}\right]$

Similarly, one of these intervals must also contain $\inline a_n$ for infinitely many positive integers n. Call this $\inline [c_2,d_2]$. Continuing this process, we get a sequence of intervals $\inline [c_1,d_1], [c_2,d_2] \cdots$ such that

$[c_1,d_1] \supset [c_2,d_2] \supset [c_3,d_3] \supset \cdots$

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

$d_k - c_k = \frac{d-c}{2^k}, \ \ \ \ \ \ \ \ k=1,2, \hdots$

Now pick a positive integer $\inline n_1$ such that $\inline a_{n_1} \in[c_1,d_1]$. Since the next interval $\inline [c_2,d_2]$ contains $\inline a_n$ for infinitely many positive integers n, we can now choose an $\inline n_2>n_1$ such that $\inline a_{n_2} \in [c_2,d_2]$. Continuing this process, we can obtain elements $\inline a_{n_1}, a_{n_2}, a_{n_3}, \hdots$ such that

$a_{n_k} \in [c_k,d_k], \ \ \ \ \ \ \ \ k=1,2,\hdots$

and

$n_1

This means the newly created sequence $\inline \inline \left \{ a_{n_k} \right \}_{k=1}^{\infty }$ is a subsequence of $\inline \left \{ a_{n} \right \}$. So we've established that every bounded real sequence has a subsequence. The next step is to go further and show that this subsequence $\inline \left \{ a_{n_{k}} \right \}$ 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 $\inline \left \{ c_k \right \}$ is always moving inward as k grows. Similarly, the sequence of upper bounds $\inline \left \{ d_k \right \}$ 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 $\inline \inline \lim_{k \to \infty}\left \{ c_k \right \}=L$. Similarly, let's label the value the upper bounds converge to as $\inline \inline \lim_{k \to \infty}\left \{ d_k \right \}=M$. Using our equation for the width of each interval from above, we know that

$d_k - c_k = \frac{d-c}{2^k}$

Taking the limit of both sides, we see that

$\lim_{k \to \infty} (d_k - c_k) = \lim_{k \to \infty}\left (\frac{d-c}{2^k} \right )$

$\Rightarrow \lim_{k \to \infty} d_k - \lim_{k \to \infty}c_k = 0$

$\Rightarrow M - L = 0$

$\Rightarrow M = L$

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

We saw above that $\left \{ a_{n_k} \right \} \in [c_k,d_k]$, so that means $\inline c_k \leq a_{n_k} \leq d_k$ for all k. But since $\inline c_k$ and $\inline d_k$ converge to the same limit of L = M, by the so-called "squeeze theorem" we know that $\inline \left \{ a_{n_k} \right \}$ must also converge to the same limit of L = M.

That shows that every closed and bounded real sequence $\inline \left \{ a_{n} \right \}$ -- that is, every sequence defined on a compact set -- has a subsequence $\inline \left \{ a_{n_k} \right \}$, 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?

* * *