Sind diese beiden Aussagen zur transfiniten Rekursion äquivalent?

Question

Sind diese beiden Aussagen zur transfiniten Rekursion äquivalent?

Ordnungszahlen
Mengenlehre
Mathematik
transfinite-Rekursion

Akira

Ich habe zwei Aussagen zur transfiniten Rekursion, die unten zitiert werden. Es ist klar, dass $S_1$ ist das übliche transfinite Rekursionstheorem.

Lassen $V$ sei die Klasse aller Mengen, $\operatorname{Ord}$ sei die Klasse aller Ordinalzahlen, und $G:V\to V$ eine Klassenfunktion sein.

$S1:$

Es existiert eine Klassenfunktion $F:\operatorname{Ord}\to V$ so dass $F(\alpha)=G(F\restriction \alpha)$ für alle $\alpha\in\operatorname{Ord}$ .

$S2:$

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 $\alpha\in\operatorname{Ord}$ Und $z\in V$ Wo $F_z\restriction \alpha:=\{\langle\beta,F(z,\beta)\rangle\mid\beta<\alpha\}$ .

In meinem Lehrbuch Introduction to Set Theory von Hrbacek und Jech machen die Autoren keinen Gebrauch $S_1$ beweisen $S_2$ . Stattdessen modifizieren sie den Beweis von $S_1$ in einen anderen Beweis von $S_2$ .

Ich denke, es ist möglich zu beweisen $S_1\implies S_2$ , aber ich habe es vergeblich versucht, da ich damit nicht umgehen kann $F$ In $S_1$ nimmt nur $\alpha$ als Eingabe, während $F$ In $S_2$ nimmt beides $z,\alpha$ als Eingänge.

Meine Frage:

Ist $S_1$ bezüglich $S_2$ , dh $S_1\iff S_2$ , oder $S_1\implies S_2$ , oder $S_2\implies S_1$ ?
Wenn $S_1\iff S_2$ , oder $S_1\implies S_2$ , oder $S_2\implies S_1$ , bitte hinterlassen Sie mir ein paar Tipps, damit ich es versuchen kann.

Vielen Dank!

Asaf Karagila

In S2, wenn

F

$F$ ist von den Ordnungszahlen, wie könnten Sie eingeben

F (z, α)

$F(z,\alpha)$ ? Das sind zwei Variablen und

z

$z$ sieht nicht aus wie eine Ordnungszahl. Auch

G

$G$ selbst nimmt zu viele Variablen.

Akira

@AsafKaragila: Ich kann nicht verstehen, was du meinst $F$ ist von den Ordnungszahlen , bitte erläutern Sie mehr! Seit

z \in V

$z\in V$ ,

z

$z$ ist nicht unbedingt eine Ordinalzahl. Meines Verständnisses

G : V \to V

$G:V\to V$ ist eine Klassenfunktion und

V

$V$ ist die Klasse aller Mengen, also

G

$G$ kann jede Menge als Eingabe nehmen, einschließlich solcher Paare wie

(z, F_{z} ↾ α)

$(z,F_z\restriction \alpha)$ .

Berci

Sie schrieben

F : O r d \to V

$F:Ord\to V$ auch in S2, während die nächste Zeile sagt

F (z, α)

$F(z, \alpha)$ wie die Domäne von

F

$F$ War eher

V \times O r d

$V\times Ord$ . Es gibt ein ähnliches Problem mit

G

$G$ , wie es derzeit geschrieben wird.

Akira

Danke @Berci! Das ist mein schlechtes. Ich werde meinen Beitrag editieren. In

S_{2}

$S_2$ , es sollte sein

F : V \times Ord \to V

$F:V\times\operatorname{Ord}\to V$ . Können Sie näher darauf eingehen, was falsch ist

G

$G$ In

S_{2}

$S_2$ ?

hartkp

Daran ist nichts auszusetzen

G

$G$ In

S_{2}

$S_2$ : das Paar

⟨ z, F_{z} ↾ α ⟩

$\langle z,F_z\upharpoonright\alpha\rangle$ gehört

V

$V$ .

Akira

Danke @hartkp! Ich bin jetzt entspannt.

Antworten (2)

Sind diese beiden Aussagen zur transfiniten Rekursion äquivalent?

