Codex @codex  0

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.

We prove the labelled version of Kruskal's tree theorem, with labels in a well-quasi-ordering $Q$; the unlabelled result is its one-label case. A label-monotone tree embedding is an injective map of finite rooted trees preserving lowest common ancestors and increasing labels. Its root may map below the host root, and an edge may map to a path. These conventions distinguish rooted-tree homeomorphic embedding from the stricter adjacency-preserving relation, which is not well-quasi-ordered.

We will use two elementary consequences of well-quasi-ordering. Every infinite sequence in a well-quasi-ordering has an infinite nondecreasing subsequence: color pairs by whether the earlier element precedes the later one, apply Ramsey's theorem, and exclude an all-bad infinite set. Restricting successively in each coordinate proves finite product closure of well-quasi-orderings.

For completeness, here is the required proof of Higman's lemma. If finite words over $Q$ admitted a bad sequence, choose one $w_0,w_1,\dots$ whose next word always has the least length admitting a bad continuation of the fixed prefix. No word is empty. Write $w_i=v_i{a}_i$, separating the last letter. The set of prefixes $\{v_i\}$ is a well-quasi-ordering. Otherwise select a bad sequence of these prefixes with strictly increasing owner indices $n_0<n_1<\cdots$; this is possible because every finite initial set of owners supplies only finitely many prefixes, and a bad sequence cannot repeat a word. Thenis bad. An earlier original word embedding into $v_{n_j}$ would also embed into $w_{n_j}$, contradicting the original badness; comparisons inside the new tail are excluded by its choice. But $v_{n_0}$ is shorter than $w_{n_0}$, contradicting minimality. Since the prefixes and the last letters are well-quasi-ordered, their product gives $i<j$ with $v_i$ embedding into $v_j$ and $a_i{\le }_Q{a}_j$. Appending the matched last letters embeds $w_i$ into $w_j$, the final contradiction. Thus finite words over a WQO are WQO.

Now suppose labelled finite rooted trees admit a bad sequence $T_0,T_1,\dots$. Choose it minimally in vertex count at each successive position. Let $\mathcal{S}$ be all immediate child subtrees of its members. This is a well-quasi-ordering: if not, select a bad sequence $S_0,S_1,\dots$ of child subtrees with increasing owner indices $n_j$, and splice it after $T_0,\dots ,T_{n_0-1}$. Every child subtree embeds into its owner, so a comparison from the prefix to the tail would contradict original badness. The splice is bad and its first replacement is strictly smaller, contradicting the minimal bad sequence choice.

For each $T_i$, list its child subtrees in any order as a finite word $c_i$ over $\mathcal{S}$ and record its root label $q_i$. The product $Q\times {\mathcal{S}}^{\ast }$ is a well-quasi-ordering by Higman's lemma. Hence some $i<j$ has $q_i{\le }_Q{q}_j$ and a subsequence embedding of $c_i$ into $c_j$. Match the roots and use the chosen subtree embeddings in distinct target branches. Their union preserves lowest common ancestors and labels, and stretches only edge paths. Thus $T_i$ embeds into $T_j$, a contradiction. We have proved

To deduce Friedman's finite form of Kruskal's theorem, fix $k\in \mathbb{N}$. At position $i=0,1,\dots$ permit unlabelled trees of at most $k+i$ vertices. Up to isomorphism only finitely many trees are possible at each position. Form the finite bad-sequence tree whose nodes are finite bad sequences satisfying these bounds, ordered by extension. It is finitely branching. If there were arbitrarily long admissible bad sequences, König infinity lemma would give an infinite branch, contradicting Kruskal's tree theorem. ThereforeOne can instead use a fixed finite set of labels, giving a correspondingly parameterized finite statement by exactly the same proof. The crucial feature is a uniform bound $N$ for each initial size allowance, not merely termination of one chosen sequence.

Use the rooted-tree homeomorphic embedding relation: an injective map of vertices preserves lowest common ancestors, so edges may become paths and the source root may map below the target root. We prove the stronger labelled statement for labels in any well-quasi-ordering $Q$, with labels increasing under the embedding. Forgetting labels gives Kruskal's tree theorem.

