7.5 Zermelo Fraenkel Axioms (ZF, ZFC)

Set theory becomes a foundation for mathematics only after its basic principles are stated as axioms. Informal set language is useful, but it can lead to contradictions if every definable collection is allowed to be a set. The Zermelo Fraenkel axioms provide a controlled formal framework in which sets may be built, compared, and used without allowing unrestricted comprehension.

Motivation

A naive view says that every collection described by a property should be a set. For example, one might try to form:

R=\{x:x\notin x\}

This is the collection of all sets that are not elements of themselves. If $R$ were a set, then one could ask whether:

R\in R

By the definition of $R$ , we would have:

R\in R \quad \text{if and only if} \quad R\notin R

This is impossible. The contradiction shows that sets cannot be formed by arbitrary properties without restriction.

The axioms of ZF set theory avoid this problem by allowing only certain controlled ways of forming sets. Instead of saying that every property defines a set, ZF says that sets can be constructed from existing sets by specific operations.

Definition 7.98 (Language of Set Theory)

The language of set theory is a first order language with one nonlogical binary relation symbol:

\in

The formula:

x\in y

is read as “ $x$ is an element of $y$ ”.

Equality is part of first order logic, so formulas may also use:

x=y

All objects in the theory are sets. Thus set theory does not begin with separate primitive kinds such as numbers, functions, or relations. These objects are later represented as sets.

Axiom 7.99 (Extensionality)

Sets with the same elements are equal:

\forall A\,\forall B\,\bigl(\forall x\,(x\in A\leftrightarrow x\in B)\to A=B\bigr)

This axiom says that a set is completely determined by its elements. There is no additional hidden structure attached to a set beyond membership.

Example 7.100

By extensionality:

\{1,2,3\}=\{3,2,1\}

because both sets have the same elements.

Also:

\{1,1,2\}=\{1,2\}

because repetition does not create a new element.

Axiom 7.101 (Empty Set)

There exists a set with no elements:

\exists E\,\forall x\,(x\notin E)

Such a set is denoted:

\varnothing

The empty set is unique by extensionality.

Lemma 7.102 (Uniqueness of the Empty Set)

If $E$ and $F$ have no elements, then:

E=F

Proof

Assume:

\forall x\,(x\notin E)

and:

\forall x\,(x\notin F)

Then for every $x$ , both statements $x\in E$ and $x\in F$ are false. Therefore:

x\in E\leftrightarrow x\in F

for every $x$ . By extensionality:

E=F

Axiom 7.103 (Pairing)

For any sets $a$ and $b$ , there exists a set whose elements are exactly $a$ and $b$ :

\forall a\,\forall b\,\exists P\,\forall x\,(x\in P\leftrightarrow (x=a\lor x=b))

The set $P$ is denoted:

\{a,b\}

If $a=b$ , then:

\{a,b\}=\{a\}

This axiom allows the formation of unordered pairs and singleton sets.

Definition 7.104 (Singleton)

The singleton containing $a$ is:

\{a\}=\{a,a\}

It is the unique set whose only element is $a$ :

x\in\{a\} \quad \text{if and only if} \quad x=a

Axiom 7.105 (Union)

For every set $A$ , there exists a set whose elements are exactly the elements of elements of $A$ :

\forall A\,\exists U\,\forall x\,\bigl(x\in U\leftrightarrow \exists y\,(y\in A\land x\in y)\bigr)

This set is denoted:

\bigcup A

The union axiom allows many sets already collected inside $A$ to be merged into one set.

Example 7.106

If:

A=\{\{1,2\},\{2,3\}\}

then:

\bigcup A=\{1,2,3\}

because the elements of elements of $A$ are exactly $1$ , $2$ , and $3$ .

Definition 7.107 (Binary Union)

The union of two sets $A$ and $B$ is defined by:

A\cup B=\bigcup\{A,B\}

Thus:

x\in A\cup B \quad \text{if and only if} \quad x\in A\lor x\in B

This definition uses Pairing to form $\{A,B\}$ and Union to merge its elements.

Axiom 7.108 (Power Set)

For every set $A$ , there exists a set whose elements are exactly the subsets of $A$ :

\forall A\,\exists P\,\forall X\,(X\in P\leftrightarrow X\subseteq A)

This set is denoted:

\mathcal{P}(A)

Thus:

X\in\mathcal{P}(A) \quad \text{if and only if} \quad X\subseteq A

The power set axiom is one of the main sources of large sets, because Cantor theorem shows:

|A|<|\mathcal{P}(A)|

for every set $A$ .

Axiom Schema 7.109 (Separation)

