Better-quasi-ordering

A quasi-order is better-quasi-ordered if every array into it from every barrier in better-quasi-order theory is good: some barrier members $s◃t$ satisfy $f(s)\le f(t)$. Singleton barriers recover the usual infinite-sequence condition for a well-quasi-ordering. The stronger condition is useful for infinitary closure operations for which well-quasi-ordering alone fails. Equivalently one may use continuous maps from infinite subsets of an infinite subset of the natural numbers, with the discrete topology on the range, and compare $X$ with $X\setminus \{\min X\}$.

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.

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.

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.

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 .