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.

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] It is common in better-quasi-ordering theory to write

for the set of finite, strictly increasing sequences with terms in

is a strict initial segment of

that contains an initial segment[clarification needed] of every infinite subset of

[clarification needed] for every pair

is called a better-quasi-ordering if there is no bad

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

By observing that every block contains a barrier, one sees that

is a better-quasi-ordering if and only if there is no bad

Simpson introduced an alternative definition of better-quasi-ordering in terms of Borel functions

, the set of infinite subsets of

, is given the usual product topology.

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.

[clarification needed] A partial ranking

is a well-founded partial ordering of

is minimal bad (with respect to the partial ranking

depend on a partial ranking

is not the strict part of the relation

Theorem (Minimal Bad Array Lemma).

be a quasi-order equipped with a partial ranking and suppose

Then there is a minimal bad