ZFC

Zermelo–Fraenkel set theory with the axiom of choice

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 modern (2000) set theory, regarded both as a field of mathematical research and as a foundation for ongoing mathematics (cf. also Axiomatic set theory). Set theory emerged from the researches of G. Cantor into the transfinite numbers and his continuum hypothesis and of R. Dedekind in his incisive analysis of natural numbers (see [a5] or [a10]). E. Zermelo [a20] in 1908, under the influence of D. Hilbert at Göttingen, provided the first full-fledged axiomatization of set theory, from which ZFC in large part derives. Although several axiom systems were later proposed, ZFC became generally adopted by the 1960{}s because of its schematic simplicity and open-endedness in codifying the minimally necessary set existence principles needed and is now (as of 2000) regarded as the basic framework onto which further axioms can be adjoined and investigated. A modern presentation of ZFC follows.

The language of set theory is first-order logic with a binary predicate symbol $\in$ for membership ( "first-order" refers to quantification only over individuals, not e.g. properties). This language has as symbols an infinite store of variables; logical connectives ($\neg$ for "not" , $\vee$ for "or" , $\wedge$ for "and" , $\rightarrow$ for "implies" , and $\leftrightarrow$ for "is equivalent to" ); quantifiers ($\forall$ for "for all" and $\exists$ for "there exists" ); two binary predicate symbols, $=$ and $\in$; and parentheses. (A more parsimonious presentation is possible, e.g. one can do with just $\neg$, $\vee$ and $\forall$, and leave out parentheses with a different syntax.) The formulas of the language are generated as follows: $x = y$ and $x \in y$ are (the atomic) formulas whenever $x$ and $y$ are variables. If $\varphi$ and $\psi$ are formulas, then so are $( \neg \varphi )$, $( \varphi \vee \psi )$, $( \varphi \wedge \psi )$, $( \varphi \rightarrow \psi )$, $( \varphi \leftrightarrow \psi )$, $\forall x \varphi$, and $\exists x \varphi$, whenever $x$ is a variable. The various further notations can be regarded as abbreviations; for example, $x \subseteq y$ for "x is a subset of y" abbreviates $\forall z ( z \in x \rightarrow z \in y )$.

The axioms of ZFC are as follows, with some historical and notational commentary.

A1) Axiom of extensionality:

\begin{equation*} \forall x \forall y ( \forall z ( z \in x \leftrightarrow z \in y ) \rightarrow x = y ). \end{equation*}

This is a fundamental principle of sets, that sets are to be determined solely by their members. The arrow "" can be replaced by "" since the other direction is immediate. Indeed, the axiom can then be taken to be a means of introducing $=$ itself as an abbreviation, as a symbol defined in terms of $\in$. The term "extensionality" stems from a traditional philosophical distinction between the intension and the extension of a term, where loosely speaking the extension of a term is the collection of things of which the term is true of, and the intension is some more intrinsic sense of the term. A clear statement of the principle of extensionality had already appeared in the pioneering work of Dedekind [a3], which provided a development of the natural numbers in set-theoretic terms and anticipated Zermelo's axiomatic, abstract approach to set theory. Cf. also Axiom of extensionality.

A2) Axiom of the empty set:

\begin{equation*} \exists x \forall y ( \neg y \in x ). \end{equation*}

This axiom asserts the existence of an empty set; by A1), such a set is unique, and is denoted by the term $\emptyset$. Terms are similarly introduced in connection with other axioms below, and in general such terms can be eliminated in favour of their definitions; for example, $\emptyset \in z$ can be regarded as an abbreviation for $\exists x ( \forall y ( \neg y \in x ) \wedge x \in z )$.

A3) Axiom of pairs:

\begin{equation*} \forall x \forall y \exists z \forall v ( v \in z \leftrightarrow ( v = x \vee v = y ) ). \end{equation*}

