Statement and proof by bisection

Statement

Bolzano-Weierstrass theorem. Every bounded real sequence has a convergent subsequence.

The result bears the names of Bolzano, who used it as early as 1817 in his proof of the intermediate value theorem, and of Weierstrass, who isolated the general statement around 1860. It expresses a deep property of $\mathbb{R}$: the compactness of closed bounded intervals.

Note carefully what the theorem does not say. It does not claim that the sequence converges, only that one of its subsequences converges. The sequence $u_n = (-1)^n$ is bounded and divergent, but $\left(u_{2n}\right)$ converges to $1$.

The construction by bisection

Let $(u_n)$ be a bounded sequence: there exist $a$ and $b$ such that $u_n \in [a, b]$ for all $n$. Set $I_0 = [a, b]$.

Constructing the intervals. Suppose $I_n = [a_n, b_n]$ has been constructed, with the property

$$\mathcal{P}_n : \quad \left\{\, k \in \mathbb{N} \;:\; u_k \in I_n \,\right\} \ \text{is infinite}$$

Cut $I_n$ at its midpoint $m_n = \dfrac{a_n + b_n}{2}$. The two halves $\left[a_n, m_n\right]$ and $\left[m_n, b_n\right]$ share the infinite set of indices $k$ such that $u_k \in I_n$. If each contained only finitely many, their union would be finite, which is absurd. At least one of the two halves therefore contains infinitely many indices: we choose it as $I_{n+1}$, and $\mathcal{P}_{n+1}$ holds.

Property $\mathcal{P}_0$ is true, since all indices qualify. The construction therefore continues indefinitely, and by bisection

$$b_n - a_n = \frac{b - a}{2^n} \xrightarrow[n \to +\infty]{} 0$$

Constructing the extraction map. We define $\varphi$ recursively:

$$\varphi(0) = \min \left\{\, k \in \mathbb{N} \;:\; u_k \in I_0 \,\right\} = 0$$

$$\varphi(n+1) = \min \left\{\, k \in \mathbb{N} \;:\; k > \varphi(n) \ \text{ and } \ u_k \in I_{n+1} \,\right\}$$

This set is nonempty, precisely because $\mathcal{P}_{n+1}$ provides infinitely many suitable indices: so some remain beyond $\varphi(n)$. Since every nonempty subset of $\mathbb{N}$ has a least element, $\varphi(n+1)$ exists, and $\varphi(n+1) > \varphi(n)$ by construction. The map $\varphi$ is indeed strictly increasing.

Conclusion. By construction, $u_{\varphi(n)} \in I_n$, that is,

$$a_n \leq u_{\varphi(n)} \leq b_n$$

The intervals $I_n$ are nested and their length tends to $0$: by the nested intervals theorem, $a_n$ and $b_n$ converge to the same real number $c$. The squeeze theorem then gives

$$u_{\varphi(n)} \xrightarrow[n \to +\infty]{} c$$

The subsequence $\left(u_{\varphi(n)}\right)$ converges: the theorem is proved.

Cluster points

The limit $c$ obtained is called a cluster point (or subsequential limit) of $(u_n)$: a real number that is the limit of at least one subsequence. The theorem can be restated as:

Every bounded real sequence has at least one cluster point.

A bounded sequence can have several — two for $(-1)^n$, infinitely many for a sequence that densely sweeps $[0, 1]$. The link with convergence is as follows: a bounded sequence that has a unique cluster point converges to it.

Classic pitfall

Writing "we keep the half that contains infinitely many terms" instead of infinitely many indices. The distinction is real: the constant sequence $u_n = 0$ takes only one value, so "infinitely many terms" would make no sense, whereas the set of indices $k$ such that $u_k \in I_n$ is indeed infinite. The argument is always about indices.

Second pitfall, more serious in an exam: forgetting the condition $k > \varphi(n)$ in the definition of $\varphi(n+1)$. Without it, you get a sequence of terms, but not a subsequence, and the whole proof collapses.