Sind diese beiden parametrischen Versionen der transfiniten Rekursion äquivalent?

Obwohl ich es beweisen kann$S_1\implies S_2$mit nicht viel Mühe konnte ich es nicht beweisen$S_2\implies S_1$nach mehreren Versuchen. Insbesondere kann ich den Fall nicht behandeln, in dem$F(z,\alpha+1)=G_2(z,F_z(\alpha))$, wie unser gewünschtes Ergebnis ist$F(z,\alpha+1)=G_2(z,F_z\restriction \alpha+1)$. Mein Versagen rührt daher, dass$F_z(\alpha)$ist eine Ausgabe einer Funktion, wohingegen$F_z\restriction \alpha+1$ist selbst eine Funktion.

Bitte hinterlassen Sie mir einige Hinweise zum Beweis$S_2\implies S_1$! Vielen Dank für Ihre engagierte Hilfe!

---

Lassen$V$sei die Klasse aller Mengen,$\operatorname{Ord}$sei die Klasse aller Ordinalzahlen, und$G,G_1,G_2,G_3$Klassenfunktionen von sein$V$Zu$V$.

$S_1:$

Es existiert eine Klassenfunktion$F:V\times\operatorname{Ord}\to V$so dass$F(z,\alpha)=G(z,F_z\restriction \alpha)$für alle$z\in V$und für alle$\alpha\in\operatorname{Ord}$, mit$F_z\restriction \alpha:=\{\langle\beta,F(z,\beta)\rangle\mid\beta<\alpha\}$.

$S_2:$

Es existiert eine Klassenfunktion$F:V\times\operatorname{Ord}\to V$so dass, für alle$z\in V$

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

• $F(z,\alpha+1)=G_2(z,F_z(\alpha))$für alle$\alpha\in\operatorname{Ord}$, mit$F_z(\alpha):=F(z,\alpha)$

• $F(z,\alpha)=G_3(z,F_z\restriction\alpha)$für alle$\alpha\neq 0$Grenze, mit$F_z\restriction \alpha:=\{\langle\beta,F(z,\beta)\rangle\mid\beta<\alpha\}$

---

Update: Ich habe versucht, den Beweis hier zu replizieren . Alles scheint in Ordnung zu sein, bis ich das Gewünschte nicht definieren kann$F$aus$H$. Bitte werfen Sie mir ein paar Lichter!

Gegeben$G$, Wir definieren$G_1,G_2,G_3$folgendermaßen

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

Von$S_2$, gibt es eine Klassenfunktion$H:V\times\operatorname{Ord}\to V$so dass, für alle$z\in V$

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

• $H(z,\alpha+1)=G_2(z,H_z(\alpha))$für alle$\alpha\in\operatorname{Ord}$

• $H(z,\alpha)=G_3(z,H_z\restriction\alpha)$für alle$\alpha\neq 0$Grenze

Das beweisen wir erstmal$H(z,\alpha)$ist eine Funktion mit Definitionsbereich$\alpha$für alle$\alpha\in\operatorname{Ord}$Und$H(z,\alpha)\restriction\beta=H(z,\beta)$für alle$\beta<\alpha$.

• $H(z,0)=G_1(z,\emptyset)=\emptyset$. Dann ist die Aussage trivialerweise wahr für$\alpha=0$.

• Nehmen Sie an, dass die Aussage gilt für$\alpha$. Dann$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\}$. Es folgt dem$\operatorname{dom}(H(z,\alpha+1))=\operatorname{dom}(H_z(\alpha))\cup \{\alpha\}=\alpha\cup \{\alpha\}=\alpha+1$. Für$\beta=\alpha$,$H(z,\alpha+1)\restriction \beta=H(z,\alpha+1)\restriction \alpha=H_z(\alpha)=H_z(\beta)$. Für$\beta<\alpha$,$H(z,\alpha+1)\restriction \beta=$ $H_z(\alpha)\restriction \beta=H(z,\beta)$. Daher$H(\alpha+1)\restriction \beta=H(z,\beta)$für alle$\beta<\alpha+1$.

• Nehmen Sie an, dass die Aussage für alle gilt$\beta<\alpha$Wo$\alpha\neq\emptyset$ist Grenzwertordnungszahl. Dann$H(z,\alpha)=G_3(z,H_z\restriction\alpha)=\bigcup\operatorname{ran}(H_z\restriction\alpha)=\bigcup\{H(z,\beta)\mid \beta<\alpha\}$. Für alle$\beta_1\le\beta_2<\alpha$:$H(z,\beta_2)\restriction\beta_1=H(z,\beta_1)$und somit$H(z,\beta_1)\subseteq H(z,\beta_2)$. Dann$H(z,\alpha)=\bigcup\{H(z,\beta)\mid \beta<\alpha\}$ist eigentlich eine Funktion. Es folgt dem$\operatorname{dom}(H(z,\alpha))=\bigcup_{\beta<\alpha}\operatorname{dom}(H(z,\beta))=\bigcup_{\beta<\alpha}\beta=\alpha$seit$\alpha$ist eine Grenzordnungszahl. Darüber hinaus,$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)$.

Infolge,$\forall\beta<\alpha:H(z,\alpha)\restriction \beta=H(z,\beta)$und somit$\forall\beta<\alpha:H(z,\beta)\subsetneq H(z,\alpha)$.

Update: Ich habe herausgefunden, wie man definiert$F$. Wenn es Ihnen nichts ausmacht, überprüfen Sie bitte meinen Versuch. Vielen Dank!

Wir definieren$F:V\times\operatorname{Ord}\to V$folgendermaßen

$$F(z,\alpha):=H(z,\alpha+1)(\alpha)$$

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

Außerdem,$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$.

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