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?

---

I didn't know where else to post this, but I found two typos in the text.

1) Page 31, about halfway down

\((x-1)^2-t=0\) should be \((x-1)^2-t^2=0\)

2) Page 59, first line

\(x^5yz^2\) should be \(x^5yz\)

---

I was also thinking about classifying the different orderings we've covered (lex, grlex & grevlex) by their criteria and generalizing from a combinatorial perspective.

A = "Alphabetical" order (\(x_1, x_2, \dots)\)

B = Total degree (high-to-low)

C = Degree of variable (high-to-low)

The priority of criteria will be a left-to-right listing of \(A,B,C\)

Reverse or inverse order (inv) will be denoted as \(A^{-1}, B^{-1}, C^{-1}\)

Lex = \(AC\) (total degree not relevant)

Grlex = \(BAC\)

Grevlex = \(BA^{-1}C^{-1}\)

Note that if A (lex) precedes B (total order), then B is irrelevant. Once we establish which variable comes first lexicographically, then we sort by that variable, tie going to order of that variable. Total degree never comes into play.

Ignoring inverses, we have:

AC

BAC

BCA

CA

CBA

Each criteria has two values, high-to-low, or low-to-high (inv).

This gives us a total of \(2(2^{2})+3(2^{3}) = 8+24 = 32\) distinct orderings with those criteria.

---

We were told that if a set has total order, and every finite subset has a smallest element, then it's well-ordered. However, any finite subset of \(Z_{n}\) has a smallest element, but since 0<n-1 and n-1<0 (since (n-1)+1 = 0) it doesn't obey trichotomy, so it's a well-ordered set that doesn't have total order. Is there an exception for finite cyclic sets?

Matthew.Lehman (talk)

Actually there is no standard order on \(Z_n\), essentially for the reason you've identified. (The relation you're thinking of isn't actually a partial order. If it were, then \(0\leq n-1\leq 0\) would force \(0 = n-1\) by antisymmetry.) - Steven.Jackson (talk) 17:07, 11 March 2013 (EDT)