[FOM] Order types: a proof

JoeShipman@aol.com JoeShipman at aol.com
Sun Mar 6 18:07:28 EST 2005

Theorem: If X is an ordered set such that for all a<b in X, 
(a,b) is order-isomorphic to the real numbers, then there are 11 possibilities for the order type of X:

The vacuous example (X = empty set)
The trivial example (X = a 1-element set)
9=3x3 nontrivial examples, where there are 3 possibilities 
for the left and right "ends": an ordinary real interval with 
and without endpoints, and a (standard or reversed) "long 
line".  A "long line" is isomorphic to aleph-1 x [0,1) in the 
dictionary order.

Proof: It suffices to show that if X is an ordered set with 
least element whose closed initial segments are isomorphic to 
[0,1], and X has no countable unbounded subset, then X is 
isomorphic to the long line.

Map aleph-1 into X as follows: Identify the "bottom" 
elements: f(0)=0.  For successor ordinals a+1 in aleph-1, 
choose for f(a+1) an arbitrary element of X greater than 
f(a).  (If this is impossible then X has a top element, and 
therefore a countable unbounded set.) 

For limit ordinals b in aleph-1, consider the subset Y of X 
defined by {f(a)|a<b}.  Pick z in X greater than all the 
elements of y. (If this is impossible, then X has a countable 
unbounded set because b is a countable ordinal.) Then [0,z] 
contained in X is isomorphic to the real interval [0,1], so 
has the least upper bound property. Let f(b) be the least 
upper bound of Y.

After aleph-1 stages, we have a copy X' of aleph-1 lying 
cofinally in X.  (If it were not cofinal, so that x in X were 
greater than all elements of the copy of aleph-1, then [0,x] 
could not be isomorphic to the real interval [0,1].)  Most 
importantly, each limit ordinal in X' is the LUB in X of the 
earlier elements of X'.

We now map the long line aleph-1 x [0,1) onto X as follows: 
Map aleph-1 x {0} canonically to X'.  Between every element 
of X' and its successor is an isomorphic copy of the reals, 
to which we can map the copy of the real interval (0,1) 
between the corresponding two elements of the long line. The 
LUB property of X' ensures that this map is onto, and the 
remaining details are easy.

The argument above fails if we substitute "rationals" 
for "reals", because we don't have the LUB property 
available.  But it is still surprising to have the number of 
possible solutions be so much larger (increasing from 11 to 

Can anyone provide an EXPLICIT (choiceless) construction of 
an example not isomorphic to one of the 11 obtained from 
the "real" examples above by replacing the reals with the 
rationals in the obvious way?  It's nice to show that there 
are 2^aleph-1 of them with a stationary set argument, but it 
ought to be possible to get just one more without going 
through such advanced combinatorics.

-- JS

More information about the FOM mailing list