HOME

TheInfoList



OR:

In
set theory Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, is mostly concern ...
, Zermelo–Fraenkel set theory, named after mathematicians
Ernst Zermelo Ernst Friedrich Ferdinand Zermelo (, ; 27 July 187121 May 1953) was a German logician and mathematician, whose work has major implications for the foundations of mathematics. He is known for his role in developing Zermelo–Fraenkel axiomatic ...
and Abraham Fraenkel, is an axiomatic system that was proposed in the early twentieth century in order to formulate a theory of sets free of paradoxes such as Russell's paradox. Today, Zermelo–Fraenkel set theory, with the historically controversial
axiom of choice In mathematics, the axiom of choice, or AC, is an axiom of set theory equivalent to the statement that ''a Cartesian product of a collection of non-empty sets is non-empty''. Informally put, the axiom of choice says that given any collection ...
(AC) included, is the standard form of
axiomatic set theory Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, is mostly concern ...
and as such is the most common foundation of mathematics. Zermelo–Fraenkel set theory with the axiom of choice included is abbreviated ZFC, where C stands for "choice", and ZF refers to the axioms of Zermelo–Fraenkel set theory with the axiom of choice excluded. Informally, Zermelo–Fraenkel set theory is intended to formalize a single primitive notion, that of a
hereditary Heredity, also called inheritance or biological inheritance, is the passing on of traits from parents to their offspring; either through asexual reproduction or sexual reproduction, the offspring cells or organisms acquire the genetic informa ...
well-founded
set Set, The Set, SET or SETS may refer to: Science, technology, and mathematics Mathematics *Set (mathematics), a collection of elements *Category of sets, the category whose objects and morphisms are sets and total functions, respectively Electro ...
, so that all
entities An entity is something that exists as itself, as a subject or as an object, actually or potentially, concretely or abstractly, physically or not. It need not be of material existence. In particular, abstractions and legal fictions are usually re ...
in the universe of discourse are such sets. Thus the
axiom An axiom, postulate, or assumption is a statement that is taken to be true, to serve as a premise or starting point for further reasoning and arguments. The word comes from the Ancient Greek word (), meaning 'that which is thought worthy or ...
s of Zermelo–Fraenkel set theory refer only to pure sets and prevent its
models A model is an informative representation of an object, person or system. The term originally denoted the plans of a building in late 16th-century English, and derived via French and Italian ultimately from Latin ''modulus'', a measure. Models c ...
from containing
urelement In set theory, a branch of mathematics, an urelement or ur-element (from the German prefix ''ur-'', 'primordial') is an object that is not a set, but that may be an element of a set. It is also referred to as an atom or individual. Theory There ...
s (elements of sets that are not themselves sets). Furthermore, proper classes (collections of mathematical objects defined by a property shared by their members where the collections are too big to be sets) can only be treated indirectly. Specifically, Zermelo–Fraenkel set theory does not allow for the existence of a universal set (a set containing all sets) nor for unrestricted comprehension, thereby avoiding Russell's paradox. Von Neumann–Bernays–Gödel set theory (NBG) is a commonly used conservative extension of Zermelo–Fraenkel set theory that does allow explicit treatment of proper classes. There are many equivalent formulations of the axioms of Zermelo–Fraenkel set theory. Most of the axioms state the existence of particular sets defined from other sets. For example, the
axiom of pairing In 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. It was introduced by as a special case of his axiom of elementary set ...
says that given any two sets a and b there is a new set \ containing exactly a and b. Other axioms describe properties of set membership. A goal of the axioms is that each axiom should be true if interpreted as a statement about the collection of all sets in the von Neumann universe (also known as the cumulative hierarchy). Formally, ZFC is a one-sorted theory in first-order logic. The
signature A signature (; from la, signare, "to sign") is a Handwriting, handwritten (and often Stylization, stylized) depiction of someone's name, nickname, or even a simple "X" or other mark that a person writes on documents as a proof of identity and ...
has equality and a single primitive
binary relation In mathematics, a binary relation associates elements of one set, called the ''domain'', with elements of another set, called the ''codomain''. A binary relation over sets and is a new set of ordered pairs consisting of elements in and in ...
, intended to formalize
set membership In mathematics, an element (or member) of a set is any one of the distinct objects that belong to that set. Sets Writing A = \ means that the elements of the set are the numbers 1, 2, 3 and 4. Sets of elements of , for example \, are subsets o ...
, which is usually denoted \in. The
formula In science, a formula is a concise way of expressing information symbolically, as in a mathematical formula or a ''chemical formula''. The informal use of the term ''formula'' in science refers to the general construct of a relationship betwe ...
a\in 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"). The
metamathematics Metamathematics is the study of mathematics itself using mathematical methods. This study produces metatheories, which are mathematical theories about other mathematical theories. Emphasis on metamathematics (and perhaps the creation of the ter ...
of Zermelo–Fraenkel set theory has been extensively studied. Landmark results in this area established the
logical independence In mathematical logic, independence is the unprovability of a sentence from other sentences. A sentence σ is independent of a given first-order theory ''T'' if ''T'' neither proves nor refutes σ; that is, it is impossible to prove σ from ''T' ...
of the axiom of choice from the remaining Zermelo-Fraenkel axioms (see ) and of the continuum hypothesis from ZFC. The consistency of a theory such as ZFC cannot be proved within the theory itself, as shown by Gödel's second incompleteness theorem.


History

The modern study of
set theory Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, is mostly concern ...
was initiated by
Georg Cantor Georg Ferdinand Ludwig Philipp Cantor ( , ;  – January 6, 1918) was a German mathematician. He played a pivotal role in the creation of set theory, which has become a fundamental theory in mathematics. Cantor established the importance o ...
and Richard Dedekind in the 1870s. However, the discovery of paradoxes in
naive set theory Naive set theory is any of several theories of sets used in the discussion of the foundations of mathematics. Unlike axiomatic set theories, which are defined using formal logic, naive set theory is defined informally, in natural language. It ...
, such as Russell's paradox, led to the desire for a more rigorous form of set theory that was free of these paradoxes. In 1908,
Ernst Zermelo Ernst Friedrich Ferdinand Zermelo (, ; 27 July 187121 May 1953) was a German logician and mathematician, whose work has major implications for the foundations of mathematics. He is known for his role in developing Zermelo–Fraenkel axiomatic ...
proposed the first
axiomatic set theory Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, is mostly concern ...
, Zermelo set theory. However, as first pointed out by Abraham Fraenkel in a 1921 letter to Zermelo, this theory was incapable of proving the existence of certain sets and
cardinal number In mathematics, cardinal numbers, or cardinals for short, are a generalization of the natural numbers used to measure the cardinality (size) of sets. The cardinality of a finite set is a natural number: the number of elements in the set. ...
s whose existence was taken for granted by most set theorists of the time, notably the cardinal number \aleph_ and the set \, where Z_ is any infinite set and \mathcal is the
power set In mathematics, the power set (or powerset) of a set is the set of all subsets of , including the empty set and itself. In axiomatic set theory (as developed, for example, in the ZFC axioms), the existence of the power set of any set is post ...
operation. Moreover, one of Zermelo's axioms invoked a concept, that of a "definite" property, whose operational meaning was not clear. In 1922, Fraenkel and Thoralf Skolem independently proposed operationalizing a "definite" property as one that could be formulated as a well-formed formula in a first-order logic whose atomic formulas were limited to set membership and identity. They also independently proposed replacing the axiom schema of specification with the axiom schema of replacement. Appending this schema, as well as the
axiom of regularity In mathematics, the axiom of regularity (also known as the axiom of foundation) is an axiom of Zermelo–Fraenkel set theory that states that every non-empty set ''A'' contains an element that is disjoint from ''A''. In first-order logic, the a ...
(first proposed by
John von Neumann John von Neumann (; hu, Neumann János Lajos, ; December 28, 1903 – February 8, 1957) was a Hungarian-American mathematician, physicist, computer scientist, engineer and polymath. He was regarded as having perhaps the widest c ...
), to Zermelo set theory yields the theory denoted by ZF. Adding to ZF either the
axiom of choice In mathematics, the axiom of choice, or AC, is an axiom of set theory equivalent to the statement that ''a Cartesian product of a collection of non-empty sets is non-empty''. Informally put, the axiom of choice says that given any collection ...
(AC) or a statement that is equivalent to it yields ZFC.


Axioms

There are many equivalent formulations of the ZFC axioms; for a discussion of this see . The following particular axiom set is from . 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 that directly asserts the existence of a set, in addition to the axioms given below (although he notes that he does so only "for emphasis"). Its omission here can be justified in two ways. First, in the standard semantics of first-order logic in which ZFC is typically formalized, the
domain of discourse In the formal sciences, the domain of discourse, also called the universe of discourse, universal set, or simply universe, is the set of entities over which certain variables of interest in some formal treatment may range. Overview The doma ...
must be nonempty. Hence, it is a logical theorem of first-order logic that something exists — usually expressed as the assertion that something is identical to itself, \exists x ( x = x ). Consequently, it is a theorem of every first-order theory that something exists. However, as noted above, because in the intended semantics of ZFC there are only sets, the interpretation of this logical theorem in the context of ZFC is that some ''set'' exists. Hence, there is no need for a separate axiom asserting that a set exists. Second, however, even if ZFC is formulated in so-called
free logic A free logic is a logic with fewer existential presuppositions than classical logic. Free logics may allow for terms that do not denote any object. Free logics may also allow models that have an empty domain. A free logic with the latter propert ...
, in which it is not provable from logic alone that something exists, the axiom of infinity (below) asserts that an ''infinite'' set exists. This implies that ''a'' set exists and so, once again, it is superfluous to include an axiom asserting as much.


1. Axiom of extensionality

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 an abbreviation for the following formula: \forall z \in x \Leftrightarrow z \in y\land \forall w \in w \Leftrightarrow y \in w In this case, the axiom of extensionality can be reformulated as : \forall x \forall y forall z (z \in x \Leftrightarrow z \in y) \Rightarrow \forall w (x \in w \Leftrightarrow y \in w) which says that if x and y have the same elements, then they belong to the same sets.


2. Axiom of regularity (also called the axiom of foundation)

Every non-empty set x contains a member y such that x and y are
disjoint sets In mathematics, two sets are said to be disjoint sets if they have no element in common. Equivalently, two disjoint sets are sets whose intersection is the empty set.. For example, and are ''disjoint sets,'' while and are not disjoint. A ...
. : \forall x exists a ( a \in x) \Rightarrow \exists y ( y \in x \land \lnot \exists z (z \in y \land z \in x)) or in modern notation: \forall x\,(x \neq \varnothing \Rightarrow \exists y (y \in x \land y \cap x = \varnothing)). This (along with the Axiom of Pairing) implies, for example, that no set is an element of itself and that every set has an ordinal
rank Rank is the relative position, value, worth, complexity, power, importance, authority, level, etc. of a person or object within a ranking, such as: Level or position in a hierarchical organization * Academic rank * Diplomatic rank * Hierarchy * ...
.


3. Axiom schema of specification (also called the axiom schema of separation or of restricted comprehension)

Subsets are commonly constructed using
set builder notation In set theory and its applications to logic, mathematics, and computer science, set-builder notation is a mathematical notation for describing a set by enumerating its elements, or stating the properties that its members must satisfy. Def ...
. For example, the even integers can be constructed as the subset of the integers \mathbb satisfying the congruence modulo predicate x \equiv 0 \pmod 2: : \. In general, the subset of a set z obeying a formula \varphi(x) with one free variable x may be written as: : \. The axiom schema of specification states that this subset always exists (it is an axiom ''schema'' because there is one axiom for each \varphi). Formally, let \varphi be any formula in the language of ZFC with all free variables among x,z,w_,\ldots,w_ (y is not free in \varphi). Then: : \forall z \forall w_1 \forall w_2\ldots \forall w_n \exists y \forall x \in y \Leftrightarrow (( x \in z )\land \varphi(x,w_1,w_2,...,w_n,z) ) Note that the axiom schema of specification can only construct subsets, and does not allow the construction of entities of the more general form: : \. This restriction is necessary to avoid Russell's paradox (let y=\ then y \in y \Leftrightarrow y \notin y) and its variants that accompany naive set theory with unrestricted comprehension. In some other axiomatizations of ZF, this axiom is redundant in that it follows from the axiom schema of replacement and the axiom of the empty set. On the other hand, the axiom of specification can be used to prove the existence of the
empty set In mathematics, the empty set is the unique set having no elements; its size or cardinality (count of elements in a set) is zero. Some axiomatic set theories ensure that the empty set exists by including an axiom of empty set, while in othe ...
, denoted \varnothing, once at least one set is known to exist (see above). One way to do this is to use a property \varphi which no set has. For example, if w is any existing set, the empty set can be constructed as : \varnothing = \. 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 (does not depend on w). It is common to make a
definitional extension In mathematical logic, more specifically in the proof theory of first-order theories, extensions by definitions formalize the introduction of new symbols by means of a definition. For example, it is common in naive set theory to introduce a symbol ...
that adds the symbol "\varnothing" to the language of ZFC.


4. Axiom of pairing

If x and y are sets, then there exists a set which contains x and y as elements. : \forall x \forall y \exists z ((x \in z) \land (y \in z)). The axiom schema of specification must be used to reduce this to a set with exactly these two elements. The axiom of pairing is part of Z, but is redundant in ZF because it follows from the axiom schema of replacement, if we are given a set with at least two elements. The existence of a set with at least two elements is assured by either the
axiom of infinity In axiomatic set theory and the branches of mathematics and philosophy that use it, the axiom of infinity is one of the axioms of Zermelo–Fraenkel set theory. It guarantees the existence of at least one infinite set, namely a set containing th ...
, or by the axiom schema of specification and the axiom of the power set applied twice to any set.


5. Axiom of union

The union over the elements of a set exists. For example, the union over the elements of the set \ is \. The axiom of union states that for any set of sets \mathcal there is a set A containing every element that is a member of some member of \mathcal: : \forall \mathcal \,\exists A \, \forall Y\, \forall x x \in Y \land Y \in \mathcal) \Rightarrow x \in A Although this formula doesn't directly assert the existence of \cup \mathcal, the set \cup \mathcal can be constructed from A in the above using the axiom schema of specification: : \cup \mathcal=\.


