UTM Ideals Varieties and Algorithm - Chapter 2 Section 2 Exercise 5

Problem:

Solution:

All we needed to do for this problem is to verify the three rules.

(i) > is a total (or linear order) on $\mathbf{Z}^n_{\ge 0}$

This is simple to verify according to the definition. As long as two monomials are not the same, then either one is strictly larger than the other.

(ii) If $\alpha > \beta$ and $\gamma \in \mathbf{Z}^n_{\ge 0}$, then $\alpha + \gamma > \beta + \gamma$.

This is also simple to verify. if $\alpha$ has a total degree larger than $\beta$, then so is $\alpha + \gamma$ and $\beta + \gamma$. Otherwise if the rightmost element of $\alpha - \beta$ is negative, then so is $\alpha + \gamma$ and $\beta + \gamma$ as well.

(iii) > is a well ordering

For any set of $n$ tuple, their total order is a set of non-negative integer and therefore there exist a smallest total degree, consider that subset of $n$ tuples with smallest total degree.

For any set of $n$ tuple with the same total order, their last element is an integer, and therefore exists a smallest first element, consider that subset of $n$ tuples with smallest total degree and smallest last element. (*)

Repeat the above until we find the one with every element smallest. Now we have found a smallest element.

Suppose we have two elements $\alpha$ and $\beta$ with same total degree to compare with and $\alpha$ has a smallest last element, then $\alpha - \beta$ will have a negative rightmost non-zero element.