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 (i1,...,in).
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.
(i1,...,in) < (i1,...,in)
iff
when one looks at the successive differences i1-j1,
i2-j2,..., in-jn, 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.