The complexity of the reals in inner models of set

arXiv:math/9501203v1[math.LO]2Jan1995ComplexityoftherealsofinnermodelsofsettheoryBobanVelickovicandW.HughWoodinIntroductionTheusualdefinitionofthesetofconstructiblerealsRLisΣ12.Thissetcanhaveasimplerdefinitionif,forexample,itiscountableorifeveryrealisinL.MartinandSolovay[MS1]haveshownthatifMAℵ1holdsandthereisarealrsuchthatℵL[r]1=ℵ1theneverysetofrealsofsizeℵ1isco-analytic.ThusbyacccforcingoverauniverseofV=LwecanobtainauniverseofsettheoryinwhichRLisanuncountableco-analyticsetyetnoteveryrealisinL.TheresultsofthispaperweremotivatedbyaquestionofH.Friedman[Fr,problem86]whoaskedifRLcanbeanalyticorevenBorelinanontrivialway,thatisbothuncountableandnotequaltothesetofallreals.ThereisacompanionquestionduetoK.PrikrywhetherRLcouldcontainaperfectsetandnotbeequaltothesetofallreals.Clearlyapositiveanswertothefirstquestionwouldalsoimplyapositiveanswertothesecondone.ThemainresultofthispaperisanegativeanswertoFriedman’squestion.InfactweprovethatifMisaninnermodelofsettheoryandthesetRMofrealsinMisanalytictheneitherallrealsareinMorelseℵM1iscountable.SincethecardinalityofRLisℵL1thisimpliesthedesiredresultinthecaseM=L.Wealsoshowthatinthecontextoflargecardinalsthisresultcanbeextendedtoprojectivesetsinplaceofanalyticsets.However,theconclusionofthemaintheoremcannotbestrengthenedtosaythateitherallrealsareinMorelsethecontinuumofMiscountable.WeproduceapairofgenericextensionsWandVofLsuchthatW⊆V,therealsofWformanuncountableFσsetinV,andyetnotallrealsfromVareinW.1InrelationtoPrikry’sproblemweshowthatifaninnermodelMcontainsasuperperfectsetofrealsthenitcontainsallreals.Theproofisbasedonaconstructionofarecursivecoloringoftriplesofrealsinto2ωsuchthatforanysuperperfectsetPthetriplesfromPobtainallcolors.AsimilarpartitionwasusedbyGitik[Gi]whoshowedthatifVisauniverseofsettheoryandrisarealnotinVthenthesetofcountablesubsetsofω2inV[r]whicharenotinVformastationarysetin[ω2]ℵ0.Itwasobservedbythefirstauthorin[Ve]thatthisimpliesthatiftheSemiProperForcingAxiom(SPFA)holdsandMisaninnermodelofsettheorysuchthatℵM2=ℵ2thenallrealsareinM.InthepositivedirectionofPrikry’sproblemwegiveanexampleoftwogenericextensionsVandWofLsuchthatW⊆V,ℵW1=ℵV1,andthereisaperfectsetinVconsistingofrealsfromW.Thepaperisorganizedasfollows.In§1wepresentthecoloringoftriplesofrealsdescribedabove.Itusesoscillationsofrealsnumbers,atechniquecommonlyusedintheconstructionofexamplestonegativepartitionrelations(seeforexample[To]).Wethenuseittoproveaspecialcaseofthemaintheoreminthecaseoftheconstructibleuniverse.Althoughthisproof,whichusesJensen’sCoveringLemma,issubsumedbyTheorem3wepresentitsinceitmayhavesomeinterestofitsown.In§2weproveakindofregularitypropertyforΣ11setssayingthatifananalyticsetAcontainscodesforallcountableordinalstheneveryrealishy-perarithmeticinafinitesequenceofelementsofA.Fromthisourmainresultfollowseasily.Wethenextendthistohigherlevelsoftheprojectivehierarchyunderappropriatelargecardinalassumptionsorprojectivedeterminacy.Section§3containsexamplesofpairsofmodelsofsettheorywhichshowthattheaboveresultsareinsomesensebestpossible.WeprovethatitispossibletohaveaninnermodelofsettheoryWwhoserealsformanuncountableFσsetandyetnotallrealsbelongtoW.ThennecessarilyℵW1iscountable.HoweveritispossibletohaveℵW1=ℵ1ifweonlyrequirethatWcontainsaperfectsetofreals.Finallyin§4weproveassumingAD+V=L(R)thatifMisanin-nermodelofZFcontainingaSouslinprewellorderingofrealsoflengthℵV1thenallrealsareinM.ThisresulthassomeconsequencesinthetheoryofcardinalsinL(R)undertheaxiomofdeterminacy.Someassumptionontheprewellorderingintheaboveresultisnecessary.WeproveinZFalonethatassumingthereisanonconstructiblerealthereisaninnermodelMofZFcontainingaprewellorderingofrealsoflengthℵV1andsuchthatnotallreals2belongtoM.Ournotationisfairlystandardorself-explanatory.Forallundefinednotionssee[Ku].ForanindexsetIweshallletC(I)denotetheusualforcingforaddingICohenreals.ThusconditionsinC(I)arefinitepartialfunctionsfromω×Ito{0,1}andtheorderisinclusion.1ColoringtriplesofrealsWenowpresentthecoloringoftriplesofrealsdescribedintheintroduction.Firstwemakesomerelevantdefinitions.WeidentifythesetofrealsRwiththeset(ω)ωofallinfiniteincreasingsequencesofnaturalnumbers.Weshalllet≤∗denotetheorderingofeventualdominanceon(ω)ω.Wealsolet(ω)ωdenotethesetofallfiniteincreasingsequencesofnaturalnumbers.Then(ω)ωformsatreeunderinclusion.GivenasubtreeTof(ω)ωwesaythatanodes∈Tisω-splittingiftheset{k:sbk∈T}isinfinite.Tiscalledsuperperfectifaboveeverynodes∈Tthereisanodet∈Twhichisω-splitting.AsubsetPof(ω)ωiscalledsuperperfectifthesetTofallfiniteinitialsegmentsofmembersofPformsasuperperfecttree.Theorem1Thereisapartialrecursivefunctiono:R3→{0,1}ωsuchthatforeverysuperperfectsetPo′′(P3)={0,1}ω.PROOF:Givendistinctrealsx,y,z∈(ω)ωletO(x,y,z)={n:z(n−1)≤x(n−1),y(n−1)andx(n),y(n)z(n)}.o(x,y,z)willbedefinediffO(x,y,z)isinfinite.IfO(x,y,z)isinfinitelet{nk:kω}betheincreasingenumerationofitsmembers.Defineo(x,y,z)tobethefunctionα:ω→{0,1}whereforeverykω,α(k)=0iffx(nk)≤y(nk).WeshowthatifPisasuperperfectsubsetof(ω)ωandα∈{0,1}ωtherearex,y,z∈Psuchthato(x,y,z)=α.Thus,fixsuchasuperperfectsetPandletTbethe