Zermelo–Fraenkel set theory

This article includes a list of general references, but it lacks sufficient corresponding inline citations. Please help to improve this article by introducing more precise citations. (February 2024) (Learn how and when to remove this message)

In

and ZF refers to the axioms of Zermelo–Fraenkel set theory with the axiom of choice excluded.

Informally,

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 says that given any two sets ${\displaystyle a}$ and ${\displaystyle b}$ there is a new set ${\displaystyle \{a,b\}}$ containing exactly ${\displaystyle a}$ and ${\displaystyle 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).

The

.

The modern study of set theory was initiated by Georg Cantor and Richard Dedekind in the 1870s. However, the discovery of paradoxes in naive set theory, 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,

whose existence was taken for granted by most set theorists of the time, notably the cardinal number aleph-omega (${\displaystyle \aleph _{\omega }}$) and the set ${\displaystyle \{Z_{0},{\mathcal {P}}(Z_{0}),{\mathcal {P}}({\mathcal {P}}(Z_{0})),{\mathcal {P}}({\mathcal {P}}({\mathcal {P}}(Z_{0}))),...\},}$ where ${\displaystyle Z_{0}}$ is any infinite set and ${\displaystyle {\mathcal {P}}}$ is the power set operation.^[3] 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 (first proposed by John von Neumann),^[4] to Zermelo set theory yields the theory denoted by ZF. Adding to ZF either the axiom of choice (AC) or a statement that is equivalent to it yields ZFC.

Formally, ZFC is a

has a single predicate symbol, usually denoted ${\displaystyle \in }$, which is a predicate symbol of arity 2 (a binary relation symbol). This symbol symbolizes a ${\displaystyle a\in b}$ means that ${\displaystyle a}$ is an element of the set ${\displaystyle b}$ (also read as ${\displaystyle a}$ is a member of ${\displaystyle b}$).

There are different ways to formulate the formal language. Some authors may choose a different set of connectives or quantifiers. For example, the logical connective NAND alone can encode the other connectives, a property known as functional completeness. This section attempts to strike a balance between simplicity and intuitiveness.

The language's alphabet consists of:

• A countably infinite amount of variables used for representing sets
• The logical connectives ${\displaystyle \lnot }$, ${\displaystyle \land }$, ${\displaystyle \lor }$
• The quantifier symbols ${\displaystyle \forall }$, ${\displaystyle \exists }$
• The equality symbol ${\displaystyle =}$
• The set membership symbol ${\displaystyle \in }$
• Brackets ( )

With this alphabet, the recursive rules for forming

(wff) are as follows:

• Let ${\displaystyle x}$ and ${\displaystyle y}$ be metavariables for any variables. These are the two ways to build atomic formulae (the simplest wffs):

${\displaystyle x=y}$

${\displaystyle x\in y}$

• Let ${\displaystyle \phi }$ and ${\displaystyle \psi }$ be metavariables for any wff, and ${\displaystyle x}$ be a metavariable for any variable. These are valid wff constructions:

${\displaystyle \lnot \phi }$

${\displaystyle (\phi \land \psi )}$

${\displaystyle (\phi \lor \psi )}$

${\displaystyle \forall x\phi }$

${\displaystyle \exists x\phi }$

A well-formed formula can be thought as a syntax tree. The leaf nodes are always atomic formulae. Nodes ${\displaystyle \land }$ and ${\displaystyle \lor }$ have exactly two child nodes, while nodes ${\displaystyle \lnot }$, ${\displaystyle \forall x}$ and ${\displaystyle \exists x}$ have exactly one. There are countably infinitely many wffs, however, each wff has a finite number of nodes.

There are many equivalent formulations of the ZFC axioms.

and high-level abbreviations.

Axioms 1–8 form ZF, while the axiom 9 turns ZF into ZFC. Following Kunen (1980), we use the equivalent well-ordering theorem in place of the axiom of choice for axiom 9.

