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. Every better-quasi-ordering is a well-quasi-ordering.

Motivation[edit]

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[edit]

It is common in better-quasi-ordering theory to write ${_{*}}x$ for the sequence $x$ with the first term omitted. Write $[\omega ]^{<\omega }$ for the set of finite, strictly increasing sequences with terms in $\omega$ , and define a relation $\triangleleft$ on $[\omega ]^{<\omega }$ as follows: $s\triangleleft t$ if there is $u\in [\omega ]^{<\omega }$ such that $s$ is a strict initial segment of $u$ and $t={}_{*}u$ . The relation $\triangleleft$ is not transitive.

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

Simpson's alternative definition[edit]

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

Let $Q$ be a quasi-ordering and endow $Q$ with the discrete topology. A $Q$ -array is a Borel function $[A]^{\omega }\to Q$ for some infinite subset $A$ of $\omega$ . A $Q$ -array $f$ is bad if $f(X)\not \leq _{Q}f({_{*}}X)$ for every $X\in [A]^{\omega }$ ; $f$ is good otherwise. The quasi-ordering $Q$ is a better-quasi-ordering if there is no bad $Q$ -array in this sense.

Major theorems[edit]

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 $(Q,\leq _{Q})$ is a quasi-order.^{[clarification needed]} A partial ranking $\leq '$ of $Q$ is a well-founded partial ordering of $Q$ such that $q\leq 'r\to q\leq _{Q}r$ . For bad $Q$ -arrays (in the sense of Simpson) $f\colon [A]^{\omega }\to Q$ and $g\colon [B]^{\omega }\to Q$ , define:

g\leq ^{*}f{\text{ if }}B\subseteq A{\text{ and }}g(X)\leq 'f(X){\text{ for every }}X\in [B]^{\omega }

g<^{*}f{\text{ if }}B\subseteq A{\text{ and }}g(X)<'f(X){\text{ for every }}X\in [B]^{\omega }

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

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

References[edit]

^ Rado, Richard (1954). "Partial well-ordering of sets of vectors". Mathematika. 1 (2): 89–95. doi:10.1112/S0025579300000565. MR 0066441.
^ Nash-Williams, C. St. J. A. (1965). "On well-quasi-ordering infinite trees". Mathematical Proceedings of the Cambridge Philosophical Society. 61 (3): 697–720. Bibcode:1965PCPS...61..697N. doi:10.1017/S0305004100039062. ISSN 0305-0041. MR 0175814. S2CID 227358387.
^ Laver, Richard (1971). "On Fraïssé's Order Type Conjecture". The Annals of Mathematics. 93 (1): 89–111. doi:10.2307/1970754. JSTOR 1970754.
^ Martinez-Ranero, Carlos (2011). "Well-quasi-ordering Aronszajn lines". Fundamenta Mathematicae. 213 (3): 197–211. doi:10.4064/fm213-3-1. ISSN 0016-2736. MR 2822417.
^ ^a ^b Simpson, Stephen G. (1985). "BQO Theory and Fraïssé's Conjecture". In Mansfield, Richard; Weitkamp, Galen (eds.). Recursive Aspects of Descriptive Set Theory. The Clarendon Press, Oxford University Press. pp. 124–38. ISBN 978-0-19-503602-2. MR 0786122.
^ 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. ISBN 978-0-12-599101-8. MR 0520553.

[Rado54-1] Rado, Richard (1954). "Partial well-ordering of sets of vectors". Mathematika. 1 (2): 89–95. doi:10.1112/S0025579300000565. MR 0066441.

[Nash-Williams65-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. Bibcode:1965PCPS...61..697N. doi:10.1017/S0305004100039062. ISSN 0305-0041. MR 0175814. S2CID 227358387.

[Laver71-3] Laver, Richard (1971). "On Fraïssé's Order Type Conjecture". The Annals of Mathematics. 93 (1): 89–111. doi:10.2307/1970754. JSTOR 1970754.

[Martinez-Ranero2011-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. MR 2822417.

[Simpson85-5] Simpson, Stephen G. (1985). "BQO Theory and Fraïssé's Conjecture". In Mansfield, Richard; Weitkamp, Galen (eds.). Recursive Aspects of Descriptive Set Theory. The Clarendon Press, Oxford University Press. pp. 124–38. ISBN 978-0-19-503602-2. MR 0786122.

[Laver78-6] 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. ISBN 978-0-12-599101-8. MR 0520553.

[1]

[2]

[3]

[4]

[5]

[6]

v t e Order theory
Topics Glossary Category
Key concepts	Binary relation Boolean algebra Cyclic order Lattice Partial order Preorder Total order Weak ordering
Results	Boolean prime ideal theorem Cantor–Bernstein theorem Cantor's isomorphism theorem Dilworth's theorem Dushnik–Miller theorem Hausdorff maximal principle Knaster–Tarski theorem Kruskal's tree theorem Laver's theorem Mirsky's theorem Szpilrajn extension theorem Zorn's lemma
Properties & Types (list)	Antisymmetric Asymmetric Boolean algebra topics Completeness Connected Covering Dense Directed (Partial) Equivalence Foundational Heyting algebra Homogeneous Idempotent Lattice Bounded Complemented Complete Distributive Join and meet Reflexive Partial order Chain-complete Graded Eulerian Strict Prefix order Preorder Total Semilattice Semiorder Symmetric Total Tolerance Transitive Well-founded Well-quasi-ordering (Better) (Pre) Well-order
Constructions	Composition Converse/Transpose Lexicographic order Linear extension Product order Reflexive closure Series-parallel partial order Star product Symmetric closure Transitive closure
Topology & Orders	Alexandrov topology & Specialization preorder Ordered topological vector space Normal cone Order topology Order topology Topological vector lattice Banach Fréchet Locally convex Normed
Related	Antichain Cofinal Cofinality Comparability Graph Duality Filter Hasse diagram Ideal Net Subnet Order morphism Embedding Isomorphism Order type Ordered field Positive cone of an ordered field Ordered vector space Partially ordered Positive cone of an ordered vector space Riesz space Partially ordered group Positive cone of a partially ordered group Upper set Young's lattice

Motivation[edit]

Definition[edit]

Simpson's alternative definition[edit]

Major theorems[edit]

See also[edit]

References[edit]