# Sequences, Bolzano Weierstrass theorem

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.

• If it isn't monotonic, then there exists a subsequence of the original sequence that is monotonic. – Rustyn Nov 20 '14 at 22:36
• But then if theres a subsequence that is monotonic, then thats the end of the proof, isnt it? Because using the completeness axiom, it is deduced if a sequence is monotonic and bounded (as the original sequence is), then the sequence is convergent? Why bother doing the proof like above? – Skipe Nov 20 '14 at 22:41

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.

• Yeah, the one that my lecturer provided uses nested sequence intervals. What I dont get is how can you just divide the interval and immediately call it as your subsequence? I am sorry I am just very sketchy with the idea of sequences and subsequences. – Skipe Nov 20 '14 at 23:01
• But yeah. Just about the dividing part, after the dividing part I get it. – Skipe Nov 20 '14 at 23:02
• I've added details. Each time you subdivide the interval, you choose another term for your subsequence. It could be any term really --- all that matters is that it's your subinterval $I_k$ --- but for concreteness, take the first term that you haven't already used and which lies in $I_k$. – aes Nov 20 '14 at 23:04
• Thanks for the very detailed explanation, highly appreciate it! I think I kind of understand it now. True, I looked at the other proof using monotone subsequence using the two lemmas, and I think it is just so much easier to understand. – Skipe Nov 20 '14 at 23:09