8

4

Suppose one has a set $S$ of positive real numbers, such that the usual numerical ordering on $S$ is a well-ordering. Is it possible for $S$ to have any countable ordinal as its order type, or are the order types that can be formed in this way more restricted than that?

flag
A small remark: I once gave a graduate-level course in which I wanted to do transfinite induction over the countable ordinals but didn't want to spend time developing the theory of ordinals. So I defined the countable ordinals as equivalence classes of well-ordered subsets of the reals, which is the kind of thing one would like to do for the ordinals themselves but cannot because of set-theoretic paradoxes. It worked nicely and was completely rigorous. – gowers May 18 2010 at 10:32
All well-orderings are rigid as orders, and this question: mathoverflow.net/questions/9901/… inquires more generally about other rigid suborders of the real line. – Joel David Hamkins May 18 2010 at 13:59
As a remark, this result is used to prove that the long line really is a $1$-manifold. – Robin Chapman May 18 2010 at 17:04

4 Answers

16

Yes, one can have any countable ordering. Indeed any countable totally ordered set can be embedded in $\mathbb{Q}$. Write your ordered set as $ \lbrace a_1,a_2,\ldots \rbrace $ and define the embedding recursively: once you have placed $a_1,\ldots,a_{n-1}$ there will always be an interval to slot $a_n$ into.

link|flag
I don't get this answer. The ordinal $\omega+1$ is an order-type that is countable, but your method of embedding won't work without some modification (if you place a_i at the rational number i, there will be no room left for the final entry). I would recommend David checkbox gowers answer, as it actually covers all of the countable well-orderings. – Pace Nielsen Oct 29 2010 at 19:53
It does work: $\omega+1$ is a countable set. We can write its elements as $\omega,0,1,2,\ldots$. This is an order we can insert them in. There is no "final" entry. – Robin Chapman Oct 30 2010 at 6:59
But the original question asked about all possible countable order types. If you re-order things, you have changed the order type. For example, if you rearrange the countable set $\omega+1$ as $\omega,0,1,2,\ldots$, your new order type is just $\omega$. – Pace Nielsen Oct 30 2010 at 14:44
2 
 No, I have not altered the order type. All I have done is use a bijection between $\mathbb{N}$ and the ordered set. In $\omega+1$, $\omega$ is still the largest element -- but it's the one you insert first. So in your example we could start by mapping $\omega$ to $0$, then map $0$ to $-1$, then $1$ to $-1/2$ etc. The insight is that one doesn't have to insert your elements in increasing order! – Robin Chapman Oct 31 2010 at 7:44
Ah, that wasn't clear from your original answer. Now that you say that, it makes total sense. – Pace Nielsen Nov 1 2010 at 15:48
7

You can get any order type. Let's assume you can get all order types up to but not including alpha, using subsets of (0,1]. If alpha=beta + 1 then squash your representation of beta and add an extra point. If alpha is a limit ordinal, choose a sequence of ordinals that converges to alpha and put the first one into (0,1/2], the second into (1/2,3/4] etc. and the result will have order type alpha.

link|flag
This seems like a good answer to me, too, but I gave the checkbox to Robin's because it uses less about the structure of the ordinals: just the fact of their countability rather than a decomposition into limits and non-limits. – David Eppstein May 18 2010 at 17:50
4

To complete the picture (the obvious remaining part). If ${S\subset\mathbb R}$ is well ordered, then it is countable: indeed it has countable cofinality. Thus well-ordered subsets of R are exactly countable ordinals.

link|flag
1 
 Another way to see this is to note that there is a rational between the images of $\alpha$ and $\alpha+1$ and these rationals are all distinct. – Robin Chapman May 18 2010 at 8:12
Yes, this is why I included "countable" already in the statement of the question. – David Eppstein May 18 2010 at 15:42
0

Using wellorderings of positive reals is actually the standard way to construct an Aronszajn tree.

link|flag
I thought the "standard" method is to use 1-1 maps from the countable ordinals into $\omega$. A tree constructed in this way can't have an uncountable chain lest we map $\omega_1$ 1-1 into $\omega$. – Kiochi May 18 2010 at 14:17

Your Answer

Get an OpenID
or

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