MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
See related, finding a countable chain or antichain in any partial order. – Joel David Hamkins Jan 15 '12 at 1:43
up vote 8 down vote accepted

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

share|cite|improve this answer
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 -… – 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. – Andrés E. 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.

share|cite|improve this answer

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

share|cite|improve this answer
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^*$. – Andrés E. Caicedo Jan 15 '12 at 3:17

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.