Zermelo–Fraenkel set theory

Zermelo–Fraenkel set theory, with the axiom of choice, commonly abbreviated ZFC, is the most common form of axiomatic set theory, and as such is the most common foundation of mathematics.

Introduction

ZFC consists of a single primitive ontological notion, that of set, and a single ontological assumption, namely that all individuals in the universe of discourse (i.e., all mathematical objects) are sets. There is a single primitive binary relation, set membership; that set a is a member of set b is written a ∈ b (usually read "a is an element of b"). ZFC is a first-order theory; hence ZFC includes axioms whose background logic is first-order logic. These axioms govern how sets behave and interact. ZFC is the standard form of axiomatic set theory. For an ongoing derivation of a great deal of ordinary mathematics using ZFC, see the Metamath online project.

In 1908, Ernst Zermelo proposed the first axiomatic set theory, Zermelo set theory. This axiomatic theory did not allow the construction of the ordinal numbers; 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 unambiguous. In 1922, Abraham Fraenkel and Thoralf Skolem independently proposed defining a "definite" property as any property that could be formulated in first-order logic. From their work emerged the axiom of replacement. Appending this axiom, as well as the axiom of regularity, to Zermelo set theory yields the theory denoted by ZF.

Adding the axiom of choice (AC) to ZF yields ZFC. When a mathematical result requires the axiom of choice, this is sometimes stated explicitly. The reason for singling out AC in this manner is that AC is inherently nonconstructive; it posits the existence of a set (the choice set), without specifying just how that set is to be constructed. Hence results proved using AC may involve sets that, although they can be proved to exist (at least if one is not committed to a constructivist ontology), can never be constructed explicitly.

ZFC has an infinite number of axioms because the Replacement axiom is actually an axiom schema. It is known that both ZFC and ZF set theory cannot be axiomatized by a finite set of axioms; this was first demonstrated by Richard Montague. On the other hand, NBG set theory can be finitely axiomatized. The ontology of NBG includes classes as well as sets; classes are entities that have members but that cannot be members of another class. NBG and ZFC are equivalent set theories, in the sense that any theorem about sets (i.e., not mentioning classes in any way) which can be proved in one theory can be proved in the other.

Because of Gödel's second incompleteness theorem, the consistency of ZFC cannot be proved within ZFC itself. 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 weakly inaccessible cardinal, something whose existence is not provable in ZFC. Nevertheless, almost no one fears 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 easily proved immune to the three great paradoxes of naive set theory, Russell's paradox, the Burali-Forti paradox, and Cantor's paradox.

Drawbacks of ZFC that have been discussed in the literature include:

It is stronger than what is required for nearly all of everyday mathematics (Saunders MacLane and Solomon Feferman have each made this point);
Compared to other axiomatizations of set theory, ZFC is comparatively weak. For example, it does not admit the existence of a universal set (as in New Foundations) or class (as in NBG);
Saunders MacLane (a founder of category theory) and others have argued that any axiomatic set theory does not do justice to the way mathematics works in practice. According to his view, mathematics is not about collections of abstract objects and their properties, but about structure and structure-preserving mappings.

The axioms

There are many equivalent formulations of the axioms of ZFC. The following particular set of formal axioms is given by Kunen ^*; English descriptions have been added here for clarity.

1) Axiom of extensionality: Two sets are the same if and only if they have the same members.

\forall x \forall y ( \forall z (z \in x \leftrightarrow z \in y)

\rightarrow x = y)

2) Axiom of regularity (also called the Axiom of foundation): Every non-empty set x contains some member y such that x and y are 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) Axiom scheme of separation (also called the Axiom scheme of comprehension): If x is a set then any formal definition of a potential subset of x does define a subset of x, subject to a restriction to avoid paradoxes. Formally: for any formula

\phi

in the language of ZFC with free variables among

x,z,w_1,\ldots,w_n