6. Axiom schema of replacement

The axiom schema of replacement asserts that the
image An image is a visual representation of something. It can be two-dimensional, three-dimensional, or somehow otherwise feed into the visual system to convey information. An image can be an artifact, such as a photograph or other two-dimensio ...
of a set under any definable function will also fall inside a set. Formally, let \varphi be any
formula In science, a formula is a concise way of expressing information symbolically, as in a mathematical formula or a ''chemical formula''. The informal use of the term ''formula'' in science refers to the general construct of a relationship betwe ...
in the language of ZFC whose
free variable In mathematics, and in other disciplines involving formal languages, including mathematical logic and computer science, a free variable is a notation (symbol) that specifies places in an expression where substitution may take place and is not ...
s are among x, y, A, w_1, \dotsc, w_n, so that in particular B is not free in \varphi. Then: : \forall A\forall w_1 \forall w_2\ldots \forall w_n \bigl forall x ( x\in A \Rightarrow \exists! y\,\varphi ) \Rightarrow \exists B \ \forall x \bigl(x\in A \Rightarrow \exists y (y\in B \land \varphi)\bigr)\bigr For the meaning of \exists!, see uniqueness quantification. In other words, if the relation \varphi represents a definable function f, A represents its
domain Domain may refer to: Mathematics *Domain of a function, the set of input values for which the (total) function is defined ** Domain of definition of a partial function ** Natural domain of a partial function **Domain of holomorphy of a function * ...
, and f(x) is a set for every x \in A, then the range of f is a subset of some set B. The form stated here, in which B may be larger than strictly necessary, is sometimes called the axiom schema of collection.


