Better-quasi-ordering

From HandWiki

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.[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 [math]\displaystyle{ {_*}x }[/math] for the sequence [math]\displaystyle{ x }[/math] with the first term omitted. Write [math]\displaystyle{ [\omega]^{\lt \omega} }[/math] for the set of finite, strictly increasing sequences with terms in [math]\displaystyle{ \omega }[/math], and define a relation [math]\displaystyle{ \triangleleft }[/math] on [math]\displaystyle{ [\omega]^{\lt \omega} }[/math] as follows: [math]\displaystyle{ s\triangleleft t }[/math] if there is [math]\displaystyle{ u \in [\omega]^{\lt \omega} }[/math] such that [math]\displaystyle{ s }[/math] is a strict initial segment of [math]\displaystyle{ u }[/math] and [math]\displaystyle{ t={}_*u }[/math]. The relation [math]\displaystyle{ \triangleleft }[/math] is not transitive.

A block [math]\displaystyle{ B }[/math] is an infinite subset of [math]\displaystyle{ [\omega]^{\lt \omega} }[/math] that contains an initial segment[clarification needed] of every infinite subset of [math]\displaystyle{ \bigcup B }[/math]. For a quasi-order [math]\displaystyle{ Q }[/math], a [math]\displaystyle{ Q }[/math]-pattern is a function from some block [math]\displaystyle{ B }[/math] into [math]\displaystyle{ Q }[/math]. A [math]\displaystyle{ Q }[/math]-pattern [math]\displaystyle{ f\colon B\to Q }[/math] is said to be bad if [math]\displaystyle{ f(s)\not \le_Q f(t) }[/math][clarification needed] for every pair [math]\displaystyle{ s,t\in B }[/math] such that [math]\displaystyle{ s\triangleleft t }[/math]; otherwise [math]\displaystyle{ f }[/math] is good. A quasi-ordering [math]\displaystyle{ Q }[/math] is called a better-quasi-ordering if there is no bad [math]\displaystyle{ Q }[/math]-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 [math]\displaystyle{ \subset }[/math]. A [math]\displaystyle{ Q }[/math]-array is a [math]\displaystyle{ Q }[/math]-pattern whose domain is a barrier. By observing that every block contains a barrier, one sees that [math]\displaystyle{ Q }[/math] is a better-quasi-ordering if and only if there is no bad [math]\displaystyle{ Q }[/math]-array.

Simpson's alternative definition

Simpson introduced an alternative definition of better-quasi-ordering in terms of Borel functions [math]\displaystyle{ [\omega]^{\omega}\to Q }[/math], where [math]\displaystyle{ [\omega]^{\omega} }[/math], the set of infinite subsets of [math]\displaystyle{ \omega }[/math], is given the usual product topology.[5]

Let [math]\displaystyle{ Q }[/math] be a quasi-ordering and endow [math]\displaystyle{ Q }[/math] with the discrete topology. A [math]\displaystyle{ Q }[/math]-array is a Borel function [math]\displaystyle{ [A]^{\omega}\to Q }[/math] for some infinite subset [math]\displaystyle{ A }[/math] of [math]\displaystyle{ \omega }[/math]. A [math]\displaystyle{ Q }[/math]-array [math]\displaystyle{ f }[/math] is bad if [math]\displaystyle{ f(X)\not\le_Q f({_*}X) }[/math] for every [math]\displaystyle{ X\in[A]^{\omega} }[/math]; [math]\displaystyle{ f }[/math] is good otherwise. The quasi-ordering [math]\displaystyle{ Q }[/math] is a better-quasi-ordering if there is no bad [math]\displaystyle{ Q }[/math]-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 [math]\displaystyle{ (Q,\le_Q) }[/math] is a quasi-order.[clarification needed] A partial ranking [math]\displaystyle{ \le' }[/math] of [math]\displaystyle{ Q }[/math] is a well-founded partial ordering of [math]\displaystyle{ Q }[/math] such that [math]\displaystyle{ q\le'r \to q \le_Q r }[/math]. For bad [math]\displaystyle{ Q }[/math]-arrays (in the sense of Simpson) [math]\displaystyle{ f\colon [A]^{\omega}\to Q }[/math] and [math]\displaystyle{ g\colon [B]^{\omega}\to Q }[/math], define:

[math]\displaystyle{ g\le^* f \text{ if } B\subseteq A \text{ and } g(X)\le' f(X) \text{ for every } X\in[B]^{\omega} }[/math]
[math]\displaystyle{ g \lt ^* f \text{ if } B\subseteq A \text{ and } g(X) \lt ' f(X) \text{ for every } X\in[B]^{\omega} }[/math]

We say a bad [math]\displaystyle{ Q }[/math]-array [math]\displaystyle{ g }[/math] is minimal bad (with respect to the partial ranking [math]\displaystyle{ \le' }[/math]) if there is no bad [math]\displaystyle{ Q }[/math]-array [math]\displaystyle{ f }[/math] such that [math]\displaystyle{ f \lt ^* g }[/math]. The definitions of [math]\displaystyle{ \le^* }[/math] and [math]\displaystyle{ \lt ' }[/math] depend on a partial ranking [math]\displaystyle{ \le' }[/math] of [math]\displaystyle{ Q }[/math]. The relation [math]\displaystyle{ \lt ^* }[/math] is not the strict part of the relation [math]\displaystyle{ \le^* }[/math].

Theorem (Minimal Bad Array Lemma). Let [math]\displaystyle{ Q }[/math] be a quasi-order equipped with a partial ranking and suppose [math]\displaystyle{ f }[/math] is a bad [math]\displaystyle{ Q }[/math]-array. Then there is a minimal bad [math]\displaystyle{ Q }[/math]-array [math]\displaystyle{ g }[/math] such that [math]\displaystyle{ g \le^* f }[/math].

See also

References

  1. ↑ Rado, Richard (1954). "Partial well-ordering of sets of vectors". Mathematika 1 (2): 89–95. doi:10.1112/S0025579300000565. 
  2. ↑ Nash-Williams, C. St. J. A. (1965). "On well-quasi-ordering infinite trees". Mathematical Proceedings of the Cambridge Philosophical Society 61 (3): 697–720. doi:10.1017/S0305004100039062. ISSN 0305-0041. Bibcode: 1965PCPS...61..697N. 
  3. ↑ Laver, Richard (1971). "On Fraïssé's Order Type Conjecture". The Annals of Mathematics 93 (1): 89–111. doi:10.2307/1970754. 
  4. ↑ Martinez-Ranero, Carlos (2011). "Well-quasi-ordering Aronszajn lines". Fundamenta Mathematicae 213 (3): 197–211. doi:10.4064/fm213-3-1. ISSN 0016-2736. 
  5. ↑ 5.0 5.1 Simpson, Stephen G. (1985). "BQO Theory and Fraïssé's Conjecture". in Mansfield, Richard; Weitkamp, Galen. Recursive Aspects of Descriptive Set Theory. The Clarendon Press, Oxford University Press. pp. 124–38. ISBN 978-0-19-503602-2. https://archive.org/details/recursiveaspects0000mans/page/124. 
  6. ↑ Laver, Richard (1978). "Better-quasi-orderings and a class of trees". in Rota, Gian-Carlo. Studies in foundations and combinatorics. Academic Press. pp. 31–48. ISBN 978-0-12-599101-8. 



Retrieved from "https://handwiki.org/wiki/index.php?title=Better-quasi-ordering&oldid=3367884"