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 for the sequence with the first term omitted. Write for the set of finite, strictly increasing
sequences with terms in , and define a relation on as follows: if there is such that is a strict initial segment of and . The relation is not
transitive.
A block is an infinite subset of that contains an initial segment[clarification needed] of every
infinite subset of . For a quasi-order , a -pattern is a function from some block into . A -pattern is said to be bad if [clarification needed] for every pair such that ; otherwise is good. A quasi-ordering is called a better-quasi-ordering if there is no bad -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 . A -array is a -pattern whose domain is a barrier. By observing that every block contains a barrier, one sees that is a better-quasi-ordering if and only if there is no bad -array.
Simpson's alternative definition
Simpson introduced an alternative definition of better-quasi-ordering in terms of
Borel functions, where , the set of infinite subsets of , is given the usual
product topology.[5]
Let be a quasi-ordering and endow with the
discrete topology. A -array is a Borel function for some infinite subset of . A -array is bad if for every ;
is good otherwise. The quasi-ordering is a better-quasi-ordering if there is no bad -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.
We say a bad -array is minimal bad (with respect to the partial ranking ) if there is no bad -array such that .
The definitions of and depend on a partial ranking of . The relation is not the strict part of the relation .
Theorem (Minimal Bad Array Lemma). Let be a
quasi-order equipped with a partial ranking and suppose is a bad -array. Then there is a minimal bad -array such that .
^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.
ISBN978-0-12-599101-8.
MR0520553.