- Zermelo–Fraenkel set theory
**Zermelo–Fraenkel set theory, with the axiom of choice**, commonly abbreviated**ZFC**, is the standard form ofaxiomatic set theory and as such is the most common foundation of mathematics.ZFC consists of a single primitive ontological notion, that of set, and a single ontological assumption, namely that all

individual s in theuniverse of discourse (i.e., all mathematical objects) are sets. There is a single primitivebinary relation , set membership; that set "a" is a member of set "b" is written $a\; in\; b$ (usually read "a" is an element of "b" or "a" is in "b"). ZFC is a one-sortedfirst-order theory ; hence the background logic isfirst-order logic . The axioms of ZFC govern how sets behave and interact.**History**In 1908,

Ernst Zermelo proposed the firstaxiomatic set theory ,Zermelo set theory . This axiomatic theory did not allow the construction of theordinal number s; while most of "ordinary mathematics" can be developed without ever using ordinals, ordinals are an essential tool in most set-theoretic investigations. Moreover, one of Zermelo's axioms invoked a concept, that of a "definite" property, whose operational meaning was not clear. In 1922,Abraham Fraenkel andThoralf Skolem independently proposed operationalizing a "definite" property as one that could be formulated as a first order theory whoseatomic formula s were limited to set membership and identity. They also independently proposed replacing theaxiom schema of specification with theaxiom schema of replacement . Appending this schema, as well as theaxiom of regularity (proposed by Zermelo in 1930), to Zermelo set theory yields the theory denoted by**ZF**. Adding to ZF either theaxiom of choice (AC) or a statement equivalent thereto, yields ZFC.**The axioms**There are many equivalent formulations of the ZFC axioms; for a rich but somewhat dated discussion of this fact, see Fraenkel "et al." (1973). The following particular axiom set is from Kunen (1980). The axioms per se are expressed in the symbolism of

first order logic . The associated English prose is only intended to aid the intuition.All formulations of ZFC imply that at least one set exists. Kunen includes an axiom, in addition to the following, which directly asserts the existence of a set. Many authors require a nonempty

domain of discourse as part of the semantics of the first-order logic in which ZFC is formalized. The axiom of infinity (below) also asserts that at least one set exists, as it begins with an existential quantifier.**1.**Two sets are equal (are the same set) if they have the same elements.:$forall\; x\; forall\; y\; [\; forall\; z\; (z\; in\; x\; Leftrightarrow\; z\; in\; y)\; Rightarrow\; x\; =\; y]\; .$The converse of this axiom follows from the substitution property of equality. If the background logic does not include equality "=", "x"="y" may be defined as abbreviating ∀"z" ["z"∈"x"↔"z"∈"y"] ∧ ∀"z" ["x"∈"z"↔"y"∈"z"] , [Axiom of extensionality :*Hatcher (1982), p. 138, Def. 1.*] in which case this axiom can be reformulated as $forall\; x\; forall\; y\; [\; forall\; z\; (z\; in\; x\; Leftrightarrow\; z\; in\; y)\; Rightarrow\; forall\; z\; (x\; in\; z\; Leftrightarrow\; y\; in\; z)\; ]$ — if "x" and "y" have the same elements, then they belong to the same sets (Fraenkel "et al." 1973).**2.**(also called the "Axiom of foundation"): Every non-empty set "x" contains a member "y" such that "x" and "y" areAxiom of regularity disjoint sets .:$forall\; x\; [\; exists\; y\; (\; y\; in\; x)\; Rightarrow\; exists\; y\; (\; y\; in\; x\; land\; lnot\; exists\; z\; (z\; in\; y\; land\; z\; in\; x))]\; .$**3.**(also called the axiom schema of "separation" or of "restricted comprehension"): If "z" is a set, and $phi!$ is any property which may characterize the elements "x" of "z", then there is a subset "y" of "z" containing those "x" in "z" which satisfy the property. The "restriction" to "z" is necessary to avoidAxiom schema of specification Russell's paradox and its variants. More formally, let $phi!$ be any formula in the language of ZFC with free variables among $x,z,w\_1,ldots,w\_n!$. So "y" is not free in $phi!$. Then::$forall\; z\; forall\; w\_1\; ldots\; w\_n\; exists\; y\; forall\; x\; [x\; in\; y\; Leftrightarrow\; (\; x\; in\; z\; land\; phi\; )]\; .$This axiom is part of Z, but can be redundant in ZF, in that it may follow from theaxiom schema of replacement , with (as here) or without theaxiom of the empty set . [*See [*]*http://us.metamath.org/mpegif/axsep.html here*] for a Metamath derivation of a version of the separation schema from a version of the replacement schema.The axiom of specification can be used to prove the existence of the

