# Bolzano-Weierstrass Theorem

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

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

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

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

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

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

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

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

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

quod erat demonstrandum