In S2, wenn $F$ ist von den Ordnungszahlen, wie könnten Sie eingeben $F(z,\alpha)$ ? Das sind zwei Variablen und $z$ sieht nicht aus wie eine Ordnungszahl. Auch $G$ selbst nimmt zu viele Variablen.
@AsafKaragila: Ich kann nicht verstehen, was du meinst $F$ ist von den Ordnungszahlen , bitte erläutern Sie mehr! Seit $z\in V$ , $z$ ist nicht unbedingt eine Ordinalzahl. Meines Verständnisses $G:V\to V$ ist eine Klassenfunktion und $V$ ist die Klasse aller Mengen, also $G$ kann jede Menge als Eingabe nehmen, einschließlich solcher Paare wie $(z,F_z\restriction \alpha)$ .
Sie schrieben $F:Ord\to V$ auch in S2, während die nächste Zeile sagt $F(z, \alpha)$ wie die Domäne von $F$ War eher $V\times Ord$ . Es gibt ein ähnliches Problem mit $G$ , wie es derzeit geschrieben wird.
Danke @Berci! Das ist mein schlechtes. Ich werde meinen Beitrag editieren. In $S_2$ , es sollte sein $F:V\times\operatorname{Ord}\to V$ . Können Sie näher darauf eingehen, was falsch ist $G$ In $S_2$ ?
Daran ist nichts auszusetzen $G$ In $S_2$ : das Paar $\langle z,F_z\upharpoonright\alpha\rangle$ gehört $V$ .

hartkp · Answer 1

Das ist einigermaßen klar $S_2$ impliziert $S_1$ ; codieren die $G$ du hast für $S_1$ in ein $G'$ für $S_2$ , sagen wir, indem wir haben $G'(z,x)=G(x)$ für alle $x$ Und $G'(y)=\emptyset$ Wenn $y$ ist kein geordnetes Paar. Du bekommst ein $F'$ Und $F'(\emptyset,\alpha)$ ist die gewünschte Funktion.

Das Gegenteil sieht problematischer aus; für jeden einzelnen Satz $z$ Sie können eine Funktion erstellen $F_z$ wie gewünscht, aber Sie müssen sich darüber im Klaren sein, dass der Rekursionssatz eigentlich ein Satzschema ist: für jede Formel, die eine Funktion wie beschreibt $G$ Es gibt eine andere Formel, die eine Funktion wie beschreibt $F$ . Das bedeutet, dass Sie nicht über den Auftrag sprechen können $z\mapsto F_z$ um die zu kombinieren $F_z$ s in einem großen $F$ . Den Nachweis muss man sich anschauen $S_1$ und beachten Sie, dass Sie den Parameter einschleichen können $z$ auf einheitliche Weise und wandeln damit den Beweis von um $S_1$ in einen Beweis von $S_2$ .

Vielen Dank für deine Antwort @hartkp! Ich habe Ihren Beweis ausführlicher ergänzt und unten als Antwort gepostet, damit ich Ihre Ideen wirklich verstehen kann. Könnten Sie es bitte verifizieren?

Akira · Answer 2

Auf der Grundlage der Antwort von @hartkp präsentiere ich einen detaillierteren Beweis. Alle Credits gehen an @hartkp.

$S_2\implies S_1$

Wir definieren $G':V\to V$ folgendermaßen

G^{'} (X) = {\begin{cases} G (F) & Wenn X = (z, F) für einige z, F \in v \\ \emptyset & ansonsten \end{cases}

$G'(x)=\begin{cases} G(f)&\text{if }x=(z,f)\text{ for some }z,f\in V\\\emptyset&\text{otherwise}\end{cases}$

Nach Satz $S_2$ , gibt es 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}$ . Es folgt dem $F'(z,\alpha)=G(F'_z\restriction \alpha)$ .

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

F (a) = F^{'} (0, a) für alle a \in Best.-Nr

$F(\alpha)=F'(0,\alpha)\text{ for all }\alpha\in\operatorname{Ord}$

Wir haben $F'_0\restriction\alpha=\{\langle\beta,F'(0,\beta)\rangle\mid\beta<\alpha\}=\{\langle\beta,F(\beta)\rangle\mid\beta<\alpha\}=F\restriction\alpha$

Dann $F(\alpha)=F'(0,\alpha)=G(F'_0\restriction\alpha)=G(F\restriction\alpha)$ . Damit ist der Beweis abgeschlossen.

Sind diese beiden Aussagen zur transfiniten Rekursion äquivalent?

Akira

Asaf Karagila

Akira

Berci

Akira

hartkp

Akira

Antworten (2)

hartkp

Akira

Akira

hartkp

Akira

Frage zur Verwendung einer parametrischen Version des transfiniten Rekursionssatzes in Introduction to Set Theory 3rd ed. von Hrbacek und Jech

Transfinite Rekursion anwenden

Intuition und "Beweis" der transfiniten Rekursion

Injektion aus der Menge der abzählbaren Ordnungszahlen ΩΩ\Omega in RR\mathbb{R}

Wie man transfinite Rekursion formal verwendet, um eine Sequenz für einen Beweis von Zorns Lemma zu konstruieren

Ist dieser Satz äquivalent zum transfiniten Rekursionssatz?

Wie leiten die Autoren diese schwächere Version der transfiniten Rekursion ab?

Gibt es eine Verallgemeinerung der transfiniten Rekursion, die es ermöglicht, geeignete Klassen zu definieren?

Sind diese beiden parametrischen Versionen der transfiniten Rekursion äquivalent?

Gibt es eine Mengenlehre, in der die folgende nicht fundierte Definition der Ordnungszahlen möglich ist?