Extracting countable chains from linear orders - MathOverflow

Extracting countable chains from linear orders

2012-01-15T00:11:06Z

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?

Answer by François G. Dorais for Extracting countable chains from linear orders

2012-01-15T00:27:08Z

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.

Answer by Goldstern for Extracting countable chains from linear orders

2012-01-15T00:27:22Z

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

Answer by Andreas Blass for Extracting countable chains from linear orders

2012-01-15T02:03:56Z

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

Answer by Butch Malahide for Extracting countable chains from linear orders

2013-05-10T08:30:11Z

Every infinite sequence has a monotone subsequence. (In introductory real analysis texts this is proved for sequences of real numbers, but the same proof works for sequences in a linearly ordered set.) So take an infinite sequence of distinct elements, etc.