#### Supplement to Set Theory

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