Ist diese Theorie des rekursiven Zählens mit PA gleich interpretierbar?

Fügen Sie der in diesem Link vorgestellten Theorie ein zweistelliges Funktionssymbol hinzu # eine Zählfunktion für Zahlen in Mengen bezeichnen, zur Liste der Grundelemente dieser Sprache hinzufügen und das Axiom hinzufügen:

# K ( X ) = N ↔ [ X = M ich N ( K ) ∧ N = 1 ] ∨ [ X ∈ K ∧ M ich N ( K ) < X ∧ N = S [ # K ( P K ( X ) ) ]

Definieren P K ( X ) = j ⟺ X ∈ K ∧ j ∈ K ∧ j < X ∧ ∄ z ∈ K ( j < z < X ) ]

Nachfolger definieren als: X = S ( j ) ⟺ j < X ∧ ∄ z ( j < z < X )

Definieren: X = M ich N ( K ) ⟺ X ∈ K ∧ ∀ j ∈ K ( X ≤ j )

Wäre die resultierende Theorie mit der Peano-Arithmetik "PA" gleich interpretierbar? Und verlängert damit PA konservativ.

Antworten (1)

Auf den ersten Blick lautet die Antwort ja .

Als Obergrenze für die Stärke funktioniert das Argument, das Sie in Ihrer vorherigen Frage angegeben haben, sobald wir es einbeziehen # .

Die Untergrenze ergibt sich dann wie folgt: if M ist also ein Modell von PA M ausgestattet mit seinen intern endlichen Mengen "ist" ein Modell Ihrer Theorie (wir müssen die Sprache natürlich etwas massieren). Hier ist eine innerlich endliche Menge eine Menge der Form { X : N > X ∧ M ⊨ φ ( X ) } für einige Formeln mit Parametern φ und einige N ∈ M .

Diese untere Grenze hat eine Feinheit: Um das Verständnis zu beweisen, müssen wir zeigen, dass etwas, das durch Quantifizierung über intern endliche Mengen definierbar ist, im ursprünglichen Sinne definierbar ist. Dies folgt aus dem Folgenden: für jede Formel φ ( X ; j 1 , . . . , j k ) , PA beweist Folgendes:

Für alle A 1 , . . . , A k , N , da ist ein C so dass für alle ich wir haben

P ich | C ⟺ ich < N ∧ φ ( ich ; A 1 , . . . , A k ) .

Das heißt, in jedem Modell von PA sind alle intern endlichen Mengen tatsächlich quantifiziererfrei definierbar, und wir können über Formeln begrenzter Quantifiziererkomplexität quantifizieren.

Übrigens ist die Verständnissubtilität etwas, das ich in meiner Antwort auf die vorherige Frage des OP nicht angesprochen habe . Obwohl ich denke, dass alle Behauptungen dort tatsächlich wahr sind, ist das Argument unvollständig.
Ist diese Theorie des rekursiven Zählens mit PA gleich interpretierbar?
AntwortenHierDatenschutz-Bestimmungen1y, 0v