Bolzano–Weierstrass theorem

Proof

First we prove the theorem for ${\displaystyle \mathbb{R}}$ (set of all real numbers), in which case the ordering on ${\displaystyle \mathbb{R}}$ can be put to good use. Indeed, we have the following result:

Lemma: Every infinite sequence ${\displaystyle (x_n)}$ in ${\displaystyle \mathbb{R}}$ has an infinite monotone subsequence (a subsequence that is either non-decreasing or non-increasing).

Proof: Let us call a positive integer ${\displaystyle n}$ of a sequence a "peak index" of the sequence when ${\displaystyle x_m\le x_n}$ for every ${\displaystyle m>n}$. Suppose first that the sequence has infinitely many peaks, which means there is a subsequence with the following indices ${\displaystyle n_1<n_2<n_3<\cdots <n_j<\dots }$ and the following terms ${\displaystyle x_{n_1}\ge x_{n_2}\ge x_{n_3}\ge \cdots \ge x_{n_j}\ge \dots }$. So, the infinite sequence ${\displaystyle (x_n)}$ in ${\displaystyle \mathbb{R}}$ has a monotone (non-increasing) subsequence, which is ${\displaystyle (x_{n_j})}$. But suppose now that there are only finitely many peaks, let ${\displaystyle N}$ be the final peak if one exists (let ${\displaystyle N=0}$ otherwise) and let the first index of a new subsequence ${\displaystyle (x_{n_j})}$ be set to ${\displaystyle n_1=N+1}$. Then ${\displaystyle n_1}$ is not a peak, since ${\displaystyle n_1}$ comes after the final peak, which implies the existence of ${\displaystyle n_2}$ with ${\displaystyle n_1<n_2}$ and ${\displaystyle x_{n_1}<x_{n_2}}$. Again, ${\displaystyle n_2}$ comes after the final peak, hence there is an ${\displaystyle n_3}$ where ${\displaystyle n_2<n_3}$ with ${\displaystyle x_{n_2}<x_{n_3}}$. Repeating this process leads to an infinite non-decreasing subsequence ${\displaystyle x_{n_1}<x_{n_2}<x_{n_3}<\dots }$, thereby proving that every infinite sequence ${\displaystyle (x_n)}$ in ${\displaystyle \mathbb{R}}$ has a monotone subsequence.

Now suppose one has an infinite bounded sequence in ${\displaystyle \mathbb{R}}$. By the lemma proven above, there exists a monotone subsequence, likewise also bounded. It follows from the monotone convergence theorem that this subsequence converges.

The general case in ${\displaystyle {\mathbb{R}}^n}$ can be proven using this lemma as follows. Firstly, we will acknowledge that any sequence ${\displaystyle (x_m{)}_{m\in I}}$ in ${\displaystyle {\mathbb{R}}^n}$ (where ${\displaystyle I}$ denotes its index set) has a convergent subsequence if and only if there exists a countable set ${\displaystyle K\subseteq I}$ such that ${\displaystyle (x_m{)}_{m\in K}}$ converges. Let ${\displaystyle (x_m{)}_{m\in I}}$ be any bounded sequence in ${\displaystyle {\mathbb{R}}^n}$, then it can be expressed as an n-tuple of sequences in ${\displaystyle \mathbb{R}}$ by writing ${\displaystyle x_m=(x_{m1},x_{m2},\dots ,x_{mn})}$, where ${\displaystyle (x_{mj}{)}_{m\in I}}$ is a sequence for ${\displaystyle j=1,2,\dots ,n}$. Since ${\displaystyle (x_m)}$ is bounded, ${\displaystyle (x_{mj})}$ is also bounded for ${\displaystyle j=1,2,\dots ,n}$. It follows then by the lemma that ${\displaystyle (x_{m1})}$ has a convergent subsequence and hence there exists a countable set ${\displaystyle K_1\subseteq I}$ such that ${\displaystyle (x_{m1}{)}_{m\in K_1}}$ converges. For the sequence ${\displaystyle (x_{m2})}$, by applying the lemma once again there exists a countable set ${\displaystyle K_2\subseteq K_1\subseteq I}$ such that ${\displaystyle (x_{m2}{)}_{m\in K_2}}$ converges and hence ${\displaystyle (x_{m2})}$ has a convergent subsequence. This reasoning may be applied until we obtain a countable set ${\displaystyle K_n}$ for which ${\displaystyle (x_{mj}{)}_{m\in K_n}}$ converges for ${\displaystyle j=1,2,\dots ,n}$. Hence, ${\displaystyle (x_m{)}_{m\in K_n}}$ converges and therefore, since ${\displaystyle (x_m)}$ was arbitrary, any bounded sequence in ${\displaystyle {\mathbb{R}}^n}$ has a convergent subsequence.

