Zermelo–Fraenkel set theory

From Exampleproblems

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.

Contents 1 Introduction 2 The Axioms 3 See also 4 Bibliography 5 External links

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 dyadic relation, set membership; that set a is a member of set b is written . 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, and hence was inadequate for all of ordinary mathematics. 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 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, it is customary to state that fact 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 axiom of replacement is in truth an axiom schema. In 1957, Richard Montague proved that ZF (and hence a fortiori ZFC) cannot be stated without invoking at least one axiom schema; ZFC cannot be finitely axiomatized. On the other hand, the rival 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 anything. 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.

ZFC is believed consistent. One thing is certain: ZFC is easily proved immune to the three great paradoxes of naive set theory, those of Russell, Burali-Forti, and Cantor. Nowadays, almost no one fears that an unsuspected contradiction can be derived from the ZFC axioms; if ZFC were inconsistent, that fact would have been uncovered by now. However the consistency of ZFC cannot be proved using ordinary mathematics, since its axioms are the basis of ordinary mathematics; this is a consequence of Gödel's second incompleteness theorem. On the other hand, the consistency of ZFC is provable if we assume something whose existence does not follow from ZFC: a weakly inaccessible cardinal.

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

• It is stronger than what is required for nearly all of everyday mathematics (both Saunders MacLane and Solomon Fefferman have made this point);
• Among rival set theories, it 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

The ZFC axioms are:

• Extensionality: Two sets are the same if and only if they have the same members.

  

• Empty Set: There exists a set with no members, called the empty set and denoted {}.

  

• Pairing: If x, y are sets, then there exists a set, denoted {x,y} or {x} ∪ {y}, whose sole members are x and y.

  

• Union: For any set x, there is a set y such that the elements of y are precisely the members of the members of x.

  

• Infinity: There exists a set x such that {} is a member of x ,and whenever y is in x, so is y ∪ {y}.

  

• Power Set: Given any set, its power set exists. That is, for any set x there exists a set y, such that the members of y are precisely the subsets of x.

  

• Regularity: Every non-empty set x contains some member y such that x and y are disjoint sets.

  

• Separation (or subset axiom): Given any set and any proposition P(x), there exists a subset of the original set containing precisely those members x for which P(x) holds. (This is an axiom schema.)

  

• Replacement: Given any set A and any functional mapping, defined as a dyadic relation P(x,y) such that P(x,y₁) and P(x,y₂) implies y₁ = y₂, there is a set containing precisely the images of the members of A. Colloquially, if the domain of a function is a set, its range is as well. (This is an axiom schema.)

  

• Choice: Given any set of pairwise disjoint non-empty sets, there exists a set that contains exactly one member from each of these non-empty sets.

  

  

The symbolic statements of Choice and Replacement are somewhat more concise than is usual in the literature, because they employ a device that, while definable in first order logic with identity, is not, strictly speaking, part of that logic: the uniqueness quantifier .

See also

• Axiomatic set theory
• Zermelo set theory
• Whitehead-Russell axioms
• List of statements undecidable in ZFC

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.
• Suppes, Patrick, 1972 (1960). Axiomatic Set Theory. Dover.
• 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. How to build up a great deal of mathematics using ZFC and first order logic.
• Stanford Encyclopedia of Philosophy: Set Theory by Thomas Jech.