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*_{1},...,i_{n}).
The way this works is that the natural numbers **N** are totally ordered, as usual
so that the lexicographic ordering makes **N**x**N** totally ordered.
Now apply the lexicogrpahic ordering to **N**x(**N**x**N**)
and we get that **N**x**N**x**N** 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*_{1},...,i_{n}) < (i_{1},...,i_{n})
iff
when one looks at the successive differences *i*_{1}-j_{1},
i_{2}-j_{2},..., 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.