What does the bolded part in the proof of the Bolzano-Weierstrass theorem mean?

[_Andreas]

According to the Bolzano-Weierstrass theorem, a bounded sequence has a convergent subsequence. My problem is with the proof. Either I've got a bad textbook, or my reading comprehension is lacking. This is how it's formulated:

Let x1, x2, ... be a bounded sequence. Let E be the set of all numbers in the sequence. The set E is clearly bounded. The set E is either finite or infinite. If E is finite there exists a number that is repeated an infinite amount of times in the sequence x1, x2, ... . This means that there is a sequence of positive integers n1 < n2 < ... such that xn1 = xn2 ... . Therefore xn1, xn2, ... is a convergent subsequence to xn.

For starters, I need to know what the bolded part means. If the sequence x1, x2, ... is 0,1,2,3,4,0,1,2,3,4,0,1,2,3,4, ... , is E={0,1,2,3,4}, or E={0,1,2,3,4,0,1,2,3,4,0,1,2,3,4, ... }?

 

[AKG]

According to the Bolzano-Weierstrass theorem, a bounded sequence has a convergent subsequence. My problem is with the proof. Either I've got a bad textbook, or my reading comprehension is lacking. This is how it's formulated:

Let x1, x2, ... be a bounded sequence. Let E be the set of all numbers in the sequence. The set E is clearly bounded. The set E is either finite or infinite. If E is finite there exists a number that is repeated an infinite amount of times in the sequence x1, x2, ... . This means that there is a sequence of positive integers n1 < n2 < ... such that xn1 = xn2 ... . Therefore xn1, xn2, ... is a convergent subsequence to xn.

For starters, I need to know what the bolded part means. If the sequence x1, x2, ... is 0,1,2,3,4,0,1,2,3,4,0,1,2,3,4, ... , is E={0,1,2,3,4}, or E={0,1,2,3,4,0,1,2,3,4,0,1,2,3,4, ... }?

It's both. {0,1,2,3,4} = {0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,...}. In this instance, it's most useful to think of it as {0,1,2,3,4}.

 

[_Andreas]

It's both. {0,1,2,3,4} = {0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,...}. In this instance, it's most useful to think of it as {0,1,2,3,4}.

Ok, thanks. This set is then finite, right? And if the sequence x1, x2, ... had instead been 0,1,2,3,4,5,6, ... E would've been infinite but bounded (with a lower bound of 0), right?

I'd like to take a look at the proof again:

Let x1, x2, ... be a bounded sequence. Let E be the set of all numbers in the sequence. The set E is clearly bounded. The set E is either finite or infinite. If E is finite there exists a number that is repeated an infinite amount of times in the sequence x1, x2, ... . This means that there is a sequence of positive integers n1 < n2 < ... such that xn1 = xn2 ... . Therefore xn1, xn2, ... is a convergent subsequence to xn.

So if, to use my previous example, E={0,1,2,3,4}, we know that the sequence x1, x2, ... is 0,1,2,3,4,0,1,2,3,4, ... ? And then we could form a subsequence of xn from the subsequences xn1= xn2= xnk= 0, which is 0,0,0,0, ...? And this sequence would then be convergent (lim 0 = 0 when k goes to infinity)?

Many questions at once, I know :shy:

 

[HallsofIvy]

Ok, thanks. This set is then finite, right?

Yes, that's correct.

And if the sequence x1, x2, ... had instead been 0,1,2,3,4,5,6, ... E would've been infinite but bounded (with a lower bound of 0), right?

