Let be a positive natural number and let . Define a relation on by if the set is empty or, if nonempty with maximal element , we have .

- Prove that the grading of is an m-order. (See this previous exercise. Note that itself is not an m-order since, for example, is a chain with no lower bound.) Let where if and otherwise. Prove that if , then .

A monomial ordering induced by the grading of some is called a *grevlex* monomial order. (See this previous exercise.)

- Show that the grevlex ordering and the grlex ordering on with respect to are the same. Prove that the grevlex ordering on is not the grading of any lexicographic ordering.
- Sort , , , , , , , , , and under the grevlex ordering with respect to .

We begin with a lemma.

Lemma: Let be a linear order on which respects addition. Then the grading of , denoted , is an m-order. Proof: Certainly is linear and respects addition; it remains to be seen that is well-founded. To that end, let be a nonempty subset. Let consist of those elements such that is minimal. Certainly then every element of is less than every element of that is not in with respect to . Moreover, is necessarily finite and thus contains a minimal element, which is minimal in .

With this lemma in mind, we need to show that is a linear order which respects addition.

- (Reflexive) Certainly the set is empty. Thus .
- (Antisymmetric) Suppose and . If is empty, then we have . Suppose now that this set is nonempty with maximal element ; then we must have , a contradiction.
- (Transitive) Suppose and . If either of and is empty, then either or and certainly . Suppose both are nonempty with maximal elements and , respectively. Now and , and certainly and for and . If , then is maximal in the nonempty set , and we have . Similarly if .
- (Total) Let and . If is empty, then . If this set is nonempty, then it has a maximal element . Either or .
- (Respects addition) Let . If for all , then certainly . If there exists a maximal such that , then we also have maximal such that . Thus .

Thus the grading of is an m-order on . With defined as above, if , and is maximal in . Since and , we have .

Let and denote the grevlex and grlex orders on , respectively. Suppose . If , then . If , then we have b_1 < b_2$, as otherwise and . Then , and thus . Thus . Now suppose . Again, if then . If , then we have . Thus , and we have . Thus . Hence the grevlex and grlex orders on are the same.

There are six distinct lexicographic orders on ; one for each permutation of . We will let denote the lexicographic order which looks at the coordinate first, then , then . Let denote the grevlex order (with respect to the identity permutation of the indices). Note that . However, . Similarly, but , and while . So the grevlex order on is not the grading of any lexicographic order.

Finally, let denote the grevlex order on with respect to and note the following.

- since the total degrees are the same and .
- since the total degrees are the same, the -degrees agree, and the -degree on the left is zero and on the right is 2.
- since the total degree on the left is 4 while on the right is 3.
- since the total degree on the left is 3 while on the right is 2.
- since the total degrees are the same, the -degrees are the same, and the degree is smaller on the left.
- since the total degrees are the same and the -degree is smaller on the left.
- since the total degrees are the same and the -degree is smaller on the left.
- since the total degree is larger on the left.
- since the total degrees are the same, the -degrees are the same, and the degree is smaller on the left.