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]