This axiom asserts, for any sets $x$ and $y$, the existence of their (unordered) pair, the set consisting exactly of $x$ and $y$. This set is denoted by $\{ x , y \}$. A3) implies, taking its $y$ to be $x$, that for any set $x$ there is a set consisting solely of $x$, denoted by $\{ x \}$.

The existence of $\emptyset$ and the distinction between a set $x$ and the single-membered $\{ x \}$ were not clearly delineated in the early development of set theory, and equivocations in these directions can be found, e.g., in [a3].

A4) Axiom of union:

\begin{equation*} \forall x \exists z \forall v ( v \in z \leftrightarrow \exists y ( y \in x \bigwedge v \in y ) ). \end{equation*}

This axiom asserts, for any set $x$, the existence of its (generalized) union, the set consisting exactly of the members of members of $x$. This union is denoted by $\cup x$. Note that for two sets $a$ and $b$, $\cup \{ a , b \}$ is the usual union $a \cup b$.

A5) Axiom of power set:

\begin{equation*} \forall x \exists z \forall v ( v \in z \leftrightarrow \forall w ( w \in v \rightarrow w \in x ) ). \end{equation*}

This axiom asserts, for any set $x$, the existence of its power set, the set consisting exactly of those sets $v$ that are subsets of $x$. This power set is denoted by $\mathcal{P} ( x )$. The axioms A3)–A5) are generative axioms, providing various means of collecting sets together to form new sets. The generative process can be started with A2), an outright existence axiom. The next axiom is another outright existence axiom, which for convenience is stated via terms defined above:

A6) Axiom of infinity:

\begin{equation*} \exists x ( \emptyset \in x \bigwedge \forall y ( y \in x \rightarrow y \bigcup \{ y \} \in x ) ). \end{equation*}

Among various possible approaches, this axiom asserts the existence of an infinite set of a specific kind: the set contains the empty set and is moreover closed in the sense that whenever $y$ is in the set, so also is $y \cup \{ y \}$. Hence, $\emptyset$, $\{ \emptyset \}$, $\{ \emptyset , \{ \emptyset \} \}$, $\{ \emptyset , \{ \emptyset \} , \{ \emptyset , \{ \emptyset \} \} \}, \dots$ are to be members; these are indeed sets by A2) and A3) and are moreover distinct from each other by A1). Zermelo himself had $\{ y \}$ in place of $y \cup \{ y \}$, but the modern formulation derives from the formulation by J. von Neumann [a16] of the ordinal numbers within set theory (cf. also Ordinal number). Dedekind [a3] had (in)famously "proved" the existence of an infinite set; Zermelo was first to see the need to postulate the existence of an infinite set. In the presence of A6), A5) becomes a much more powerful axiom, purportly collecting together in one set all arbitrary subsets of an infinite set; Cantor famously established that no set is in bijective correspondence with its power set, and this leads to an infinite range of transfinite cardinalities (cf. also Transfinite number).

A7) Axiom of choice:

\begin{equation*} \forall x: \end{equation*}

\begin{equation*} \exists y \forall v ( ( v \in x \bigwedge ( \neg v = \emptyset ) ) \rightarrow \exists s \forall t ( ( t \in v \bigwedge t \in y ) \leftrightarrow s = t ) ). \end{equation*}

This is one of the most crucial axioms of Zermelo's axiomatization [a20] (cf. also Axiom of choice). To unravel it, the hypothesis asserts that $x$ consists of pairwise disjoint sets, and the conclusion, that there is a set $y$ that with each non-empty member of $x$ has exactly one common member. Thus, $y$ serves as a "selector" of elements from members of $x$. A7) is usually stated in terms of functions: The theory of functions, construed as sets of ordered pairs with the univalent property on the second coordinate, is first developed with the previous axioms. Then A7) has an equivalent formulation as: Every set has a choice function, i.e. a function $f$ whose domain is the set and such that for each non-empty member $y$ of the set, $f ( y ) \in y$.

