Given two sets X
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
and y <= v
. This partial
order is a total order
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.
write it down for concreteness.
(i1,...,in) < (i1,...,in)
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