empty set , denoted $varnothing$, once the existence of at least one set is established (see above). A common way to do this is to use an instance of specification for a property which all sets do not have. For example, if "w" is a set which already exists, the empty set can be constructed as:$varnothing\; =\; \{u\; in\; w\; mid\; (u\; in\; u)\; land\; lnot\; (u\; in\; u)\; \}$. If the background logic includes equality, it is also possible to define the empty set as :$varnothing\; =\; \{u\; in\; w\; mid\; lnot\; (u\; =\; u)\; \}$. Thus theaxiom of the empty set is implied by the nine axioms presented here. The axiom of extensionality implies the empty set is unique, if it exists. It is common to make adefinitional extension that adds the symbol $varnothing$ to the language of ZFC.**4.**If "x" and "y" are sets, then there exists a set which contains "x" and "y" as elements.:$forall\; x\; forall\; y\; exist\; z\; (x\; in\; z\; land\; y\; in\; z).$This axiom is part of Z, but is redundant in ZF because it follows from theAxiom of pairing :axiom schema of replacement applied to any two-member set. The existence of such a set is assured by either theaxiom of infinity , or by theaxiom of the power set applied twice to the empty set.**5.**For any set $mathcal\{F\}$ there is a set "A" containing every set that is a member of some member of $mathcal\{F\}.$:$forall\; mathcal\{F\}\; ,exists\; A\; ,\; forall\; Y,\; forall\; x\; (x\; in\; Y\; land\; Y\; in\; mathcal\{F\}\; Rightarrow\; x\; in\; A).$Axiom of union :**6. Axiom schema of collection:**Let $phi\; !$ be any formula in the language of ZFC whosefree variable s are among $x,y,A,w\_1,ldots,w\_n\; !$. So "B" is not free in $phi\; !$. $exists\; !\; y$ is aquantifier binding "y", meaning that exactly one $y!$ exists, up to equality. Then::$forall\; A,forall\; w\_1,ldots,w\_n\; [\; (\; forall\; x\; in\; A\; exists\; !\; y\; phi\; )\; Rightarrow\; exists\; B\; forall\; x\; in\; A\; exists\; y\; in\; B\; phi]\; .$Less formally, this axiom states that if the domain of a function "f" is a set, and "f"("x") is a set for any "x" in that domain, then the range of "f" is a subclass of a set, subject to a restriction needed to avoid paradoxes.**7.**Let $S(x)!$ abbreviate $x\; cup\; \{x\}\; !$, where $x\; !$ is some set. Then there exists a set "X" such that the empty set $varnothing$ is a member of "X" and, whenever a set "y" is a member of "X", then $S(y)!$ is also a member of "X". :$exist\; X\; left\; [varnothing\; in\; X\; and\; forall\; y\; (y\; in\; X\; Rightarrow\; S(y)\; in\; X)\; ight\; ]\; .$More colloquially, there exists a set "X" having infinitely many members. The minimal set "X" satisfying the axiom of infinity is theAxiom of infinity :von Neumann ordinal ω.**8.**Let $z\; subseteq\; x$ abbreviate $forall\; q\; (q\; in\; z\; Rightarrow\; q\; in\; x).$ For any set "x", there is a set "y" which is aAxiom of power set :superset of thepower set of "x". The power set of "x" is the class whose members are every possible subset of "x".:$forall\; x\; exists\; y\; forall\; z\; [z\; subseteq\; x\; Rightarrow\; z\; in\; y]\; .$Alternative forms of axioms