Let $\varphi(x)$ be any formula of the language of set theory, possibly with parameters. For every set $A$ , there exists a set containing exactly those elements of $A$ that satisfy $\varphi$ :

\forall A\,\exists B\,\forall x\,\bigl(x\in B\leftrightarrow (x\in A\land \varphi(x))\bigr)

This set is denoted:

B=\{x\in A:\varphi(x)\}

Separation is an axiom schema because there is one axiom for each formula $\varphi$ .

The restriction $x\in A$ is essential. Separation does not say that every definable collection is a set. It only says that a definable subcollection of an existing set is a set.

Example 7.110

If:

A=\{0,1,2,3,4,5\}

then Separation allows the formation of:

\{x\in A:x \text{ is even}\}

which is:

\{0,2,4\}

The property “is even” is used only to select elements from a set already known to exist.

Lemma 7.111 (Russell Collection Is Not a Set)

There is no set:

R=\{x:x\notin x\}

Proof

Suppose such a set $R$ exists. Then by its defining property:

x\in R \quad \text{if and only if} \quad x\notin x

for every set $x$ .

Taking $x=R$ , we obtain:

R\in R \quad \text{if and only if} \quad R\notin R

This is impossible. Therefore no such set exists.

This argument explains why Separation is restricted to subsets of already existing sets.

Axiom Schema 7.112 (Replacement)

Let $\varphi(x,y)$ be a formula such that for each $x$ in a set $A$ there is a unique $y$ satisfying $\varphi(x,y)$ . Then the collection of all such $y$ is a set.

Formally:

\forall A\,\Bigl(\forall x\in A\,\exists!y\,\varphi(x,y) \to \exists B\,\forall y\,(y\in B\leftrightarrow \exists x\in A\,\varphi(x,y))\Bigr)

Replacement says that the image of a set under a definable function is again a set.

This axiom is needed for many transfinite constructions, because it allows sets indexed by large ordinals to be collected as sets.

Example 7.113

Suppose $A$ is a set and the formula $\varphi(x,y)$ defines:

y=\{x\}

Then Replacement gives the set:

\{\{x\}:x\in A\}

This is the image of $A$ under the operation $x\mapsto\{x\}$ .

Axiom 7.114 (Infinity)

There exists a set containing the empty set and closed under the successor operation:

\exists I\,\bigl(\varnothing\in I\land \forall x\,(x\in I\to x\cup\{x\}\in I)\bigr)

The successor of a set $x$ is:

S(x)=x\cup\{x\}

The axiom of infinity guarantees the existence of an infinite set. It is the axiom that allows the construction of the natural numbers as sets.

Definition 7.115 (Natural Numbers as Sets)

The natural numbers are represented by finite ordinals:

0=\varnothing

1=\{0\}

2=\{0,1\}

3=\{0,1,2\}

and in general:

n+1=n\cup\{n\}

The set of all natural numbers is denoted:

\omega

Axiom 7.116 (Foundation)

Every nonempty set has an element disjoint from it:

\forall A\,\bigl(A\ne\varnothing\to \exists x\in A\,(x\cap A=\varnothing)\bigr)

This axiom is also called the axiom of regularity.

It prevents infinitely descending membership chains such as:

x_0\ni x_1\ni x_2\ni x_3\ni\cdots

It also rules out sets satisfying:

x\in x

Lemma 7.117 (No Set Is an Element of Itself)

Assuming Foundation, no set $x$ satisfies:

x\in x

Proof

Suppose, for contradiction, that:

x\in x

Consider the singleton:

A=\{x\}

This set is nonempty. By Foundation, there exists an element $y\in A$ such that:

y\cap A=\varnothing

Since $A=\{x\}$ , the only element of $A$ is $x$ , so:

y=x

Thus:

x\cap A=\varnothing

But $x\in x$ and $x\in A$ , so:

x\in x\cap A

This contradicts:

x\cap A=\varnothing

Therefore:

x\notin x

for every set $x$ .

Axiom 7.118 (Choice)

The axiom of choice says that for every set of nonempty pairwise disjoint sets, there is a set containing exactly one element from each of them.

One common formulation is:

For every set $A$ whose elements are nonempty sets, there exists a function $f$ with domain $A$ such that:

f(X)\in X

for every $X\in A$ .

Such a function is called a choice function.

Definition 7.119 (ZF and ZFC)

ZF is the theory consisting of the following axioms and axiom schemas:

Extensionality
Empty Set
Pairing
Union
Power Set
Separation
Replacement
Infinity
Foundation

ZFC is ZF together with the axiom of choice.

Thus:

