Automorphisms and strongly invariant relations

Automorphisms and strongly invariant relations

3

2

ep

S

9

]

O

L

.

th

a

m

[

1

v

5

6

1

9

3

/

tha

m

:v

i

Xr

aAutomorphismsandstronglyinvariantrelationsFerdinandB¨orner,MartinGoldstern,andSaharonShelahAbstract.WeinvestigatecharacterizationsoftheGaloisconnectionsInv–Autbetweensetsof nitaryre-lationsonabasesetAandtheirautomorphisms.Inparticular,forA=ω1,weconstructacountablesetRofrelationsthatisclosedunderallinvariantoperationsonrelationsandunderarbitraryintersections,butisnotclosedundersInvAut.Ourstructure(A,R)hasanω-categorical rstordertheory.Ahigherorderde nablewell-ordermakesitrigid,butanyreducttoa nitelanguageishomogeneous.1.IntroductionOurmainquestioniseasytoformulate.LetRbeasetof nitaryrelationsonanonemptybasesetA,andletAutRdenotethesetofallautomorphismsofthestructure(A;( ) ∈R).Conversely,ifGisasetofpermutationsonA,thensInvGdenotesthethesetofallrelationsσonAsuchthatallpermutationsinGareautomorphismsofσ.(FormalDe nitionsfollowinthenextsection.)Thequestionis:HowcanwecharacterizetherelationsetsoftheformsInvAutR?Ofcourse,theoperatorsInvAutisaclosureoperator,andtheoperatorpairsInv–AutformsaGaloisconnectionbetweensetsofrelationsonAandsetsofpermutationsonA.Wecanreformulateourproblemas“WhichsetsRofrelationsareGalois-closed,i.e.,satisfyR=sInvAutR?”or:“DescribetheclosureoperatorsInvAutinternally”,i.e.,withoutexplicitreferencetopermutations.Probablythe rstonewhoinvestigatedthisquestioninasystematicwaywasMarcKrasner.In uencedbytheGaloisconnectionbetweenpermutationgroupsand eldextensionshetriedto‘generalizethenotionofa eld’[7].Insteadoftheactionofpermutationson eldelements,heconsideredthemorecomplexactiononrelations.For nitebasesetsAhedescribedtheclosedsetsofrelationswiththehelpofsomeoperationsonrelations.Alogicaloperationonrelationsisanoperation,de nablebyaformulaofthe rstorderlogic.(Fordetailsseethenextsection.)WecallasetofrelationsaKrasneralgebraifitisclosedunderalllogicaloperations.For niteA,theGaloisclosedsetsofrelationsareexactlytheKrasneralgebras.(Atthispointweremarkthatournotationdi ersfromKrasner’soriginalnotation.)ItiseasytoextendthischaracterizationtocountablebasesetsA:InthiscasetheGaloisclosedrelation setsareexactlythoseKrasneralgebrasthatareadditionallyclosedunderarbitrary

intersections(–closedKrasneralgebras).

ButthisisnolongertrueforthegeneralcaseofuncountablesetsA.ForthiscasethereexistsacharacterizationbyR.P¨oschel[12,13]withthehelpofadditionaloperationsofuncountablearity.Buttheuseofsuchoperationsisnotverysatisfying.Thereforewecontinuetolookforbetterresults.

Onereasonfortheexistenceof –closedKrasneralgebrasthatarenotGaloisclosedisthefactthat rstorderlogicissimply“tooweak”todistinguishbetweensetsofdi erentin nitecardinalities.Consequently,itisanaturalideatoreplacethelogicaloperationsbyastrongerclassofoperations.Ann–aryoperationFonrelationsiscalledinvariant,ifthefollowingidentityholdsforallpermutationsgandallrelations 1, n(withappropriatearities)onA:

F(g[ 1],...,g[ n])=g[F( 1,..., n)]

Automorphisms and strongly invariant relations

2¨FERDINANDBORNER,MARTINGOLDSTERN,ANDSAHARONSHELAH

Clearly,everyGaloisclosedsetofrelationsis–closedandclosedunderallinvariantoperations.

Butitwasunknown whethertheconverseisalsotrue.Theproblemis:Doesthereexistasetofrelationsthatis–closedandclosedunderallinvariantoperations,butnotGaloisclosedforsInv–Aut?([3,Problem2.5.2].)

Surprisingly,theanswertothisquestionisyes!Inthemainpartofourarticle,section3,wegiveamodeltheoreticalconstructionofsuchasetofrelationsonabasesetAofcardinalityω1.

Finally,insection4,wegiveacharacterizationoftheGaloisclosedrelationsetswiththehelpofadditionalinvariantin nitaryoperations.IncontrasttoP¨oschelscharacterization,werestrictthesein nitearitiestobecountable.Section3showsthatwecannotrestrictthearitiestobe nite,sothisseemstobethebestpossibleresult.

2.Preliminaries.

Notation.Throughout,letAdenoteanonemptybaseset.Writeωforthesetofallnaturalnumbers(andatthesametimethe rstin niteordinal).Anm–aryrelationonAisasubsetof Am,thesetofallm–aryrelationsisdenotedbyRel(m)(A),andRel(A):=1 m∈ωRel(m)(A)isthesetofall nitaryrelations.IfR Rel(A),thenR(m):=R∩Rel(m)(A).Wedonotdistinguish

)havethesamemeaning.Thesetofallbetweenrelationsandpredicates,thereforea

permutationsonAisdenotedbySym(A).Forg∈Sym(A)anda

):=(g(a1),...,g(am)),

andfor Amwewrite

