Suppose one has a set $S$ of positive real numbers, such that the usual numerical ordering on $S$ is a wellordering. 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?

1$\begingroup$ A small remark: I once gave a graduatelevel 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 wellordered subsets of the reals, which is the kind of thing one would like to do for the ordinals themselves but cannot because of settheoretic paradoxes. It worked nicely and was completely rigorous. $\endgroup$ – gowers May 18 '10 at 10:32

$\begingroup$ All wellorderings are rigid as orders, and this question: mathoverflow.net/questions/9901/… inquires more generally about other rigid suborders of the real line. $\endgroup$ – Joel David Hamkins May 18 '10 at 13:59

$\begingroup$ As a remark, this result is used to prove that the long line really is a $1$manifold. $\endgroup$ – Robin Chapman May 18 '10 at 17:04
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_{n1}$ there will always be an interval to slot $a_n$ into.

$\begingroup$ I don't get this answer. The ordinal $\omega+1$ is an ordertype 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 wellorderings. $\endgroup$ – Pace Nielsen Oct 29 '10 at 19:53

$\begingroup$ 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. $\endgroup$ – Robin Chapman Oct 30 '10 at 6:59

$\begingroup$ But the original question asked about all possible countable order types. If you reorder 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$. $\endgroup$ – Pace Nielsen Oct 30 '10 at 14:44

3$\begingroup$ 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! $\endgroup$ – Robin Chapman Oct 31 '10 at 7:44

$\begingroup$ Ah, that wasn't clear from your original answer. Now that you say that, it makes total sense. $\endgroup$ – Pace Nielsen Nov 1 '10 at 15:48
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.

$\begingroup$ 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 nonlimits. $\endgroup$ – David Eppstein May 18 '10 at 17:50
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 wellordered subsets of R are exactly countable ordinals.

2$\begingroup$ 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. $\endgroup$ – Robin Chapman May 18 '10 at 8:12

$\begingroup$ Yes, this is why I included "countable" already in the statement of the question. $\endgroup$ – David Eppstein May 18 '10 at 15:42
Using wellorderings of positive reals is actually the standard way to construct an Aronszajn tree.

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