\forall z \forall w_1 \ldots w_n \exists y \forall x (x \in y \leftrightarrow x \in z \land \phi)

4) Axiom of pairing: If x and y are sets then there exists a set containing both of them.

\forall x \forall y \exist z (x \in z \land y \in z)

5) Axiom of union: 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)

6) Axiom scheme of replacement: Every formally defined function whose domain is a set has a codomain which is also a set, subject to a restriction to avoid paradoxes. Formally: for each formula $\phi$ in the language of ZFC with free variables among $x,y,A,w_1,\ldots,w_n$ :

\forall A\,\forall w_1,\ldots,w_n \forall x \in A \exists ! y \phi \rightarrow \exists Y \forall x \in A \exists y \in Y \phi .

Here the quantifer

\exists ! y

means that a unique such

y

exists, up to equality.

The next axiom makes use of the notation $S(x) = x \cup \{x\}$ . Axioms 1 through 6 prove that $S(x)$ exists and is unique for each set $x$ . They also imply that the empty set $\varnothing$ exists and is unique.

7) Axiom of infinity: There exists a set x such that the empty set is a member of x and whenever y is in x, so is S(y).

\exists x  ( \varnothing \in x \land \forall y \in x ( S(y) \in x))

8) Axiom of power set: For any set x there is a set y that contains every subset of x.

\forall x \exists y  \forall z (z \subseteq x \rightarrow z \in y)

Here

z \subseteq x

is an abbreviation for

\forall q (q \in z \rightarrow q \in x)

9) Axiom of choice: For any set X there is a binary relation R which well-orders X. This means that R is a linear order on X and every nonempty subset of X has an element which is minimal under R.

\forall A \exists R ( R \;\mbox{well-orders}\; A)

These nine axioms are not independent. For example, the axiom scheme of comprehension is derivable from the other eight axioms. Kunen also includes a redundant axiom saying that at least one set exists.

Alternative forms of the first eight axioms are often encountered. For example, Axiom 4 is often changed to say that for any sets x and y there is a set containing exactly x and y, Axiom 8 is often changed to say that y contains exactly the subsets of x. An axiom is sometimes added which asserts that the empty set exists. For an example of some of these variations, see the list of axioms given by Jech ^*.

The Axiom of choice has many equivalent statements (that is, there are many statements that the first 8 axioms prove to be equivalent to axiom 9). These include the statement that every set of nonempty sets has a choice function; the name of the axiom is taken from this equivalent form.

Bibliography

Abian, Alexander, 1965. The Theory of Sets and Transfinite Arithmetic. W B Saunders.
Keith Devlin, 1996 (1984). The Joy of Sets. Springer.
Abraham Fraenkel, Yehoshua Bar-Hillel, and Levy, Azriel, 1973 (1958). Foundations of Set Theory. North Holland.
Hatcher, William, 1982 (1968). The Logical Foundations of Mathematics. Pergamon.
Jech, Thomas, 2003. Set Theory: The Third Millenium Edition, Revised and Expanded. Springer. ISBN 3-540-44085-2.
Kunen, Kenneth, 1980. Set Theory: An Introduction to Independence Proofs. Elsevier. ISBN 0-444-86839-9.
Suppes, Patrick, 1972 (1960). Axiomatic Set Theory. Dover.
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 by Zermelo, Frankel, and Skolem bearing on ZFC.

External links

Metamath. An online project building a great deal of mathematics from first-order logic and ZFC. Principia Mathematica done right.
Stanford Encyclopedia of Philosophy: Set Theory -- by Thomas Jech.

Set theory | Z notation

Zermelo-Fraenkel-Mengenlehre | Axiomas de Zermelo-Fraenkel | ZFC | Teoria degli insiemi di Zermelo - Fraenkel | Aksjomaty Zermelo-Fraenkela

Gourt Home::Gourt :: Zermelo–Fraenkel set theory

Introduction

The axioms

See also

Bibliography

External links