∈ }.g[ ]:={g(a

Letg∈Sym(A)and ∈Rel(A).Wesaythatgisanautomorphismof ,orthatgstronglypreserves ,orthat isastronglyinvariantrelationforg,if

g[ ]= .

Thisisequivalenttog[ ] andg 1[ ] .

ForR Rel(A)andG Sym(A)wede neoperatorsAut:PRel(A)→PSym(A)andsInv:PSym(A)→PRel(A):

AutR:={g∈Sym(A)|g[ ]= forall ∈R}

{ ∈Rel(A)|g[ ]= forallg∈G}sInvG:=

(ForasetX,PXdenotesthesetofallsubsetsofX.)

TheoperatorpairsInv–AutformsaGaloisconnectionbetweensetsofpermutationsandsetsofrelationsonA,i.e.thefollowingconditionsaresatis ed:

R1 R2 AutR2 AutR1andG1 G2 sInvG2 sInvG1

R sInvAutRandG AutsInvG.

Consequently,theoperators

sInvAut:PRel(A)→PRel(A)andAutsInv:PSym(A)→PSym(A)

areclosureoperators.ThesetsofrelationsandthesetsofpermutationswhichareclosedundertheseclosureoperatorsarecalledGaloisclosed(withrespecttotheGaloisconnectionsInv–Aut).CharacterizingaGaloisconnectionmeanstodescribetheGaloisclosedsetswithoutreferringtotheconnectionitself.

Inourarticlewewantto ndanddiscusscharacterizationsofourGaloisconnectionsInv–Aut.ThereexistmanysimilarGaloisconnectionsbetweensetsofrelationsandsetsofdi erentkindsoffunctions,andtheyturnedouttobeusefulespeciallyfortheinvestigationof nitemathematicalstructures.Asageneralsource,wereferto[11]andthelistofreferencesgiventhere.Hereweareinterestedincharacterizationsforin nitebasesetsA.

Themaintoolforthedescriptionoftheclosedsetsofrelationsareoperationsonrelations.Theseoperationsareoftheform

F:Rel(m1)(A)×...×Rel(mn)(A)→Rel(m)(A),

Automorphisms and strongly invariant relations

AUTOMORPHISMSANDSTRONGLYINVARIANTRELATIONS3

with0 n∈ω.AsetR Rel(A)isclosedunderFifF( 1,..., n)∈Rforall i∈R(mi),1 i n.

Specialoperationsonrelationsarethelogicaloperationswhichcanbede nedwiththehelpof rstorderformulas.Moreexactly:Let (P1,...,Pn;x1,...,xm)beaformulawithpredicatesymbolsPi(ofaritymi),whereallfreevariablesarein{xj|1 j m}.Wede ne

L ( 1,..., n):={(a1,...,am)∈Am| A( 1,..., n,a1,...,am)},

where A( 1,..., n,a1,...,am)meansthat holdsinthestructure A; 1,..., n fortheeval-uationxj:=aj,(1 j m).

ExamplesoflogicaloperationsaretheBooleanoperationsintersection∩andcomplementationC,de nedbytheformulasP1(x1,...,xm)∧P2(x1,...,xm)and¬P(x1,...,xm).

PropertiesofGaloisclosedrelationsets.

De nition2.1.AsetR Rel(A)iscalledaKrasneralgebra(KA)onA,ifRisclosedunderalllogicaloperations.1

IfQ Rel(A),then Q KAdenotestheKrasneralgebrageneratedbyQ,i.e.theleastsetofrelationsonAthatcontainsQand isclosedunderalllogicaloperations.

AsetRofrelationsiscalled–closed,if

(1)Am∈Rforallm∈ω\{0}

(2)Risclosedunderarbitraryintersections )i.e.forallmandallQ R(m)wehaveQ∈R(m.(Hereweput =Am.) IfQ Rel(A),then Q KA, denotestheleast–closedKrasneralgebracontainingQ.

Clearly, KA). ,areclosureoperatorswith Q KA Q KA,forallQ Rel(A

IfasetRofrelationsis–closedandclosedundercomplementationC(e.g.ifR= R KA,),

thenitisalsoclosedunderarbitraryunions.

ThenextLemmagivestheobviousconnectionbetweenthesenotionsandtheGaloisclosedrelationsets.Foraproofwerefere.g.to[3]. Lemma2.2.IfR Rel(A)isGaloisclosed(R=sInvAutR),thenRisa–closedKrasneralgebra,R= R KA, .Consequently,forallQ Rel(A)wehave Q KA, sInvAutQ.

(GaloisclosedsetsofrelationsaresometimescalledKrasnerclones.SoeveryKrasnercloneisaKrasneralgebra,butnotviceversa.)

De nition2.3.LetR Rel(A)anda

):= { ∈R(m)|a

∈Am.Thenthefollowinghold.

(1)R1 R2 ΓR2(a)

)andΓR(a(2)a

∈R. (3)IfRis–closed,thenΓR(a

～Rb

～Rb

)=ΓR2(a∈Am.∈ΓR(bfromb∈ .Moreover, = a)forall)|a

Automorphisms and strongly invariant relations

4FERDINANDBORNER,¨MARTINGOLDSTERN,ANDSAHARONSHELAH

(6)ΓsInvG(a)|g∈ G group},where G groupisthesubgroupofSym(A),generated

byG.

Proof.(1)–(5)aredirectconsequencesoftheDe nitions.For(6),we rstnotethat{g(a

andisstronglyinvariant forallg∈G.ThereforeΓsInvG(a)|

g∈ G group}.Ontheotherhand,sInvGis–closed,thereforea)∈sInvG,andeveryrelationwiththesepropertiesmustcontainallg(a

) {g(a

,b～Rb

=g(a

)=ΓsInvAutR(a.Becauseof2.4(6),thisis

equivalenttoΓR(a)|g∈AutR}. Partialautomorphisms.ThelastLemmacanbeusedto ndcharacterizationsinsomespecialcases.

De nition2.6.ApartialautomorphismfofarelationsetQ Rel(A)(orofthestructureA

=(A;(σ)σ∈Q))issaidtobehomogeneous,ifevery nite

partialautomorphismcanbeextendedtoanautomorphismofQ.

Lemma2.7.IfQ Rel(A)isahomogeneoussetofrelations,then Q KA, =sInvAutQ.Proof.FirstnotethatsInvAutQishomogeneousand Q KA, sInvAutQ,soalso Q KA, ishomogeneous.SowlogQ= Q KA,

b1 .Leta=(,...,bm).Wewilluse2.5.So,assuminga,wehaveto

ndanautomorphismgwithg(a.Notethatainparticularimpliesthatai=aji bi=bj,foranyi,j.Sothemapf:={(ai,bi)|i=1,...,m}isa nite1-1map.AsnorelationinQseparatesa,fisevenapartialautomorphismforQ.

BecauseofthehomogeneityofQ,fcanbeextendedtoanautomorphismg∈AutQ.Thereforeb)forsomeg∈AutQ.

RelationsetsoftheformsInvAutQarehomogeneous.Hence,a –closedKrasneralgebraisGaloisclosedifandonlyifitishomogeneous.

TheGaloisclosedpermutationsets.WewanttohaveashortlookattheothersideofourGaloisconnection.ThecharacterizationoftheGaloisclosedpermutationsetsiswellknown([5])andprovidesnodi culties.WeneedanadditionalclosureoperatorLoco:PSym(A)→PSym(A):

LocoG:={f∈Sym(A)|( m∈ω\{0})( a)=g(a

Automorphisms and strongly invariant relations

AUTOMORPHISMSANDSTRONGLYINVARIANTRELATIONS5

A rstcharacterizationoftheGaloisclosedrelationsets.In[12]and[13],R.P¨oschelcharacterizedtheclosedsetsofrelationswiththehelpofin nitaryoperations.LetIbeanarbitraryindexset,letm,mi∈ω\{0}(i∈I).ForanI-tuple( i)i∈Iofrelationswith i∈

miisde nedasfollows:Rel(mi)(A)thestrongsuperpositionwithparametersai∈A

sSupai)i∈I( i)i∈I:={g(ai)∈ iforalli∈I}

AsetR Rel(A)isclosedunderstrongsuperposition,ifsSupai)i∈I( i)i∈I∈Rwhenever i∈Rfori∈I. Theorem2.9.LetR Rel(A)be–closedandclosedunderC.ThenR=sInvAutRifandonlyifRisclosedunderstrongsuperposition.

Proof.Iff∈Sym(A),thenthede nitionofsSupa

sSupai)i∈I(f[ i])i∈I =fsSupai)i∈Iimpliesi)i∈I( i)i∈I.

