A question on a proof that every sequence has a monotone subsequence

Consider the following proof that every sequence $$\{x_n\}_n$$ in $$\mathbb R$$ has a monotone subsequence.

Proof: Let us call a positive integer $$n$$ a peak of the sequence if $$m > n \implies x_n > x_m$$  i.e., if  $$x_n$$ is greater than every subsequent term in the sequence.

Suppose first that the sequence has infinitely many peaks, $$n_1 < n_2 < n_3 < … < n_j < …$$. Then the subsequence $$\{x_{n_j}\}_j$$  corresponding to these peaks is monotonically decreasing, and we are done.

So suppose now that there are only finitely many peaks, let $$N$$ be the last peak and set $$n_1 = N + 1$$.

Then $$n_1$$ is not a peak, since $$n_1 > N$$, which implies the existence of an $$n_2 > n_1$$ with $$x_{n_2} \geq x_{n_1}.$$  Again, as $$n_2 > N$$ it is not a peak, hence there is $$n_3 > n_2$$ with $$x_{n_3} \geq x_{n_2}.$$  Repeating this process leads to an infinite non-decreasing subsequence $$x_{n_1} \leq x_{n_2} \leq x_{n_3} \leq \ldots$$ as desired.

In the second case, if $$n_1$$ is not a peak, how does this imply the existence of an $$n_2 > n_1$$ with $$x_{n_2} \geq x_{n_1}$$? Can't it be possible that there does not exist any $$n_2 > n_1$$ such that $$x_{n_2} \geq x_{n_1}$$?

A possible example can be the sequence $$\{\sin n\}_n$$, taking $$N$$ to be the closest integer to $$\pi/2$$

• that is by assumption ($n_1$ not a peak) and definition. Just evaluate the statement $n_1$ is not a peak (negation of $n_1$ is a peak). Commented Sep 12, 2014 at 6:15
• The integer closest to π/2 is not a peak for {sin n}, sin 2 < sin 8. I am not conviced that this sequence has any peaks - ie. I think sin n, with integer n, can approximate 1 arbitrary well. Commented Sep 12, 2014 at 11:04

If you have a statement "for all $$x$$, $$P(x)$$ is true", then the negation of this statement is "there exists an $$x$$ such that $$P(x)$$ is not true". (the negation of $$\forall x: P(x)$$ is $$\exists x: \neg P(x)$$).

$$n_1$$ is not a peak. The definition of $$n_1$$ being a peak is:

$$\forall \,n> n_1: x_{n_1}>x_n$$ meaning that by definition, $$n_1$$ is not a peak iff $$\exists \, n > n_1: x_n\leq x_{n_1}$$ which is exactly what you have.

Here is a tedious proof that avoids dealing with peaks:

Let $\bar{x} = \limsup_n x_n$.

If $\bar{x} = \infty$, then let $n_1 = 1$, and $n_{k+1} = \min \{n | n \ge n_k+1,\ x_n \ge x_{n_k} +1 \}$, then $x_{n_k}$ is a monotone sequence.

Otherwise, suppose $\bar{x} < \infty$.

Suppose $\{x_n\} \cap (\bar{x},\infty)$ contains an infinite subset. Let $x_{n_k}$ be the subsequence of $x_n$ that lies in $(\bar{x},\infty)$. Then $x_{n_k} > \bar{x}$, and $\lim_k x_{n_k} = \bar{x}$. Let $m_1 = n_{1}$, and $m_{k+1} = \min \{n_j | n_j \ge m_k+1,\ x_{n_j} < x_{m_k} \}$, then $x_{m_k}$ is a monotone sequence.

Now suppose $\{x_n\} \cap (\bar{x},\infty)$ is finite.

Suppose $\{x_n\} \cap \{\bar{x}\}$ contains an infinite subset, then clearly this subsequence is a monotone (in fact, constant) subsequence.

Now suppose $\{x_n\} \cap [\bar{x},\infty)$ is finite. Then $x_n < \bar{x}$ (after a finite number of terms), and there exists a subsequence $x_{n_k}$ such that $\lim_k x_{n_k} = \bar{x}$. Similar to above, let $m_1 = n_1$, and $m_{k+1} = \min \{n_j | n_j \ge m_k+1,\ x_{n_j} > x_{m_k} \}$, then $x_{m_k}$ is a monotone sequence.