Set Theory/Zermelo-Fraenkel (ZF) Axioms

Formally, a set is not defined besides what the axioms say. We can define any collection of objects as a class, so that any set is a class, but not any class is a set (classes which are not set are sometimes known as proper classes).

The Zermelo-Fraenkel (ZF) Set Theory Axioms

In order to prove some of the fundamental results of set theory, and to begin to define other branches of mathematics based on it, we need to start with some axioms that we religiously take to be true. There are many possibilities for choices of axioms, but the most popular set of axioms is the Zermelo-Fraenkel system, or, more generally, Zermelo-Fraenkel with the Axiom of Choice.

We will start by saying that the universe is non-empty.

ZF1 (Axiom of Empty Set) $\exists y:\forall x:(x\notin y)$ "there exists a set with no elements."

We call a set that contains no elements, an empty set. A natural question to ask is whether such a set is unique.

We will need a notion of equality between sets.

ZF2 (Axiom of Extensionality) $\forall x:\forall y:((x=y)\Leftrightarrow (\forall z:(z\in x)\Leftrightarrow (z\in y)))$ "if two sets have the same elements, then they are said to be equal."

We can now prove the uniqueness of an empty set. We prove this informally, and use the argument: reductio ad absurdum. Which in English means proof by contradiction.

Proof:

• Suppose that an empty set is not unique.
• This means that there exists empty sets $x$ and $y$ such that $x\neq y$.
• So by ZF1, we have $z\notin y$ and $z\notin x$ for any set $z$.
• Therefore by ZF2, we have $x=y$ since $(z\in x)\Leftrightarrow (z\in y)$ for any set $z$ is vacuously true, or in Latin ex falso sequitur quodlibet.
• And thus we have our contradiction. So the empty set is unique. $\Box$

We define the empty set as $\emptyset$.

So far, we have only shown the existence of the empty set. Thus motivates our next axiom.

ZF3 (Axiom of Pair) $\forall x:\forall y:\exists m:\forall u:(u\in m)\Leftrightarrow ((u=x)\vee (u=y))$ "if we have two sets $x$ and $y$, then we can form an unordered pair set $m$ that contains exactly $x$ and $y$. We write this as $\{x,y\}$."

It follows directly from ZF2, that the unordered pair set is de facto unique (so our intuition that order does not matter in unordered pair sets is true, $\{x,y\}=\{y,x\}$). It also follows directly from ZF2 that if $x$ is a set, then by ZF3 we have a set containing $x$, i.e., $\{x\}$.

Our theory so far shows the existence of infinitely many sets. We get $\emptyset$ with ZF1, and by ZF3 we get $\{\emptyset \}$, and again by ZF3 we get $\{\{\emptyset \}\}$, and so on...

The notion of infinite here is used informally since we have not yet defined it.

The only con we currently have in our theory is that we can only form empty sets, singleton sets, and pair sets. More precisely, we can say,

• empty$(x):\Leftrightarrow (\forall y:y\notin x)$
• singleton$(x):\Leftrightarrow (\forall y:(x=\{y\}))$
• pair$(x):\Leftrightarrow (\forall y:\forall z:(x=\{y,z\})\wedge (y\neq z))$

We can now define an ordered pair set as $(x,y)=\{\{x\},\{x,y\}\}$. It is easy to see that if $x\neq y$, then $(x,y)\neq (y,x)$. This was defined by Kuratowski in 1921 .

To define larger sets, we need the following axiom.

ZF4 (Axiom of Union) $\forall x:\exists u:\forall y:(y\in u)\Leftrightarrow (\exists z:(y\in z)\wedge (z\in x))$ "for any set $x$, there exists another set whose elements are precisely the elements of the elements of $x$. We write the set $u$ as $\bigcup u$."

So, the union of sets $\{x,y\}$ and $\{z\}$ is simply $\{x,y,z\}$. Thus we have a triple set. We can continue unionising sets to form even larger sets.

