Monotone Subsequence Theorem

The Monotone Subsequence Theorem states that every $(a_n) \subset \mathbb{R}$ has a monotone subsequence. A sequence is said to be monotone if it is either increasing or decreasing.

Let’s prove the Monotone Subsequence Theorem:

Suppose a sequence $A = \{ i \in \mathbb{N} | a_i > a_{j} \forall i,j \in \mathbb{N} \text{ with } i < j \}$

If $A$ is a countable set, then be $n_1 = min(A)$ and $n_2 = min(A \setminus \{n_1\})$. We can continue this way to get a subsequence $a_{n_1}, a_{n_2}, a_{n_3}, ...$ that is strictly decreasing as $a_{n_1} > a_{n_2} > a_{n_3} > ...$.

If $A$ is a finite set, then be $n_1 = min(\mathbb{N} \setminus A)$, then exists $n_2 > n_1$ such that $a_{n_2} > a_{n_1}$. We can continue this way to get so $a_{n_1} < a_{n_2} < a_{n_3} < ... < a_{n_k} > ...$. So, the sequence $\{a_{n_1}, a_{n_2}, a_{n_3}, ..., a_{n_k} \}$ is a strictly increasing subsequence.

Therefore, every real sequence has a monotone subsequence.