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.

Related work