Is this theorem equivalent to Transfinite Recursion Theorem?

Question

Let $V$ be the class of all sets, $\operatorname{Ord}$ be the class of all ordinals, and $G:V\to V$ be a class function.

Transfinite Recursion Theorem:

There exists a class function $F:\operatorname{Ord}\to V$ such that $F(\alpha)=G(F\restriction \alpha)$ for all $\alpha\in\operatorname{Ord}$.

---

While I'm able to prove that Transfinite Recursion Theorem implies the below theorem, I have tried but to no avail in proving that the theorem implies Transfinite Recursion Theorem.

I would like to ask if it is possible to prove that this theorem implies Transfinite Recursion Theorem.

Thank you for your help!

---

Theorem:

Let $G_1,G_2,G_3$ be class functions from $V$ to $V$. There exists a class function $F:\operatorname{Ord}\to V$ such that

(1) $F(0)=G_1(\emptyset)$

(2) $F(\alpha+1)=G_2(F(\alpha))$ for all $\alpha\in\operatorname{Ord}$

(3) $F(\alpha)=G_3(F\restriction\alpha)$ for all limit $\alpha\neq 0$

Answer 1

The trick is to not construct $F$ itself, but to construct the function $H$ which sends $\alpha$ to $F\restriction \alpha$. That way, at successor steps you have access to the entire history of the recursion so far and not just the last step.

In detail, given $G:V\to V$, we define $G_1$, $G_2$, and $G_3$ as follows: $$G_1(x)=\emptyset$$ $$G_2(x)=x\cup\{(\operatorname{dom}(x),G(x))\}$$ $$G_3(x)=\bigcup\operatorname{ran}(x)$$ By the theorem, we then get a function $H:Ord\to V$ such that $H(0)=G_1(\emptyset)$, $H(\alpha+1)=G_2(H(\alpha))$, and $H(\alpha)=G_3(H\restriction\alpha)$ for $\alpha\neq 0$ limit. It is then easy to prove by induction that $H(\alpha)$ is a function with domain $\alpha$ for each $\alpha$, with $H(\alpha)\restriction \beta=H(\beta)$ for all $\beta<\alpha$. So, defining $F=\bigcup\operatorname{ran}(H)$, $F$ is a function on $Ord$ with $F\restriction\alpha=H(\alpha)$ for each $\alpha$. For each $\alpha$, we then have $$F(\alpha)=H(\alpha+1)(\alpha)=G_2(H(\alpha))(\alpha)=G_2(F\restriction\alpha)(\alpha).$$ Since $\operatorname{dom}(F\restriction\alpha)=\alpha$, our definition of $G_2$ tells us that $$F(\alpha)=G_2(F\restriction\alpha)(\alpha)=G(F\restriction\alpha),$$ as desired.

Answer 2

I fill in @Eric Wofsey's proof with detail and post it here. All credits are given to @Eric Wofsey.

---

Given $G:V\to V$, we define $G_1$, $G_2$, and $G_3$ as follows: $$\begin{align}&G_1(x)=\emptyset\text{ for all }x\\&G_2(x)=\begin{cases} x\cup\{(\operatorname{dom}(x),G(x))\}&\text{if }x\text{ is a function}\\\emptyset&\text{otherwise}\end{cases}\\&G_3(x)=\begin{cases} \bigcup\operatorname{ran}(x)&\text{if }x\text{ is a function}\\\emptyset&\text{otherwise}\end{cases}\end{align}$$

By The theorem, there is a class function $H:\operatorname{Ord}\to V$ such that $H(0)=G_1(\emptyset)$, $H(\alpha+1)=G_2(H(\alpha))$, and $H(\alpha)=G_3(H\restriction\alpha)$ for $\alpha\neq 0$ limit.

First, we prove by induction that $H(\alpha)$ is a function with domain $\alpha$ for all $\alpha\in\operatorname{Ord}$ and with $H(\alpha)\restriction \beta=H(\beta)$ for all $\beta<\alpha$.

• $H(0)=G_1(0)=\emptyset$. Then the statement is trivially true for $\alpha=0$.