**1–8**are often encountered, some of which are listed in Jech (2003). Some ZF axiomatizations include an axiom asserting that the empty set exists. The axioms of pairing, union, replacement, and power set are often stated so that the members of the set "x" whose existence is being asserted, are just those sets which the axiom asserts "x" must contain.**9.**For any set "X", there is aWell-ordering theorem :binary relation "R" which well-orders "X". This means "R" is alinear order on "X" such that every nonemptysubset of "X" has a member which is minimal under "R".:$forall\; X\; exists\; R\; (\; R\; ;mbox\{well-orders\};\; X).$Given axioms

**1-8**, there are many statements provably equivalent to axiom**9**, the best known of which is theaxiom of choice (AC), which goes as follows. Let "X" be a set whose members are all non-empty. Then there exists a function "f", called a "choice function," whose domain is "X", and whose range is a set, called the "choice set," each member of which is a single member of each member of "X". Since the existence of a choice function when "X" is afinite set is easily proved from axioms**1-8**, AC only matters for certaininfinite set s. AC is characterized as nonconstructive because it asserts the existence of a choice set but says nothing about how the choice set is to be "constructed." Much research has sought to characterize the definability (or lack thereof) of certain sets whose existence AC asserts.**Metamathematics**The axiom schemata of replacement and separation each contain infinitely many instances. Montague (1961) included a result first proved in his 1957 Ph.D. thesis: if ZFC is consistent, it is impossible to axiomatize ZFC using only finitely many axioms. On the other hand,

Von Neumann–Bernays–Gödel set theory (NBG) can be finitely axiomatized. The ontology of NBG includes proper classes as well as sets; a set is any class that can be a member of another class. NBG and ZFC are equivalent set theories in the sense that anytheorem not mentioning classes and provable in one theory can be proved in the other.Gödel's second incompleteness theorem says that no recursively axiomatizable system that can interpretRobinson arithmetic can prove its own consistency. Moreover, Robinson arithmetic can be interpreted ingeneral set theory , a small fragment of ZFC. Hence the consistency of ZFC cannot be proved within ZFC itself (unless it is actually inconsistent). Thus, to the extent that ZFC is identified with ordinary mathematics, the consistency of ZFC cannot be demonstrated in ordinary mathematics. The consistency of ZFC does follow from the existence of a weaklyinaccessible cardinal , which is unprovable in ZFC if ZFC is consistent. Nevertheless, it is unlikely that ZFC harbors an unsuspected contradiction; if ZFC were inconsistent, it is widely believed that that fact would have been uncovered by now. This much is certain — ZFC is immune to the classic paradoxes ofnaive set theory :Russell's paradox , theBurali-Forti paradox , andCantor's paradox .Abian and LaMacchia (1978), using simple models, prove consistent the theory including the axioms of extensionality, union, powerset, replacement, and choice. They then proved that each of the axioms of extensionality, replacement, and power set is independent of the four remaining axioms in this set. If this five axiom set is augmented with the axiom of infinity, each of the axioms of union, choice, and infinity is independent of the five remaining axioms. Because

non-well-founded set theory is a model of ZFC without the axiom of regularity, that axiom is independent of the other ZFC axioms.One piece of evidence bearing on ZFC as a foundation of mathematics is

Metamath , an ongoing web-based project that seeks to derive much of contemporary mathematics from the ZFC axioms,first order logic , and a host of definitions, with all proofs verified by machine. As of early 2008, the Metamath database includes about 8000 proved theorems. This project can be seen as being in the same spirit asBertrand Russell 's "Principia Mathematica ", except grounded in logical and nonlogical axioms that benefit from nearly a century of subsequent research.ZFC does not prove the existence of the

