7
$\begingroup$

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?

Improve this question
$\endgroup$
1

3 Answers 3

Reset to default
9
$\begingroup$

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

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ 15 seconds behind Francois... $\endgroup$
    – Goldstern
    Commented Jan 15, 2012 at 0:29
  • 1
    $\begingroup$ 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. $\endgroup$
    – François G. Dorais
    Commented Jan 15, 2012 at 0:33
  • $\begingroup$ 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. $\endgroup$
    – Goldstern
    Commented Jan 15, 2012 at 0:49
  • $\begingroup$ 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/… $\endgroup$
    – François G. Dorais
    Commented Jan 15, 2012 at 0:55
  • $\begingroup$ 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. $\endgroup$
    – Andrés E. Caicedo
    Commented Jan 15, 2012 at 3:19
8
$\begingroup$

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.

Improve this answer
$\endgroup$
8
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ 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^*$. $\endgroup$
    – Andrés E. Caicedo
    Commented Jan 15, 2012 at 3:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .