# 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.

• We do need to worry about increasing versus non-decreasing. Consider the sequence $0,1,0,1,0,1,\dots$. – André Nicolas Mar 18 '14 at 5:41
• @André Nicolas Sorry forgot to mention that. Any sequence of the form $x_1 \le x_2 \le ... x_n \le x_{n + 1} \le ...$ is considered monotone increasing. That's the definition in the book. So that is generally what one would call non-decreasing I believe. – Ishfaaq Mar 18 '14 at 5:43
• That's OK with me. So those examples are buried under your second "without loss of generality." – André Nicolas Mar 18 '14 at 5:46
• @André Nicolas: Okay.. Well I've assumed the sequence is not bounded. Based on this there is no loss generality in assuming it is not bounded above. If it is then it is not bounded below and we may construct a decreasing sequence in pretty much the same way. Any issues with this argument?? – Ishfaaq Mar 18 '14 at 5:47
• Your second without loss of generality. The subsequence with limit $y$. There is also an implicit use I think of AC, at least some weak form of it. That's probably fine. – André Nicolas Mar 18 '14 at 5:50

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.

• Thanks for the response. But my knowledge in Graph Theory is restricted to the very basics I am not great with colouring. My question is how do we claim that $A_0$ and $A_1$ contain edges of the same colour? $A_1$ must be infinite but it could contain edges of the opposite colour. So the sequence $i_0, i_1,..$ need not be increasing. Where am I going wrong here?? – Ishfaaq Mar 18 '14 at 6:38
• The sequence is increasing by construction: $i_0=0$, and $i_{n+1}$ is the minimum of $A_n$. To get $i_{n+2}$ you get inside the rest of $A_n$ (excluding its minimum), so you are automatically dealing only with numbers larger than $i_{n+1}$. You then select an infinite subset $A_{n+1}$ of $A_n$ (according to the prescription in paragraph 3), and then pick $i_{n+2}$ as the minimum of $A_{n+1}$. So, necessarily, the $i_n$ are increasing, we designed them that way. – Andrés E. Caicedo Mar 19 '14 at 1:17

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.

• How we can build the increasing sub-sequence later? – Sushil Mar 29 at 13:25
• @Sushil Suppose $x = \sup R_N$ is not a member of the sequence. Let $a_{k_1}$ be a member of $R_N$ with $|x - a_{k_1}| < 1$. Having chosen $a_{n_k}$, choose $a_{n_{k+1}}$ with $|x - a_{n_{k+1}}| < 1/(k+1)$ and with $a_{k+1} > a_k$. – Ovi Mar 30 at 1:15