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

Meine Frage bezieht sich auf einen Beweis von Theorem 4.12, der in dem Text Introduction to Set Theory von Hrbacek und Jech gegeben wird.

Die Autoren beweisen zunächst die Sätze 4.9 , 4.10 und 4.11 . Als Referenz zitiere ich diese Theoreme unten.


Lassen v sei die Klasse aller Mengen, Best.-Nr sei die Klasse aller Ordinalzahlen, und G : v v eine Klassenfunktion sein.

Satz 4.9: Transfiniter Rekursionssatz

Es existiert eine Klassenfunktion F : Best.-Nr v so dass F ( a ) = G ( F a ) für alle a Best.-Nr .

Satz 4.10: Transfiniter Rekursionssatz, parametrische Version

Es existiert eine Klassenfunktion F : Best.-Nr v so dass F ( z , a ) = G ( z , F z a ) für alle a Best.-Nr Und z v Wo F z a := { β , F ( z , β ) β < a } .

Satz 4.11:

Lassen G 1 , G 2 , G 3 Klassenfunktionen von sein v Zu v . Es existiert eine Klassenfunktion F : Best.-Nr v so dass

(1) F ( 0 ) = G 1 ( )

(2) F ( a + 1 ) = G 2 ( F ( a ) ) für alle a Best.-Nr

(3) F ( a ) = G 3 ( F a ) für alle Grenzen a 0


Dann sagen sie: Eine parametrische Version von Theorem 4.11 ist einfach und wir überlassen es dem Leser . Aus meinem Versuch ist die parametrische Version von Theorem 4.11 wie folgt (Ehrlich gesagt bin ich mir nicht sicher, ob mein Versuch richtig ist oder nicht)

Lassen G 1 , G 2 , G 3 Klassenfunktionen von sein v Zu v . Es existiert eine Klassenfunktion F so dass, für alle z v

F ( z , 0 ) = G 1 ( z , )

F ( z , a + 1 ) = G 2 ( z , F z ( a ) ) für alle a Best.-Nr

F ( z , a ) = G 3 ( z , F z a ) für alle Grenzen a 0

Als nächstes verwenden sie diese parametrische Version von Theorem 4.11 im Beweis von Theorem 4.12 .

Satz 4.12:

Für jeden Satz A , gibt es eine eindeutige unendliche Folge ( F N N N ) so dass

(1) F 0 = A

(2) F N + 1 = G ( F N , N ) für alle N N

Der im Text angegebene Beweis für Satz 4.12 lautet wie folgt:

Lassen G : v v eine Klassenfunktion sein. Wir wollen finden, für jeden Satz A , eine Sequenz ( F N N N ) so dass F 0 = A Und F N + 1 = G ( F N , N ) für alle N N . Nach der parametrischen Version des Transfiniten Rekursionssatzes 4.11 gibt es eine Klassenfunktion F so dass F ( 0 ) = A Und F ( N + 1 ) = G ( F ( N ) , N ) für alle N N . Nun wenden wir das Ersetzungsaxiom an: Es existiert eine Folge ( F N N N ) das ist gleich F ω und der Satz folgt.


Ich verstehe nicht, wie die parametrische Version von Theorem 4.11 verwendet wird, um die Klassenfunktion abzuleiten F im Beweis von Satz 4.12 . Kann mir bitte jemand beim Ausfüllen der Lücken helfen?

Antworten (2)

Wir brauchen die parametrische Version von Theorem 4.11 eigentlich nicht. Tatsächlich impliziert Satz 4.11 Satz 4.12. So steht es in Ihrem Lehrbuch.

Lassen G 1 , G 2 Und G 3 ist eine Klassenfunktion, so dass G 1 ( 0 ) = ( { ( 0 , A ) } , 0 ) ,

