Die Rolle des Axiomschemas der Ersetzung im Beweis des transfiniten Rekursionssatzes

Question

Die Rolle des Axiomschemas der Ersetzung im Beweis des transfiniten Rekursionssatzes

Mengenlehre
Mathematik
Beweis-Erklärung
transfinite-Rekursion

Akira

Transfiniter Rekursionssatz:

Lassen $G:V\to V$ eine Klassenfunktion sein. Dann gibt es eine einzigartige Funktion $F:\operatorname{Ord}\to V$ so dass
$\forall a \in Best.-Nr : F (a) = G (F ↾ a)$ $\forall \alpha\in \operatorname{Ord}:F(\alpha)=G(F\restriction\alpha)$

Ich fand, dass der Beweis dieses Theorems oft folgt:

Erstens beweist es das

Für alle $\alpha\in\operatorname{Ord}$ , gibt es eine eindeutige Funktion $f_{\alpha}$ das befriedigt

(1) $\operatorname{dom}f_{\alpha} = \alpha+1$

(2) $\forall \beta\le\alpha:f_{\alpha}(\beta) = G(f_{\alpha}\restriction\beta)$

Zweitens definiert es $F$

Für alle $\alpha\in\operatorname{Ord}$ , $F(\alpha):=f_{\alpha}(\alpha)$ .

Das beweist es $F\restriction\alpha$ ist eine Menge mit der folgenden Argumentation

Wir haben $F\restriction\alpha=\{\langle \beta,F(\beta)\rangle\mid \beta<\alpha\}$ , also nach Axiom der Schemaersetzung, $F\restriction\alpha$ Ist ein Satz.

Meine Fragen:

Meines Verständnisses nach definieren $F$ von $\forall\alpha\in\operatorname{Ord}:F(\alpha):=f_{\alpha}(\alpha)$ . Ich glaube, ich habe unsere Aufgabe erfüllt, nämlich zu definieren $F$ .

Ich kann nicht verstehen, warum der Beweis das beweist $F\restriction\alpha$ ist ein Set für alle $\alpha\in\operatorname{Ord}$ .

Meines Verständnisses $F$ ist eine Funktion und $F\restriction\alpha$ ist eine Beschränkung auf $F$ und ist somit eine Menge.

Ich kann nicht verstehen, welche Rolle das Axiom of Schema Replacement hier spielt.

Vielen Dank für Ihre Antwort!

Antworten (1)

Die Rolle des Axiomschemas der Ersetzung im Beweis des transfiniten Rekursionssatzes

Asaf Karagila · Answer 1

Wie kannst du das beweisen $F\restriction\alpha$ ist ein Satz sonst? Dies ist buchstäblich eine Möglichkeit, das Ersetzungsaxiom-Schema zu formulieren: Eine auf eine Menge beschränkte Klassenfunktion ist eine Menge.

Der Punkt ist, dass, wenn Sie das argumentieren wollen $F(\alpha)=G(F\restriction\alpha)$ , dann musst du das beweisen $F\restriction\alpha$ liegt im Bereich von $G$ , oder mit anderen Worten, eine Menge. Das könntest du wohl nachweisen $F\restriction\alpha+1=f_\alpha$ , aber auch dies erfordert, dass Sie sich auf Replacement (oder seine Formulierung über transfinite Induktion) berufen.

Eine gute Möglichkeit, dies zu sehen, besteht darin, zu versuchen, den Beweis in einer Umgebung zu rekonstruieren, von der wir wissen, dass er fehlschlagen wird. In ... Arbeiten $V_{\omega+\omega}$ und bedenke $G(x)=\omega+n$ Wenn $x\in V_{\omega+n+1}\setminus V_{\omega+n}$ , oder wenn $x\in V_{n+1}\setminus V_n$ , und ansonsten $G(x)=0$ .

Definieren Sie dies nun durch Rekursion $F$ . Dann $F(0)=G(\varnothing)=0$ , Dann $F(1)=G(F\restriction 1)=\omega+k$ für einige angemessen $k$ (natürlich abhängig von Ihrer Codierung der geordneten Paare und Funktionen). Im weiteren Verlauf merkt man das $F\restriction\omega$ ist kein Satz mehr. Wie könnte man also definieren $F(\omega)$ ?

