Extracting countable chains from linear orders There is a well-known fact in infinite combinatorics asserting that for each infinite linear order $P$ there is a countable subset $R\subseteq P$ of order type either $\omega$ or $\omega^{*}$ 
(by $\omega^{*}$ I mean set of natural number with reversed order). It seems to be a non-trivial result - for example, one can derive it from the Baumgartner-Hajnal theorem but this is, in my taste, too heavy machinery. 
Do you know who iss responsible for this result? Are there any cheaper ways (than the BH-theorem) to obtain it?  
 A: It seems to me that a natural solution is to use Ramsey's theorem $\aleph_0 \to (\aleph_0)^2_2$: enumerate a countable subset, and color two points depending on whether the enumeration agrees with the given order. 
This proof seems "cheaper" to me: Wlog the linear order  $P$ is a subset of the rationals.  Find a limit point $r$.  Wlog $r$ is a limit point of the points from $P$ below $r$ -- so you can find an increasing sequence converging to $r$.
A: You can derive it straight from Ramsey's Theorem. We may assume the linear order is countably infinite, say $x_0,x_1,x_2,\ldots$ enumerates it. Define the coloring $c:[\omega]^2\to2$ by $c(i,j) = 0$ iff $i \lt j$ and $x_i \lt_P x_j$ (and color 1 if the two orderings disagree). If $H$ is a homogeneous set for $c$, then the subsequence $\langle x_i \rangle_{i \in H}$ is either increasing or decreasing with respect to ${\lt_P}$.
This result is actually not quite as strong as Ramsey's Theorem (for pairs and two colors). See Hirschfeldt & Shore, Combinatorial principles weaker than Ramsey's theorem for pairs, JSL 72 (2007), 171-206.
A: Here's another "cheap" proof.  If your linear ordering doesn't have a decreasing $\omega$-sequence, then it's well-ordered, and therefore order-isomorphic to an ordinal.  Since it's infinite, that ordinal is at least $\omega$, and so your ordering not only has a subset of order-type $\omega$ but has an initial segment of order-type $\omega$.  (I've used the axiom of choice, or at least dependent choice, to infer "well-ordered" from the non-existence of a decreasing $\omega$-sequence, but some choice is needed in any proof.  Without choice, there can be infinite linearly ordered sets with no countably infinite subsets.)
