Notes - Set Theory HT25, Replacement

If $a$ is a set and $F : a \to \mathbf V$ is a class function, then the range

\[\mathbf F[a] := \\{\mathbf F(x) : x \in a\\}\]

is a set.

For each parameterised $\mathcal L$-formula $\phi(x, y, z _ 1, \ldots, z _ n)$, introduce the axiom

\[\forall z_1 \cdots \forall z_n \forall w (\forall x \in w \exists y (\phi(x, y, z_1, \ldots, z_n) \land \forall y' (\phi(x, y', z_1, \ldots, z_n) \to y' = y)) \to \exists v \forall u (u \in v \leftrightarrow \exists x \in w \text{ } \phi(x, u, z_1, \ldots, z_n)))\]

Suppose:

• $X$ is a set
• $G : \mathbf V \to \mathbf V$ is a class function
• $x _ 0 \in X$

Then there exists a unique function $f : \omega \to \mathbf V$ such that

• $f(0) = x _ 0$
• $f(n^+) = G(f(n))$

Consider the function $f : \mathbb N \to \mathbf{ON}$ defined recursively by $f(0) = \omega$ and $f(x) = \mathbf G(x) = x^+$ so that $f(n) = \omega + n$. Then by replacement, $\text{ran}(f)$ is a set, and hence $\bigcup \text{ran}(f) = \bigcup _ n (\omega + n) =: \omega + \omega$ is the ordinal we were looking for.

Consider the function $f$ defined by recursion via

• $f(0) = \mathbb N$
• $f(x^+) = \mathcal P(x)$

(this uses the class function version of definition by recursion). Then $\text{ran}(f) = f[\mathbb N]$ is a set that could be written as $\{\mathbb N, \mathcal P(\mathbb N), \mathcal P(\mathcal P(\mathbb N)), \ldots\}$. Then if $X := \bigcup f[\mathbb N]$, for any $n \in \mathbb N$ we have $f(n) \subseteq X$ and hence $ \vert X \vert \ge f(n)$.

Suppose:

• $\mathbf G : \mathbf V \to \mathbf V$ is a class function

Then:

• There exists a unique class function $\mathbf F : \mathbf{ON} \to \mathbf V$ such that for all $\alpha \in \mathbf{ON}$, $\mathbf F(\alpha) = \mathbf G(\mathbf F \vert _ \alpha)$.

Suppose:

• $x _ 0$ is a set
• $\mathbf S : \mathbf V \to \mathbf V$

Then there is a unique class function $\mathbf F : \mathbf{ON} \to \mathbf V$ such that:

• $\mathbf F(0) = x _ 0$
• $\mathbf F(\alpha^+) = \mathbf S(\mathbf F(\alpha))$ for all $\alpha \in \mathbf{ON}$
• If $\eta \in \mathbf{ON}$ is a limit ordinal, then $\mathbf F(\eta) = \bigcup \{\mathbf F(\beta) : \beta \in \eta\} = \bigcup \mathbf F[\eta]$.

Define $\mathbf G(f)$ as follows.

• If $f$ is a function with $\text{dom}(f) = \beta$:
  • If $\beta = 0$, then set $G(f) = x _ 0$
  • If $\beta = \alpha^+$ a successor, then set $\mathbf G(f) = \mathbf S(f(\alpha))$
  • Otherwise, set $\mathbf G(f) := \bigcup \text{ran}(f)$.
• Otherwise:
  • Set $\mathbf G(f) := 0$

Now apply the result to obtain $\mathbf F$ with $\mathbf F(\beta) = \mathbf G(\mathbf F \vert _ \beta)$ and note that it satisfies all required properties.

Suppose:

• $\mathbf X$ is a class
• $\mathbf G _ 0 : \mathbf X \to \mathbf V$ is a class function
• $\mathbf G _ + : \mathbf X \times \mathbf V \to \mathbf V$ is a class function

Then there exists a unique class function $\mathbf F : \mathbf X \times \mathbf{ON} \to \mathbf V$ such that for all $b \in \mathbf X$,

• $\mathbf F(b, 0) = \mathbf G _ 0(b)$
• $\mathbf F(b, \alpha^+) = \mathbf G _ + (b, \mathbf F(b, \alpha))$ for all $\alpha \in \mathbf{ON}$
• If $\eta \in \mathbf{ON}$ is a limit ordinal, then $\mathbf F(b, \eta) = \bigcup \{\mathbf F(b, \beta) : \beta \in \eta\}$.