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