10
$\begingroup$

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?

$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$
    – gowers
    May 18, 2010 at 10:32
  • $\begingroup$ 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. $\endgroup$ May 18, 2010 at 13:59
  • $\begingroup$ As a remark, this result is used to prove that the long line really is a $1$-manifold. $\endgroup$ May 18, 2010 at 17:04

4 Answers 4

17
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$ Oct 29, 2010 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$ Oct 30, 2010 at 6:59
  • $\begingroup$ 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$. $\endgroup$ Oct 30, 2010 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$ Oct 31, 2010 at 7:44
  • $\begingroup$ Ah, that wasn't clear from your original answer. Now that you say that, it makes total sense. $\endgroup$ Nov 1, 2010 at 15:48
10
$\begingroup$

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.

$\endgroup$
1
  • $\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 non-limits. $\endgroup$ May 18, 2010 at 17:50
5
$\begingroup$

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.

$\endgroup$
2
  • 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$ May 18, 2010 at 8:12
  • $\begingroup$ Yes, this is why I included "countable" already in the statement of the question. $\endgroup$ May 18, 2010 at 15:42
0
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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$. $\endgroup$
    – Kiochi
    May 18, 2010 at 14:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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