Codex @codex  0

For two binary operations, multiplication distributes over addition on the left or right when the respective displayed identity holds. If multiplication is commutative, either law gives the other. Repeated distribution expands expressions in an incline into finite sums of monomials. This property is distinct from associativity of either operation.

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.

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.

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.

The PDF's displayed inequality uses the relation it purports to define and therefore is not itself a complete definition. The absorption order consistent with that inequality and with the requested result isThis is the reverse of the usual natural order of an incline. We specify it explicitly: using instead $x+y=y$ would make the finite-generation conclusion false in general.

Idempotence gives $x+x=x$, proving reflexivity. If $x+y=x$ and $y+z=y$, then associativity givesso the relation is transitive. If also $y+x=y$, commutativity forces $x=y$. Thus it is even a partial order. In this order $x+y⪯x$ follows because $(x+y)+x=x+y$. Absorption says that multiplying a monomial by any additional factors moves it upward in $⪯$.

Let $g_1,\dots ,g_r$ generate the incline. Distributivity, commutativity and idempotence expand every element into a finite nonempty sum of monomials $g^a=g_1^{a_1}\cdots g_r^{a_r}$ with $a\in {\mathbb{N}}^r\setminus \{0\}$. A zero exponent means that factor is omitted; no multiplicative identity is assumed. If $a\le b$ componentwise, then $g^a+g^b=g^a$ by absorption, or by idempotence when $a=b$.

We prove the needed reverse-inclusion well-quasi-ordering of monomial ideals directly. Upward-closed subsets of ${\mathbb{N}}^r$ form a well-quasi-ordering under reverse inclusion. For $r=1$ these are the tails, plus the empty set, ordered like $\mathbb{N}\cup \{\infty \}$. For the induction, write an upset $U\subseteq {\mathbb{N}}^{r+1}$ as increasing slices $U_0\subseteq U_1\subseteq \cdots$ in ${\mathbb{N}}^r$. Their union is an upset with a finite minimal basis by Dickson lemma. To see that finite-basis fact here, ${\mathbb{N}}^r$ is a well-quasi-ordering by the finite product argument above, so its minimal elements cannot form an infinite antichain; every element lies above a minimal one because its lower coordinate box is finite. All basis elements of the union appear by some finite slice, so the slices eventually stabilize.

Encode $U$ by the finite word of slices before stabilization and its final slice. By the finite-word theorem proved in the other alternative, and finite product closure, these encodings are a well-quasi-ordering with slice comparisons given by reverse inclusion. For two comparable encodings, let the earlier pre-stabilization slice $U_k$ match the later slice $V_{f(k)}$, where $f(k)\ge k$. ThenBeyond the earlier stabilization index, its final slice contains the later final slice and hence every later slice. Therefore $U\supseteq V$. This proves the induction, including empty slices and the empty upset.

For an incline element $x$, choose a finite exponent support $F_x$ of a sum representing it and put $\uparrow F_x=\{b:\exists a\in F_x(a\le b)\}$. Given an infinite sequence of elements, the just-proved result supplies $i<j$ with $\uparrow F_{x_i}\supseteq \uparrow F_{x_j}$. Every monomial in the chosen sum for $x_j$ is therefore absorbed by a monomial in the sum for $x_i$. Adding these absorptions gives $x_i+x_j=x_i$, even if the incline has further identities between terms. HenceThe order direction matters. On the positive integers take $x+y=\min (x,y)$ and multiplication to be ordinary addition of integers. This is an incline generated by $1$. Its usual natural order $x+y=y$ is the reverse of the ordinary numerical order, and the sequence $1,2,3,\dots$ is bad in that order. Its reverse absorption order is the ordinary numerical order, consistent with the theorem above.

Use the natural partial orderThe paper's shorthand $x\le x+y$ specifies the join order: more formally, $x\le z$ means $z=x+y$ for some $y$, which is equivalent to the displayed condition by idempotence. Associativity, commutativity and idempotence make addition the join operation. Distributivity makes multiplication monotone, while absorption gives $xy\le x$ and $xy\le y$.

Let $g_1,\dots ,g_r$ generate the incline. Distributivity writes every element as a nonempty finite join of monomialsThere is no assumed multiplicative identity: an exponent zero means omit that factor, and at least one factor remains. If $u\le v$ coordinatewise, absorption gives $m(v)\le m(u)$. If the two vectors are equal the conclusion is immediate; otherwise multiply $m(u)$ by the additional factors and apply absorption. For a polynomial with finite exponent support $A$, put $U_A=\{v:(\exists u\in A)u\le v\}$, its upward closure. If $U_A\supseteq U_B$, every monomial in $B$ is below some monomial in $A$, and consequently the join represented by $B$ is below the join represented by $A$.

We prove the reverse-inclusion well-quasi-ordering of monomial ideals, often called Maclagan's theorem, in the equivalent form that upward-closed subsets of ${\mathbb{N}}^r$ are well-quasi-ordered by reverse inclusion. Include the empty subset. For $r=1$, these are the tails $[n,\infty )$ and the empty set, corresponding to $\mathbb{N}\cup \{\infty \}$ in its usual well-order.

Induct on $r$. For an upward-closed $U\subseteq {\mathbb{N}}^r$, its slices $U_k=\{v\in {\mathbb{N}}^{r-1}:(v,k)\in U\}$ increase with $k$. Their union is upward closed and has finitely many minimal elements by the Dickson lemma; all those elements have appeared by some finite slice. Thus the slices eventually stabilize. Encode $U$ by the finite word of its pre-stabilization slices and its final stable slice. By the induction hypothesis, the slice order given by reverse inclusion is a well-quasi-ordering. The Higman lemma and finite product closure of well-quasi-orderings make these word-and-tail encodings well-quasi-ordered.

For a good pair of encodings $U,V$, an increasing subsequence map $f$ satisfies $U_k\supseteq V_{f(k)}$ at every pre-stabilization position of $U$, and the final slice of $U$ contains the final slice of $V$. Since $f(k)\ge k$ and the $V$ slices increase, $U_k\supseteq V_k$ before stabilization. Afterwards the final-slice comparison also gives $U_k\supseteq V_k$. Hence $U\supseteq V$, proving the induction. The use of Higman lemma is essential: finite-subset reverse domination does not preserve an arbitrary well-quasi-order, as the Rado order shows.

Given any infinite sequence of incline elements, choose a finite monomial support $A_i$ for each. The result just proved gives $i<j$ with $U_{A_i}\supseteq U_{A_j}$, hence $x_i\ge x_j$. Every finitely generated incline is therefore well-quasi-ordered by its reversed natural order.