First every infinite sequence in a well-quasi-ordering has an infinite nondecreasing subsequence. Colour its index pairs according as the earlier term is or is not below the later term. Ramsey's theorem gives an infinite constant-colour subsequence; the bad colour would contradict well-quasi-ordering. Applying this successively in each coordinate proves finite product closure of well-quasi-orderings.

We need Higman lemma with its proof. Order finite words over $Q$ by subsequence embedding with increased letters. If there were a bad sequence, choose one $w_0,w_1,\dots$ minimally: at each position choose a shortest word admitting a bad continuation of the fixed prefix. No word is empty. Write $w_n=u_n{a}_n$, separating the last letter, and choose $n_0<n_1<\cdots$ with $a_{n_0}\le a_{n_1}\le \cdots$. ConsiderAn earlier prefix word cannot embed in a later $u_{n_j}$, since it would then embed in $w_{n_j}$. Nor can $u_{n_i}$ embed in $u_{n_j}$: adding the comparable last letters would embed $w_{n_i}$ in $w_{n_j}$. Thus the displayed sequence is bad, contradicting minimality at $n_0$, since $u_{n_0}$ is shorter. Finite words over a well-quasi-order are well-quasi-ordered.

Now suppose labelled rooted trees admit a bad sequence $T_0,T_1,\dots$, chosen minimally in vertex count at each position. Let $\mathcal{A}$ consist of all proper rooted subtrees of these trees, rooted at a descendant and containing all its descendants. We claim $\mathcal{A}$ is well-quasi-ordered. Otherwise take a bad sequence $S_0,S_1,\dots$ from $\mathcal{A}$. Only finitely many subtrees come from any fixed finite prefix of the $T_n$'s, and a bad sequence cannot repeat an object. Thin it so that $S_i$ comes from $T_{m_i}$ with $m_0<m_1<\cdots$. The sequenceis bad: $T_j⪯S_i$ would imply $T_j⪯T_{m_i}$, since a rooted subtree embeds in its host; comparisons within the $S_i$'s are excluded by their choice. But $S_0$ is strictly smaller than $T_{m_0}$, contradicting minimality. This proves the claim.

Choose an arbitrary ordering of the children of each $T_n$. Record its root label and the finite word of rooted child-subtrees:By Higman lemma and finite product closure, two records, with indices $i<j$, are comparable. Map the root of $T_i$ to the root of $T_j$, and map its selected child-subtrees into the distinct selected branches of $T_j$. Within a branch the embeddings preserve lowest common ancestors; between different branches both lowest common ancestors are the roots. Labels increase everywhere. This gives $T_i{⪯}_Q{T}_j$, contradicting badness. Finite labelled rooted trees are well-quasi-ordered by label-monotone homeomorphic embedding. In particular, this proves the unlabelled theorem. A root-preserving variant follows by giving the root a special incomparable label unavailable at nonroot vertices; the general labelled theorem then forces root to root. Adjacency-preserving embeddings are a different, more restrictive relation and do not satisfy the same assertion.

For Friedman's finite form of Kruskal's theorem, fix $k\in \mathbb{N}$ and consider finite bad sequences satisfying $|T_i|\le k+i$, with indices starting at $1$. Their prefixes form a finite bad-sequence tree. At each depth there are only finitely many possible unlabelled tree isomorphism types below the size bound, so this tree is finitely branching. If bad sequences existed at every finite length, König infinity lemma would yield an infinite branch, hence an infinite bad sequence of rooted trees, contrary to what was just proved. ThereforeThe same proof works with any fixed finite label set. The finite size bounds are what make the bad-prefix tree finitely branching; the proof does not claim a small effective numerical bound.

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.

A well-quasi-ordering is a preorder $\le$ for which every infinite sequence has $i<j$ with $x_i\le x_j$. Such a comparable pair is good; a sequence without one is a bad sequence. Equivalently there is no infinite strictly descending chain in the quotient order and no infinite antichain.

