Nachfolgerarithmetik ist nicht endlich axiomatisierbar

Betrachten Sie die Theorie Th ( N , 0 , S ) , mit S als Nachfolgefunktion. In seinem Buch A Course in Model Theory behauptet Poizat (S. 109), dass diese Theorie nicht endlich axiomatisierbar ist. Intuitiv liegt dies daran, dass wir ein Axiomenschema verwenden müssen, so dass für jedes N , gibt es ein Axiom, das besagt, dass es keinen Längenkreis gibt N (dh, S N ( X ) ≠ X , Wo S N ( X ) bezeichnet die Anwendung von S Zu X N mal). Das ist soweit in Ordnung, aber wie würde man beweisen, dass diese Theorie nicht endlich axiomatisierbar ist? Ich meine, es ist klar, dass keine endliche Teilmenge dieser Axiomatisierung ausreicht, aber vielleicht könnte es eine andere endliche Axiommenge geben, die funktionieren würde. Wie schließen wir das aus?

Die einzigen mir bekannten Beweise für nicht-endliche Axiomatisierbarkeit sind für PA und ZF, und sie verwenden Reflexionsschemata. Was ist hier die Alternative?

Üblicherweise werden Peanos Axiome in der Sprache der Mengenlehre wie folgt angegeben: 1. 0 ∈ N 2. ∀ X ∈ N : S ( X ) ∈ N 3. ∀ X , j ∈ N : [ S ( X ) = S ( j ) ⟹ X = j ] 4. ∀ X ∈ N : S ( X ) ≠ 0 5. ∀ P ⊂ N : [ [ 0 ∈ P ∧ ∀ X ∈ P : S ( X ) ∈ P ] ⟹ P = N ]         Warum ist das ein Problem?
@DanChristensen - Tut mir leid, wenn ich mich nicht klar ausgedrückt habe, aber vorbei Th ( N , 0 , S ) , ich meinte die Theorie erster Ordnung der natürlichen Zahlen mit der Nachfolgefunktion, nicht die Theorie zweiter Ordnung. Ähnliches gilt für die anderen erwähnten Theorien.
Wenn Sie also endliche Axiomabilität (?) Wollen, brauchen Sie PA zweiter Ordnung. OK. Danke.

Antworten (2)

Dies ist ein großartiges Beispiel für die Kraft der Kompaktheit!

Da die Logik erster Ordnung kompakt ist, reicht es aus zu zeigen, dass keine endliche Unteraxiomatisierung der in Ihrer früheren Frage angegebenen Standardaxiomatisierung die Aufgabe erfüllt (siehe zB hier ). Und das können wir ganz konkret: Vermieten M N die Nachfolgestruktur bestehend aus einer Kopie von sein N wie gewohnt und dann eine separate N -Zyklus können Sie das jeweils schnell überprüfen M N erfüllt die erste N -viele Axiome der Theorie, aber nein M N erfüllt die ganze Theorie.

Beachten Sie, dass nichts davon sehr nützlich sein kann P A oder Z F C , von denen jede endlich axiomatisierte Untertheorien ohne "einfach beschreibbare" Modelle hat. Und natürlich würde die ganze Idee zusammenbrechen, wenn wir in einer nicht kompakten Logik arbeiten würden – zu zeigen, dass beispielsweise eine gegebene Theorie zweiter Ordnung nicht endlich axiomatisierbar ist, ist normalerweise extrem schwierig, da wir die Dinge nicht vereinfachen können, indem wir uns auf konzentrieren eine einzige wohlverstandene Familie von möglichen endlichen Axiomatisierungen.