Zermelo [a18] formulated A7) and with it, established his famous well-ordering theorem: Every set can be well-ordered (cf. also Zermelo theorem). Zermelo maintained that the axiom of choice is a "logical principle" which "is applied without hesitation everywhere in mathematical deduction" . However, Zermelo's axiom and result generated considerable criticism because of the positing of arbitrary functions following no particular rule governing the passage from argument to value. Since then, of course, the axiom has become deeply embedded in mathematics, assuming a central role in its equivalent formulation as Zorn's lemma (cf. also Zorn lemma). In response to critics, Zermelo [a19] published a second proof of his well-ordering theorem, and it was in large part to buttress this proof that he published [a20] his axiomatization, making explicit the underlying set-existence assumptions used (see [a13]).

A8) Axiom (schema) of separation: For any formula $\varphi$ with unquantified variables among $v , v _ { 1 } , \dots , v _ { n }$,

\begin{equation*} \forall x \forall v _ { 1 } \ldots \forall v _ { n } \exists y \forall v ( v \in y \leftrightarrow ( v \in x \bigwedge \varphi ) ). \end{equation*}

This is another crucial component of Zermelo's axiomatization [a20]. Actually, it is an infinite package of axioms, one for each formula $\varphi$, positing for any set $x$ the existence of a subset $y$ consisting of those members of $x$ "separated" out according to $\varphi$. Zermelo was aware of the paradoxes of logic emerging at the time, and he himself had found the famous Russell paradox independently (cf. also Paradox; Antinomy). Russell's paradox results from "full comprehension" , the allowing of any collection of sets satisfying a property to be a set: Consider the property $( \neg y \in y )$; if there were a set $R$ consisting exactly of those $y$ satisfying this property, one would have the contradiction $( R \in R \leftrightarrow ( \neg R \in R ) )$. Zermelo saw that if one only allowed collections of sets satisfying a property "and drawn from a given set" to be a set, then there are no apparent contradictions. Thus was Zermelo able to retain, in an adequate way as it has turned out, the important capability of generating sets corresponding to properties. The first theorem in [a20] applies A8) together with the Russell paradox argument to assert that the universe of sets (cf. also Universe) is not itself a set.

Zermelo's version of A8) retained an intensional aspect, with his $\varphi$ being some "definite" property determinate for any $y \in x$ whether the property is true of $y$ or not. However, this became unsatisfactory in the development of set theory, and eventually the suggestion of T. Skolem [a14] of taking Zermelo's definite properties as those expressible in first-order logic was adopted, yielding A8). Generally speaking, logic loomed large in the formalization of mathematics at the turn into the twentieth century, at the time of G. Frege and B. Russell, but in the succeeding decades there was a steady dilution of what was considered to be logical in mathematics. Many notions came to be considered distinctly set-theoretic rather than logical, and what was retained of logic in mathematics was first-order logic.

A9) Axiom (schema) of replacement: For any formula $\varphi$ in two unquantified variables $v$ and $w$,

\begin{equation*} \forall v \exists u ( \forall w \varphi \leftrightarrow u = w ) \end{equation*}

\begin{equation*} \downarrow \forall x \exists y \forall w ( w \in y \leftrightarrow \exists v ( v \in x \bigwedge \varphi ) ). \end{equation*}

This also is an infinite package of axioms, one for each $\varphi$. To unravel it, the hypothesis asserts that $\varphi$ is "functional" in the sense that to each set $v$ there is a unique corresponding set $u$ satisfying $\varphi$, and the conclusion, that for any set $x$ there is a set $y$ serving as the "image of x under v" . In short, for any definable function correspondence and any set, the image of that set under the correspondence is also a set.

A9) was not part of Zermelo's original axiomatization [a20], and to meet its inadequacies for generating certain kinds of sets, A. Fraenkel [a6] and Skolem [a14] independently proposed adjoining A9). Because of historical circumstance, it was Fraenkel whose initial became part of the acronym ZFC. However, it was Von Neumann's incorporation [a17] of a method into set theory, transfinite recursion, that necessitated the full exercise of A9). In particular, he [a16] defined (what are now called the von Neumann) ordinals within set theory to correspond to Cantor's original, abstract ordinal numbers, and A9) is needed to establish that every well-ordered set is order-isomorphic to an ordinal. By a simple argument, A9) implies A8).

