Every sequence has a monotone subsequence.

Question

Prop: Every sequence has a monotone subsequence.

Pf: Suppose $\{a_n\}_{n\in \mathbb{N}}$ is a sequence. Choose $a_{n_1} \in \{a_1,a_2,...\}$. Further choose smallest possible $a_{n_2} \in \{a_1,a_2,...\}$ such that $a_{n_1}\leq a_{n_2}$. Denote the subsequence of $\{a_n\}$ starting with $a_{n_2}$ by $\{a^{(2)}_{n}\}$. Choose smallest possible $a_{n_3}\in \{a^{(2)}_n\}$ such that $a_{n_2}\leq a_{n_3}$. Denote the subsequence of $\{a^{(2)}_n\}$ starting with $a_{n_3}$ by $\{a^{(3)}_{n}\}$. Choose smallest possible $a_{n_4} \in \{a^{(3)}_n\}$ such that $a_{n_3}\leq a_{n_4}$. Denote the subsequence of $\{a^{(3)}_n\}$ starting with $a_{n_4}$ by $\{a^{(4)}_{n}\}$. Choose smallest possible $a_{n_5} \in \{a^{(3)}_n\}$ such that $a_{n_4}\leq a_{n_5}$. Then, $a_{n_1}\leq a_{n_2}\leq ... \leq a_{k}\leq a_{k+1}$. Conversely, if there exists an index $n_2$ such that $a_{n_1}\geq a_{n_2}$, denote the subsequence of $\{a_n\}$ starting with $a_{n_2}$ by $\{b^{(2)}_n\}$. Choose largest possible $a_{n_3} \in \{b^{(2)}_n\}$ such that $a_{n_2}\geq a_{n_3}$. Repeating the same process, we inductively conclude that for all $k \in \mathbb{N}$, $a_k \geq a_{k+1}$. Thus, $a_1\geq a_2 \geq ... \geq a_k \geq a_{k+1}$.

Does my proof look correct? I wrote my arguments more understandable.

Answer 1

Your proof will work, with the natural changes, if you argue as follows: let $\;a_n\;$ be an infinite sequence. If for some $\;N\in\Bbb N\;$ we have that the sequence is monotonic (whatever: ascending or descending) for $\;n>N\;$, then we're clearly done, otherwise...and now you do what you wrote, but you will prove something stronger: that the sequence has a monotonic ascending subsequence:

Let $\;a_{n_1}=a_1\;$, and now let $\;n_2\;$ be the first index greater that $\;n_1=1\;$ with $\;a_{n_1}\le a_{n_2}\;$ (this

index $\;n_2\;$ must exist otherwise the sequence is monotonic descending for $\;n>1$..!). Next, let $\;n_3\;$

be the first index greater than $\;n_2\;$ such that $\;a_{n_2}\le a_{n_3}\;$ (again argue as before to show it exists...)

and etc. Inductively we've defined a subsequence $\;\{a_{n_k}\}_{k=1}^\infty\subset \{a_n\}_{n=1}^\infty\;$ which is monotonic

ascending.

Pollish now the above and there you go...

Note: as you can read in the comment below, a correction must be made in the above. Instead of taking $\;a_{n_1}=a_1\;$ , which could cause the problem described in the comment, choose $\;n_1\;$ to be the first index for which there exisats a least an index $\;m>n_1\;$ s.t. $a_{n_1}\le a_m\;$ . The consecutive subindices chosen will be equally required to fulfill this.

Or it is possible to write the proof: if $\;a_1\;$ is bigger than any other element in the sequence, then we'll show a monotonic descending subsequence...and you proceed as before to choose indices that will make sure the subsequence is monotonic descending

Answer 2

Say that a term $a_n$ is dominant if $a_n\ge a_m$ whenever $n\le m$.

• Show that if there are infinitely many dominant terms, they form an infinite non-increasing subsequence.

Suppose, then, that there are only finitely many dominant terms, say $\{a_{k_0},\ldots,a_{k_\ell}\}$. Fix $n_0>k_\ell$; then for each $n\ge n_0$ there is an $m>n$ such that $a_n<a_m$. (Why?) Now use your argument to construct an infinite strictly increasing subsequence.