[FOM] Constructive solutions to the order type puzzle

Ali Enayat enayat at american.edu
Mon Mar 7 11:39:40 EST 2005

This is a partial reply to Joe Shipman's query in connection with the 
"order-type" puzzle. In his posting (March 6, 2005), he asked:

"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."

It is known that every Borel linear order L is embeddable into a linear 
order of the form 2^alpha, where alpha is a countable ordinal, and 2^alpha 
is the set of binary sequences of length alpha, endowed with the 
lexicographical ordering [Harrington, Marker, Shelah, 1988, Transactions of 
American Mathematical Society].

This result implies that every Borel linear order has countable cofinality, 
which in turn can be used to prove that in the *Borel realm*, the answer to 
the puzzle is reduced to 6 (with the "long line" solutions out of the 
picture).  Therefore any explicit construction, besides these 6, must be 
"highly" nonconstructive.


Ali Enayat 

More information about the FOM mailing list