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

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 $\alpha$ is lexicographically larger than $\beta$, 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 first element is an integer, and therefore exists a smallest first element, consider that subset of $n$ tuples with smallest total degree and smallest first element.

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