7. Axiom of infinity

Let S(w) abbreviate w \cup \, where w is some set. (We can see that \ is a valid set by applying the Axiom of Pairing with x = y = w so that the set is \). Then there exists a set such that the empty set \varnothing, defined axiomatically, is a member of and, whenever a set is a member of then S(y) is also a member of . : \exists X \left exists e (\forall z \, \neg (z \in e) \land e \in X) \land \forall y (y \in X \Rightarrow S(y) \in X)\right More colloquially, there exists a set having infinitely many members. (It must be established, however, that these members are all different, because if two elements are the same, the sequence will loop around in a finite cycle of sets. The axiom of regularity prevents this from happening.) The minimal set satisfying the axiom of infinity is the
von Neumann ordinal In set theory, an ordinal number, or ordinal, is a generalization of ordinal numerals (first, second, th, etc.) aimed to extend enumeration to infinite sets. A finite set can be enumerated by successively labeling each element with the leas ...
which can also be thought of as the set of
natural numbers In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country"). Numbers used for counting are called '' cardinal ...
\mathbb.


8. Axiom of power set

By definition a set z is a
subset In mathematics, set ''A'' is a subset of a set ''B'' if all elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are unequal, then ''A'' is a proper subset of ...
of a set x if and only if every element of z is also an element of x: : (z \subseteq x) \Leftrightarrow ( \forall q (q \in z \Rightarrow q \in x)). The Axiom of Power Set states that for any set x, there is a set y that contains every subset of x: : \forall x \exists y \forall z \subseteq x \Rightarrow z \in y The axiom schema of specification is then used to define the
power set In mathematics, the power set (or powerset) of a set is the set of all subsets of , including the empty set and itself. In axiomatic set theory (as developed, for example, in the ZFC axioms), the existence of the power set of any set is post ...
\mathcal(x) as the subset of such a y containing the subsets of x exactly: : \mathcal(x) = \. Axioms 1–8 define ZF. Alternative forms of these axioms are often encountered, some of which are listed in . 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. The following axiom is added to turn ZF into ZFC:


