Graphics Reference
In-Depth Information
2
3
XXX
<
XX
23
1
2
1
for degrevlex order.
We would like to isolate the essential properties that an ordering should possess
to be useful. Since ordering monomials
ee
e
n
cX
12
...
x
X
12
will ignore the constant c and will be equivalent to ordering their exponent tuples
e
=
(
)
ee
,
,...,
e
n
12
in
N
n
, the definition of an ordering often deals simply with orderings of elements of
N
n
rather than monomials. We shall state both definitions for comparison purposes
but concentrate on
N
n
.
A
monomial ordering
of
N
n
is a total ordering < on
N
n
that satisfies
Definition.
(1)
0
£
e
for all
e
Œ
N
n
, and
(2) if whenever
e
,
f
Œ
N
n
and
e
<
f
, then
e
+
g
<
f
+
g
for all
g
Œ
N
n
.
Definition.
A
monomial ordering
of k[X
1
,X
2
,...,X
n
] is a total ordering < on the
monomials of k[X
1
,X
2
,...,X
n
] satisfying
(1) c < X
i
for all c Πk and all i.
(2) For all monomials u, v, w Πk[X
1
,X
2
,...,X
n
], u < v implies that uw < vw.
Every monomial ordering of
N
n
is a well-ordering.
10.10.3. Theorem.
Proof.
Let < be monomial ordering. We need to show that every subset of
N
n
has a
smallest element, or, equivalently, that every decreasing sequence
(
)
Œ
n
...
<<<<<
+
ee
...
eee
ee
,
...,
e
N
,
(10.62)
i
1
i
2
1
,
i
i
1
i
2
,
in
must terminate after a finite number of steps. The theorem will be proved by induc-
tion on n.
If n = 1, then it is easy to show that < is just the standard less than relation on the
nonnegative integers. Assume that n ≥ 2 and that the theorem is true for n - 1. Suppose
that we have a decreasing sequence of elements
e
i
as shown in (10.62).
Claim 1.
The theorem is true if there is a j so that all the jth entries in the
e
i
are
constant.
Without loss of generality we may assume that j = n. Suppose that e
in
= c for all
i. Because
(
)
<
(
)
ff
,
,...,
f
,
c
gg
,
,...,
g
,
c
if and only if
il
i
2
in
-
1
il
i
2
in
-
1
(
)
<
(
)
ff
,
,...,
f
,
0
gg
,
,...,
g
,
0
,
il
i
2
in
-
1
il
i
2
in
-
1
