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.
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