online advertising

Thursday, March 10, 2016

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.

No comments:

Post a Comment