The game introdues a pre-order vandthe orrespondingequivalenerelation

Comparison game on Borel ideals

Mihael

Hrus

ak, David

Meza-Al

antara

Abstrat.We propose and study a \lassiation" of Borelideals based on a

naturalinnitegameinvolvingapairofideals.Thegameinduesapre-orderv

and theorrespondingequivalenerelation. Thepre-orderiswellfoundedand

\almostlinear". WeonentrateonF andF

Æ

ideals. Inpartiular,weshow

thatallF-idealsarev-equivalentand formtheleast equivalenelass. There

isalsoa leastlassofnon-F Borelideals,and thereareat leasttwo distint

lassesofF

Æ

non-F ideals.

Keywords:idealson ountable sets, omparisongame,Tukey order,gameson

integers

Classiation: 03E15,03E05

Introdution

Weproposeandstudy anaturalWadge-liketwo-playergame,alled theom-

parison game, assoiated to a pair of ideals. The game introdues a pre-order

vandthe orrespondingequivalenerelation. On Borelideals,this pre-orderis

well-foundedandalmost-linear(allantihainshavesize atmost2).

We show that all F

-ideals are v-equivalent, and form the least equivalene

lass. In order to do this, we prove a ombinatorial haraterization of F

-

ideals,identifyingF

-idealsasexatlythoseBorelidealswhihhavetheP +

(tree)-

