# Converging subsequence

1. Oct 10, 2007

### _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, ... }?

2. Oct 10, 2007

### AKG

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}.

3. Oct 10, 2007

### _Andreas

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:

Last edited: Oct 10, 2007
4. Oct 11, 2007

### HallsofIvy

Staff Emeritus
Yes, that's correct.

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}$$

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.

5. Oct 11, 2007

### HallsofIvy

Staff Emeritus
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> 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> i_1$ such that $a_{i_2}\le a_{i_1}$. Since $i_2> 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.

6. Oct 11, 2007

### _Andreas

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

Makes a lot of sense. Thanks!

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

Last edited: Oct 11, 2007
7. Oct 11, 2007

### _Andreas

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

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?

Last edited: Oct 11, 2007
8. Oct 11, 2007

### HallsofIvy

Staff Emeritus
"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!

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.

9. Oct 11, 2007

### _Andreas

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