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.
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.
It is common in better-quasi-ordering theory to write
{*}x
x
[\omega]<\omega
\omega
\triangleleft
[\omega]<\omega
s\triangleleftt
u\in[\omega]<\omega
s
u
t={}*u
\triangleleft
A block
B
[\omega]<\omega
cupB
Q
Q
B
Q
Q
f\colonB\toQ
f(s)\not\leQf(t)
s,t\inB
s\triangleleftt
f
Q
Q
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
Q
Q
Q
Q
Simpson introduced an alternative definition of better-quasi-ordering in terms of Borel functions
[\omega]\omega\toQ
[\omega]\omega
\omega
Let
Q
Q
Q
[A]\omega\toQ
A
\omega
Q
f
f(X)\not\leQf({*}X)
X\in[A]\omega
f
Q
Q
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,\leQ)
\le'
Q
Q
q\le'r\toq\leQr
Q
f\colon[A]\omega\toQ
g\colon[B]\omega\toQ
g\le*fifB\subseteqAandg(X)\le'f(X)foreveryX\in[B]\omega
g<*fifB\subseteqAandg(X)<'f(X)foreveryX\in[B]\omega
Q
g
\le'
Q
f
f<*g
\le*
<'
\le'
Q
<*
\le*
Theorem (Minimal Bad Array Lemma). Let
Q
f
Q
Q
g
g\le*f