Begründung induktiver Definitionen im formalen ZFC

Question

Begründung induktiver Definitionen im formalen ZFC

Logik
Mengenlehre
Mathematik
transfinite-Rekursion

Benutzer377104

Allgemeine Frage: Wie kann man induktive Definitionen in formalen ZFC rechtfertigen?

Wenn wir einen Begriff pro Rekursion definieren wollen, schreiben wir normalerweise einfach zum Beispiel

F_{1} = 1; F_{2} = 1

$F_1 = 1; \, F_2=1$

F_{N + 2} = F_{N} + F_{N + 1} Wo N \geq 1

$F_{n+2} = F_n + F_{n+1}\quad\text{where }n\geq 1$

und darauf vertrauen, dass dies eine eindeutige Sequenz ergibt $(F_n)$ . Wenn man diesen Prozess formalisieren möchte, fällt mir als erstes ein, dass dies als axiomatische Definition angesehen werden kann: Wir geben nur die Eigenschaften an, die der zu definierende Begriff haben soll. Aber formal ZFC – die Theorie erster Ordnung über die Sprache $\{\in\}$ – ist statisch, das können wir nicht.

Aber wie können wir die Definition im formellen ZFC rechtfertigen? Kann man das in ZFC beweisen

Es gibt eine einzigartige Sequenz (F_{N}) so dass die obigen Eigenschaften gelten

$\text{there is a unique sequence $(F_n)$ such that the above properties hold}$ ? Oder kann man eine Formel angeben

ϕ (x, y)

$\phi(x,y)$ das ausdrückt

F_{x} = y

$F_x = y$ ?

Bei der ersten Möglichkeit (Beweis, dass diese Folge eindeutig ist) spricht man vom Begriff einer Folge. Dies ist nicht möglich, wenn man per Rekursion einen Begriff definieren möchte, bei dem die Domäne eine echte Klasse wäre, wie zum Beispiel in der Definition des von Neumann-Universums:

v_{0} = \emptyset

$V_0=\emptyset$

v_{β + 1} = P (v_{β})

$V_{\beta+1}= P(V_{\beta})$

v_{λ} = ⋃_{β < λ} v_{β}

$V_{\lambda}=\bigcup_{\beta<\lambda} V_{\beta}$

Die Ordnungszahlen stellen keine Menge dar, daher kann man nicht von der Folge sprechen $(V_{\alpha})$ direkt. Aber dann, wie kann man darüber sprechen $(V_{\alpha})$ im formellen ZFC? Kann man eine Formel geben $\phi$ das definiert diesen Begriff?

Arthur

Man kann nicht von einer Folge sprechen, wohl aber von „der kleinsten Ordnungszahl, für die unser Ding nicht definiert ist“ . Wenn die Existenz einer solchen Ordnungszahl unserer transfiniten rekursiven / induktiven Definition widerspricht, dann ist unser Ding für jede Ordnungszahl definiert.

Noah Schweber

@ Arthur Dein erster Satz ist nicht ganz richtig. Wir können nicht direkt über Folgen der Länge ON sprechen, aber wir können direkt über Folgen beliebiger ordinaler Länge sprechen.

Git Gud

Siehe Rekursionssatz von Dedekind .

Noah Schweber

Siehe auch math.stackexchange.com/questions/804034/… .

Daniel Wainfleet

Siehe 9.3.Theorem. Tranfinite Recursion on ON, in Kunen: Set Theory: An Introduction to Independence Proofs (erste Ausgabe, Kapitel 1, Abschnitt 9, Seiten 25-26, einschließlich der Diskussion nach dem Beweis.)

V_{α}

$V_{\alpha}$ ist rekursiv definiert.

Antworten (1)

Begründung induktiver Definitionen im formalen ZFC