Thereforeeveryautomorphismof{ i|i∈I}isanautomorphismofsSupai)i∈I( i)i∈I.Conse-quently,everyGaloisclosedsetofrelationsisclosedunderstrongsuperposition.

IfRisclosedunderstrongsuperposition,thenwecanchooseIand(b

i.(Thisispossiblewith|I|=|A|.)ThenR

) sSupai)i∈I(ΓR(bcontainstherelationsSupai)i∈I(ΓR(b

∈ΓR(a=g(an)∈ΓR(c∈A.ThisgisanautomorphismofR,therefore2.5implies

thatRisGaloisclosed.

Asseenintheproof,wecanrestrictthearitiesofthestrongsuperpositionsto|I|=|A|.Nevertheless,tobeclosedunderstrongsuperpositionisaverystrongcondition.Itimmediatelyimpliestheexistenceofthenecessaryautomorphismsinthesenseof2.5.Therefore,wecontinueto ndbettercharacterizations.

ACharacterizationforcountablebasesetA.For nitebasesetA,theGaloisclosedrelationsetsareexactlytheKrasneralgebras([7,8,9,11]).Thisresultcanbeextendedtothecountablecase:

Theorem2.10.R Rel(A).ThenR=sInvAutRifand LetAbeacountableor nitesetand

onlyifRisa–closedKrasneralgebra,R= R KA, .Therefore Q KA, =sInvAutQforallQ Rel(A).

Proof.Fortheproofwereferto[2,3.3.6.(v)]orto[3,2.4.4.(i)].OnedirectionisprovidedbyLemma2.2.Fortheotherdirectionwecanuseaback&forthconstructiontoobtaintheauto-morphismsthatarenecessarytoapplyLemma2.5.

Thenextexampleshowsthatthischaracterizationcannotbeextendedtouncountablesets.Example2.11.Considerthefollowingthreecountablestructures:

(1)(Q;<)(therationalnumberswiththelinearorder).

(2)Thefullcountablebipartitegraph:(A∪B; ),whereAandBaredisjointcountablesets,

and =(A×B)∪(B×A).

(3)Thecountablerandomgraph.(Seee.g.[4,6.4.4].)

EachofthesestructuresM

),the rstordertheoryofM

))tox=xortox=x,i.e.,

theonlysubsetsofM

κofcardinalityκsuchthattheset

:={x:Theset{y: (x,y)}iscountable}

isneitheremptynorthefullmodel.

Automorphisms and strongly invariant relations

6¨FERDINANDBORNER,MARTINGOLDSTERN,ANDSAHARONSHELAH

IneachofthesemodelsM

theset isa(higherorder)de nablesubsetofMκ,hence ∈

sInvAut(R)\R.

ThisshowsthatRisnotGaloisclosed.

Invariantoperations.Inthelastexample,thelogicaloperations,togetherwitharbitraryinter-sections,aretooweaktoprovidetheclosureundersInvAut.Inparticular,withlogicaloperationsitisnotpossibletodistinguishbetweensetsofdi erentin nitecardinality.Sothenextideatoobtainacharacterizationistoreplacethelogicaloperationsbyafamilyofstrongeroperationsonrelations.

De nition2.12.AnoperationF:Rel(m1)(A)×...×Rel(mn)(A)→Rel(m)(A)iscalledinvariant,ifforallg∈Sym(A)andall i∈Relmi(A)thefollowingidentityholds:

F(g[ 1],...,g[ n])=g[F( 1,..., n)]

IfQ Rel(A),then Q invdenotestheclosureofQunderallinvariantoperations,and Q inv, denotestheleastsetofrelationsthatisclosedunderallinvariantoperations,–closedandcontainsthesetQ.

(Thenotations“logicaloperations”and“invariantoperations”areadoptedfrom[6].)TheoperatorsQ→ Q invandQ→ Q inv, areclosureoperators,andwehave Q inv Q inv, forallQ Rel(A).

Wecollectsomeeasypropertiesoftheinvariantoperations.

Lemma2.13.(1)Everylogicaloperationisinvariant.IfAis nite,theneveryinvariant

operationislogical.

(2)Theinvariantoperationsformaclone,i.e.thesuperpositionofinvariantoperationsis

againaninvariantoperation.

(3)IfFisinvariantand i∈Rel(A)(1 i n),then

Aut{ 1,..., n} Aut{F( 1,..., n)}.

(4)R R inv R inv, sInvAutRforallR.So,ifR=sInvAutR,thenRis

andclosedunderallinvariantoperations,R= R inv, . –closedκ

Proof.For(1)and(2)wereferto[6].(3)isadirectconsequenceof2.12and(4)isadirectconsequenceof(3).

ThenextLemmashowsthatinvariantoperationsaresu cient,ifwehaveonly nitelymanyrelations.

Lemma2.14.LetQ Rel(A)bea niteset.ThensInvAutQ= Q inv.

Proof.LetQ={ 1,..., n}andletσ∈sInvAutR.Wede neaninvariantoperationFwithF( 1,..., n)=σ: F(σ1,...,σn):={g[σ]|g∈Sym(A)and( i=1...n)g[ i]=σi}

ItiseasytoverifythatFhasthedesiredproperties.

LetH:PZ→PZbeaclosureoperatoronasetZ.ThealgebraicpartofHistheclosureoperator Halg:PZ→PZ,X→{HX0|X0 X,X0 nite}.

HisalgebraicifH=Halg.

Lemma2.14showsthattheclosureoperatorQ→ Q invisthealgebraicpartofsInvAut.Moreexactly,forallQ Rel(A)wehave Q inv={sInvAutQ0|Q0 QandQ0is nite}=(sInvAut)algQ

Automorphisms and strongly invariant relations

AUTOMORPHISMSANDSTRONGLYINVARIANTRELATIONS7

Sofar,wehavetheclosureoperators inv, inv, andsInvAut.Theoperators invarealgebraic,theotheroperatorsarenotalgebraicifAisin nite.ForallQ Rel(A)wehave

Q KA Q inv

Q KA, Q inv, sInvAutQ.

For nitebasesetAalltheseclosureoperatorscoincide.

For

countable

A,theoperators

invand KA, =

KA, =

=(M;( m)1 m∈ω),where m∈

Rel(A)forallm.SoourlanguageLhasexactlyonerelationsymbolforeveryaritym.(Weusethepredicatesymbolsalsotodenotethecorrespondingrelations.)

[m]IfM:=(M; 1,..., m)denotesthereductof

M(m)

=(A;( m)1 m∈ω)beanin nitemodel.LetA

)isω-categorical(i.e.,hasuptoisomorphismexactlyonecountable

model).

(2)Forallm,thereductA

isrigid,i.e.AutA

,wehave:

1,..., m KA=sInvAut{ 1,..., m}

m 1,..., m KA,but

R= R inv, sInvAutRandR=

Proof.FirstnotethatR(aswellas 1, 2,... m KA)isclosedunderarbitraryintersections,since(byRyll-Nardzewski’stheorem)thereareonly nitelymanyk-aryrelationsinR,foranyk.

WenowshowthatRisalsoclosedunderallinvariantoperations.Wehave

Trivially, 1, 2,..., m KA= 1, 2,..., m KA,

1, 2,..., m KA 1, 2,..., m inv sInvAut{ 1, 2,..., m},

butby(2)and2.7wehave

so 1, 2,..., m KA, =sInvAut{ 1, 2,..., m},

1, 2,..., m KA= 1, 2,..., m inv.

Automorphisms and strongly invariant relations

8¨FERDINANDBORNER,MARTINGOLDSTERN,ANDSAHARONSHELAH

Asbothoperators invarealgebraic,thisyields

R= 1, 2,... KA= 1, 2,... inv

henceR= R inv, .

ClearlyRiscountable.ButAutR={idA}andsosInvAutR=Rel(A),whichisanuncountableset.Consequently

R inv, =sInvAutR.

Itremainstoprovethatamodelwithproperties(1)–(3)exists.Becauseof2.10,suchamodelcannotbecountable.Westartbyde ningthelogicaltheoryTthatwewantourmodeltosatisfy.Firstwede neanappropriatenotionofaclause.

De nition3.2.Aliteralinthevariablesx0,...,xn(n∈ω)isaformulaoftheform

m(xi1,...,xim)(unnegated)or¬ m(xi1,...,xim)(negated)

suchthat1 m n+1,{i1,...,im} {0,...,n},thei1,...,imarepairwisedistinctand0∈{i1,...,im}.

Aclauseinx0,...,xnisaconjunctionKofliteralsinx0,...,xn,suchthatnoliteralwillappeartwice,andnoliteralappearsinnegatedandunnegatedform.

Pleasenotethatthereareonly nitelymanyclausesinx0,...,xn.Thevariablex0playsaspecialrole—ithastoappearineveryliteral.

NowweformulateourtheoryT:

De nition3.3.Tconsistsof(theuniversalclosuresof)thefollowingformulas:Firstly,forall1 m∈ωwehave: (T1) m(x1,...,xm)→1 i<j mxi=xj

Secondly,foralln∈ωandallclausesK=K(x0,...,xn)inx0,...,xnwetaketheformula: (T2)1 i<j nxi=xj→( x0)K(x0,...,xn)

InformalDiscussion3.4.WewillseebelowthatthetheoryTiscompleteandω-categorical.OuraimistoconstructanuncountablemodelM

,weallowourmodeltodisobeythisrecommendation,ifthereisagood

reasonforit.Agoodreasoncanbethedesiretosatisfyanaxiomofourtheory,ortoextendapartialautomorphism.

Tokeeptrackofthecaseswheretherecommendationisnotfollowed,weconstructanauxiliaryfunctionh:M→ω,andwewilldemandthefollowing“law”,whichisarelaxedversionofthe“recommendation”:

Forallsu cientlylongtuples(x1,...,xn):

(x1,x2,...,xn)mustholdifx1<x2<···<xn,andmustnotholdotherwise

Here,“su cientlylong”isde nedas:n>max(h(x1),...,h(xn)).

Thus,wheneverweviolateourrecommendationatatuple(x1,...,xn),wewillde neasu -cientlylargevalueofhatoneofthepointsx1,...,xn.

BeforeweinvestigatethetheoryT,wewanttoexaminesometechnicalde nitionsandlemmas.ω1denotesthe rstuncountableordinal,ω1={α|α<ω1}.ω1iswell-orderedby<.Theuniversesofallourmodelswillbesubsetsofω1.[m]

Automorphisms and strongly invariant relations

AUTOMORPHISMSANDSTRONGLYINVARIANTRELATIONS9

De nition3.5.LetM

=(a1,...,an)∈Mn.Wesaythata

):=max{h(ai)|ai∈domh}<n.

