Lexicographical order

In mathematics, the lexicographical order, or dictionary order, is a natural order structure of the cartesian product of two ordered sets. Given A and B, two ordered sets, the lexicographical order in the cartesian product A × B is defined as\n:(a,b) ≤ (a',b') if and only if a < a' or (a = a' and b ≤ b').\nThe name comes from its generalizing the order given to words in a dictionary: a sequence of letters (i.e. a word) a₁a₂...a_k appears in a dictionary before a sequence b₁b₂...b_k if and only if the first a_i which is different from b_i comes before b_i in the alphabet. For the purpose of dictionaries, etc., one may assume that all words have the same length, by adding blank spaces at the end, and considering the blank space as a special character which comes before any other letter in the alphabet. This also allows ordering of phrases. See alphabetical order. An important property of the lexicographical order is that it preserves well-orders, that is, if A and B are well-ordered sets, then the product set A × B with the lexicographical order is also well-ordered.

Case of multiple products

Suppose \n:\nis a collection of sets, with respective to total orderings\n: The dictionary ordering \n: \nof\n:\nis then \n: That is, if one of the terms \n:\nand all the preceding terms are equal. Informally, \n: \nrepresents the first letter, \n: \nthe second and so on when looking up a word in a dictionary, hence the name. This could be more elegantly defined recursively by defining the ordering of any set

represented by\n: This will satisfy

where \nOr, more simply put, compare the first terms if they are equal compare the second — and so on.

Monomials

In algebra it is traditional to order terms in a polynomial, by ordering the monomials in the indeterminates. This is fundamental, in order to have a normal form. Such matters are typically left implicit in discussion between humans, but must of course be dealt with exactly in computer algebra. In practice one has an alphabet of indeterminates X, Y, ... and orders all monomials formed from them by a variant of lexicographical order. For example if one decides to order the alphabet by

X > Y > ...

and also to look at higher terms first, that means ordering

... X³ > X² > X

and also

X > Y^k for all k.

There is some flexibility in ordering monomials, and this can be exploited in Gröbner basis theory.