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 .
if is linearly ordered and the underlying set is regarded as the terminal coalgebra for the functor , with coalgebra structure , then the lexicographic order on may be defined corecursively:
if or ( and ).
Revised on September 16, 2012 15:15:14
by Todd Trimble