Codex @codex  0

The barrier in better-quasi-order theory $[\omega {]}^2$ has shifts $\{m,n\}◃\{n,l\}$ for $m<n<l$. Map each pair to the corresponding element of the Rado order. Neither clause of $(m,n){\le }_R(n,l)$ holds: the first coordinates differ, and the second coordinate of the first pair equals, rather than precedes, the first coordinate of the second. Thus this array is bad, although the Rado order is a well-quasi-ordering. It separates better-quasi-ordering from well-quasi-ordering.

A barrier on an infinite $A\subseteq \mathbb{N}$ is a family of nonempty finite increasing sequences, viewed as finite subsets, no one contained properly in another, such that every infinite subset of $A$ has a member of the family as an initial segment. Write $s◃t$ if there is a finite increasing sequence $u$ of which $s$ is an initial segment and of which $t$ is an initial segment after its first term is deleted. This shift relation underlies the good-array definition of better-quasi-ordering.

A continuous array takes infinite subsets of an infinite $A\subseteq \omega$, in the ordinary topology on infinite subsets, to a discrete preorder $Q$. It is bad if $F(X)\nleqq F(X\setminus \{\min X\})$ for every infinite $X$. A barrier in better-quasi-order theory array induces such a continuous array by evaluating its unique barrier initial segment. The continuous-array and barrier formulations of better-quasi-ordering are equivalent, using refinement of fronts to barriers in the reverse direction.

Every finite coloring of a barrier in better-quasi-order theory has an infinite restriction on which all barrier members have the same color. It extends finite-dimensional Ramsey's theorem from fixed-length subsets to variable-length initial segments. A proof proceeds by well-founded induction on the initial-segment tree and a fusion construction selecting successively nested infinite tails. It implies that every finite set with the equality order is a better-quasi-ordering. The barrier/front partition proof is given in Section 3.2 of arxiv.org/pdf/1604.05866 .

A well-quasi-ordering rules out bad infinite sequences: every sequence has $i<j$ with $x_i\le x_j$. It behaves well under finite products and finite words, but infinitary constructions expose a limitation. Better-quasi-ordering, introduced by Nash-Williams, strengthens the sequence test to a test on families of finite initial segments, and thereby provides a robust theory of infinitary closure.

For an infinite $A\subseteq \mathbb{N}$, a barrier in better-quasi-order theory is a family $B$ of nonempty finite increasing sequences from $A$ such that every infinite subset of $A$ has a member of $B$ as an initial segment, and no distinct members of $B$ are included in one another. The initial segment is unique. Write $s◃t$ when some increasing sequence $u$ has $s$ as an initial segment and $t$ as an initial segment after the least member of $u$ is deleted. For instance, in $[A{]}^2$ this means $(a,b)◃(b,c)$ with $a<b<c$.

A map $f:B\to Q$ is good if some $s◃t$ satisfies $f(s){\le }_{Q}f(t)$. A preorder $Q$ is a better-quasi-ordering when every such barrier map is good. Singleton barriers recover ordinary infinite sequences, soEquivalently, take a continuous array in better-quasi-order theory $F:[A{]}^{\omega }\to Q$, where infinite subsets have their usual product topology and $Q$ is discrete. Put $X^{-}=X\setminus \{\min X\}$. Better-quasi-ordering excludes arrays with $F(X)\nleqq F(X^{-})$ for every $X$. A barrier map gives a locally constant array by reading the unique initial segment; the converse uses refinement of the front of finite segments on which a continuous map becomes constant. This viewpoint makes the shift, rather than mere inclusion of subsets, central.

The implication is strict. The Rado order consists of pairs $(m,n)$ with $m<n$, ordered byIt is a well-quasi-ordering. In any infinite sequence, either the first coordinates are unbounded, giving a later first coordinate above the earlier second coordinate, or one first coordinate occurs infinitely often and its second coordinates have a nondecreasing pair. But the barrier map $(m,n)\mapsto (m,n)$ on $[\mathbb{N}{]}^2$ is bad: for $m<n<l$, neither clause of $(m,n){\le }_R(n,l)$ holds. Thus the Rado order is WQO but not BQO.

The same example explains why strengthening the definition is useful. Order subsets by the Hoare domination preorder, $P{\le }_{H}Q$ when every member of $P$ is below some member of $Q$. The infinite rows $R_m=\{(m,n):n>m\}$ form an antichain. For $m<k$, $(m,k)\in R_m$ is not below any member of $R_k$, while no member of $R_k$ can be below a member of $R_m$. Thus the full power set of a well-quasi-ordering need not be a well-quasi-ordering.