Obwohl ich Ihr Beispiel nicht verstehen kann (da ich gerade etwas über transfinite Induktion / Rekursion gelernt habe), scheine ich Ihre erste Argumentation zu verstehen. Für die Formel $F(\alpha)=G(F\restriction\alpha)$ arbeiten, $G(F\restriction\alpha)$ muss wohldefiniert sein und somit $F\restriction\alpha$ muss in der Domäne von liegen $G$ . Darüber hinaus, $G$ ist eine Funktion, die nur set als Eingabe akzeptiert. Also müssen wir beweisen $F\restriction\alpha$ muss eine Menge sein.[...]
[...]In meinem Beweis habe ich das bereits bewiesen $f_{\alpha}$ ist ein Set für alle $\alpha\in\operatorname{Ord}$ (nach Axiom der Schemaersetzung). Ist es richtig, wenn ich diese Transformation verwende, um das zu beweisen? $F\restriction\alpha$ Ist ein Satz: $F\restriction\alpha=\{\langle \beta,F(\beta)\rangle\mid \beta<\alpha\}=\{\langle \beta,f_{\beta}(\beta)\rangle\mid \beta<\alpha\}=\{\langle \beta,f_{\alpha}(\beta)\rangle\mid \beta<\alpha\}=f_{\alpha}\restriction\alpha$ . Da wir das schon wissen $f_{\alpha}$ Ist ein Satz. Dann $f_{\alpha}\restriction\alpha$ ist eine Menge und somit $F\restriction\alpha$ ist auch ein Satz.
Wie hast du definiert $f_\alpha$ Wenn $\alpha$ ist ein Grenzwert ordinal?
Hallo @Asaf! Ich habe es so gemacht: Setze das für alle voraus $\beta<\alpha$ , gibt es eine eindeutige Funktion $f_{\beta}$ das die Bedingungen erfüllt. Lassen $f=\bigcup_{\beta<\alpha}f_{\beta}$ . Das Axiom des Ersatzschemas behauptet dies $f$ Ist ein Satz. Lassen $f_{\alpha}=f\cup\{\langle\alpha,G(f)\rangle\}$ Als nächstes beweisen wir das $f_{\alpha}$ erfüllt die Bedingungen.
Also, woher weißt du das? $\bigcup_{\beta<\alpha}f_\beta$ Ist ein Satz?
Hallo @Asaf! Lassen $P(\beta,f_{\beta})$ die Aussage sein $f_{\beta}$ erfüllt (1) und (2) . Durch induktive Hypothese für alle $\beta<\alpha$ , gibt es eine eindeutige Funktion $f_{\beta}$ die (1) und (2) erfüllt. Dann Aussage $P(\beta,f_{\beta})$ erfüllt die Anforderung des Axiom Schema of Replacement. Daher $T:=\{f_{\beta}\mid P(\beta,f_{\beta}) \text{ holds for some } \beta<\alpha\}$ Ist ein Satz. Dann $\bigcup T$ ist eine Menge und somit $\bigcup_{\beta<\alpha}f_\beta=\bigcup T$ Ist ein Satz.
Ja, siehst du? Ersatz war notwendig. Je nachdem, wie genau Sie die Dinge beweisen, können Sie möglicherweise die Verwendung aus diesem letzten Teil entfernen (dh $F\restriction\alpha$ ), aber es bietet uns eine einfache Lösung.
Hallo @Asaf! Stimmt das mit meiner obigen Argumentation (natürlich muss ich bei diesem Ansatz Axiom Schema of Replacement verwenden, um das zu zeigen $f_{\alpha}$ ist ein Set für alle $\alpha\in\operatorname{Ord}$ ), es folgt dem $F\restriction\alpha$ ist eine Menge ohne die Notwendigkeit einer zusätzlichen Begründung? Mein schlechtes Sprachverständnis in Englisch macht mich unsicher, so dass ich erneut um Ihre Bestätigung bitten muss.
Vielen Dank @Asaf. Ich weiß, dass Sie solche Fragen stellen, um sicherzustellen, dass ich Konzepte richtig verstehe.

Die Rolle des Axiomschemas der Ersetzung im Beweis des transfiniten Rekursionssatzes

Akira

Antworten (1)

Asaf Karagila

Akira

Akira

Asaf Karagila

Akira

Asaf Karagila

Akira

Asaf Karagila

Akira

Akira

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

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

Transfinite Rekursion anwenden

"Quantifizieren" über Eigenschaften und "Operationen" in ZFC und transfinite Rekursion: Klärung von Verwirrung

Intuition und "Beweis" der transfiniten Rekursion

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

Begründung induktiver Definitionen im formalen ZFC

Transfinite Rekursion und Ersetzung

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?