ZFC - Encyclopedia of Mathematics

ZFC is the acronym for Zermelo–Fraenkel set theory with the axiom of choice, formulated in first-order logic. ZFC is the basic axiom system for ...   Login www.springer.com TheEuropeanMathematicalSociety Navigation Mainpage PagesA-Z StatProbCollection Recentchanges Currentevents Randompage Help Projecttalk Requestaccount Tools Whatlinkshere Relatedchanges Specialpages Printableversion Permanentlink Pageinformation Namespaces Page Discussion Variants Views View Viewsource History Actions ZFC FromEncyclopediaofMathematics Jumpto:navigation, search Zermelo–Fraenkelsettheorywiththeaxiomofchoice ZFCistheacronymforZermelo–Fraenkelsettheorywiththeaxiomofchoice,formulatedinfirst-orderlogic.ZFCisthebasicaxiomsystemformodern(2000)settheory,regardedbothasafieldofmathematicalresearchandasafoundationforongoingmathematics(cf.alsoAxiomaticsettheory).SettheoryemergedfromtheresearchesofG.CantorintothetransfinitenumbersandhiscontinuumhypothesisandofR.Dedekindinhisincisiveanalysisofnaturalnumbers(see[a5]or[a10]).E.Zermelo[a20]in1908,undertheinfluenceofD.HilbertatGöttingen,providedthefirstfull-fledgedaxiomatizationofsettheory,fromwhichZFCinlargepartderives.Althoughseveralaxiomsystemswerelaterproposed,ZFCbecamegenerallyadoptedbythe1960{}sbecauseofitsschematicsimplicityandopen-endednessincodifyingtheminimallynecessarysetexistenceprinciplesneededandisnow(asof2000)regardedasthebasicframeworkontowhichfurtheraxiomscanbeadjoinedandinvestigated.AmodernpresentationofZFCfollows. Thelanguageofsettheoryisfirst-orderlogicwithabinarypredicatesymbol$\in$formembership("first-order"referstoquantificationonlyoverindividuals,note.g.properties).Thislanguagehasassymbolsaninfinitestoreofvariables;logicalconnectives($\neg$for"not",$\vee$for"or",$\wedge$for"and",$\rightarrow$for"implies",and$\leftrightarrow$for"isequivalentto");quantifiers($\forall$for"forall"and$\exists$for"thereexists");twobinarypredicatesymbols,$=$and$\in$;andparentheses.(Amoreparsimoniouspresentationispossible,e.g.onecandowithjust$\neg$,$\vee$and$\forall$,andleaveoutparentheseswithadifferentsyntax.)Theformulasofthelanguagearegeneratedasfollows:$x=y$and$x\iny$are(theatomic)formulaswhenever$x$and$y$arevariables.If$\varphi$and$\psi$areformulas,thensoare$(\neg\varphi)$,$(\varphi\vee\psi)$,$(\varphi\wedge\psi)$,$(\varphi\rightarrow\psi)$,$(\varphi\leftrightarrow\psi)$,$\forallx\varphi$,and$\existsx\varphi$,whenever$x$isavariable.Thevariousfurthernotationscanberegardedasabbreviations;forexample,$x\subseteqy$for"xisasubsetofy"abbreviates$\forallz(z\inx\rightarrowz\iny)$. TheaxiomsofZFCareasfollows,withsomehistoricalandnotationalcommentary. A1)Axiomofextensionality: \begin{equation*}\forallx\forally(\forallz(z\inx\leftrightarrowz\iny)\rightarrowx=y).\end{equation*} Thisisafundamentalprincipleofsets,thatsetsaretobedeterminedsolelybytheirmembers.Thearrow""canbereplacedby""sincetheotherdirectionisimmediate.Indeed,theaxiomcanthenbetakentobeameansofintroducing$=$itselfasanabbreviation,asasymboldefinedintermsof$\in$.Theterm"extensionality"stemsfromatraditionalphilosophicaldistinctionbetweentheintensionandtheextensionofaterm,wherelooselyspeakingtheextensionofatermisthecollectionofthingsofwhichthetermistrueof,andtheintensionissomemoreintrinsicsenseoftheterm.AclearstatementoftheprincipleofextensionalityhadalreadyappearedinthepioneeringworkofDedekind[a3],whichprovidedadevelopmentofthenaturalnumbersinset-theoretictermsandanticipatedZermelo'saxiomatic,abstractapproachtosettheory.Cf.alsoAxiomofextensionality. A2)Axiomoftheemptyset: \begin{equation*}\existsx\forally(\negy\inx).\end{equation*} Thisaxiomassertstheexistenceofanemptyset;byA1),suchasetisunique,andisdenotedbytheterm$\emptyset$.Termsaresimilarlyintroducedinconnectionwithotheraxiomsbelow,andingeneralsuchtermscanbeeliminatedinfavouroftheirdefinitions;forexample,$\emptyset\inz$canberegardedasanabbreviationfor$\existsx(\forally(\negy\inx)\wedgex\inz)$. A3)Axiomofpairs: \begin{equation*}\forallx\forally\existsz\forallv(v\inz\leftrightarrow(v=x\veev=y)).\end{equation*} Thisaxiomasserts,foranysets$x$and$y$,theexistenceoftheir(unordered)pair,thesetconsistingexactlyof$x$and$y$.Thissetisdenotedby$\{x,y\}$.A3)implies,takingits$y$tobe$x$,thatforanyset$x$thereisasetconsistingsolelyof$x$,denotedby$\{x\}$. Theexistenceof$\emptyset$andthedistinctionbetweenaset$x$andthesingle-membered$\{x\}$werenotclearlydelineatedintheearlydevelopmentofsettheory,andequivocationsinthesedirectionscanbefound,e.g.,in[a3]. A4)Axiomofunion: \begin{equation*}\forallx\existsz\forallv(v\inz\leftrightarrow\existsy(y\inx\bigwedgev\iny)).\end{equation*} Thisaxiomasserts,foranyset$x$,theexistenceofits(generalized)union,thesetconsistingexactlyofthemembersofmembersof$x$.Thisunionisdenotedby$\cupx$.Notethatfortwosets$a$and$b$,$\cup\{a,b\}$istheusualunion$a\cupb$. A5)Axiomofpowerset: \begin{equation*}\forallx\existsz\forallv(v\inz\leftrightarrow\forallw(w\inv\rightarroww\inx)).\end{equation*} Thisaxiomasserts,foranyset$x$,theexistenceofitspowerset,thesetconsistingexactlyofthosesets$v$thataresubsetsof$x$.Thispowersetisdenotedby$\mathcal{P}(x)$.TheaxiomsA3)–A5)aregenerativeaxioms,providingvariousmeansofcollectingsetstogethertoformnewsets.ThegenerativeprocesscanbestartedwithA2),anoutrightexistenceaxiom.Thenextaxiomisanotheroutrightexistenceaxiom,whichforconvenienceisstatedviatermsdefinedabove: A6)Axiomofinfinity: \begin{equation*}\existsx(\emptyset\inx\bigwedge\forally(y\inx\rightarrowy\bigcup\{y\}\inx)).\end{equation*} Amongvariouspossibleapproaches,thisaxiomassertstheexistenceofaninfinitesetofaspecifickind:thesetcontainstheemptysetandismoreoverclosedinthesensethatwhenever$y$isintheset,soalsois$y\cup\{y\}$.Hence,$\emptyset$,$\{\emptyset\}$,$\{\emptyset,\{\emptyset\}\}$,$\{\emptyset,\{\emptyset\},\{\emptyset,\{\emptyset\}\}\},\dots$aretobemembers;theseareindeedsetsbyA2)andA3)andaremoreoverdistinctfromeachotherbyA1).Zermelohimselfhad$\{y\}$inplaceof$y\cup\{y\}$,butthemodernformulationderivesfromtheformulationbyJ.vonNeumann[a16]oftheordinalnumberswithinsettheory(cf.alsoOrdinalnumber).Dedekind[a3]had(in)famously"proved"theexistenceofaninfiniteset;Zermelowasfirsttoseetheneedtopostulatetheexistenceofaninfiniteset.InthepresenceofA6),A5)becomesamuchmorepowerfulaxiom,purportlycollectingtogetherinonesetallarbitrarysubsetsofaninfiniteset;Cantorfamouslyestablishedthatnosetisinbijectivecorrespondencewithitspowerset,andthisleadstoaninfiniterangeoftransfinitecardinalities(cf.alsoTransfinitenumber). A7)Axiomofchoice: \begin{equation*}\forallx:\end{equation*} \begin{equation*}\existsy\forallv((v\inx\bigwedge(\negv=\emptyset))\rightarrow\existss\forallt((t\inv\bigwedget\iny)\leftrightarrows=t)).\end{equation*} ThisisoneofthemostcrucialaxiomsofZermelo'saxiomatization[a20](cf.alsoAxiomofchoice).Tounravelit,thehypothesisassertsthat$x$consistsofpairwisedisjointsets,andtheconclusion,thatthereisaset$y$thatwitheachnon-emptymemberof$x$hasexactlyonecommonmember.Thus,$y$servesasa"selector"ofelementsfrommembersof$x$.A7)isusuallystatedintermsoffunctions:Thetheoryoffunctions,construedassetsoforderedpairswiththeunivalentpropertyonthesecondcoordinate,isfirstdevelopedwiththepreviousaxioms.ThenA7)hasanequivalentformulationas:Everysethasachoicefunction,i.e.afunction$f$whosedomainisthesetandsuchthatforeachnon-emptymember$y$oftheset,$f(y)\iny$. Zermelo[a18]formulatedA7)andwithit,establishedhisfamouswell-orderingtheorem:Everysetcanbewell-ordered(cf.alsoZermelotheorem).Zermelomaintainedthattheaxiomofchoiceisa"logicalprinciple"which"isappliedwithouthesitationeverywhereinmathematicaldeduction".However,Zermelo'saxiomandresultgeneratedconsiderablecriticismbecauseofthepositingofarbitraryfunctionsfollowingnoparticularrulegoverningthepassagefromargumenttovalue.Sincethen,ofcourse,theaxiomhasbecomedeeplyembeddedinmathematics,assumingacentralroleinitsequivalentformulationasZorn'slemma(cf.alsoZornlemma).Inresponsetocritics,Zermelo[a19]publishedasecondproofofhiswell-orderingtheorem,anditwasinlargeparttobuttressthisproofthathepublished[a20]hisaxiomatization,makingexplicittheunderlyingset-existenceassumptionsused(see[a13]). A8)Axiom(schema)ofseparation:Foranyformula$\varphi$withunquantifiedvariablesamong$v,v_{1},\dots,v_{n}$, \begin{equation*}\forallx\forallv_{1}\ldots\forallv_{n}\existsy\forallv(v\iny\leftrightarrow(v\inx\bigwedge\varphi)).\end{equation*} ThisisanothercrucialcomponentofZermelo'saxiomatization[a20].Actually,itisaninfinitepackageofaxioms,oneforeachformula$\varphi$,positingforanyset$x$theexistenceofasubset$y$consistingofthosemembersof$x$"separated"outaccordingto$\varphi$.Zermelowasawareoftheparadoxesoflogicemergingatthetime,andhehimselfhadfoundthefamousRussellparadoxindependently(cf.alsoParadox;Antinomy).Russell'sparadoxresultsfrom"fullcomprehension",theallowingofanycollectionofsetssatisfyingapropertytobeaset:Considertheproperty$(\negy\iny)$;iftherewereaset$R$consistingexactlyofthose$y$satisfyingthisproperty,onewouldhavethecontradiction$(R\inR\leftrightarrow(\negR\inR))$.Zermelosawthatifoneonlyallowedcollectionsofsetssatisfyingaproperty"anddrawnfromagivenset"tobeaset,thentherearenoapparentcontradictions.ThuswasZermeloabletoretain,inanadequatewayasithasturnedout,theimportantcapabilityofgeneratingsetscorrespondingtoproperties.Thefirsttheoremin[a20]appliesA8)togetherwiththeRussellparadoxargumenttoassertthattheuniverseofsets(cf.alsoUniverse)isnotitselfaset. Zermelo'sversionofA8)retainedanintensionalaspect,withhis$\varphi$beingsome"definite"propertydeterminateforany$y\inx$whetherthepropertyistrueof$y$ornot.However,thisbecameunsatisfactoryinthedevelopmentofsettheory,andeventuallythesuggestionofT.Skolem[a14]oftakingZermelo'sdefinitepropertiesasthoseexpressibleinfirst-orderlogicwasadopted,yieldingA8).Generallyspeaking,logicloomedlargeintheformalizationofmathematicsattheturnintothetwentiethcentury,atthetimeofG.FregeandB.Russell,butinthesucceedingdecadestherewasasteadydilutionofwhatwasconsideredtobelogicalinmathematics.Manynotionscametobeconsidereddistinctlyset-theoreticratherthanlogical,andwhatwasretainedoflogicinmathematicswasfirst-orderlogic. A9)Axiom(schema)ofreplacement:Foranyformula$\varphi$intwounquantifiedvariables$v$and$w$, \begin{equation*}\forallv\existsu(\forallw\varphi\leftrightarrowu=w)\end{equation*} \begin{equation*}\downarrow\forallx\existsy\forallw(w\iny\leftrightarrow\existsv(v\inx\bigwedge\varphi)).\end{equation*} Thisalsoisaninfinitepackageofaxioms,oneforeach$\varphi$.Tounravelit,thehypothesisassertsthat$\varphi$is"functional"inthesensethattoeachset$v$thereisauniquecorrespondingset$u$satisfying$\varphi$,andtheconclusion,thatforanyset$x$thereisaset$y$servingasthe"imageofxunderv".Inshort,foranydefinablefunctioncorrespondenceandanyset,theimageofthatsetunderthecorrespondenceisalsoaset. A9)wasnotpartofZermelo'soriginalaxiomatization[a20],andtomeetitsinadequaciesforgeneratingcertainkindsofsets,A.Fraenkel[a6]andSkolem[a14]independentlyproposedadjoiningA9).Becauseofhistoricalcircumstance,itwasFraenkelwhoseinitialbecamepartoftheacronymZFC.However,itwasVonNeumann'sincorporation[a17]ofamethodintosettheory,transfiniterecursion,thatnecessitatedthefullexerciseofA9).Inparticular,he[a16]defined(whatarenowcalledthevonNeumann)ordinalswithinsettheorytocorrespondtoCantor'soriginal,abstractordinalnumbers,andA9)isneededtoestablishthateverywell-orderedsetisorder-isomorphictoanordinal.Byasimpleargument,A9)impliesA8). A10)Axiomoffoundation: \begin{equation*}\forallx((\negx=\emptyset)\rightarrow\existsy(y\inx\bigwedge\forallz(z\inx\rightarrow\negz\iny))).\end{equation*} Thisassertsthateverynon-emptyset$x$iswell-founded,i.e.hasa"minimal"member$y$intermsof$\in$. A10)alsowasnotpartofZermelo'saxiomatization[a20],butappearedinhisfinalaxiomatization[a21].A10)isanelegantformoftheassertionthattheformaluniverse$V$ofsetsisstratifiedintoacumulativehierarchy:Theaxiomisequivalenttotheassertionthat$V$islayeredintosets$V_{\alpha}$for(vonNeumann)ordinals$\alpha$,where: \begin{equation*}V_{0}=\emptyset;V_{\alpha}=\bigcup_{\beta