Allothern-tuplesarecalledstrongforh.

=(M;( m)1 m∈ω)bemodelswithN M ω1.LetNowletN

h:M →ωbeapartialfunctionwithdomh=M\N.WewriteNif

(1)N(N),and

(2)foralln-tuples(a1,a2,...,an)∈Mnthatareweakforhthefollowingconditionholds:

n(a1,...,an) a1<a2<...<an

(Here<isthewell-orderingonω1.)

ifNforsomepartialfunctionhwithdomh=M\N.WewriteN

Lemma3.6.

(2)IfM0(1)Therelation<istransitive.<···isachainoflengthω,andMω

<MωnisalsoasubmodelofMω

)i≤α(whereαisalimitordinal)isacontinuouschainofmodels(i.e., Mi≤Mjforalli≤j≤α,andforeachlimitδ≤αwehaveMδ=i<δMi),and

i<α:Mi,

forallj<α.thenMj

Proof.

andM2forsomeh1:M2\M1→ωandh2:M3\M2→ω,(1)AssumingM1

wehavetoshowM1.nnPuth:=h1∪h2:M3\M1→ω.Ifa∈(M2\M1)

oroneoftheaibelongstoM3\M2.Inthe rstcase,maxh2(a)<n,anda

isasubmodelofM3

) 2n(a

) maxh(aisweakforh3and 3n(a

0=(M0;( m)1 m∈ω)beacountablemodelofourlanguageL,suchthat →M0M0 ω1and m(x1,...,xm)→1 i<j mxi=xjholdsforallm.Moreover,letπ0:M0

beapartial( niteorin nite)automorphismofthereductM0

=(Mω;( ωm)1 m∈ω)withM0 Mω ω1,α∈Mω

andatotalautomorphismπω:Mω →Mωofthes–reductMω

<Mω

isamodelofthetheoryT.

(3)πωextendsπ0

Proof.WeconstructMω

Mjwithj∈ω.Wewillhaveforallj∈ω,andforeveryjwewillhaveapartialautomorphismπjofMj

,K)|n∈ω,a

Automorphisms and strongly invariant relations

10¨FERDINANDBORNER,MARTINGOLDSTERN,ANDSAHARONSHELAH

a

beanenumerationofthisset.

LetB ω1\Mjbeacountablesetofordinals,andletB={bk|k∈ω}beanenumerationofB.(Again,thisenumerationneednotnecessarilyfollowthewell-order<onω1.)Weput+1Mj+1:=Mj∪B,andwehavetode netherelations jmandthepartialfunctionπj+1.Moreover,wemustde neafunctionh:B→ω,inordertoestablishtherelationMj.

Forallmandallm-tuplesa

): jm(a

Mj+1l,Kl)l∈ω

)

