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

Question

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

Answer 1

I will provide the framework, you can fill the details.

• Call a natural number $n$ "good" if $a_n > a_m$ for all $m > n$.

• If there are infinitely many good points, then these good points form a decreasing subsequence.

• 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.

Answer 2

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.