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$
 A: 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.
A: 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.
