Two other proofs of the Bolzano-Weierstrass Theorem

We prove the result:

• If $\mathbb{X} = \{x_n: n \in \mathbb{N}\}$ is a sequence of real numbers, then $\mathbb{X}$ has a monotone subsequence.

Then the Bolzano-Weierstrass Theorem follows immediately, since if $\mathbb{X}$ is bounded, so is any subsequence, so there is a monotone bounded subsequence, which we know has a limit: its $\sup$ in the increasing case and its $\inf$ in the decreasing case.

To prove the result, let $\mathbb{X} = \{x_n: n \in \mathbb{N}\}$ be a given sequence.
Let $\mathbb{X}_{k} = \{ x_{n + k - 1}: n \in \mathbb{N}\}$ so $\mathbb{X}_k$ is a subsequence of $\mathbb{X}$ for each $k \in \mathbb{N}$.
Note that the first term of $\mathbb{X}_k$ is $x_k$ and we have $\mathbb{X}_j \subset \mathbb{X}_k$ when $j \ge k$.

• We say that $k \in \mathbb{N}$ is a peak if and only if $\sup(\mathbb{X}_k)$ exists and is $x_k$.

Let $\mathbb{Z}$ be the set of all peaks.

• If $\mathbb{Z}$ is a finite (or empty) set, let $N_1$ be the smallest positive integer larger than any $y \in \mathbb{Y}$.
  • Then $N_1$ is not a peak, so some $N_2$ exists, with $N_2 > N_1$, such that $x_{N_2} > x_{N_1}$.
  • Then $N_2$ is not a peak, so some $N_3$ exists, with $N_3 > N_2$, such that $x_{N_3} > x_{N_2}$.
  • Then $N_3$ is not a peak, so some $N_4$ exists, with $N_4 > N_3$, such that $x_{N_4} > x_{N_3}$.
  This process may be continued forever, with the result that we construct a subsequence $\mathbb{Y} = \{x_{N_j}; j \in \mathbb{N}\}$ of $\mathbb{X}$, such that $x_{N_{j + 1}} > x_{N_j}$, for each $j \in \mathbb{N}$. So the sequence $\mathbb{Y}$ is a strictly increasing subsequence of $\mathbb{X}$ and we are done.
• If $\mathbb{Z}$ is an infinite set, we list them in order $\mathbb{Z} = \{ M_j: j \in \mathbb{N}\}$, where $M_j < M_{j + 1}$, for each $j$. Then put $\mathbb{Y} = \{ x_{M_j}: j \in \mathbb{N}\}$. Then if $k \in \mathbb{N}$, we have $x_{M_{k + 1}} \in \mathbb{X}_{M_k}$, since $M_{k + 1} > M_k$. So we have, since $M_k$ is a peak, $x_{M_{k + 1}} \le \sup(\mathbb{X}_{M_k}) = x_{M_k}$. So the sequence $\mathbb{Y}$ is a monotonic decreasing subsequence of $\mathbb{X}$ and we are done.

So in all cases we produce a monotonic subsequence of $\mathbb{X}$ and the result is proved. For the third proof, we use interval subdivision. Let $\mathbb{X}$ be a bounded sequence, so $\mathbb{X} \subset \mathbb{J}_1 = [a_1, b_1]$ for some real numbers $a_1$ and $b_1$ with $a_1 < b_1$.