9. Well-ordering theorem

For any set X, there is a
binary relation In mathematics, a binary relation associates elements of one set, called the ''domain'', with elements of another set, called the ''codomain''. A binary relation over sets and is a new set of ordered pairs consisting of elements in and in ...
R which well-orders X. This means R is a
linear order In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X: # a \leq a ( reflexive) ...
on X such that every nonempty
subset In mathematics, set ''A'' is a subset of a set ''B'' if all elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are unequal, then ''A'' is a proper subset of ...
of X has a member which is minimal under R. : \forall X \exists R ( R \;\mbox\; X). Given axioms 1 – 8, there are many statements equivalent to axiom 9, the best known of which is the
axiom of choice In mathematics, the axiom of choice, or AC, is an axiom of set theory equivalent to the statement that ''a Cartesian product of a collection of non-empty sets is non-empty''. Informally put, the axiom of choice says that given any collection ...
(AC), which goes as follows. Let X be a set whose members are all nonempty. Then there exists a function f from X to the union of the members of X, called a "
choice function A choice function (selector, selection) is a mathematical function ''f'' that is defined on some collection ''X'' of nonempty sets and assigns some element of each set ''S'' in that collection to ''S'' by ''f''(''S''); ''f''(''S'') maps ''S'' to ...
", such that for all Y\in X one has f(Y)\in Y. Since the existence of a choice function when X is a
finite set In mathematics, particularly set theory, a finite set is a set that has a finite number of elements. Informally, a finite set is a set which one could in principle count and finish counting. For example, :\ is a finite set with five elements. T ...
is easily proved from axioms 1–8, AC only matters for certain infinite sets. 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 Neumann John von Neumann (; hu, Neumann János Lajos, ; December 28, 1903 – February 8, 1957) was a Hungarian-American mathematician, physicist, computer scientist, engineer and polymath. He was regarded as having perhaps the widest c ...
. In this viewpoint, the universe of set theory is built up in stages, with one stage for each
ordinal number In set theory, an ordinal number, or ordinal, is a generalization of ordinal numerals (first, second, th, etc.) aimed to extend enumeration to infinite sets. A finite set can be enumerated by successively labeling each element with the leas ...
. 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. 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 ''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 (or before) 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 (or before) stage α, and that the powerset of ''x'' will be added at the next stage after α. For a complete argument that ''V'' satisfies ZFC see . 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 theory (often called NBG) and
Morse–Kelley set theory In the foundations of mathematics, Morse–Kelley set theory (MK), Kelley–Morse set theory (KM), Morse–Tarski set theory (MT), Quine–Morse set theory (QM) or the system of Quine and Morse is a first-order axiomatic set theory that is closely ...
. The cumulative hierarchy is not compatible with other set theories such as
New Foundations In mathematical logic, New Foundations (NF) 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 Foundatio ...
. 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 universe ''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 of constructibility".


