Bolzano-Weierstrass Theorem

(See MATH 409 Lecture 7#Bolzano-Weierstrass Theorem→)

Theorem. Every bounded sequence of real numbers has a convergent subsequence.

Proof. Let $\left\{x_n\right\}$ be a bounded sequence of real numbers. We are going to build a nested sequence of intervals $I_n=[a_n,b_n]$ for $n\in \mathbb{\mathbb{N}}$, such that each $I_n$ contains infinitely many elements of $\left\{x_n\right\}$ and $\left|I_{n+1}\right|=\frac{\left|I_n\right|}{2}$ for all $n\in \mathbb{\mathbb{N}}$. The sequence is built inductively.

Basis. First we set $I_1$ to be any closed bounded interval that contains all elements of $\left\{x_n\right\}$ (such an interval exists because the sequence $\left\{x_n\right\}$ is bounded).

Induction. Now assume that for some $n\in \mathbb{\mathbb{N}}$ the interval $I_n$ is already chosen and it contains infinitely many elements of $\left\{x_n\right\}$. Then at least one of the subintervals $I^{\prime }=[a_n,\frac{a_n+b_n}{2}]$ and $I^{″}=[\frac{a_n+b_n}{2},b_n]$ also contains infinitely many elements of $\left\{x_n\right\}$. We set $I_{n+1}$ to be such an interval. By construction, $I_{n+1}\subset I_n$ and $\left|I_{n+1}\right|=\frac{\left|I_n\right|}{2}$.

Since $\left|I_{n+1}\right|=\frac{\left|I_n\right|}{2}$ for all $n\in \mathbb{\mathbb{N}}$, it follows by induction that $\left|I_n\right|=\frac{\left|I_1\right|}{2^{n-1}}$ for all $n\in \mathbb{\mathbb{N}}$. As a consequence, $\left|I_n\right|\to 0$ as $n\to \mathrm{\infty }$. By the Nested Intervals Property, the intersection of the intervals consists of a single number $a$.

Next we are going to build a strictly increasing sequence of natural numbers $\left\{n_k\right\}$ such that $x_{n_k}\in I_k$ for all $k\in \mathbb{\mathbb{N}}$. The sequence is built inductively:

Basis. First let $n_1=1$.

Induction. Now assume that for some $k\in \mathbb{\mathbb{N}}$ the number $n_k$ is already chosen. Since the interval $I_{k+1}$ contains infinitely many elements of the sequence $\left\{x_n\right\}$, there exists $m>n_k$ such that $x_m\in I_{k+1}$. We set $n_{k+1}=m$.

Now we claim that the subsequence ${\left\{x_{n_k}\right\}}_{k\in \mathbb{\mathbb{N}}}$ of the sequence $\left\{x_n\right\}$ converges to $a$. Indeed, for any $k\in \mathbb{\mathbb{N}}$, the points $x_{n_k}$ and $a$ both belong to the interval $I_k$. Hence $|x_{n_k}-a|\le \left|I_k\right|$. Since $\left|I_k\right|\to 0$ as $k\to \mathrm{\infty }$, it follows that $x_{n_k}\to a$ as $k\to \mathrm{\infty }$.

quod erat demonstrandum