Need help to understand a lemma

I need help with understanding Lemma,

Lemma: For every sequence (a_{n}) 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

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.

Re: Need help to understand a lemma

Quote:

Originally Posted by

**davidciprut** Lemma: For every sequence (a_{n}) in *R* it has monotonic subsequence.

Here is the classic proof.

Let $\displaystyle \mathcal{S}=\{K: (\forall j>K)[a_j>a_K]\}$.

Note that $\displaystyle n\in\mathcal{S}\text{ iff }\forall j>n\to~a_j>a_n$ and $\displaystyle n\notin\mathcal{S}\text{ iff }\exists k>n \to a_k\le a_n$.

There are two cases:

1) $\displaystyle \mathcal{S}$ can be infinite, in which case there is an increasing subsequence.

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