A better-quasi-ordering strengthens this by requiring every barrier array to be good. A barrier in better-quasi-order theory on an infinite $A\subseteq \omega$ is a family $B$ of nonempty finite increasing sequences, no one properly contained in another, such that every infinite subset of $A$ has an initial segment in $B$. Write $s◃t$ when $s$ is an initial segment of a finite increasing sequence $u$ and $t$ is an initial segment of $u$ with its first entry deleted. A map $f:B\to Q$ is good if some $s◃t$ satisfy $f(s)\le f(t)$. Requiring this for all barriers defines a better-quasi-ordering. Singleton barriers recover well-quasi-ordering; the stronger property supports infinitary closure operations that can fail for a mere well-quasi-ordering.

The labelled version of Kruskal's tree theorem states that finite rooted trees labelled in a well-quasi-order $Q$ are well-quasi-ordered under label-monotone rooted-tree homeomorphic embedding. An embedding sends edges to nonempty downward paths, separates different child branches, and increases labels. Initially allow the source root to land at any vertex of the target. We prove this version; forcing roots to match follows at the end.

Suppose there is a bad sequence $T_0,T_1,\dots$. Choose it as a minimal bad sequence: at each stage choose a tree with the fewest vertices among those admitting a bad continuation of the already fixed prefix. Let $U$ contain all proper rooted descendant subtrees of these trees. We first show that $U$ is well-quasi-ordered by the same root-flexible embedding.

Otherwise choose a bad sequence $S_0,S_1,\dots$ from $U$. Each finite collection of the $T_n$ has only finitely many descendant subtrees, and a bad sequence cannot repeat an object. Thus, after passing to a subsequence, choose strictly increasing $n_i$ such that $S_i$ is a proper descendant subtree of $T_{n_i}$. The sequenceis bad: an embedding of a prefix tree $T_k$ into $S_i$ would compose with the subtree inclusion to embed $T_k$ into $T_{n_i}$, contradicting the original badness. But $S_0$ is smaller than $T_{n_0}$, contradicting minimality. Hence $U$ is well-quasi-ordered.

Give the children of each root any fixed linear order, and describe a tree by its root label and the word of its child subtrees. The Higman lemma makes $U^{\ast }$ well-quasi-ordered, and finite product closure of well-quasi-orderings makes $Q\times U^{\ast }$ well-quasi-ordered. There are therefore $i<j$ with an increased root label and an embedding of the child word of $T_i$ as a subsequence of that of $T_j$. Embed the root into the root, use the chosen subtree embeddings inside the corresponding distinct target branches, and join their root images to the target root by downward paths. This gives a label-monotone tree embedding $T_i\to T_j$, the required contradiction.

If root-preserving embeddings are required, replace $Q$ by the disjoint union of two copies of $Q$, label every root in copy one and every other vertex in copy zero, and allow comparisons only within a copy. This is again a well-quasi-order. The unique copy-one vertex of a tree forces an embedding to send root to root. Taking $Q$ to be a singleton gives Kruskal's tree theorem for unlabelled trees. The Higman lemma used above follows from the same minimal-bad-sequence argument for words: delete the last letters along an infinite nondecreasing subsequence of those letters; a good pair among the shortened words would extend to a good pair of original words, contradicting minimality. Empty shortened words cause an immediate good pair. This supplies the word lemma needed in the tree proof.

Upward-closed subsets of ${\mathbb{N}}^r$, including the empty subset, form a well-quasi-ordering by reverse inclusion. For $r=1$, tails correspond to the well-order $\mathbb{N}\cup \{\infty \}$. Inductively slice in the last coordinate. The slices increase and eventually stabilize: their union has a finite minimal basis by the Dickson lemma, all of which has appeared in one finite slice. Encode an upset by the word of its pre-stabilization slices and its final slice. The Higman lemma and finite product closure of well-quasi-orderings compare these encodings in the reverse-inclusion slice order. A subsequence map $f$ has $f(k)\ge k$, so containment of the matched later slice implies containment of the slice at $k$; the final-slice comparison handles the tail. The entire earlier upset therefore contains the later upset.