property onsidered byLaamme and Leary [4℄. There is also a\seond least"

equivalene lass, the equivalene lass of the ideal I

0

dened below. We show

thatthere areatleasttwodistintlassesofF

Æ non-F

ideals,andexatlytwo

distintlassesofanalytiP-ideals.

Wealsostudy aproblemofI.Farahonerninginner strutureof F

Æ -ideals,

loselyrelatedtotheomparisongame.

Byanidealon!wemeananidealIonaountablesetX (typiallyX=!the

rstinniteordinal)whihontainsallnitesubsetsofX anddoesnotontainX.

Byonsidering I asasubspae ofP(X), endowed with theprodut topologyof

theCantorspae 2 X

throughthe bijetionA7!

A

, weanalulate theBorel

omplexityofI.

Theresearhofthe rstandthe seondauthorwaspartiallysupportedbyPAPIITgrant

IN101608andCONACYTgrant80355.

TheseondauthorwassupportedbyCONACYTsholarship180319andpartiallysupported

1. ComparisonGame Order

Denition1.1. LetIand Jbeidealson!. The ComparisonGame forI andJ

denotedbyG(I;J)isdenedasfollows: Instepn,PlayerIhoosesanelementI

n

ofI and PlayerII hoosesanelement J

n

ofJ. PlayerII winsif S

n I

n

2I ifand

onlyif S

n J

n

2J;otherwise,PlayerI wins.

Comparisongameinduesanorderbetweenidealson!.

Denition 1.2. Let I and J be ideals on !. We say I v J if Player II has a

winning strategyintheomparison gameG(I;J). Wesaythat I'JifIvJand

JvI.

Letusnotethattherelationvisreexiveandtransitive,butnotantisymmet-

ri;andtherelation'isanequivalenerelation.

First, we will prove that the omparison game among Borel ideals is deter-

mined. Tothatendwedenethefollowinggame

Denition 1.3. The gameG 0

(I;J)is dened for idealsI andJ on! asfollows:

Instepn PlayerIhoosesanaturalnumberk

n

andPlayerII hooses anatural

numberl

n

. PlayerIIwinsiffk

n

:n<!g2Iifandonlyiffl

n

:n<!g2J.

Let us note that by dening aset

~

X = fx 2 !

!

: rng(x) 2Xg for asubset

X of P(!), wehavethat gameG 0

(I;J)is equivalentto theWadge game W(

~

I;

~

J)

(see[3℄).

Theorem1.4. PlayerI hasawinning strategyin G(I;J)ifand onlyifPlayerI

hasawinningstrategyin G 0

(I;J),andthesameforPlayerII.

Proof: First,letusassumethat PlayerIhasawinningstrategy onthegame

G(I;J),andtakeabijetivefuntionf from!onto!!suhthatiff(n)=hk;li

thenmaxfk;lgn. Awinning strategyforPlayerIin G 0

(I;J)anbedesribed

byplayinginparallelthegameG(I;J). Instep0,PlayerIplaystherstelement

k

0 of I

0

, where I

0

= (;). If in the rst n-many steps the players played a

sequene hk

0

;l

0

;:::;k

n

;l

n

iin the game G 0

(I;J), and attahed to this sequene,

weonsidertheorrespondingsequenehI

0

;fl

0 g;I

1

;fl

1 g;:::;I

n

;fl

n

giinthegame

G(I;J) aording to , then, by taking k

n+1

as the k-th element of I

l , where

f(n+1)=hk;li,(ifitexists,andk

n+1

=0ifnot), wehavedened thewinning

strategyfor PlayerI.This istrue sine S

n<!

I

n fk

n

:n<!g=f0g[ S

n I

n

andthesequenehI

0

;fl

0 g;I

1

;fl

1

g;:::ifollowsawinning strategyforPlayerI in

G(I;J),that isfk

n

:n<!g2Iifandonlyiffl

n

:n<!g2=J.

On the other hand, let us assume that Player I has a winning strategy in

G 0

(I;J). Instep0,PlayerIplaysfk

0

g,wherek

0

=(;),andinstepn+1PlayerI

plays fk

n+1

gwhere k

n+1

is the answergiven by PlayerI in G 0

(I;J) following

when PlayerII hasplayedthe l-th elementl

n+1 of J

k

where f(n+1) = hk;li,

if J

k

has at least l elements, and 0 if not. Then, S

n fk

n

g 2 I if and only if

fk

n

:n<!g2Iifandonlyif S

n J

n

=f0g[fl

n

:n<!g2=J.

Analogouslyitanbeprovedthat PlayerII hasawinning strategyin G(I;J)

0

Bythe previous theorem we an onludethat I v J if and only if

~

I

W

~

J.

AstheWadgeorderiswellfounded(Theorem21.15in[3℄),soistheomparison

gameorder,whihisalso\almostlinear".

Lemma1.5. If I, JandKareBorelideals,I6vJandJ6vKthenKvI.

Proof: The hypothesis means that Player I has a winning strategy in games

G(I;J) andG(J;K). ThenPlayerII is goingto followthose strategies. First, in

bothgamesG(I;J)andG(J;K),PlayerI followsherownstrategies,produingI

0

and J

0

. Given the rst hoie K

0

of PlayerI in G(K;I), letus onsider K

0 as

theanswerof PlayerII in G(J;K), and thenletJ

1

bethe answerofPlayerI in

thesamegame,givenbyherwinning strategy. Letusonsider J

1

astheanswer

ofPlayerII in G(I;J) andletI

1

betheanswerof PlayerIgivenbyher winning

strategy and thenI

1

will be theanswerof PlayerII in G(K;I). Let us suppose

that in step n, PlayerI hooses a set K

n

. That set an be onsidered as the

answerofPlayerIIin G(J;K)forthesequenehJ

0

;K

0

;J

1

;:::;J

n

i,andthenthe

winning strategy for PlayerI in this game makes her hoose a set J

n+1 . Suh

setJ

n+1

anbeonsideredas theanswerof PlayerII in G(I;J)forthesequene

hI

0

;J

1

;I

1

;:::;I

n

i and then thewinning strategy for PlayerI makes her hoose

a set I

n+1

. Suh set will be what PlayerII plays in G(K;I) in step n. Hene,

sinethesequeneshJ

0

;K

0

;J

1

;K

1

;:::iandhI

0

;J

1

;I

1

;J

2

;:::ifollowthewinning

strategiesforPlayerIin G(J;K)andG(I;J)respetively,wehavethat S

n J

n 2J

ifandonlyif S

n K

n

= 2K,and

S

n1 J

n

2Jifand onlyif S

n I

n

=

2Iand thenwe

aredone.

An immediate onsequeneof the previouslemma is that if we havetwo in-

omparableideals then everyother idealhas thesameorder relation with both

idealsof theinomparablepair.

Corollary1.6. LetIandJbetwov-inomparableideals. Then,foranyidealK

on!whihisnotv-equivalenttoInorJ,(KvI i KvJ)or(IvK i JvK).

Thenextlemmashowsthattheorderv\almost"respetsBorelomplexities.

Proposition1.7. If IandJareBorelideals,IvJandIis

thenJis

+1 .

Proof: It suÆes to show that if I is a 0

(respetively 0

) ideal then

~

I is

a 0

+1

(resp.

0

+1

) set. Dene a funtion rng

n : !

!

! P(!) by rng

n (x) =

fx(k) : k < ng for all x 2 !

!

. Note that rng

n

is a ontinuous funtion and

rng (x)=lim

n!1 rng

n

(x) forallx2!

!

. Hene,preimagesof lopensets under

rngare 0

2

sets,andindutivelyweangettheresult.

Anotheronsequeneis thatomparison gameorderis atleastaslongasthe

Borelhierarhy.

Corollary 1.8. ThegameG(I;J)isdeterminedforeverypairI;JofBorel

ideals.

Theequivalene lassesof' areunions of \intervals"of Wadge degrees

ofideals.

Thereareunountablymany'-lasses.

Question 1.9. Is theorder vlinear(a well order)? Arethere twoBorelideals

whih arev-equivalent,but oneis

whiletheotherisnot?

2. F

-ideals in theomparison gameorder

TheidealFinisbelowallidealsinthev-order. Wewillshowthat theequiv-

alenelassofFinonsistsexatlyofF

-ideals. Intheproesswegiveaombi-

natorialharaterization of F

-ideals asexatlythoseBorel idealswhihsatisfy

theP +

(tree)-property.

Proposition 2.1. LetJbeanidealon!. ThenFinvJ.

Proof: Awinning strategyforPlayerII inG(Fin;J)isthefollowing. PlayerII

answerstheinitialintervalJ

n

=[0;max(

S

in I

i

)℄,giventhat I

i

,(in)arethe

nite sets playedby PlayerI until step n. Then, S

n I

n

2 Finimplies S

n J

n is

anite set and then anelementof J. On theother hand, if S

n I

n

=

2 Fin then

S

n J

n

=!2J +

.

Remark 2.2. If I is an ideal on ! then I vFin ifand only if PlayerII has a

winningstrategyinthegameG 00

(I)denedasfollows: Instepn,PlayerIhooses

anelementI

n

of I and PlayerII hoosesanaturalnumberk

n

. PlayerII winsif

S

n I

n

2Iifandonlyifthesequenefk

n

:n<!gisbounded.

Tosee this, notethat ifPlayerIIhas awinning strategy inG(I;Fin)then in

step n, PlayerII of G 00

(I) plays k

n

= maxJ

n

, where J

n

is the nite set played

byPlayerII followingaxed winning strategyfor herin G(I;Fin), keepingthe

sameplay by PlayerI.Ontheother hand,thewinning strategyforPlayerII in

G(I;Fin)onsistsintoplayfk

n

ginstepn,wherek

n

istheanswergiveninstepn

foraxedwinning strategyforPlayerII inG 00

(I).

DealingwithF

ideals,thefollowingtheoremisuseful. Alowersemiontinuous

submeasurefor !(lssm)isafuntion ':P(!)![0;1℄suhthat (1)'(;)=0,

(2) '(A) '(B) if A B, (3) '(A[B) '(A)+'(B) and (4) '(A) =

lim

n!1

'(A\[0;n℄). If' isalssm thenFin(') =fA! :'(A) <1g isan

F

-ideal,andmoreover:

Theorem 2.3 (Mazur [5℄). For eah F

-ideal I there is a lssm ' suh that

I=Fin(').

UsingMazur'stheoremweanprovethatallF

-idealsareequivalent.

Lemma2.4. If Iis anF

-idealthenIvFin.

Proof: Let'bealssm suh thatI=Fin('). Letusplaythegame G 00

(I). In

stepn PlayerII plays k

n

, the minimal k 2! suh that '(

S

jn I

j

) <k. Then

'(

S

I

n

)<1ifand onlyiffk

n

:n<!gisbounded.

Thedenition ofaP +

(tree)-idealistakenfrom[4℄.

Denition2.5(LaammeandLeary[4℄). LetX beasetofinnitesubsetsof!.

A tree T ([!℄

<!

)

<!

is an X-tree of nite sets if for eah s 2 T there is an

X

s

2X suhthat s a

a2T foreaha2[X

s

℄

<!

.

AnidealIon!isaP +

(tree)-ideal ifeveryI +

-treeofnitesetshasabranhwhose

unionisin I +

.

LaammeandLearyprovedthatanidealIisnotP +

(tree)ifandonlyifPlayerI

has awinning strategy in the followinggame H(I): In step n, PlayerI hooses

anI-positivesetX

n

andPlayerII hoosesaniteset F

n X

n

. PlayerIIwinsif

S

n<!

F

n 2I

+

.

Infat,thisgameharaterizesF

-ideals,asthefollowingtheorem shows:

Theorem2.6. LetIbeaBorelideal. ThenIisaP +

(tree)-idealifandonlyif I

isanF

-ideal.

Proof: The theorem follows immediately from the following laim and Borel

determinay.

Claim 2.7. Let I be aBorel ideal. Then, Player II has a winning strategy in

H(I)ifandonlyif IisanF

-ideal.

Proof: If I is an F

ideal then there is a lssm ' suh that I = Fin ('). In

stepn, II playsanitesubsetF

n ofX

n

with'(F

n

)n. Thatis possible sine

'(X

n )=1.

Ontheotherhand,wewill provethatPlayerIhasawinning strategyin H(I)

ifIisnotanF

ideal. Reallthefollowingresult(Theorem21.22in[3℄).

Theorem2.8 (Kehris-Louveau-Woodin). LetX beaPolish spae,letAX

beanalyti,andletB X bearbitrarywithA\B=;. Theneitherthereisan

F

setKX separatingAfromB orthereisaperfetsetC A[Bsuhthat

C\B isountabledenseinC.

By2.8, there is aperfet set C P(!) suh that C\I +

is ountable dense

in C. Inthe Banah-Mazur game played inside C (denoted by G

0 )

1

in C\I +

,

Player I has a winning strategy, sine I is omeager in C. Now, we will prove

thatifPlayerI hasawinningstrategyinG

0 (C\I

+

)thenPlayerIhasawinning

strategyinH(I). LetbeawinningstrategyforPlayerIinG

0 (C\I

+

). Instep0,

let(;)=X

0 2V

0

=(;)beanI-positiveset. SuhsetexistssineV

0

isanopen

non-empty subset of C and I +

\C is dense in C. Let us assume that we have

denedourstrategy untilstepntogetherwithasequeneof-legalpositions.

Wewilldeneitforstepn+1. GivenananswerF X

n

ofPlayerIIfora-legal

sequenehX

0

;F

0

;:::;X

n 1

;F

n 1

;X

n

i, onsiders F asthelopen set U ofall

1

Banah-MazurgameG

0 (C\I

+

)isdenedasfollows:Instep0,PlayerIhoosesanonempty

opensetV

0

andPlayerIIhoosesanonemptyopensubsetU

0 ofV

0

.Instepn + 1,PlayerIhooses

anonemptyopenset V

n+1 U

n

and PlayerIIhooses anonemptyopenset U

n+1 V

n+1 .

PlayerIIwinsif T

Un= T

VnI +

.

subsetsAof!suhthatA\(max (F)+1)=F,andifhV

0

;U

0

;:::;V

n 1

;U

n 1

;V

n i

isthe-legal position assoiatedto hX

0

;F

0

;:::;X

n 1

;F

n 1

;X

n

i,then U =U

n ,

V

n+1

=(hV

0

;U

0

;:::;V

n 1

;U

n 1

;V

n

;U

n

i)andlet(bydensityofI +

inC)

(hX

0

;F

0

;:::;X

n 1

;F

n 1

;X

n

;Fi)=X

n+1 2V

n

be an I-positiveset. Finally, note that is awinning strategy for I, sine for

every-legalrun ofH(I)hX

0

;F

0

;X

1

;F

1

;:::i, S

n<!

F

n

T

n<!

U

n

2I.

ReturningtotheomparisongamewiththeidealFinasPlayerIIwehavethe

followingresult.

Lemma 2.9. If I is not aP +

(tree)-ideal then PlayerI hasa winning strategy

inG 00

(I).

Proof: Let T be an I +

-tree of nite sets with all branhes in I. In her rst

fewsteps,PlayerI playsin theinreasingorder theelementsof S

su

T

(;)until

PlayerIIinreasesheranswer.Ifinstepn,PlayerIIhoosesanumberbiggerthan

allofherpreviousplaysthenPlayerIolletsthe(nite)setF

0

ofanswersgiven

byheruntiltheurrentstepandthenshebeginstakingelementsofsu

T (F

0 )in

theinreasingorderuntilthePlayerII inreasesherhoie. Hene,ifeventually

PlayerII does notinreaseher piksthen PlayerI will hoose everyelement of

su

T

(t) for somet 2 T and then he will ollet anI-positive set. Inthe other

asePlayerII will ollet aset whih followsa branh of T and then itsunion

willbein I.

Theorem2.10. ForanyBorelidealI,I'Fin ifandonlyif IisF

.

Proof: Itfollowsfromtwofats: IfIis aBorelidealthenG 00

(I) isdetermined,

and by Theorem2.6, J is aP +

(tree)-idealifand onlyifJ isan F

-ideal, forall

BorelidealJ.

3. F

Æ

-ideals in theComparison Game Order

Wenow dene anideal I

0

whih is theminimal ideal I suh that there is an

I +

-treeofnitesets whih doesnothaveanI-positivebranh, i.e.whih isnota

P +

(tree)-ideal. LetusdenoteA

f

=ffn:n<!gforagivenf 22

!

.

Denition3.1. TheidealI

0

istheidealon2

<!

generatedbythefamilyofsets

A

f

wheref 22

!

isnoteventuallyzero.

Theorem3.2. If IisaBorelidealwhihisnotF

thenI

0 vI.

Proof: BytheKehris-Louveau-Woodintheorem2.8thereisaCantorsetC

P(!) suh that D = CnI is ountable dense in C. Let T 2

<!

be aperfet

tree suh that [T℄ = C. Sine D is a ountable dense subset of 2

!

, there is a

homeomorphism ': 2

!

!C suh that if F =ff 2 2

!

:(8 1

n)f(n)=0g then

' 00

F =D. Suh ' indues anembedding 2

: 2

<!

![!℄

<!

whihis monotone

2

Theembeddingisdened sothat foreahs22

<!

,the niteset(s)determinesthe

00

(i.e.st implies(s)(t)) andsuhthat S

n

(f n)2Iifand onlyiff is

noteventuallyzero.

Now we desribe a winning strategy for Player II in G(I

0

;I). In step n, if

PlayerI playsI

n 2I

0

thenPlayerIIplaysJ

n

=[0;k

n

℄[ S

f(s):(9kn)(9t2

I

k

)(st)g,wherek

n

isthemaximalardinalityofanantihainin S

k n I

k .

Wearguewhythisis awinningstrategy forPlayerII.If I = S

n I

n 2I

0 then

therearem<! andf

0

;:::;f

m 22

!

nF suhthatI S

jm A

f

j

. Thenmisan

upperbound fork

n and

S

f(s):(9k<!)(9t2I

k

)(st)g S

jm S

n (f

j

n)2I, andthen S

n J

n

2I. Ontheotherhand,ifI 2=I

0

theneither hk

n

:n<!i

isunbounded, andthenJ = S

n J

n

=

2I, orthere isaneventuallyzerofuntion f

suhthat f n2I forinnitelymanyn<!,andin thatase,

[

n

f(s):(9t2I

n

)stg [

n

f(f n):n<!g2=I:

TheidealI

0 isF

Æ

. ConsideranotherF

Æ -ideal.

;Fin=fA!!:(8n)(9m)(8k)((n;k)2A!km)g:

Theorem3.3.

;Fin6vI

0 :

Proof: Forevery1n<!wedeneagameG

n

asfollows. Instepk,PlayerI

piksanitesubsetI

k

of!!andPlayerIIpiksanantihainJ

k

ofardinality

ninI

0

,andsuhthatforalli<kandalltinJ

i

thereisauniques2J

k

suhthat

st. PlayerIIwinsif S

n I

n

2;Finifandonlyif S

n J

n 2I

0

. Indutively,we

willprovethatPlayerIhasawinningstrategyingameG

n

,foralln,havingdone

that,wewillshowhow thisfat implies thatPlayerI hasawinning strategy in

G(;Fin;I

0 ).

Claim3.4. PlayerIhasawinning strategyin thegameG

n

,foralln.

Proofof Claim: First we prove that Player I has a winning strategy in the

gameG

1

. Instep0,PlayerIplaysf(0;0)g. Instepk,deneN(k)=minf P

h(l):

hisamaximalsequeneinJ

k

^l2dom(h)g,andPlayerIjustplaysadoubleton

with the form f(0;N(k));(n

k

;m

k

)g, where n

0

=m

0

= 0; (1) ifJ

k )J

k 1 and

thereism2J

k nJ

k 1

suhthatJ

k

(m)=1thenn

k

=n

k 1 andm

k

=m

k 1 +1;

and(2)n

k

=n

k 1

+1andm

k

=m

k +1

otherwise.

WeshowwhyisthisawinningstrategyforPlayerI.Ifinsomestepk,PlayerII

playsaninniteset J

k

thenshewill beplayingalongthebranh S

J

k

andthen

PlayerIknowthatshehaswonbeauseshejustwilllltheolumnf0g!if S

J

k

isnoteventuallyzero,orthe rawfkg! otherwise. Withoutlossofgenerality,

letusassumethat PlayerII playsniteinreasingsets. Thenif thereisK suh

that J

k

= J

K

for all k K then S

n J

n 2 I

0

but Player I will ll the olumn

fm

K

g(!nn

K

)for K minimal; and ifPlayerII inreasesthelengthof J

k for

innitelymanysteps k then,if there isK suh that theinreasing of J is just

with 0's then olumn f0gN(k) will not inrease and hoies of PlayerI will

follow ahorizontalline; but ifPlayerII inreasesthelengthof J

k

and sheadds

anew1in innitelymanystepsthenPlayerI willmaketheolumn f0gN(k)

inreasetof0g! andthen S

n I

n

=

2;Fin.

IndutivelyassumethatPlayerIhasawinningstrategyinG

n

andletusprove

thatshehasawinningstrategyinG

n+1

. Fixapartition fX j

i

:j n^i<!gof

!nf0g. In step0,PlayerI plays; andthen, assumethat PlayerII hasplayed

anantihain J

k

ofardinalityn+1(we anassume this by identifying J

k with

its maximal elements. Let us enumerate this antihain asfa 0

r

: r ngand for

eah r n, we enumerate J

k

= fa k

r

: r ng in suh way that a k

r a

0

r for all

rn. Then,PlayerI willplaysimultaneouslythegameG

n inX

r

i

! forsome

i (depending of k and r), where answersof Player I are given by the winning

strategyforherwhenPlayerIIplaysJ

k na

k

r

;andfollowingthisrule: Ifa k

r )a

k 1

r

andPlayerIisplayingintheopyX r

i

!thensheabandonsthisopyandbegins

playing G

n in X

r

i+1

!; and if not, she still playing in the sameX r

i

!, i.e.,

i(k;r)=i(k 1;r). Inbothases PlayerI addsthe olumn f0gN(k)(reall

N(k)wasdened twoparagraphsabove). Nowweprovethat this isa winning

strategyforPlayerI.

Ifallthesequenesa k

r

areeventuallyinreasingthenwehavetwoases:

(1)Foreah kn thesequene S

r a

k

r

isnoteventually-zero. Then, PlayerI

willinreasetheolumn f0gN(k)tof0g!,making S

n J

n

=

2;Fin.

(2) There is k n suh that S

r a

k

r

is an eventually-zerobranh. Then, the

olumnf0gN(k)willnotinreaseandin allthepiees ofthepartitionwill be

played the game G

n

and sineall inrease, all piees are eventuallyabandoned

andthen, S

n J

n

2;Fin.

Ifforsomek, thesequenea k

r

doesnotinreasethenPlayerI willbeplaying

the game G

n

and sine she has a winning strategy in this game, we are done,

beausetheolumnf0gN(k)will notinrease.

LetfX

r

: r <!gbe apartition of !nf0gin innite sets. The main ideais

basedonthefollowingtrik: PlayerIisgoingtoplaythegameG

n

butinX

n !

instead of ! !. In step 0, PlayerI plays ; and in step k > 0, let M(k) be

the maximal ardinality of an antihain in S

i<k J

i

. If M(k) = M(k 1) then

Player I has to play the game G

M(k ) in X

M(k 1)

! instead of !!, and if

M(k)>M(k 1), thenPlayerIhastoabandonwhathehasplayedandbegina

newgameofG

M(k )

insidetheopyX

M(k )

!,andinbothases,PlayerIhasto

addfminX

M(k )

gN(k)tothesetsdenedabove.

IfPlayerIImakesM(k)inreaseininnitelymanysteps,then S

n J

n

= 2I

0 ,but

PlayerI willabandonallpieeswhere heplayed,andthen S

n I

n

2;Fin.

IfthereisKsuhthatM(k)=M(K)forallk>Kthenthewinningstrategy

forPlayerIin G

M(K)

makesPlayerI wininG(;!;I

0

).

Nowwegiveariterionforidealsto bev-below;Fin.

Proposition3.5. LetIbeanidealon!. ThenIv;FinifandonlyifPlayerII

hasawinningstrategy in thefollowinggameG 000

(I): Instepn,PlayerI hooses

an element I

n

of I and then Player II hooses an inreasing funtion f

n 2 !

!

.

PlayerIIwinsif S

n I

n

2Iifandonlyifthesequeneff

n

:n<!gisbounded.

Proof: LetusassumethatPlayerIIhasawinningstrategyinG(I;;Fin). For

everyelementJ 2;Fin, letf

J

:!!! givenbyf

J

(n)=min fk>f

J

(n 1):

(8m > k) (n;m) 2= Jg. Then we desribe a winning strategy for Player II in

G 000

(I) asfollows: Given I

0

2 I, let f

0

be the funtion f

(I0)

. Assume that the

legalpositionhI

0

;f

0

;:::;I

n

;f

n

ifollowsthestrategywhihwearedening. Then

in parallel we havealegal position hI

0

;J

0

;:::;I

n

;J

n

iof G(I;;Fin) following

. Then,givenI

n+1

, deneJ

n+1

=(hI

0

;J

0

;:::;I

n

;J

n

;I

n+1

i)andthe funtion

f

n+1

=f

J

n+1

. It iseasyto hekthatthis isawinning strategyforPlayerII in

G 000

(I). Ontheotherhand,foranyfuntionf 2!

!

deneJ

f

=f(n;m)2!!:

mf(n)g. Analogoustorstpart,PlayerIIinG(I;;Fin)hasplaysJ

f where

f istheanswergivenbyPlayerIIin G 000

(I).

Ilijas Farah askedin [2℄ if for every F

Æ

-ideal I there is a family of ompat

hereditarysetsfC

n

:n<!gsuh that

I=fA!:(8n<!)(9m<!)(An[0;m)2C

n )g:

WewillsayIisaFarahideal ifIfullsthatproperty. NotethateveryFarahideal

IisanF

Æ

ideal. Thefollowingisasimpleobservation.

Proposition 3.6. Let I be anidealon !. Then, I isFarah ifand only ifthere

isasequenefF

n

:n<!gofhereditaryF

-sets losedundernitehangessuh

thatI= T

n F

n .

Proof: Let hC

n

: n < !i be a family of ompat hereditary sets suh that

I = fA ! : (8n)(9k)(Ank 2 C

n

)g. For any n, dene F

n

as the losure

of C

n

under nite hanges. It is lear that F

n

is hereditary, F

, losed under

nite hanges, and ontains I. If A 2 F

n

then there is a nite set F suh that

AMF 2C

n

andbytakinganadequatek>max(F)wehavethatAnk2C

n .

Now, letfF

n

:n<!gbeaninreasingsequene ofhereditary F

-sets losed

under nite hanges suh that I = T

n F

n

. Let us write F

n

= S

k E

n

k where

hE n

k

:k<!iisan inreasingsequeneof losed sets. We anassumethat eah

E n

k

isahereditaryset,andweandene

~

E n

k

=fAn(k+1)[fkg:A2E n

k g

and C

n

= f;g[ S

k

~

E n

k

. Note that eah C

n

is a losed hereditary set, and if

Ank 2 C

n

we an assume k 2 A and then A 2

~

E n

k F

n

, for all n. Finally,

ifA is an inniteset in I (the nite aseis trivial) then for eah n takek suh

thatAnk2E n

k

andk2A(thisispossiblesinetheE n

k

isaninreasingfamily).

HeneAnk2C .

Wedenotebynwdtheidealofallnowheredensesubsetsofthesetofrational

numbersQ.

Example3.7. Theidealnwd isFarah.

Proof: LetfU

n

:n<!gbeabaseofthetopologyofQ, anddeneF

n

=fA

Q :(9m)(U

m U

n

^A\U

m

=;)g. Notethat nwd= T

n F

n

and eahF

n isF

hereditaryandlosedundernite hanges.

WereneProposition3.6asfollows.

Theorem3.8. Let Ibeanidealon!. Then, IisFarahifand onlyifthereis a

sequenefF

n

:n<!gof F

setslosedundernitehangessuhthatI= T

n F

n .

Proof: Withoutlossofgenerality, weanassumethateveryF

n

is meager,be-

auseif F

n

isnon-meager thenthere is anon-empty lopenset ontainedin F

n

andbylosednessunder nitehanges,F

n

=2

!

.

SuÆienyisaonsequeneofProposition3.6,andbythesameresult,itwill

be enoughto provethatifF is ameagerF

-set losedunder nitehangesand

ontaining I, then there is a hereditary F

-set E suh that I E F, sine

thelosureofE undernitehangeswouldbethehereditarylosedunder nite

hanges wanted. Letus onsiderthe gameH dened sothatin stepk, PlayerI

hoosesaset B

k

=

2F andPlayerIIpiksanitesubseta

k ofB

k

. PlayerI wins

if S

k a

k

2I. Notethat H isdetermined sineIisBorel.

Claim3.9. PlayerII hasawinningstrategyin H.

Proofof laim: LetfE

n

:n<!gbeaninreasingsequeneoflosedsetssuh

that F = S

n E

n

and foreah n, let T

n

be a prunedtree suh that E

n

= [T

n

℄.

SineeahE

n

isanowheredenseset,instepk,ifPlayerIplaysB

k

thenthereis

m

k

<! suh that m

k 1

<m

k (m

1

=0) and

B

k m

k

= 2 T

k

. Then, PlayerII

playsa

k

=B

k

\m

k

. Itislearthat S

k a

k

=

2F andthen S

k a

k

=

2I.

Itisveryeasytoseethat

Claim3.10. PlayerIIhasawinningstrategyinHifthereisatreeT([!℄

<!

)

<!

suh that (a) forallA 2= F andall t2T there is a2su

T

(t)suhthat aA

and(b) S

n

f(n)2I +

forallf 2[T℄.

Hene,bydening C

t

=fA!: (8a2su

T

(t))(a*A)g,for allt2T, we

haveimmediatelythat C

t

islosedand hereditaryandI S

t2T C

t

. Finally,(a)

isequivalentto S

t2T C

t

F. Hene, S

t C

t

isthehereditaryF

-setrequired.

ByTheorem3.6 itislearthat anyFarahidealsatisesthefollowing.

Denition 3.11. Anideal Iis weakly Farah if thereis asequenehF

n

:n<!i

ofhereditaryF

-sets suhthat I= T

n F

n .

Withoutlossofgenerality,thesequeneinthepreviousdenitionisdereasing,

anditislearthatanyweaklyFarahidealisF

Æ .

Proof: LetfF

n

:n<!gbeafamilyofhereditaryF

-setssuhthatI= T

n F

n .

Without lossof generality, we an assume that for any n, F

n

= S

k E

n

k where

(E n

k )

k

isaninreasingsequeneoflosed hereditarysets. Then, foranyA!

A2I i (9f

A 2!

!

)(8k;n<!)(A2=E n

k

$k<f

A (n)):

Hene, playing the game G 000

(I), forany stepn, PlayerII playsf S

j<n I

j

. So, if

I = S

n<!

I

n

2I thenf

I

bounds allthef

In

funtions;and ifI 2=I thenthere is

j suhthat I 2=E j

k

forallk<! andthen, hf

In

(j):n<!iinreasesto innity,

beause in other ase, there were k suh that I

n 2 E

j

k

for all n and I 2= E j

k ,

ontraditingthelosednessofE j

k

.

Apositiveanswerto Farah's questionwould implythat everyF

Æ

-idealisv-

below;Fin.

ReallthefollowingharaterizationofanalytiP-ideals.

Theorem3.13 (Soleki [7℄). If I isan analytiP-ideal thenthere is alssm'

suhthat I=Exh(')=fA!:lim

n!1

'(An[n;1))=0g.

Note that by Soleki's theorem, every analyti P-ideal is a Farah ideal, and

then, ifI is ananalytiP-ideal then Iv;Fin. Conerning analytiP-ideals,

everyone of them is either equivalentwith Fin (i.e., is F

) or equivalent with

;Fin,i.e.,thelassofP-ideals\skips"theintermediatelassofI

0 .

Theorem3.14. LetIbeananalytiP-ideal. TheneitherI'FinorI';Fin.

Proof: Let'bealssmsuhthatI=Exh('). Considertwoases:

Case 1. There is">0suhthat foranyset X, '(X)<"impliesX 2I. Note

thanin suhase Iis anF

ideal,beauseC =fA! :'(X)"gisalosed

setandI= S

n

fA!:Ann2Cg.

Case 2. Forall">0there is anI-positivesetX suh that'(X)<". Wewill

usethefollowingresult,whihisaknownonsequeneofJalali-Naini{Talagrand

theorem(see[1℄).

Lemma 3.15 (Disjoint Renement Lemma for Denable Ideals, see [6℄). If I

is a hereditarily meager ideal and fX

m

: m < !g is a family of I-positive sets

thenthere isapairwise disjointfamilyfY

m

:m<!gofI-positivesets suh that

Y

m X

m

forallm<!.

TakeafamilyY

m

ofI-positivesetssuhthat'(Y

m )2

m

andbytheDisjoint

Renement Lemma for hereditary meagre ideals, there is a disjoint family of

positive sets fX

m

: m < !g suh that '(X

m ) 2

m

. Let fx m

k

: k < !g

be an enumeration of X

m

. Let us desribe a winning strategy for PlayerII in

G(;Fin;I). In stepn, ifPlayerI playsI

n

, we onsiderthe funtion f

n given

by f

n

(i) = maxf0g[fj : (9l n)((i;j) 2 I

l

)g and then PlayerII plays J

n

=

fx i

j :jf

n

(i)g. Hene,ifI = S

n I

n

2Ithenthefamilyhf

n

:n<!iisbounded

byafuntion f,andthen J = S

J

n

intersetseahX

n

in anitesetF

n whih

hassubmeasuresmallerthan 2 andso, J isa'-exhaustiveset. Ontheother

hand,ifI 2=;Finthenthereismsuhthatf

n

(m)inreasestoinnity,andso,

J\X

m

=X

m 2I

+

.

Realltheasymptotialdensity zeroideal Z isdened by

Z=

A!: lim

n!1

jA\[0;n)j

n

=0

and(byitsdenition)is ananalytiP-ideal.

Remark3.16. Thefollowingidealson! areomparisongameequivalent:

(1) Z,

(2) nwd,and

(3) ;Fin.

Proof: (1)'(3)useZ isananalytiP-idealwhihisnotF

.

(2)v(3)usenwdisaFarahideal.

(3)v(2) LetfV

n

:n<!gbeasequene ofpairwise disjointopensubsetsof

Q and for eah n, letfq n

k

: k < !gbe an enumeration of V

n

. Let us play the

G(;Fin;nwd) game. Instep n, if Player I hasplayedI

n

2 ;Fin, take a

funtion f 2!

!

suh that forall k;m, (k;m) 2I

n

impliesm f(k),and then

PlayerII mustplayJ

n

=fq k

s

:s<f(k)^k<!g. J

n

is anowheredensesubset

ofQ sineitintersetseahV

n

in anite set,and ifI = S

n I

n

2;Fin then

J = S

n J

n

intersetseahV

n

inaniteset,andthen,J 2nwd;andifforsomek,

I\(fkg!)isinnite,thenJ willontainV

k

,andthenJ 2nwd +

.

4. Finalremarks

ReallthatFinFinistheidealon!! generatedbytheolumnsfng!

and the sets f(n;m) : m < f(n)g, for f 2 !

!

. We nally will show that the

ideal FinFin belongs to a higher lass than ;Fin. It is easy to see that

;FinvFinFin.

Proposition 4.1. ;FinvFinFin.

Proof: LetfX

n

:n<!gbeaninnitepartitionof!ininnitepiees. GivenI

in;Fin,wedeneanelementJ

I

of;Finby

J

I

=f(k;l):(9n<!)(k2X

n

^(n;l)2I)g:

ThewinningstrategyforPlayerIIonsistsinplayingJ

In

asananswertoasetI

n

playedbyPlayerIinstepn. IfI = S

n I

n

2;FinthenJ = S

n J

In

2FinFin,

andifforsomek<!,I\(fkg!)isinnitethenJ\(flg!)willbeinnite

foralll2X

k

,andsoJ 2=FinFin.

Theorem4.2. FinFin6v;Fin.

Proof: We will desribe a winning strategy for Player I in G 000

(FinFin).

Withoutlossofgenerality,weanassumethatPlayerII playsinsuhawaythat

f

k

(n)f

k 1

(n)for alln. First,takeaninnitepartition fX

n

:n<!gof! in

innitepiees,and letfx n

r

:r<!gbeanenumerationofX

n

. PlayerIwill play

just seletorsofthefamilyfX

n

! :n<!g. Instep0,PlayerIplaysf(x 0

r

;0):

r<!g. Instep k, iff

k

=f

k 1 (f

1

0) and J

k 1

=f(x n

r

;m n

r

):r<!gthen

J

k +1

=f(x n

r

;m n

r

+1):r <!g, andotherwise, ifl=min fn: f

k

(n)>f

k 1 (n)g

thenJ

k +1

=f(x n

r

;m n

r

+1):rlg[f(x n

r+1

;m n

r

):r>lg.

IfthereisN suhthatff

k

(N):k<!ginreasesinnitelyoftenthen S

n J

n 2I

sine all but nitely many piees X

r

are \turning to the right" innitely often

and if ff

k

: k < !g is bounded by a funtion f then for eah r, there are k

and N suh that PlayerI will be \lling" the olumn fx k

r

g(!nN), making

S

n J

n

=

2FinFin.

Reallthatafuntionf fromItoJisaTukey funtion ifforeahA2Jthere

isB 2I suhthat I B iff(I)A. Tukeyorderis dened byI

T

J ifthere

is aTukeyfuntion from I to J; and let us denote by I

MT

J when there is a

monotone (with respet to inlusion) Tukeyfuntion from I to J. Theorder v

renesthemonotoneTukeyorder.

Lemma4.3. If I

MT

JthenIvJ.

Proof: Letf :I !Jbe amonotoneTukeyfuntion. Then PlayerII onlyhas

toanswerf(I

n

)foranyI

n

givenbyPlayerI.If S

n I

n

2Ithen bymonotoniity,

S

n f(I

n )f(

S

n I

n

)2J. If S

n I

n

=

2IthenbyTukeyness S

n f(I

n

)2=J.

Note that the Tukeyand monotone Tukeyorders are quite dierent: There

isa Tukey-maximalidealamong all ideals,whihis F

. On theother hand,by

Lemma4.3andProposition1.7,ifI

MT

JandIisF

thenJisF

Æ .

5. Questions

(1) Arethere exatlytwolassesofF

Æ non-F

-ideals?

(2) HowmanylassesofF

Æ

-idealsarethere?

(3) IseveryF

Æ

-idealweaklyFarah? IseveryweaklyFarahaFarahideal?

Aknowledgments. Wewouldliketo thanktheanonymous refereeforareful

readingofthemanusriptandforrefutingoneofouronjetures.

Referenes

[1℄ BartoszynskiT.,JudahH.,SetTheory: OntheStrutureof theRealLine,A.K.Peters,

Wellesley,Massahusetts,1995.

[2℄ FarahI.,Analytiquotients: Theoryof liftingsforquotientsoveranalytiideals oninte-

gers,Mem.Amer.Math.So.148(2000),no.702.

[3℄ KehrisA.S.,ClassialDesriptiveSetTheory,Springer,NewYork,1995.

[4℄ LaammeC.,LearyC.C.,Filtergameson!andthedualideal,Fund.Math.173(2002),

[5℄ MazurK., F-ideals and !1!

1

-gaps in the Boolean algebras P(!)=I, Fund. Math. 138

(1991),no.2,103{111.

[6℄ Meza-AlantaraD.,Idealsandltersonountablesets,Ph.D.Thesis,UniversidadNaional

AutonomadeMexio,Morelia,Mihoaan,Mexio,2009.

[7℄ SolekiS., AnalytiIdeals andtheir Appliations,AnnalsofPure andApplied Logi99

(1999),51{72.

Instituto de

Matem

atias, UNAM, Apartado Postal 61-3, Xangari, 58089

Morelia,

Mihoa

an, M

exio

E-mail: mihaelmatmor.unam.mx

Faultad de Cienias F

sio-Matem

atias, Universidad Mihoaana de San

Niol

as de Hidalgo, Edifiio Alpha, Ciudad Universitaria, 58060 Morelia,

Mihoa

an, M

exio

E-mail: dmezasmat.umih.mx

(Reeived Marh26,2010,revised Marh17,2011 )