Zermelo–Fraenkel set theory with the axiom of choice, commonly abbreviated
ZFC, is the standard form of axiomatic set theory and as such is the most common
foundation of mathematicsFoundations of mathematics is a term sometimes used for certain fields of mathematics, such as mathematical logic, axiomatic set theory, proof theory, model theory, type theory and recursion theory...
. It has a single primitive
ontologicalOntology is the philosophical study of the nature of being, existence or reality in general, as well as of the basic categories of being and their relations...
notion, that of a
hereditaryIn set theory, a hereditary set is a set all of whose elements are hereditary sets. That is, all elements of the set are themselves sets, as are all elements of the elements, and so on...
well-founded set, and a single ontological assumption, namely that all
individualAs commonly used, individual refers to a person or to any specific object in a collection. In the 15th century and earlier, and also today within the fields of statistics and metaphysics, individual means "indivisible", typically describing any numerically singular thing, but sometimes meaning "a...
s in the universe of discourse are such sets.
ZFC is a one-sorted theory in
first-order logicFirst-order logic is a formal logic used in mathematics, philosophy, linguistics, and computer science. It goes by many names, including: first-order predicate calculus, the lower predicate calculus, and predicate logic...
. The signature has equality and a single primitive
binary relationIn mathematics, a binary relation on a set A is a collection of ordered pairs of elements of A. In other words, it is a subset of the Cartesian product A2 = . More generally, a binary relation between two sets A and B is a subset of...
, set membership, which is usually denoted ∈. The formula
a ∈
b means that the set
a is a member of the set
b (which is also read, "
a is an element of
b" or "
a is in
b").
Most of the ZFC axioms state that particular sets exist. For example, the
axiom of pairingIn axiomatic set theory and the branches of logic, mathematics, and computer science that use it, the axiom of pairing is one of the axioms of Zermelo-Fraenkel set theory.- Formal statement :...
says that given any two sets
a and
b there is a new set {
a,
b} containing exactly
a and
b. Other axioms describe properties of set membership. A goal of the ZFC axioms is that each axiom should be true if interpreted as a statement about the collection of all sets in the
von Neumann universeIn set theory and related branches of mathematics, the von Neumann universe, or von Neumann hierarchy of sets, denoted V, is the class of well-founded sets...
(also known as the cumulative hierarchy).
The
metamathematicsMetamathematics is the study of mathematics itself using mathematical methods. This study produces metatheories, which are mathematical theories about other mathematical theories...
of ZFC has been extensively studied. Landmark results in this area established the independence of the
continuum hypothesisIn mathematics, the continuum hypothesis is a hypothesis, advanced by Georg Cantor in 1877, about the possible sizes of infinite sets. It states:Establishing the truth or falsehood of the continuum hypothesis is the first of Hilbert's twenty-three problems presented in the year 1900...
from ZFC, and of the
axiom of choiceIn mathematics, the axiom of choice, or AC, is an axiom of set theory. Informally put, the axiom of choice says that given any collection of bins, each containing at least one object, it is possible to make a selection of exactly one object from each bin, even if there are infinitely many bins and...
from the remaining ZFC axioms.
History
In 1908,
Ernst ZermeloErnst Friedrich Ferdinand Zermelo was a German mathematician, whose work has major implications for the foundations of mathematics and hence on philosophy.-Life:...
proposed the first axiomatic set theory,
Zermelo set theoryZermelo set theory, as set out in an important paper in 1908 by Ernst Zermelo, is the ancestor of modern set theory. It bears certain differences from its descendants, which are not always understood, and are frequently misquoted...
. This axiomatic theory did not allow the construction of the
ordinal numberIn set theory, an ordinal number, or just ordinal, is the order type of a well-ordered set. They are usually identified with hereditarily transitive sets. Ordinals are an extension of the natural numbers different from integers and from cardinals...
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 and
Thoralf SkolemThoralf Albert Skolem was a Norwegian mathematician known mainly for his work on mathematical logic and set theory.-Life:...
independently proposed operationalizing a "definite" property as one that could be formulated as a
first order theoryFirst-order logic is a formal logic used in mathematics, philosophy, linguistics, and computer science. It goes by many names, including: first-order predicate calculus, the lower predicate calculus, and predicate logic...
whose
atomic formulaIn mathematical logic, an atomic formula is a formula with no deeper propositional structure, that is, a formula that contains no logical connectives or equivalently a formula that has no strict subformulas. Atoms are thus the simplest well-formed formulas of the logic...
s were limited to set membership and identity. They also independently proposed replacing the
axiom schema of specificationIn axiomatic set theory and the branches of logic, mathematics, and computer science that use it, the axiom schema of specification, axiom schema of separation, subset axiom scheme or axiom schema of restricted comprehension, is a schema of axioms in Zermelo-Fraenkel set theory...
with the
axiom schema of replacementIn set theory, the axiom schema of replacement is a schema of axioms in Zermelo-Fraenkel set theory that asserts that the image of any set under any definable mapping is also a set...
. Appending this schema, as well as the
axiom of regularityIn mathematics, the axiom of regularity is one of the axioms of Zermelo-Fraenkel set theory and was introduced by...
(proposed by Zermelo in 1930), to Zermelo set theory yields the theory denoted by
ZF. Adding to ZF either the
axiom of choiceIn mathematics, the axiom of choice, or AC, is an axiom of set theory. Informally put, the axiom of choice says that given any collection of bins, each containing at least one object, it is possible to make a selection of exactly one object from each bin, even if there are infinitely many bins and...
(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 discourseThe domain of discourse, sometimes called the universe of discourse, logical discourse, or simply discourse, is an analytic tool used in deductive logic, especially predicate logic...
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. Axiom of extensionalityIn axiomatic set theory and the branches of logic, mathematics, and computer science that use it, the axiom of extensionality, or axiom of extension, is one of the axioms of Zermelo-Fraenkel set theory.- Formal statement :...
: Two sets are equal (are the same set) if they have the same elements.
The converse of this axiom follows from the substitution property of
equalityEquality, or more formally the identity relation, is the binary relation on a set X defined by .The identity relation is the paradigmatic example of the more general concept of an equivalence relation on a set: those binary relations which are reflexive, symmetric, and transitive. The relation of...
. If the background logic does not include equality "=",
x=
y may be defined as an abbreviation for the following formula (Hatcher 1982, p. 138, def. 1):
In this case, the axiom of extensionality can be reformulated as
which says that if
x and
y have the same elements, then they belong to the same sets (Fraenkel
et al. 1973).
2. Axiom of regularityIn mathematics, the axiom of regularity is one of the axioms of Zermelo-Fraenkel set theory and was introduced by...
(also called the
Axiom of foundation): Every non-empty set
x contains a member
y such that
x and
y are
disjoint setsIn mathematics and computer science, two sets are said to be disjoint if they have no element in common. For example, {1, 2, 3} and {4, 5, 6} are disjoint sets.- Explanation :...
.
3. Axiom schema of specificationIn axiomatic set theory and the branches of logic, mathematics, and computer science that use it, the axiom schema of specification, axiom schema of separation, subset axiom scheme or axiom schema of restricted comprehension, is a schema of axioms in Zermelo-Fraenkel set theory...
(also called the axiom schema of
separation or of
restricted comprehension): If
z is a set, and 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 avoid
Russell's paradoxIn the foundations of mathematics, Russell's paradox , discovered by Bertrand Russell in 1901, showed that the naive set theory of Frege leads to a contradiction....
and its variants. More formally, let be any formula in the language of ZFC with free variables among . So
y is not free in . Then:
This axiom is part of Z, but can be redundant in ZF, in that it may follow from the
axiom schema of replacementIn set theory, the axiom schema of replacement is a schema of axioms in Zermelo-Fraenkel set theory that asserts that the image of any set under any definable mapping is also a set...
, with (as here) or without the axiom of the empty set.
The axiom of specification can be used to prove the existence of the
empty setIn mathematics, and more specifically set theory, the empty set is the unique set having no members; its size is zero. Some axiomatic set theories assure that the empty set exists by including an axiom of empty set; in other theories, its existence can be deduced...
, denoted , 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.
If the background logic includes equality, it is also possible to define the empty set as.
Thus the axiom 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 a definitional extension that adds the symbol to the language of ZFC.
4. Axiom of pairingIn axiomatic set theory and the branches of logic, mathematics, and computer science that use it, the axiom of pairing is one of the axioms of Zermelo-Fraenkel set theory.- Formal statement :...
: If
x and
y are sets, then there exists a set which contains
x and
y as elements.
This axiom is part of Z, but is redundant in ZF because it follows from the
axiom schema of replacementIn set theory, the axiom schema of replacement is a schema of axioms in Zermelo-Fraenkel set theory that asserts that the image of any set under any definable mapping is also a set...
applied to any two-member set. The existence of such a set is assured by either the
axiom of infinityIn axiomatic set theory and the branches of logic, mathematics, and computer science that use it, the axiom of infinity is one of the axioms of Zermelo-Fraenkel set theory...
, or by the axiom of the power set applied twice to the empty set.
5. Axiom of unionIn axiomatic set theory and the branches of logic, mathematics, and computer science that use it, the axiom of union is one of the axioms of Zermelo-Fraenkel set theory, stating that, for any set x there is a set y whose elements are precisely the elements of the elements of x...
: For any set there is a set
A containing every set that is a member of some member of
6. Axiom schema of collection: Let be any formula in the language of ZFC whose free variables are among . So
B is not free in . is a quantifier binding
y, meaning that exactly one exists, up to equality. Then:
Less formally, this axiom states that if the
domainIn mathematics, the domain of a given functionis the set of "input" values for which the function is defined. For instance, the domain of cosine would be all real numbers, while the domain of the square root would be only numbers greater than or equal to 0...
of a function
f is a set, and
f(
x) is a set for any
x in that domain, then the
rangeIn mathematics, the range of a function is the set of all "output" values produced by f.Sometimes it is called the image, or more precisely, the image of the domain of the function. If a function is a surjection then its range is equal to its codomain...
of
f is a subclass of a set, subject to a restriction needed to avoid paradoxes.
7. Axiom of infinityIn axiomatic set theory and the branches of logic, mathematics, and computer science that use it, the axiom of infinity is one of the axioms of Zermelo-Fraenkel set theory...
: Let abbreviate , where is some set. Then there exists a set
X such that the empty set is a member of
X and, whenever a set
y is a member of
X, then is also a member of
X.
More colloquially, there exists a set
X having infinitely many members. The minimal set
X satisfying the axiom of infinity is the von Neumann ordinal ω.
8. Axiom of power setIn mathematics, the axiom of power set is one of the Zermelo-Fraenkel axioms of axiomatic set theory.In the formal language of the Zermelo-Fraenkel axioms, the axiom reads:where P stands for the power set, , of A. In English, this says:...
: Let abbreviate For any set
x, there is a set
y which is a
supersetSuperSet Software was a group founded by friends and former Eyring Research Institute co-workers Drew Major, Dale Neibaur, Kyle Powell and later joined by Mark Hurst...
of the
power setIn mathematics, given a set S, the power set of S, written , P, ℘ or 2
S, is the set of all subsets of S. In axiomatic set theory In mathematics, given a set S, the power set (or powerset) of S, written , P(S), ℘(S) or 2
S, is the set of all subsets of S. In...
of
x. The power set of
x is the class whose members are all of the subsets of
x.
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 existsIn axiomatic set theory, the axiom of empty set is an axiom of Zermelo–Fraenkel set theory, the fragment thereof Burgess calls ST, and Kripke–Platek set theory.- Formal statement :In the formal language of the Zermelo–Fraenkel axioms, the axiom reads:...
. 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. Well-ordering theoremIn Mathematics, the well-ordering theorem states that every set can be well-ordered. This is known as the Zermelo's theorem and is equivalent to the Axiom of Choice as a result of a theorem which states that if every set can be well ordered, then for every set there exists a choice function.Ernst...
: For any set
X, there is a
binary relationIn mathematics, a binary relation on a set A is a collection of ordered pairs of elements of A. In other words, it is a subset of the Cartesian product A2 = . More generally, a binary relation between two sets A and B is a subset of...
R which well-orders
X. This means
R is a linear order on
X such that every nonempty
subsetIn mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. Notice that A and B may coincide...
of
X has a member which is minimal under
R.
Given axioms
1-8, there are many statements provably equivalent to axiom
9, the best known of which is the
axiom of choiceIn mathematics, the axiom of choice, or AC, is an axiom of set theory. Informally put, the axiom of choice says that given any collection of bins, each containing at least one object, it is possible to make a selection of exactly one object from each bin, even if there are infinitely many bins and...
(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
domainIn mathematics, the domain of a given functionis the set of "input" values for which the function is defined. For instance, the domain of cosine would be all real numbers, while the domain of the square root would be only numbers greater than or equal to 0...
is
X, and whose
rangeIn mathematics, the range of a function is the set of all "output" values produced by f.Sometimes it is called the image, or more precisely, the image of the domain of the function. If a function is a surjection then its range is equal to its codomain...
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 a
finite setIn mathematics, finite set is a set that has a finite number of elements. For example,is a finite set with five elements. The number of elements of a finite set is a natural number , and is called the cardinality of the set. A set that is not finite is called infinite...
is easily proved from axioms
1-8, AC only matters for certain
infinite setIn set theory, an infinite set is a set that is not a finite set. Infinite sets may be countable or uncountable. Some examples are:* the set of all integers, {..., -1, 0, 1, 2, ...}, is a countably infinite set; and...
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.
Motivation via the cumulative hierarchy
One motivation for the ZFC axioms is the cumulative hierarchy of sets introduced by
John von NeumannJohn von Neumann was a Hungarian American mathematician who made major contributions to a vast range of fields, including set theory, functional analysis, quantum mechanics, ergodic theory, continuous geometry, economics and game theory, computer science, numerical analysis, hydrodynamics John...
(Shoenfield 1977, sec. 2). In this viewpoint, the universe of set theory is built up in stages, with one stage for each
ordinal numberIn set theory, an ordinal number, or just ordinal, is the order type of a well-ordered set. They are usually identified with hereditarily transitive sets. Ordinals are an extension of the natural numbers different from integers and from cardinals...
. At stage 0 there are no sets yet. At each following stage, a set is added to the universe if all of its elements have been added at previous stages. Thus the empty set is added at stage 1, and the set containing the empty set is added at stage 2; see Hinman (2005, p. 467). The collection of all sets that are obtained in this way, over all the stages, is known as V. The sets in V can be arranged into a hierarchy by assigning to each set the first stage at which that set was added to V.
It is provable that a set is in V if and only if the set is pure and well-founded; and provable that V satisfies all the axioms of ZFC, if the class of ordinals has appropriate reflection properties. For example, suppose that a set
x is added at stage α, which means that every element of
x was added at a stage earlier than α. Then every subset of
x is also added at stage α, because all elements of any subset of
x were also added before stage α. This means that any subset of
x which the axiom of separation can construct is added at stage α, and that the powerset of
x will be added at the next stage after α. For a complete argument that V satisfies ZFC see Shoenfield (1977).
The picture of the universe of sets stratified into the cumulative hierarchy is characteristic of ZFC and related axiomatic set theories such as
Von Neumann–Bernays–Gödel set theoryIn the foundations of mathematics, Von Neumann–Bernays–Gödel set theory is an axiomatic set theory that is a conservative extension of the canonical axiomatic set theory ZFC. A statement in the language of ZFC is provable in NBG if and only if it is provable in ZFC. The ontology of NBG includes...
(often called NBG) and
Morse–Kelley set theoryIn the foundation of mathematics, Kelley–Morse or Morse–Kelley set theory is a first order axiomatic set theory that is closely related to Von Neumann–Bernays–Gödel set theory . MK allows the bound variables in the schematic formula appearing in the axiom schema of Class Comprehension to range...
. The cumulative hierarchy is not compatible with other set theories such as
New FoundationsIn mathematical logic, New Foundations is an axiomatic set theory, conceived by Willard Van Orman Quine as a simplification of the theory of types of Principia Mathematica. Quine first proposed NF in a 1937 article titled "New Foundations for Mathematical Logic"; hence the name...
.
It is possible to change the definition of V so that at each stage, instead of adding all the subsets of the union of the previous stages, subsets are only added if they are definable in a certain sense. This results in a more "narrow" hierarchy which gives the
constructible universeIn mathematics, the constructible universe , denoted L, is a particular class of sets which can be described entirely in terms of simpler sets. It was introduced by Kurt Gödel in his 1938 paper "The Consistency of the Axiom of Choice and of the Generalized Continuum-Hypothesis"...
L, which also satisfies all the axioms of ZFC, including the axiom of choice. It is independent from the ZFC axioms whether V = L. Although the structure of L is more regular and well behaved than that of V, few mathematicians argue that V = L should be added to ZFC as an additional axiom.
Metamathematics
The axiom schemata of replacement and separation each contain infinitely many instances.
MontagueRichard Merett Montague was an American mathematician and philosopher.-Career:...
(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 theoryIn the foundations of mathematics, Von Neumann–Bernays–Gödel set theory is an axiomatic set theory that is a conservative extension of the canonical axiomatic set theory ZFC. A statement in the language of ZFC is provable in NBG if and only if it is provable in ZFC. The ontology of NBG includes...
(NBG) can be finitely axiomatized. The ontology of NBG includes
proper classesIn set theory and its applications throughout mathematics, a class is a collection of sets which can be unambiguously defined by a property that all its members share. The precise definition of "class" depends on foundational context...
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 any
theoremIn mathematics, a theorem is a statement proved on the basis of previously accepted or established statements such as axioms. In formal mathematical logic, the concept of a theorem may be taken to mean a formula that can be derived according to the derivation rules of a fixed formal system.In...
not mentioning classes and provable in one theory can be proved in the other.
Gödel's second incompleteness theorem says that a recursively axiomatizable system that can interpret
Robinson arithmeticIn mathematics, Robinson arithmetic, or Q, is a finitely axiomatized fragment of Peano arithmetic , first set out in Robinson . Q is essentially PA without the axiom schema of induction...
can prove its own consistency only if it is inconsistent. Moreover, Robinson arithmetic can be interpreted in
general set theoryGeneral set theory is George Boolos's name for a fragment of the canonical axiomatic set theory Z. GST is sufficient for all mathematics not requiring infinite sets, and is the weakest known set theory whose theorems include the Peano axioms....
, a small fragment of ZFC. Hence the
consistencyIn logic, a consistent theory is one that does not contain a contradiction. The lack of contradiction can be defined in either semantic or syntactic terms. The semantic definition states that a theory is consistent if it has a model; this is the sense used in traditional Aristotelian logic,...
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 weakly
inaccessible cardinalIn set theory, an uncountable regular cardinal number is called weakly inaccessible if it is a weak limit cardinal, and strongly inaccessible, or just inaccessible, if it is a strong limit 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 of
naive set theoryNaive set theory is one of several theories of sets used in the discussion of the foundations of mathematics. The informal content of this naive set theory supports both the aspects of mathematical sets familiar in discrete mathematics , and the everyday usage of set theory concepts in most...
:
Russell's paradoxIn the foundations of mathematics, Russell's paradox , discovered by Bertrand Russell in 1901, showed that the naive set theory of Frege leads to a contradiction....
, the
Burali-Forti paradoxIn set theory, a field of mathematics, the Burali-Forti paradox demonstrates that naively constructing "the set of all ordinal numbers" leads to a contradiction and therefore shows an antinomy in a system that allows its construction...
, and
Cantor's paradoxIn set theory, Cantor's paradox is derivable from the theorem that there is no greatest cardinal number, so that the collection of "infinite sizes" is itself infinite...
.
Abian and LaMacchia (1978) studied a subtheory of ZFC consisting of the axioms of extensionality, union, powerset, replacement, and choice. Using
modelsIn mathematics, model theory is the study of mathematical structures such as groups, fields, graphs, or even universes of set theory, using tools from mathematical logic. A structure that gives meaning to the sentences of a formal language is called a model for the language...
, they proved this subtheory consistent, and proved that each of the axioms of extensionality, replacement, and power set is independent of the four remaining axioms of this subtheory. If this subtheory 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 theoryNon-well founded set theories are variants of axiomatic set theory which allow sets to contain themselves and otherwise violate the rule of well-foundedness...
is a
modelIn mathematics, model theory is the study of mathematical structures such as groups, fields, graphs, or even universes of set theory, using tools from mathematical logic. A structure that gives meaning to the sentences of a formal language is called a model for the language...
of ZFC without the axiom of regularity, that axiom is independent of the other ZFC axioms.
If consistent, ZFC cannot prove the existence of the
inaccessible cardinalIn set theory, an uncountable regular cardinal number is called weakly inaccessible if it is a weak limit cardinal, and strongly inaccessible, or just inaccessible, if it is a strong limit cardinal...
s that
category theoryIn mathematics, category theory deals in an abstract way with mathematical structures and relationships between them: it abstracts from sets and functions to objects linked in diagrams by morphisms or arrows....
requires. Huge sets of this nature are possible if ZF is augmented with
Tarski's axiomTarski–Grothendieck set theory is an axiomatic set theory that was introduced as part of the Mizar system for formal verification of proofs...
(Tarski 1939). Assuming that axiom turns the axioms of
infinityIn axiomatic set theory and the branches of logic, mathematics, and computer science that use it, the axiom of infinity is one of the axioms of Zermelo-Fraenkel set theory...
and
choiceIn mathematics, the axiom of choice, or AC, is an axiom of set theory. Informally put, the axiom of choice says that given any collection of bins, each containing at least one object, it is possible to make a selection of exactly one object from each bin, even if there are infinitely many bins and...
(
7 and
9 above) into theorems.
Independence in ZFC
Many important statements are independent of ZFC (see
list of statements undecidable in ZFC). The independence is usually proved by
forcingIn the mathematical discipline of set theory, forcing is a technique invented by Paul Cohen for proving consistency and independence results. It was first used, in 1962, to prove the independence of the continuum hypothesis and the axiom of choice from Zermelo–Fraenkel set theory...
, whereby it is shown that every countable transitive
modelIn mathematics, model theory is the study of mathematical structures such as groups, fields, graphs, or even universes of set theory, using tools from mathematical logic. A structure that gives meaning to the sentences of a formal language is called a model for the language...
of ZFC (sometimes augmented with large cardinal axioms) 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 particular
inner modelIn mathematical logic, suppose T is a theory in the languageof set theory.If M is a model of describing a set theory and N is a class of M such that...
s, such as in the
constructible universeIn mathematics, the constructible universe , denoted L, is a particular class of sets which can be described entirely in terms of simpler sets. It was introduced by Kurt Gödel in his 1938 paper "The Consistency of the Axiom of Choice and of the Generalized Continuum-Hypothesis"...
. However, some statements that are true about constructible sets are not consistent with hypothesized large cardinal axioms.
Forcing proves that the following statements are independent of ZFC:
- Continuum hypothesis
In mathematics, the continuum hypothesis is a hypothesis, advanced by Georg Cantor in 1877, about the possible sizes of infinite sets. It states:Establishing the truth or falsehood of the continuum hypothesis is the first of Hilbert's twenty-three problems presented in the year 1900...
- Diamond principle
In mathematics, and particularly in axiomatic set theory, is a certain family of combinatorial principles.- Definition :For a given cardinal number and a stationary set , the statement is the statement that there is a sequence such that...
- Suslin hypothesis
In mathematics, Suslin's problem is a question about totally ordered sets posed by Mikhail Yakovlevich Suslin in the early 1920s.It has been shown to be independent of the standard axiomatic system of set theory known as ZFC: the statement can neither be proven nor disproven from those axioms.In...
- Kurepa hypothesis
In set theory, a Kurepa tree is a tree of height , each of whose levels is at most countable, and has at least many branches. It was named after Yugoslav mathematician Đuro Kurepa. The existence of a Kurepa tree is independent of the axioms of ZFC. As Solovay showed, there are Kurepa trees in...
- Martin's axiom
In the mathematical field of set theory, Martin's axiom, named after Donald A. Martin, is a statement which is independent of the usual axioms of ZFC set theory. It is implied by the continuum hypothesis, so certainly consistent with ZFC, but is also known to be consistent with...
(which is not a ZFC axiom)
- Axiom of Constructibility (V=L)
The axiom of constructibility is a possible axiom for set theory in mathematics that asserts that every set is constructible. The axiom is usually written as "V = L", where V and L denote the von Neumann universe and the constructible universe, respectively.- Implications :The axiom of...
(which is also not a ZFC axiom).
Remarks:
- The consistency of V=L is provable by inner model
In mathematical logic, suppose T is a theory in the languageof set theory.If M is a model of describing a set theory and N is a class of M such that...
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.
- The constructible universe
In mathematics, the constructible universe , denoted L, is a particular class of sets which can be described entirely in terms of simpler sets. It was introduced by Kurt Gödel in his 1938 paper "The Consistency of the Axiom of Choice and of the Generalized Continuum-Hypothesis"...
satisfies the Generalized Continuum Hypothesis, the Diamond Principle, Martin's Axiom and the Kurepa Hypothesis.
A variation on the method of
forcingIn the mathematical discipline of set theory, forcing is a technique invented by Paul Cohen for proving consistency and independence results. It was first used, in 1962, to prove the independence of the continuum hypothesis and the axiom of choice from Zermelo–Fraenkel set theory...
can also be used to demonstrate the consistency and unprovability of the
axiom of choiceIn mathematics, the axiom of choice, or AC, is an axiom of set theory. Informally put, the axiom of choice says that given any collection of bins, each containing at least one object, it is possible to make a selection of exactly one object from each bin, even if there are infinitely many bins and...
, 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 (provided that ZFC is, in fact, consistent). 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 and second order arithmetic (as explored by the program of
reverse mathematicsReverse mathematics is a program in mathematical logic that seeks to determine which axioms are required to prove theorems of mathematics. The method can briefly be described as "going backwards from the theorems to the axioms." This contrasts with the ordinary mathematical practice of deriving...
).
Saunders Mac LaneSaunders Mac Lane was an American mathematician who cofounded category theory with Samuel Eilenberg.-Career:...
and
Solomon FefermanSolomon Feferman is an American philosopher and mathematician with major works in mathematical logic.He was born in New York City, New York, and received his Ph.D. in 1957 from the University of California, Berkeley under Alfred Tarski...
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 theoryZermelo set theory, as set out in an important paper in 1908 by Ernst Zermelo, is the ancestor of modern set theory. It bears certain differences from its descendants, which are not always understood, and are frequently misquoted...
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. Unlike
New FoundationsIn mathematical logic, New Foundations is an axiomatic set theory, conceived by Willard Van Orman Quine as a simplification of the theory of types of Principia Mathematica. Quine first proposed NF in a 1937 article titled "New Foundations for Mathematical Logic"; hence the name...
, ZFC does not admit the existence of a
universal setIn set theory, a universal set is a set which contains all objects, including itself. The most widely-studied set theory with a universal set is Willard Van Orman Quine’s New Foundations, but Alonzo Church and Arnold Oberschelp also published work on such set theories...
. Hence the
universeThe Universe comprises everything that physically exists, the entirety of space and time, all forms of matter and energy, and the physical laws and constants that govern them...
of sets under ZFC is not closed under the elementary operations of the
algebra of setsThe algebra of sets develops and describes the basic properties and laws of sets, the set-theoretic operations of union, intersection, and complementation and the relations of set equality and set inclusion...
. Unlike
von Neumann–Bernays–Gödel set theoryIn the foundations of mathematics, Von Neumann–Bernays–Gödel set theory is an axiomatic set theory that is a conservative extension of the canonical axiomatic set theory ZFC. A statement in the language of ZFC is provable in NBG if and only if it is provable in ZFC. The ontology of NBG includes...
and
Morse–Kelley set theoryIn the foundation of mathematics, Kelley–Morse or Morse–Kelley set theory is a first order axiomatic set theory that is closely related to Von Neumann–Bernays–Gödel set theory . MK allows the bound variables in the schematic formula appearing in the axiom schema of Class Comprehension to range...
(MK), ZFC does not admit the existence of proper classes. These
ontologicalOntology is the philosophical study of the nature of being, existence or reality in general, as well as of the basic categories of being and their relations...
restrictions are required for ZFC to avoid
Russell's paradoxIn the foundations of mathematics, Russell's paradox , discovered by Bertrand Russell in 1901, showed that the naive set theory of Frege leads to a contradiction....
, 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 the
axiom of choiceIn mathematics, the axiom of choice, or AC, is an axiom of set theory. Informally put, the axiom of choice says that given any collection of bins, each containing at least one object, it is possible to make a selection of exactly one object from each bin, even if there are infinitely many bins and...
included in ZFC is weaker than the
axiom of global choiceIn class theories, the axiom of global choice is a stronger variant of the axiom of choice which applies to proper classes as well as sets.- Statement :The axiom can be expressed in various ways which are equivalent:...
included in MK.
There are numerous
mathematical statements undecidable in ZFC. These include the
continuum hypothesisIn mathematics, the continuum hypothesis is a hypothesis, advanced by Georg Cantor in 1877, about the possible sizes of infinite sets. It states:Establishing the truth or falsehood of the continuum hypothesis is the first of Hilbert's twenty-three problems presented in the year 1900...
, the
Whitehead problemIn group theory, a branch of abstract algebra, the Whitehead problem is the following question:Shelah proved that Whitehead's problem was undecidable within standard ZFC set theory.-Refinement:...
, and the
Normal Moore space conjectureIn mathematics, particularly topology, a Moore space is a topological space satisfying an axiom that may be thought of as a separation axiom. In fact, Moore spaces are generally interesting in mathematics because they may be applied to prove interesting metrization theorems. The concept of a Moore...
. Some of these conjectures are provable with the addition of axioms such as
Martin's axiomIn the mathematical field of set theory, Martin's axiom, named after Donald A. Martin, is a statement which is independent of the usual axioms of ZFC set theory. It is implied by the continuum hypothesis, so certainly consistent with ZFC, but is also known to be consistent with...
, large cardinal axioms to ZFC. Some others are decided in ZF+AD where AD is the
axiom of determinacyThe axiom of determinacy is a possible axiom for set theory introduced Jan Mycielski and Hugo Steinhaus. It refers to certain two-person games of length ω with perfect information...
, a strong supposition incompatible with choice. One attraction of large cardinal axioms is that they enable many results from ZF+AD to be established in ZFC adjoined by some large cardinal axiom (see projective determinacy). The
Mizar systemThe Mizar system consists of a language for writing strictly formalized mathematical definitions and proofs, a computer program which is able to check proofs written in this language, and a library of definitions and proved theorems which can be referenced and used in new articles...
has adopted
Tarski-Grothendieck set theoryTarski–Grothendieck set theory is an axiomatic set theory that was introduced as part of the Mizar system for formal verification of proofs...
instead of ZFC so that proofs involving
Grothendieck universeIn mathematics, a Grothendieck universe is a set U with the following properties:# If x is an element of U and if y is an element of x, then y is also an element of U...
s (encountered in category theory and algebraic geometry) can be formalized.
See also
- Foundation of mathematics
- Inner model
In mathematical logic, suppose T is a theory in the languageof set theory.If M is a model of describing a set theory and N is a class of M such that...
- Large cardinal axiom
- Non-well-founded set theory
Non-well founded set theories are variants of axiomatic set theory which allow sets to contain themselves and otherwise violate the rule of well-foundedness...
Related axiomatic set theories:
- Morse-Kelley set theory
- Von Neumann-Bernays-Gödel set theory
- Tarski-Grothendieck set theory
Tarski–Grothendieck set theory is an axiomatic set theory that was introduced as part of the Mizar system for formal verification of proofs...
- Constructive set theory
Constructive set theory is an approach to mathematical constructivism following the program of axiomatic set theory. That is, it uses the usual first-order language of classical set theory, and although of course the logic is constructive, there is no explicit use of constructive types...
External links
- Stanford Encyclopedia of Philosophy
The Stanford Encyclopedia of Philosophy is a freely-accessible online encyclopedia of philosophy maintained by Stanford University. Each entry is written and maintained by an expert in the field, including professors from over 65 academic institutions worldwide...
articles by Thomas JechThomas J. Jech is a mathematician specializing in set theory who was at Penn State for more than 25 years. He was educated at Charles University and is now at the of the Academy of Sciences of the Czech Republic.-Books:* Lectures in set theory, Springer-Verlag Lecture Notes in Mathematics 217 ...
:
- Metamath version of the ZFC axioms — A concise and nonredundant axiomatization. The background first order logic is defined especially to facilitate machine verification of proofs.
- A derivation in Metamath of a version of the separation schema from a version of the replacement schema.