Schreier Sets in Ramsey Theory
a r X i v :m a t h /0510102v 1 [m a t h .C O ] 5 O c t 2005SCHREIER SETS IN RAMSEY THEORY
V.FARMAKI AND S.NEGREPONTIS
Abstract.We show that Ramsey theory,a domain presently conceived to guaran-tee the existence of large homogeneous sets for partitions on k -tuples of words (for every natural number k )over a ?nite alphabet,can be extended to one for partitions on Schreier-type sets of words (of every countable ordinal).Indeed,we establish an extension of the partition theorem of Carlson about words and of the (more general)partition theorem of Furstenberg-Katznelson about combinatorial subspaces of the set of words (generating from k -tuples of words for any ?xed natural number k )into a partition theorem about combinatorial subspaces (generating from Schreier-type sets of words of order any ?xed countable ordinal).Furthermore,as a result we obtain a strengthening of Carlson’s in?nitary Nash-Williams type (and Ellentuck type)partition theorem about in?nite sequences of variable words into a theorem,in which an in?nite sequence of variable words and a binary partition of all the ?nite sequences of words,one of whose components is,in addition,a tree,are assumed,concluding that all the Schreier-type ?nite reductions of an in?nite reduction of the given sequence have a be-havior determined by the Cantor-Bendixson ordinal index of the tree-component of the partition,falling in the tree-component above that index and in its complement below it.Introduction Our aim is to extend Ramsey theory so that it applies not only to partitions of k -tuples of words but more generally to partitions of Schreier-type sets of words of a ?xed countable ordinal number.For a ?nite non-empty alphabet Σwe denote by W k (Σ)(respectively,W k (Σ;υ))the family of sequences of k many words (respectively,variable words)over Σ,and by W ω(Σ;υ)the family of in?nite sequences of variable words over Σ.By a reduction (respectively,variable reduction)of w =(w n )n ∈N ∈W ω(Σ;υ)we mean
any in?nite sequence of words (respectively,variable words),denoted by u ? w ,obtained from w by replacing each occurence of the variable in each w n by one element of the set Σ∪{υ},dividing the resulting sequence into in?nitely many ?nite blocks of consecutive words,and concatenating the members of each block;the ?rst element (respectively,the ?rst k elements)of a reduction of w is called a reduced word (respectively,a ?nite reductions with k words)of w .(These terms will be de?ned more formally below).For a
natural number r,an r-coloring(or an r-partition)of a set S is a mapχ:S→{1,...,r}, andχ(s)is the color of s for s∈S.A set T?S is monochromatic(underχ)ifχis constant on T.
The fundamental classical partition theorems of Ramsey theory,namely(a)Carlson’s partition theorem(Lemma5.9in[C],Corollary4.6in[BBH]in strenthened form),(b) the Furstenberg-Katznelson partition theorem(Theorems2.7and3.1in[FK1]),and(c) Carlson’s Nash-Williams type in?nitary partition theorem(Theorem2in[C]),can now be stated as follows:
Theorem0.1(Carlson’s theorem,[C],[BBH]).Letχ1:W1(Σ)→{1,...,r1}andχ2: W1(Σ;υ)→{1,...,r2}be?nite colorings of the sets W1(Σ)and W1(Σ;υ),respectively and w∈Wω(Σ;υ)be an in?nite sequence of variable words overΣ;then there exists a variable reduction u? w of w such that all the reduced words of u are monochromatic underχ1and all the reduced variable words of u are monochromatic underχ2.
Theorem0.2(Furstenberg-Katznelson’s theorem,[FK1]).Let k be any natural number,χ1:W k(Σ)→{1,...,r1}andχ2:W k(Σ;υ)→{1,...,r2}be?nite colorings of the sets W k(Σ)and W k(Σ;υ),respectively and w∈Wω(Σ;υ)be an in?nite sequence of variable words overΣ;then there exists a variable reduction u? w of w such that all the?nite reductions with k words of u are monochromatic underχ1and all the?nite variable reductions with k variable words of u are monochromatic underχ2.
In addition Furstenberg and Katznelson in[FK2]introduced the notion of a k-dimen-sional combinatorial subspace of W(Σ)for k any natural number and proved(in Theorem 3.1)a partition theorem about these combinatorial subspaces.
Theorem0.3(Carlson’s in?nitary partition theorem,[C]).Let U?Wω(Σ;υ)be a point-wise closed family of in?nite sequences of variable words overΣand w∈Wω(Σ;υ)be an in?nite sequence of variable words overΣ;then there exists a variable reduction u? w of w overΣsuch that either all the variable reductions of u are contained in U or all variable reductions of u are contained in the complement of U.
As stated,the aim of the present paper is to show that stronger versions of these partition theorems hold for the family of Schreier-type sets of words of every countable ordinal,and not just for the family of k-tuples of words,with k restricted to a natural number.The hierarchy(Aξ)ξ<ω
of the families of Schreier sets of natural numbers,de-
1
?ned on the countable ordinals,provides a classi?cation of the class of all?nite subsets of
the natural numbers measuring their complexity.The recursive de?nition of the Schreier sets (A ξ)ξ<ω1is as follows:
De?nition 0.4(The Schreier system ,[F1,Def.7],[F2,Def. 1.5][F3,Def. 1.3]).For every non-zero,countable,limit ordinal λchoose and ?x a strictly increasing sequence (λn )n ∈N of successor ordinals smaller than λwith sup n λn =λ.The system (A ξ)ξ<ω1is de?ned recursively as follows:
(1)A 0={?}and A 1={{n }:n ∈N };
(2)A ζ+1={s ∈[N ]<ω>0:s ={n }∪s 1,where n ∈N ,{n }0:s = n i =1s i ,where n =min s 1,s 1<···
s 1,...,s n ∈A ωβ};
(3ii)for a non-zero,countable limit ordinal λ,
A ωλ={s ∈[N ]<ω>0:s ∈A ωλn with n =min s };and
(3iii)for a limit ordinal ξsuch that ωα<ξ<ωα+1for some 0<α<ω1,if ξ=ωαp + m i =1ωa i p i ,where m ∈N with m ≥0,p,p 1,...,p m are natural numbers
with p,p 1,...,p m ≥1(so that either p >1,or p =1and m ≥1)and a,a 1,...,a m are ordinals with a >a 1>···a m >0,A ξ={s ∈[N ]<ω>0:s =s 0∪( m i =1s i )with s m <···
with s 01<···
?1≤i ≤m }.
Note that in case 3(iii))above the Cantor normal form of ordinals is employed (cf.[KM],[L]).Note also that for k a natural number,i.e.a ?nite ordinal,the Schreier family A k coincides with the family of all k -elements subsets of the natural numbers.In the de?nition of a Schreier system (A ξ)ξ<ω1we can ?x for each non-zero,countable,
limit ordinal λthe particular sequence ((λ)n )n ∈N or equivalently the sequence of successor ordinals ((λ)1n )n ∈N de?ned below:
De?nition 0.5.Let λbe a non-zero,countable,limit ordinal and n ∈N .
(i)We de?ne inductively the ordinal (λ)n as follows:
(1)(ω)n =n .
(2)(ωα+1)n =ωαn for every 0<α<ω1.
(3)For a non-zero,countable limit ordinal αwith α<ωα,
(ωα)n =ω(α)n .
(4)For a non-zero,countable limit ordinalαwithα=ωα,letβ0be the smallest
ordinal such thatαcan be obtained as the limit of the sequence(βn)n∈N,where βn+1=ωβn.We set(α)n=βn.
(5)For a limit ordinalλ=ωα1p1+...+ωαm p m,where m,p1,...,p m∈N and
λ>α1>...>αm>0
(λ)n=ωα1p1+...+ωαm?1p m?1+ωαm(p m?1)+(ωαm)n.
(ii)Consider the strictly decreasing sequenceλ(0),λ(1),...,λ(kλ
n )
de?ned byλ(0)=λ,
λ(i+1)=(λ(i))n for0≤i n ) is a successor ordinal.As this sequence of ordinals is strictly decreasing,it must terminate and let(λ)1n=λ(kλ n ) be the?nal term of this sequence. Although the recursive Schreier system(Aξ)ξ<ω 1 is a purely combinatorial entity,it nevertheless arose gradually in connection with the theory of Banach spaces,originally the family Aξwas de?ned by Schreier([S])(forξ=ω),next by Alspach-Odell[AO] (forξ=ωκ,κa natural number)and Alspach-Argyros[AA](forξ=ωα,αa countable ordinal),and?nally by Farmaki[F1],[F2],[F3]and Tomczak-Jaegermann[TJ](forξany countable ordinal).(The reader is referred to the introduction of[F3]for more details). Schreier sets were used?rstly for the following trans?nite extension of the classical Ramsey partition theorem([R]),a result about the existence of monochromatic sets for ?nite colorations of the family of all k-tuples,with k a natural number: Theorem0.6(Ramsey partition theorem on Schreier sets,([F2])).Letξbe a non-zero countable ordinal number.For any?nite colorationχof the family Aξand M an in?nite subset of N there exists an in?nite subset L of M such that Aξ∩[L]<ωis monochromatic. Using the family Aξwe de?ne(in De?nition2.1)the families Wξ(Σ),Wξ(Σ;υ)of Schreier-type sets of words,variable words respectively overΣ,of a?xed countable ordinal numberξ.Carlson’s theorem(Theorem0.1)and the more general Furstenberg-Katznelson’s theorem(Theorem0.2)will be extended from k-tuples to Schreier-type sets of every countably ordinal;this is the content of the main Theorem in Section2(see Theorem2.3).With the notation and de?nitions given in Section1,it reads as follows: Theorem A.Letξbe a countable ordinal,χ1:Wξ(Σ)→{1,...,r1}andχ2:Wξ(Σ;υ)→{1,...,r2}be?nite colorings of the sets Wξ(Σ)and Wξ(Σ;υ),respectively and w∈Wω(Σ;υ)be an in?nite sequence of variable words overΣ;then there exists a variable reduction u? w of w such that all the?nite reductions of u in the set Wξ(Σ)are monochromatic underχ1and all the?nite variable reductions of u in the set Wξ(Σ;υ) are monochromatic underχ2. The proof of this result is closer to the method employed by us in proving Schreier type extensions of Hindman’s and Milliken-Taylor’s theorems in[FN],which in turn is inspired by the method invented by Baumgartner to prove Hindman’s theorem in[B]; in particular,we do not use topological dynamics(as employed in[FK1])or idempotent ultra?lters(as employed in[C],[BBH]).Some consequences of the Main Theorem are described in Section2.Beside the Carlson and the Furstenberg-Katznelson theorems, Schreier-type extensions of the Hale-Jewett’s theorem([HJ])and consequently of the van der Waerden’s theorem([vdW])are obtained. Theorem A is next used,in conjuction with the tools developed in Section3,one of which is a suitable Cantor-Bendixson index,to strengthen Carlson’s in?nitary theorem (Theorem0.3)to various forms of Nash-Williams type partition theorems for words and variable words,involving Schreier families.A somewhat weaker version of our main results(Theorems4.2,4.4)is contained in the following statement,which also strengthen Theorem0.3(see Remark4.6). Theorem B.Let G?W<ω(Σ)and F?W<ω(Σ;υ)be trees and w∈Wω(Σ;υ)be an in?nite sequence of variable words overΣ;then either there exists a variable reduction u? w of w such that all the?nite reductions of u overΣare contained in G or there exists a countable ordinalξ1=ζG such that for allξ>ξ1there exists a variable reduction w u? w of w such that all the?nite reductions of u in the set Wξ(Σ)are contained in the complement of G. Furthermore,either there exists a variable reduction u? w of w such that all the?nite variable reductions of u overΣare contained in F or there exists a countable ordinal such that for allξ>ξ2there exists a variable reduction u? w of w such that all ξ2=ζF w the?nite variable reductions of u in the set Wξ(Σ;υ)are contained in the complement of F. Theorem B is strengthened,involving the Ellentuck topology T E in Theorem5.2.A simple consequence of Theorem5.2is the characterization of completely Ramsey parti-tions of Wω(Σ)and Wω(Σ;υ)in terms of the Baire property in the topology T E,a result proved with di?erent methods by Carlson in[C]. Let us remark at this point that the attractive alternative approach to Ramsey theory, via located words rather than’classical’words,given by Bergelson-Blass-Hindman in [BBH],also admits of a Schreier-type extension,analogous to the one given in the present paper.The details will appear elsewhere. The extended Ramsey theory developed in the present paper is a more powerful tool than the’classical’Ramsey theory in that Schreier sets of all countable-ordinal orders capture a considerable part of Analysis,which is beyond the reach of the arithmetically oriented’classical’Ramsey theory.This is attested by the fact that the Schreier families have found essential applications in Banach space theory on such questions as,for exam-ple,unconditionality,l1and c0embeddability,and distortion(see e.g.[F1],[O],[AGR], [F4]). It is also noteworthy that the hereditary family(Aω)?={t∈[N]<ω:t?s for some s∈Aω}∪{?}generated by Aω?gures prominently(under the name of the family of“not large”sets)in fundamental questions of mathematical logic,speci?cally in the (Ramsey type)Paris-Harrington statements,statements true and provable in set-theory but unprovable in Peano arithmetic(cf.[PH],[KS]and[GRS],pp.169-180).The higher order hereditary Schreier families(Aξ)?might well be useful in forming and proving statements true but unprovable in certain systems endowed with induction stronger than that in Peano arithmetic. The fact that Carlson’s and Furstenberg-Katznelson’s partition theorems have found important applications in various branches of Mathematics,including Ramsey ergodic theory,such as in the proof of the density version of the Hales-Jewett theorem by Fursten-berg and Katznelson in[FK2],and the deep relations that exist between Ramsey ergodic theory and the exciting methods developed by Green and Tao in[GT]on the existence of arbitrarily long arithmetic progressions of primes,make it reasonable to expect that the Schreier-type extension of Ramsey theory presented in this paper will?nd interesting applications. 1.terminology and notation We develop in this section the necessary terminology and notation.We denote by N={1,2,...}the set of natural numbers,[N]<ω the set of all non-empty,?nite subsets >0 of N,[N]<ω=[N]<ω>0∪{?}and[N]ωthe set of all in?nite subsets of N. LetΣbe a?nite,non-empty alphabet,andυ/∈Σan entity which we call a variable. A word overΣis a?nite sequence of elements ofΣ.The set of all the words overΣis denoted by W(Σ);thus W(Σ)={w=α1...αk:k∈N,α1,...,αk∈Σ}. W(Σ)is turned into a semigroup by the operation of concatenation:the concatenation of two words w1=α1...αk,w2=β1...βl overΣis de?ned to be the word w1?w2=α1...αkβ1...βl. For two words w1=α1...αk,w2=β1...βl overΣwe write w1∝w2i?k and in case w1∝w2we set w2?w1=βk+1...βl∈W(Σ). A variable word overΣis a word overΣ∪{υ}in whichυactually appears.So,the set W(Σ;υ)of variable words overΣis de?ned as W(Σ;υ)=W(Σ∪{υ})\W(Σ). We note that the concatenation of two variable words is also a variable word.If w is a variable word overΣandα∈Σ∪{υ}then we write w(α)for the result of replacing every occurence of the variableυin w byα.Thus w(α)∈W(Σ)forα∈Σand w(υ)=w. For two variable words w1=α1...αk,w2=β1...βl overΣwe write w1∝w2i?k W<ω(Σ;υ)={w=(w1,...,w l):l∈N,w1,...,w l∈W(Σ;υ)}∪{?}, Wω(Σ)={ w=(w n)n∈N:w n∈W(Σ)for every n∈N}, Wω(Σ;υ)={ w=(w n)n∈N:w n∈W(Σ;υ)for every n∈N}. The complexity of a?nite sequence w=(w1,...,w l)∈W<ω(Σ∪{υ})\{?}of words, with w i=αk i αk i+1 ...αk i+1?1 for i=1,...,l,is described by the complexity of the corre- sponding?nite sequence of natural numbers1=k1<··· with d(w)=?if l=1,and d(w)={k2 w n=αk n αk n+1 ...αk n+1?1 for all n∈N,the corresponding complexity is described by the complexity of the in?nite sequence1=k1 d:Wω(Σ∪υ)→[N]ωwith d((w n)n∈N)=(k2 A?nite sequence w=(w1,...,w l)∈W<ω(Σ∪{υ})is an initial segment of the?nite sequence u=(u1,...,u k)∈W<ω(Σ∪{υ})i?l u\w=(u l+1,...,u k)and u\w=(u n)n>l respectively. De?nition1.1.(1)(Reduction of an in?nite sequence of words by a word)For an in?nite sequence w=(w n)n∈N∈Wω(Σ;υ)of variable words and for a(variable or non-variable) word t=α1...αk∈W(Σ∪{υ})(over the alphabetΣ),we set w[t]=w1(α1)?...?w k(αk)∈W(Σ∪{υ}). The family RW( w)of all the reduced words and the family V RW( w)of all the variable reduced words of w overΣare de?ned as follows: RW( w)={ w[t]:t∈W(Σ)}and V RW( w)={ w[t]:t∈W(Σ;υ)}. For u1= w[t1],u2= w[t2]∈RW( w)(resp.u1,u2∈V RW( w))we write u1∝u2i?t1∝t2. (2)(Reduction of an in?nite sequence of words by a?nite sequence of words)For an in?nite sequence w=(w n)n∈N∈Wω(Σ;υ)of variable words and for a?nite sequence of(variable or non-variable)words t=(t1,...,t l)∈W<ω(Σ∪{υ})\{?},with t i=αk i αk i+1 ...αk i+1?1 for all i=1,...,l,we set w[t]=(u1,...,u l)∈W<ω(Σ∪{υ})where u i=w k i (αk i )?w k i+1 (αk i+1 )?...?w k i+1?1 (αk i+1?1 )for all i=1,...,l. Also we set w[?]=?.The?nite sequences of words w[t]for t∈W<ω(Σ)are called?nite reductions of w overΣand the?nite sequences of variable words w[t]for t∈W<ω(Σ;υ) are called?nite variable reductions of w overΣ.The set of all the?nite reductions and the set of all the?nite variable reductions of w overΣare denoted as follows: RW<ω( w)={ w[t]:t∈W<ω(Σ)}and V RW<ω( w)={ w[t]:t∈W<ω(Σ;υ)}. We set d w:RW<ω( w)∪V RW<ω( w)\{?}→[N]<ωwith d w( w[t])=d(t). Observ e that RW<ω( e)=W<ω(Σ),V RW<ω( e)=W<ω(Σ;υ)and d e=d i f e=(e n)n∈N with e n=υfor every n∈N.Note also that it is not always true that d w(u)=d(u)for every u∈RW<ω( w). (3)(Reduction of an in?nite sequence of words by an in?nite sequence of words)For an in?nite sequence w=(w n)n∈N∈Wω(Σ;υ)of variable words and for an in?nite sequence t=(t n)n∈N∈Wω(Σ∪{υ})of(variable or non-variable)words,with t n= αk n αk n+1 ...αk n+1?1 for all n∈N,we set w[ t]=(u n)n∈N∈Wω(Σ∪{υ})where u n=w k n (αk n )?w k n+1 (αk n+1 )?...?w k n+1?1 (αk n+1?1 )for all n∈N. An in?nite sequences of words w[ t]for t∈Wω(Σ)is called a reduction of w overΣand for t∈Wω(Σ;υ)a variable reduction of w overΣ,respectively.The sets of all the reductions and all the variable reductions of w overΣrespectively are denoted as follows: RWω( w)={ w[ t]: t∈Wω(Σ)}and V RWω( w)={ w[ t]: t∈Wω(Σ;υ)}. For u, w∈Wω(Σ;υ),we write u? w if and only if u∈V RWω( w). Notice that u? w if and only if V RW( u)?V RW( w).Hence, w? e for every w∈W<ω(Σ;υ)in case e=(e n)n∈N with e n=υfor every n∈N.We de?ne d w:RWω( w)∪V RWω( w)→[N]ωwith d w( w[ t])=d( t). (1*)(Reduction of a?nite sequence of words by a word)For a?nite sequence w= (w1,...,w n)∈W<ω(Σ;υ)of variable words over the alphabetΣ,we de?ne the sets RW((w1,...,w n))={w1(α1)?...?w n(αn):α1...αn∈W(Σ)}and V RW((w1,...,w n))={w1(α1)?...?w n(αn):α1...αn∈W(Σ;υ)}, of all the reduced words and variable reduced words,respectively,of(w1,...,w n)overΣ. Notice that RW((w1,...,w n)),V RW((w1,...,w n))are?nite sets and that for a se-quence w=(w n)n∈N∈Wω(Σ;υ)we have that RW( w)= {RW(w1,...,w n):n∈N} and V RW( w)= {V RW(w1,...,w n):n∈N}. (2*)(Reduction of a?nite sequence of words by a?nite sequence of words)For a?nite sequence w=(w1,...,w n)∈W<ω(Σ;υ)of variable words over the alphabetΣ,we de?ne analogously the families RW<ω(w)and V RW<ω(w)of all?nite reductions and variable?nite reductions,respectively,of w overΣ.So,(u1,...,u l)∈RW<ω(w)if there exists t=(t1,...,t l)∈W<ω(Σ),where t i=αk i αk i+1 ...αk i+1?1 for all i=1,...,l and k l+1=n+1,such that u i=w k i (αk i )?w k i+1 (αk i+1 )?...?w k i+1?1 (αk i+1?1 )for i=1,...,l. We set d w(u)={k2,...,k l}. In the sequel we will also employ the following notation.For the families G?W<ω(Σ), F?W<ω(Σ;υ)and the words s∈W(Σ),t∈W(Σ;υ)we set G(s)={w∈W<ω(Σ):either w=(w1,...,w l)=?,s∝w1and (s,w1?s,w2,...,w l)∈G or w=?and(s)∈G},and F(t)={w∈W<ω(Σ;υ):either w=(w1,...,w l),t∝w1and (t,w1?t,w2,...,w l)∈F,or w=?and(t)∈F}. Also, G?s={w∈G:either w=(w1,...,w l)and s∝w1,or w=?}and F?t={w∈F:either w=(w1,...,w l)and t∝w1,or w=?}. For the sequence w=(w n)n∈N∈Wω(Σ;υ)and the words t∈V RW( w),s∈RW( w)) with t∈V RW((w1,...,w k))and s∈RW((w1,...,w k))for some k∈N,we set w?t=(w0,w k+2,w k+3,...)∈V RWω( w),where w0=t?w k+1,and w?s=(w0,w k+2,w k+3,...)∈V RWω( w),where w0=s?w k+1. Also,we set w\t= w\s=(w k+1,w k+2,...)∈Wω(Σ;υ). 2.The main partition theorem on Schreier families The main theorem of this section is Theorem2.3,given in equivalent form in Theo-rem2.6;this is a partition theorem for the Schreier?nite sequences of words and the Schreier?nite sequences of variable words over a?nite non-empty alphabetΣof every countable order,and constitutes an extension to every countable orderξ(a)of Carlson’s theorem,Theorem0.1,corresponding to ordinal levelξ=0and(b)of Theorem0.2, proved by Furstenberg and Katznelson,corresponding to?nite ordinalsξ<ω. In order to state Theorem2.3we need the following de?nitions: De?nition2.1(The Schreier systems(Wξ(Σ))0≤ξ<ω 1and(Wξ(Σ;υ))0≤ξ<ω 1 ).Let(Aξ)ξ<ω 1 be a Schreier system of families of?nite subsets of N andΣbe an alphabet.We will de?ne the families Wξ(Σ)and Wξ(Σ;υ)of the Schreier?nite sequences of words and of variable words overΣrespectively,for every countable ordinalξrecursively as follows: W0(Σ)={w=(w1):w1∈W(Σ)}and W0(Σ;υ)={w=(w1):w1∈W(Σ;υ)}, and for every countable ordinalξ≥1 Wξ(Σ)={w=(w1,...,w l)∈W<ω(Σ):d((w1,...,w l))∈Aξ};and Wξ(Σ;υ)={w=(w1,...,w l)∈W<ω(Σ;υ):d((w1,...,w l))∈Aξ}. For an in?nite sequence w=(w n)n∈N∈Wω(Σ;υ)of variable words overΣ,we de?ne the families of Schreier?nite reductions and of variable reductions of w overΣas follows: RW0( w)={u=(u1):u1∈RW( w)}and V RW0( w)={u=(u1):u1∈V RW( w)}. and for every countable ordinalξ≥1 RWξ( w)={u=(u1,...,u l)∈RW<ω( w):d w((u1,...,u l))∈Aξ};and V RWξ( w)={u=(u1,...,u l)∈V RW<ω( w):d w((u1,...,u l))∈Aξ}. Hence,a?nite sequence w∈W<ω(Σ)of words overΣbelongs to the family Wξ(Σ) for some1≤ξ<ω1i?w=(w1,...,w l)with l>1and there exist1=k1<···< k l l+1?1 ∈Σsuch that w i= αk i αk i+1 ...αk i+1?1 for all i=1,...,l. Observe that w=(w)∈W0(Σ)for every w∈W(Σ),while w=(w)/∈Wξ(Σ)for everyξ>0,also that Wξ(Σ)=RWξ( e)and Wξ(Σ;υ)=V RWξ( e)for every countable ordinalξ,in case e=(e n)n∈N with e n=υfor every n∈N and that it is not true that Wξ(Σ)=RWξ( w)for every w∈Wω(Σ;υ). The following proposition justi?es the recursiveness of the Schreier systems(Wξ(Σ))0≤ξ<ω 1 and(Wξ(Σ;υ))0≤ξ<ω 1 . Proposition2.2.For every countable ordinalξ>0there exists a concrete sequence (ξn)n>1of countable ordinals withξn<ξfor every n∈N,1 Wξ(Σ)(s)=Wξn(Σ)∩(W<ω(Σ)?s)and Wξ(Σ;υ)(t)=Wξn(Σ;υ)∩(W<ω(Σ;υ)?t) for every n∈N,1 Proof.According to Proposition1.7in[F3],for every countable ordinalξ>0there exists a concrete sequence(ξn)of countable ordinals withξn<ξsuch that Aξ(n)=Aξ n ∩[{n+1,n+2,...}]<ωfor every n∈N, where,Aξ(n)={s∈[N]<ω:{n} Moreover,ξn=ζfor every n∈N ifξ=ζ+1and(ξn)is a strictly increasing sequence with sup nξn=ξifξis a limit ordinal. Let n>1and s=α1...αn?1∈W(Σ),t=β1...βn?1∈W(Σ;υ).We will prove that Wξ(Σ)(s)=Wξn(Σ)∩(W<ω(Σ)?s)for every countable ordinalξ>0.Similarly can be proved that Wξ(Σ;υ)(t)=Wξn(Σ;υ)∩(W<ω(Σ;υ)?t)for every0<ξ<ω1. Forξ=1,of course W1(Σ)(s)=W0(Σ)∩(W<ω(Σ)?s).Let1<ξ<ω1.Then ?/∈Wξ(Σ)(s),since if?∈Wξ(Σ)(s),then(s)∈Wξ(Σ)forξ>0and of course?/∈Wξn(Σ)for every0≤ξn<ω1.Let w=(w1,...,w l)∈W<ω(Σ)\{?}.Then there exist 1=k1<··· l+1?1∈Σsuch that w i=αk i αk i+1 ...αk i+1?1 for all i=1,...,l. If w∈Wξ(Σ)(s),then s∝w1and(s,w1?s,...,w l)∈Wξ(Σ).In case l>1we have that n n and consequently (w1,w2,...,w l)∈Wξn(Σ)∩(W<ω(Σ)?s).In case w=(w1)∈Wξ(Σ)(s),we have that s∝w1and(s,w1?s)∈Wξ(Σ).Thus{n}∈Aξand consequently?∈Aξ n .This implies ξn=0and indeed w∈Wξn(Σ)∩(W<ω(Σ)?s). If w=(w1,...,w l)∈Wξn(Σ)∩(W<ω(Σ)?s)and l>1,then{k2,...,k l}∈Aξ n ∩[{n+1,n+2,...}]<ω?Aξ(n).Hence,{n,k2,...,k l}∈Aξ,so(s,w1?s,...,w k)∈Wξ(Σ)and consequently w∈Wξ(Σ)(s).If w=(w1)∈Wξn(Σ)∩(W<ω(Σ)?s),then ξn=0and consequently{n}∈Aξ.Hence(s,w1?s)∈Wξ(Σ)and w∈Wξ(Σ)(s). Now we can state and prove the main theorem of this section. Theorem2.3(A partition theorem on Schreier sets of words).Letξbe a countable ordinal andΣa?nite non-empty alphabet.For every G?W<ω(Σ),F?W<ω(Σ;υ)and every in?nite sequence w∈Wω(Σ;υ)of variable words overΣthere exists a variable reduction u? w of w overΣsuch that: either Wξ(Σ)∩RW<ω( u)?G or Wξ(Σ)∩RW<ω( u)?W<ω(Σ)\G,and either Wξ(Σ;υ)∩V RW<ω( u)?F or Wξ(Σ;υ)∩V RW<ω( u)?W<ω(Σ;υ)\F. For the proof of this partition theorem we will make use of a diagonal argument, contained in the following lemmas. Lemma2.4.Let w=(w n)n∈N∈Wω(Σ;υ)be an in?nite sequence of variable words over the alphabetΣandΠ1={(s, u):s∈RW( w)and u? w\s}. If a subset R ofΠ1satis?es: (i)for every(s, u)∈Π1there exists(s, u1)∈R with u1? u;and (ii)for every(s, u1)∈R and u2? u1we have(s, u2)∈R, then there exists u? w such that(s, s)∈R for all s∈RW( u)and s? u\s. Proof.Let u0=w1and u0= w.According to conditions(i)and(ii),there exists u1=(u1n)n∈N∈Wω(Σ;υ)such that u1? w\u0and(u0(α), u1)∈R for every α∈Σ.Let u1=u11.Then(u0,u1)∈V RW<ω( w).We assume now that there have been constructed u1,..., u n∈Wω(Σ;υ)and u0,u1,...,u n∈W(Σ;υ)such that (u0,u1,...,u n)∈V RW<ω( w),u i∈V RW( u i), u i? u i?1\u i?1for each1≤i≤n and (s, u i)∈R for all s∈RW((u0,...,u i?1))and1≤i≤n. We will construct u n+1and u n+1.Let RW((u0,...,u n))={s1,...,s k}for some k∈N. Then(s i, u)∈Π1for every u? u n\u n and i=1,...,k.According to condition(i),there exist u1n+1,..., u k n+1∈Wω(Σ;υ)such that u k n+1?···? u1n+1? u n\u n and(s i, u i n+1)∈R for every1≤i≤k.Set u n+1= u k n+1.If u n+1=(u n+1 i )i∈N,then set u n+1=u n+1 1 . Of course u n+1? u n\u n,u n+1∈V RW( u n+1),(u0,u1,...,u n+1)∈V RW<ω( w)and, according to condition(ii),(s i, u n+1)∈R for all1≤i≤k. Set u=(u0,u1,u2,...)∈Wω(Σ;υ).Then u? w,since(u0,u1,...,u n)∈V RW<ω( w) for every n∈N.Let s∈RW( u)and s? u\s.Then there exists n∈N such that s∈RW((u0,u1,...,u n)).Thus(s, u n+1)∈R and,according to(ii),(s, u\s)∈R,since u\s? u n+1.So(s, s)∈R,since s? u\s. Lemma2.5.Let w=(w n)n∈N∈Wω(Σ;υ)be an in?nite sequence of variable words over the alphabetΣandΠ2={(t, u):t∈V RW( w)and u? w\t}. If a subset R ofΠ2satis?es: (i)for every(t, u)∈Π2there exists(t, u1)∈R with u1? u;and (ii)for every(t, u1)∈R and u2? u1we have(t, u2)∈R, then there exists u? w such that(t, t)∈R for all t∈V RW( u)and t? u\t. Proof.Let u0=w1and u0= w.According to condition(i),there exists u1=(u1n)n∈N∈Wω(Σ;υ)such that u1? w\u0and(u0, u1)∈R.Let u1=u11.Then(u0,u1)∈V RW<ω( w).The proof can be continued analogously to the proof of Lemma2.4. We are now ready to prove Theorem2.3. Proof of Theorem2.3.Let G?W<ω(Σ),F?W<ω(Σ;υ)and w=(w n)n∈N∈Wω(Σ;υ). Forξ=0the theorem is valid,according to Carlson’s theorem,Theorem0.1.Letξ>0 be a countable ordinal.Assume that the theorem is valid for everyζ<ξ. For every reduced word s∈RW( w)of w overΣand every variable reduction u= (u n)n∈N? w\s of w\s overΣis de?ned the variable reduction u s=(s?u1,u2,...)? w of w overΣ.So,we can de?ne the following set R1={(s, u):s∈RW( w), u? w\s and either Wξ(Σ)(s)∩RW<ω( u s)?(G∩RW<ω( w))(s) or Wξ(Σ)(s)∩RW<ω( u s)?W<ω(Σ)\(G∩RW<ω( w))(s)}. Of course R1?Π1={(s, u):s∈RW( w)and u? w\s}and obviously R1satis?es the conditions(ii)of Lemma2.4.We will prove that R1satis?es also the condition(i) of Lemma2.4. Let(s, u)∈Π1.Then s∈RW( w)?W(Σ),hence s=α1...αn?1for some n∈N with n>1andα1,...,αn?1∈Σ.According to Proposition2.2,there existsξn<ξsuch that Wξ(Σ)(s)=Wξn(Σ)∩(W<ω(Σ)?s). If u=(u n)n∈N? w\s,then u s=(s?u1,u2,...)? https://www.wendangku.net/doc/199650990.html,ing the induction hypothesis, there exists a variable reduction u1=(u1n)n∈N? u s of u s overΣsuch that either Wξn(Σ)∩RW<ω( u1)?(G∩RW<ω( w))(s) or Wξn(Σ)∩R<ω( u1)?W<ω(Σ)\(G∩RW<ω( w))(s). Then either Wξ(Σ)(s)∩RW<ω( u1)?(G∩RW<ω( w))(s) or Wξ(Σ)(s)∩RW<ω( u1)?W<ω(Σ)\(G∩RW<ω( w))(s). Since u1=(u1n)n∈N? u s,we have that s∝u11so we set u1=(u11?s,u12,...).Then u1? u? w\s and( u1)s= u1.Thus(s, u1)∈R1.Hence,R1satis?es the condition(i) of Lemma2.4. According to Lemma2.4,there exists w1=(w1n)n∈N? w such that(s, s)∈R1for all s∈RW( w1)and s? w1\s.Thus,for every s∈RW( w1)and v=(v n)n∈N? w1?s, setting v1=(v1?s,v2,...)we have that(s, v1)∈R1and,since( v1)s= v we have that either Wξ(Σ)(s)∩RW<ω( v)?(G∩RW<ω( w))(s) or Wξ(Σ)(s)∩RW<ω( v)?W<ω(Σ)\(G∩RW<ω( w))(s). Now,de?ning analogously for every variable reduced word t∈V RW( w1)of w1overΣand every variable reduction u=(u n)n∈N? w1\t of w1\t overΣthe variable reduction u t=(t?u1,u2,...)? w1of w1overΣ,we can de?ne the set R2={(t, u):t∈V RW( w1), u? w1\t and either Wξ(Σ;υ)(t)∩V RW<ω( u t)?(F∩V RW<ω( w))(t) or Wξ(Σ;υ)(t)∩V RW<ω( u t)?W<ω(Σ;υ)\(F∩V RW<ω( w))(t)}. Then R2?Π2={(t, u):t∈V RW( w1)and u? w1\t}and R2satis?es the condition (ii)of Lemma2.5. Let(t, u)∈Π2.Then t∈V RW( w1)and t=β1...βn?1∈W(Σ;υ)for some n∈N with n>1andβ1,...,βn?1∈Σ∪{υ}.According to Proposition2.2,there existsξn<ξsuch that Wξ(Σ;υ)(t)=Wξn(Σ;υ)∩(W<ω(Σ;υ)?t). If u=(u n)n∈N? w1\t,then u t=(t?u1,u2,...)? https://www.wendangku.net/doc/199650990.html,ing the induction hypothesis, there exists a variable reduction u1=(u1n)n∈N? u t of u t overΣsuch that either Wξn(Σ;υ)∩V RW<ω( u1)?(F∩V RW<ω( w))(t) or Wξn(Σ;υ)∩V RW<ω( u1)?W<ω(Σ;υ)\(F∩V RW<ω( w))(t). Then either Wξ(Σ;υ)(t)∩V RW<ω( u1)?(F∩V RW<ω( w))(t) or Wξ(Σ;υ)(t)∩V RW<ω( u1)?W<ω(Σ;υ)\(F∩V RW<ω( w))(t). Seting u1=(u11?t,u12,...)we have that u1? u? w1\t and that(t, u1)∈R2.Hence, R2satis?es also the condition(i)of Lemma2.5(replacing w by w1). According to Lemma2.5,there exists w2=(w2n)n∈N? w1? w such that(t, t)∈R2for all t∈V RW( w2)and t? w2\t.Hence,for every s∈RW( w2)?RW( w1),t∈V RW( w2) and v1? w2?s? w1?s, v2? w2?t we have either Wξ(Σ)(s)∩RW<ω( v1)?(G∩RW<ω( w))(s) or Wξ(Σ)(s)∩RW<ω( v1)?W<ω(Σ)\(G∩RW<ω( w))(s);and either Wξ(Σ;υ)(t)∩V RW<ω( v2)?(F∩V RW<ω( w))(t) or Wξ(Σ;υ)(t)∩V RW<ω( v2)?W<ω(Σ;υ)\(F∩V RW<ω( w))(t). Let G1={s∈RW( w2):Wξ(Σ)(s)∩RW<ω( w2?s)?(G∩RW<ω( w))(s)}and F1={t∈V RW( w2):Wξ(Σ;υ)(t)∩V RW<ω( w2?t)?(F∩V RW<ω( w))(t)}. We use the induction hypothesis forξ=0(Theorem0.1).Then,there exists a variable reduction u? w2of w2such that: either RW( u)?G1or RW( u)?W(Σ)\G1;and either V RW( u)?F1or V RW( u)?W(Σ;υ)\F1. Since u? w2,we have that RW( u)?RW( w2)and V RW( u)?V RW( w2).Thus either Wξ(Σ)(s)∩RW<ω( u?s)?(G∩RW<ω( w))(s)for every s∈RW( u) or Wξ(Σ)(s)∩RW<ω( u?s)?W<ω(Σ)\(G∩RW<ω( w))(s)for every s∈RW( u); and either Wξ(Σ;υ)(t)∩V RW<ω( u?t)?(F∩V RW<ω( w))(t)for every t∈V RW( u) or Wξ(Σ;υ)(t)∩V RW<ω( u?t)?W<ω(Σ;υ)\(F∩V RW<ω( w))(t)for every t∈V RW( u). Hence, either Wξ(Σ)∩RW<ω( u)?G or Wξ(Σ)∩RW<ω( u)?W<ω(Σ)\G,and either Wξ(Σ;υ)∩V RW<ω( u)?F or Wξ(Σ;υ)∩V RW<ω( u)?W<ω(Σ;υ)\F. We next give a more general statement of Theorem2.3. Theorem2.6.Letξbe a countable ordinal,and w0∈Wω(Σ;υ)be an in?nite sequence of variable words over a?nite,non-empty alphabetΣ.For any?nite coloringsχ1: RWξ( w0)→{1,...,r1}andχ2:V RWξ( w0)→{1,...,r2}of the sets RWξ( w0)and V RWξ( w0)respectively and any variable reduction w? w0of w0overΣthere exists a variable reduction u? w of w overΣsuch that all the?nite reductions of w overΣin the set RWξ( w0)are monochromatic underχ1and all the?nite variable reductions of w overΣin the set V RWξ( w0)are monochromatic underχ2. Proof.Let f:W<ω(Σ∪{υ})→RW<ω( w0)∪V RW<ω( w0)with f(s)= w0[s].Given the?nite coloringsχ1:RWξ( w0)→{1,...,r1}andχ2:V RWξ( w0)→{1,...,r2} are de?ned the?nite coloringsψ1:W<ω(Σ)→{1,...,r1}whereψ1(s)=χ1(f(s))in case s∈Wξ(Σ)andψ1(s)=1otherwise andψ2:W<ω(Σ;υ)→{1,...,r2}where ψ2(t)=χ2(f(t))in case t∈Wξ(Σ;υ)andψ2(t)=1otherwise. For a given w? w0there exists t∈Wω(Σ;υ)such that w= w0[ t].According to Theorem2.3,there exists a variable reduction t1? t of t overΣsuch that the set Wξ(Σ)∩RW<ω( t1)is monochromatic underψ1and the set Wξ(Σ;υ)∩V RW<ω( t1)is monochromatic underψ2.Set u= w0[ t1]? w.Then the set RWξ( w0)∩RW<ω( u)is monochromatic underχ1and V RWξ( w0)∩V RW<ω( u)is monochromatic underχ2. We recall that in case w0= e=(e n)n∈N with e n=υfor every n∈N all the in?-nite sequences of variable words overΣare variable reductions of w0overΣand that RWξ( w0)=Wξ(Σ),V RWξ( w0)=Wξ(Σ;υ)for every0≤ξ<ω1.In this case Theo-rem2.6is indenti?ed with Theorem A referred to the introduction. For k∈N and u∈Wω(Σ;υ)we have that W k(Σ)∩RW<ω( u)=RW k( u)and W k(Σ;υ)∩V RW<ω( u)=V RW k( u),hence Theorem2.6in caseξ=k∈N implies Theorem0.2which essencially has be proved by Furstenberg and Katznelson in[FK1] (Theorems2.7and3.1). The following theorem is a?nitary consequence of Theorem2.6.It follows from The-orem2.6using a compactness argument.We will need the following notation to state it.For a word w=α1...αl over an alphabetΣlet l be the length of w.We denote by W l(Σ)the set of all words overΣwith length l.For a countable ordinalξ,we denote by Wξ (Σ)the set of all?nite sequences of words in Wξ(Σ)such that the sum of the lengths M of their words is equal to M. Theorem2.7(Extended Hales-Jewett theorem).For every r,n,k∈N,Σa?nite,non-empty alphabet of k elements andξa countable ordinal there exists M=M(r,n,k,ξ) (Σ)there exists a?nite sequence w=(w1,...,w n)of such that for every r-coloring of Wξ M (Σ)are monochro-variable words overΣall of whose the?nite reductions overΣin Wξ M matic. The classical Hales-Jewett theorem([HJ]),is a trivial consequence of the caseξ=0, n=1.Since van der Waerden’s theorem([vdW])may be obtained as a corollary of the Hales-Jewett theorem,Theorem2.7can be used to obtain a corresponding extention of van der Waerden’s theorem. Furstenberg and Katznelson in[FK1]introduced the notion of a k-dimensional combi-natorial subspace of W(Σ)for k∈N and proved(in Theorem3.1)a partition theorem about these combinatorial subspaces.Theorem2.3implies an extension of this partition theorem to every countable ordinal.Let give the neccesary notation. LetΣbe a?nite,non-empty alphabet.A?nite-dimensional combinatorial subspace [w]of W(Σ)is de?ned by a?nite sequence w=(w1,...,w k)∈W<ω(Σ;υ)of variable words overΣas follows: [w]=RW((w1,...,w k))={w1(α1)?...?w k(αk):α1,...,αk∈Σ}. In the same way an in?nite-dimensional combinatorial subspace[ w]of W(Σ)is de?ned by an in?nite sequence w=(w n)n∈N∈Wω(Σ;υ)}as follows: [ w]=RW( w)={w1(α1)?...?w k(αk):k∈N,α1,...,αk∈Σ}. A?nite(or in?nite)-dimensional combinatorial subspace of W(Σ)contained in an in?nite-dimensional combinatorial subspace[ w]of W(Σ)is called a?nite(or in?nite)-dimensional combinatorial subspace of[ w].It is not hard to check that a?nite-dimensional combinatorial subspaces of[ w]is of the form[u],where u∈V RW<ω( w)and that an in?nite-dimensional combinatorial subspaces of[ w]is of the form[ u],where u∈V RWω( w). De?nition2.8.Letξbe a countable ordinal.Aξ-combinatorial subspace[w]of W(Σ) is a?nite-dimensional combinatorial subspace of W(Σ)such that w∈Wξ(Σ;υ)and aξ-combinatorial subspace[w]of an in?nite-dimensional combinatorial subspace[ w]of W(Σ)is a?nite-dimensional combinatorial subspace of[ w]such that w∈V RWξ( w). The class of k-combinatorial subspaces of W(Σ),for k∈N,coincites with the class of k+1-dimensional combinatorial subspaces of W(Σ),while the class ofξ-combinatorial subspaces of W(Σ),for a countable ordinalξ≥ω,contains?nite-dimensional combina-torial subspaces of W(Σ)of arbitrary large?nite dimentions.Also,observe that although for k∈N the k-combinatorial subspaces of[ w]are exactly the k-combinatorial subspaces of W(Σ)contained in[ w],for a countable ordinalξ≥ωit is not always true that every ξ-combinatorial subspaces of[ w]is aξ-combinatorial subspaces of W(Σ),since it is not true that d w(w)=d(w)for every w∈R<ω( w). We will state now a corollary of Theorem2.3which extents Theorem3.1in[FK2], corresponding to?nite ordinalsξ<ω,to every countable ordinalξ. Corollary2.9(Combinatorial subspaces partition theorem).Letξbe a countable ordinal. For any?nite coloring of the set CSξ(Σ)of allξ-combinatorial subspaces of W(Σ)and any in?nite-dimensional combinatorial subspace[ w]of W(Σ),there exists an in?nite-dimensional combinatorial subspace[ u]of[ w]such that all theξ-combinatorial subspaces of W(Σ)contained in[ u]are monochromatic. Proof.Given the?nite coloringχ:CSξ(Σ)→{1,...,r},is de?ned the?nite coloring ψ:Wξ(Σ;υ)→{1,...,r}withψ(s)=χ([s]).Apply Theorem2.6for w0=(e n)n∈N with e n=υfor every n∈N.Then for any w∈Wω(Σ;υ),there exists a variable reduction u of w overΣsuch that all the elements of the set Wξ(Σ;υ)∩V RW<ω( u) areψ-monochromatic.Hence,for any in?nite-dimensional combinatorial subspace[ w]of W(Σ),there exists an in?nite-dimensional combinatorial subspace[ u]of[ w]such that all theξ-combinatorial subspaces of W(Σ)contained in[ u]areχ-monochromatic. Corollary2.10.Letξbe a countable ordinal,and w0∈Wω(Σ;υ).For any?nite col-oring of allξ-combinatorial subspaces of[ w0]and any in?nite-dimensional combinatorial subspace[ w]of w0,there exists an in?nite-dimensional combinatorial subspace[ u]of[ w] such that all theξ-combinatorial subspaces of[ w0]contained in[ u]are monochromatic. Using the previous terminology we obtain a generalization of Hales-Jewett theorem to higher dimensions,as a consequence of Theorem2.7. Corollary2.11.For every r,n,k∈N,Σa?nite,non-empty alphabet of k elements andξa countable ordinal there exists M=M(r,n,k,ξ)such that for any r-coloring of W M(Σ)there exists a monochromaticξ-combinatorial subspace of W(Σ). 3.Basic properties of the Schreier type families of the finite sequences of words This section is preparatory for the results of sections 4and 5.We prove here (a)the thiness of the Schreier-type families of words W ξ(Σ)and variable words W ξ(Σ;υ)(Propo-sition 3.2),and (b)the canonical representation of every (in?nite or ?nite)sequence of (variable)words over Σwith respect to the Schreier-type families (Proposition 3.3).Fur-thermore we introduce the (strong)Cantor-Bendixson index of a hereditary subfamily of the family of the ?nite sequences of (variable)words (De?nition 3.10),and we prove that the index of the hereditary family generated by the ξ-Schreier-type family of ?nite sequences of words is ξ+1for every countable ordinal ξ(Proposition 3.12).In addi-tion,in Theorem 3.6,we strengthen Theorem 2.3in case the partition family is (not an arbitrary family but)a tree. De?nition 3.1.Let Σbe a ?nite,non empty alphabet and F ?W <ω(Σ∪{υ})be a family of ?nite sequences of words over Σ∪{υ}. (i)F is thin if there are no elements s =(s 1,...,s k ),t =(t 1,...,t k )∈F with s ∝t (which means that k (ii)F ?=F ∪{t ∈W <ω(Σ∪{υ}):t ∝s for some s ∈F}∪{?}. (iii)F is a tree if F ?=F . Proposition 3.2.Let w =(w n )n ∈N ∈W ω(Σ;υ)be an in?nite sequence of variable words over an alphabet Σ.The families W ξ(Σ;υ),W ξ(Σ),V RW ξ( w ),RW ξ( w )are thin for every ξ<ω1. Proof.It follows from the fact that the families A ξof Schreier ?nite subsets of N are thin (which means that if s,t ∈A ξand s is an initial segment of t ,then s =t ). Proposition 3.3.Let ξ>0be a countable ordinal number. (i)Every in?nite sequence s =(s n )n ∈N ∈W ω(Σ∪{υ})of words over Σ∪{υ}has canonical representation with respect to W ξ(Σ∪{υ}),which means that there exists a unique strictly increasing sequence (m n )n ∈N in N such that (s 1,...,s m 1)∈W ξ(Σ∪{υ}) and (s n ,s m n ?1+1,...,s m n )∈W ξ(Σ∪{υ})for every n >1,where s n =s 1?...?s m n ?1.(ii)Every nonempty ?nite sequence s =(s 1,...,s k )∈W <ω(Σ∪{υ})of words over Σ∪{υ}has canonical representation with respect to W ξ(Σ∪{υ}),which means that either s ∈ W ξ(Σ∪{υ}) ?\W ξ(Σ∪{υ})or there exist unique n ∈N ,and m 1,...,m n ∈N with m 1<... Wξ(Σ∪{υ})for every n>1,where s n=s1?...?s m n?1 and in case m n (s n+1,s m n+1 ,...,s k)∈ Wξ(Σ∪{υ}) ?\Wξ(Σ∪{υ})where s n+1=s1?...?s m n. Proof.(i)Letξ>0and s=(s n)n∈N∈Wω(Σ∪{υ}).Then the sequence d((s n)n∈N)= (k n)n≥2of natural numbers has canonical representation with respect to Aξ,which means that there exists a unique strictly increasing sequence(m n)n∈N in N so that(k2,...,k m 1 )∈ Aξand(k m n?1+1,...,k m n )∈Aξfor every n>1.Hence,(s1,...,s m 1 )∈Wξ(Σ∪{υ}) and(s n,s m n?1+1,...,s m n )∈Wξ(Σ∪{υ})for every n>1,where s n=s1?...?s m n?1 . (ii)Let s=(s1,...,s k)∈W<ω(Σ∪{υ}).Set s n=υfor every n∈N with n>k. The sequence s=(s n)n∈N∈Wω(Σ∪{υ})has canonical representation with respect to Wξ(Σ∪{υ}),according to(i). According to Proposition3.3,every?nite or in?nite reduction(or variable reduction) of a sequence w=(w n)n∈N∈Wω(Σ;υ)has canonical representation with respect to RWξ( w)(or to V RWξ( w)),for every1≤ξ<ω1.For example u ˉ= w[s]∈RW<ω( w) has canonical representation with respect to RWξ( w),as s has canonical representation with respect to Wξ(Σ). Now exploiting the canonical representation of every sequence of words overΣ∪{υ} with respect to Wξ(Σ∪{υ})we will give alternative descriptions of the dichotomies described in Theorem2.3. Proposition3.4.Let G?W<ω(Σ),F?W<ω(Σ;υ)and letξbe a countable ordinal. Then,for every in?nite sequence u=(u n)n∈N∈Wω(Σ;υ)of variable words overΣthe following are equivalent: (i)Wξ(Σ)∩RW<ω( u)?G(resp.Wξ(Σ;υ)∩V RW<ω( u)?F). (ii)For every variable reduction u1of u the unique initial segment s=(u11,...,u1m)of u1which is an element of Wξ(Σ;υ)satis?es the property(u11(α1),...,u1m(αm))∈G for everyα1,...,αm∈Σ(resp.the property s∈F). (iii)Given any sequence( u n)n∈N of in?nite sequences of variable words overΣsuch that u1? u and u n+1? u n for every n∈N and any t n∈V RW( u n)with t n∝t n+1 for every n∈N,there exists m∈N such that(t11(α1),...,t1m(αm))∈Wξ(Σ)∩G for everyα1,...,αm∈Σ,where t11=t1and t1i=t i?t i?1for i=2,...,m(resp.such that (t11,...,t1m)∈Wξ(Σ;υ)∩F). Proof.(i)?(ii).Let u1=(u1n)n∈N be a variable reduction of https://www.wendangku.net/doc/199650990.html,ing the canonical representation of u1with respect to Wξ(Σ;υ)(Proposition3.3),there exists a unique initial segment s=(u11,u12,...,u1m)of u1which is an element of Wξ(Σ;υ).According