forsometuplesa

betheelementofKwithindexl.Wede neh(bk):=nl+1.Now,forevery

literalwhichoccursinK,wede nethetruthvaluesinsuchaway,thatKl(bk,a

l=(al(1),...,al(nl)),wede netruthvaluesforcertaintuplesfromtheset

{al(1),...,al(nl),bk}<ω\{al(1),...,al(nl)})<ω.

ThelargestindexmofaliteralwhichoccursinKlisnl+1.Thereforeallthesetuplesc

)≥h(bk)≥mandarestrongforh.[Notethatinnopreviousstephavewecommitted

inwhichbkappears.]ourselvestothetruthvalueof j(c

Stepkfork=3l+1:Inthiscasewede neh(bk):=s,andweextendthepartialfunctionpk 1.Ifdompk 1 Mj,thenwesimplyputpk:=pk 1andwearedone.l,Kl)

Automorphisms and strongly invariant relations

AUTOMORPHISMSANDSTRONGLYINVARIANTRELATIONS11

k=3l+1,

de nitionof

(c))aipkbk

...

)

domk 1...cimpk 1

IfMj\dompk 1= ,thenleti:=min{i|ai∈/dompk 1}.Weextendpk 1byde ningpk(ai):=bk.Then,forallm sandallc1,...,cm∈impksuchthatc1,...,cmarepairwisedistinctand+1bk∈{c1,...,cm},wede nethetruthvalueof jm(c1,...,cm).Writec1))isalreadyknown,inparticularifp k(c

1): j+1(p k(c

1))isstillnot xed(inparticular,thenthep k(ci)cannotallbeinMj),thenwe

