How do Hrbacek and Jech derive the class function $F$ in Theorem 4.12 from Theorem 4.11?

Question

My question is about a proof of Theorem 4.12 given in the text Introduction to Set Theory by Hrbacek and Jech.

---

Let $V$ be the class of all sets, $\operatorname{Ord}$ be the class of all ordinals, and $G,G_1,G_2,G_3$ be class functions from $V$ to $V$.

Theorem 4.11:

There exists a class function $F:V\times\operatorname{Ord}\to V$ such that, for all $z\in V$

$F(z,0)=G_1(z,\emptyset)$

$F(z,\alpha+1)=G_2(z,F_z(\alpha))$ for all $\alpha\in\operatorname{Ord}$, with $F_z(\alpha):=F(z,\alpha)$

$F(z,\alpha)=G_3(z,F_z\restriction\alpha)$ for all $\alpha\neq 0$ limit, with $F_z\restriction \alpha:=\{\langle\beta,F(z,\beta)\rangle\mid\beta<\alpha\}$

Theorem 4.12:

For any set $a$, there is a unique infinite sequence $(f_n\mid n\in \Bbb N)$ such that

(1) $f_0=a$

(2) $f_{n+1}=G(f_n,n)$ for all $n\in \Bbb N$

The proof for Theorem 4.12 is given in the text as follows:

Let $G:V\to V$ be a class function. We want to find, for every set $a$, a sequence $(f_n\mid n\in \Bbb N)$ such that $f_0=a$ and $f_{n+1}=G(f_n,n)$ for all $n\in \Bbb N$. By Theorem 4.11, there is class function $F$ such that $F(0)=a$ and $F(n+1)=G(F(n),n)$ for all $n\in \Bbb N$. Now we apply the Axiom of Replacement: There exists a sequence $(f_n\mid n\in \Bbb N)$ that is equal to $F\restriction \omega$ and the Theorem follows.

---

I don't understand how Theorem 4.11 is used to derive the class function $F$ in the proof of Theorem 4.12. Can someone elaborate on how to obtain the desired $F$?

Thank you for your help!

Answer 1

Here is one way. define auxilliary functions $G_1$, $G_2$ and $G_3$. To get what you want. And afterwards you have to modify the resulting function a bit. Define $G_1(z,\emptyset)=\langle z,0\rangle$, and $G_2(z,\langle x,y\rangle) = \langle G(x,y),y\cup\{y\}\rangle$, and $G_3(z,x)=G(x)$ (these are the important cases, in all other cases set the value to $\emptyset$. Theorem 4.11 gives you a function $H$ that satisfies its conclusions. Note that $H(z,0)=\langle z,0\rangle$, that $H(z,n+1) = G_2(z,H(z,n)) = \langle G(H_1(z,n)),H_2(z,n)), H_2(z,n)+1\rangle$ ($H_1$ and $H_2$ are the coordinates of $H$.. Prove by induction that $H_2(z,n)=n$ for all $n$, so that $H(z,n+1)$ is actually equal to $\langle G(H_1(z,n)), n+1\rangle$. Finally then define $F(n)=H_1(a,n)$, that $F$ is as needed in the proof.

Because you can use ordered pairs you can code a lot of stuff into this kind of recursions.

Answer 2

I fill in @hartkp's proof with details. All credits are given to @hartkp.

---

\begin{align}&G_1(x)=\begin{cases} \langle z,0\rangle&\text{if }x=\langle z,\emptyset\rangle\\\emptyset&\text{otherwise}\end{cases}\\\\&G_2(x)=\begin{cases} \langle G(y,\alpha),\alpha\cup\{\alpha\}\rangle&\text{if }x=(z,\langle y,\alpha\rangle)\\\emptyset&\text{otherwise}\end{cases}\\&G_3(x)=\begin{cases} G(\alpha)&\text{if }x=(z,\alpha)\\\emptyset&\text{otherwise}\end{cases}\end{align}

By Theorem 4.11, there exists a class function $H:V\times\operatorname{Ord}\to V$ such that, for all $z\in V$

• $H(z,0)=G_1(z,\emptyset)$

• $H(z,\alpha+1)=G_2(z,H_z(\alpha))$ for all $\alpha\in\operatorname{Ord}$

• $H(z,\alpha)=G_3(z,H_z\restriction\alpha)$ for all $\alpha\neq 0$ limit

First, we prove that $H(a,n)$ is of the form of an ordered pair $\langle f_n,n\rangle$ for all $n\in\Bbb N$.

• $H(a,0)=G_1(a,\emptyset)=\langle a,\emptyset\rangle=\langle a,0\rangle=\langle f_0,0\rangle$ where $f_0=a$. Thus the statement is trivially true for $n=0$.

• Assume that $H(a,n)$ is of the form of an ordered pair $\langle f_n,n\rangle$. Then $H(a,n+1)=G_2(a,H_a(n))=G_2(a,H(a,n))=G_2(a,\langle f_n,n\rangle)$ $=\langle G(f_n,n),n\cup\{n\}\rangle=\langle G(f_n,n),n+1\rangle=\langle f_{n+1},n+1\rangle$ where $f_{n+1}=G(f_n,n)$. Thus the statement is true for $n+1$.

From $(H(a,n)\mid n\in\Bbb N)$, we extract the desired sequence $(f_n\mid n\in\Bbb N)$.