[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
2^aleph-1.)
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