# 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} for some $$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 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$. Commented Dec 13, 2017 at 5:16
• I see. So I need to consider cases bounded above and bounded below separately? Commented Dec 13, 2017 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. Commented Dec 13, 2017 at 5:21
• @астонвіллаолофмэллбэрг: How to ensure that a sequence without monotone decreasing subsequence contains a monotone increasing subsequence? For example, the sequence $(\sin(n))$. Commented Dec 13, 2017 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? Commented Dec 13, 2017 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.