Schreier Sets in Ramsey Theory

arXiv:math/0510102v1[math.CO]5Oct2005SCHREIERSETSINRAMSEYTHEORYV.FARMAKIANDS.NEGREPONTISAbstract.WeshowthatRamseytheory,adomainpresentlyconceivedtoguaran-teetheexistenceoflargehomogeneoussetsforpartitionsonk-tuplesofwords(foreverynaturalnumberk)overafinitealphabet,canbeextendedtooneforpartitionsonSchreier-typesetsofwords(ofeverycountableordinal).Indeed,weestablishanextensionofthepartitiontheoremofCarlsonaboutwordsandofthe(moregeneral)partitiontheoremofFurstenberg-Katznelsonaboutcombinatorialsubspacesofthesetofwords(generatingfromk-tuplesofwordsforanyfixednaturalnumberk)intoapartitiontheoremaboutcombinatorialsubspaces(generatingfromSchreier-typesetsofwordsoforderanyfixedcountableordinal).Furthermore,asaresultweobtainastrengtheningofCarlson’sinfinitaryNash-Williamstype(andEllentucktype)partitiontheoremaboutinfinitesequencesofvariablewordsintoatheorem,inwhichaninfinitesequenceofvariablewordsandabinarypartitionofallthefinitesequencesofwords,oneofwhosecomponentsis,inaddition,atree,areassumed,concludingthatalltheSchreier-typefinitereductionsofaninfinitereductionofthegivensequencehaveabe-haviordeterminedbytheCantor-Bendixsonordinalindexofthetree-componentofthepartition,fallinginthetree-componentabovethatindexandinitscomplementbelowit.IntroductionOuraimistoextendRamseytheorysothatitappliesnotonlytopartitionsofk-tuplesofwordsbutmoregenerallytopartitionsofSchreier-typesetsofwordsofafixedcountableordinalnumber.Forafinitenon-emptyalphabetΣwedenotebyWk(Σ)(respectively,Wk(Σ;υ))thefamilyofsequencesofkmanywords(respectively,variablewords)overΣ,andbyWω(Σ;υ)thefamilyofinfinitesequencesofvariablewordsoverΣ.Byareduction(respectively,variablereduction)of~w=(wn)n∈N∈Wω(Σ;υ)wemeananyinfinitesequenceofwords(respectively,variablewords),denotedby~u≺~w,obtainedfrom~wbyreplacingeachoccurenceofthevariableineachwnbyoneelementofthesetΣ∪{υ},dividingtheresultingsequenceintoinfinitelymanyfiniteblocksofconsecutivewords,andconcatenatingthemembersofeachblock;thefirstelement(respectively,thefirstkelements)ofareductionof~wiscalledareducedword(respectively,afinitereductionswithkwords)of~w.(Thesetermswillbedefinedmoreformallybelow).Fora1991MathematicsSubjectClassification.Primary05D10;Secondary28D05.Keywordsandphrases.Ramseytheory,Schreiersets,words.1naturalnumberr,anr-coloring(oranr-partition)ofasetSisamapχ:S→{1,...,r},andχ(s)isthecolorofsfors∈S.AsetT⊆Sismonochromatic(underχ)ifχisconstantonT.ThefundamentalclassicalpartitiontheoremsofRamseytheory,namely(a)Carlson’spartitiontheorem(Lemma5.9in[C],Corollary4.6in[BBH]instrenthenedform),(b)theFurstenberg-Katznelsonpartitiontheorem(Theorems2.7and3.1in[FK1]),and(c)Carlson’sNash-Williamstypeinfinitarypartitiontheorem(Theorem2in[C]),cannowbestatedasfollows:Theorem0.1(Carlson’stheorem,[C],[BBH]).Letχ1:W1(Σ)→{1,...,r1}andχ2:W1(Σ;υ)→{1,...,r2}befinitecoloringsofthesetsW1(Σ)andW1(Σ;υ),respectivelyand~w∈Wω(Σ;υ)beaninfinitesequenceofvariablewordsoverΣ;thenthereexistsavariablereduction~u≺~wof~wsuchthatallthereducedwordsof~uaremonochromaticunderχ1andallthereducedvariablewordsof~uaremonochromaticunderχ2.Theorem0.2(Furstenberg-Katznelson’stheorem,[FK1]).Letkbeanynaturalnumber,χ1:Wk(Σ)→{1,...,r1}andχ2:Wk(Σ;υ)→{1,...,r2}befinitecoloringsofthesetsWk(Σ)andWk(Σ;υ),respectivelyand~w∈Wω(Σ;υ)beaninfinitesequenceofvariablewordsoverΣ;thenthereexistsavariablereduction~u≺~wof~wsuchthatallthefinitereductionswithkwordsof~uaremonochromaticunderχ1andallthefinitevariablereductionswithkvariablewordsof~uaremonochromaticunderχ2.InadditionFurstenbergandKatznelsonin[FK2]introducedthenotionofak-dimen-sionalcombinatorialsubspaceofW(Σ)forkanynaturalnumberandproved(inTheorem3.1)apartitiontheoremaboutthesecombinatorialsubspaces.Theorem0.3(Carlson’sinfinitarypartitiontheorem,[C]).LetU⊆Wω(Σ;υ)beapoint-wiseclosedfamilyofinfinitesequencesofvariablewordsoverΣand~w∈Wω(Σ;υ)beaninfinitesequenceofvariablewordsoverΣ;thenthereexistsavariablereduction~u≺~wof~woverΣsuchthateitherallthevariablereductionsof~uarecontainedinUorallvariablereductionsof~uarecontainedinthecomplementofU.Asstated,theaimofthepresentpaperistoshowthatstrongerversionsofthesepartitiontheoremsholdforthefamilyofSchreier-typesetsofwordsofeverycountableordinal,andnotjustforthefamilyofk-tuplesofwords,withkrestrictedtoanaturalnumber.Thehierarchy(Aξ)ξω1ofthefamiliesofSchreiersetsofnaturalnumbers,de-finedonthecountableordinals,providesaclassificationoftheclassofallfinitesubsetsof2thenaturalnumbersmeasuringtheircomplexity.TherecursivedefinitionoftheSchreiersets(Aξ)ξω1isasfollows:Definition0.4(TheSchreiersystem,[F1,Def.7],[F2,Def.1.5][F3,Def.1.3]).Foreverynon-zero,countable,limitordinalλchooseandfixastrictlyincreasingsequence(λn)n∈Nofsuccessorordinalssmallerthanλwithsupnλn=λ.Thesystem(Aξ)ξω1isdefinedrecursivelyasfollows:(1)A0={∅}andA1={{n}:n∈N};(2)Aζ+1={s∈[N]ω0:s={n}∪s1,wheren∈N,{n}s1ands1∈Aζ};(3i)Aωβ+1={s∈[N]ω0:s=Sni=1si,wheren=mins1,s1···snands1,...,sn∈Aωβ};(3ii)foranon-zero,countablelimitordinalλ,Aωλ={s∈[N]ω0:s∈Aωλnwithn=mins};and(3iii)foralimitordinalξsuchthatωαξωα+1forsome0αω1,ifξ=ωαp+Pmi=1ωaipi,wherem∈Nwithm≥0,p