• Bisect $\mathbb{J}_1$: $\mathbb{J}_1 = \mathbb{L}_1 \cup \mathbb{R}_1$, where $\mathbb{L}_1 = \left[a_1, \frac{a_1 + b_1}{2}\right]$ and $\mathbb{R}_1 = \left[ \frac{a_1 + b_1}{2}, b_1\right]$.
  Put $\mathbb{N}_1 = \mathbb{N}$.
  Then define the sets $\lambda_1 = \{ n \in \mathbb{N}_1: x_n \in \mathbb{L}_1\}$ and $\rho_1 = \{ n \in \mathbb{N}_1: x_n \in \mathbb{R}_1\}$. Then $\lambda_1 \cup \rho_1 = \mathbb{N}_1 = \mathbb{N}$, so at least one of the sets $\lambda_1$ and $\rho_1$ is infinite.
  • If $\lambda_1$ is infinite, put $\mathbb{J}_2 = \mathbb{L}_1 = [a_2, b_2]$, with $a_2 = a_1$ and $b_2 = \frac{a_1 + b_1}{2}$ and $a_1 \le a_2 < b_2 \le b_1$.
    Also put $n_1 = \inf(\lambda_1)$ and $\mathbb{N}_2 = \{ n \in \mathbb{N}_1: n > n_1\}$.
  • If $\lambda_1$ is finite or empty, put $\mathbb{J}_2 = \mathbb{R}_1 = [a_2, b_2]$, with $a_2 = \frac{1}{2}(a_1 + b_1)$ and $b_2 = b_1$ and $a_1 \le a_2 < b_2 \le b_1$.
    Also put $n_1 = \inf(\rho_1)$ and $\mathbb{N}_2 = \{ n \in \mathbb{N}_1: n > n_1\}$.
• Now bisect $\mathbb{J}_2$: $\mathbb{J}_2 = \mathbb{L}_2 \cup \mathbb{R}_2$, where $\mathbb{L}_2 = \left[a_2, \frac{a_2 + b_2}{2}\right]$ and $\mathbb{R}_2 = \left[ \frac{a_2 + b_2}{2}, b_2\right]$.
  Then define the sets $\lambda_2 = \{ n \in \mathbb{N}_2: x_n \in \mathbb{L}_2\}$ and $\rho_2 = \{ n \in \mathbb{N}_2: x_n \in \mathbb{R}_2\}$. Then $\lambda_2 \cup \rho_2 = \mathbb{N}_2$, which is an infinite set, so at least one of the sets $\lambda_2$ and $\rho_2$ is infinite.
  • If $\lambda_2$ is infinite, put $\mathbb{J}_3 = \mathbb{L}_2 = [a_3, b_3]$, with $a_3 = a_2$ and $b_3 = \frac{a_2 + b_2}{2}$ and $a_2 \le a_3 < b_3 \le b_2$.
    Also put $n_2 = \inf(\lambda_2)$ and $\mathbb{N}_3 = \{ n \in \mathbb{N}_2: n > n_2\}$.
  • If $\lambda_2$ is finite or empty, put $\mathbb{J}_3 = \mathbb{R}_2 = [a_3, b_3]$, with $a_3 = \frac{1}{2}(a_2 + b_2)$ and $b_3 = b_2$ and $a_2 \le a_3 < b_3 \le b_2$.
    Also put $n_2 = \inf(\rho_2)$ and $\mathbb{N}_3 = \{ n \in \mathbb{N}_1: n > n_2\}$.

We may continue this process for ever, producing a nested sequence of intervals $\mathbb{J}_n = [a_n, b_n]$, for $n \in \mathbb{N}$, such that each interval $\mathbb{J}_n$ contains an infinite number of elements of $\mathbb{X}$. At the same time, we produce a subsequence $\mathbb{Y} = \{ x_{n_k}: k \in \mathbb{N}\}$ of $\mathbb{X}$, such that $a_k \le x_{n_k} \le b_k$, for all $k \in \mathbb{N}$.
Note that the length of $\mathbb{J}_n = \frac{1}{2^{n -1}} [b_1 - a_1]$, for each $n \in \mathbb{N}$, which has limit zero, as $n$ goes to infinity. So by the theory of nested intervals, we have $\mathbb{J} = \bigcap_{n = 1}^\infty \mathbb{J}_n = \{\alpha\}$, where $\alpha = \lim_{k\rightarrow \infty} a_k = \lim_{k\rightarrow \infty} b_k$.
So by squeeze applied to the inequality $a_k \le x_{n_k} \le b_k$, for all $k \in \mathbb{N}$, we see that $\mathbb{Y}$ converges with limit $\alpha$ and we are done: the sequence $\mathbb{X}$ has a convergent subsequence, proving Bolzano-Weierstrass again.