Help me understand the proof for Bolzano-Weierstrass Theorem!

The proof is from the book Advanced Calculus: An Introduction to Linear Analysis by Leonard F. Richardson

Theorem (Bolzano-Weierstrass): Let $x_n$ be any bounded sequence of real numbers, so that there exists $M \in \mathbb{R}$ such that $|x_n|\leq M$ for all $n$. Then there exists a convergent subsequence $x_{n_k}$ of $x_n$. That is, there exists a subsequence $x_{n_k}$ that converges to some $L \in [-M,M]$.

Proof: We will use the method of interval-halving introduced previously to prove the existence of least upper bounds. Let $a_1=-M$ and $b_1=M$. So $x_n \in [a_1,b_1]$, for all $n \in \mathbb{N}$. Let $x_{n_1}=x_1$. Now divide $[a_1,b_1]$ in half using $\frac{a_1+b_1}{2}=0$.

i. If there exist $\infty$-many values of $n$ such that $x_n \in [a_1,0]$, then let $a_2=a_1$ and $b_2=0$.

ii. But if there do not exist $\infty$-many such terms in $[a_1,0]$, then there exist $\infty$-many such terms in $[0,b_1]$. In that case, let $a_2=0$ and $b_2=b_1$.

Now, since there exist $\infty$-many terms of $x_n$ in $[a_2,b_2]$, pick any $n_2>n_1$ such that $x_{n_2} \in [a_2,b_2]$ in half and pick one of the halves $[a_3,b_3]$ having $\infty$-many terms of $x_n$ in it. Then pick $n_3>n_2$ such that $x_{n_3} \in [a_3,b_3]$. Observe that $$|b_k-a_k|=\frac{2M}{2^{k-1}} \rightarrow 0$$

as $k \rightarrow \infty$. So if $\epsilon > 0$, there exists $K$ such that $k \geq K$ implies $|b_k-a_k|< \epsilon$. Thus if $j$ and $k \geq K$, we have $|x_{n_j}-x_{n_k}|<\epsilon$ as well. Hence, $x_{n_k}$ is a Cauchy sequence and must converge. Since $[-M,M]$ is a closed interval, we know from a previous exercise that $x_{n_k} \rightarrow L$ as $k\rightarrow \infty$ for some $L \in [-M,M]$. $\blacksquare$

I boxed the part I didn't understand. I don't understand how we know which interval has $\infty$-many values of n for $x_n$ to be in that interval. Take $(-1)^n$ for example, I feel like both intervals $[-1,0]$ and $[0,1]$ have $\infty$-many values of $n$ such that $x_n$ are in the intervals, i.e., $1 \in [0,1]$ and $-1 \in [-1,0]$. Aren't both even numbers and odd numbers of $n$ be infinitely many in $\mathbb{N}$? Since $\mathbb{N}$ is $\infty$-many, how can we extract one set with $\infty$-many and another with finitely many numbers? I just can't convince myself to accept this part.

• At least one interval between $[a_1,0]$ and $[0, b_1]$ has infinitely many $x_n$. He always try $[a_1,0]$ first. If $[a_1,0]$ doesn't have infinitely many, then he takes $[0,b_1]$ instead. I mean, if both has infinitely many, he takes $[a_1,0]$. – positrón0802 Jan 19 '17 at 19:55
• Your brain does a very good job of checking the details. I know because otherwise you wouldn't have thought to ask this question. So good job. Now, to answer your question, as others have said (and you have said yourself), it's entirely possible that both intervals have infinitely many elements from the sequence in them. If that's the case, you can pick either one and move on to the next step. Since you can choose either one in this case, why not always just choose the left hand one? It doesn't matter, but it's a neater proof to say "choose the left hand one." – layman Jan 19 '17 at 20:06
• Does that mean this proof only proves that there is only one subsequence that is convergent? If I choose to only pick one particular interval over the other regardless the other interval having infinitely many $n$, wouldn't that disregard that there will be a convergent sequence in the other interval, too? Thank you for the comments! – user3000482 Jan 19 '17 at 20:09
• @user3000482 The statement of the theorem asserts the existence of a convergent subsequence. To show existence, you just have to show you can find one. Finding more than one, although it might be possible, would be superfluous/redundant/extra. – layman Jan 19 '17 at 20:16

The proof doesn't assume that one of the half-intervals has infinitely many terms while the other has finitely many terms; it only says that at least one of the halves has infinitely many terms, and one can be chosen arbitrarily. In fact, if $[a_n,\frac{a_n+b_n}{2}]$ and $[\frac{a_n+b_n}{2},b_n]$ both have infinitely many terms, the process used in the proof may be applied to both intervals, and thus there are at least two subsequences converging to different values. This is the case for your example of $(-1)^n$, since there are subsequences converging to both $1$ and $-1$.
• Thanks it makes sense now! But now I think any interval can have infinitely many n to make $x_n$ in the interval, i.e., there are infinitely many intervals we can make this true because $\mathbb{N}$ is infinite. – user3000482 Jan 19 '17 at 20:12
• If a sequence $x_n$ has any real value between $[-1,1]$, then is it true I can make any subsequence to converge to any real number in the interval $[-1,1]$? – user3000482 Jan 19 '17 at 20:16
• There is no sequence $x_n$ which attains every real value between $[-1,1]$. If there were, then $[-1,1]$ would be countable. – Michael M Jan 19 '17 at 20:21
• However, it is possible for a sequence $x_n$ to satisfy the property that for all $y\in [-1,1]$, there is a subsequence converging to $y$. For example, let $x_n$ be an enumeration of $\mathbb Q\cap [-1,1]$; then this property holds since $\mathbb Q\cap [-1,1]$ is dense in $[-1,1]$. – Michael M Jan 19 '17 at 20:24