G 2 ( X ) = { ( G ( F , N ) , N + 1 ) Wenn  X = ( F , N )  für einige  N  Und  F , ansonsten,
Und G 3 ( X ) = . Sie können sehen, dass F ( N ) = ( F N , N ) . Das heißt, die Sequenz der ersten Komponente von F ( N ) ist unsere gewünschte Sequenz.

Vielen Dank für Ihre Antwort! Vielleicht bin ich falsch. Bitte überprüfen Sie meine Argumentation: Aus Satz 4.11 haben wir F ( N + 1 ) = G 2 ( F ( N ) ) . Aber wir sind uns dessen nicht sicher F ( N ) = ( F , N ) für einige F (Es ist klar, dass ( F , N ) ist ein Paar, aber F ( N ) ist nicht unbedingt ein Paar). Infolgedessen sind wir uns nicht sicher, ob F ( N ) = ( F , N ) für einige F oder andernfalls. Daher können wir die Definition von nicht anwenden G 2 Zu F ( N ) .
@LeAnhDung Du kannst es beweisen F ( N ) hat immer die form ( F , N ) durch Induktion für N .
Oh, ich habe es verstanden. Ich habe Ihre Antwort in einen detaillierten Beweis umformuliert und unten als Antwort veröffentlicht, damit ich Ihre Ideen wirklich verstehen kann. Könnten Sie es bitte verifizieren? Vielleicht irre ich mich, aber ich denke G 1 ( 0 ) = ( A , 0 ) statt G 1 ( 0 ) = ( { ( 0 , A ) } , 0 ) um F 0 = A . Wenn nicht, F 0 = { ( 0 , A ) } , was nicht so ist, wie wir es uns gewünscht haben.
@LeAnhDung Ich denke, dein Beweis und deine Beobachtung zu meinem Fehler sind richtig.
Vielen Dank für Ihre Antwort! Nur zu meiner Neugier: Ist es möglich, die parametrische Version von Theorem 4.11 anstelle von Theorem 4.11 zu verwenden, um Theorem 4.12 zu beweisen, wie von den Autoren meines Lehrbuchs vorgeschlagen?
@LeAnhDung Sie können die parametrische Version von Theorem 4.11 leicht aus Theorem 4.11 beweisen; indem Sie einfach einige Änderungen vornehmen G ich S.
Hallo! Ich wollte Theorem 4.12 durch die parametrische Version von Theorem 4.11 beweisen, nicht die parametrische Version von Theorem 4.11 durch Theorem 4.11 beweisen. Ich bin immer noch besessen von den Beweisen der Autoren.
Ah ... Ich habe Ihre Frage falsch verstanden. Die parametrische Version von Theorem 4.11 impliziert Theorem 4.11, also ist mein Beweis tatsächlich ein Beweis, den Sie wollen (aber ich glaube nicht, dass Sie ihn als gültig ansehen). Ich habe keine Ahnung, wie man den Parameter verwendet z zum leichteren Beweis.
Deshalb habe ich eine weitere Frage gestellt :) Da Sie meinten, dass die parametrische Version von Theorem 4.11 Theorem 4.11 impliziert , könnten Sie sich bitte diese Frage ansehen ?

Auf der Grundlage von Hanul Jeons Antwort. Eine ausführliche Lösung stelle ich hier vor. Alle Credits werden Hanul Jeon gegeben.


Wir definieren G 1 , G 2 folgendermaßen

G 1 ( X ) = { ( A , 0 ) Wenn  X = 0 ansonsten

G 2 ( X ) = { ( G ( F , N ) , N + 1 ) Wenn  X = ( F , N )  für einige  F v  Und  N N ansonsten

Nach Satz 4.11 existiert eine Funktion F so dass F ( 0 ) = G 1 ( 0 ) Und F ( a + 1 ) = G 2 ( F ( a ) ) für alle a Best.-Nr . Es folgt dem F ( 0 ) = ( A , 0 ) Und F ( N + 1 ) = G 2 ( F ( N ) ) für alle N N .

Das beweisen wir per Induktion F ( N ) ist von der Form ( F N , N ) für alle N N . Das ist trivial F ( 0 ) = ( A , 0 ) ist von der Form ( F 0 , 0 ) . Annehmen, dass F ( N ) ist von der Form ( F N , N ) . Dann F ( N + 1 ) = G 2 ( F ( N ) ) = G 2 ( F N , N ) = ( G ( F N , N ) , N + 1 ) = ( F N + 1 , N + 1 ) Wo F N + 1 = G ( F N , N ) .

Dann extrahieren wir die Sequenz ( F N N N ) aus ( F ( N ) N N ) . Es ist klar, dass F 0 = 0 und das F N + 1 = G ( F N , N ) für alle N N .