Metamathematics


Virtual classes

As noted earlier, proper classes (collections of mathematical objects defined by a property shared by their members which are too big to be sets) can only be treated indirectly in ZF (and thus ZFC). An alternative to proper classes while staying within ZF and ZFC is the ''virtual class'' notational construct introduced by , where the entire construct ''y'' ∈ is simply defined as F''y''. This provides a simple notation for classes that can contain sets but need not themselves be sets, while not committing to the ontology of classes (because the notation can be syntactically converted to one that only uses sets). Quine's approach built on the earlier approach of . Virtual classes are also used in , , and in the Metamath implementation of ZFC.


Von Neumann–Bernays–Gödel set theory

The axiom schemata of replacement and separation each contain infinitely many instances. 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 any
theorem In mathematics, a theorem is a statement that has been proved, or can be proved. The ''proof'' of a theorem is a logical argument that uses the inference rules of a deductive system to establish that the theorem is a logical consequence of t ...
not mentioning classes and provable in one theory can be proved in the other.


Consistency

Gödel's second incompleteness theorem says that a recursively axiomatizable system that can interpret
Robinson arithmetic In mathematics, Robinson arithmetic is a finitely axiomatized fragment of first-order Peano arithmetic (PA), first set out by R. M. Robinson in 1950. It is usually denoted Q. Q is almost PA without the axiom schema of mathematical induction. Q i ...
can prove its own consistency only if it is inconsistent. Moreover, Robinson arithmetic can be interpreted in general set theory, a small fragment of ZFC. Hence the
consistency In classical deductive logic, a consistent theory is one that does not lead to a logical contradiction. The lack of contradiction can be defined in either semantic or syntactic terms. The semantic definition states that a theory is consistent ...
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 cardinal, which is unprovable in ZFC if ZFC is consistent. Nevertheless, it is deemed unlikely that ZFC harbors an unsuspected contradiction; it is widely believed that if ZFC were inconsistent, that fact would have been uncovered by now. This much is certain — ZFC is immune to the classic paradoxes of
naive set theory Naive set theory is any of several theories of sets used in the discussion of the foundations of mathematics. Unlike axiomatic set theories, which are defined using formal logic, naive set theory is defined informally, in natural language. It ...
: Russell's paradox, the
Burali-Forti paradox In set theory, a field of mathematics, the Burali-Forti paradox demonstrates that constructing "the set of all ordinal numbers" leads to a contradiction and therefore shows an antinomy in a system that allows its construction. It is named after C ...
, and
Cantor's paradox In set theory, Cantor's paradox states that there is no set of all cardinalities. This is derived from the theorem that there is no greatest cardinal number. In informal terms, the paradox is that the collection of all possible "infinite sizes" is ...
. studied a subtheory of ZFC consisting of the axioms of extensionality, union, powerset, replacement, and choice. Using
models A model is an informative representation of an object, person or system. The term originally denoted the plans of a building in late 16th-century English, and derived via French and Italian ultimately from Latin ''modulus'', a measure. Models c ...
, 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 there are non-well-founded models that satisfy each axiom of ZFC except the axiom of regularity, that axiom is independent of the other ZFC axioms. If consistent, ZFC cannot prove the existence of the inaccessible cardinals that
category theory Category theory is a general theory of mathematical structures and their relations that was introduced by Samuel Eilenberg and Saunders Mac Lane in the middle of the 20th century in their foundational work on algebraic topology. Nowadays, ca ...
requires. Huge sets of this nature are possible if ZF is augmented with Tarski's axiom. Assuming that axiom turns the axioms of
infinity Infinity is that which is boundless, endless, or larger than any natural number. It is often denoted by the infinity symbol . Since the time of the ancient Greeks, the philosophical nature of infinity was the subject of many discussions am ...
,
power set In mathematics, the power set (or powerset) of a set is the set of all subsets of , including the empty set and itself. In axiomatic set theory (as developed, for example, in the ZFC axioms), the existence of the power set of any set is post ...
, and
choice A choice is the range of different things from which a being can choose. The arrival at a choice may incorporate motivators and models. For example, a traveler might choose a route for a journey based on the preference of arriving at a give ...
(7 – 9 above) into theorems.