No, that sequence is not bounded! "Bounded" means having both lower and upper bounds. A bounded sequence might be something like
{(-1)^n\frac{n-1}{n}

I'd like to take a look at the proof again:

Let x1, x2, ... be a bounded sequence. Let E be the set of all numbers in the sequence. The set E is clearly bounded. The set E is either finite or infinite. If E is finite there exists a number that is repeated an infinite amount of times in the sequence x1, x2, ... . This means that there is a sequence of positive integers n1 < n2 < ... such that xn1 = xn2 ... . Therefore xn1, xn2, ... is a convergent subsequence to xn.

So if, to use my previous example, E={0,1,2,3,4}, we know that the sequence x1, x2, ... is 0,1,2,3,4,0,1,2,3,4, ... ?

No, we don't know that! If all we know is that E= {0,1,2,3,4}, the sequence could be {0,1,2,3,4,4,4,4,...} or {3, 1, 4, 2, 4, 2, 3, 1, 3, 2, 4...}, or any sequence that contains only those 5 numbers. The point is that since a sequence contains an infinite number of terms, and there are only a finite number of possible terms, at least one of them must be repeated infinitely.

And then we could form a subsequence of xn from the subsequences xn1= xn2= xnk= 0, which is 0,0,0,0, ...? And this sequence would then be convergent (lim 0 = 0 when k goes to infinity)?

Many questions at once, I know :shy:

 

[HallsofIvy]

I notice you didn't include the "if E is infinite part". I'm sure that's the hard part. I am also sure that it includes using "monotone convergence" or the "least upper bound property" since Bolzano-Weierstrass is equivalent to those. (Since this proof immediately converts the sequence to a set, I suspect "least upper bound property".)

Here's a completely different proof that uses monotone convergence:

Lemma: Every sequence contains a monotone sequence.
Let {a_n} be a sequence of real numbers and let S be the set of all indices i such that if j> i then a_j&gt; a_i. That is, i is in S if and only if a_i is smaller than all succeeding terms in the sequence. Of course, if the sequence is increasing S is just all positive integers. On the other hand, if the sequence is decreasing, S is empty. And, of course, you can imagine sequences where S is some positive integers but not all.

Case 1: S is infinite. Then we are done! The sequence {a_n}_{n \epsilon S} is a strictly increasing sequence.

Case 2: S is either empty or finite. In either case, there exist i_1 larger than anything is S. Since i_1 itself is not in S, there must exist i_2&gt; i_1 such that a_{i_2}\le a_{i_1}. Since i_2&gt; i_1 and i_1 is larger than any member of S, i_2 is also not in S. That means there exist i_3 such that a_{i+3}\le a_{i_2}. Continuing in that way, we get a (non-strictly) decreasing subsequence.

Theorem: Every bounded sequence contains a convergent subsequence.
Let {a_i} be a bounded sequence. By the lemma, {a_i} has a monotone subsequence, {a_i}_{i\epsilon S} for some set of positive integers S. Since {a_i} is bounded, it has both upper and lower bounds. By "monotone convergence", then, whether that subsequence is increasing or decreasing it converges.

 

[_Andreas]

No, that sequence is not bounded! "Bounded" means having both lower and upper bounds. A bounded sequence might be something like
{(-1)^n\frac{n-1}{n}

Ok, so it's infinite, but not bounded?

No, we don't know that! If all we know is that E= {0,1,2,3,4}, the sequence could be {0,1,2,3,4,4,4,4,...} or {3, 1, 4, 2, 4, 2, 3, 1, 3, 2, 4...}, or any sequence that contains only those 5 numbers. The point is that since a sequence contains an infinite number of terms, and there are only a finite number of possible terms, at least one of them must be repeated infinitely.

Makes a lot of sense. Thanks!

And then we could form a subsequence of xn from the subsequences xn1= xn2= xnk= 0, which is 0,0,0,0, ...? And this sequence would then be convergent (lim 0 = 0 when k goes to infinity)?

Is it correct that a subsequence can contain only one element, i.e. is the above correct?

 

[_Andreas]

I notice you didn't include the "if E is infinite part". I'm sure that's the hard part.

Actually, I have some difficulties trying to conceptualize an infinite but bounded E. What could such a set look like?

I am also sure that it includes using "monotone convergence" or the "least upper bound property" since Bolzano-Weierstrass is equivalent to those. (Since this proof immediately converts the sequence to a set, I suspect "least upper bound property".)

Here's a completely different proof that uses monotone convergence:

Lemma: Every sequence contains a monotone sequence.
Let {a_n} be a sequence of real numbers and let S be the set of all indices i such that if j> i then a_j&gt; a_i. That is, i is in S if and only if a_i is smaller than all succeeding terms in the sequence. Of course, if the sequence is increasing S is just all positive integers. On the other hand, if the sequence is decreasing, S is empty. And, of course, you can imagine sequences where S is some positive integers but not all.

Case 1: S is infinite. Then we are done! The sequence {a_n}_{n \epsilon S} is a strictly increasing sequence.

Case 2: S is either empty or finite. In either case, there exist i_1 larger than anything is S. Since i_1 itself is not in S, there must exist i_2&gt; i_1 such that a_{i_2}\le a_{i_1}. Since i_2&gt; i_1 and i_1 is larger than any member of S, i_2 is also not in S. That means there exist i_3 such that a_{i+3}\le a_{i_2}. Continuing in that way, we get a (non-strictly) decreasing subsequence.

Theorem: Every bounded sequence contains a convergent subsequence.
Let {a_i} be a bounded sequence. By the lemma, {a_i} has a monotone subsequence, {a_i}_{i\epsilon S} for some set of positive integers S. Since {a_i} is bounded, it has both upper and lower bounds. By "monotone convergence", then, whether that subsequence is increasing or decreasing it converges.

Thanks again! However, isn't a sequence monotone if aj>=ai for all succeeding aj:s, and strictly monotone if aj>ai for all aj:s?

 

[HallsofIvy]

Actually, I have some difficulties trying to conceptualize an infinite but bounded E. What could such a set look like?k

"Infinite" just means the set contains an infinite number of points. The interval (0, 1) is bounded but has an infinite number of points. for that matter, the interval (0, 0.00000000000001) is very bounded but contains an infinite number of points!

Thanks again! However, isn't a sequence monotone if aj>=ai for all succeeding aj:s, and strictly monotone if aj>ai for all aj:s?

Yes, that was why I made the point that if the set S defined above was infinite, then the sequence [/itex]\{a_n\} for n\epsilon S[/itex] is strictly increasing while if S is not infinite, then the sequence produced is non-strictly decreasing. Either one is monotonic. (Actually, what you wrote isn't quite right- the two sequences you give are strictly increasing and non-strictly increasing. A monotone sequence may be decreasing also but I think that was what you really meant.

 

[_Andreas]

Ok, thanks HallsofIvy! I think I have a much better understanding of this now.