Axioms: Sets (ZF and ZFC)

In a previous post Axioms: Sets (Russell’s Paradox) we discussed axiomatic systems and we explored an example of why we might need one. Here we will view the axiomatic system that “fixed” naive set theory. This material will be a little heavy so in between each axiom We will see a little intuition to better help understand the system. This list is known as the Zermelo-Fraenkel axioms, and is the most widely used system in modern mathematics. We cannot however just dive right in. As seen in the tree analogy, we need to know our undefined terms and definitions. Recall that we are assuming the logical system is understood.

Our undefined terms will be set and the binary relation of membership, $\in$ when we write $x\in y$ it will read as “$x$ is a member of $y$.  We will use capital letters and $x, y$ to represent sets.

(1) AXIOM (of Extensionality) : For every $x$ and for every $y$ and for every $z$ if $z\in x$ implies $z\in y$ and is $z\in y$ implies $z\in x$ then $x = y$. This can also be stated as

$\forall x \forall y \forall z (z\in x$ $\Leftrightarrow$ $z\in y \Rightarrow x = y)$.

We have here what it means for two sets to be equal. That is, two sets are equal if they contain the same members. The next axiom guarantees the existence of subsets in a way.

(2) AXIOM (Schema of Comprehension): Suppose $P(z)$ is a property of z. For every $z$ there exists $y$ so that $z \in y$ if and only if $(z\in x)$ and $P(z)$ is true. We see this as,

$\forall x \forall P \exists y\forall z(z\in Y \Leftrightarrow (z\in X) \& P(z))$

DEFINITION: The set $y$ is a subset of the set $x$ if and only if $z\in y$ implies $z\in x$, in this case we write $y\subset x$.

Suppose we are given $P(z) = z\neq z"$. Then for any $A$ we are guaranteed, by the Axiom Schema of Comprehension, that there is some $B$ whose elements all satisfy $P(z)$. But since there is nothing that satisfies $P(z)$ we conclude $B$ contains no elements. Notice, as of right now, our $B$ depends on a given $A$. Suppose there is some other set, $C$ with no members. Then the statement $z\in B \Rightarrow z\in C$ is vacuously true as the antecedent $z\in B$ is always false. We use the same reasoning to see that the statement $z\in C \Rightarrow z\in B$. We conclude then by the Axiom of Extensionality that $B = C$. (this is actually a proof of the proposition: “There exists a unique set with no elements”) Hence, the set with no elements exists and is unique, so we obtain the following definition.

DEFINITION: The set with no elements will be called the empty set and will be denoted, $\emptyset$.

Notice the empty set is a subset of every set since the statement $z\in\emptyset \Rightarrow z\in x$ is vacuously true. The next axiom allows us to “build” sets in a way. It tells us that we can find a set containing two given sets.

(3) AXIOM (of Pairing): For any $x$ and $y$, there exists $z$ so that $x\in z$ and $y\in z$.

$\forall x \forall y \exists z ((x\in z) \& (y\in z))$

Notice that this axiom does not give us that $z$ contains only $x$ and $y$. For this we have the following proposition.

PROPOSITION: For any pair $x, y$ there exists a unique set $\{x,y\}$ containing exactly $x$ and $y$ as its only members.

Proof: Let $z$ be a set containing $x$ and $y$ by the Axiom of Pairing. Let $P(w)$ be the statement “$w=x$ or $w=y$“. By logic and the Axiom Schema of Comprehension we find that $\{x,y\}$ exists. We conclude that $\{x,y\}$ is unique by the Axiom of Extensionality.

From the Axiom of pairing we also get for any set $w$ the set $\{w\}$ is valid. And, we get that $w\neq \{w\}$. This will come in handy later but first,

(4) AXIOM (of Union): For any set $x$ there exists a set $\cup x$ whose elements contain all of those elements in the members of $x$.

$\forall x \exists y \forall z (z\in y \Leftrightarrow \exists w((w\in X) \& (z\in w)))$

