Zermelo-Fraenkel Set Theory (ZF)

Axioms of ZF

Extensionality:
\(\forall x\forall y[\forall z (\left.z \in x\right. \leftrightarrow \left. z \in y\right.) \rightarrow x=y]\)

This axiom asserts that when sets \(x\) and \(y\) have the same members, they are the same set.

The next axiom asserts the existence of the empty set:

Null Set:
\(\exists x \neg\exists y (y \in x)\)

Since it is provable from this axiom and the previous axiom that there is a unique such set, we may introduce the notation ‘\(\varnothing\)’ to denote it.

The next axiom asserts that given any sets \(x\) and \(y\), there exists a pair set of \(x\) and \(y\), i.e., a set which has only \(x\) and \(y\) as members:

Pairs:
\(\forall x\forall y \exists z \forall w (w\in z \leftrightarrow w=x \lor w=y)\)

Since it is provable that there is a unique pair set for each given \(x\) and \(y\), we introduce the notation ‘{\(x\),\(y\)}’ to denote it. In the particular case when \( x =y\), the axiom asserts the existence of the singleton \( \{ x\}\), namely the set having \( x\) as its unique member.

The next axiom asserts that for any set \(x\), there is a set \(y\) which contains as members all those sets whose members are also elements of \(x\), i.e., \(y\) contains all of the subsets of \(x\):

Power Set:
\(\forall x \exists y \forall z[z\in y \leftrightarrow \forall w(w\in z \rightarrow w\in x)]\)

Since every set provably has a unique ‘power set’, we introduce the notation ‘\(\mathscr{P}(x)\)’ to denote it. Note also that we may define the notion x is a subset of y (‘\(x \subseteq y\)’) as: \(\forall z(z\in x\rightarrow z\in y)\). Then we may simplify the statement of the Power Set Axiom as follows:

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

The next axiom asserts that for any given set \(x\), there is a set \(y\) which has as members all of the members of all of the members of \(x\):

Unions:
\(\forall x\exists y\forall z[z\in y \leftrightarrow \exists w(w\in x \land z\in w)]\)

Since it is provable that there is a unique ‘union’ of any set \(x\), we introduce the notation ‘\(\bigcup x\)’ to denote it.

The next axiom asserts the existence of an infinite set, i.e., a set with an infinite number of members:

Infinity:
\(\exists x[\varnothing\in x \land \forall y(y\in x \rightarrow \bigcup\{y,\{y\}\}\in x)]\)

We may think of this as follows. Let us define the union of x and y (‘\(x\cup y\)’) as the union of the pair set of \(x\) and \(y\), i.e., as \(\bigcup \{x,y\}\). Then the Axiom of Infinity asserts that there is a set \(x\) which contains \(\varnothing\) as a member and which is such that whenever a set \(y\) is a member of \(x\), then \(y\cup\{y\}\) is also a member of \(x\). Consequently, this axiom guarantees the existence of a set of the following form:

\(\{\varnothing,\{\varnothing\},\{\varnothing,\{\varnothing\}\},\{\varnothing,\{\varnothing\},\{\varnothing,\{\varnothing\}\}\},\ldots\}\)

Notice that the second element, \(\{\varnothing \}\), is in this set because (1) the fact that \(\varnothing\) is in the set implies that \(\varnothing \cup \{\varnothing \}\) is in the set and (2) \(\varnothing \cup \{\varnothing \}\) just is \(\{\varnothing\}\). Similarly, the third element, \(\{\varnothing,\{\varnothing\}\}\), is in this set because (1) the fact that \(\{\varnothing\}\) is in the set implies that \(\{\varnothing \} \cup\{\{\varnothing \}\}\) is in the set and (2) \(\{\varnothing \} \cup \{\{\varnothing \}\}\) just is \(\{\varnothing, \{\varnothing \}\}\). And so forth.

Next is the Separation Schema, which is a formula-pattern that uses a metavariable (in this case \(\psi\)) to describe an infinite list of axioms – one axiom for each formula of the language of set theory with at least a free variable. Every instance of the Separation Schema asserts the existence of a set that contains the elements of a given set \(w\) that satisfy a certain condition, which is given by a formula \(\psi\). That is, suppose that \(\psi(x,u_1,\ldots,u_k)\) is a formula of the language of set theory that has \(x\) free and may or may not have \(u_1,\ldots,u_k\) free. Then the Separation Schema for the condition \(\psi\) asserts:

Separation:
\(\forall u_1 \ldots\forall u_k [\forall w\exists v\forall r(r\in v \leftrightarrow r\in w \land \psi(r,u_1,\ldots,u_k))]\)

In other words, given sets \(w\) and \(u_1,\ldots,u_k\), there exists a set \(v\) which has as members precisely the members \(r\) of \(w\) which satisfy the formula \(\psi(r,u_1,\ldots,u_k)\).

Next is the Replacement Schema, which is also a formula-pattern that uses a metavariable (in this case \(\phi\)) to describe an infinite list of axioms -- one axiom for each formula of the language of set theory with at least two free variables. Suppose that \(\phi(x,y,u_1,\ldots,u_k)\) is a formula with \(x\) and \(y\) free, and in which \(u_1,\ldots u_k\) may or may not be free. Then the instance of the Replacement Schema given by \(\phi(x,y,u_1,\ldots,u_k)\) is the following axiom:

Replacement:
\(\forall u_1 \ldots\forall u_k [\forall x\exists!y\phi(x,y,u_1,\ldots u_k)\rightarrow\)
  \(\forall w\exists v\forall r(r\in v\leftrightarrow \exists s(s\in w \land \phi (s,r,u_1,\ldots u_k)))]\)

In other words, if we know that \(\phi\) is a functional formula (which relates each set \(x\) to a unique set \(y\)), then if we are given a set \(w\), we can form a new set \(v\) as follows: collect all of the sets to which the members of \(w\) are uniquely related by \(\phi\).

Note that the Replacement Schema can take you ‘out of’ the set \(w\) when forming the set \(v\). The elements of \(v\) need not be elements of \(w\). By contrast, the Separation Schema of Zermelo only yields subsets of the given set \(w\).

The final axiom asserts that every set is ‘well-founded’:

Regularity:
\(\forall x[x\ne\varnothing\rightarrow\exists y(y\in x\land\forall z(z\in x \rightarrow\neg(z\in y)))]\)

A member \(y\) of a set \(x\) with this property is called a ‘minimal’ element. This axiom rules out the existence of circular chains of sets (e.g., such as \(x\in y \land y\in z \land z\in x\)) as well as infinitely descending chains of sets (such as … \(x_3\in x_2\in x_1\in x_0\)).