# Show that every sequence in $\mathbb{R}$ has a monotone subsequence.

I am working on Real Mathematical Analysis by Pugh, page $125,$ exercise $11.$

Let $(x_n)$ be a sequence in $\mathbb{R}.$ Prove that $(x_n)$ has a monotone subsequence.

My attempt:

If $(x_n)$ is not bounded above, then for every $M>0,$ there exists $n_M\in\mathbb{N}$ such that $x_{n_M}>M.$ For $M=1,$ let $$n_1:=\min\{ n\in\mathbb{N}:x_n>1 \}.$$ For $M=2,$ let $$n_2:=\min\{ n\in\mathbb{N}:x_n>2 \}$$ with $n_2>n_1.$ In general, for any natural number $k,$ let $$n_k:=\min\{ n\in\mathbb{N}:x_n>k \}$$ and $n_k>n_{k-1}.$ Note that $n_k$ is well-defined as $(x_n)$ not bounded above implies that $\{n\in\mathbb{N}:x_n>k\}$ is non-empty and $\mathbb{N}$ is well-ordered.

We claim that $(x_{n_k})$ is an increasing subsequence of $(x_n).$ Subsequence is clear as $(n_k)$ is an increasing subsequence of $(n).$ If $x_{n_k}<x_{n_{k'}}$ for some $k'<k,$ then $x_{n_{k'}}>k,$ contradicts with monotonicity of $(n_k).$ In conclusion, $(x_n)$ has a monotone subsequence if it is not bounded above.

Similarly, if $(x_n)$ is not bounded below, by defining $$n_k:=\max\{ n\in\mathbb{N}: x_n<k \}$$ with $n_{k}>n_{k-1}$ for every natural number $k,$ one can obtain a monotone subsequence.

If the sequence $(x_n)$ is bounded, then for all natural number $n,$ define $$s_n:=\sup_{k\geq n}x_k \text{ and }l_n:=\inf_{k\geq n}x_k.$$ Since $(x_n)$ is bounded, both sets $\{ x_k:k\geq n \}$ and $\{ x_k:k\geq n \}$ are bounded as well. Therefore, $s_n$ and $l_n$ are well-defined for all $n\in\mathbb{N}.$ Clearly $(s_n)$ and $(l_n)$ are decreasing and increasing subsequences of $(x_n).$

Is there any mistake in my proof?

EDIT: As suggested by @Cave Johnson in comment, for bounded sequence $(x_n)$, consider $$s_n:=\sup_{k\leq n}x_k \text{ and }l_n:=\inf_{k\leq n}x_k.$$ Then $(s_n)$ and $(l_n)$ are monotone subsequences. DONE

• It is not always the case that $s_n$ and $l_n$ are even elements of the sequence. For example, if you take the sequence $\frac 1n$, then $l_n$ will always be zero which is not an element of $x_n$. – астон вілла олоф мэллбэрг Dec 13 '17 at 5:16
• I see. So I need to consider cases bounded above and bounded below separately? – Idonknow Dec 13 '17 at 5:18
• What you need to do is this : you are asked to show that there is either a monotone increasing subsequence, or a monotone decreasing subsequence. What this means, is that if there isn't a monotone decreasing sequence, then there must be a monotone increasing sequence. Now, prove this fact. You do not even need a bounded-unbounded case split now. – астон вілла олоф мэллбэрг Dec 13 '17 at 5:21
• @астонвіллаолофмэллбэрг: How to ensure that a sequence without monotone decreasing subsequence contains a monotone increasing subsequence? For example, the sequence $(\sin(n))$. – Idonknow Dec 13 '17 at 5:23
• Now you know that $\sup_{n\ge k}x_n$ and $\inf_{n\ge k}x_n$ are monotone, but not necessarily a subsequence. So why don't you consider $\sup_{n\le k}x_n$ and $\inf_{n\le k}x_n$ instead? – Cave Johnson Dec 13 '17 at 5:25

• Call a natural number $n$ "good" if $a_n > a_m$ for all $m > n$.
• If there are only finitely many such good points, then let $N$ be larger than all these finitely many numbers, and define $a_{n_1}:=a_N$ and $a_{n_k} := \min\{t \geq n_{k-1} : a_t \geq a_{n_{k-1}}\}$. This is well defined and gives an increasing subsequence.
Let $E=\{k:a_n \leq a_k$ for all $n>k\}$. Consider two cases: E finite and E infinite. In the first case there exists m such that $k>m$ implies $k\notin E$ so $a_n>a_k$ for some $n>k$. Inductively choose an increasing subsequence in this case. Now consider the case when E is an infinite set. Pick an increasing sequence of integers $\{n_j\}$ in E. It follows that ${a_n}_j$ is decreasing.