inaccessible cardinal s required bycategory theory . Huge sets of this nature are possible if ZF is augmented with Tarski's axiom (Tarski 1939). Assuming that axiom turns the axioms of infinity and choice (**7**and**9**above) into theorems. Tarski's axiom is not a trivial affair, as it contains 7existential quantifier s and 23atomic formula s. [*[*]*http://us.metamath.org/mpegif/grothprim.html Metamath version*] of Tarski's axiom, expressed using only the primitives membership and identity. With the help of 4 defined notions, this axiom can be recast [*http://us.metamath.org/mpegif/axgroth2.html more concisely*] so as to require merely 2 existential quantifiers and 10 atomic formulas.**Independence in ZFC**Many important statements are independent of ZFC (see

list of statements undecidable in ZFC ). The independence is usually proved by forcing, whereby it is shown that every countable transitive model of ZFC (sometimes augmented withlarge cardinal axiom s) can be expanded to satisfy the statement in question. The negation of the statement is then shown to satisfy a different expansion. An independence proof by forcing automatically proves independence from arithmetical statements, other concrete statements, and large cardinal axioms. Some statements independent of ZFC can be proven to hold in particularinner model s, such as in theconstructible universe . However, some statements that are true about constructible sets are not consistent with hypothesised large cardinal axioms.Forcing proves that the following statements are independent of

ZFC :

*Continuum hypothesis

*Diamond principle

*Suslin hypothesis

*Kurepa hypothesis

*Martin's axiom (which is not a ZFC axiom)

*Axiom of Constructibility (V=L) (which is also not a ZFC axiom).Remarks:

*The consistency of V=L is provable byinner model s but not forcing: every model of ZF can be trimmed to become a model of ZFC+V=L.

*The Diamond Principle implies the Continuum Hypothesis and the negation of the Suslin Hypothesis.

*Martin's axiom plus the negation of the Continuum Hypothesis implies the Suslin Hypothesis.

*Theconstructible universe satisfies the Generalized Continuum Hypothesis, the Diamond Principle, Martin's Axiom and the Kurepa Hypothesis.A variation on the method of forcing can also be used to demonstrate the consistency and unprovability of the

axiom of choice , i.e., that the axiom of choice is independent of ZF. The consistency of choice can be (relatively) easily verified by proving that the inner model L satisfies choice. (Thus every model of ZF contains a submodel of ZFC, so that Con(ZF) implies Con(ZFC).) Since forcing preserves choice, we cannot directly produce a model contradicting choice from a model satisfying choice. However, we can use forcing to create a model which contains a suitable submodel, namely one satisfying ZF but not C.Another method of proving independence results, one owing nothing to forcing, is based on Gödel's second incompleteness theorem. This approach employs the statement whose independence is being examined, to prove the existence of a set model of ZFC, in which case Con(ZFC) is true. Since ZFC satisfies the conditions of Gödel's second theorem, the consistency of ZFC is unprovable in ZFC. Hence no statement allowing such a proof can be proved in ZFC. This method can prove that the existence of

large cardinals is not provable in ZFC, but cannot prove that assuming such cardinals, given ZFC, is free of contradiction.**Criticisms**:"For criticism of set theory in general, see Objections to set theory"

ZFC has been criticized both for being excessively strong and for being excessively weak, as well as for its failure to capture objects such as proper classes and the universal set.

Many mathematical theorems can be proven in much weaker systems than ZFC, such as

Peano arithmetic andsecond order arithmetic (as explored by the program ofreverse mathematics ).Saunders Mac Lane andSolomon Feferman have both made this point. Some of "mainstream mathematics" (mathematics not directly connected with axiomatic set theory) is beyond Peano arithmetic and second order arithmetic, but still, all such mathematics can be carried out ZC (Zermelo set theory with choice), another theory weaker than ZFC. Much of the power of ZFC, including the axiom of regularity and the axiom schema of replacement, is included primarily to facilitate the study of the set theory itself.On the other hand, among

