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

  • $\begingroup$ 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$. $\endgroup$ – Teresa Lisbon Dec 13 '17 at 5:16
  • $\begingroup$ I see. So I need to consider cases bounded above and bounded below separately? $\endgroup$ – Idonknow Dec 13 '17 at 5:18
  • $\begingroup$ 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. $\endgroup$ – Teresa Lisbon Dec 13 '17 at 5:21
  • $\begingroup$ @астонвіллаолофмэллбэрг: How to ensure that a sequence without monotone decreasing subsequence contains a monotone increasing subsequence? For example, the sequence $(\sin(n))$. $\endgroup$ – Idonknow Dec 13 '17 at 5:23
  • 1
    $\begingroup$ 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? $\endgroup$ – Cave Johnson Dec 13 '17 at 5:25

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.

  • $\begingroup$ What is a motivation of considering the notion 'good'? $\endgroup$ – Idonknow Dec 13 '17 at 5:35
  • $\begingroup$ I can't really say much, other than the fact that it is the best word to express what I had in mind for such a number. But you can verify the details. $\endgroup$ – Teresa Lisbon Dec 13 '17 at 5:36

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.