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]
Definitionedit
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 definitionedit
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 theoremsedit
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.
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 .
^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.
^ abSimpson, 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. ISBN978-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. ISBN978-0-12-599101-8. MR 0520553.
April 12, 2024
better, quasi, ordering, order, theory, better, quasi, ordering, quasi, ordering, that, does, admit, certain, type, array, every, better, quasi, ordering, well, quasi, ordering, contents, motivation, definition, simpson, alternative, definition, major, theorem. 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 Contents 1 Motivation 2 Definition 3 Simpson s alternative definition 4 Major theorems 5 See also 6 ReferencesMotivation editThough 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 w 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 Fraisse 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 editIt is common in better quasi ordering theory to write x displaystyle x nbsp for the sequence x displaystyle x nbsp with the first term omitted Write w lt w displaystyle omega lt omega nbsp for the set of finite strictly increasing sequences with terms in w displaystyle omega nbsp and define a relation displaystyle triangleleft nbsp on w lt w displaystyle omega lt omega nbsp as follows s t displaystyle s triangleleft t nbsp if there is u w lt w displaystyle u in omega lt omega nbsp such that s displaystyle s nbsp is a strict initial segment of u displaystyle u nbsp and t u displaystyle t u nbsp The relation displaystyle triangleleft nbsp is not transitive A block B displaystyle B nbsp is an infinite subset of w lt w displaystyle omega lt omega nbsp that contains an initial segment clarification needed of every infinite subset of B displaystyle bigcup B nbsp For a quasi order Q displaystyle Q nbsp a Q displaystyle Q nbsp pattern is a function from some block B displaystyle B nbsp into Q displaystyle Q nbsp A Q displaystyle Q nbsp pattern f B Q displaystyle f colon B to Q nbsp is said to be bad if f s Qf t displaystyle f s not leq Q f t nbsp clarification needed for every pair s t B displaystyle s t in B nbsp such that s t displaystyle s triangleleft t nbsp otherwise f displaystyle f nbsp is good A quasi ordering Q displaystyle Q nbsp is called a better quasi ordering if there is no bad Q displaystyle Q nbsp 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 displaystyle subset nbsp A Q displaystyle Q nbsp array is a Q displaystyle Q nbsp pattern whose domain is a barrier By observing that every block contains a barrier one sees that Q displaystyle Q nbsp is a better quasi ordering if and only if there is no bad Q displaystyle Q nbsp array Simpson s alternative definition editSimpson introduced an alternative definition of better quasi ordering in terms of Borel functions w w Q displaystyle omega omega to Q nbsp where w w displaystyle omega omega nbsp the set of infinite subsets of w displaystyle omega nbsp is given the usual product topology 5 Let Q displaystyle Q nbsp be a quasi ordering and endow Q displaystyle Q nbsp with the discrete topology A Q displaystyle Q nbsp array is a Borel function A w Q displaystyle A omega to Q nbsp for some infinite subset A displaystyle A nbsp of w displaystyle omega nbsp A Q displaystyle Q nbsp array f displaystyle f nbsp is bad if f X Qf X displaystyle f X not leq Q f X nbsp for every X A w displaystyle X in A omega nbsp f displaystyle f nbsp is good otherwise The quasi ordering Q displaystyle Q nbsp is a better quasi ordering if there is no bad Q displaystyle Q nbsp array in this sense Major theorems editMany 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 Q displaystyle Q leq Q nbsp is a quasi order clarification needed A partial ranking displaystyle leq nbsp of Q displaystyle Q nbsp is a well founded partial ordering of Q displaystyle Q nbsp such that q r q Qr displaystyle q leq r to q leq Q r nbsp For bad Q displaystyle Q nbsp arrays in the sense of Simpson f A w Q displaystyle f colon A omega to Q nbsp and g B w Q displaystyle g colon B omega to Q nbsp define g f if B A and g X f X for every X B w displaystyle g leq f text if B subseteq A text and g X leq f X text for every X in B omega nbsp g lt f if B A and g X lt f X for every X B w displaystyle g lt f text if B subseteq A text and g X lt f X text for every X in B omega nbsp We say a bad Q displaystyle Q nbsp array g displaystyle g nbsp is minimal bad with respect to the partial ranking displaystyle leq nbsp if there is no bad Q displaystyle Q nbsp array f displaystyle f nbsp such that f lt g displaystyle f lt g nbsp The definitions of displaystyle leq nbsp and lt displaystyle lt nbsp depend on a partial ranking displaystyle leq nbsp of Q displaystyle Q nbsp The relation lt displaystyle lt nbsp is not the strict part of the relation displaystyle leq nbsp Theorem Minimal Bad Array Lemma Let Q displaystyle Q nbsp be a quasi order equipped with a partial ranking and suppose f displaystyle f nbsp is a bad Q displaystyle Q nbsp array Then there is a minimal bad Q displaystyle Q nbsp array g displaystyle g nbsp such that g f displaystyle g leq f nbsp See also editWell quasi ordering Well orderReferences 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 Fraisse 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 Fraisse 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 Retrieved from https en wikipedia org w index php title Better quasi ordering amp oldid 1204509107, wikipedia, wiki, book, books, library,