Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
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 '10 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 '10 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 '10 at 17:04

4 Answers 4

up vote 16 down vote accepted

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.

share|improve this answer
    
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 '10 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 '10 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 '10 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 '10 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 '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.

share|improve this answer
    
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 '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 well-ordered subsets of R are exactly countable ordinals.

share|improve this answer
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 '10 at 8:12
    
Yes, this is why I included "countable" already in the statement of the question. –  David Eppstein May 18 '10 at 15:42

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

share|improve this answer
    
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 '10 at 14:17

Your Answer

 
discard

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.