Proof of the ascending descending sequence principle

Question

I'm really stuck trying to prove the ascending descending sequence principle, that is the fact that given any infinite linear order $(L,<)$ there is a subset of $L$ with order type either $\omega$ or $\omega^*$ (where $(\omega^*,\in):=(\omega,\ni)$). In other words, that there is either a strictly increasing or a strictly decreasing sequence $\omega\to L$.

My guess is that we can use Ramsey's Theorem in order to get an homogeneous subset of $L$ for a suitable function which says something about the order, but I really cannot find how to do that precisely.

Thanks in advance!

Answer 1

Since $L$ is infinite it contains a sequence $(x_1,x_2,\dots)$.

Say $n$ is dominant if $$x_m\le x_n\quad(\forall{m\ge n}).$$

If there are infinitely many dominant values of $n$ then the subsequence of $(x_n)$ for $n$ dominant is non-increasing. Otoh if there are only finitely many dominant values of $n$ then it's not hard to show there is a non-decreasing subsequence.

Answer 2

Your idea of using Ramsey theory also works (though David's proof is the slick "book proof"): let $x_n, n \in \omega$ be a (1-1) subsequence of $L$ which must exist by $L$ being infinite.

Colour $[\omega]^2$ by $\{0,1\}$ by saying that $f(\{x_n, x_m\})=0$ when the order of $\{n,m\}$ (in $\omega$) and $\{x_n,x_m\}$ (in $L$) agree, and $1$ otherwise.

By Ramsey's theorem that $\aleph_0 \to (\aleph_0)^2_2$ we have a homogeneous infinite subset $A$ of $\omega$ and if it has colour $0$, the $x_n, n \in A$ is increasing and otherwise decreasing.