All formulations of ZFC imply that at least one set exists. Kunen includes an axiom that directly asserts the existence of a set, although he notes that he does so only "for emphasis".^[6] 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 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, ${\displaystyle \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, in which it is not provable from logic alone that something exists, the axiom of infinity 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.

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 equality. ZFC is constructed in first-order logic. Some formulations of first-order logic include identity; others do not. If the variety of first-order logic in which you are constructing set theory does not include equality "${\displaystyle =}$", ${\displaystyle x=y}$ may be defined as an abbreviation for the following formula:^[7] ${\displaystyle \forall z[z\in x\Leftrightarrow z\in y]\land \forall w[x\in w\Leftrightarrow y\in w].}$

In this case, the axiom of extensionality can be reformulated as

which says that if ${\displaystyle x}$ and ${\displaystyle y}$ have the same elements, then they belong to the same sets.^[8]

Every non-empty set ${\displaystyle x}$ contains a member ${\displaystyle y}$ such that ${\displaystyle x}$ and ${\displaystyle y}$ are disjoint sets.

or in modern notation: ${\displaystyle \forall x\,(x\neq \varnothing \Rightarrow \exists y(y\in x\land y\cap x=\varnothing )).}$

This (along with the axioms of pairing and union) implies, for example, that no set is an element of itself and that every set has an

.

Subsets are commonly constructed using

. For example, the even integers can be constructed as the subset of the integers ${\displaystyle \mathbb {Z} }$ satisfying the predicate ${\displaystyle x\equiv 0{\pmod {2}}}$:

In general, the subset of a set ${\displaystyle z}$ obeying a formula ${\displaystyle \varphi (x)}$ with one free variable ${\displaystyle 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 ${\displaystyle \varphi }$). Formally, let ${\displaystyle \varphi }$ be any formula in the language of ZFC with all free variables among ${\displaystyle x,z,w_{1},\ldots ,w_{n}}$ (${\displaystyle y}$ is not free in ${\displaystyle \varphi }$). Then:

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 ${\displaystyle y=\{x:x\notin x\}}$ then ${\displaystyle y\in y\Leftrightarrow y\notin y}$) and its variants that accompany naive set theory with

(since under this restriction ${\displaystyle y}$ only refers to sets within ${\displaystyle z}$ that don't belong to themselves, and ${\displaystyle y\in z}$ has not been established, even though ${\displaystyle y\subseteq z}$ is the case, so ${\displaystyle y}$ stands in a separate position from which it can't refer to or comprehend itself; therefore, in a certain sense, this axiom schema is saying that in order to build a ${\displaystyle y}$ on the basis of a formula ${\displaystyle \varphi (x)}$, we need to previously restrict the sets ${\displaystyle y}$ will regard within a set ${\displaystyle z}$ that leaves ${\displaystyle y}$ outside so ${\displaystyle y}$ can't refer to itself; or, in other words, sets shouldn't refer to themselves).

In some other axiomatizations of ZF, this axiom is redundant in that it follows from the

.

On the other hand, the axiom schema of specification can be used to prove the existence of the empty set, denoted ${\displaystyle \varnothing }$, once at least one set is known to exist. One way to do this is to use a property ${\displaystyle \varphi }$ which no set has. For example, if ${\displaystyle w}$ is any existing set, the empty set can be constructed as

Thus, the

is implied by the nine axioms presented here. The axiom of extensionality implies the empty set is unique (does not depend on ${\displaystyle w}$). It is common to make a that adds the symbol "${\displaystyle \varnothing }$" to the language of ZFC.

If ${\displaystyle x}$ and ${\displaystyle y}$ are sets, then there exists a set which contains ${\displaystyle x}$ and ${\displaystyle y}$ as elements, for example if x = {1,2} and y = {2,3} then z will be {{1,2},{2,3}}

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

applied twice to any set.

The union over the elements of a set exists. For example, the union over the elements of the set ${\displaystyle \{\{1,2\},\{2,3\}\}}$ is ${\displaystyle \{1,2,3\}.}$

The axiom of union states that for any set of sets ${\displaystyle {\mathcal {F}}}$, there is a set ${\displaystyle A}$ containing every element that is a member of some member of ${\displaystyle {\mathcal {F}}}$:

Although this formula doesn't directly assert the existence of ${\displaystyle \cup {\mathcal {F}}}$, the set ${\displaystyle \cup {\mathcal {F}}}$ can be constructed from ${\displaystyle A}$ in the above using the axiom schema of specification:

The axiom schema of replacement asserts that the image of a set under any definable function will also fall inside a set.

Formally, let ${\displaystyle \varphi }$ be any

are among ${\displaystyle x,y,A,w_{1},\dotsc ,w_{n},}$ so that in particular ${\displaystyle B}$ is not free in ${\displaystyle \varphi }$. Then:

(The unique existential quantifier ${\displaystyle \exists !}$ denotes the existence of exactly one element such that it follows a given statement.)

In other words, if the relation ${\displaystyle \varphi }$ represents a definable function ${\displaystyle f}$, ${\displaystyle A}$ represents its domain, and ${\displaystyle f(x)}$ is a set for every ${\displaystyle x\in A,}$ then the range of ${\displaystyle f}$ is a subset of some set ${\displaystyle B}$. The form stated here, in which ${\displaystyle B}$ may be larger than strictly necessary, is sometimes called the axiom schema of collection.

First several von Neumann ordinals

0	=	{}	=	∅
1	=	{0}	=	{∅}
2	=	{0,1}	=	{∅,{∅}}
3	=	{0,1,2}	=	{∅,{∅},{∅,{∅}}}
4	=	{0,1,2,3}	=	{∅,{∅},{∅,{∅}},{∅,{∅},{∅,{∅}}}}

