1
$\begingroup$

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?

  • 0
    @Asaf: Yes, that it what I had intended to write. @ccc: I see, thank you.2011-07-14

3 Answers 3

3

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

  • 0
    @Asaf: By the way, let me explain the density comment in case it wasn't clear what I meant. In Case 3 I was mentally assuming WLOG that all uncountable intervals were not in Cases 1 or 2 (and in this situation you really can build a copy of the rationals, but it's not so important). But then I unsuccessfully tried to simplify the argument! Goes to show what simplicity is worth. Anyway, many thanks again for catching the error.2011-07-14
2

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.

  • 0
    If this was a book you could write "A simple corollary from the Baumgartner-Hajnal partition theorem ...". Nice.2011-07-14
0

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.