ω-konsistente Theorie

aus Wikipedia, der freien Enzyklopädie

In der mathematischen Logik wird eine Theorie als ω-konsistent (oder omega-konsistent) bezeichnet, falls sie keine Existenzaussage beweisen kann, wenn sie alle konkreten Instanzen dieser Aussage widerlegen kann.

Definition

Sei T eine Theorie, die die Arithmetik interpretiert, das bedeutet, dass jeder natürlichen Zahl n ein Term der Sprache zugeordnet werden kann, der im Folgenden mit bezeichnet werde. T heißt ω-konsistent, falls es keine Formel gibt, sodass sowohl   als auch für jede natürliche Zahl n beweisbar ist. Formal:

Eine ω-konsistente Theorie ist automatisch konsistent, umgekehrt gibt es aber konsistente Theorien, die nicht ω-konsistent sind, s. Beispiel.

Beziehung zu anderen Konsistenzprinzipien

Ist eine Theorie T rekursiv axiomatisierbar, dann kann man nach einem Resultat von C. Smoryński die ω-Konsistenz wie folgt charakterisieren:[1]

T ist ω-konsistent genau dann wenn konsistent ist.

Hier bezeichnet die Menge aller Π02-Sätze, welche im Standardmodell der Arithmetik gültig sind. ist das uniforme Reflexionsprinzip für T, welches aus den Axiomen

für jede Formel mit einer freien Variable besteht.

Insbesondere ist eine endlich axiomatisierbare Theorie T in der Sprache der Arithmetik ω-konsistent genau dann wenn T+PA -korrekt ist.

Beispiel

Bezeichne PA die Theorie der Peano-Arithmetik und Con(PA) sei diejenige arithmetische Aussage, die die Behauptung PA ist konsistent formalisiert. Meist wird Con(PA) von folgender Gestalt sein:

Für jede natürliche Zahl n: n ist nicht die Gödelnummer eines Beweises von 0=1 in PA (d. h., es gibt keinen Beweis des Widerspruchs 0=1)

Auf Grund von Gödels Unvollständigkeitssatz wissen wir, dass, falls PA konsistent ist, auch PA+¬Con(PA) konsistent sein muss. PA+¬Con(PA) ist jedoch nicht ω-konsistent aus folgendem Grund: Für jede natürliche Zahl n beweist bereits PA, dass n nicht die Gödelnummer eines Beweises von 0=1 ist, also beweist PA+¬Con(PA) dies sicher auch. Jedoch beweist ¬Con(PA) auch, dass es eine natürliche Zahl m gibt, so dass m die Gödelnummer eines Beweises von 0=1 ist (die ist nämlich gerade die Aussage ¬Con(PA) selber).

Einzelnachweise

  1. Craig Smoryński: Self-reference and modal logic, in: The Journal of Symbolic Logic, 53:1 (1988), Seite 306–309. Springer, Berlin 1985.