How do we know that the algorithm for polynomial division terminates after finitely many steps?

Question

Recently I have been relearning Grobner basis's and as such I had another look at the proof of the algorithm for polynomial division in multiple variables. However, I'm struggling to see exactly why we can ensure that the algorithm terminates after finitely many steps. In particular, every argument I can find says that after each step of the algorithm the new polynomial has leading term of monomial order strictly less than the old one and hence must terminate. However, I don't see how this ensures it terminates after finite steps since unlike the usual ordering on $\mathbb{N}_0$, under monomial orders elements don't necessarily have finitely many elements strictly less than them.

For more detail about what I mean, fix a monomial order $<$ on $k[x_1,\cdots, x_n]$. Then to divide a polynomial $f$ by polynomials $f_1,\cdots, f_m$ in $k[x_1,\cdots , x_n]$ the division algorithm is usually given by:

1. Set polynomials $q_1=\cdots=q_m=r=0.$
2. If $f=0$ stop. Otherwise, for each $i=1,\cdots, m$ check if $LT(f_i)$ divides $LT(f)$. If so, replace $f$ by $f-\frac{LT(f)}{LT(f_i)}f_i$ and $q_i$ by $q_i + \frac{LT(f)}{LT(f_i)}$ and then return to the beginning of step 2. If no $LT(f_i)$ divides $LT(f)$ then go to step 3.
3. Add $LT(f)$ to $r$ and replace $f$ by $f-LT(f)$. Go to step 2.

Every time $f$ is replaced, it is done so with a polynomial with strictly smaller leading term. Every proof I have then seen will say something along the lines of that since monomial orders are well orders the process will terminate. I have taken this to mean that if we denote the intermediate $f$'s in the algorithm by $\{g_i\}_{i\in I}$ for some indexing set $I$, then due to well ordering this has a minimal element and so we can conclude the algorithm terminates since if it didn't no minimal element would exist. However I fail to see how this would imply the set is finite.

I don't have much experience with well orderings, so perhaps this is fairly simple but any help on clarifying this point for me would be greatly appreciated.

Answer 1

It's a little hard to wrap your head around, but every strictly decreasing sequence in a well ordering is finite. This is true even for gargantuan ordinals. For suppose $a_1,a_2,\ldots$ is an infinite decreasing sequence. The set of values $\{a_i\}$ is a subset of a well ordering, so it has a least element. This least value must be achieved at some $a_N$. Then $a_n=a_N$ for all $n\geq N$ because the sequence is decreasing.

Answer 2

Indeed the termination is non-trivial. It is asserted by Dickson's lemma and/or Hilbert's basis theorem. They boil down to the following:

If you consider the ideal consisting of the leading monomials generated throughout Buchberger's algorithm, you have an ascending chain of ideals in $R=k[x_1,\dots,x_n]$. Since a polynomial ring over a Noetherian ring (in particular, over a field $k$) is again Noetherian, this ascending chain will eventually become stationary. Hence, no additional leading monomials will be required from this point.