= Solution
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\triangleleft 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\triangleleft t$ satisfy $f(s)\leq f(t)$. The definition is
$$
\boxed{Q\text{ is BQO }\Longleftrightarrow
\text{ every map from every barrier into }Q\text{ is good}.}
$$
Both quantifiers matter: testing only barriers of one fixed finite length is insufficient.
For the singleton barrier $B=[A]^1$, shifted pairs are just $\{a\}\triangleleft\{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 satisfy
$$
F(X)>F(X\setminus\{\min X\})
>F(X\setminus\{\text{first two entries}\})>\cdots
$$
for 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'$ on which the array is constant. The comparison of an infinite <subset> of $A'$ with its shift is then good.
The implication to a well-quasi-order is strict. The <Rado order> is
$$
R=\{(m,n)\in\omega^2:m<n\},\qquad
(m,n)\leq_R(k,l)\ \Longleftrightarrow\
(m=k\text{ and }n\leq l)\text{ or }n<k.
$$
It 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 \b[<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.
Back to article page