axiomatic set theories , ZFC is comparatively weak. UnlikeNew Foundations , ZFC does not admit the existence of auniversal set . Hence theuniverse of sets under ZFC is not closed under the elementary operations of thealgebra of sets . Unlikevon Neumann–Bernays–Gödel set theory andMorse–Kelley set theory (MK), ZFC does not admit the existence ofproper class es. These ontological restrictions are required for ZFC to avoidRussell's paradox , but critics argue these restrictions make the ZFC axioms fail to capture the informal concept of "set". A further comparative weakness of ZFC is that theaxiom of choice included in ZFC is weaker than theaxiom of global choice included in MK.There are numerous mathematical statements undecidable in ZFC. These include the

continuum hypothesis , theWhitehead problem , and the Normal Moore space conjecture. Some of these conjectures are provable with the addition of axioms such asMartin's axiom , large cardinal axioms, or theaxiom of determinacy to ZFC. TheMizar system has adoptedTarski-Grothendieck set theory instead of ZFC so that proofs involvingGrothendieck universe s (encountered in category theory and algebraic geometry) can be formalized.**See also***

Axiomatic set theory

*List of statements undecidable in ZFC

*Metamath

*Non-well-founded set theory

* "Principia Mathematica "

*Set theory

*Von Neumann–Bernays–Gödel set theory

*Z notation

*Zermelo set theory **Notes****References***

Alexander Abian , 1965. "The Theory of Sets and Transfinite Arithmetic". W B Saunders.

*-------- and LaMacchia, Samuel, 1978, " [*http://projecteuclid.org/DPubS/Repository/1.0/Disseminate?view=body&id=pdf_1&handle=euclid.ndjfl/1093888220 On the Consistency and Independence of Some Set-Theoretical Axioms,*] " "Notre Dame Journal of Formal Logic" 19: 155-58.

*Keith Devlin , 1996 (1984). "The Joy of Sets". Springer.

*Abraham Fraenkel ,Yehoshua Bar-Hillel , andAzriel Levy , 1973 (1958). "Foundations of Set Theory". North Holland. Fraenkel's final word on ZF and ZFC.

*Hatcher, William, 1982 (1968). "The Logical Foundations of Mathematics". Pergamon.

*Thomas Jech , 2003. "Set Theory: The Third Millennium Edition, Revised and Expanded". Springer. ISBN 3-540-44085-2.

*Kenneth Kunen , 1980. "Set Theory: An Introduction to Independence Proofs". Elsevier. ISBN 0-444-86839-9.

*Richard Montague , 1961, "Semantic closure and non-finite axiomatizability" in "Infinistic Methods". London: Pergamon: 45-69.

*Patrick Suppes , 1972 (1960). "Axiomatic Set Theory". Dover reprint. Includes many theorems.

*Gaisi Takeuti and Zaring, W M, 1971. "Introduction to Axiomatic Set Theory". Springer Verlag.

*Alfred Tarski , 1939, "On well-ordered subsets of any set,", "Fundamenta Mathematicae" 32: 176-83.

*Tiles, Mary, 2004 (1989). "The Philosophy of Set Theory". Dover reprint. Weak on metatheory; the author is not a mathematician.

*Tourlakis, George, 2003. "Lectures in Logic and Set Theory, Vol. 2". Cambridge Univ. Press.

*Jean van Heijenoort , 1967. "From Frege to Godel: A Source Book in Mathematical Logic, 1879-1931". Harvard Univ. Press. Includes annotated English translations of the classic articles byZermelo ,Fraenkel , andSkolem bearing on**ZFC**.**External links***

Stanford Encyclopedia of Philosophy articles byThomas Jech :

** [*http://plato.stanford.edu/entries/set-theory/ Set Theory*] ;

** [*http://plato.stanford.edu/entries/set-theory/ZF.html Axioms of Zermelo-Fraenkel Set Theory*] .

* [*http://us.metamath.org/mpegif/mmset.html#staxioms Metamath version of the ZFC axioms*] — A concise and nonredundant axiomatization. The backgroundfirst order logic is defined especially to facilitate machine verification of proofs.

*

*Wikimedia Foundation.
2010.*