Question regarding a sequence and a monotone subsequence Let $x_n$ be a sequence and $x_0$ a number. How can I show that $x_n$ --> $x_0$ if and only if ${x_n}_k$ --> $x_0$ for every monotone subsequence ${x_n}_k$? Any hints or solutions welcome.
 A: If $x_n$ does not converge to $x_0$ then there is an $\epsilon>0$ and a subsequence $x_{n_k}$ such that $|x_{n_k}-x_0|\ge\epsilon$ for all $k$. In particular, no subsequence of $x_{n_k}$ can converge to $x_0$ either.
Now, note that a subsequence of a subsequence is again a subsequence, and argue abstractly that any sequence contains a monotone subsequence. 
The proof of the latter is somewhat non-trivial. It can be seen as a consequence of Ramsey's theorem; Given a sequence $y_1,y_2,\dots$, define a two-coloring of the two-sized subsets of $\mathbb N$ as follows: Given $i<j$, color $\{i,j\}$ red iff $y_i<y_j$ and blue otherwise. Ramsey's theorem ensures that there is an infinite monochromatic set. The corresponding subsequence is increasing if the color is red, and decreasing otherwise.
(Some analysis books include a proof that any sequence contains a monotone subsequence. Typically, the argument avoids mentioning Ramsey's theorem, but the proof tends to be very close to the usual proof of the theorem anyway.)
A: First, it's confusing to denote the limit $x_0$. My the sequence will be $x_0, x_1, x_2, \ldots$ and $A$ will be the limit.
The $\Longrightarrow$ part is easy. If $x_{n_k}$ is any subsequence of $x_n$, then for all $\varepsilon>0$ there is $N\in\mathbb N$ such that $\underset{n\geq N}\forall\ |x_n-A|<\varepsilon$ which implies $\underset{k\geq N}\forall\ |x_{n_k}-A|<\varepsilon$, because $n_k\geq k$. This means $x_{n_k}\to A$.
The $\Longleftarrow$ is a little harder, if $x_n\not\to A$, then there exists $\varepsilon>0$ such that for all $k\in\mathbb N$ we have $\underset{n_k\geq k}\exists\ |x_{n_k}-A|\geq\varepsilon$. It's obvious we can choose each $n_k$ so that $n_{k+1}>n_k$, which means there's a subsequence $x_{n_k}\not\to A$. If this subsequence is monotone, we have a contradiction. So the only thing to prove is that from any sequence we can choose a monotone subsequence.
Let's do it. Suppose we have a sequence $a_n$ of real numbers. Ask the following question:
$$\text{Is there }n\in\mathbb N\text{ such that }\{k\in\mathbb N|k>n\land a_k\geq a_n\}\text{ is infinite?}\tag Q$$
Now suppose it's true, let $n_0$ be the $n$ from $(Q)$ and throw away any elements of $a_n$ which are less than $a_{n_0}$ (we can do this because there's still infinitely many left). Ask again, but this time we want $n$ such that $n>n_0$, if it's true again let it be $n_1$ and throw away elements which are less than $x_{n_1}$.
If $(Q)$ is always true for $n\geq n_k$ and what's left of the sequence, we get a subsequence $x_{n_k}$ which is nondecreasing by the construction and we are done.
But if this construction fails, it means we have a sequence such that for any $n\in\mathbb N$ the set $\{k\in\mathbb N|k>n\land a_k\geq a_n\}$ is finite. Which means there's only finitely many elements with value higher or equal to any element we choose, so there has to be a decreasing subsequence. $\square$
A: The latter is really the hardest part. Suppose to the contrary that $x_n \not \to x_0$. Thus there is a $\varepsilon>0$ such that for all $N\ge 0$ there is a $n\ge N$ for which $|x_n-x_0|>\varepsilon$. Define 
$$E=\{n\in \mathbb{N}:|x_n-x_0|>\varepsilon\} $$
We must have $E$ infinite  since otherwise this would imply that $x_n$ is $\varepsilon$-close to $x_0$.  Also there exists strict ordered preserving map $f: \mathbb{N} \to \mathbb{E}$ (just take the minimum), $f_0<f_1 \ldots <f_k< \ldots$ In particular we have 
$$|x_{f_n}-x_0|>\varepsilon \text{ for all } n \in \mathbb{N} \tag{1}$$
Thus $x_{f_n}$ is a subsequence of $x_n$. 

Claim 1: Any sequence contain a monotone subsequence.

Proof: Let call $n\in \mathbb{N}$ "nice" if $a_n >a_m$ for all $m> n$. 
(1) Suppose that $(a_n)$ contain infinitely many "nice" points. In this case if $n_1<n_2<\ldots<n_i< \ldots$ are the "nice" points, we have $a_{n_1}>a_{n_2}> \ldots>a_{n_i}> \ldots$, then $(a_{n_i})$ is a decreasing subsequence.
(2) The sequence contains finitely many "nice" points. Let $n_1$ be greater that all the "nice" points. Since $n_1$ is not "nice" there is a  $n_2>n_1$ such that $a_{n_2}\ge a_{n_1}$. Since $n_2$ is also not "nice", is greater than $n_1$ and for instance greater than all the "nice" points, there is a point $n_3>n_2$ such that $a_{n_3}\ge a_{n_2}$. Continuous in this fashion we obtain a non-decreasing subsequence $(a_{n_i})$ $\square$
By the above claim there is a monotone subsequence of $x_{f_n}$. Let $x_{{f_n}_k}$ be such a subsequence, note that is a subsequence of the original sequence (why?), then converges to $x_0$ by hypothesis. But this contradicts $(1)$. From this contradiction we conclude that $x_n \to x_0$.
