Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

Question: If $\Theta$ is the order type of an uncountable set, then show that for $\alpha < \omega_1$, $\alpha \preceq \Theta$ or $\alpha^* \preceq \Theta.$ Where $\preceq$ is an ordering of order types.

This makes sense to me conceptually. For every order type less than the first uncountable order type, this order type must be less than any uncountable order type. Is this way of thinking correct?

share|cite|improve this question
I'm not sure what do you mean by $\preceq^*$ and by "$\preceq$ is an ordering of order types". Also is $\Theta$ a linear order type? – Asaf Karagila Jul 14 '11 at 16:29
Ohhh, the $\preceq^*$ means that $\alpha^*$ (i.e. the inverse order of $\alpha$) embeds into $\Theta$. Am I correct in my reading? – Asaf Karagila Jul 14 '11 at 17:16
@Asaf: well I hope so because that's what I assumed in my answer. @furs: I forgot to answer the question about the concept of the second paragraph. That way of thinking is not correct, since $\omega_1$ isn't the "first uncountable order type." It makes sense for wellorders, but for general linear orders there are lots of others to worry about (the reals, for instance) that don't have any clear relation to $\omega_1$. – user83827 Jul 14 '11 at 17:36
@Asaf: Yes, that it what I had intended to write. @ccc: I see, thank you. – furs Jul 14 '11 at 19:33

This sketch assumes $\mathtt{AC}$. I'll provide more details if necessary, but I think it's instructive to work through them.

One way to proceed is to consider three special cases, and then argue that in general you can reduce to some special case.

Case 1: The order leans to the right. That is, each point in $\Theta$ has only countably many points less than it. A straightforward transfinite induction allows you to build a copy of each countable ordinal $\alpha$ sitting inside $\Theta$ (at each stage, there are only countably many points to less than or equal to a point you've added, so you have plenty of ways to continue the construction).

Case 2: The order leans to the left. Predictably, this means each point in $\Theta$ sees countably many points greater than it. This is just like Case 1, except you build a reversed copy of $\alpha$.

EDIT: Asaf pointed out an oversight which has now been fixed (I hope!).

Case 3: The balanced case. For each $x \in \Theta$ the set of successors of $x$ does not fall into Case 1 and the set of predecessors of $x$ does not fall into Case 2. In this case you can by transfinite induction show directly that each $\alpha$ embeds into a balanced order. One approach here is to show that in each balanced order you can find an increasing sequence $(x_n)_{n \in \omega}$ such that for each $n$ the interval $(x_n, x_{n+1})$ is uncountable. If one of those intervals falls into Case 1 or 2 (which we've already handled), so we can assume they're all Case 3. This lets you squeeze ordinals you've already handled in sequence, letting you build bigger countable ordinals.

Intuitively, Case 1 should feel like you're working with an ordinal, Case 2 with a reverse ordinal, and Case 3 like the reals (but this is just a heuristic!).

So why are these cases sufficient?

Given an arbitrary $\Theta$, let $\Theta_l$ be the set of points with only countably many predecessors (think of this as the "left end" of $\Theta$), let $\Theta_r$ be those points with only countably many successors (the "right end"), and let $\Theta_m$ be the rest (the "middle"). If $\Theta_l$ is uncountable, you can apply Case 1 to it. Likewise with $\Theta_2$ and Case 2. So WLOG assume both are countable. Then, look for points $x \in \Theta_m$ such that the set of successors of $x$ does not fall into Case 1 and the set of predecessors of $x$ does not fall into Case 2. Show that if you can't find any, then $\Theta_m$ is balanced (be careful here!).

share|cite|improve this answer
In case 3 you cannot always build a copy of the rationals, suppose $\omega_1^*+\omega_1$. It is uncountable, every point has uncountably many above and below; however it is scattered and does not embed the rationals. The right thing to do for case 3 is to cut it at some point and since you have uncountably many points above each point from here on end, you can do case 1, or alternatively case 2 towards the bottom. – Asaf Karagila Jul 14 '11 at 17:39
Ugh, you're right, I was assuming Case 3 occurs densely often. But what you're saying isn't quite right either, since Cases 1 and 2 require countably initial/terminal segments to ensure you don't exhaust the set prematurely. I'll fix it. – user83827 Jul 14 '11 at 17:43
There are two cases: There are uncountably many points above someone; there are uncountably many points below someone. It doesn't even matter if there is only an uncountable interval and then countably many points (e.g. $\omega^*+\omega_1+\omega^\omega+34103$) – Asaf Karagila Jul 14 '11 at 17:51
@Asaf: having uncountably many points above someone is not enough to build a copy of $\omega$ above him, let alone arbitrary countable $\alpha$. I must be misunderstanding what you're claiming. Anyway, hopefully my answer is at least correct now. Please write another answer if you see a better way. And of course let me know if I made any more errors! – user83827 Jul 14 '11 at 17:59
Actually it is, by this very question. Take the order type of the uncoutnably many points, by the theorem above it embeds either $\omega$ or $\omega^*$ :-), I see the fine point in your comment though (for example $\omega+\omega_1^*$, take any point in the $\omega$ part, there are uncountably many points above it, but you cannot find an increasing chain which is infinite) – Asaf Karagila Jul 14 '11 at 18:05

Here is a perhaps silly way to prove this result. The Baumgartner-Hajnal partition theorem says that $\omega_1 \to (\alpha)^2_2$ for all $\alpha < \omega_1$. In plain English, for every coloring $c:[\omega_1]^2\to\{0,1\}$ there is a set $A \subseteq \omega_1$ with order-type $\alpha$ such that $c$ is constant on $[A]^2$.

Given an uncountable linear ordering $\Theta$. First, pick an arbitrary injection $f:\omega_1\to\Theta$ and define the coloring $c:[\omega_1]^2\to\{0,1\}$ by $$c(x,y) = \begin{cases} 0 & \text{when } f(x) >_\Theta f(y) \\ 1 & \text{when } f(x) <_\Theta f(y)\end{cases}$$ for all $x < y < \omega_1$. By the Baumgartner-Hajnal partition theorem, there is a set $A \subseteq \omega_1$ with order-type $\alpha$ such that $c$ is constant on $[A]^2$. If the constant value of $c$ is $1$, then the restriction of $f$ to $A$ is order preserving; if the constant value of $c$ is $0$, then the restriction of $f$ to $A$ is order reversing. Thus, either $\alpha \preceq \Theta$ or $\alpha^* \preceq \Theta$.

The reason why this argument is a little silly is that the Baumgartner-Hajnal partition theorem is much harder to prove than the result on order-types. Indeed, the result on order-types can be thought of as a motivation for the Baumgartner-Hajnal partition theorem.

share|cite|improve this answer
If this was a book you could write "A simple corollary from the Baumgartner-Hajnal partition theorem ...". Nice. – Asaf Karagila Jul 14 '11 at 18:14

I think by $\alpha \preceq \Theta$ it is meant that $\alpha$ is order-isomorphic to a subset of $\Theta$. In a sense I think what is going on is that $\omega_1$ is so "sparse" among uncountable linearly ordered sets that each uncountable linearly ordered set contains (if reverse ordering is also allowed) every initial segment of $\omega_1$, or something like this. The best reference I know for this sort of stuff is

Joseph G. Rosenstein, "Linear Orderings", Academic Press, 1982.

share|cite|improve this answer

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.