In
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
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.
Suppose is a
] A
partial ranking of
is a
partial ordering
of
such that
. For bad
-arrays (in the sense of Simpson)
and
, define:
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
.
See also
References