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?
$\begingroup$
$\endgroup$
3
asked May 18, 2010 at 7:30
-
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$– gowersCommented 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$– Joel David HamkinsCommented 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$– Robin ChapmanCommented May 18, 2010 at 17:04
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
6
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.
answered May 18, 2010 at 7:36
-
$\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$ Commented 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$ Commented 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$ Commented 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$ Commented 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$ Commented Nov 1, 2010 at 15:48
$\begingroup$
$\endgroup$
1
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 non-limits. $\endgroup$ Commented May 18, 2010 at 17:50
$\begingroup$
$\endgroup$
2
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.
answered May 18, 2010 at 7:42
-
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$ Commented May 18, 2010 at 8:12
-
$\begingroup$ Yes, this is why I included "countable" already in the statement of the question. $\endgroup$ Commented May 18, 2010 at 15:42
$\begingroup$
$\endgroup$
1
Using wellorderings of positive reals is actually the standard way to construct an Aronszajn tree.
-
$\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$– KiochiCommented May 18, 2010 at 14:17