Came across the following exercise in Bartle's Elements of Real Analysis. This is the solution I came up with. Would be grateful if someone could verify it for me and maybe suggest better/alternate solutions.
I also looked up these related questions - (1), (2), (3) - but was not happy with proofs given there. I seem to need some help understanding these. Any such help is appreciated.
Show that every sequence in $\Bbb R$ either has a monotone increasing sub-sequence or a monotone decreasing sub-sequence.
Let $(x_n)$ be a sequence in $\Bbb R$. Suppose $(x_n)$ is not bounded. Without loss of generality we may assume that $(x_n)$ is not bounded above. Therefore given any real number there is a member of the sequence which is greater. Let $x_{n_1}$ be any member of the sequence.
There is $x_{n_2} \gt \sup\{x_1, x_2, ..., x_{n_1} \}$. For $i \gt 1$ let $x_{n_i} = \{x_1, x_2, ..., x_{n_{i - 1}}\}$ then $(x_{n_k})$ forms a monotone subsequence of $(x_n)$.
Now suppose instead that $(x_n)$ is bounded. By the Bolzano-Weierstrass Theorem there is a subsequence $(y_n)$ of $(x_n)$ which converges to a limit $y$. Without loss of generality there are infinitely many distinct values in $(y_n)$ that are unequal to $y$. Let $y_{k1}$ be the first such element. Let $y_{k2}$ be any element in $\{ y' \in (y_n) \ \ | \ \ |y' - y | \lt |y - y_{k1}| \}$.
For $i \gt 1$ let $y_{ki} \in \{ y' \in (y_n) \ \ | \ \ |y' - y | \lt |y - y_{k \ i - 1}| \}$. Such $y_{ki}$ exists for every $i \in \Bbb N$ since $ \lim (y_n) = y $. Now let $(y_{kn})$ be the sub-sequence of $(y_n)$ thus formed. At least one of the two following sets must contain infinitely many elements.
- $\{ y \in (y_{kn}) \ \ | \ \ y \gt x\}$
- $\{ y \in (y_{kn}) \ \ | \ \ y \lt x\}$
The one which does forms a monotone subsequence.
$\endgroup$ 153 Answers
$\begingroup$This is a very classic argument, I think. Let $n\in \mathbb{N}$ be called "nice" if $a_n >a_m$ for all $m> n$. So we have only two possibilities:
(1) The sequence contains infinitely many "nice" points. If $n_1<n_2<\ldots<n_i< \ldots$ are the "nice" points, we have $a_{n_1}>a_{n_2}> \ldots>a_{n_i}> \ldots$, so $(a_{n_i})$ is a decreasing subsequence.
(2) The sequence contains finitely many "nice" points. Let $n_1$ be greater than all the "nice" points. Since $n_1$ is not "nice" there is some $n_2>n_1$ such that $a_{n_2}\ge a_{n_1}$, and we continue in this fashion to get a non-decreasing subsequence $(a_{n_i})$.
More formally: Let $N$ be a natural number which is greater than all the "nice" points. We define $n_1:= N$ and $n_{i+1}:=\min\{n> n_{i}: a_n\ge a_{n_{i}}\}$. Hence $(a_{n_i})$ is non-decreasing.
$\endgroup$ $\begingroup$I like to think of this in terms of Ramsey theory. We are coloring the edges of the complete graph on $\mathbb N$, using two colors, and want to ensure that there is a complete infinite subgraph that is monochromatic.
The case that concerns us is the coloring where, for $i<j$, the edge $\{i,j\}$ is colored red if $x_i\le x_j$, and blue otherwise. An infinite monochromatic subgraph gives us the indices of a monotone subsequence: If red, the subsequence is increasing while, if blue, it is strictly decreasing.
Start by noting that there is an infinite $A_0$ with all edges $\{0,i\}$, $i\in A_0$, of the same color. Let $i_0=0$ and $i_1=\min(A_0)$. There is an infinite $A_1\subset A_0$ with all edges $\{i_1,i\}$, $i\in A_1$, of the same color. Let $i_2=\min(A_1)$, and continue this way.
We get $i_0<i_1<\dots$ with the property that, for any $n$, all pairs $\{i_n,i_m\}$ with $m>n$, have the same color. Call it $c_n$. Now, the sequence $c_0,c_1,c_2,\dots$ is a sequence that only takes two values, so it has a constant subsequence. The corresponding $i_n$ form the monochromatic set we were looking for.
$\endgroup$ 2 $\begingroup$I think the other proofs are superior, but this is a sketch of the method I came up with when trying to solve it on my own:
If $a_n$ is unbounded, we are done.
Suppose $a_n$ is bounded and let $R_N = \{a_n| n \ge N \}$ (i.e. the range of $a_n$ after $N$). Since $R_N$ is nonempty and bounded, it has a supremum. Note that for every $N$, $\sup R_{N+1} \le \sup R_N$. Thus if $\forall N \sup R_N$ is a member of the sequence, then we can construct a decreasing subsequence.
Now to finish up, suppose that for some $N$, $x = \sup R_N$ is not a member of the sequence. From the definition of supremum, we know that $\forall \epsilon >0$ there exists an element of the sequence, $a_n$, with $x- \epsilon <a_n$, and we can build an increasing subsequence based on that.
$\endgroup$ 2
