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

Let $P$ be an uncountable linear ordering. Is it true that either $P$ contains an order-copy of $\omega_1$ or there is $x_0\in P$ such that there exist uncountably many distinct $y\in P$ with $y< x_0$? If so, where can I find a reference for this?

Thank you.

share|cite|improve this question
You might also be interested in this: Justin Moore shows that, under the proper forcing axiom, every uncountable linear order contains a subset isomorphic to one of 5 different types. – Shawn Henry Oct 15 '12 at 21:08
up vote 7 down vote accepted

If every initial segment of the order has only countably many predecessors, then every countable subset of the order would be bounded (for otherwise the whole order would be a countable union of countable sets). In this case, we may therefore construct an increasing $\omega_1$ sequence in the order by recursion: start by choosing any point. After any countable number of stages, you've picked at most countably many points, which are bounded, and so there remains points above for you to pick. Thus, by recursion, you find an increasing $\omega_1$ sequence from the order.

In case anyone objects to the fact that the previous argument uses the axiom of choice, let me point out that one cannot prove the result without any use of the axiom of choice. To see this, recall that it is known to be relatively consistent with ZF that $\omega_1$ is singular, the limit of countably many countable ordinals. Suppose that $\omega_1=\sup_n\alpha_n$, where $\alpha_0\lt\alpha_1\lt\cdots$ and so on. Let $L$ be the linear order obtained by chopping $\omega_1$ into the $\omega$ many corresponding intervals $[\alpha_n,\alpha_{n+1})$, but turning each of these intervals upside down, to have the reverse order. So we have an $\omega$ increasing sequence of blocks, each is anti-well-ordered with countable order type. This is an uncountable order, and every initial segment is countable, because it is a finite union of countable sets. But there is no increasing $\omega_1$ sequence in $L$, because any well-ordered sequence can have at most finitely many members of each (anti-well-ordered block), and there are $\omega$ many blocks in order. So every increasing suborder has finite order type or order type $\omega$ at most. Thus, it is consistent with ZF that the desired result about orders is false.

share|cite|improve this answer
Very nice construction with the singular $\omega_1$. Another option is to use quasi-amorphous ($\aleph_1$-amorphous) sets, i.e. every subset is countable or co-countable. It is consistent that there is a linearly ordered $\aleph_1$-amorphous set, and in such linear order when cutting at a particular point we have that below it there are only countably many (if not, inverse the order of course). – Asaf Karagila Oct 15 '12 at 19:58

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.