ω-konsistente Theorie

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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[Bearbeiten]

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 \dot{n} bezeichnet werde. T heißt ω-konsistent, falls es keine Formel \phi(x) gibt, sodass sowohl  \exists x\phi(x) als auch für jede natürliche Zahl n \neg\phi(\dot{n}) beweisbar ist. Formal:

\text{T ist }\omega\text{-konsistent  }\leftrightarrow\text{ Es gibt keine Formel }\phi(x)\text{, so dass T}\vdash\exists x\phi(x)\text{ und für jede natürliche Zahl n: T}\vdash\neg\phi(\dot{n})

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

Beziehung zu anderen Konsistenzprinzipien[Bearbeiten]

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 T+\mathrm{RFN}_T+\mathrm{Th}_{\Pi^0_2}(\mathbb N) konsistent ist.

Hier bezeichnet \mathrm{Th}_{\Pi^0_2}(\mathbb N) die Menge aller Π02-Sätze, welche im Standardmodell der Arithmetik gültig sind. \mathrm{RFN}_T ist das uniforme Reflexionsprinzip für T, welches aus den Axiomen

\forall x\,(\mathrm{Prov}_T(\varphi(\dot x))\to\varphi(x))

für jede Formel \varphi mit einer freien Variable besteht.

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

Beispiel[Bearbeiten]

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, muss auch PA+¬Con(PA) konsistent sein. 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[Bearbeiten]

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