Man kann nicht von einer Folge sprechen, wohl aber von „der kleinsten Ordnungszahl, für die unser Ding nicht definiert ist“ . Wenn die Existenz einer solchen Ordnungszahl unserer transfiniten rekursiven / induktiven Definition widerspricht, dann ist unser Ding für jede Ordnungszahl definiert.
@ Arthur Dein erster Satz ist nicht ganz richtig. Wir können nicht direkt über Folgen der Länge ON sprechen, aber wir können direkt über Folgen beliebiger ordinaler Länge sprechen.
Siehe 9.3.Theorem. Tranfinite Recursion on ON, in Kunen: Set Theory: An Introduction to Independence Proofs (erste Ausgabe, Kapitel 1, Abschnitt 9, Seiten 25-26, einschließlich der Diskussion nach dem Beweis.) $V_{\alpha}$ ist rekursiv definiert.

Noah Schweber · Answer 1

Ihr Instinkt ist richtig: Für klassenlange Induktionen verwenden wir Formeln. Also zum Beispiel die Aussage „Die Sequenz $V_\alpha$ ( $\alpha\in ON$ ) existiert" ist nicht ganz richtig, sondern wir können eine Formel aufschreiben $\varphi$ von zwei Variablen, so dass $\varphi(x, y)$ bedeutet, dass $y$ ist eine Ordnungszahl und $x=V_y$ . Das können wir jetzt argumentieren $V_\alpha$ existiert für jede Ordnungszahl, indem man das für jede Ordnungszahl zeigt $\alpha$ es gibt einige $x$ so dass $\varphi(x, \alpha)$ hält; und um dies zu tun , verwenden wir Induktion über die Ordnungszahlen, das heißt, die Tatsache, dass jede nicht leere Menge von Ordnungszahlen ein kleinstes Element hat. Beachten Sie, dass wir über "Folgen beliebiger Ordnungslänge" sprechen können : nämlich eine Menge $s$ ist für einige eine Folge der ordinalen Länge iff $\alpha$ und einige eingestellt $X$ , $s$ ist eine Funktion aus $\alpha$ Zu $X$ . Wir haben dann in ZFC:

Vermuten $\varphi$ ist eine Formel in zwei Variablen, so dass für jede Sequenz mit ordinaler Länge $s$ , es gibt genau einen $x$ so dass $\varphi(s, x)$ hält. Dann für jede Ordnungszahl $\alpha$ , gibt es eine eindeutige Sequenz $t$ der Länge $\alpha$ (d.h. Funktion aus $\alpha$ ) so dass für alle $\gamma<\alpha$ , $\varphi(t\upharpoonright\gamma, t(\gamma))$ hält.

Also zum Beispiel für jeden $\alpha$ Wir können die Reihenfolge definieren $(V_\beta:\beta<\alpha)$ über die obige Behauptung angewendet auf die Formel

φ (S, X) \equiv S ist eine Folge der Länge γ für einige γ, Und X = P (⋃ R A N (S)) .

$\varphi(s, x)\equiv\mbox{$s$ is a sequence of length $\gamma$ for some $\gamma$, and $x=\mathcal{P}(\bigcup ran(s))$.}$

Begründung induktiver Definitionen im formalen ZFC

Benutzer377104

Arthur

Noah Schweber

Git Gud

Noah Schweber

Daniel Wainfleet

Antworten (1)

Noah Schweber

Ist „Klassentheorie“ in NBG und ZFC „konstruktiv“? Wie kann man Sätze über „Klassen“ aufstellen, die ∃!∃!\exists! beinhalten?

Wie man in ZFC transfinite Hierarchien von richtigen Klassen definiert (mit einem für die Beweistheorie nützlichen Beispiel)

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

Einige Fragen zur Größe der richtigen Klassen in ZFC

Jedes ZFC-Modell hat ein Element, das ein ZFC-Modell ist

Konkrete Beispiele für Nicht-Standard-Modelle des ZFZFZF −−- _Infinity_ +++ /⧸\not _Infinity_

Warum haben Modelle von ZF, die keine ωω\omega-Modelle sind, nicht standardisierte Formeln, deren Länge "unendlich große natürliche Zahlen" sind?

Klassen, die nicht ersatzlos als ordnungsgemäß nachgewiesen werden können

Philosophie des Zwanges

Beweist ZZ\mathbf{Z} die Existenz eines transitiven Abschlusses jeder Menge?