Order Types of Words over a Countable Alphabet
In preparation  results first announced approximately 1982.
Quentin F. Stout
EECS Department, University of Michigan
Abstract:
Let A be a countable linearly ordered alphabet, and let
W(A) denote the linearly ordered set of all finite words of length
0 or greater over A, with the standard lexical ordering.
Then the order type of W(A) is the order type of
 the empty set, if A is the empty set
 N (the natural numbers), if A is a single element
 Q[0,1) (the rationals in [0,1)), if A is nonempty
and has no first element
 Q[0,1) x N otherwise, where the ordering on the product
is the lexical ordering.
Thus there are only 4 possible order types for W(A), despite
the fact that there are uncountably many order types for A.
When A is only partially ordered, then W(A) is only
partially ordered and the variety of order types attained is vastly
expanded. The complete determination of all possibilities is an open
question, as are extensions to uncountable alphabets or index systems
other than the natural numbers.
Keywords:
lexical (lexicographic) ordering, dictionaries, finite
words, countable alphabet, order types, total orders, search,
discrete mathematics
Let me know if you are interested in this  it might motivate me to
write it up.

Copyright © 20052016
Quentin F. Stout 