\mathrm{ZFC}=\mathrm{ZF}+\mathrm{AC}

where $\mathrm{AC}$ denotes the axiom of choice.

Example 7.120

Let:

A=\{\{1,2\},\{3,4\},\{5,6\}\}

A choice function on $A$ may be given by:

f(\{1,2\})=1

f(\{3,4\})=3

f(\{5,6\})=5

The axiom of choice becomes important when the family of nonempty sets is infinite and no explicit rule is given for choosing one element from each set.

Theorem 7.121 (Equivalent Forms of Choice)

Over ZF, the following principles are equivalent:

The axiom of choice.
Every set can be well ordered.
Every surjective function has a right inverse.
Every vector space has a basis.
Every product of nonempty sets is nonempty.

Proof

We do not prove all equivalences here, but we explain the main connections.

The axiom of choice gives a way to choose elements during the construction of a well ordering, which yields the well ordering theorem.

If every set can be well ordered, then given any family of nonempty sets, choose the least element of each member under a well ordering of the union. This gives a choice function.

If every surjection has a right inverse, then applying this to the map from pairs $(X,x)$ with $x\in X$ onto the family of sets gives a choice function.

The equivalence with bases of vector spaces and products of nonempty sets shows that the axiom of choice appears throughout algebra, topology, and analysis, not only in set theory.

Cumulative Hierarchy

ZF is often understood through the cumulative hierarchy. Sets are built in stages.

Start with:

V_0=\varnothing

At a successor stage:

V_{\alpha+1}=\mathcal{P}(V_\alpha)

At a limit stage $\lambda$ :

V_\lambda=\bigcup_{\alpha<\lambda}V_\alpha

The universe of sets is then informally described as:

V=\bigcup_{\alpha\in\mathrm{Ord}}V_\alpha

This is not a set union over all ordinals inside ZF, but a class sized construction. It expresses the idea that every set appears at some stage of the hierarchy.

Definition 7.122 (Rank)

The rank of a set $x$ is the least ordinal $\alpha$ such that:

x\subseteq V_\alpha

Equivalently, $x$ appears by stage:

V_{\alpha+1}

Rank measures how deeply a set is built from the empty set.

Example 7.123

The empty set has rank:

0

The set:

\{\varnothing\}

has rank:

1

The set:

\{\varnothing,\{\varnothing\}\}

has rank:

2

Finite ordinals have finite rank, while sets involving $\omega$ may have infinite rank.

Classes and Sets

Not every definable collection is a set. A collection described by a formula may be too large to be a set. Such a collection is often called a proper class.

Examples include:

\{x:x=x\}

the collection of all sets, and:

\mathrm{Ord}

the collection of all ordinals.

These collections can be discussed informally or in class theories, but they are not sets in ZF.

Lemma 7.124 (There Is No Set of All Sets)

There is no set $V$ such that:

\forall x\,(x\in V)

Proof

Suppose such a set $V$ exists. By Separation, form:

R=\{x\in V:x\notin x\}

Since $V$ contains every set, the set $R$ is an element of $V$ . Therefore the defining condition applies to $R$ :

R\in R \quad \text{if and only if} \quad R\notin R

This is impossible. Hence there is no set of all sets.

Lemma 7.125 (There Is No Set of All Ordinals)

There is no set whose elements are exactly all ordinals.

Proof

Suppose, for contradiction, that:

O=\{\alpha:\alpha \text{ is an ordinal}\}

is a set.

Since every element of $O$ is an ordinal and ordinals are linearly ordered by membership, the union:

\bigcup O

is an ordinal. But because $O$ contains all ordinals:

\bigcup O\in O

Now $\bigcup O$ is an ordinal, so its successor:

(\bigcup O)+1

is also an ordinal. Hence:

(\bigcup O)+1\in O

But every element of $O$ is contained in $\bigcup O$ , so:

(\bigcup O)+1\subseteq \bigcup O

This is impossible, since:

\bigcup O\in(\bigcup O)+1

but:

\bigcup O\notin \bigcup O

Therefore the ordinals cannot form a set.

Role of ZF and ZFC

ZF provides the standard background theory for most ordinary mathematics. It supports the construction of numbers, ordered pairs, relations, functions, algebraic structures, topological spaces, and many other objects used throughout mathematics.

ZFC is stronger because it includes the axiom of choice. Many standard theorems depend on choice, including the well ordering theorem, Tychonoff theorem for arbitrary products, and the existence of bases for arbitrary vector spaces.

At the same time, some statements cannot be decided from ZF or ZFC alone, assuming these theories are consistent. Later chapters study this phenomenon through constructibility, forcing, independence, and large cardinals.