Ahh, sehr schön, das Argument der Kompaktheit hat mir gefehlt. Vielen Dank für dieses supereinfache Argument.
@tomasz Ich glaube nicht, dass ich dem zustimme. Nehmen wir zum Beispiel Logik zweiter Ordnung: Wir können die Theorie zweiter Ordnung des Rings ganzer Zahlen über einen einzigen Satz zweiter Ordnung oder über eine vollständig nicht-redundante unendliche Menge von Sätzen zweiter Ordnung axiomatisieren (ungefähr: „Alles ist endlich weit weg 0 " + "Es gibt zumindest N Elemente" für jedes spezifische N ∈ N ). Tatsächlich „Jedes Unendliche L -Theorie, die semantisch äquivalent zu einer Endlichkeit ist L -Theorie ist semantisch äquivalent zu einer ihrer eigenen endlichen Untertheorien" ist äquivalent zu " L ist kompakt."
@NoahSchweber: Du hast absolut recht. Ich war wirklich müde, hätte in diesem Zustand nichts schreiben sollen. Hier geht es mehr um Cover als um Bases, also total um Kompaktheit.

Kompaktheit wurde in einer anderen Antwort erwähnt, aber Kompaktheit ist hier ein bisschen ein Ablenkungsmanöver. Mit dem können wir alles machen ⊢ Begriff der Wahrscheinlichkeit und das Korrektheitstheorem.

Der erste Schritt ist der Beweis, dass die Axiome der Form ∀ X ( S N ( X ) ≠ X ) und die Axiome ∀ X ( 0 ≠ S ( X ) ) Und ∀ X ∀ j ( S ( X ) = S ( j ) → X = j ) sind in T H ( N , 0 , S ) . Das ist ziemlich einfach.

Der schwierige Teil besteht darin, zu zeigen, dass die obigen Axiome generiert werden T H ( N , 0 , S ) . Mit anderen Worten, wir müssen zeigen, dass jede wahre Aussage über N ist aus den obigen Axiomen beweisbar. Ich werde das hier nicht durchgehen, es sei denn, dies wird angefordert, aber dies ist der entscheidende Schritt.

Als nächstes zeigen wir, dass keine endliche Teilmenge der obigen Axiome zur Generierung ausreicht T H ( N ) . Dies beinhaltet die Betrachtung von Modellen der Form N ∪ C N + 1 , Wo C N + 1 ist ein Längenkreis N + 1 .

Nehmen wir schließlich an, dass es eine endliche Liste gibt A 1 , … , A N ∈ T H ( N ) . Dann jeweils A ich kann aus endlich vielen der obigen Axiome bewiesen werden, und daher können wir eine endliche Teilmenge nehmen Q der obigen Axiome, die alle beinhaltet A ich . Aber wie wir oben gezeigt haben, gibt es ein gewisses Element von T H ( N ) woraus nicht folgt Q und folgt daher nicht aus der A ich . So T H ( N ) ist nicht endlich axiomatisierbar.

Beachten Sie, dass diese Antwort vom Vollständigkeitssatz ausgeht, der nicht einfacher zu beweisen ist als der Kompaktheitssatz; Ich glaube nicht, dass es sich grundlegend von meinem unterscheidet.
@NoahSchweber Nein, der Vollständigkeitssatz wird überhaupt nicht verwendet. Es wird nur der Korrektheitssatz benötigt.
OK, wie beweisen Sie, dass die obigen Axiome generiert werden T H ( N , 0 , S ) ? Der einfachste Ansatz, den ich mir vorstellen kann, ist der Vollständigkeitssatz, es sei denn, mir fehlt etwas.
@NoahSchweber Führen Sie zuerst ein neues Funktionssymbol ein P so dass P ( S ( X ) ) = X Und P ( 0 ) = 0 . Die Idee ist, wenn ϕ ( w , X 1 , … , X N ) eine quantifiziererfreie Formel ist, dann können wir eine quantifiziererfreie erzeugen ϕ ' ( X 1 , … , X N ) und beweise das mit unseren Axiomen ∃ w ϕ ( w , X 1 , … , X N ) Und ϕ ' ( X 1 , … , X N ) sind logisch äquivalent. Ein bisschen Induktion erlaubt uns zu beweisen, dass jede Aussage zu einer bestimmten quantifiziererfreien Aussage über dieselben Variablen äquivalent ist. Insbesondere ist ein Satz äquivalent zu einem quantifiziererfreien Satz.
@NoahSchweber Im Wesentlichen ist der Schlüssel immer von ϕ Zu ϕ ' ist wie folgt: let N sei die Anzahl der Vorkommen von beiden P oder S In ϕ . Dann genügt es, nur diese zu betrachten w so dass entweder w ≤ N + 1 oder es gibt welche ich so dass | w − X ich | ≤ N + 1 (offensichtlich formalisiert im Sinne von 0 , P , S ). Auf einer separaten Anmerkung, wie würden Sie den Vollständigkeitssatz verwenden, um zu beweisen, dass unsere Axiome generiert werden T H ( N ) ?
Fair - Ich denke, dass es für mich eines meiner Lieblingsdinge am Kompaktheitssatz ist, diese Art von Argument zu umgehen (bezüglich "am einfachsten" in meinem vorherigen Kommentar). Betreff: Der Vollständigkeit halber können wir (z. B. über EF-Spiele) zeigen, dass die Modelle des betreffenden Axiomensystems alle elementar äquivalent sind N , und dann sagt der Vollständigkeitssatz genau, dass das bedeutet, dass unsere Axiome erzeugen T H ( N ).
Nachfolgerarithmetik ist nicht endlich axiomatisierbar
AntwortenHierDatenschutz-Bestimmungen1y, 0v