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}=\left[a_{n},b_{n}\right]$ for $n\in \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 {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 {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'=\left[a_{n},{\frac {a_{n}+b_{n}}{2}}\right]$ and $I''=\left[{\frac {a_{n}+b_{n}}{2}},b_{n}\right]$ 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 {N}$, it follows by induction that $\left|I_{n}\right|={\frac {\left|I_{1}\right|}{2^{n-1}}}$ for all $n\in \mathbb {N}$. As a consequence, $\left|I_{n}\right|\to 0$ as $n\to \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 {N}$. The sequence is built inductively:

Basis. First let $n_{1}=1$.

Induction. Now assume that for some $k\in \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 {N} }$ of the sequence $\left\{x_{n}\right\}$ converges to $a$. Indeed, for any $k\in \mathbb {N}$, the points $x_{n_{k}}$ and $a$ both belong to the interval $I_{k}$. Hence $\left|x_{n_{k}}-a\right|\leq \left|I_{k}\right|$. Since $\left|I_{k}\right|\to 0$ as $k\to \infty$, it follows that $x_{n_{k}}\to a$ as $k\to \infty$.

quod erat demonstrandum