A10) Axiom of foundation:

\begin{equation*} \forall x ( ( \neg x = \emptyset ) \rightarrow \exists y ( y \in x \bigwedge \forall z ( z \in x \rightarrow \neg z \in y ) ) ). \end{equation*}

This asserts that every non-empty set $x$ is well-founded, i.e. has a "minimal" member $y$ in terms of $\in$.

A10) also was not part of Zermelo's axiomatization [a20], but appeared in his final axiomatization [a21]. A10) is an elegant form of the assertion that the formal universe $V$ of sets is stratified into a cumulative hierarchy: The axiom is equivalent to the assertion that $V$ is layered into sets $V _ { \alpha }$ for (von Neumann) ordinals $\alpha$, where:

\begin{equation*} V _ { 0 } = \emptyset ; V _ { \alpha } = \bigcup _ { \beta < \alpha } \mathcal{P} ( V _ { \beta + 1 } ) ; \text { and } V = \bigcup _ { \alpha } V _ { \alpha }. \end{equation*}

D. Mirimanoff and von Neumann had also formulated the cumulative hierarchy, but more to specific purposes. Zermelo substantially advanced the schematic generative picture with his adoption of A10), and K. Gödel urged this view of the set-theoretic universe. A10) is the one axiom unnecessary for the recasting of mathematics in set-theoretic terms, but the axiom is also the salient feature that distinguishes investigations specific to set theory as an autonomous field of mathematics. Indeed, it can fairly be said that current set theory is at base the study of well-foundedness, the Cantorian well-ordering doctrines adapted to the Zermelian generative conception of sets.

ZFC, again, is the standard system of axioms for set theory, given by the axioms A1)–A10) above. "Z" is the common acronym for Zermelo set theory, the axioms above but with A9), the axiom (schema) of replacement, deleted. Finally, "ZF" is the common acronym for Zermelo–Fraenkel set theory, the axioms above but with A7), the axiom of choice, deleted.

There has been a tremendous amount of work done in the axiomatic investigation of set theory. The first substantial result was Gödel's relative consistency result [a7], [a8], that if ZF is consistent, then so also is ZFC (and this together with Cantor's continuum hypothesis; cf. also Consistency). P. Cohen [a1], [a2], in famous work leading to the Fields Medal, established the relative independence result, that if ZF is consistent, then so also is ZF together with the negation of the axiom of choice (and so also is ZFC together with the negation of the continuum hypothesis). (Cf. also Forcing method.) For these results, see [a9], [a12]. A great deal of the work of the last several decades (as of 2000) has been devoted to the investigation of large cardinal axioms adjoined to ZFC and their consequences and interactions with ongoing mathematics (see [a10]).

References

