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

This is a very classic argument, I think. Let call $n\in \mathbb{N}$ "nice" if $a_n >a_m$ for all $m> n$. So we have only two possibilities:

(1) The sequence contain 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$, then $(a_{n_i})$ is a decreasing subsequence.

(2) The sequence contains finitely many "nice" points. Let $n_1$ be greater that 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 continuous in this fashion we 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.


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.


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.