Lexicographic

Otherwise known as dictionary ordering, or alphabetic ordering. Known in discrete mathematics as a partial ordering. Where the relation is reflexive, transitive, and antisymmetric.

Given two sets X and Y that have a partial order then the cartesian product XxY gets a partial ordering called the lexicogaphic ordering if we define (x,y) <= (u,v) iff x < u or x=u and y <= v. This partial order is a total order if X and Y were totally ordered.

This lexicographic order turns up most often for n-tuples of natural numbers (i₁,...,i_n). The way this works is that the natural numbers N are totally ordered, as usual so that the lexicographic ordering makes NxN totally ordered. Now apply the lexicogrpahic ordering to Nx(NxN) and we get that NxNxN is totally ordered. By iterating the above we arrive at a total ordering on n-tuples of natural numbers.

Let's write it down for concreteness. (i₁,...,i_n) < (i₁,...,i_n) iff when one looks at the successive differences i₁-j₁, i₂-j₂,..., i_n-j_n, the first nonzero one is negative.

For example, (1,2) < (1,3) and (3,3) < (4,2).

This ordering is useful when dealing with polynomials in several variables.

Lex`i*co*graph"ic (?), Lex`i*co*graph"ic*al (?), a. [Cf. F. lexicographique.]

Of or pertaining to, or according to, lexicography.

-- Lex`i*co*graph"ic*al*ly, adv.

 

© Webster 1913.