[a1]	P.J. Cohen, "The independence of the continuum hypothesis I" Proc. Nat. Acad. Sci. USA , 50 (1963) pp. 1143–1148
[a2]	P.J. Cohen, "Set theory and the continuum hypothesis" , Benjamin (1966)
[a3]	R. Dedekind, "Was sind und was sollen die Zahlen?" , Vieweg (1888) (English transl.: R. Dedekind, Essays on the theory of numbers, Dover 1963; W.B. Ewald, From Kant to Hilbert: A source book in the foundations of mathematics, Oxford Univ. Press, 1996, pp. 790-833)
[a4]	"From Kant to Hilbert: A source book in the foundations of mathematics" W.B. Ewald (ed.) , Oxford Univ. Press (1996)
[a5]	J. Ferreirós, "Labyrinth of thought: A history of set theory and its role in modern mathematics" , Birkhäuser (1999)
[a6]	A.A. Fraenkel, "Über die Zermelosche Begründung der Mengenlehre (abstract)" Jahresber. Deutsch. Math. Verein. , 30 : II (1921) pp. 97–98
[a7]	K.F. Gödel, "The consistency of the axiom of choice and of the generalized continuum-hypothesis" Proc. Nat. Acad. Sci. USA , 24 (1938) pp. 556–557
[a8]	K.F. Gödel, "The consistency of the axiom of choice and of the generalized continuum hypothesis with the axioms of set theory" , Ann. of Math. Stud. , 3 , Princeton Univ. Press (1940)
[a9]	Th.J. Jech, "Set theory" , Acad. Press (1997) (Edition: Second, corrected)
[a10]	A. Kanamori, "The mathematical development of set theory from Cantor to Cohen" Bull. Symbolic Logic , 2 (1996) pp. 1–71
[a11]	A. Kanamori, "The higher infinite" , Springer (1997) (Corrected second printing)
[a12]	K. Kunen, "Set theory: An introduction to independence proofs" , North-Holland (1980)
[a13]	G.H. Moore, "Zermelo's axiom of choice: Its origins, development and influence" , Springer (1982)
[a14]	T. Skolem, "Einige Bemerkungen zur axiomatischen Begründung der Mengenlehre" , Matematikerkongressen i Helsingfors den 4-7 Juli, 1922, Den femte Skand. Matematikerkongressen, Redogörelse Helsinki , Akad. Bokhandeln (1923) pp. 217–232 (English transl.: J. van Heijenoort (ed.), From Frege to Gödel: A source book in mathematical logic 1879-1931, Cambridge Univ. Press, 1967, pp. 290-301)
[a15]	"From Frege to Gödel: A source book in mathematical logic 1879-1931" J. van Heijenoort (ed.) , Cambridge Univ. Press (1967)
[a16]	J. von Neumann, "Zur Einführung der transfiniten Zahlen" Acta Litterarum ac Scientiarum Regiae Univ. Hung. Francisco–Josephinae, Sectio Sci. Math. , 1 (1923) pp. 199–208 (English transl.: J. van Heijenoort (ed.), From Frege to Gödel: A source book in mathematical logic 1879-1931, Cambridge Univ. Press, 1967, pp. 346-354)
[a17]	J. von Neumann, "Eine Axiomatisierung der Mengenlehre" J. Reine Angew. Math. (Crelle's J.) , 154 (1925) pp. 219–240 (Berichtigung, J. Reine Angew. Math. 155 (1925), 128; English transl. J. van Heijenoort (ed.), From Frege to Gödel: A source book in mathematical logic 1879-1931, Cambridge Univ. Press, 1967, pp. 393-413)
[a18]	E. Zermelo, "Beweis, dass jede Menge wohlgeordnet werden kann (Aus einem an Herrn Hilbert gerichteten Briefe)" Math. Ann. , 59 (1904) pp. 514–516 (English transl.: J. van Heijenoort (ed.), From Frege to Gödel: A source book in mathematical logic 1879-1931, Cambridge Univ. Press, 1967, pp. 139-141)
[a19]	E. Zermelo, "Neuer Beweis für die Möglichkeit einer Wohlordnung" Math. Ann. , 65 (1908) pp. 107–128 (English transl.: J. van Heijenoort (ed.), From Frege to Gödel: A source book in mathematical logic 1879-1931, Cambridge Univ. Press, 1967, pp. 183-198)
[a20]	E. Zermelo, "Untersuchungen über die Grundlagen der Mengenlehre I" Math. Ann. , 65 (1908) pp. 261–281 (English transl.: J. van Heijenoort (ed.), From Frege to Gödel: A source book in mathematical logic 1879-1931, Cambridge Univ. Press, 1967, pp. 199-215)
[a21]	E. Zermelo, "Über Grenzzahlen und Mengenbereiche: Neue Untersuchungen über die Grundlagen der Mengenlehre" Fundam. Math. , 16 (1930) pp. 29–47 (English transl.: W.B. Ewald (ed.), From Kant to Hilbert: A source book in the foundations of mathematics, Oxford Univ. Press, 1996, pp. 1219-1233)