# question about the proof that every sequence contains a monotone subsequence by Bruckner

Bruckner gives the following proof that every sequence has a monotone subsequence:

We construct first a non-increasing subsequence if possible. We call the $m$th element $x_{m}$ of the sequence $\{x_{n}\}$ a turn-back point if all later elements are less than or equal to it, in symbols if $x_{m}\geq x_{n}$ for all $n < m$. If there is an infinite subsequence of turn-back points $x_{{m}_{1}},x_{{m}_{2}},x_{{m}_{3}},x_{{m}_{4}},\dots$ then we have found our non-increasing subsequence since $$x_{{m}_{1}}\geq x_{{m}_{2}}\geq x_{{m}_{3}}\geq x_{{m}_{4}}\geq \dots$$ This would not be possible if there are only finitely many turn-back points. Let us suppose that $x_{M}$ is the last turn-back point so that any element $x_{n}$ for $n>M$ is not a turn-back point. Since it is not there must be an element further on in the sequence greater than it, in symbols $x_{m}>x_{n}$ for some $m>n$. Thus we can choose $x_{{m}_{1}} > x_{M+1}$ with $m_{1}> M+1$, then $x_{{m}_{2}} > x_{{m}_{1}}$ with $m_{2}>m_{1}$, and then $x_{{m}_{3}} > x_{{m}_{2}}$ with $m_{3}>m_{2}$, and so on to obtain an increasing subsequence $$x_{M+1}< x_{{m}_{1}}< x_{{m}_{2}}< x_{{m}_{3}}<x_{{m}_{4}}< \dots$$ as required.

Now my question is this: When we say there exists the first turn-back point this is equivalent to saying that the first turn-back point is the maximum of $\{x_{n}|n\in \mathbb{N}$. How do we know that such a maximum exists to begin with. For example, take the sequence $\{x_{n}\}$ such that $x_{n}=-1/n$ when $n$ is odd and $x_{n}=-1/\sqrt{n}$. Then, there is no maximum element to begin with. That's what I don't understand.

• Incidentally, your sequence also has no turn-back point, nor is it possible to find an infinte decreasing subsequence. So for this sequence that second variant applies and we can extract an infinite increasing subsequence ... – Hagen von Eitzen Apr 8 '15 at 21:45
• @HagenvonEitzen my question is: what would the $M$ be in my sequence? – user39723 Apr 8 '15 at 21:54
• Every bounded sequence? – Aaron Maroja Apr 8 '15 at 22:06
• No, the sequence need not be bounded. Together with the fact that monotone and bounded sequences converge, this is a classical proof of Bolzano-Weierstrass. – thomas Apr 8 '15 at 22:08

The formulation by Bruckner is unfortunate and the construction doesn't work the way he states it. But the idea is clear. You see that his idea will work once you realize that the element $x_{M+1}$ can actually be replaced by any element after the last turn-back point $x_M$.
Hence, instead of requiring the existence of a "last turn-back point", we just assume the existence of $N$ such that the sequence $x_N, x_{N+1}, x_{N+2}, \dots$ doesn't contain a turn-back point.
More explicitly: If $\{x_n\}$ doesn't contain a turn-back point, then we can choose $N=0$. If there is a finite number of turn-back points, we choose $N = M+1$ (with $x_M$ the "last turn-back point").
Starting from $x_N$ (instead of $x_{M+1}$) we can now do Bruckner's construction for the second case.