Alternative proof over R using nested intervals

There is also an alternative proof of the Bolzano–Weierstrass theorem using nested intervals. We start with a bounded sequence ${\displaystyle (x_n)}$:

Because we halve the length of an interval at each step, the limit of the interval's length is zero. Also, by the nested intervals theorem, which states that if each ${\displaystyle I_n}$ is a closed and bounded interval, say

${\displaystyle I_n=[a_n,b_n]}$

with

${\displaystyle a_n\le b_n}$

then under the assumption of nesting, the intersection of the ${\displaystyle I_n}$ is not empty. Thus there is a number ${\displaystyle x}$ that is in each interval ${\displaystyle I_n}$. Now we show, that ${\displaystyle x}$ is an accumulation point of ${\displaystyle (x_n)}$.

Take a neighbourhood ${\displaystyle U}$ of ${\displaystyle x}$. Because the length of the intervals converges to zero, there is an interval ${\displaystyle I_N}$ that is a subset of ${\displaystyle U}$. Because ${\displaystyle I_N}$ contains by construction infinitely many members of ${\displaystyle (x_n)}$ and ${\displaystyle I_N\subseteq U}$, also ${\displaystyle U}$ contains infinitely many members of ${\displaystyle (x_n)}$. This proves that ${\displaystyle x}$ is an accumulation point of ${\displaystyle (x_n)}$. Thus, there is a subsequence of ${\displaystyle (x_n)}$ that converges to ${\displaystyle x}$.

Sequential compactness in Euclidean spaces

Definition: A set ${\displaystyle A\subseteq {\mathbb{R}}^n}$ is sequentially compact if every sequence ${\displaystyle \{x_n\}}$ in ${\displaystyle A}$ has a convergent subsequence converging to an element of ${\displaystyle A}$.

Theorem: ${\displaystyle A\subseteq {\mathbb{R}}^n}$ is sequentially compact if and only if ${\displaystyle A}$ is closed and bounded.

Proof: (sequential compactness implies closed and bounded)

Suppose ${\displaystyle A}$ is a subset of ${\displaystyle {\mathbb{R}}^n}$ with the property that every sequence in ${\displaystyle A}$ has a subsequence converging to an element of ${\displaystyle A}$. Then ${\displaystyle A}$ must be bounded, since otherwise the following unbounded sequence ${\displaystyle \{x_n\}\in A}$ can be constructed. For every ${\displaystyle n\in \mathbb{N}}$, define ${\displaystyle x_n}$ to be any arbitrary point such that ${\displaystyle ||x_n||\ge n}$. Then, every subsequence of ${\displaystyle \{x_n\}}$ is unbounded and therefore not convergent. Moreover, ${\displaystyle A}$ must be closed, since any limit point of ${\displaystyle A}$, which has a sequence of points in ${\displaystyle A}$ converging to itself, must also lie in ${\displaystyle A}$.

Proof: (closed and bounded implies sequential compactness)

Since ${\displaystyle A}$ is bounded, any sequence ${\displaystyle \{x_n\}\in A}$ is also bounded. From the Bolzano–Weierstrass theorem, ${\displaystyle \{x_n\}}$ contains a subsequence converging to some point ${\displaystyle x\in {\mathbb{R}}^n}$. Since ${\displaystyle x}$ is a limit point of ${\displaystyle A}$ and ${\displaystyle A}$ is a closed set, ${\displaystyle x}$ must be an element of ${\displaystyle A}$.

Thus the subsets ${\displaystyle A}$ of ${\displaystyle {\mathbb{R}}^n}$ for which every sequence in A has a subsequence converging to an element of ${\displaystyle A}$ – i.e., the subsets that are sequentially compact in the subspace topology – are precisely the closed and bounded subsets.

This form of the theorem makes especially clear the analogy to the Heine–Borel theorem, which asserts that a subset of ${\displaystyle {\mathbb{R}}^n}$ is compact if and only if it is closed and bounded. In fact, general topology tells us that a metrizable space is compact if and only if it is sequentially compact, so that the Bolzano–Weierstrass and Heine–Borel theorems are essentially the same.

Application to economics

There are different important equilibrium concepts in economics, the proofs of the existence of which often require variations of the Bolzano–Weierstrass theorem. One example is the existence of a Pareto efficient allocation. An allocation is a matrix of consumption bundles for agents in an economy, and an allocation is Pareto efficient if no change can be made to it that makes no agent worse off and at least one agent better off (here rows of the allocation matrix must be rankable by a preference relation). The Bolzano–Weierstrass theorem allows one to prove that if the set of allocations is compact and non-empty, then the system has a Pareto-efficient allocation.