Are these two parametric versions of Transfinite Recursion equivalent?

179 Views Asked by At

Although I'm able to prove $S_1\implies S_2$ with not much difficulty, I failed to prove $S_2\implies S_1$ after several attempts. In particular, I can not handle the case in which $F(z,\alpha+1)=G_2(z,F_z(\alpha))$, as our desired result is $F(z,\alpha+1)=G_2(z,F_z\restriction \alpha+1)$. My failure stems from the fact that $F_z(\alpha)$ is an output of a function, whereas $F_z\restriction \alpha+1$ is itself a function.

Please leave me some hints to prove $S_2\implies S_1$! Thank you for your dedicated help!


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$.

$S_1:$

There exists a class function $F:V\times\operatorname{Ord}\to V$ such that $F(z,\alpha)=G(z,F_z\restriction \alpha)$ for all $z\in V$ and for all $\alpha\in\operatorname{Ord}$, with $F_z\restriction \alpha:=\{\langle\beta,F(z,\beta)\rangle\mid\beta<\alpha\}$.

$S_2:$

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\}$


Update: I have tried to replicate the proof here. Everything seems to be fine until I'm unable to define the desired $F$ from $H$. Please shed me some lights!

Given $G$, We define $G_1,G_2,G_3$ as follows

$$\begin{align}&G_1(z,x)=\emptyset\text{ for all }z,x\\&G_2(z,x)=\begin{cases} x\cup\{\langle\operatorname{dom}(x),G(z,x)\rangle\}&\text{if }x\text{ is a function}\\\emptyset&\text{otherwise}\end{cases}\\&G_3(z,x)=\begin{cases} \bigcup\operatorname{ran}(x)&\text{if }x\text{ is a function}\\\emptyset&\text{otherwise}\end{cases}\end{align}$$

By $S_2$, 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(z,\alpha)$ is a function with domain $\alpha$ for all $\alpha\in\operatorname{Ord}$ and $H(z,\alpha)\restriction\beta=H(z,\beta)$ for all $\beta<\alpha$.

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

  • Assume that the statement is true for $\alpha$. Then $H(z,\alpha+1)=G_2(z,H_z(\alpha))=$ $H_z(\alpha)\cup\{\langle\operatorname{dom}(H_z(\alpha)),G(z,H_z(\alpha))\rangle\}=H_z(\alpha)\cup\{\langle\alpha,G(z,H_z(\alpha))\rangle\}$. It follows that $\operatorname{dom}(H(z,\alpha+1))=\operatorname{dom}(H_z(\alpha))\cup \{\alpha\}=\alpha\cup \{\alpha\}=\alpha+1$. For $\beta=\alpha$, $H(z,\alpha+1)\restriction \beta=H(z,\alpha+1)\restriction \alpha=H_z(\alpha)=H_z(\beta)$. For $\beta<\alpha$, $H(z,\alpha+1)\restriction \beta=$ $H_z(\alpha)\restriction \beta=H(z,\beta)$. Thus $H(\alpha+1)\restriction \beta=H(z,\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(z,\alpha)=G_3(z,H_z\restriction\alpha)=\bigcup\operatorname{ran}(H_z\restriction\alpha)=\bigcup\{H(z,\beta)\mid \beta<\alpha\}$. For any $\beta_1\le\beta_2<\alpha$: $H(z,\beta_2)\restriction\beta_1=H(z,\beta_1)$and thus $H(z,\beta_1)\subseteq H(z,\beta_2)$. Then $H(z,\alpha)=\bigcup\{H(z,\beta)\mid \beta<\alpha\}$ is actually a function. It follows that $\operatorname{dom}(H(z,\alpha))=\bigcup_{\beta<\alpha}\operatorname{dom}(H(z,\beta))=\bigcup_{\beta<\alpha}\beta=\alpha$ since $\alpha$ is a limit ordinal. Moreover, $H(z,\alpha)\restriction \beta=\{(\gamma,H(z,\alpha)(\gamma))\mid \gamma<\beta\}=\{(\gamma,H(z,\gamma+1)(\gamma))\mid \gamma<\beta\}=$ $\{(\gamma,H(z,\beta)(\gamma))\mid \gamma<\beta\}=H(z,\beta)$.

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

Update: I have figured out how to define $F$. If you don't mind, please have a check on my attempt. Thank you so much!

We define $F:V\times\operatorname{Ord}\to V$ as follows $$F(z,\alpha):=H(z,\alpha+1)(\alpha)$$

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

Furthermore, $H_z(\alpha)=H(z,\alpha)=\{\langle\beta,H(z,\alpha)(\beta) \rangle\mid \beta<\alpha\}=\{\langle\beta,H(z,\beta+1)(\beta) \rangle\mid \beta<\alpha\}=\{\langle\beta,F(z,\beta) \rangle\mid \beta<\alpha\}=F_z\restriction \alpha$.

Finally, $F(z,\alpha)=G(z,H_z(\alpha))=G(z,F_z\restriction \alpha)$.

1

There are 1 best solutions below

1
On BEST ANSWER

This is how I would have done it. It looks correct to me.