THERE EXISTS A MAXIMAL 3-C.E. ENUMERATION DEGREE

THEREEXISTSAMAXIMAL3-C.E.ENUMERATIONDEGREES.BARRYCOOPER,ANGSHENGLI,ANDREASORBIANDYUEYANGAbstract.Weconstructanincomplete3-c.e.enumerationdegreewhichismaximalamongthen-c.e.enumerationdegreesforeverynwith3·n·!.Consequentlythen-c.e.enumerationdegreesarenotdenseforanysuchn.Weshowalsothatnolown-c.e.e-degreecanbemaximalamongthen-c.e.e-degrees,for2·n·!.1.IntroductionAnalgorithm©relativetoauxiliaryinformation(ororacle)Kyieldsafunc-tion©KcomputablefromK,whichmayormaynotbede¯nedonallinputs.Restrictingone'sattentiontothespecialcasewhen©Kisacharacteristicfunc-tionleadsdirectlytothesetsTuringreducibletoK,andtothefamiliarlocalstructureoftheTuringdegrees.Thebasisfortheexclusionofnontotal©Ais,ofcourse,nonconstructive(byRogers[19],thesetofindicesoftotal©Ais¦A2-complete).Andinanycase,therearetheoreticalimperativesleadingnotmerelytoamorecomprehensivestructure(theenumerationdegrees),buttoamathematicallyinformativecontextfortheTuringdegreesthemselves.Thisistheperspectivefromwhichweapproach,below,thequestionoflocaldensity/nondensityofdegreestructures.ComputabilitytheoryhasuntilrecentlybeendominatedbythestructureoftheTuringdegrees,especiallyofthecomputablyenumerable(orc.e.)Turingdegrees.Asthestructureofthec.e.Turingdegreesbecomesincreasinglywellunderstood,leavingasmallnumberofimportantandintractableproblemsap-parentlyoutofthereachofcurrenttechniques,thereismoreandmoreinterest1991MathematicsSubjectClassi¯cation.03D30.The¯rsttwoauthorswerepartiallysupportedbyEPSRCResearchGrant\TuringDe-¯nabilityNo.GR/M91419(UK),andthesecondauthorbyNSFgrantNo.69973048andbyNSFmajorgrantNo.19931020(P.R.CHINA),andbyanINDAMvisitingprofessorshipattheUniversityofSiena.ThelastauthorwaspartiallysupportedasavisitingscholarbytheUniversityofSiena.The¯rstthreeauthorswerefundedbytheINTAS-RFBRjointprojectComputabilityandModels,no.972-139.ThefourthauthorwouldliketothankMaratArslanovforusefuldiscussions.12S.BARRYCOOPER,ANGSHENGLI,ANDREASORBIANDYUEYANGinrelatedstructures|suchasthen-c.e.Turingdegrees,theenumerationde-greesofthe§02setsandthen-c.e.enumerationdegrees,eachofwhichformsanaturalextensionsofthec.e.Turingdegrees.ComparedwiththeTuringorc.e.Turingdegrees,theseextensionsappeartohavemanynovelfeatures.Webeginwithabriefsurveyofdensityresultsforvariousdegreestructures.1.1.TheTuringdegrees.AprototypicalresultofSacksintheearly1960'ssettledthedensityproblemforthec.e.Turingdegrees.Theorem1.1(SacksDensityTheorem[22]).Foranypairofc.e.Turingde-greesab,thereisac.e.Turingdegreecsuchthatacb.ConcerningtheglobalstructureoftheTuringdegrees,Spector[23]showedthatthereisaminimaldegree(below000),aresultlaterimprovedbySacks.Theorem1.2(Sacks[21]).Thereisaminimaldegreea00.1.2.Theenumerationdegrees.Letus¯rstrecallsomebasicfactsabouttheenumerationdegrees.Ourformalizationofenumerationreducibilitycloselyfollows[12];seealso[20].Formoreinformation,seeCooper'ssurveypaper[6].De¯nition1.3.Anenumerationoperator(ore-operator)isacomputablyenumerablesetªofpairshx;Fi,whereFis(thecodeof)a¯nitesubsetof!.Eachpairhx;Fi2ªiscalledaª-axiomandFiscalledapositiveneighborhoodcondition.ForasetB,ifFµBthenwesaythattheª-axiomhx;FiappliestoB.Foranye-operatorªandanysetB,ªBisde¯nedtobetheset:ªB=fx:(9F)(hx;Fi2ª^FµB)g:WesaythatasetAise-reducibletoasetB(insymbols:A·eB)ifthereisane-operatorªsuchthatA=ªB.Thedegreestructureinducedbye-reducibilityisthestructureoftheenu-merationdegrees(ore-degrees),whichisanaturalextensionofthestructureoftheTuringdegrees,afact¯rstnoticedbyMyhill[17].Indeed,itiseasilyseenthatthemappingdegT(A)7!dege(cA)(wherecAdenotesthegraphofthecharacteristicfunctionofA)isanorder-theoreticembeddingoftheTuringdegreesintothee-degrees.Seeforinstance[20,Corollary9.XXIV].Itiseasytoseethatunderthisembeddingthec.e.Turingdegreescorrespondtothe¦01e-degrees.ThustheSacksDensityTheoremforthec.e.Turingdegreesimmediatelygivesusdensityofthe¦01e-degrees.Densityinthee-degreesisbynowafairlywellunderstoodphenomenon.Itisknownforinstancethatthelocalstructureofthee-degrees,whichcoincideswiththe§02e-degrees,isdense.THEREEXISTSAMAXIMAL3-C.E.ENUMERATIONDEGREE3Theorem1.4(Cooper[4];seealsoLachlanandShore[15]).Thestructureofthe§02e-degreesisdense.UnlikethecaseoftheTuringdegrees,thereisnominimale-degree,asprovedbyGutteridge,[13];seealsoCooper[4].Theproofcombinestworesults:First,anycandidatetobeaminimale-degreemustbe¢02;thenitmakesuseofthefollowinglemma.Lemma1.5([5]).Forany¢02setBwith;eB,thereisa¢02setAsuchthat;eAeB.However,theglobalstructureofthee-degreesisnotdense.Thisresultwas¯rstshownbyCooper[5],andlaterimprovedbyCalhounandSlaman.Theorem1.6(CalhounandSlaman[3]).Thestructureofthe¦02e-degreesisnotdense.Infactthereisanemptyinterval(a;b)ofe-degreeswithaandb¦02e-degreesandaeb.Recently,Arslanov,KalimullinandSorbiestablishedthefulldensityofthe¢02e-degrees.Theorem1.7(Arslanov,KalimullinandSorbi[2]).Thestructureofthe¢02e-degreesisdense.1.3.Then-c.e.Turingdegrees.Then-c.e.setswere¯rststudiedbyPut-nam[18]andErshov[9],[10],[11].Formoreinformation,seee.g.Epstein,HaasandKramer[8].Werecallthebasicde¯nitions.De¯nition1.8.AsetAissaidtoben-c.e