The lexicographic order is a generalization of the order in which words are listed in a dictionary, according to the order of letters where the spelling of two words first differs.
While this notion is most often seen for linear orders, it can be applied also toward more general relations. For example, one might apply the construction to sets equipped with a transitive relation , dropping the trichotomy assumption.
Often this notion is extended to subsets of as well. For instance, the free monoid on a linearly ordered set can be embedded in a countable power
where is the result of freely adjoining a bottom element to , and for each finite list we have
Then the lexicographic order on is the one inherited from its embedding into the lexicographically ordered set .
The decision to freely adjoin a bottom element is of course purely a convention, based on the ordinary dictionary convention that the Scrabble word AAH should come after AA. Alternatively, we could equally well deem that is a freely adjoined top element, so that AA comes after AAH; this might be called the “anti-dictionary” convention.
For the special case , the terminal coalgebra with this lexicographic order is order-isomorphic to the real interval . This isomorphism is described more precisely here.