Let ${\displaystyle S(w)}$ abbreviate ${\displaystyle w\cup \{w\},}$ where ${\displaystyle w}$ is some set. (We can see that ${\displaystyle \{w\}}$ is a valid set by applying the axiom of pairing with ${\displaystyle x=y=w}$ so that the set z is ${\displaystyle \{w\}}$). Then there exists a set X such that the empty set ${\displaystyle \varnothing }$, defined axiomatically, is a member of X and, whenever a set y is a member of X then ${\displaystyle S(y)}$ is also a member of X.

or in modern notation: ${\displaystyle \exists X\left[\varnothing \in X\land \forall y(y\in X\Rightarrow S(y)\in X)\right].}$

More colloquially, there exists a set X 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 X satisfying the axiom of infinity is the

${\displaystyle \mathbb {N} .}$

By definition, a set ${\displaystyle z}$ is a subset of a set ${\displaystyle x}$ if and only if every element of ${\displaystyle z}$ is also an element of ${\displaystyle x}$:

The Axiom of power set states that for any set ${\displaystyle x}$, there is a set ${\displaystyle y}$ that contains every subset of ${\displaystyle x}$:

The axiom schema of specification is then used to define the power set ${\displaystyle {\mathcal {P}}(x)}$ as the subset of such a ${\displaystyle y}$ containing the subsets of ${\displaystyle x}$ exactly:

Axioms 1–8 define ZF. Alternative forms of these axioms are often encountered, some of which are listed in Jech (2003). 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 ${\displaystyle x}$ whose existence is being asserted are just those sets which the axiom asserts ${\displaystyle x}$ must contain.

The following axiom is added to turn ZF into ZFC:

The last axiom, commonly known as the axiom of choice, is presented here as a property about well-orders, as in Kunen (1980). For any set ${\displaystyle X}$, there exists a binary relation ${\displaystyle R}$ which well-orders ${\displaystyle X}$. This means ${\displaystyle R}$ is a

on ${\displaystyle X}$ such that every nonempty subset of ${\displaystyle X}$ has a under the order ${\displaystyle R}$.

Given axioms 1 – 8, many statements are provably equivalent to axiom 9. The most common of these goes as follows. Let ${\displaystyle X}$ be a set whose members are all nonempty. Then there exists a function ${\displaystyle f}$ from ${\displaystyle X}$ to the union of the members of ${\displaystyle X}$, called a "choice function", such that for all ${\displaystyle Y\in X}$ one has ${\displaystyle f(Y)\in Y}$. A third version of the axiom, also equivalent, is Zorn's lemma.

Since the existence of a choice function when ${\displaystyle X}$ is a

because it asserts the existence of a choice function but says nothing about how this choice function is to be "constructed".

One motivation for the ZFC axioms is

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

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. The cumulative hierarchy is not compatible with other set theories such as New Foundations.

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".

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 Quine (1969), where the entire construct y ∈ { x | Fx } is simply defined as Fy.^[13] 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 Bernays & Fraenkel (1958). Virtual classes are also used in Levy (2002), Takeuti & Zaring (1982), and in the Metamath implementation of ZFC.

The axiom schemata of replacement and separation each contain infinitely many instances. Montague (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 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 not mentioning classes and provable in one theory can be proved in the other.

.

, 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 requires. Huge sets of this nature are possible if ZF is augmented with Tarski's axiom.^[14] Assuming that axiom turns the axioms of infinity, power set, and choice (7 – 9 above) into theorems.

Many important statements are

. 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:

• Axiom of constructibility (V=L) (which is also not a ZFC axiom)
• Continuum hypothesis
• Diamond principle
• Martin's axiom (which is not a ZFC axiom)
• Suslin hypothesis

Remarks:

• The consistency of V=L is provable by inner models 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
  generalized continuum hypothesis
  , the diamond principle, Martin's axiom and the Kurepa hypothesis.
• The failure of the
  strongly inaccessible cardinal
  .

A variation on the method of forcing can also be used to demonstrate the consistency and unprovability of the axiom of choice, 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

is not provable in ZFC, but cannot prove that assuming such cardinals, given ZFC, is free of contradiction.

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".^[15] 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" 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.^[16]

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

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

included in NBG and MK.

There are numerous

(encountered in category theory and algebraic geometry) can be formalized.

See also

• Foundations of mathematics
• Inner model
• Large cardinal axiom

Related

:

• Morse–Kelley set theory
• Von Neumann–Bernays–Gödel set theory
• Tarski–Grothendieck set theory
• Constructive set theory
• Internal set theory

External links

• Axioms of set Theory - Lec 02 - Frederic Schuller on
  YouTube
• "ZFC", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
• Stanford Encyclopedia of Philosophy articles by Joan Bagaria:
  • Bagaria, Joan (31 January 2023). "Set Theory". In Zalta, Edward N. (ed.). Stanford Encyclopedia of Philosophy.
  • — (31 January 2023). "Axioms of Zermelo–Fraenkel Set Theory". In — (ed.). Stanford Encyclopedia of Philosophy.
• 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.
• Weisstein, Eric W. "Zermelo-Fraenkel Set Theory". MathWorld.