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 better-quasi-ordering is a well-quasi-ordering.

Motivation

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

Definition

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

A block${\displaystyle B}$ is an infinite subset of ${\displaystyle [\omega ]^{<\omega }}$ that contains an initial segment^{[ clarification needed ]} of every infinite subset of ${\displaystyle \bigcup B}$. For a quasi-order ${\displaystyle Q}$, a ${\displaystyle Q}$-pattern is a function from some block ${\displaystyle B}$ into ${\displaystyle Q}$. A ${\displaystyle Q}$-pattern ${\displaystyle f\colon B\to Q}$ is said to be bad if ${\displaystyle f(s)\not \leq _{Q}f(t)}$^{[ clarification needed ]} for every pair ${\displaystyle s,t\in B}$ such that ${\displaystyle s\triangleleft t}$; otherwise ${\displaystyle f}$ is good. A quasi-ordering ${\displaystyle Q}$ is called a better-quasi-ordering if there is no bad ${\displaystyle 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 ${\displaystyle \subset }$. A ${\displaystyle Q}$-array is a ${\displaystyle Q}$-pattern whose domain is a barrier. By observing that every block contains a barrier, one sees that ${\displaystyle Q}$ is a better-quasi-ordering if and only if there is no bad ${\displaystyle Q}$-array.

Simpson's alternative definition

Simpson introduced an alternative definition of better-quasi-ordering in terms of Borel functions ${\displaystyle [\omega ]^{\omega }\to Q}$, where ${\displaystyle [\omega ]^{\omega }}$, the set of infinite subsets of ${\displaystyle \omega }$, is given the usual product topology. ^[5]

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

Major theorems

Many major results in better-quasi-ordering 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.^{[ clarification needed ]} A partial ranking${\displaystyle \leq '}$ of ${\displaystyle Q}$ is a well-founded partial ordering of ${\displaystyle Q}$ such that ${\displaystyle q\leq 'r\to q\leq _{Q}r}$. For bad ${\displaystyle 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 ${\displaystyle Q}$-array ${\displaystyle g}$ is minimal bad (with respect to the partial ranking ${\displaystyle \leq '}$) if there is no bad ${\displaystyle Q}$-array ${\displaystyle f}$ such that ${\displaystyle f<^{*}g}$. The definitions of ${\displaystyle \leq ^{*}}$ and ${\displaystyle <'}$ depend on a partial ranking ${\displaystyle \leq '}$ of ${\displaystyle Q}$. The relation ${\displaystyle <^{*}}$ is not the strict part of the relation ${\displaystyle \leq ^{*}}$.

Theorem (Minimal Bad Array Lemma). Let ${\displaystyle Q}$ be a quasi-order equipped with a partial ranking and suppose ${\displaystyle f}$ is a bad ${\displaystyle Q}$-array. Then there is a minimal bad ${\displaystyle Q}$-array ${\displaystyle 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 Fraïssé'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 (eds.). Recursive Aspects of Descriptive Set Theory. The Clarendon Press, Oxford University Press. pp.  124–38. ISBN   978-0-19-503602-2. MR   0786122.
6. Laver, Richard (1978). "Better-quasi-orderings and a class of trees". In Rota, Gian-Carlo (ed.). Studies in foundations and combinatorics. Academic Press. pp. 31–48. ISBN   978-0-12-599101-8. MR   0520553.