Let $x$ and $y$ be sets. We can use the Axiom of Pairing to obtain a set $\{x,y\}$. Then the axiom of union guarantees $x\cup y$ exists.  But what about intersections? We have actually had the definition of intersection all along. Let $P(z)$ be the statement “$z\in y$“. Then we obtain by the Axiom Schema of Comprehension, there is a $w$ containing elements $z$ of $x$ for which $P(z)$ is true. But this makes $w$ exactly the set of all $z$ for which $z\in x$ and $z\in y$. Hence $w = x\cap y$. We obtain the following definitions.

DEFINITION: Let $x$ and $y$ be sets. The union of $x$ and $y$ is the set $x\cup y$ where $z \in x\cup y$ if and only if $z\in x$ or \$latex z\in y.

The intersection of $x$ and $y$ is the set $x\cap y$ for which $z\in x\cap y$ if and only if $z\in x$ and $z\in y$.

(5) AXIOM (of Replacement):  Let $P(x,y)$ be a property such that for every $x$ there is a unique $y$ so that $P(x,y)$ holds. Then for every $A$ there exists a $B$ such that for every $x\in A$ there is a $y\in B$ so that $P(x,y)$ is true.

$\forall P (\forall x \exists ! y ( P(x,y)) \Rightarrow \forall A \exists B \forall z (z \in A \Rightarrow \exists w((w\in B) \& (P(z,w))$

We can use this axiom along with the Axiom Schema of Comprehension to show that there is a set containing exactly the $y$ that satisfy $P(x,y)$. We can show it is unique by the Axiom of Extensionality. (Try this!)

(6) AXIOM (of Infinity): There is a set $x$ so that $\emptyset \in x$ and whenever $y\in x$, $y\cup \{y\} \in x$.

$\exists x ((\emptyset \in x) \& \forall y (y\in x)\Rightarrow (y\cup\{y\}\in x))$

From this we find $\emptyset \in x$, $\emptyset\cup\{\emptyset\} = \{\emptyset\} \in x$, and $\emptyset\cup\{\emptyset\}\cup\{\emptyset, \{\emptyset\}\} = \{\emptyset, \{\emptyset\}\}\in x$, and so on. Let $P(w)$ be the property that $w$ is one of these sets. Then we define the set $\mathbb{N}$ to be the set of all $w$ so that $P(w)$ is true. This is no mistake for this set is exactly what we will call the natural numbers. In this way we replace these sets with notation, $0 = \emptyset, 1 = \{\emptyset\}, 2 = \{\emptyset, \{\emptyset\}\}, ...$ There are many more intricacies of this process (such as uniqueness) that we will not delve into in this post. For our subject is that of Zermelo-Fraenkel axioms. So we shall proceed from this topic.

(7) AXIOM (of Power Set): For every set $x$ there exists a set $y$ so that $z\subset x$ implies $z\in y$.

$\forall x \exists y \forall z (z\subset x \Rightarrow z\in y$

From this axiom (and the others we have used) we can define the unique power set of a set (prove it!).

DEFINITION: Let $x$ be a set. The power set of $x$, $\mathcal{P}(x)$, is the set which contains exactly all of the subsets of $x$.

The next axiom will complete the list for Zermelo-Fraenkel (ZF) set theory.

(8) AXIOM (of Foundation): Every nonempty set (a set so that $x\neq \emptyset$) contains a member $y$ so that $x\cap y = \emptyset$.

$\forall x (x\neq \emptyset)\Rightarrow \exists y ((y\in x)\&(y\cap x = \emptyset))$.

The Axiom of Foundation tells us that if $x$ is a set then $x\notin x$. (Why?) Then we see that in this system Russell’s Paradox is not possible. The final axiom is the Axiom of Choice. This is a very controversial axiom, so in the interest of space we will simply state it in this post.

(9) AXIOM (of Choice): Suppose $X$ is a collection of nonempty sets. There exists a function $f$ that assigns to each set $x\in X$ an element $z\in x$.

The axiomatic system formed by (1)-(9) is known as ZF+C or ZFC and is the most widely used and accepted system in mathematics today. In the next post we will explore the Axiom of Choice and its equivalents. We have seen that, by assuming the Axiom of Choice, it is possible to split a sphere into two spheres that are congruent to the original. The next axiomatic system we will look at is Bernays-Gödel-von Neumann axiomatics as presented in Dugundji’s Topology. This will be the last set theory system we will explore for a while.