Monotone subsequence of an infinite sequence

Question

Does every infinite sequence have a monotone subsequce? Here by "monotone" we may either (non-strictly) increasing or decreading. More precisely, given a sequence (a_n)_n≥1, does there exist a subsequence (a_{n_j}) that either satisfies a_{n_j} ≥ a_{n_{j+1}} for all j or a_{n_j} ≤ a_{n_{j+1}} for all j. To clarify the notation for a subsequence, here we denote a subsequence of (a_n) by (a_{n_j}) = (a_{n_1}, a_{n_2}, ... a_{n_j}, _..., with the assumption that n_j ≥ j, and n_j < n_{j+1}. In other words, n_j represents a positive integer, and the sequence (n_j) is strictly increasing. e.g. for the sequence (F_n) = (1, 1, 2, 3, 5, 8, ...) has a subsequence (F_2m) = (1, 3, 8, ...0).

Answer 1

The answer is YES!

We can show that if (a_n) does not have any (infinite) decreasing subsequence, then it must have an (infinite) increasing subsequence.

Consider all decreasing subsequences staring with a₁. By our assumption, they must have finite length (length = the number of terms in this subsequence). Among such subsequences, there must be one with maximal length (otherwise there would be at least one decreasing subsequence of infinite length starting with a₁). Let a_{n_1} be the last term of the subsequence of maximal length starting with a₁. Now consider all decreasing subsequences starting with the term a_{n_1+1}, which is the term next to a_{n_1}. Again they all have finite length and there is one with maximal length. Let a_{n_2} be the last term of the subsequence of maximal length starting with a_{n_1+1.} Next consider all decreasing subsequences starting with a_{n_2+1}, which is the term next to a_{n_2}. Let a_{n_3} be the last term of the subsequence of maximal length starting with a_{n_2+1.} Continue this procedure, and we obtain a subsequence (a_{n_j}) of (a_n). We claim that it is increasing.

Indeed, if it is not increasing, then there must be some j with a_{n_j} > a_{n_{j+1}.} But then we can add a_{n_{j+1}} after a_{n_j} to form a decreasing subsequence starting with a_{n_{j−1}+1} whose length is one more than that ending with a_{n_j.} This contracdicts with the assumption that a_{n_j} is the last term of the decreasing subsequence of maximal length starting with a_{n_{j-1}+1}. Therefore (a_{n_j}) must be an increasing subsequence of (a_n).