According to Bolzano Weierstrass Theorem,
Every bounded sequence has a convergent subsequence.
And I saw the proof where if lets say we have this sequence bounded from [-M, M], you just kind of divide this interval in halves infinitely many times and so this interval just gets smaller and smaller so the numbers kind of converge to this little interval.
I kind of get the proof but then how can we just assume that the sequence is monotonic? As in the sequence could be random right? It could be 1, 6, -4, 8, and just other random number. And I come across somewhere that subsequences has to stay in the same order as the original sequence. However, in the proof of Bolzano Weierstrass Theorem, we kind of blindly assume that the sequence is monotonic, starting from -M to M or vice versa.
I know I must be wrong, but where am I wrong? I hope I am not as confusing as I am confused.
Best Answer
There are a variety of methods for proving the Bolzano-Weierstrass theorem.
One (such as the one given on wikipedia) relies on extracting a monotone subsequence.
Another, like the one you are reading I suspect, relies on the nested interval theorem: Given any nested sequence of closed bounded intervals $I_0 \supset I_1 \supset I_2 \supset \cdots$ there exists a point in the intersection $\cap_{k=0}^\infty I_k$.
A sketch of the rest of the proof: take a point (by the nested interval theorem) in the intersection of all the intervals you're considering. Then show that this point is in fact the limit of the subsequence, since the length of the intervals is going to zero.
I'll give some more details. The proof is as follows:
Let $M$ be an upper bound on the absolute values of the terms in your sequence. Let $I_0 = [-M,M]$. Let $a_0$ be the first term in your sequence. Note that infinitely many terms in the sequence are in $I_0$ (in fact they all are).
We inductively construct a subsequence. Given $I_k$ such that infinitely many terms in the sequence are in $I_k$, let $I_{k+1}$ be the closed left half of $I_k$ if there are infinitely many terms in the sequence in the closed left half. Otherwise, let $I_{k+1}$ be the closed right half of $I_k$ (necessarily with infinitely many terms). Let $a_{k+1}$ be the smallest term in your sequence which is both in $I_{k+1}$ and not already used.
Lemma: given $x \in I_k$, we have, for $j \geq k$ that $|x - a_j| \leq \frac{M}{2^k}$
Let $y \in \cap_{k=0}^\infty I_k$, which exists by the nested interval theorem.
For $j \geq k$, we have $|y - a_j| \leq \frac{M}{2^k}$ by the lemma, since $y \in I_k$. Thus the subsequence we have constructed converges to $y$.
One proof of the nested interval theorem: The left endpoints of the intervals form a monotone sequence. The limit of this sequence is in every one of the intervals.
While it's a slightly longer proof than the monotone subsequence proof, I find it highly intuitive, and the nice thing about this proof is that it generalizes well to higher dimensions.