Proof Verification - Every sequence in $\Bbb R$ contains a monotone sub-sequence

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.

Solution 1:

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.

Solution 2:

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.