Zermelo–Fraenkel set theory - Wikipedia

Zermelo–Fraenkel set theory with the axiom of choice included is abbreviated ZFC, where C stands for "choice", and ZF refers to the axioms of Zermelo–Fraenkel ... Zermelo–Fraenkelsettheory FromWikipedia,thefreeencyclopedia Jumptonavigation Jumptosearch Standardsystemofaxiomaticsettheory "ZFC"redirectshere.Forotheruses,seeZFC(disambiguation). Insettheory,Zermelo–Fraenkelsettheory,namedaftermathematiciansErnstZermeloandAbrahamFraenkel,isanaxiomaticsystemthatwasproposedintheearlytwentiethcenturyinordertoformulateatheoryofsetsfreeofparadoxessuchasRussell'sparadox.Today,Zermelo–Fraenkelsettheory,withthehistoricallycontroversialaxiomofchoice(AC)included,isthestandardformofaxiomaticsettheoryandassuchisthemostcommonfoundationofmathematics.Zermelo–FraenkelsettheorywiththeaxiomofchoiceincludedisabbreviatedZFC,whereCstandsfor"choice",[1]andZFreferstotheaxiomsofZermelo–Fraenkelsettheorywiththeaxiomofchoiceexcluded. Zermelo–Fraenkelsettheoryisintendedtoformalizeasingleprimitivenotion,thatofahereditarywell-foundedset,sothatallentitiesintheuniverseofdiscoursearesuchsets.ThustheaxiomsofZermelo–Fraenkelsettheoryreferonlytopuresetsandpreventitsmodelsfromcontainingurelements(elementsofsetsthatarenotthemselvessets).Furthermore,properclasses(collectionsofmathematicalobjectsdefinedbyapropertysharedbytheirmemberswherethecollectionsaretoobigtobesets)canonlybetreatedindirectly.Specifically,Zermelo–Fraenkelsettheorydoesnotallowfortheexistenceofauniversalset(asetcontainingallsets)norforunrestrictedcomprehension,therebyavoidingRussell'sparadox.VonNeumann–Bernays–Gödelsettheory(NBG)isacommonlyusedconservativeextensionofZermelo–Fraenkelsettheorythatdoesallowexplicittreatmentofproperclasses. TherearemanyequivalentformulationsoftheaxiomsofZermelo–Fraenkelsettheory.Mostoftheaxiomsstatetheexistenceofparticularsetsdefinedfromothersets.Forexample,theaxiomofpairingsaysthatgivenanytwosets a {\displaystylea} and b {\displaystyleb} thereisanewset { a , b } {\displaystyle\{a,b\}} containingexactly a {\displaystylea} and b {\displaystyleb} .Otheraxiomsdescribepropertiesofsetmembership.AgoaloftheaxiomsisthateachaxiomshouldbetrueifinterpretedasastatementaboutthecollectionofallsetsinthevonNeumannuniverse(alsoknownasthecumulativehierarchy).Formally,ZFCisaone-sortedtheoryinfirst-orderlogic.Thesignaturehasequalityandasingleprimitivebinaryrelation,setmembership,whichisusuallydenoted ∈ {\displaystyle\in} .Theformula a ∈ b {\displaystylea\inb} meansthattheset a {\displaystylea} isamemberoftheset b {\displaystyleb} (whichisalsoread," a {\displaystylea} isanelementof b {\displaystyleb} "or" a {\displaystylea} isin b {\displaystyleb} "). ThemetamathematicsofZermelo–Fraenkelsettheoryhasbeenextensivelystudied.LandmarkresultsinthisareaestablishedthelogicalindependenceoftheaxiomofchoicefromtheremainingZermelo-Fraenkelaxioms(seeAxiomofchoice§ Independence)andofthecontinuumhypothesisfromZFC.TheconsistencyofatheorysuchasZFCcannotbeprovedwithinthetheoryitself,asshownbyGödel'ssecondincompletenesstheorem. Contents 1History 2Axioms 2.11.Axiomofextensionality 2.22.Axiomofregularity(alsocalledtheaxiomoffoundation) 2.33.Axiomschemaofspecification(alsocalledtheaxiomschemaofseparationorofrestrictedcomprehension) 2.44.Axiomofpairing 2.55.Axiomofunion 2.66.Axiomschemaofreplacement 2.77.Axiomofinfinity 2.88.Axiomofpowerset 2.99.Well-orderingtheorem 3Motivationviathecumulativehierarchy 4Metamathematics 4.1Virtualclasses 4.2VonNeumann–Bernays–Gödelsettheory 4.3Consistency 4.4Independence 4.5Proposedadditions 5Criticisms 6Seealso 7Notes 8Workscited 9Externallinks History[edit] ThemodernstudyofsettheorywasinitiatedbyGeorgCantorandRichardDedekindinthe1870s.However,thediscoveryofparadoxesinnaivesettheory,suchasRussell'sparadox,ledtothedesireforamorerigorousformofsettheorythatwasfreeoftheseparadoxes. In1908,ErnstZermeloproposedthefirstaxiomaticsettheory,Zermelosettheory.However,asfirstpointedoutbyAbrahamFraenkelina1921lettertoZermelo,thistheorywasincapableofprovingtheexistenceofcertainsetsandcardinalnumberswhoseexistencewastakenforgrantedbymostsettheoristsofthetime,notablythecardinalnumber ℵ ω {\displaystyle\aleph_{\omega}} andtheset { Z 0 , P ( Z 0 ) , P ( P ( Z 0 ) ) , P ( P ( P ( Z 0 ) ) ) , . . . } , {\displaystyle\{Z_{0},{\mathcal{P}}(Z_{0}),{\mathcal{P}}({\mathcal{P}}(Z_{0})),{\mathcal{P}}({\mathcal{P}}({\mathcal{P}}(Z_{0}))),...\},} where Z 0 {\displaystyleZ_{0}} isanyinfinitesetand P {\displaystyle{\mathcal{P}}} isthepowersetoperation.[2]Moreover,oneofZermelo'saxiomsinvokedaconcept,thatofa"definite"property,whoseoperationalmeaningwasnotclear.In1922,FraenkelandThoralfSkolemindependentlyproposedoperationalizinga"definite"propertyasonethatcouldbeformulatedasawell-formedformulainafirst-orderlogicwhoseatomicformulaswerelimitedtosetmembershipandidentity.Theyalsoindependentlyproposedreplacingtheaxiomschemaofspecificationwiththeaxiomschemaofreplacement.Appendingthisschema,aswellastheaxiomofregularity(firstproposedbyJohnvonNeumann),[3]toZermelosettheoryyieldsthetheorydenotedbyZF.AddingtoZFeithertheaxiomofchoice(AC)orastatementthatisequivalenttoityieldsZFC. Axioms[edit] TherearemanyequivalentformulationsoftheZFCaxioms;foradiscussionofthisseeFraenkel,Bar-Hillel&Lévy1973.ThefollowingparticularaxiomsetisfromKunen(1980).Theaxiomsperseareexpressedinthesymbolismoffirstorderlogic.TheassociatedEnglishproseisonlyintendedtoaidtheintuition. AllformulationsofZFCimplythatatleastonesetexists.Kunenincludesanaxiomthatdirectlyassertstheexistenceofaset,inadditiontotheaxiomsgivenbelow(althoughhenotesthathedoessoonly"foremphasis").[4]Itsomissionherecanbejustifiedintwoways.First,inthestandardsemanticsoffirst-orderlogicinwhichZFCistypicallyformalized,thedomainofdiscoursemustbenonempty.Hence,itisalogicaltheoremoffirst-orderlogicthatsomethingexists—usuallyexpressedastheassertionthatsomethingisidenticaltoitself, ∃ x ( x = x ) {\displaystyle\existsx(x=x)} .Consequently,itisatheoremofeveryfirst-ordertheorythatsomethingexists.However,asnotedabove,becauseintheintendedsemanticsofZFCthereareonlysets,theinterpretationofthislogicaltheoreminthecontextofZFCisthatsomesetexists.Hence,thereisnoneedforaseparateaxiomassertingthatasetexists.Second,however,evenifZFCisformulatedinso-calledfreelogic,inwhichitisnotprovablefromlogicalonethatsomethingexists,theaxiomofinfinity(below)assertsthataninfinitesetexists.Thisimpliesthatasetexistsandso,onceagain,itissuperfluoustoincludeanaxiomassertingasmuch. 1.Axiomofextensionality[edit] Mainarticle:Axiomofextensionality Twosetsareequal(arethesameset)iftheyhavethesameelements. ∀ x ∀ y [ ∀ z ( z ∈ x ⇔ z ∈ y ) ⇒ x = y ] . {\displaystyle\forallx\forally[\forallz(z\inx\Leftrightarrowz\iny)\Rightarrowx=y].} Theconverseofthisaxiomfollowsfromthesubstitutionpropertyofequality.Ifthebackgroundlogic[definitionneeded]doesnotincludeequality" = {\displaystyle=} ", x = y {\displaystylex=y} maybedefinedasanabbreviationforthefollowingformula:[5] ∀ z [ z ∈ x ⇔ z ∈ y ] ∧ ∀ w [ x ∈ w ⇔ y ∈ w ] . {\displaystyle\forallz[z\inx\Leftrightarrowz\iny]\land\forallw[x\inw\Leftrightarrowy\inw].} Inthiscase,theaxiomofextensionalitycanbereformulatedas ∀ x ∀ y [ ∀ z ( z ∈ x ⇔ z ∈ y ) ⇒ ∀ w ( x ∈ w ⇔ y ∈ w ) ] , {\displaystyle\forallx\forally[\forallz(z\inx\Leftrightarrowz\iny)\Rightarrow\forallw(x\inw\Leftrightarrowy\inw)],} whichsaysthatif x {\displaystylex} and y {\displaystyley} havethesameelements,thentheybelongtothesamesets.[6] 2.Axiomofregularity(alsocalledtheaxiomoffoundation)[edit] Mainarticle:Axiomofregularity Everynon-emptyset x {\displaystylex} containsamember y {\displaystyley} suchthat x {\displaystylex} and y {\displaystyley} aredisjointsets. ∀ x [ ∃ a ( a ∈ x ) ⇒ ∃ y ( y ∈ x ∧ ¬ ∃ z ( z ∈ y ∧ z ∈ x ) ) ] . {\displaystyle\forallx[\existsa(a\inx)\Rightarrow\existsy(y\inx\land\lnot\existsz(z\iny\landz\inx))].} [7] orinmodernnotation: ∀ x ( x ≠ ∅ ⇒ ∃ y ∈ x ( y ∩ x = ∅ ) ) . {\displaystyle\forallx\,(x\neq\varnothing\Rightarrow\existsy\inx\,(y\capx=\varnothing)).} This(alongwiththeAxiomofPairing)implies,forexample,thatnosetisanelementofitselfandthateverysethasanordinalrank. 3.Axiomschemaofspecification(alsocalledtheaxiomschemaofseparationorofrestrictedcomprehension)[edit] Mainarticle:Axiomschemaofspecification Subsetsarecommonlyconstructedusingsetbuildernotation.Forexample,theevenintegerscanbeconstructedasthesubsetoftheintegers Z {\displaystyle\mathbb{Z}} satisfyingthecongruencemodulopredicate x ≡ 0 ( mod 2 ) {\displaystylex\equiv0{\pmod{2}}} : { x ∈ Z : x ≡ 0 ( mod 2 ) } . {\displaystyle\{x\in\mathbb{Z}:x\equiv0{\pmod{2}}\}.} Ingeneral,thesubsetofaset z {\displaystylez} obeyingaformula ϕ ( x ) {\displaystyle\phi(x)} withonefreevariable x {\displaystylex} maybewrittenas: { x ∈ z : ϕ ( x ) } . {\displaystyle\{x\inz:\phi(x)\}.} Theaxiomschemaofspecificationstatesthatthissubsetalwaysexists(itisanaxiomschemabecausethereisoneaxiomforeach ϕ {\displaystyle\phi} ).Formally,let ϕ {\displaystyle\phi} beanyformulainthelanguageofZFCwithallfreevariablesamong x , z , w 1 , … , w n {\displaystylex,z,w_{1},\ldots,w_{n}} ( y {\displaystyley} isnotfreein ϕ {\displaystyle\phi} ).Then: ∀ z ∀ w 1 ∀ w 2 … ∀ w n ∃ y ∀ x [ x ∈ y ⇔ ( ( x ∈ z ) ∧ ϕ ) ] . {\displaystyle\forallz\forallw_{1}\forallw_{2}\ldots\forallw_{n}\existsy\forallx[x\iny\Leftrightarrow((x\inz)\land\phi)].} Notethattheaxiomschemaofspecificationcanonlyconstructsubsets,anddoesnotallowtheconstructionofentitiesofthemoregeneralform: { x : ϕ ( x ) } . {\displaystyle\{x:\phi(x)\}.} ThisrestrictionisnecessarytoavoidRussell'sparadoxanditsvariantsthataccompanynaivesettheorywithunrestrictedcomprehension. InsomeotheraxiomatizationsofZF,thisaxiomisredundantinthatitfollowsfromtheaxiomschemaofreplacementandtheaxiomoftheemptyset. Ontheotherhand,theaxiomofspecificationcanbeusedtoprovetheexistenceoftheemptyset,denoted ∅ {\displaystyle\varnothing} ,onceatleastonesetisknowntoexist(seeabove).Onewaytodothisistouseaproperty ϕ {\displaystyle\phi} whichnosethas.Forexample,if w {\displaystylew} isanyexistingset,theemptysetcanbeconstructedas ∅ = { u ∈ w ∣ ( u ∈ u ) ∧ ¬ ( u ∈ u ) } . {\displaystyle\varnothing=\{u\inw\mid(u\inu)\land\lnot(u\inu)\}.} Thustheaxiomoftheemptysetisimpliedbythenineaxiomspresentedhere.Theaxiomofextensionalityimpliestheemptysetisunique(doesnotdependon w {\displaystylew} ).Itiscommontomakeadefinitionalextensionthataddsthesymbol" ∅ {\displaystyle\varnothing} "tothelanguageofZFC. 4.Axiomofpairing[edit] Mainarticle:Axiomofpairing If x {\displaystylex} and y {\displaystyley} aresets,thenthereexistsasetwhichcontains x {\displaystylex} and y {\displaystyley} aselements. ∀ x ∀ y ∃ z ( ( x ∈ z ) ∧ ( y ∈ z ) ) . {\displaystyle\forallx\forally\existsz((x\inz)\land(y\inz)).} Theaxiomschemaofspecificationmustbeusedtoreducethistoasetwithexactlythesetwoelements.TheaxiomofpairingispartofZ,butisredundantinZFbecauseitfollowsfromtheaxiomschemaofreplacement,ifwearegivenasetwithatleasttwoelements.Theexistenceofasetwithatleasttwoelementsisassuredbyeithertheaxiomofinfinity,orbytheaxiomschemaofspecificationandtheaxiomofthepowersetappliedtwicetoanyset. 5.Axiomofunion[edit] Mainarticle:Axiomofunion Theunionovertheelementsofasetexists.Forexample,theunionovertheelementsoftheset { { 1 , 2 } , { 2 , 3 } } {\displaystyle\{\{1,2\},\{2,3\}\}} is { 1 , 2 , 3 } . {\displaystyle\{1,2,3\}.} Theaxiomofunionstatesthatforanysetofsets F {\displaystyle{\mathcal{F}}} thereisaset A {\displaystyleA} containingeveryelementthatisamemberofsomememberof F {\displaystyle{\mathcal{F}}} : ∀ F ∃ A ∀ Y ∀ x [ ( x ∈ Y ∧ Y ∈ F ) ⇒ x ∈ A ] . {\displaystyle\forall{\mathcal{F}}\,\existsA\,\forallY\,\forallx[(x\inY\landY\in{\mathcal{F}})\Rightarrowx\inA].} Althoughthisformuladoesn'tdirectlyasserttheexistenceof ∪ F {\displaystyle\cup{\mathcal{F}}} ,theset ∪ F {\displaystyle\cup{\mathcal{F}}} canbeconstructedfrom A {\displaystyleA} intheaboveusingtheaxiomschemaofspecification: ∪ F = { x ∈ A : ∃ Y ( x ∈ Y ∧ Y ∈ F ) } . {\displaystyle\cup{\mathcal{F}}=\{x\inA:\existsY(x\inY\landY\in{\mathcal{F}})\}.} 6.Axiomschemaofreplacement[edit] Mainarticle:Axiomschemaofreplacement Theaxiomschemaofreplacementassertsthattheimageofasetunderanydefinablefunctionwillalsofallinsideaset. Formally,let ϕ {\displaystyle\phi} beanyformulainthelanguageofZFCwhosefreevariablesareamong x , y , A , w 1 , … , w n , {\displaystylex,y,A,w_{1},\dotsc,w_{n},} sothatinparticular B {\displaystyleB} isnotfreein ϕ {\displaystyle\phi} .Then: ∀ A ∀ w 1 ∀ w 2 … ∀ w n [ ∀ x ( x ∈ A ⇒ ∃ ! y ϕ ) ⇒ ∃ B   ∀ x ( x ∈ A ⇒ ∃ y ( y ∈ B ∧ ϕ ) ) ] . {\displaystyle\forallA\forallw_{1}\forallw_{2}\ldots\forallw_{n}{\bigl[}\forallx(x\inA\Rightarrow\exists!y\,\phi)\Rightarrow\existsB\\forallx{\bigl(}x\inA\Rightarrow\existsy(y\inB\land\phi){\bigr)}{\bigr]}.} Forthemeaningof ∃ ! {\displaystyle\exists!} ,seeuniquenessquantification. Inotherwords,iftherelation ϕ {\displaystyle\phi} representsadefinablefunction f {\displaystylef} , A {\displaystyleA} representsitsdomain,and f ( x ) {\displaystylef(x)} isasetforevery x ∈ A , {\displaystylex\inA,} thentherangeof f {\displaystylef} isasubsetofsomeset B {\displaystyleB} .Theformstatedhere,inwhich B {\displaystyleB} maybelargerthanstrictlynecessary,issometimescalledtheaxiomschemaofcollection. 7.Axiomofinfinity[edit] Mainarticle:Axiomofinfinity FirstfewvonNeumannordinals 0 ={} =∅ 1 ={0} ={∅} 2 ={0,1} ={∅,{∅}} 3 ={0,1,2} ={∅,{∅},{∅,{∅}}} 4 ={0,1,2,3} ={∅,{∅},{∅,{∅}},{∅,{∅},{∅,{∅}}}} Let S ( w ) {\displaystyleS(w)} abbreviate w ∪ { w } , {\displaystylew\cup\{w\},} where w {\displaystylew} issomeset.(Wecanseethat { w } {\displaystyle\{w\}} isavalidsetbyapplyingtheAxiomofPairingwith x = y = w {\displaystylex=y=w} sothatthesetzis { w } {\displaystyle\{w\}} ).ThenthereexistsasetXsuchthattheemptyset ∅ {\displaystyle\varnothing} isamemberofXand,wheneverasetyisamemberofXthen S ( y ) {\displaystyleS(y)} isalsoamemberofX. ∃ X [ ∅ ∈ X ∧ ∀ y ( y ∈ X ⇒ S ( y ) ∈ X ) ] . {\displaystyle\existsX\left[\varnothing\inX\land\forally(y\inX\RightarrowS(y)\inX)\right].} Morecolloquially,thereexistsasetXhavinginfinitelymanymembers.(Itmustbeestablished,however,thatthesemembersarealldifferent,becauseiftwoelementsarethesame,thesequencewilllooparoundinafinitecycleofsets.Theaxiomofregularitypreventsthisfromhappening.)TheminimalsetXsatisfyingtheaxiomofinfinityisthevonNeumannordinalωwhichcanalsobethoughtofasthesetofnaturalnumbers N . {\displaystyle\mathbb{N}.} 8.Axiomofpowerset[edit] Mainarticle:Axiomofpowerset Bydefinitionaset z {\displaystylez} isasubsetofaset x {\displaystylex} ifandonlyifeveryelementof z {\displaystylez} isalsoanelementof x {\displaystylex} : ( z ⊆ x ) ⇔ ( ∀ q ( q ∈ z ⇒ q ∈ x ) ) . {\displaystyle(z\subseteqx)\Leftrightarrow(\forallq(q\inz\Rightarrowq\inx)).} TheAxiomofPowerSetstatesthatforanyset x {\displaystylex} ,thereisaset y {\displaystyley} thatcontainseverysubsetof x {\displaystylex} : ∀ x ∃ y ∀ z [ z ⊆ x ⇒ z ∈ y ] . {\displaystyle\forallx\existsy\forallz[z\subseteqx\Rightarrowz\iny].} Theaxiomschemaofspecificationisthenusedtodefinethepowerset P ( x ) {\displaystyle{\mathcal{P}}(x)} asthesubsetofsucha y {\displaystyley} containingthesubsetsof x {\displaystylex} exactly: P ( x ) = { z ∈ y : z ⊆ x } . {\displaystyleP(x)=\{z\iny:z\subseteqx\}.} Axioms1–8defineZF.Alternativeformsoftheseaxiomsareoftenencountered,someofwhicharelistedinJech(2003).SomeZFaxiomatizationsincludeanaxiomassertingthattheemptysetexists.Theaxiomsofpairing,union,replacement,andpowersetareoftenstatedsothatthemembersoftheset x {\displaystylex} whoseexistenceisbeingassertedarejustthosesetswhichtheaxiomasserts x {\displaystylex} mustcontain. ThefollowingaxiomisaddedtoturnZFintoZFC: 9.Well-orderingtheorem[edit] Mainarticle:Well-orderingtheorem Foranyset X {\displaystyleX} ,thereisabinaryrelation R {\displaystyleR} whichwell-orders X {\displaystyleX} .Thismeans R {\displaystyleR} isalinearorderon X {\displaystyleX} suchthateverynonemptysubsetof X {\displaystyleX} hasamemberwhichisminimalunder R {\displaystyleR} . ∀ X ∃ R ( R well-orders X ) . {\displaystyle\forallX\existsR(R\;{\mbox{well-orders}}\;X).} Givenaxioms1 – 8,therearemanystatementsprovablyequivalenttoaxiom9,thebestknownofwhichistheaxiomofchoice(AC),whichgoesasfollows.Let X {\displaystyleX} beasetwhosemembersareallnonempty.Thenthereexistsafunction f {\displaystylef} from X {\displaystyleX} totheunionofthemembersof X {\displaystyleX} ,calleda"choicefunction",suchthatforall Y ∈ X {\displaystyleY\inX} onehas f ( Y ) ∈ Y {\displaystylef(Y)\inY} .Sincetheexistenceofachoicefunctionwhen X {\displaystyleX} isafinitesetiseasilyprovedfromaxioms1–8,AConlymattersforcertaininfinitesets.ACischaracterizedasnonconstructivebecauseitassertstheexistenceofachoicesetbutsaysnothingabouthowthechoicesetistobe"constructed."Muchresearch[vague]hassoughttocharacterizethedefinability(orlackthereof)ofcertainsets[exampleneeded]whoseexistenceACasserts. Motivationviathecumulativehierarchy[edit] Furtherinformation:VonNeumannuniverse OnemotivationfortheZFCaxiomsisthecumulativehierarchyofsetsintroducedbyJohnvonNeumann.[8]Inthisviewpoint,theuniverseofsettheoryisbuiltupinstages,withonestageforeachordinalnumber.Atstage0therearenosetsyet.Ateachfollowingstage,asetisaddedtotheuniverseifallofitselementshavebeenaddedatpreviousstages.Thustheemptysetisaddedatstage1,andthesetcontainingtheemptysetisaddedatstage2.[9]Thecollectionofallsetsthatareobtainedinthisway,overallthestages,isknownasV.ThesetsinVcanbearrangedintoahierarchybyassigningtoeachsetthefirststageatwhichthatsetwasaddedtoV. ItisprovablethatasetisinVifandonlyifthesetispureandwell-founded;andprovablethatVsatisfiesalltheaxiomsofZFC,iftheclassofordinalshasappropriatereflectionproperties.Forexample,supposethatasetxisaddedatstageα,whichmeansthateveryelementofxwasaddedatastageearlierthanα.Theneverysubsetofxisalsoaddedatstageα,becauseallelementsofanysubsetofxwerealsoaddedbeforestageα.Thismeansthatanysubsetofxwhichtheaxiomofseparationcanconstructisaddedatstageα,andthatthepowersetofxwillbeaddedatthenextstageafterα.ForacompleteargumentthatVsatisfiesZFCseeShoenfield(1977). ThepictureoftheuniverseofsetsstratifiedintothecumulativehierarchyischaracteristicofZFCandrelatedaxiomaticsettheoriessuchasVonNeumann–Bernays–Gödelsettheory(oftencalledNBG)andMorse–Kelleysettheory.ThecumulativehierarchyisnotcompatiblewithothersettheoriessuchasNewFoundations. ItispossibletochangethedefinitionofVsothatateachstage,insteadofaddingallthesubsetsoftheunionofthepreviousstages,subsetsareonlyaddediftheyaredefinableinacertainsense.Thisresultsinamore"narrow"hierarchywhichgivestheconstructibleuniverseL,whichalsosatisfiesalltheaxiomsofZFC,includingtheaxiomofchoice.ItisindependentfromtheZFCaxiomswhetherV = L.AlthoughthestructureofLismoreregularandwellbehavedthanthatof V,fewmathematiciansarguethat V= LshouldbeaddedtoZFCasanadditional"axiomofconstructibility". Metamathematics[edit] Virtualclasses[edit] Thismainarticlemetamathematicsneedsadditionalcitationsforverification.Pleasehelpimprovethisarticlebyaddingcitationstoreliablesources.Unsourcedmaterialmaybechallengedandremoved.Findsources: "Zermelo–Fraenkelsettheory" – news ·newspapers ·books ·scholar ·JSTOR(March2019)(Learnhowandwhentoremovethistemplatemessage) Asnotedearlier,properclasses(collectionsofmathematicalobjectsdefinedbyapropertysharedbytheirmemberswhicharetoobigtobesets)canonlybetreatedindirectlyinZF(andthusZFC). AnalternativetoproperclasseswhilestayingwithinZFandZFCisthevirtualclassnotationalconstructintroducedbyQuine(1969),wheretheentireconstructy∈{x|Fx}issimplydefinedasFy.[10]Thisprovidesasimplenotationforclassesthatcancontainsetsbutneednotthemselvesbesets,whilenotcommittingtotheontologyofclasses(becausethenotationcanbesyntacticallyconvertedtoonethatonlyusessets).Quine'sapproachbuiltontheearlierapproachofBernays&Fraenkel(1958).VirtualclassesarealsousedinLevy(2002),Takeuti&Zaring(1982),andintheMetamathimplementationofZFC. VonNeumann–Bernays–Gödelsettheory[edit] Theaxiomschemataofreplacementandseparationeachcontaininfinitelymanyinstances.Montague(1961)includedaresultfirstprovedinhis1957Ph.D.thesis:ifZFCisconsistent,itisimpossibletoaxiomatizeZFCusingonlyfinitelymanyaxioms.Ontheotherhand,vonNeumann–Bernays–Gödelsettheory(NBG)canbefinitelyaxiomatized.TheontologyofNBGincludesproperclassesaswellassets;asetisanyclassthatcanbeamemberofanotherclass.NBGandZFCareequivalentsettheoriesinthesensethatanytheoremnotmentioningclassesandprovableinonetheorycanbeprovedintheother. Consistency[edit] Gödel'ssecondincompletenesstheoremsaysthatarecursivelyaxiomatizablesystemthatcaninterpretRobinsonarithmeticcanproveitsownconsistencyonlyifitisinconsistent.Moreover,Robinsonarithmeticcanbeinterpretedingeneralsettheory,asmallfragmentofZFC.HencetheconsistencyofZFCcannotbeprovedwithinZFCitself(unlessitisactuallyinconsistent).Thus,totheextentthatZFCisidentifiedwithordinarymathematics,theconsistencyofZFCcannotbedemonstratedinordinarymathematics.TheconsistencyofZFCdoesfollowfromtheexistenceofaweaklyinaccessiblecardinal,whichisunprovableinZFCifZFCisconsistent.Nevertheless,itisdeemedunlikelythatZFCharborsanunsuspectedcontradiction;itiswidelybelievedthatifZFCwereinconsistent,thatfactwouldhavebeenuncoveredbynow.Thismuchiscertain—ZFCisimmunetotheclassicparadoxesofnaivesettheory:Russell'sparadox,theBurali-Fortiparadox,andCantor'sparadox. Abian&LaMacchia(1978)studiedasubtheoryofZFCconsistingoftheaxiomsofextensionality,union,powerset,replacement,andchoice.Usingmodels,theyprovedthissubtheoryconsistent,andprovedthateachoftheaxiomsofextensionality,replacement,andpowersetisindependentofthefourremainingaxiomsofthissubtheory.Ifthissubtheoryisaugmentedwiththeaxiomofinfinity,eachoftheaxiomsofunion,choice,andinfinityisindependentofthefiveremainingaxioms.Becausetherearenon-well-foundedmodelsthatsatisfyeachaxiomofZFCexcepttheaxiomofregularity,thataxiomisindependentoftheotherZFCaxioms. Ifconsistent,ZFCcannotprovetheexistenceoftheinaccessiblecardinalsthatcategorytheoryrequires.HugesetsofthisnaturearepossibleifZFisaugmentedwithTarski'saxiom.[11]Assumingthataxiomturnstheaxiomsofinfinity,powerset,andchoice(7 – 9above)intotheorems. Independence[edit] ManyimportantstatementsareindependentofZFC(seelistofstatementsindependentofZFC).Theindependenceisusuallyprovedbyforcing,wherebyitisshownthateverycountabletransitivemodelofZFC(sometimesaugmentedwithlargecardinalaxioms)canbeexpandedtosatisfythestatementinquestion.Adifferentexpansionisthenshowntosatisfythenegationofthestatement.Anindependenceproofbyforcingautomaticallyprovesindependencefromarithmeticalstatements,otherconcretestatements,andlargecardinalaxioms.SomestatementsindependentofZFCcanbeproventoholdinparticularinnermodels,suchasintheconstructibleuniverse.However,somestatementsthataretrueaboutconstructiblesetsarenotconsistentwithhypothesizedlargecardinalaxioms. ForcingprovesthatthefollowingstatementsareindependentofZFC: Continuumhypothesis Diamondprinciple Suslinhypothesis Martin'saxiom(whichisnotaZFCaxiom) AxiomofConstructibility(V=L)(whichisalsonotaZFCaxiom). Remarks: TheconsistencyofV=Lisprovablebyinnermodelsbutnotforcing:everymodelofZFcanbetrimmedtobecomeamodelofZFC+V=L. TheDiamondPrincipleimpliestheContinuumHypothesisandthenegationoftheSuslinHypothesis. Martin'saxiomplusthenegationoftheContinuumHypothesisimpliestheSuslinHypothesis. TheconstructibleuniversesatisfiestheGeneralizedContinuumHypothesis,theDiamondPrinciple,Martin'sAxiomandtheKurepaHypothesis. ThefailureoftheKurepahypothesisisequiconsistentwiththeexistenceofastronglyinaccessiblecardinal. Avariationonthemethodofforcingcanalsobeusedtodemonstratetheconsistencyandunprovabilityoftheaxiomofchoice,i.e.,thattheaxiomofchoiceisindependentofZF.Theconsistencyofchoicecanbe(relatively)easilyverifiedbyprovingthattheinnermodelLsatisfieschoice.(ThuseverymodelofZFcontainsasubmodelofZFC,sothatCon(ZF)impliesCon(ZFC).)Sinceforcingpreserveschoice,wecannotdirectlyproduceamodelcontradictingchoicefromamodelsatisfyingchoice.However,wecanuseforcingtocreateamodelwhichcontainsasuitablesubmodel,namelyonesatisfyingZFbutnotC. Anothermethodofprovingindependenceresults,oneowingnothingtoforcing,isbasedonGödel'ssecondincompletenesstheorem.Thisapproachemploysthestatementwhoseindependenceisbeingexamined,toprovetheexistenceofasetmodelofZFC,inwhichcaseCon(ZFC)istrue.SinceZFCsatisfiestheconditionsofGödel'ssecondtheorem,theconsistencyofZFCisunprovableinZFC(providedthatZFCis,infact,consistent).HencenostatementallowingsuchaproofcanbeprovedinZFC.ThismethodcanprovethattheexistenceoflargecardinalsisnotprovableinZFC,butcannotprovethatassumingsuchcardinals,givenZFC,isfreeofcontradiction. Proposedadditions[edit] TheprojecttounifysettheoristsbehindadditionalaxiomstoresolvetheContinuumHypothesisorothermeta-mathematicalambiguitiesissometimesknownas"Gödel'sprogram".[12]Mathematicianscurrentlydebatewhichaxiomsarethemostplausibleor"self-evident",whichaxiomsarethemostusefulinvariousdomains,andabouttowhatdegreeusefulnessshouldbetradedoffwithplausibility;some"multiverse"settheoristsarguethatusefulnessshouldbethesoleultimatecriterioninwhichaxiomstocustomarilyadopt.Oneschoolofthoughtleansonexpandingthe"iterative"conceptofasettoproduceaset-theoreticuniversewithaninterestingandcomplexbutreasonablytractablestructurebyadoptingforcingaxioms;anotherschooladvocatesforatidier,lesscluttereduniverse,perhapsfocusedona"core"innermodel.[13] Criticisms[edit] Forcriticismofsettheoryingeneral,seeObjectionstosettheory ZFChasbeencriticizedbothforbeingexcessivelystrongandforbeingexcessivelyweak,aswellasforitsfailuretocaptureobjectssuchasproperclassesandtheuniversalset. ManymathematicaltheoremscanbeproveninmuchweakersystemsthanZFC,suchasPeanoarithmeticandsecond-orderarithmetic(asexploredbytheprogramofreversemathematics).SaundersMacLaneandSolomonFefermanhavebothmadethispoint.Someof"mainstreammathematics"(mathematicsnotdirectlyconnectedwithaxiomaticsettheory)isbeyondPeanoarithmeticandsecond-orderarithmetic,butstill,allsuchmathematicscanbecarriedoutinZC(Zermelosettheorywithchoice),anothertheoryweakerthanZFC.MuchofthepowerofZFC,includingtheaxiomofregularityandtheaxiomschemaofreplacement,isincludedprimarilytofacilitatethestudyofthesettheoryitself. Ontheotherhand,amongaxiomaticsettheories,ZFCiscomparativelyweak.UnlikeNewFoundations,ZFCdoesnotadmittheexistenceofauniversalset.HencetheuniverseofsetsunderZFCisnotclosedundertheelementaryoperationsofthealgebraofsets.UnlikevonNeumann–Bernays–Gödelsettheory(NBG)andMorse–Kelleysettheory(MK),ZFCdoesnotadmittheexistenceofproperclasses.AfurthercomparativeweaknessofZFCisthattheaxiomofchoiceincludedinZFCisweakerthantheaxiomofglobalchoiceincludedinNBGandMK. TherearenumerousmathematicalstatementsindependentofZFC.Theseincludethecontinuumhypothesis,theWhiteheadproblem,andthenormalMoorespaceconjecture.SomeoftheseconjecturesareprovablewiththeadditionofaxiomssuchasMartin'saxiomorlargecardinalaxiomstoZFC.SomeothersaredecidedinZF+ADwhereADistheaxiomofdeterminacy,astrongsuppositionincompatiblewithchoice.OneattractionoflargecardinalaxiomsisthattheyenablemanyresultsfromZF+ADtobeestablishedinZFCadjoinedbysomelargecardinalaxiom(seeprojectivedeterminacy).TheMizarsystemandMetamathhaveadoptedTarski–Grothendiecksettheory,anextensionofZFC,sothatproofsinvolvingGrothendieckuniverses(encounteredincategorytheoryandalgebraicgeometry)canbeformalized. Seealso[edit] Foundationsofmathematics Innermodel Largecardinalaxiom Relatedaxiomaticsettheories: Morse–Kelleysettheory VonNeumann–Bernays–Gödelsettheory Tarski–Grothendiecksettheory Constructivesettheory Internalsettheory Notes[edit] ^Ciesielski1997."Zermelo-Fraenkelaxioms(abbreviatedasZFCwhereCstandsfortheaxiomofChoice" ^Ebbinghaus2007,p. 136. ^Halbeisen2011,pp. 62–63. ^Kunen(1980,p. 10). ^Hatcher1982,p. 138,def. 1. ^Fraenkel,Bar-Hillel&Lévy1973. ^Shoenfield2001,p. 239. ^Shoenfield1977,section 2. ^Hinman2005,p. 467. ^(Link2014) ^Tarski1939. ^Feferman1996. ^Wolchover2013. Workscited[edit] Abian,Alexander(1965).TheTheoryofSetsandTransfiniteArithmetic.WBSaunders. ———;LaMacchia,Samuel(1978)."OntheConsistencyandIndependenceofSomeSet-TheoreticalAxioms".NotreDameJournalofFormalLogic.19:155–58.doi:10.1305/ndjfl/1093888220. Bernays,Paul;Fraenkel,A.A.(1958).AxiomaticSetTheory.Amsterdam:NorthHolland. Ciesielski,Krzysztof(1997).SetTheoryfortheWorkingMathematician.CambridgeUniversityPress.p. 4.ISBN 0-521-59441-3. Devlin,Keith(1996)[Firstpublished1984].TheJoyofSets.Springer. Ebbinghaus,Heinz-Dieter(2007).ErnstZermelo:AnApproachtoHisLifeandWork.Springer.ISBN 978-3-540-49551-2. Feferman,Solomon(1996)."Gödel'sprogramfornewaxioms:why,where,howandwhat?".InHájek,Petr(ed.).Gödel'96:Logicalfoundationsofmathematics,computerscienceandphysics–KurtGödel'slegacy.Springer-Verlag.pp. 3–22.ISBN 3-540-61434-6.. Fraenkel,Abraham;Bar-Hillel,Yehoshua;Lévy,Azriel(1973)[Firstpublished1958].FoundationsofSetTheory.North-Holland.Fraenkel'sfinalwordonZFandZFC. Halbeisen,LorenzJ.(2011).CombinatorialSetTheory:WithaGentleIntroductiontoForcing.Springer.pp. 62–63.ISBN 978-1-4471-2172-5. Hatcher,William(1982)[Firstpublished1968].TheLogicalFoundationsofMathematics.PergamonPress. vanHeijenoort,Jean(1967).FromFregetoGödel:ASourceBookinMathematicalLogic,1879–1931.HarvardUniversityPress.IncludesannotatedEnglishtranslationsoftheclassicarticlesbyZermelo,Fraenkel,andSkolembearingonZFC. Hinman,Peter(2005).FundamentalsofMathematicalLogic.AKPeters.ISBN 978-1-56881-262-5. Jech,Thomas(2003).SetTheory:TheThirdMillenniumEdition,RevisedandExpanded.Springer.ISBN 3-540-44085-2. Kunen,Kenneth(1980).SetTheory:AnIntroductiontoIndependenceProofs.Elsevier.ISBN 0-444-86839-9. Levy,Azriel(2002).BasicSetTheory.DoverPublications.ISBN 048642079-5. Link,Godehard(2014).FormalismandBeyond:OntheNatureofMathematicalDiscourse.WalterdeGruyterGmbH&CoKG.ISBN 978-1-61451-829-7. Montague,Richard(1961)."Semanticalclosureandnon-finiteaxiomatizability".InfinisticMethods.London:PergamonPress.pp. 45–69. Quine,WillardvanOrman(1969).SetTheoryandItsLogic(Revised ed.).Cambridge,MassachusettsandLondon,England:TheBelknapPressofHarvardUniversityPress.ISBN 0-674-80207-1. Shoenfield,JosephR.(1977)."Axiomsofsettheory".InBarwise,K.J.(ed.).HandbookofMathematicalLogic.ISBN 0-7204-2285-X. Shoenfield,JosephR.(2001)[Firstpublished1967].MathematicalLogic(2nd ed.).AKPeters.ISBN 978-1-56881-135-2. Suppes,Patrick(1972)[Firstpublished1960].AxiomaticSetTheory.Doverreprint.PerhapsthebestexpositionofZFCbeforetheindependenceofACandtheContinuumhypothesis,andtheemergenceoflargecardinals.Includesmanytheorems. Takeuti,Gaisi;Zaring,WM(1971).IntroductiontoAxiomaticSetTheory.Springer-Verlag. Takeuti,Gaisi;Zaring,WM(1982).IntroductiontoAxiomaticSetTheory. Tarski,Alfred(1939)."Onwell-orderedsubsetsofanyset".FundamentaMathematicae.32:176–83.doi:10.4064/fm-32-1-176-783. Tiles,Mary(1989).ThePhilosophyofSetTheory.Doverreprint. Tourlakis,George(2003).LecturesinLogicandSetTheory,Vol.2.CambridgeUniversityPress. Wolchover,Natalie(2013)."ToSettleInfinityDispute,aNewLawofLogic".QuantaMagazine.. Zermelo,Ernst(1908)."UntersuchungenüberdieGrundlagenderMengenlehreI".MathematischeAnnalen.65:261–281.doi:10.1007/BF01449999.S2CID 120085563.EnglishtranslationinHeijenoort,Jeanvan(1967)."Investigationsinthefoundationsofsettheory".FromFregetoGödel:ASourceBookinMathematicalLogic,1879–1931.SourceBooksintheHistoryoftheSciences.HarvardUniversityPress.pp. 199–215.ISBN 978-0-674-32449-7. Zermelo,Ernst(1930)."ÜberGrenzzahlenundMengenbereiche".FundamentaMathematicae.16:29–47.doi:10.4064/fm-16-1-29-47.ISSN 0016-2736. Externallinks[edit] "ZFC",EncyclopediaofMathematics,EMSPress,2001[1994] StanfordEncyclopediaofPhilosophyarticlesbyThomasJech: SetTheory; AxiomsofZermelo–FraenkelSetTheory. MetamathversionoftheZFCaxioms—Aconciseandnonredundantaxiomatization.Thebackgroundfirstorderlogicisdefinedespeciallytofacilitatemachineverificationofproofs. AderivationinMetamathofaversionoftheseparationschemafromaversionofthereplacementschema. Weisstein,EricW."Zermelo-FraenkelSetTheory".MathWorld. vteSettheoryOverview Set(mathematics) Axioms Adjunction Choice countable dependent global Constructibility(V=L) Determinacy Extensionality Infinity Limitationofsize Pairing Powerset Regularity Union Martin'saxiom Axiomschema replacement specification Operations Cartesianproduct Complement DeMorgan'slaws Disjointunion Intersection Powerset Setdifference Symmetricdifference Union ConceptsMethods Cardinality Cardinalnumber (large) Class Constructibleuniverse Continuumhypothesis Diagonalargument Element orderedpair tuple Family Forcing One-to-onecorrespondence Ordinalnumber Transfiniteinduction Venndiagram Settypes Amorphous Countable Empty Finite (hereditarily) Fuzzy Infinite(Dedekind-infinite) Recursive Singleton Subset ·Superset Transitive Uncountable Universal Theories Alternative Axiomatic Naive Cantor'stheorem Zermelo General PrincipiaMathematica NewFoundations Zermelo–Fraenkel vonNeumann–Bernays–Gödel Morse–Kelley Kripke–Platek Tarski–Grothendieck ParadoxesProblems Russell'sparadox Suslin'sproblem Burali-Fortiparadox Settheorists AbrahamFraenkel BertrandRussell ErnstZermelo GeorgCantor JohnvonNeumann KurtGödel PaulBernays PaulCohen RichardDedekind ThomasJech ThoralfSkolem WillardQuine vteMathematicallogicGeneral Formallanguage Formationrule Formalproof Formalsemantics Well-formedformula Set Element Class Classicallogic Axiom Ruleofinference Relation Theorem Logicalconsequence Typetheory Symbol Syntax Theory Systems Formalsystem Deductivesystem Axiomaticsystem Hilbertstylesystems Naturaldeduction Sequentcalculus Traditionallogic Proposition Inference Argument Validity Syllogism Squareofopposition Venndiagram PropositionalcalculusandBooleanlogic Booleanfunctions Propositionalcalculus Propositionalformula Logicalconnectives Truthtables Many-valuedlogic Predicatelogic First-order Quantifiers Predicate Second-order Monadicpredicatecalculus Naivesettheory Set Emptyset Element Enumeration Extensionality Finiteset Infiniteset Subset Powerset Countableset Uncountableset Recursiveset Domain Codomain Image Map Function Relation Orderedpair Settheory Foundationsofmathematics Zermelo–Fraenkelsettheory Axiomofchoice Generalsettheory Kripke–Plateksettheory VonNeumann–Bernays–Gödelsettheory Morse–Kelleysettheory Tarski–Grothendiecksettheory Modeltheory Model Interpretation Non-standardmodel Finitemodeltheory Strength Truthvalue Validity Prooftheory Formalproof Deductivesystem Formalsystem Theorem Logicalconsequence Ruleofinference Syntax Computabilitytheory Recursion Computableset Computablyenumerable Decisionproblem Church–Turingthesis Computablefunction Primitiverecursivefunction Retrievedfrom"https://en.wikipedia.org/w/index.php?title=Zermelo–Fraenkel_set_theory&oldid=1061543627" Categories:FoundationsofmathematicsSystemsofsettheoryZnotationHiddencategories:ArticleswithshortdescriptionShortdescriptionisdifferentfromWikidataWikipediaarticlesneedingclarificationfromSeptember2021AllWikipediaarticlesneedingclarificationWikipediaarticlesneedingclarificationfromNovember2018AllarticlesneedingexamplesArticlesneedingexamplesfromNovember2018ArticlesneedingadditionalreferencesfromMarch2019Allarticlesneedingadditionalreferences Navigationmenu Personaltools NotloggedinTalkContributionsCreateaccountLogin Namespaces ArticleTalk Variants expanded collapsed Views ReadEditViewhistory More expanded collapsed Search Navigation MainpageContentsCurrenteventsRandomarticleAboutWikipediaContactusDonate Contribute HelpLearntoeditCommunityportalRecentchangesUploadfile Tools WhatlinkshereRelatedchangesUploadfileSpecialpagesPermanentlinkPageinformationCitethispageWikidataitem Print/export DownloadasPDFPrintableversion Languages AlemannischالعربيةBân-lâm-gúCatalàČeštinaCymraegDanskDeutschEestiEspañolFrançais한국어HrvatskiItalianoLatinaLietuviųNederlandsPolskiPortuguêsRomânăРусскийSimpleEnglishСрпски/srpskiSvenskaTürkçeУкраїнськаTiếngViệt粵語中文 Editlinks