de nebothvalues,namelyweput

1 1+1)): p jm(ck(c1)<...<pk(cm).

(Here<denotesthewell-orderinω1.)

Becauseofthede nitionofh(bk),the(c1,...,cm)arealwaysstrongforhandhenceare1exemptedfromour“recommendation”3.4.Theothertuples,p k(c

stepk<k.]

Stepkfork=3l+2:Thisstepissimilartothepreviousstep,butthistimewetakecareof1impkratherthandompk,orinotherwords:wereversetherolesofpkandp k.Weleavethedetailstothereader.

+1Byinductionweobtainfromthesestepsamodel,wheretherelations jareonlypartiallymde ned.Inorderto nishthede nition,weput

+1 jm(c′inwhichbkappearshaveneverbeenconsideredinanyprevious

partialautomorphismofMj+1)hasnotbeende nedduringtheinductiveconstruction. .Moreover,πj+1:=k∈ωpkisaFromtheconstruction,itisnowclearthatMj

:= j∈ωMj

[s]<Mω,whichiseverywherede ned

andsurjective,i.e.itisanautomorphismofMω

andallotherextensionsofMj

.ConsequentlyMω

Automorphisms and strongly invariant relations

12¨FERDINANDBORNER,MARTINGOLDSTERN,ANDSAHARONSHELAH

Lemma3.8.(1)Tisconsistentandhasno nitemodels.

(2)Thasthepropertyofeliminationofquanti ers.

(3)Tiscomplete.

(4)Tisω–categorical.

aremodelsofTandN,N,thenN(5)IfM

,i.e.foreveryformula (x1,...,xn)andeverya

.

Proof.)inN(1)Easy.TheconsistencyofTisacorollaryof3.7,andthenonexistenceof nite

modelsisensuredbytheformulas3.3(T2).

(2)Inordertoprovethatforeveryformulaψ(x1,...,xn)thereisaquanti erfreeformula

(x1,...,xn)withT|=( ψ),itissu cienttoprovethisforformulasψoftheform

( x0)K(x0,x1,...,xn),whereKisaclauseinx0,...,xn.

