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

-
See related math.stackexchange.com/a/96486/413, finding a countable chain or antichain in any partial order. –  Joel David Hamkins Jan 15 '12 at 1:43

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

-
15 seconds behind Francois... –  Goldstern Jan 15 '12 at 0:29
It's fun when that happens! From the reverse math point of view, your second proof is actually more expensive than the first: the existence of limit points requires $ACA_0$ in general, whereas $\aleph_0 \to (\aleph_0)^2_2$ (aka $RT^2_2$) does not. –  François G. Dorais Jan 15 '12 at 0:33
But I think the second proof suggests that Weierstrass (or Cauchy, or Bolzano, or some other mathematician involved in formulating the concept of continuity) might already have considered and proved this fact. –  Goldstern Jan 15 '12 at 0:49
Yes, I like that argument too. It's a bit prettier than the combinatorial one. I think you're right about some old analysts thinking about this... At least, though significantly younger than Weierstrass and Cauchy, H. P. Rosenthal seems to have thought about it that way - mathoverflow.net/questions/12211/… –  François G. Dorais Jan 15 '12 at 0:55
Martin's second argument is common in analysis. Or at least common enough that I have seen it a few times. But I do not know how far it goes. –  Andres Caicedo Jan 15 '12 at 3:19

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.

-

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

-
A while ago, I had a comment on Andreas's last remark, but I guess I erased it by accident. It is consistent (without choice) that there are infinite Dedekind finite subsets of the reals. No such set admits a subset of type $\omega$ or $\omega^*$. –  Andres Caicedo Jan 15 '12 at 3:17