Past exam of the mathematics course of the University of Cambridge / 2001 / iii / Paper 18 / 1

Use the reverse absorption order on the incline:This is exactly the relation given by the pairs $(x+y,x)$. Indeed, if $a=x+y$ and $b=x$, then $a+b=x+y+x=a$ by additive idempotence, associativity and commutativity. Conversely $a+b=a$ expresses $a$ as $b+a$, so $(a,b)$ is one of these pairs.

Additive idempotence gives $a+a=a$, hence reflexivity. If $a+b=a$ and $b+c=b$, thenso the relation is transitive. In fact it is antisymmetric as well: $a+b=a$ and $b+a=b$, together with commutativity, imply $a=b$. Thus the relation is a partial order, and therefore a quasi-order. It is the reverse of the usual join order of an incline; keeping this reversal is essential for the well-quasi-ordering conclusion.

Both operations are order-preserving for this order. If $a⪯b$, then $(a+c)+(b+c)=a+c$ by additive idempotence, while distributivity gives $ac+bc=(a+b)c=ac$. The multiplicative absorption identity also saysThus multiplying a monomial by another factor moves upward in the reverse absorption order.

Suppose the incline is generated by $x_1,\dots ,x_r$. Repeated distributivity, followed by commutativity and additive idempotence, expresses every element as a finite nonempty sumNo multiplicative identity is assumed: a zero exponent means that the corresponding generator is omitted, and every displayed monomial has at least one factor. Different supports may represent the same element; uniqueness is unnecessary.

Associate to $A$ its upward-closed exponent setIf $U_A\supseteq U_B$, each monomial of $f_B$ is either equal to, or a multiplicative extension of, a monomial of $f_A$. It is absorbed by that earlier monomial, and hence by the full sum $f_A$. Adding the terms of $f_B$ one at a time givesFor equal exponent vectors the first absorption is additive idempotence; for strictly larger vectors it is the incline's multiplicative absorption. Thus the issue is to prove that exponent upsets are well-quasi-ordered by reverse inclusion, not merely to apply Dickson's lemma to individual exponents.

We prove the reverse-inclusion well-quasi-ordering of monomial ideals, equivalently of all upward-closed subsets of ${\mathbb{N}}^r$, by induction on $r$. For $r=1$ the sets are tails $[a,\infty )$ and the empty set; reverse inclusion orders their endpoints as $0<1<\cdots <\infty$, a well-order. The case $r=0$, if needed for the induction, is just a finite family.

For an upset $U\subseteq {\mathbb{N}}^{r+1}$, let $U_k=\{\alpha :(\alpha ,k)\in U\}$. These are upsets of ${\mathbb{N}}^r$ and satisfy $U_0\subseteq U_1\subseteq \cdots$. They stabilize. Indeed the union $U_{\infty }$ has a finite minimal basis by Dickson's lemma: an infinite set of minimal elements would be an antichain in the componentwise well-quasi-ordering of ${\mathbb{N}}^r$. Each basis element appears in some slice, and after the largest of these finitely many indices the slice contains the entire upset $U_{\infty }$.

Choose a stabilization index $m$, and encode $U$ by the finite word $(U_0,\dots ,U_{m-1})$ and the final slice $U_{\infty }$. The induction hypothesis makes slices a well-quasi-ordering by reverse inclusion. Higman's lemma, proved in Question 3 below, makes their finite words a well-quasi-ordering; finite product closure of well-quasi-orderings also compares the final slices. Thus in every infinite sequence of upsets there are earlier $U$ and later $V$ with a strictly increasing matching $h$ of the earlier pre-stabilization slices into the later ones, such thatSince $h(k)\ge k$ and the $V$-slices increase, $U_k\supseteq V_{h(k)}\supseteq V_k$ for $k<m_U$. For $k\ge m_U$, $U_k=U_{\infty }\supseteq V_{\infty }\supseteq V_k$. Therefore $U\supseteq V$, completing the induction.

Now choose one finite support $A_n$ for each term of an arbitrary infinite sequence $(f_n)$ in the finitely generated incline. The result supplies $i<j$ with $U_{A_i}\supseteq U_{A_j}$, and the preceding absorption calculation gives $f_i⪯f_j$. Hence every finitely generated incline is well-quasi-ordered by the specified reverse absorption order. The proof allows all additional algebraic identifications among the generators.