• Assume that the statement is true for $\alpha$. Then $H(\alpha+1)=G_2(H(\alpha))=$ $H(\alpha)\cup\{(\operatorname{dom}(H(\alpha)),G(H(\alpha)))\}=H(\alpha)\cup\{(\alpha,G(H(\alpha)))\}$. It follows that $\operatorname{dom}(H(\alpha+1))=\operatorname{dom}(H(\alpha))\cup \{\alpha\}=\alpha\cup \{\alpha\}=\alpha+1$. For $\beta=\alpha$, $H(\alpha+1)\restriction \beta=H(\alpha+1)\restriction \alpha=H(\alpha)=H(\beta)$. For $\beta<\alpha$, $H(\alpha+1)\restriction \beta=$ $H(\alpha)\restriction \beta=H(\beta)$. Thus $H(\alpha+1)\restriction \beta=H(\beta)$ for all $\beta<\alpha+1$.

• Assume that the statement is true for all $\beta<\alpha$ where $\alpha\neq\emptyset$ is limit ordinal. Then $H(\alpha)=G_3(H(\alpha))=\bigcup\operatorname{ran}(H(\alpha))=\bigcup\{H(\beta)\mid \beta<\alpha\}$. For any $\beta_1\le\beta_2<\alpha$: $H(\beta_2)\restriction\beta_1=H(\beta_1)$and thus $H(\beta_1)\subseteq H(\beta_2)$. Then $H(\alpha)=\bigcup\{H(\beta)\mid \beta<\alpha\}$ is actually a function. It follows that $\operatorname{dom}(H(\alpha))=\bigcup_{\beta<\alpha}\operatorname{dom}(H(\beta))=\bigcup_{\beta<\alpha}\beta=\alpha$ since $\alpha$ is limit ordinal. Moreover, $H(\alpha)\restriction \beta=\{(\gamma,H(\alpha)(\gamma))\mid \gamma<\beta\}=\{(\gamma,H(\gamma+1)(\gamma))\mid \gamma<\beta\}=$ $\{(\gamma,H(\beta)(\gamma))\mid \gamma<\beta\}=H(\beta)$.

As a result, $\forall\beta<\alpha:H(\alpha)\restriction \beta=H(\beta)$ and thus $\forall\beta<\alpha:H(\beta)\subsetneq H(\alpha)$.

Next we define $F=\bigcup\operatorname{ran}(H)$. Then $F=\bigcup\{H(\alpha)\mid \alpha\in\operatorname{Ord}\}$ is a function with domain $\operatorname{Ord}$ and with $F\restriction\alpha=\{F(\beta)\mid\beta<\alpha\}=\{H(\beta+1)(\beta)\mid\beta<\alpha\}=\{H(\alpha)(\beta)\mid\beta<\alpha\}=H(\alpha)$ for all $\alpha\in\operatorname{Ord}$.

Since $F\restriction\alpha=H(\alpha)$ and $\operatorname{dom}(H(\alpha))=\alpha$, $\operatorname{dom}(F\restriction\alpha)=\alpha$. Then $G_2(F\restriction\alpha)=(F\restriction\alpha)\cup \{(\alpha,G(F\restriction\alpha))\}$ and thus $G_2(F\restriction\alpha)(\alpha)=G(F\restriction\alpha)$.

For each $\alpha\in\operatorname{Ord}$, we have $F(\alpha)=H(\alpha+1)(\alpha)=G_2(H(\alpha))(\alpha)=G_2(F\restriction\alpha)(\alpha)=G(F\restriction\alpha)$.

---

Update: I have found another way to define $F$

We define $F$ as follows $F(\alpha):=H(\alpha+1)(\alpha)$

Then $F(\alpha)=H(\alpha+1)(\alpha)=G_2(H(\alpha))(\alpha)=(H(\alpha)\cup\{(\operatorname{dom}(H(\alpha)),G(H(\alpha)))\})(\alpha)=(H(\alpha)\cup\{(\alpha,G(H(\alpha)))\})(\alpha)=G(H(\alpha))$.

Moreover, $H(\alpha)=\{(\beta,H(\alpha)(\beta))\mid\beta<\alpha\}=\{(\beta,H(\beta+1)(\beta))\mid\beta<\alpha\}=\{(\beta,F(\beta))\mid\beta<\alpha\}=F\restriction\alpha$.

Thus $F(\alpha)=G(H(\alpha))=G(F\restriction\alpha)$.