BenjaminFine,AnthonyGaglione,AlexeiMyasnikov, GerhardRosenberger,DennisSpellman TheElementaryTheoryofGroups De Gruyter Expositions in Mathematics | Editedby VictorP.Maslov,Moscow,Russia WalterD.Neumann,NewYorkCity,NewYork,USA MarkusJ.Pflaum,Boulder,Colorado,USA DierkSchleicher,Bremen,Germany RaymondO.Wells,Bremen,Germany Volume 60 Benjamin Fine, Anthony Gaglione, Alexei Myasnikov, Gerhard Rosenberger, Dennis Spellman The Elementary Theory of Groups | A Guide through the Proofs of the Tarski Conjectures MathematicsSubjectClassification2010 20F05,20F06,20F10,20F65,20F67,20F69,20E05,20E06,20E08,20E10,20A15,03C95,03C98, 03C68 Authors Prof.Dr.BenjaminFine Prof.Dr.AnthonyGaglione FairfieldUniversity UnitedStatesNavalAcademy DepartmentofMathematics DepartmentofMathematics 1073NorthBensonRoad 9EMailStop Fairfield,CT06430 Annapolis,MD21401 USA USA [email protected] [email protected] AlexeiMyasnikov Prof.Dr.GerhardRosenberger McGillUniversity Heinrich-Barth-Str.1 Dept.ofMathematicsandStatistics 20146Hamburg 805SherbrookeSt.West Germany Montréal,QCH3A2K6 [email protected] Canada [email protected] Prof.Dr.DennisSpellman TempleUniversity Dept.ofMathematics BroadandMontgomery Philadelphia,PA19122 USA ISBN978-3-11-034199-7 e-ISBN(PDF)978-3-11-034203-1 Set-ISBN978-3-11-034204-8 ISSN0938-6572 LibraryofCongressCataloging-in-PublicationData ACIPcatalogrecordforthisbookhasbeenappliedforattheLibraryofCongress. BibliographicinformationpublishedbytheDeutscheNationalbibliothek TheDeutscheNationalbibliothekliststhispublicationintheDeutscheNationalbibliografie; detailedbibliographicdataareavailableontheInternetathttp://dnb.dnb.de. ©2014WalterdeGruyterGmbH,Berlin/Boston Typesetting:le-texpublishingservicesGmbH,Leipzig Printingandbinding:CPIbooksGmbH,Leck ♾Printedonacid-freepaper PrintedinGermany www.degruyter.com Preface In1940,AlfredTarski,thenotedlogician,askedthreemajorquestionsabouttheele- mentaryorfirst-ordertheoryoftheclassofnon-Abelianfreegroups.Theseweresub- sequentlyformalizedintoconjectures.ThefirstoftheseTarskiconjecturesaboutnon Abelian free groups isthat allnon-Abelian free groups haveexactly the samefirst- ordertheory.Thesecondisthatthenaturalembeddingofonefreegroupintoanother isanelementaryembedding.Thissecondconjectureimpliesthefirst.FinallyTarski askediftheelementarytheoryofthenon-Abelianfreegroupsisdecidable,thatisdoes thereexistanalgorithmtodetermineifafirstordersentenceistrueornotwithinthe classofnon-Abelianfreegroups.Theconjecturesremainedopenforoverfiftyyears. In a series of papers from 1998–2006 the first two Tarski conjectures were an- sweredintheaffirmativebyOlgaKharlampovichandAlexeiMyasnikov[152,153,154, 155,156]andindependentlybyZilSela[233,234,235,236,237].Kharlampovichand Myasnikov also proved Tarski conjecture 3. The proofs of both Kharlampovichand MyasnikovandofSelainvolvelongandcomplicatedapplicationsofalgebraicgeom- etryoverfreegroups(SelacallsthisDiophantinegeometry)aswellasanextension ofmethodstosolveequationsoverfreegroupsoriginallydevelopedbyMakaninand Razborov.Thematerialnecessarytounderstandtheseproofsisquitedauntingeven foraccomplishedgrouptheoristsandlogicians.Thisbookisanexaminationofthe materialongrouptheoryandlogicandonthegeneralelementarytheoryofgroups thatisnecessarytobegintounderstandtheproofs.Thismaterialincludesacomplete expositionofthetheoryoffullyresiduallyfreegroupsorlimitgroupsaswellacom- plete descriptionof the algebraic geometry of free groups. Also included areintro- ductorymaterialoncombinatorialandgeometricgrouptheoryandfirst-orderlogic. ThereisthenashortoutlineoftheproofoftheTarskiconjectures.Wefoundthatin manycases,grouptheoristsdon’tknowenoughlogictounderstandtheproofwhile thesameistrueforlogicians,thatisthelogiciansforthemostpartdon’tunderstand enoughofthegrouptheory.Partofourgoalinthisbookistocorrectthis. Wefirstintroducesomebasicideasandgivesomehistory. Theelementarytheoryofgroupsistiedtofirst-orderlogicandtomodeltheory. Wewill lookatelementary logic and modeltheory inmoredetailinChapter 4. We startwithafirst-orderlanguageappropriateforgrouptheory.Thislanguage, which wedenote𝐿 ,isthefirst-orderlanguagewithequalitycontainingabinaryoperation 0 −1 symbol⋅aunaryoperationsymbol andaconstantsymbol1.Asentencein𝐿 is 0 alogicalexpressionusingvariables,theoperationalsymbolsabove,equality,logical connectivesandquantifiers.Auniversalsentenceof𝐿 isoneoftheform∀𝑥{𝜙(𝑥)} 0 where𝑥isatupleofdistinctvariables,𝜙(𝑥)isaformulaof𝐿 containingnoquanti- 0 fiersandcontainingatmostthevariablesof𝑥.Forexample ∀(𝑥,𝑦){𝑥𝑦 = 𝑦𝑥} vi | Preface isauniversalsentencedescribinganAbeliangroup.Similarlyanexistentialsentence isoneoftheform∃𝑥{𝜙(𝑥)}where𝑥and𝜙(𝑥)areasabove.Forexample ∃(𝑥,𝑦){𝑥𝑦 ≠𝑦𝑥} isanexistentialsentencedescribinganon-Abeliangroup.Auniversal-existentialsen- tenceisoneoftheform∀𝑥∃𝑦{𝜙(𝑥,𝑦)}.Similarlydefined isanexistential-universal sentence.Itisknownthatevery sentence of 𝐿 islogically equivalenttooneofthe 0 form𝑄 𝑥 ...𝑄 𝑥 𝜙(𝑥)where𝑥 = (𝑥 ,...,𝑥 )isatupleofdistinctvariables,each𝑄 1 1 𝑛 𝑛 1 𝑛 𝑖 for𝑖 = 1,...,𝑛isaquantifier,either∀or∃,and𝜙(𝑥)isaformulaof𝐿 containing 0 noquantifiersandcontainingfreelyatmostthevariables𝑥 ,...,𝑥 .Furthervacuous 1 𝑛 quantificationsarepermitted.Finallyapositivesentenceisonelogicallyequivalentto asentenceconstructedusing(atmost)theconnectives∨,∧,∀,∃. If𝐺isagroupthentheuniversaltheoryof𝐺consistsofthesetofalluniversal sentencesof𝐿 truein𝐺.Sinceanyuniversalsentenceisequivalenttothenegation 0 ofanexistentialsentenceitfollowsthattwogroupshavethesameuniversaltheoryif andonlyiftheyhavethesameexistentialtheory.Thesetofallsentencesof𝐿 truein𝐺 0 iscalledthefirst-ordertheoryortheelementarytheoryof𝐺.Wedenotethisby𝑇ℎ(𝐺). Wenotethatbeingfirst-orderorelementarymeansthatintheintendedinterpretation ofanyformulaorsentenceallofthevariables(freeorbound)areassumedtotakeonas valuesonlyindividualgroupelements–never,forexample,subsetsof,norfunctions on,thegroupinwhichtheyareinterpreted. Wesaythattwogroups𝐺and𝐻areelementarilyequivalent(symbolically𝐺≡ 𝐻) iftheyhavethesamefirst-ordertheory,thatis𝑇ℎ(𝐺) = 𝑇ℎ(𝐻). Groupmonomorphismswhichpreservefirst-orderformulasarecalledelementary embeddings.Specifically,if𝐻and𝐺aregroupsand 𝑓: 𝐻 →𝐺 is a monomorphism then 𝑓 is an elementary embedding provided whenever 𝜙(𝑥 , 0 ...,𝑥 )isaformulaof𝐿 containingfreeatmostthedistinctvariables𝑥 ,...,𝑥 and 𝑛 0 0 𝑛 𝑛+1 (ℎ ,...,ℎ ) ∈ 𝐻 then𝜙(ℎ ,...,ℎ )istruein𝐻ifandonlyif𝜙(𝑓(ℎ ),...,𝑓(ℎ ))is 0 𝑛 0 𝑛 0 𝑛 truein𝐺.If𝐻isasubgroupof𝐺andtheinclusionmap𝑖: 𝐻 → 𝐺isanelementary embeddingthenwesaythat𝐺isanelementaryextensionof𝐻. The genesis of the Tarski problems isthe observation that most theorems con- cerningfreegroupsareindependentoftherankofthefreegroup.Asanexamplewe notetheNielsen–SchreierTheorem(seeChapter2)whichsaysthatanysubgroupof afreegroupisitselfafreegroup(independentoftherankoftheovergroup).Another example isthe result that anAbelian subgroup of a free group, again of anyrank, mustbecyclic.Proceedingfurther,supposethat𝑛< 𝑚arepositiveintegers.Fromthe Nielsen–SchreierTheoremitisclearthatafreegroupofrank𝑛canbeembeddediso- morphicallyintoafreegroupofrank𝑚.Hence𝐹 canbeembeddedinto𝐹 .Further 𝑛 𝑚 itcanbeshownthatafreegroupofanycountablerankcanbeembeddedisomorphi- Preface | vii callyintoafreegroupofrank2.Itfollowsthat𝐹 canbeembeddedinto𝐹 .Therefore 𝑚 𝑛 𝐹 and𝐹 mustbesimilar. 𝑛 𝑚 Therewassomeinitialearly success onthe Tarski conjectures. Vaught showed thattheTarskiconjectures1,2aretrueif𝐺and𝐻arebothfreegroupsofinfiniterank. Combininghisresultwiththeelementarychaintheorem(seeChapter4)reducedthe conjecturestofreegroupsoffiniterank.Healsoprovidedacriterion,nowcalledthe Tarski–Vaughtcriterion,todetermineifanembeddingofonegroupintoanotherisan elementaryembedding. The next significant progress was due to Merzljakov. The positive theory of a group𝐺consistsofallthepositivesentencestruein𝐺.Merzljakov[185]showedthat the non-Abelianfreegroupshavethe samepositivetheory. AproofofMerzljakov’s [185]resultcanbegiveninvolvinggeneralizedequationsandaquantifierelimination process. This was a precursor to the methods used in the eventual solution of the overallTarskiproblems. WorkfollowingMerzljakovcenteredonrestrictedtheoriesoffreegroups.Itisfairly straightforwardtoshowthatanytwonon-Abelianfreegroupssatisfythesameuniver- saltheory.Sacerdote[226]provedthatthiscouldbeextendedtouniversal-existential sentencesor𝜋 -sentences(seeChapter4). 2 Despite this early sucessful work, the conjectures remained open for over fifty yearsafter Tarskiinitially proposed them. Ina1988paper surveyingcombinatorial grouptheory [175]Roger LyndoncalledtheTarskiproblems,whichhedescribedas folklore,amongtheoutstandingopenproblems(atthattime)inthefield.Afterthis pointthepiecesinthebigpuzzlebegantoplacedtogether.FirstaresultofGaglione andSpellmanandindependentlyV.RemeslennikovandbuildingonresultsofGilbert BaumslagandBenjaminBaumslagshowedthatfinitelygeneratedgroupsthatshare the sameuniversaltheory asthe classof non-Abelian freegroups areprecisely the classof finitely generated fully residually free groups. Thisshifted the focus to the class of finitely generated fully residually free groups in the search for the classof groupsthatsharethesamecompletefirst-ordertheoryasthenon-Abelianfreegroups. Further from the Tarski–Vaught criterion the concentration was on the solution of equationsingroups. Dealingwithsystemsofequationover freegroups,itwasclearfromthebegin- ningthattodealwiththeTarski’sconjecturesaprecisedescriptionofsolutionsetsof equations(andinequations)overfreegroupswasneeded.Thereforeinanalogywith the classicalsolutions of polynomial equations over fields what wasneeded was a translationofclassicialalgebraicgeometrytoanalgebraicgeometryovergroups.In thelate1990sGilbertBaumslag,OlgaKharlampovich,AlexeiMyasnikov,andVladimir Remeslennikovdevelopedthebasicsofalgebraicgeometryovergroupsintroducing analogsofthestandardalgebraicgeometricnotionssuchasalgebraicsets,theZariski topology,Noetheriandomains,irreduciblevarieties,radicalsandcoordinategroups. Thefirstgeneralresultsonequationsingroupsappearedinthe1960s.RogerLyn- don developed several extremely important ideas. He considered completions of a viii | Preface givengroup𝐺byallowingexponentsinvariousringsandthenusedthesecomple- tionstoparameterizesolutionsofequationsin𝐺.Alongtheselinesheintroducedthe ℤ[𝑡] freeexponentialgroup𝐹 withexponentsintheintegralpolynomialringℤ[𝑡].Sub- sequentlyitwasshownthatthefinitelygeneratedsubgroupsofthisfreeexponential groupcoincideswiththeclassoffinitley generated fullyresiduallyfreegroupsand hencewiththeclassofuniversallyfreegroups. AnotherideaoriginatingwithLyndon,inadditiontogeneralizingtheringofex- ponentstoℤ[𝑡],istoconsidergroupswithfreelengthfunctionswithvaluesinsome orderedAbeliangroup.ThisallowsonetoaxiomatizetheclassicalNielsentechnique basedonthestandardlengthfunctioninfreegroupsandapplyitto“non-standard” extensions of free groups, for instance, to ultrapowers of free groups. A link with theTarskiproblemscomesherebytheKeisler–Shelahtheorem,thatstatesthattwo groupsareelementarilyequivalentifandonlyiftheirultrapowers(withrespecttoa non-principalultrafilter)areisomorphic. Intheeightiesnewcrucialconceptswereintroduced.Makaninprovedthealgo- rithmicdecidabilityoftheDiophantineproblemover freegroups, andshowed that both,theuniversaltheoryandthepositivetheoryofafreegrouparealgorithmically decidable.Hecreatedanextremelypowerfultechnique(theMakanineliminationpro- cess)todealwithequationsoverfreegroups.Shortlyafterwards,Razborovthende- scribedthesolutionsetofanarbitrarysystemofequationsoverafreegroupinterms ofwhatisknownnowasMakanin–Razborovdiagrams. AfewyearslaterEdmundsandCommerfordandGrigorchuckandKurchanovde- scribedsolutionsetsofarbitraryquadraticequationsoverfreegroups.Theseequa- tionscametogrouptheoryfromtopologyandtheirroleingrouptheorywasnotini- tiallyclear.Howeveritwassubsequentlyproved,anditbecamefundamentaltothe proofoftheTarskiconjectures,thatanarbitrarysystemofequationsisequivalentto acollectionofaspecialtypeofquadraticsystems. Thisbookislaidoutinthefollowingmanner.InChapter2wepresenttheneces- sarymaterialfromCombinatorialGroupTheory.Thiswillincludethematerialonfree groupsandgroupamalgams. Over the past twenty years, building on work of Gromov, Rips, Bass and Serre andothers,geometricideashavegainedprominence.Thishasbeengiventheoverall nameGeometricGroupTheoryandincludeshyperbolicgrouptheoryandthetheory ofgroupsactingonvarioustypesoftrees.InChapter3wedescribetheessentialideas inGeometricGroupTheory. InChapter4wewillformallyintroducetheideasfromfirst-orderlanguagesand modeltheory,mostofwhicharenotaswell-knowntogrouptheoristsastheyshould be.Wewillalsoreviewtheconceptsoffilters,ultra-filtersandultra-productswhich areessentialtoolsinthestudyofelementaryproperties. InChapter5wewillgiveamoreformaldescriptionoftheTarskiproblemsaswell asasurveyofTarski-likeresultsforotherclassesofgroups. Preface | ix InChapters6and7wedescribethevastbodyofresultsonfullyresiduallyfree groups.InChapter6weintroducefullyresiduallyfreegroups,andrelatedconcepts, andpresentthebasicpropertiesofsuchgroupsincludingtheequivalencewithuni- versallyfreegroups.Wealsodescribethegeneralstructuretheoryofthesegroups. InSela’sapproachtheclassoffullyresiduallyfreegroupsarisesastheclassof limitinggroupsfromhomomorphismsintofreegroups.Selatermstheselimitgroups. InChapter7wedescribetheequivalencesforvariousinterpretationsoftheclassof limitgroupsincludingsometopologicalinterpretations. InChapter8wepresentthebasicframeworkofalgebraicgeometryovergroups. Thisincludesalgebraicsets,theZariskitopology,Noetheriandomains,irreducibleva- rieties,radicalsandcoordinategroups.Wealsoprovethatthecoordinategroupsof irreduciblealgebraicvarietiesoverfreegroupsarethelimitgroups. InChapter9weoutlinetheKharlampovich–MyasnikovproofoftheTarskiprob- lems.Thisinvolvesaninductiononthenumberofquantifiersinalogicalsentence andaquantifiereliminationprocessthattheycalltheeliminationprocess. AspartofthesolutionoftheTarskiconjecturesbothKharlampovich–Myasnikov andSelaprovideacompletedescriptionoftheclassofgroupsthatsharetheelemen- tary theory of the non-Abelian free groups. These extend beyond the class of non- Abelianfreegroupsandarecalledtheelementaryfreegroups.InChapter10wecon- siderthegeneraltheoryoftheelementary freegroupsandpresentsomeproperties thatgobeyondwhatistrueinfreegroups.Itisknownthatthesurfacegroupsofhigh enoughgenusareelementaryfreeandthisprovidesamethodtoproveresultsinsur- facegroupsthatareotherwisequiteinaccesibleanddifficult.Wediscussthisalsoin Chapter10. FinallyinChapter11wediscussalargebodyofresultsconcerningdiscriminating groups,aclassofgroupsintroducedbyG.Baumslag,MyasnikovandRemeslennikov asaby-productofthedevelopmentofalgebraicgeometry. Wehopethat thebookwill find good useamong thegroup theoretic and logic community. Wewould liketo thankpeoplewho havelooked over portionsofthe bookand helpeduswiththepreparationincludingGilbertBaumslagandOlgaKharlampovich. EspeciallywethankAnjaMoldenhauer whocarefullylookedover thechaptersand preparedthediagramsandfigures. BenFine AnthonyGaglione AlexeiMyasnikov GerhardRosenberger DennisSpellman