Ist dieser Satz äquivalent zum transfiniten Rekursionssatz?

Question

Ist dieser Satz äquivalent zum transfiniten Rekursionssatz?

Ordnungszahlen
Mengenlehre
Mathematik
transfinite-Rekursion

Akira

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

Transfiniter Rekursionssatz:

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

Obwohl ich in der Lage bin zu beweisen, dass das Theorem der transfiniten Rekursion das folgende Theorem impliziert, habe ich versucht, aber ohne Erfolg zu beweisen, dass das Theorem das Theorem der transfiniten Rekursion impliziert.

Ich möchte fragen, ob es möglich ist zu beweisen, dass dieser Satz den Satz der transfiniten Rekursion impliziert.

Ich danke Ihnen für Ihre Hilfe!

Satz:

Lassen $G_1,G_2,G_3$ Klassenfunktionen von sein $V$ Zu $V$ . Es existiert eine Klassenfunktion $F:\operatorname{Ord}\to V$ so dass

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

(2) $F(\alpha+1)=G_2(F(\alpha))$ für alle $\alpha\in\operatorname{Ord}$

(3) $F(\alpha)=G_3(F\restriction\alpha)$ für alle Grenzen $\alpha\neq 0$

Eric Wofsey

Wissen Sie, wie man eine starke Induktion (on

N

$\mathbb{N}$ ) durch schwache Induktion? Es ist die gleiche Idee.

Akira

Hallo @EricWofsey! Ja, ich will. Ich werde deinen Vorschlag ausprobieren.

Antworten (2)

Ist dieser Satz äquivalent zum transfiniten Rekursionssatz?

Wissen Sie, wie man eine starke Induktion (on $\mathbb{N}$ ) durch schwache Induktion? Es ist die gleiche Idee.
Hallo @EricWofsey! Ja, ich will. Ich werde deinen Vorschlag ausprobieren.

Eric Wofsey · Answer 1

Der Trick ist, nicht zu konstruieren $F$ selbst, sondern um die Funktion zu konstruieren $H$ was sendet $\alpha$ Zu $F\restriction \alpha$ . Auf diese Weise haben Sie bei Folgeschritten Zugriff auf die gesamte Historie der bisherigen Rekursion und nicht nur auf den letzten Schritt.

Ausführlich gegeben $G:V\to V$ , wir definieren $G_1$ , $G_2$ , Und $G_3$ folgendermaßen:

G_{1} (X) = \emptyset

$G_1(x)=\emptyset$

G_{2} (X) = X \cup {(Dom (X), G (X))}

$G_2(x)=x\cup\{(\operatorname{dom}(x),G(x))\}$

G_{3} (X) = ⋃ lief (X)

$G_3(x)=\bigcup\operatorname{ran}(x)$ Nach dem Satz erhalten wir dann eine Funktion

H : O r d \to V

$H:Ord\to V$ so dass

H (0) = G_{1} (\emptyset)

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

H (α + 1) = G_{2} (H (α))

$H(\alpha+1)=G_2(H(\alpha))$ , Und

H (α) = G_{3} (H ↾ α)

$H(\alpha)=G_3(H\restriction\alpha)$ für

α \neq 0

$\alpha\neq 0$ Grenze. Das lässt sich dann leicht per Induktion beweisen

H (α)

$H(\alpha)$ ist eine Funktion mit Definitionsbereich

α

$\alpha$ für jede

α

$\alpha$ , mit

H (α) ↾ β = H (β)

$H(\alpha)\restriction \beta=H(\beta)$ für alle

β < α

$\beta<\alpha$ . Also definieren

F = ⋃ ran (H)

$F=\bigcup\operatorname{ran}(H)$ ,

F

$F$ ist eine Funktion an

O r d

$Ord$ mit

F ↾ α = H (α)

$F\restriction\alpha=H(\alpha)$ für jede

α

$\alpha$ . Für jede

α

$\alpha$ , haben wir dann

F (a) = H (a + 1) (a) = G_{2} (H (a)) (a) = G_{2} (F ↾ a) (a) .

$F(\alpha)=H(\alpha+1)(\alpha)=G_2(H(\alpha))(\alpha)=G_2(F\restriction\alpha)(\alpha).$ Seit

dom (F ↾ α) = α

$\operatorname{dom}(F\restriction\alpha)=\alpha$ , unsere Definition von

G_{2}

$G_2$ sagt uns das

F (a) = G_{2} (F ↾ a) (a) = G (F ↾ a),

$F(\alpha)=G_2(F\restriction\alpha)(\alpha)=G(F\restriction\alpha),$ wie gewünscht.

Ich fühle mich verwirrt. Sie haben gezeigt, wie man den zweiten Satz von Q aus seinem ersten herleitet. Aber der Vorschlagende scheint zu wollen, dass der erste aus dem zweiten abgeleitet wird, obwohl es offensichtlich ist, dass, wenn der zweite gilt, dies für eine gegebene Voraussetzung gilt $G$ , können wir einfach lassen $G_1=G_2=G_3=G$ . Ich denke also, dass der Antragsteller das Q rückwärts angegeben hat.
@DanielWainfleet: Ich leite den ersten Satz vom zweiten ab. Ich beginne mit einer Funktion $G$ wie im ersten Satz, dann verwenden Sie den zweiten Satz, um eine Funktion zu erhalten $H$ und dann definieren $F$ aus $H$ was die Schlussfolgerung des ersten Theorems bestätigt. Es funktioniert nicht, einfach zu definieren $G_1=G_2=G_3=G$ seit $G_2$ nimmt als seine Eingabe nur $F(\alpha)$ , nicht $F\restriction\alpha$ .
Hallo! Ich kämpfe jetzt mit einem scheinbar ähnlichen Problem wie diesem. Ich habe versucht, Ihren Beweis zu replizieren, bin aber am Ende gescheitert. Wenn es Ihnen nichts ausmacht, werfen Sie bitte einen Blick auf math.stackexchange.com/questions/2970783/… . Ich danke Ihnen für Ihre Hilfe!

