# Need help to understand a lemma

• Dec 8th 2013, 03:36 AM
davidciprut
Need help to understand a lemma
I need help with understanding Lemma,

Lemma: For every sequence (an) in R it has monotonic subsequence.

Firstly, why is this Lemma true?I mean you can have a sequence in R that is monotonically increasing, but I can't find a subsequence that is monotonically decreasing. I can find a subsequence that is monotonic in the same direction but not other directions.. ( By direction I mean increasing and decreasing)

I think I didn't understand the Lemma can someone explain? Thanks

• Dec 8th 2013, 08:19 AM
romsek
Re: Need help to understand a lemma
It doesn't say you need both directions. It just says you need a monotonic subsequence. Clearly if you have a monotonic increasing sequence it's not going to have a monotonic decreasing subsequence and vice versa.
• Dec 8th 2013, 08:46 AM
Plato
Re: Need help to understand a lemma
Quote:

Originally Posted by davidciprut
Lemma: For every sequence (an) in R it has monotonic subsequence.

Here is the classic proof.
Let $\mathcal{S}=\{K: (\forall j>K)[a_j>a_K]\}$.
Note that $n\in\mathcal{S}\text{ iff }\forall j>n\to~a_j>a_n$ and $n\notin\mathcal{S}\text{ iff }\exists k>n \to a_k\le a_n$.

There are two cases:
1) $\mathcal{S}$ can be infinite, in which case there is an increasing subsequence.

2) $\mathcal{S}$ can be finite, in which case there is an non-increasing subsequence.