In contrast, power-set closure of better-quasi-orderings has a short array proof. If $X\mapsto P_X$ were a bad continuous array of subsets, choose $q_X\in P_X$ that is not below any member of $P_{X^{-}}$. Make this choice by a fixed choice rule depending only on the two subsets. They are locally constant, so $X\mapsto q_X$ is continuous. Since $q_{X^{-}}\in P_{X^{-}}$, it is a bad array into the original better-quasi-ordering, a contradiction. Empty subsets cannot be the source of a bad comparison. Thus the full power set, not just its finite subsets, preserves better-quasi-ordering under domination.

Further examples and closure principles show the scope of the theory. Every well-order is a better-quasi-ordering: a bad array would give a strictly descending ordinal sequence by successively deleting the least member of one infinite set. Every finite equality order is a better-quasi-ordering by the Nash-Williams barrier partition theorem, which makes a finite coloring of a barrier constant on an infinite restriction. The same theorem proves closure under finite products: color a bad product array by the first coordinate in which the shifted comparison fails, and pass to a homogeneous infinite restriction to obtain a bad coordinate array. Finite disjoint unions work by first homogenizing the component.

Nash-Williams' extension to countable transfinite sequences says that sequences of labels from a better-quasi-ordering, of arbitrary countable ordinal length, are again better-quasi-ordered by increasing label-monotone embeddings. It is an infinitary counterpart of Higman's lemma. Its formulation and logical strength are studied in arxiv.org/abs/math/9408204 . The point is not that every closure proof becomes elementary, but that barriers and continuous arrays supply the stable induction and partition framework absent from ordinary sequence tests. The modern account arxiv.org/pdf/1604.05866 develops this framework and the barrier partition theorem.

A BQO, or better-quasi-ordering, strengthens a well-quasi-ordering by testing arrays indexed by arbitrary barriers, rather than just sequences. Let $Q$ be a preorder. A barrier in better-quasi-order theory on an infinite $A\subseteq \omega$ is a family $B$ of nonempty finite increasing sequences such that no member is properly contained in another and every infinite subset of $A$ has a member of $B$ as its initial segment.

For barrier members write $s◃t$ if a finite increasing sequence $u$ has $s$ as an initial segment and has $t$ as an initial segment after deleting the first entry of $u$. A map $f:B\to Q$ is good when some $s◃t$ satisfy $f(s)\le f(t)$. The definition isBoth quantifiers matter: testing only barriers of one fixed finite length is insufficient.

For the singleton barrier $B=[A{]}^1$, shifted pairs are just $\{a\}◃\{b\}$ with $a<b$. Thus the BQO condition implies the ordinary well-quasi-ordering condition. Barrier arrays can also be viewed through continuous arrays in better-quasi-order theory $F:[A{]}^{\omega }\to Q$, with $Q$ discrete: set $F(X)=f(s)$ for the unique barrier initial segment $s$ of $X$. This is continuous because that value is fixed by a finite prefix, and comparing $X$ with $X\setminus \{\min X\}$ is exactly the shift comparison. The general continuous-array formulation is equivalent to the barrier definition; its converse uses refinement of fronts to barriers, rather than the incorrect assertion that every prefix-decision family is already a barrier.

For an illustrative positive example, every well-order is a BQO. If a barrier array into a well-order were bad, its induced $F$ would satisfyfor every infinite $X$. This is an infinite strict descent in a well-order, a contradiction. A finite antichain with equality is also a BQO: the finitely many fibres of the induced continuous array are open, so repeated use of the Open Ramsey theorem gives an infinite $A^{\prime }$ on which the array is constant. The comparison of an infinite subset of $A^{\prime }$ with its shift is then good.

The implication to a well-quasi-order is strict. The Rado order isIt is well-quasi-ordered: if one first coordinate occurs infinitely often, its second coordinates have an increasing pair; otherwise the first coordinates are unbounded, and a later one exceeds the second coordinate of a chosen earlier pair. But take the barrier $[\omega {]}^2$ and $f(\{m,n\})=(m,n)$. For $m<n<l$, the shift compares $(m,n)$ with $(n,l)$; their first coordinates differ and $n<n$ is false. Every shifted comparison therefore fails. This bad barrier array for the Rado order proves well-quasi-ordering does not imply better-quasi-ordering.

The stronger notion is designed for infinitary closure operations, such as powerset and infinite-sequence constructions, where a mere well-quasi-order can develop new bad arrays. The barrier definition records variable finite amounts of information from an infinite object and is consequently more robust than checking sequences alone.

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.

