Exercise 2.2.9

Proof.

(a)

For the lexicographic order, $x_1^{a_1}\cdots x_n^{a_n}<x_1^{b_1}\cdots x_n^{b_n}$ is equivalent by definition to

$$\exists <!--\; FUNCTION\; APPLICATION\; -->j\in [1,n],(\forall <!--\; FUNCTION\; APPLICATION\; -->i\in \mathbb{N},1\le i<j\Rightarrow a_i=b_i)\mathrm{and}{a}_j<b_j.$$

(The property $(\forall <!--\; FUNCTION\; APPLICATION\; -->i\in \mathbb{N},1\le i<j\Rightarrow a_i=b_i)$ is automatically verified for $j=1$, since $1\le i<j$ is false, so the implication is true.)

In informal terms :

$a_1<b_1$ or ( $a_1=b_1$ and $a_2<b_2$) or ( $a_1=b_1,a_2=b_2$ and $a_3<b_3$) or $\text{…}$

In other words, $x_1^{a_1}\cdots x_n^{a_n}<x_1^{b_1}\cdots x_n^{b_n}$ iff the first subscript $i$ such that $a_i\ne b_i$ exists and verifies $a_i<b_i$.

This relation $\le$ is a total order.

(b)

The monomials less than $x_1=x_1^1{x}_2^0\cdots x_n^0$ for the lexicographic order contain the monomials $x_1^0{x}_2^{a_2}\dots x_n^{a_n}$, where $a_2,\cdots ,a_n$ are arbitrary integers in $\mathbb{N}={\mathbb{Z}}_{\ge 0}$. There are infinitely many such monomials.

(c)

We show this property by induction on the numbers of variables $x_i$.

If there is a unique variable, say $x_1$, then a strictly decreasing sequence of monomial $x_1^{n_0}>x_1^{n_2}>\cdots$, with $n_i\in \mathbb{N}$, is such that $n_0>n_1>\cdots$: such a sequence is necessary finite. This is a property of the natural order in $\mathbb{N}$: Every non empty subset of $\mathbb{N}$ has a smallest element, so a strictly decreasing infinite sequence in $\mathbb{N}$ doesn’t exist.

Suppose that this property is true for $n-1$ variables, say $x_2,\cdots ,x_n$. Consider the sequence

$$x_1^{i_{1,1}}\cdots x_n^{i_{1,n}}>x_1^{i_{2,1}}\cdots x_n^{i_{2,n}}>\cdots >x_1^{i_{k,1}}\cdots x_n^{i_{k,n}}>\cdots .$$

By the induction hypothesis, for each fixed exponent $i_{k,1}$ of $x_1$, there exists only finitely monomial in this sequence with this exponent for $x_1$. As these exponents are at most $i_{1,1}$, the sequence is finite and the induction is done.

(d)

The beginning of the demonstration of Theorem 2.2.2 remains unchanged with the lexicographic order. Then we builds a sequence

$$f,f_1=f-\mathit{cg},f_2=f-\mathit{cg}-c_1{g}_1,\dots$$

of polynomials whose leading terms constitute a strictly decreasing sequence for this order, until $f_i=0$. By (c), this sequence is finite, so one polynomial $f_i$ is zero, which completes the algorithm.