Foranyequivalencerelationθon{1,...,n}weput: xi=xj).xi=xj)∧(µθ:=(

(i,j)∈θ(i,j)∈/θ

LetEndenotethesetofallequivalencerelationson{1,...,n}.Then (K∧µθ).K

θ∈En

Thereforealso

( x0)K(x0,x1,...,xn)

θ∈En ( x0)(K∧µθ).

Itissu cienttoshowthateveryformula( x0)(K∧µθ)isequivalenttoaquanti erfree

formula.Ifθisnottheequalityrelation,thenwecanreplaceanyvariablexj(j≥1)

byxi,whereiisarepresentativeoftheequivalenceclassofj.IfthenavariableappearstwiceinanliteralofK,theneithertheclausebecomesfalsemoduloT(iftheliteralis

unnegated),ortheliteralcanbeomittedmoduloT(ifitisnegated).Intheendweobtain

eitherformulaswhicharetrue(moduloT)orfalse(moduloT)orequivalenttoaformulaoftheform ( x0)(K∧xi=xj).

Tcontainstheformula1 i<j nxi=xj→( x0)K,therefore

T|=(xi=xj ( x0)(K∧xi=xj).

1 i<j n1 i<j n 1 i<j n

(3)By(2),everyclosedformulais(modT)equivalenttotrueorfalse.

(4)ModuloT,thereareonly nitelymanyquanti er-freeformulasinthevariablesx1,...,xn,

namely,Booleancombinationsofatomicformulas m(xi1,...,xim),fori1,...,im∈{1,...,n}andm≤n.(Notethatformulas m(xi1,...,xim)form>nandi1,...,im≤nareauto-maticallyfalsemodT,becauseof3.3(T1).

Thisimpliesω-categoricity,byRyll-Nardzewski’stheorem.[Actually,wedonotneedω-categoricityitselfforourconstruction,weonlyneedthefactthatthereareonly nitely

many rstorderde nablek-aryrelations,foranyk.]

(5)ThisisaconsequencefromthefactthatThaseliminationofquanti ers.

Theresultsin3.8makesurethatthecondition3.1(1)issatis edforeverymodelofT.NowweconstructamodelA

asadirectedunionoveranuncountablechainofmodels,A,such

thateveryMi<Mi+1

isagainamodelofT.Becauseofi∈Mi+1foralli∈ω1 andMi ω1,thecarriersetA=i∈ω1MiisA=ω1.

Automorphisms and strongly invariant relations

AUTOMORPHISMSANDSTRONGLYINVARIANTRELATIONS13

Inordertoobtainamodelwithhomogeneouss–reducts,wehavetomakesurethatcertainpartialautomorphismscanbeextendedtoautomorphisms.Forthisreason,weuseatriply-indexedfamily(πn,i,j)n∈ω,i,j∈ω1,i jofpartialautomorphisms.

Firstweexplain,whattheπn,i,iare.IfM

[s].

Thereforethereexistsanenumeration(pn,sn)n∈ωofallthese nitepartialautomorphismswithcorrespondings.Now,fori∈ωandMweputπn,i,i:=pn,andsn,i:=sn.Therefore

( )(πn,i,i)n∈ωisalistofall nitepartialautomorphismsofallpossiblereductsMi

andsequencesofpartialautomorphisms(πn,i,j:

i≤j)bytrans niteinductiononj∈ω1).Thisconstructionwill usetheusual‘bookkeeping–argument’totakecareofω1×ωmanytasksinω1steps.Letω1=n∈ω,i∈ω1Cn,ibeapartitionofω1intopairwisedisjointsetsCn,i,suchthat|Cn,i|=ω1forall(n,i)andminCn,i≥i.

Ifj=0,thenletM0

:= i<jMi

asfollows.Let(n,i)bethepairwithj∈Cn,i.Accordingtothe

<Mj+1Lemma,thereexistsamodelMj+1j+1

[sn,i]withMj domπ¯and

Mj imπ¯.

(2)Weletπn,i,j+1bethepartialautomorphismπ¯from(1).

(3)Theπn,j+1,j+1arede nedasin( ),enumeratingall nitepartialautomorphismsof

reductsofMj+1

,andthatπn,i,jextendsπn,i,kforallkwithi k<j.

Asmentionedabove,weputA.

Lemma3.9.Ifs∈ω,thenevery nitepartialautomorphismπofA

[s].

Proof.πis nite,thereforethereexistsi∈ωwithdomπ∪imπ Mi.Mi

thereforeπisa nitepartialautomorphismofMi

construction,wehaveMj domπforallj∈Cn,i,i.e.domπ

holdsforimπ′,thereforeπ′isatotalautomorphismofA

hastheproperty3.1(3).

Lemma3.10.A={idA}.′[sn,i],[s] .Byourj∈Cn,iMj=ω1.Thesame

Proof.LetSbeacountablesubsetofA,x,y∈Sandh:A\S→ωbeafunction.Thenwede nethatE(x,y,S,h)istruei forallmandforalla

)∧maxh(a

<A

<hA∈A\S,isweakforh,then m(amm

Automorphisms and strongly invariant relations

14¨FERDINANDBORNER,MARTINGOLDSTERN,ANDSAHARONSHELAH

Proofof“ ”:LetSbeacountablesubsetofAandleth:A\S→ωbeafunctionsuchthatE(x,y,S,h).

Sinceω1hasuncountableco nality,andSiscountable,theremustbesomei<ω1withS Mi.SoletibetheleastordinalwithS Mi.Letp∈A\Mi.(Thenalsop∈A\S.)Wehave

forsomehi:A\Mi→ω.Letm:=max{h(p),hi(p)}+3andchoosez1,...,zm 3∈S,Mi

pairwisedistinctanddistinctfromxandy.Leta

)<m,soa

Butwealsohavemaxh(a<M)impliesi<j.Sox<y.).

¯(x,y): ( S)( h)E(x,y,S,h).IfπisanautomorphismofALetE

orderautomorphismof<isidA.hastopreservethewell-ordering<ofω1.Buttheonly

In3.8,3.9and

3.10wehave

veri edallpropertiesofA

=(A;( m)m∈ω)hastheproperties3.1(1)–(3).Consequently,

thesetR={ m|m∈ω}satis es

R KA= R inv, =sInvAutR.

Remark3.12.ThestructureA

inv, istooweaktoprovidethe

closureundersInvAut.Sothequestionremains,whatweshouldaddtoobtainanappropriatecharacterization.Similarasin2.9wewilladdoperationswithin nitearity.Butincontrastto

2.9,weneedonlyoperationswithcountablearities.

Lemma4.1.Letm∈ω\{0}andletQ Rel(m)(A)beclosedundercomplementation.Then

(2m)thereexistsarelation ∈ Q KA, withAutQ=Aut{ }.

Proof.QisclosedunderC,thereforetheset

M:={ΓQ(a∈Am}

isapartitionofAm.Mcanbewell-ordered,solet(γi)i<κbeacorrespondingenumerationoftheelementsofM.Weput :=γi×γj

i j<κ

Then ∈ Q KA, .Thisimplies ∈sInvAutQandthereforeAut{ } AutQ.

))∈ andNowletg∈Aut{ }.Ifa∈γi,then(a)∈ and(b)∈ ,hence(g(a

(g(b))∈ .Theγiarepairwisedisjoint,thereforethereareuniqueordinalsl,k<κwithg(a)∈γk.Now(a)∈ impliesl kand(g(a))∈ impliesk l,i.e.l=k.(2m)

Automorphisms and strongly invariant relations

AUTOMORPHISMSANDSTRONGLYINVARIANTRELATIONS15

Consequentlyalltuplesinγiaretransformedbygtotuplesinγk.Thereforethereexistsafunctiong0:κ→κwithg[γi] γg0(i).

′g 1isalsoanautomorphismof ,anditiseasytoseethatthecorrespondingfunctiong0:κ→κ

hastobetheinverseofg0.Consequently,g0isapermutationonκ.

Thepermutationg0preservesthewell-order<onκ,becauseof

i<j γi×γj γg0(i)×γg0(j) g0(i)<g0(j).

But κ,< hasonlythetrivialorderautomorphism,thereforeg0=idκ.

Weobtaing[γi] γiand(becauseg 1isalsoanautomorphism)g 1[γi] γi,i.e.g[γi]=γi.Butthen,gisanautomorphismforallrelationsinM,andthereforealsoforallrelationsinQ.ThisyieldsAut{ } AutQ,andthis nishestheproof.

AsaconsequenceofthisLemma,everypossibleautomorphismgroupappearsalreadyastheautomorphismgroupofanatmostcountablesetofrelations.

Lemma4.2.ForeverysetR Rel(A)thereexistsanatmostcountablesetR0 Rel(A)with AutR=AutR0.Moreover,ifRisa–closedKrasneralgebra,thenwecanchooseR0 R.

Proof.IfRisnotclosedunderC,thenweputR′:=R∪{Cσ|σ∈R}.ThenAutR=AutR′,thereforewecanassumew.l.o.g.thatRisclosedundercomplementation.By4.1therearerelations m∈Rel(2m)(A)withAutR(m)=Aut{ m}.Consequently: (m)AutR=AutR=Aut{ m}=Aut{ m|1 m∈ω}

1 m∈ω1 m∈ω

Thesecondpartin4.1impliesthatthe mcanbechosenfromthe

generatedbyR.

Nowwede neouradditionaloperations. –closedKrasneralgebra,

De nition4.3.Aninvariantoperationwithcountablearityisanoperationoftheform F:Rel(mi)(A)→Rel(m)(A)

1 i∈ω

(mi∈ω\{0}),suchthatforall( i)1 i∈ω∈ 1 i∈ωRel(mi)(A)andallg∈Sym(A)wehave

F(g[ i])1 i∈ω=g[F( i)1 i∈ω]

IfQ Rel(A),then Q ω invistheclosureofQunderallinvariantoperationswithcountablearity,and Q ω inv, isthe leastsetofrelationswhichisclosedunderallinvariantoperationswithcountablearityand–closed.

(Ofcourse, ω inv, areclosureoperators.)Similarasin2.13and2.14,wecanverifythefollowingproperties:

Lemma4.4.(1)IfR Rel(A)isGaloisclosed,R=sInvAutR,thenRis–closedand

closedunderallinvariantoperationswithcountablearity,R= R ω inv, .

(2)IfQ Rel(A)iscountableor nite,then Q ω inv=sInvAutQ.

NowwecanformulateourcharacterizationoftheGaloisclosedsetsofrelations.

Theorem4.5.LetRbea–closedKrasneralgebra.ThenRisGaloisclosed,R=sInvAutR,

ifandonlyifsInvAutR0 RforeverycountablesubsetR0ofR. Inparticular,asetR Rel(A)isGaloisclosedifandonlyifitis–closedandclosedunderallinvariantoperationswithcountablearity,R= R ω inv, .ForallQ Rel(A)holds Q ω inv, =sInvAutQ.

Automorphisms and strongly invariant relations

16¨FERDINANDBORNER,MARTINGOLDSTERN,ANDSAHARONSHELAH

Proof.Clearly,R0 RandR=sInvAutRimpliessInvAutR0 sInvAutR=RforeverysubsetR0ofR.Viceversa,ifsInvAutR0 Rforallcountablesubsets,then

wecanchoosethespecialsubsetR0 RwithAutR=AutR0ofLemma4.2.Thenweobtain:

R sInvAutR=sInvAutR0 R,

i.e.,RisGaloisclosed.

ThentheotherstatementsareconsequencesofLemma4.4.

References

[1]H.Andr´eka,D.Monk,I.N´emeti(Eds.).AlgebraicLogic.Pap.Colloq.,Budapest1988.(Colloq.Math.

Soc.J.Bolyai54),North–Holland,1991.

[2]F.B¨orner.OperationenaufRelationen.Dissertation,Universit¨atLeipzig,1989.

[3]F.B¨orner.Krasneralgebren.Habilitationsschrift,Universit¨atPotsdam1999.Logos–Verlag2000.

[4]W.Hodges.Ashortermodeltheory.CambridgeUniversityPress,1997.

[5]B.J´onsson.Algebraicstructureswithprescribedautomorphismgroups.Coll.Math.19(1968),1–4.

e

[6]B.J´onsson.Thetheoryofbinaryrelations.in:[1],245–292.

[7]M.Krasner.Unegeneralizationdelanotiondcorps.J.Math.PuresAppl.,17(1936),367–385.

[8]M.Krasner.Generalisationabstraitedelath´eoriedeGalois.in:

(1984),153–166.

本文来源：https://www.bwwdw.com/article/n73m.html