Show that every sequence in $\mathbb{R}$ has a monotone subsequence So I would like some hints as to how to proceed on this problem as I am stuck with a particular case. I divided this proof up into 2 cases, where the sequence is convergent and the sequence is divergent.I am somewhat confident that I have shown this for the case where the sequence is convergent, and I am currently stumped on the case for divergent sequences.
My intuition tells me that because the sequence is divergent, I can pick some $p\in \mathbb{R}$ and consider the subsequence of points which move farther and farther away from $p$, and that will give me my monotone subsequence. But in negating the definition of convergence I am only guaranteed that there exists some $\epsilon>0$ such that for any $N\in \mathbb{N}$, there exists an $n>N$ such that $|x_n-p|\geq \epsilon$, so these point can fluctuate between being exactly within $\epsilon$ of $p$ or more than $\epsilon$, and I don't have enough info about the behavior of the sequence to assure myself of a monotone subsequence.
So how can I proceed from here (assuming that I am on the right track)? Or is there a better route that I can take which does not involve a proof split into cases?
Thank you.
 A: if any value has infinite support we are done. otherwise there is an infinite subsequence of positive (or negative) terms $r_j (-r_j)$.
if the sequence is unbounded, we are done.
otherwise by the Heine-Borel theorem there is an accumulation point $a$. remove any terms equal to $a$ and after this reduction let $r^+$ and $r^-$ denote the subsequences of terms $\gt a$ and $\lt a$ respectively. at least one must be infinite. suppose this is $r^+$
set $k_1=1$ since $r^+_{k_1} \gt a$ we can find $r^+_{k_2} \in (a,r^+_{k_1})$
the subsequence $r^+_{k_n}$ is monotonic decreasing
A: You don't need to divide this into divergent/convergent sequences. Maybe this hint will already do:
For the sequence $(a_n)_{n\in\mathbb N}$ we call $k\in\mathbb N$ a spike of the sequence, if $a_k\geq a_n$ for all $n\geq k$. Now think about what happens if there are infinte many spikes? What if there are only finite many spikes?
A: Can you consider three cases? 
First, when it is not bounded from above. Then consider the subsequence defined as follows: $n_1=1$ and $n_k$ is the smallest number such that 
$$a_{n_k} >  a_{n_1}, \ldots ,a_{n_{k-1}}$$
Second, when it is not bounded from below, similarly,  $n_k$ is the smallest number such that 
$$a_{n_k} < a_{n_1}, \ldots ,a_{n_{k-1}}$$
Third, when it is bounded from above and below, so has a convergent subsequence with limit $a$. Let us consider only the subcase when infinitely many terms of that subsequence are $>a$. Now get a subsequence of that that decreasingly converges to $a$ similarly to the case above.
${\bf Added:}$ It is hard to improve on the lovely solution of @Hirshy:
But since in the comments the infinite Ramsey theorem let's sketch a proof using this: 
Let $I$, $J$ be totally ordered sets, with $I$ infinite and $\phi\colon I \to J$ any map. Then there exists $I_0 \subset I$ infinite so that $\phi_{\mid I_0}$ is either constant, or strictly increasing, or strictly decreasing. Indeed, color the subsets with $2$ elements $\{i,j\}$ of $I$, $i< j$, with R if $\phi(i) < \phi(j)$, B if $\phi(i)= \phi(j)$, and G if $\phi(i) > \phi(j)$. By Ramsey, there exists $I_0 \subset I$ so that all the subsets of $I$ have the same color.
Since we are talking about Ramsey theorem, we also have a finite version of it, that could be applied to the finite case of the problem. However, we have a direct result of Erdos et al stating: from a finite sequence of (distinct) real  $mn+1$ numbers one can extract an increasing subsequence of length $m+1$, or a decreasing subsequence of length $n+1$. 
A: Let $u=(u_n)$ be a sequence of real numbers. Let $[u]\in{}^{\ast}\mathbb{R}$ be the hyperreal number obtained as the equivalence class of the sequence $u$ in the ultrapower construction. We then exploit the order of ${}^{\ast}\mathbb{R}$ to construct a monotone subsequence as follows.
If $[u]$ is infinite, we construct a subsequence $u_{n_k}$ recursively by choosing $u_{n_{k+1}}$ always closer to $[u]$ than the previous term.  The subsequence will be increasing or decreasing depending on the sign of $[u]$.
If $[u]$ is a standard real number, then the subset of indices $n$ for which $[u]=u_n$ is infinite, and enumerating this subset of $\mathbb{N}$ we obtain the desired subsequence.
If $[u]$ is finite but nonstandard, we round it off to its nearest real $r$. Then we recursively choose $u_{n_{k+1}}$ closer to $r$ than the previous term $u_{n_{k}}$.  The subsequence will be increasing or decreasing depending on the sign of the infinitesimal $[u]-r$.
Such an approach is presented in this 2018 publication in Open Mathematics; see also arxiv.