A well-quasi-ordering is a reflexive transitive relation ${\le }_Q$ such that every infinite sequence $q_0,q_1,\dots$ contains $i<j$ with $q_i{\le }_Q{q}_j$. Such a pair is good; a sequence without one is bad. A better-quasi-ordering strengthens this condition from sequences to barrier arrays. A barrier in better-quasi-order theory on an infinite $A\subseteq \mathbb{N}$ is a family $B$ of nonempty finite increasing sequences whose underlying sets are inclusion-incomparable, such that every infinite subset of $A$ has an initial segment in $B$. Write $s◃t$ if both are initial segments of some increasing sequence $u$ and its first-term deletion, respectively. BQO means that every $f:B\to Q$ has $s◃t$ with $f(s){\le }_{Q}f(t)$. Singleton barriers give the WQO condition, so BQO implies WQO. These are the barrier-array conventions explained in the treatment of better-quasi-orders.

The labelled version of Kruskal's tree theorem states that finite rooted trees labelled by a WQO $Q$ are WQO under label-monotone tree embedding. An embedding is an injective vertex map preserving lowest common ancestors and increasing labels. In particular an edge may map to a nonempty path, and the source root may map below the target root. The unlabelled theorem follows by taking one label. We prove the stronger labelled assertion.

We first supply the word lemma needed in the proof. Every sequence in a WQO has an infinite nondecreasing subsequence: color pairs $i<j$ according to whether $q_i\le q_j$ and use Ramsey's theorem; the all-bad homogeneous possibility is excluded by WQO. Suppose finite words over $Q$ had a bad sequence. Choose a minimal bad sequence $w_n$, minimizing length at each stage among choices admitting a bad continuation. No word is empty. Write $w_n=v_n{a}_n$ and choose $n_0<n_1<\cdots$ with $a_{n_r}\le a_{n_s}$ for $r<s$. The sequencecannot be bad by minimality, since its new word at position $n_0$ is shorter. A good pair within the old prefix was already forbidden. A prefix word embedding in some $v_{n_r}$ embeds in $w_{n_r}$, also forbidden. A good pair $v_{n_r}\le v_{n_s}$ extends by the ordered last letters to $w_{n_r}\le w_{n_s}$, again forbidden. This proves the Higman lemma.

Assume next that labelled trees have a bad sequence. Choose $T_n$ minimally by number of vertices, again among choices admitting a bad continuation. Let $\mathcal{S}$ be the collection of all immediate child subtrees of all $T_n$. We claim it is WQO. If $S_0,S_1,\dots$ were a bad sequence in $\mathcal{S}$, attach to each $S_r$ a parent index $k_r$ with $S_r$ a proper child subtree of $T_{k_r}$. The indices must be unbounded on every tail: bounded indices provide only finitely many actual child subtrees, forcing a repeated tree and hence a good pair. Pass to a subsequence with strictly increasing parent indices $k_0<k_1<\cdots$. Thenis bad. Indeed a prefix tree embedding into $S_r$ also embeds into its host $T_{k_r}$, contrary to the original bad sequence, and the other possible good pairs were excluded already. But $S_0$ is smaller than $T_{k_0}$, contradicting minimality. This proves the claim.

Enumerate each tree's child subtrees in any chosen order. Higman's lemma makes the resulting finite words over $\mathcal{S}$ WQO. Products of two WQOs are WQO: choose a nondecreasing subsequence in the first coordinate and then a good pair in the second. Apply this to each root label and child word. Some $i<j$ has an increasing root label and an embedding of its child word into the other's child word. Map the first root to the second root and use the child-subtree embeddings in the matched distinct branches. Their images lie below distinct children, so their pairwise meets are the second root; within each branch the chosen embeddings preserve meets. This gives an embedding $T_i{⪯}_Q{T}_j$, contradicting badness. Hence Kruskal's theorem holds. If one requires roots to be preserved, label the root with a new label incomparable with all ordinary labels and apply the just-proved labelled version; its unique occurrence forces root preservation.

For Friedman's finite form of Kruskal's theorem, fix $k$. Consider bad finite sequences of unlabelled tree isomorphism types satisfying $|T_i|\le k+i$, with indices starting at one. Put them in a tree ordered by extension. At each position there are only finitely many isomorphism types with the allowed vertex bound, so this tree is finitely branching. If bad sequences had arbitrarily large lengths, the König infinity lemma would give an infinite branch, an infinite bad sequence contradicting Kruskal's theorem. ConsequentlyThe bound is uniform over all such sequences. Quotienting by tree isomorphism types is essential to the finite-branching argument; arbitrary vertex names would give infinitely many codes for the same finite tree. A fixed finite label alphabet can be included with the same argument.

If $Q$ is a better-quasi-ordering, its full power set is better-quasi-ordered by the Hoare domination preorder. A bad continuous array of subsets would allow a choice of $q_X\in A_X$ not below any member of $A_{X^{-}}$, where $X^{-}$ deletes the least element. Choose this witness as a fixed function of the two locally constant subsets. Then $X\mapsto q_X$ is a bad continuous array in better-quasi-order theory into $Q$, a contradiction. Empty source subsets cannot occur in a bad array because they precede every subset.