The final pages of the first chapter of Set Theory expound on a few more ZF axioms.

The axiom of power set

Let’s kick off by defining subset. We say $u$ is a subset of $X$ iff $\forall z (z \in u \implies z \in X)$. This is written as $u \subset X$. A proper subset of a set $X$ is a subset of $X$ that isn’t equal to $X$.

The axiom of power set guarantees for any set $X$, the set of subsets of $X$ exists: $$ \forall X \exists Y \forall u (u \subset X \iff u \in Y) $$ The axiom of power set allows us to define the Cartesian product.

The Cartesian product of two sets is a set

The Cartesian product of $X$ and $Y$ is written $X \times Y$ and is defined to be $$ X \times Y = \{ (x, y) \mid x \in X \land y \in Y \} $$ Let’s take a moment to prove that $X \times Y$ is in fact a set.

Proof $X \times Y$ is a set

We want to show that $X \times Y \subset \mathcal{P}(\mathcal{P}(X \cup Y))$; since a subset of a set is a set, this would prove $X \times Y$ is a set. This is equivalent to $$\forall u (u \in X \times Y \implies u \in \mathcal{P}(\mathcal{P}(X \cup Y)))$$ which would mean that $$\forall u (u \in X \times Y \implies u \subset \mathcal{P}(X \cup Y)$$ which in turn means for that same $u$ $$\forall z ( z \in u \implies z \in \mathcal{P}(X \cup Y))$$ notice again $z \in \mathcal{P}(X \cup Y) \iff z \subset (X \cup Y)$. Let $u = (x,y)$ be an element in $X \times Y$. By the definition of ordered pairs, $u = (x,y) = \{ \{x\}, \{x,y\} \}$. Now let $z$ be arbitrary in $u$: either $z = \{x\}$ or $z=\{x, y\}$. Since $x\in X$ and $y\in Y$ by assumption, $\{x\} \subset X \cup Y$ and $\{x, y\} \subset X \cup Y$. Either way $z \subset X \cup Y$, which definitionally means $z \in \mathcal{P}(X \cup Y)$.

$u$ therefore contains only elements in $\mathcal{P}(X \cup Y)$ so $u \subset \mathcal{P}(X \cup Y)$; in turn this implies $u \in \mathcal{P}(\mathcal{P}(X \cup Y))$. Since $u$ is arbitrary from $X \times Y$, we have that $X \times Y \subset \mathcal{P}(\mathcal{P}(X \cup Y))$. Thus $X \times Y$ is a set.

Relations, arity, functions

First, more notation: define $$ X_1 \times X_2 \times \dots \times X_n = (X_1 \times X_2 \times \dots \times X_{n-1}) \times X_n $$ and define $$ X^n = \underbrace{X \times X \times \dots \times X}_{n \text{ times}}$$ $X^n$ is a set of $n$-tuples with elements in $X$.

If $R$ is a subset of $X^n$ for some set $X$, we say $R$ is a relation of arity $n$. Typically we’ll write $R(x_1, x_2, \dots, x_n)$ instead of $(x_1, x_2, \dots, x_n) \in R$, but this is just a notational convention. If the arity of a relation $R$ is two we call $R$ a binary relation and write $x_1 R x_2$ to mean $(x_1, x_2) \in R$. Define the domain¹ of a relation $R$ to be $$ \text{dom}(R) \equiv \{ u \mid \exists v ( (u,v) \in R ) \} $$ and the range to be $$ \text{ran}(R) \equiv \{ v \mid \exists u ( (u,v) \in R ) \} $$ These are just the familiar concepts of domain and range presented in different notation. This concept is less familiar: define the field of a relation $R$ as $$ \text{field}(R) = \text{dom}(R) \cup \text{ran}(R) $$

Let’s take a moment to satisfy ourselves that the domain and range of a relation are both sets. Jech claims that $ \text{dom}(R) \subset \bigcup \bigcup R$, and I’ll momentarily explain why that makes sense. Let $R$ be a binary² relation over a set $X$. So $R$ is a set of ordered pairs with elements in $X^2$; we have $$ R = \{ (u_1, v_1), (u_2, v_2), \dots \} $$ and then $$ \bigcup R = (u_1, v_1) \cup (u_2, v_2) \cup \dots $$ which by the definition of ordered pairs is $$ \bigcup R = \{ \{u_1\}, \{u_1, v_1\} \} \cup \{ \{u_2\}, \{u_2, v_2\} \} \cup \dots $$ The union of that set is \begin{align*} \bigcup \bigcup R &= \{ u_1 \} \cup \{ u_1, v_1\} \cup \{ u_2 \} \cup \{ u_2, v_2 \} \cup \dots \\ &= \{ u_1, u_2, \dots v_1, v_2, \dots \} \end{align*} It should be clear that $\bigcup \bigcup R$ is a set containing all $u$ and $v$ such that $(u,v) \in R$ and is therefore a superset of $\text{dom}(R)$ and $\text{ran}(R)$.

Jech closes out this section by defining some very usual concepts like functions and their images, so we’ll move on to the next axiom.

Axiom of infinity

It’s pretty clever how you define an infinite set without yet even having defined the natural numbers. It goes like this: $$ \exists S ( \emptyset \in S \land \forall x ( x \in S \implies x \cup \{x\} \in S ) ) $$ Take a moment with that definition. We get $\emptyset \in S$. Next we’re guaranteed that $ \{ \emptyset \} \in S$ (this is $\emptyset$’s “successor”). But the successor of $\{ \emptyset \}$ is in $S$: we have $ \{ \{ \emptyset \} \} \in S$. The process doesn’t stop. $S$ should satisfy your intuitive definition of “infinite”; it’s a so-called inductive set. That’s all there is to say about the axiom of infinity for now.

The schema of replacement

The schema of replacement states that if $f$ is a function, then for any $X$, $f[X] = \{ f(x) \mid x \in X \}$ is a set. Jech gives this in formal notation: let $\phi(x,y,z)$ be a formula. Then $$ \forall x \forall y \forall z (\phi(x,y,p) \land \phi(x,z,p) \implies y = z) \implies \forall X \exists Y \forall y (y \in Y \iff (\exists x \in X)\phi(x,y,p))$$ Like the schema of replacement, the schema of replacement generates infinitely many axioms by induction over the number of parameters $p$. If we wanted to prove this we’d use the same strategy as before: replace $p$ by $p_1, \dots, p_n$ and use the definition of ordered sets. Two fun ways to restate the schema of replacement are:

• If $F$ is a function and $\text{dom}(F)$ is a set, then $\text{ran}(F)$ is a set
• If $F$ is a function and $X$ is a set, the $F\big| X$ is a set

In the second restatement, $F\big| X$ is read as “$F$ restricted to $X$” and is definitionally $$ F \big| X = \{ (x,y) \in F \mid x \in X \} $$

That’s it for ch. 1. I’ll do all the exercises in the next post. Should be fun.