Extracting countable chains from linear orders - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T05:01:25Z http://mathoverflow.net/feeds/question/85699 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/85699/extracting-countable-chains-from-linear-orders Extracting countable chains from linear orders Tomek Kania 2012-01-15T00:11:06Z 2013-05-10T08:30:11Z <p>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^{*}$ </p> <p>(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. </p> <p>Do you know who iss responsible for this result? Are there any cheaper ways (than the BH-theorem) to obtain it? </p> http://mathoverflow.net/questions/85699/extracting-countable-chains-from-linear-orders/85701#85701 Answer by François G. Dorais for Extracting countable chains from linear orders François G. Dorais 2012-01-15T00:27:08Z 2012-01-15T00:27:08Z <p>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}$.</p> <p>This result is actually not quite as strong as Ramsey's Theorem (for pairs and two colors). See Hirschfeldt &amp; Shore, <em>Combinatorial principles weaker than Ramsey's theorem for pairs</em>, JSL 72 (2007), 171-206.</p> http://mathoverflow.net/questions/85699/extracting-countable-chains-from-linear-orders/85702#85702 Answer by Goldstern for Extracting countable chains from linear orders Goldstern 2012-01-15T00:27:22Z 2012-01-15T00:27:22Z <p>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. </p> <p>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$.</p> http://mathoverflow.net/questions/85699/extracting-countable-chains-from-linear-orders/85704#85704 Answer by Andreas Blass for Extracting countable chains from linear orders Andreas Blass 2012-01-15T02:03:56Z 2012-01-15T02:03:56Z <p>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.)</p> http://mathoverflow.net/questions/85699/extracting-countable-chains-from-linear-orders/130237#130237 Answer by Butch Malahide for Extracting countable chains from linear orders Butch Malahide 2013-05-10T08:30:11Z 2013-05-10T08:30:11Z <p>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.</p>