Zermelo-Fraenkel Set Theory

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 if given any set \(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.

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

The next axiom is the Separation Schema, which asserts the existence of a set that contains the elements of a given set \(w\) that satisfy a certain condition \(\psi\). That is, suppose that \(\psi(x,\hat{u})\) has \(x\) free and may or may not have \(u_1,\ldots,u_k\) free. And let \(\psi_{x,\hat{u}}[r,\hat{u}]\) be the result of substituting \(r\) for \(x\) in \(\psi(x,\hat{u})\). Then the Separation Schema asserts:

Separation Schema:
\(\forall u_1 \ldots\forall u_k [\forall w\exists v\forall r(r\in v \leftrightarrow r\in w \land \psi_{x,\hat{u}}[r,\hat{u}])]\)

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

The next axiom of ZF is the Replacement Schema. Suppose that \(\phi(x,y,\hat{u})\) is a formula with \(x\) and \(y\) free, and let \(\hat{u}\) represent the variables \(u_1,\ldots u_k,\) which may or may not be free in \(\phi\). Furthermore, let \(\phi_{x,y,\hat{u}}[s,r,\hat{u}]\) be the result of substituting \(s\) and \(r\) for \(x\) and \(y\), respectively, in \(\phi(x,y,\hat{u})\). Then every instance of the following schema is an axiom:

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

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\)).