We also have the usual notion of unionising two sets, i.e., the union of set $x$ and set $y$, which we write as $x\cup y$, is defined as $\bigcup \{x,y\}$.

ZF5 (Axiom schema of Replacement) Given a set $z$ and a formula in the language of set theory $\phi (x,y)$, such that for all $x$ there exists a unique $y$ such that $\phi (x,y)$ is true. Then there exists a set $a$ whose elements are all those $y$. We write this as the set $\{y\,|\,\exists x\in z:\phi (x,y)\}$.

Intuitively, we can think of this as the existence of a map.

The following axiom follows from ZF5, but we will write it since it is useful to have. We shall name it ZF 5.1 to exaggerate the fact that it can be proven from ZF5.

ZF 5.1 (Axiom schema of Separation / Restricted Comprehension) Given a set $y$ and a formula in the language of set theory $\phi (x)$. Then we have a set of all $z\in y$ such that $\phi (z)$ is true. We write this as the set $\{z\in y\,|\,\phi (z)\}$.

The uniqueness of such a set (both from ZF5 and ZF 5.1) follows from ZF2.

ZF5 and ZF 5.1 are both axiom schemes since it comprises infinitely many axioms - one for each formula $\phi$. Notice that the restriction $x\in A$ in this axiom helps us to avoid Russell's paradox - in this paradox a "set" of the form $\{x\,|\,P(x)\}$, with $P(x)=x\not \in x$, was used.

From this, we can now define the intersection set. We define the intersection of set $x$, denoted as $\bigcap x$, as $\{z\in \bigcup x\,|\,(\forall y\in x:z\in y)\}$.

Note that we can now define the subset abbreviation symbol $\subseteq$. We say $x\subseteq y$ to mean $\forall a:(a\in x)\Rightarrow (a\in y)$. Exercise: Explain why the complement set of set $x\subseteq y$ is de facto a set.

Now we can prove that the universal set is not a set. We use the same argument as above, i.e., reductio ad absurdum.

Theorem. The set of all sets is not a set. Proof: Suppose the universal set exists, and let $V=\{x\,|\,x=x\}$, which is the universal set since it contains everything in the universe. Now let $V^{\prime }=\{x\in V\,|\,x\notin x\}$. This is also a set by ZF 5.1. We know $V^{\prime }\in V$ since $V$ contains everything. So if $V^{\prime }\in V^{\prime }$, then $V^{\prime }\notin V^{\prime }$, and if $V^{\prime }\notin V^{\prime }$ then $V^{\prime }\in V^{\prime }$. Which is a contradiction. Thus the universal set is not a set. $\Box$

ZF6 (Axiom of Power Set) $\forall x:\exists y:\forall z:(z\in y)\Leftrightarrow (\forall a:(a\in z)\Rightarrow (a\in x))$ "if $x$ is a set, then there exists a set ${\mathcal {P}}(x)$ whose elements are the subsets of $x$."

So the power set of an empty set, is the set of an empty set, i.e., ${\mathcal {P}}(\emptyset )=\{\emptyset \}$.

As we will see, there is no way to define an infinite set given our current axioms, so we require the following axiom.

ZF7 (Axiom of Infinity) An inductive set exists. An inductive set is a set $I$ such that, $\emptyset \in I$, and $x\in I\Rightarrow x\cup \{x\}\in I$.

The following axiom is somewhat of a convention but various models of set theory have been defined without it, or even using axiom stating things close to the opposite.

ZF8 (Axiom of Regularity) For every non-empty set $x$ there is some $y\in x$ such that $x\cap y=\emptyset$.

These eight axioms complete the list of axioms for ZF Set Theory.

The next axiom is called the Axiom of Choice or AC for short. ZF together with AC is called ZFC Set Theory.

ZFC9 Axiom of Choice (AC) For every set $S$ of nonempty disjoint sets, there exists a function $f$ defined on $S$ such that, for each set $x\in S$, $f(x)\in x$.