Math 480, Spring 2013, Assignment 4

By one of those caprices of the mind, which we are perhaps most subject to in early youth, I at once gave up my former occupations; set down natural history and all its progeny as a deformed and abortive creation; and entertained the greatest disdain for a would-be science, which could never even step within the threshold of real knowledge. In this mood of mind I betook myself to the mathematics, and the branches of study appertaining to that science, as being built upon secure foundations, and so worthy of my consideration.

- Mary Shelley, Frankenstein

Carefully define the following terms, then give one example and one non-example of each:

1. Relation (on a set \(S\)).
2. Partial order.
3. Total order.
4. Well-ordering.
5. Monomial order.

Carefully state the following theorems:

1. Theorem on well-ordered sets and descending chains.

Solve the following problems:

1. Prove that \(\leq_{\mbox{lex}}\) is a total order on \(\mathbb{Z}_{\geq0}^n\).
2. Rewrite each of the following polynomials with the terms in lex order (leading term first), and identify the leading term, leading monomial, leading coefficient, and multidegree. Then do the same using grlex order, and then using grevlex order:
   \(f(x,y,z)=2x+3y+z+x^2-z^2+x^3\)
   \(g(x,y,z)=2x^2y^8-3x^5yz^4+xyz^3-xy^4\)
3. Define a relation \(\preceq\) on \(\mathbb{Z}_{\geq0}\) by declaring that \(n\preceq m\) if and only if \(n\geq m\) (in the ordinary sense). Show that \(\preceq\) is a total ordering that satisfies \(n\preceq m\implies n+k\preceq m+k\) but is not a well-ordering (and hence not a monomial order).
4. The usual ordering on \(\mathbb{Z}_{\geq0}\) has the following property: between any two fixed elements there are only finitely many other elements. Either prove that this is true of any monomial order on \(\mathbb{Z}_{\geq0}^n\) for any \(n\), or else show by counterexample that it is not. In the latter case, why doesn't this contradict the theorem on chains in well-ordered sets?