Better-quasi-ordering

In order theory a better-quasi-ordering or bqo is a quasi-ordering that does not admit a certain type of bad array. Every bqo is well-quasi-ordered.

Motivation

Though wqo is an appealing notion, many important infinitary operations do not preserve wqoness. An example due to Richard Rado illustrates this.^[1] In a 1965 paper Crispin Nash-Williams formulated the stronger notion of bqo in order to prove that the class of trees of height ω is wqo under the topological minor relation.^[2] Since then, many quasi-orders have been proven to be wqo by proving them to be bqo. For instance, Richard Laver established Fraïssé's conjecture by proving that the class of scattered linear order types is bqo.^[3] More recently, Carlos Martinez-Ranero has proven that, under the Proper Forcing Axiom, the class of Aronszajn lines is bqo under the embeddability relation.^[4]

Definition

It is common in bqo theory to write ${\displaystyle {_{*}}x}$ for the sequence $x$ with the first term omitted. Write ${\displaystyle [\omega ]^{<\omega }}$ for the set of finite, strictly increasing sequences with terms in $\omega$, and define a relation $\triangleleft$ on ${\displaystyle [\omega ]^{<\omega }}$ as follows: ${\displaystyle s\triangleleft t}$ if and only if there is $u$ such that $s$ is a strict initial segment of $u$ and ${\displaystyle t={}_{*}u}$. Note that the relation $\triangleleft$ is not transitive.

A block is a infinite subset B of ${\displaystyle [\omega ]^{<\omega }}$ that contains an initial segment of every infinite subset of ${\displaystyle \bigcup B}$. For a quasi-order $Q$ a $Q$-pattern is a function from a block B into $Q$. A $Q$-pattern ${\displaystyle f\colon B\to Q}$ is said to be bad if ${\displaystyle f(s)\not \leq _{Q}f(t)}$ for every pair ${\displaystyle s,t\in B}$ such that ${\displaystyle s\triangleleft t}$; otherwise $f$ is good. A quasi-order $Q$ is better-quasi-ordered (bqo) if there is no bad $Q$-pattern.

In order to make this definition easier to work with, Nash-Williams defines a barrier to be a block whose elements are pairwise incomparable under the inclusion relation $\subset$. A $Q$-array is a $Q$-pattern whose domain is a barrier. By observing that every block contains a barrier, one sees that $Q$ is bqo if and only if there is no bad $Q$-array.

Simpson's alternative definition

Simpson introduced an alternative definition of bqo in terms of Borel maps ${\displaystyle [\omega ]^{\omega }\to Q}$, where ${\displaystyle [\omega ]^{\omega }}$, the set of infinite subsets of $\omega$, is given the usual (product) topology.^[5]

Let $Q$ be a quasi-order and endow $Q$ with the discrete topology. A $Q$-array is a Borel function ${\displaystyle [A]^{\omega }\to Q}$ for some infinite subset $A$ of $\omega$. A $Q$-array $f$ is bad if ${\displaystyle f(X)\not \leq _{Q}f({_{*}}X)}$ for every ${\displaystyle X\in [A]^{\omega }}$; $f$ is good otherwise. The quasi-order $Q$ is bqo if there is no bad $Q$-array in this sense.

Major theorems

Many major results in bqo theory are consequences of the Minimal Bad Array Lemma, which appears in Simpson's paper^[5] as follows. See also Laver's paper,^[6] where the Minimal Bad Array Lemma was first stated as a result. The technique was present in Nash-Williams' original 1965 paper.

Suppose ${\displaystyle (Q,\leq _{Q})}$ is a quasi-order. A partial ranking ${\displaystyle \leq '}$ of $Q$ is a well-founded partial ordering of $Q$ such that ${\displaystyle q\leq 'r\to q\leq _{Q}r}$. For bad $Q$-arrays (in the sense of Simpson) ${\displaystyle f\colon [A]^{\omega }\to Q}$ and ${\displaystyle g\colon [B]^{\omega }\to Q}$, define:

${\displaystyle g\leq ^{*}f{\text{ if }}B\subseteq A{\text{ and }}g(X)\leq 'f(X){\text{ for every }}X\in [B]^{\omega }}$

${\displaystyle g<^{*}f{\text{ if }}B\subseteq A{\text{ and }}g(X)<'f(X){\text{ for every }}X\in [B]^{\omega }}$

We say a bad $Q$-array $g$ is minimal bad (with respect to the partial ranking ${\displaystyle \leq '}$) if there is no bad $Q$-array $f$ such that ${\displaystyle f<^{*}g}$. Note that the definitions of ${\displaystyle \leq ^{*}}$ and ${\displaystyle <'}$ depend on a partial ranking ${\displaystyle \leq '}$ of $Q$. Note also that the relation ${\displaystyle <^{*}}$ is not the strict part of the relation ${\displaystyle \leq ^{*}}$.

Theorem (Minimal Bad Array Lemma). Let $Q$ be a quasi-order equipped with a partial ranking and suppose $f$ is a bad $Q$-array. Then there is a minimal bad $Q$-array $g$ such that ${\displaystyle g\leq ^{*}f}$.

See also

• Well-quasi-ordering
• Well-order

References

1. Rado, Richard (1954). "Partial well-ordering of sets of vectors". Mathematika. 1 (2): 89–95. doi:10.1112/S0025579300000565. MR 0066441.
2. Nash-Williams, C. St. J. A. (1965). "On well-quasi-ordering infinite trees". Mathematical Proceedings of the Cambridge Philosophical Society. 61 (3): 697–720. Bibcode:1965PCPS...61..697N. doi:10.1017/S0305004100039062. ISSN 0305-0041. MR 0175814.
3. Laver, Richard (1971). "On Fraisse's Order Type Conjecture". The Annals of Mathematics. 93 (1): 89–111. doi:10.2307/1970754. JSTOR 1970754.
4. Martinez-Ranero, Carlos (2011). "Well-quasi-ordering Aronszajn lines". Fundamenta Mathematicae. 213 (3): 197–211. doi:10.4064/fm213-3-1. ISSN 0016-2736. MR 2822417.
5. Simpson, Stephen G. (1985). "BQO Theory and Fraïssé's Conjecture". In Mansfield, Richard; Weitkamp, Galen. Recursive Aspects of Descriptive Set Theory. The Clarendon Press, Oxford University Press. pp. 124–38. ISBN 978-0-19-503602-2. MR 786122.
6. Laver, Richard (1978). "Better-quasi-orderings and a class of trees". In Rota, Gian-Carlo. Studies in foundations and combinatorics. Academic Press. pp. 31–48. ISBN 978-0-12-599101-8. MR 0520553.