Akira · Answer 2

Ich fülle @Eric Wofseys Beweis mit Details aus und poste ihn hier. Alle Credits gehen an @Eric Wofsey.

Gegeben $G:V\to V$ , wir definieren $G_1$ , $G_2$ , Und $G_3$ folgendermaßen:

\begin{aligned} G_{1} (X) = \emptyset für alle X \\ G_{2} (X) = {\begin{cases} X \cup {(Dom (X), G (X))} & Wenn X ist eine Funktion \\ \emptyset & ansonsten \end{cases} \\ G_{3} (X) = {\begin{cases} ⋃ lief (X) & Wenn X ist eine Funktion \\ \emptyset & ansonsten \end{cases} \end{aligned}

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

Nach dem Satz gibt es eine Klassenfunktion $H:\operatorname{Ord}\to V$ so dass $H(0)=G_1(\emptyset)$ , $H(\alpha+1)=G_2(H(\alpha))$ , Und $H(\alpha)=G_3(H\restriction\alpha)$ für $\alpha\neq 0$ Grenze.

Das beweisen wir zunächst per Induktion $H(\alpha)$ ist eine Funktion mit Definitionsbereich $\alpha$ für alle $\alpha\in\operatorname{Ord}$ und mit $H(\alpha)\restriction \beta=H(\beta)$ für alle $\beta<\alpha$ .

$H(0)=G_1(0)=\emptyset$ . Dann ist die Aussage trivialerweise wahr für $\alpha=0$ .
Nehmen Sie an, dass die Aussage gilt für $\alpha$ . Dann $H(\alpha+1)=G_2(H(\alpha))=$ $H(\alpha)\cup\{(\operatorname{dom}(H(\alpha)),G(H(\alpha)))\}=H(\alpha)\cup\{(\alpha,G(H(\alpha)))\}$ . Es folgt dem $\operatorname{dom}(H(\alpha+1))=\operatorname{dom}(H(\alpha))\cup \{\alpha\}=\alpha\cup \{\alpha\}=\alpha+1$ . Für $\beta=\alpha$ , $H(\alpha+1)\restriction \beta=H(\alpha+1)\restriction \alpha=H(\alpha)=H(\beta)$ . Für $\beta<\alpha$ , $H(\alpha+1)\restriction \beta=$ $H(\alpha)\restriction \beta=H(\beta)$ . Daher $H(\alpha+1)\restriction \beta=H(\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(\alpha)=G_3(H(\alpha))=\bigcup\operatorname{ran}(H(\alpha))=\bigcup\{H(\beta)\mid \beta<\alpha\}$ . Für alle $\beta_1\le\beta_2<\alpha$ : $H(\beta_2)\restriction\beta_1=H(\beta_1)$ und somit $H(\beta_1)\subseteq H(\beta_2)$ . Dann $H(\alpha)=\bigcup\{H(\beta)\mid \beta<\alpha\}$ ist eigentlich eine Funktion. Es folgt dem $\operatorname{dom}(H(\alpha))=\bigcup_{\beta<\alpha}\operatorname{dom}(H(\beta))=\bigcup_{\beta<\alpha}\beta=\alpha$ seit $\alpha$ ist Grenzwertordnungszahl. Darüber hinaus, $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)$ .

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

Als nächstes definieren wir $F=\bigcup\operatorname{ran}(H)$ . Dann $F=\bigcup\{H(\alpha)\mid \alpha\in\operatorname{Ord}\}$ ist eine Funktion mit Definitionsbereich $\operatorname{Ord}$ und mit $F\restriction\alpha=\{F(\beta)\mid\beta<\alpha\}=\{H(\beta+1)(\beta)\mid\beta<\alpha\}=\{H(\alpha)(\beta)\mid\beta<\alpha\}=H(\alpha)$ für alle $\alpha\in\operatorname{Ord}$ .

Seit $F\restriction\alpha=H(\alpha)$ Und $\operatorname{dom}(H(\alpha))=\alpha$ , $\operatorname{dom}(F\restriction\alpha)=\alpha$ . Dann $G_2(F\restriction\alpha)=(F\restriction\alpha)\cup \{(\alpha,G(F\restriction\alpha))\}$ und somit $G_2(F\restriction\alpha)(\alpha)=G(F\restriction\alpha)$ .

Für jede $\alpha\in\operatorname{Ord}$ , wir haben $F(\alpha)=H(\alpha+1)(\alpha)=G_2(H(\alpha))(\alpha)=G_2(F\restriction\alpha)(\alpha)=G(F\restriction\alpha)$ .

Update: Ich habe einen anderen Weg gefunden, um zu definieren $F$

Wir definieren $F$ folgendermaßen $F(\alpha):=H(\alpha+1)(\alpha)$

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

Darüber hinaus, $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$ .

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

Ist dieser Satz äquivalent zum transfiniten Rekursionssatz?

Akira

Eric Wofsey

Akira

Antworten (2)

Eric Wofsey

Daniel Wainfleet

Eric Wofsey

Akira

Daniel Wainfleet

Akira

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

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

Sind diese beiden Aussagen zur transfiniten Rekursion äquivalent?

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?