Better-quasi-order

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.
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. 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. 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.

Definition

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

A ''block'' $B$ is an infinite subset of omega that contains an initial segment of every
infinite subset of $\bigcup B$. For a quasi-order $Q$, a ''$Q$-pattern'' is a function from some block $B$ into $Q$. A $Q$-pattern $f\colon B\to Q$ is said to be ''bad'' if $f(s)\not \le_Q f(t)$ for every pair $s,t\in B$ such that $s\triangleleft t$; otherwise $f$ is ''good''. A quasi-ordering $Q$ is called a ''better-quasi-ordering'' 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 a better-quasi-ordering if and only if there is no bad $Q$-array.

Simpson's alternative definition

Simpson introduced an alternative definition of ''better-quasi-ordering'' in terms of Borel functions omega\to Q, where omega, the set of infinite subsets of $\omega$, is given the usual product topology.

Let ''$Q$'' be a quasi-ordering and endow $Q$ with the discrete topology. A ''$Q$-array'' is a Borel function \to Q for some infinite subset $A$ of $\omega$. A $Q$-array $f$ is ''bad'' if $f(X)\not\le_Q f(X)$ for every X\in ;
$f$ is ''good'' otherwise. The quasi-ordering $Q$ is a ''better-quasi-ordering'' if there is no bad $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 as follows. See also Laver's paper, where the Minimal Bad Array Lemma was first stated as a result. The technique was present in Nash-Williams' original 1965 paper.

Suppose $(Q,\le_Q)$ is a quasi-order. A ''partial ranking'' $\le'$ of $Q$ is a well-founded partial ordering of $Q$ such that $q\le'r \to q \le_Q r$. For bad $Q$-arrays (in the sense of Simpson) f\colon \to Q and g\colon \to Q, define:
: g\le^* f \text B\subseteq A \text g(X)\le' f(X) \text X\in
: g <^* f \text B\subseteq A \text g(X) <' f(X) \text X\in
We say a bad $Q$-array $g$ is ''minimal bad'' (with respect to the partial ranking $\le'$) if there is no bad $Q$-array $f$ such that $f <^* g$.
The definitions of $\le^*$ and $<'$ depend on a partial ranking $\le'$ of $Q$. The relation $<^*$ is not the strict part of the relation $\le^*$.

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 $g \le^* f$.

See also

* Well-quasi-ordering
* Well-order

References

{{Order theory

Binary relations
Order theory
Wellfoundedness