Independence

Many important statements are
independent Independent or Independents may refer to: Arts, entertainment, and media Artist groups * Independents (artist group), a group of modernist painters based in the New Hope, Pennsylvania, area of the United States during the early 1930s * Independe ...
of ZFC (see list of statements independent of ZFC). The independence is usually proved by forcing, whereby it is shown that every countable transitive model of ZFC (sometimes augmented with large cardinal axioms) can be expanded to satisfy the statement in question. A different expansion is then shown to satisfy the negation of the statement. 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 model In set theory, a branch of mathematical logic, an inner model for a theory ''T'' is a substructure of a model ''M'' of a set theory that is both a model for ''T'' and contains all the ordinals of ''M''. Definition Let L = \langle \in \rangl ...
s, such as in the constructible universe. 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 (abbreviated CH) is a hypothesis about the possible sizes of infinite sets. It states that or equivalently, that In Zermelo–Fraenkel set theory with the axiom of choice (ZFC), this is equivalent to ...
*
Diamond principle In mathematics, and particularly in axiomatic set theory, the diamond principle is a combinatorial principle introduced by Ronald Jensen in that holds in the constructible universe () and that implies the continuum hypothesis. Jensen extracted th ...
* Suslin hypothesis *
Martin's axiom In the mathematical field of set theory, Martin's axiom, introduced by Donald A. Martin and Robert M. Solovay, is a statement that is independent of the usual axioms of ZFC set theory. It is implied by the continuum hypothesis, but it is consis ...
(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 by
inner model In set theory, a branch of mathematical logic, an inner model for a theory ''T'' is a substructure of a model ''M'' of a set theory that is both a model for ''T'' and contains all the ordinals of ''M''. Definition Let L = \langle \in \rangl ...
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 satisfies the Generalized Continuum Hypothesis, the Diamond Principle, Martin's Axiom and the Kurepa Hypothesis. * The failure of the Kurepa hypothesis is equiconsistent with the existence of a
strongly inaccessible cardinal In set theory, an uncountable cardinal is inaccessible if it cannot be obtained from smaller cardinals by the usual operations of cardinal arithmetic. More precisely, a cardinal is strongly inaccessible if it is uncountable, it is not a sum of ...
. A variation on the method of forcing can also be used to demonstrate the consistency and unprovability of the
axiom of choice In mathematics, the axiom of choice, or AC, is an axiom of set theory equivalent to the statement that ''a Cartesian product of a collection of non-empty sets is non-empty''. Informally put, the axiom of choice says that given any collection ...
, 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 In the mathematical field of set theory, a large cardinal property is a certain kind of property of transfinite cardinal numbers. Cardinals with such properties are, as the name suggests, generally very "large" (for example, bigger than the least ...
is not provable in ZFC, but cannot prove that assuming such cardinals, given ZFC, is free of contradiction.


Proposed additions

The project to unify set theorists behind additional axioms to resolve the Continuum Hypothesis or other meta-mathematical ambiguities is sometimes known as "Gödel's program". Mathematicians currently debate which axioms are the most plausible or "self-evident", which axioms are the most useful in various domains, and about to what degree usefulness should be traded off with plausibility; some "
multiverse The multiverse is a hypothetical group of multiple universes. Together, these universes comprise everything that exists: the entirety of space, time, matter, energy, information, and the physical laws and constants that describe them. The dif ...
" set theorists argue that usefulness should be the sole ultimate criterion in which axioms to customarily adopt. One school of thought leans on expanding the "iterative" concept of a set to produce a set-theoretic universe with an interesting and complex but reasonably tractable structure by adopting forcing axioms; another school advocates for a tidier, less cluttered universe, perhaps focused on a "core" inner model.


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 In mathematical logic, the Peano axioms, also known as the Dedekind–Peano axioms or the Peano postulates, are axioms for the natural numbers presented by the 19th century Italian mathematician Giuseppe Peano. These axioms have been used nearl ...
and
second-order arithmetic In mathematical logic, second-order arithmetic is a collection of axiomatic systems that formalize the natural numbers and their subsets. It is an alternative to axiomatic set theory as a foundation for much, but not all, of mathematics. A precur ...
(as explored by the program of reverse mathematics).
Saunders Mac Lane Saunders Mac Lane (4 August 1909 – 14 April 2005) was an American mathematician who co-founded category theory with Samuel Eilenberg. Early life and education Mac Lane was born in Norwich, Connecticut, near where his family lived in Taftville ...
and
Solomon Feferman Solomon Feferman (December 13, 1928 – July 26, 2016) was an American philosopher and mathematician who worked in mathematical logic. Life Solomon Feferman was born in The Bronx in New York City to working-class parents who had immigrated to th ...
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 in 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. Unlike
New Foundations In mathematical logic, New Foundations (NF) 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 Foundatio ...
, ZFC does not admit the existence of a universal set. Hence the
universe The universe is all of space and time and their contents, including planets, stars, galaxies, and all other forms of matter and energy. The Big Bang theory is the prevailing cosmological description of the development of the univers ...
of sets under ZFC is not closed under the elementary operations of the
algebra of sets In mathematics, the algebra of sets, not to be confused with the mathematical structure of ''an'' algebra of sets, defines the properties and laws of sets, the set-theoretic operations of union, intersection, and complementation and the ...
. Unlike von Neumann–Bernays–Gödel set theory (NBG) and
Morse–Kelley set theory In the foundations of mathematics, Morse–Kelley set theory (MK), Kelley–Morse set theory (KM), Morse–Tarski set theory (MT), Quine–Morse set theory (QM) or the system of Quine and Morse is a first-order axiomatic set theory that is closely ...
(MK), ZFC does not admit the existence of proper classes. A further comparative weakness of ZFC is that the
axiom of choice In mathematics, the axiom of choice, or AC, is an axiom of set theory equivalent to the statement that ''a Cartesian product of a collection of non-empty sets is non-empty''. Informally put, the axiom of choice says that given any collection ...
included in ZFC is weaker than the axiom of global choice included in NBG and MK. There are numerous mathematical statements independent of ZFC. These include the continuum hypothesis, the Whitehead problem, and the normal Moore space conjecture. Some of these conjectures are provable with the addition of axioms such as
Martin's axiom In the mathematical field of set theory, Martin's axiom, introduced by Donald A. Martin and Robert M. Solovay, is a statement that is independent of the usual axioms of ZFC set theory. It is implied by the continuum hypothesis, but it is consis ...
or large cardinal axioms to ZFC. Some others are decided in ZF+AD where AD is the axiom of determinacy, 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 In mathematical logic, projective determinacy is the special case of the axiom of determinacy applying only to projective sets. The axiom of projective determinacy, abbreviated PD, states that for any two-player infinite game of perfect informatio ...
). The Mizar system and Metamath have adopted Tarski–Grothendieck set theory, an extension of ZFC, so that proofs involving Grothendieck universes (encountered in category theory and algebraic geometry) can be formalized.


See also

*
Foundations of mathematics Foundations of mathematics is the study of the philosophical and logical and/or algorithmic basis of mathematics, or, in a broader sense, the mathematical investigation of what underlies the philosophical theories concerning the nature of mathe ...
*
Inner model In set theory, a branch of mathematical logic, an inner model for a theory ''T'' is a substructure of a model ''M'' of a set theory that is both a model for ''T'' and contains all the ordinals of ''M''. Definition Let L = \langle \in \rangl ...
* Large cardinal axiom Related axiomatic set theories: *
Morse–Kelley set theory In the foundations of mathematics, Morse–Kelley set theory (MK), Kelley–Morse set theory (KM), Morse–Tarski set theory (MT), Quine–Morse set theory (QM) or the system of Quine and Morse is a first-order axiomatic set theory that is closely ...
* Von Neumann–Bernays–Gödel set theory * Tarski–Grothendieck set theory * Constructive set theory *
Internal set theory Internal set theory (IST) is a mathematical theory of sets developed by Edward Nelson that provides an axiomatic basis for a portion of the nonstandard analysis introduced by Abraham Robinson. Instead of adding new elements to the real numbers, ...


Notes


Works cited

* * * * * * *. * Fraenkel's final word on ZF and ZFC. * * * Includes annotated English translations of the classic articles by Zermelo, Fraenkel, and Skolem bearing on ZFC. * * * * * * * * * *Perhaps the best exposition of ZFC before the independence of AC and the Continuum hypothesis, and the emergence of large cardinals. Includes many theorems. * * * * * *. * English translation in *


External links

* *
Stanford Encyclopedia of Philosophy The ''Stanford Encyclopedia of Philosophy'' (''SEP'') combines an online encyclopedia of philosophy with peer-reviewed publication of original papers in philosophy, freely accessible to Internet users. It is maintained by Stanford University. E ...
articles by Thomas Jech: *
Set Theory
*



— A concise and nonredundant axiomatization. The background first order logic is defined especially to facilitate machine verification of proofs. **
derivation
in Metamath of a version of the separation schema from a version of the replacement schema. * {{DEFAULTSORT:Zermelo-Fraenkel Set Theory Foundations of mathematics Systems of set theory Z notation