Tarskis Undefinierbarkeitssatz

Der Satz von Tarski über die Undefinierbarkeit der Wahrheit ist ein einschränkendes Ergebnis in der mathematischen Logik, das auf Alfred Tarski (1936) zurückgeht. Informell sagt der Satz, dass der Begriff der Wahrheit in einer Sprache nicht mit den Ausdrucksmitteln der Sprache selbst definiert werden kann. Die Beweisführung erfolgt über die sogenannten Tarski-Sätze, selbstreferenzielle Sätze der Form: ich bin ein Element von M für eine Menge M. Wählt man für M die Menge aller falschen Sätze eines Systems, führt die Konstruktion eines Tarski-Satzes zu einem Widerspruch: Ein wahrer Satz, der im System unbeweisbar ist. Daraus lässt sich folgern, dass die Menge aller wahren Sätze eines Systems nicht innerhalb dieses Systems definierbar ist. Dies ist kein Widerspruch zu den Beispielen formaler Systeme, die Tarski selbst angab, bei denen der Wahrheitsbegriff mit dem Beweisbarkeitsbegriff übereinstimmt. In diesen Fällen ist der Beweisbarkeitsbegriff nicht innerhalb des Systems definierbar.

Geschichte

Im Jahr 1931 veröffentlichte Kurt Gödel die Unvollständigkeitssätze, zu deren Beweis er zeigte, wie die Syntax der formalen Logik innerhalb der Arithmetik erster Ordnung dargestellt werden kann. Jedem Ausdruck der formalen Sprache der Arithmetik wird eine eindeutige Nummer zugewiesen. Dieses Verfahren ist verschiedentlich als Gödel-Nummerierung, Kodierung oder allgemeiner als Arithmetisierung bekannt. Insbesondere werden verschiedene Mengen oder Ausdrücke als Zahlenmengen kodiert. Es stellt sich heraus, dass für verschiedene syntaktische Eigenschaften (z. B. ist eine Formel, ist ein Satz) diese Mengen berechenbar sind.

Darüber hinaus können alle berechenbaren Mengen oder Zahlen durch eine arithmetische Formel definiert werden. Zum Beispiel gibt es Formeln in der Sprache der Arithmetik, die die Menge der Gödelnummern für Sätze der Arithmetik und für beweisbare Sätze der Arithmetik definieren.

Der Undefinierbarkeitssatz zeigt, dass diese Arithmetisierung nicht für semantische Begriffe wie Wahrheit durchgeführt werden kann. Der Satz zeigt, dass keine hinreichend mächtige, interpretierte Sprache ihre eigene Semantik darstellen kann. Eine Folgerung ist, dass eine Metasprache, die in der Lage ist, die Semantik einer Objektsprache auszudrücken, eine höhere Ausdrucksfähigkeit als diese Sprache haben muss.

Der Satz über die Undefinierbarkeit der Wahrheit wird allgemein Alfred Tarski zugeschrieben. Jedoch entdeckte Gödel diesen Satz bereits während er am Beweis seiner 1931 veröffentlichten Unvollständigkeitssätze arbeitete, lange vor der Veröffentlichung von Tarskis Arbeit 1936 (Murawski 1998). Gödel hat nie etwas zu seiner unabhängigen Entdeckung der Undefinierbarkeit veröffentlicht, beschrieb sie jedoch bereits 1931 in einem Brief an Johann von Neumann. Tarski hatte zwischen 1929 und 1931 schon fast alle Ergebnisse seines 1936 erschienenen Aufsatzes Der Wahrheitsbegriff in den formalisierten Sprachen erhalten und vor polnischem Publikum darüber gesprochen. Wie er jedoch im Aufsatz betonte, war der Satz über die Undefinierbarkeit der Wahrheit das einzige Ergebnis, das er nicht früher erhalten hatte. In der Fußnote zum Satz merkt Tarski an, dass er den Satz und seine Beweisskizze erst nach Fertigstellung der Druckfassung hinzugefügt hatte.

Aussage des Satzes

Wir werden zuerst eine vereinfachte Version des Satzes von Tarski angeben, erklären und im nächsten Abschnitt eine Version beweisen, die Tarski tatsächlich 1936 bewiesen hat. Sei $L$ die Sprache der Arithmetik erster Ordnung und $N$ die Standardstruktur für $L$. Das Paar $(L,N)$ ist dann eine Interpretation der Arithmetik in der Sprache der Prädikatenlogik erster Stufe. Jeder Satz $x$ in $L$ hat eine Gödel-Nummer $g(x)$. Weiter bezeichne $T$ die Menge der $L$-Sätze, die in $N$ wahr sind, und $T^{*}$ die Menge der Gödelnummern der Sätze in $T$.

Tarskis Undefinierbarkeitssatz: Es gibt keine $L$-Formel $W(n)$, die $T^{*}$ definiert. Das heißt, es gibt keine $L$-Formel $W(n)$, die für eine gegebene Gödelnummer $n$ entscheidet, ob der zugehörige arithmetische Satz wahr ist.

Einfach ausgedrückt kann für eine gegebene Arithmetik das Konzept der Wahrheit in einer Interpretation nicht mit den Mitteln dieser arithmetischen Sprache ausgedrückt werden. In einer geeigneten Metasprache zu $L$ kann jedoch eine solche Formel $W(n)$ definiert werden. Zum Beispiel kann ein Wahrheitsprädikat für die Arithmetik erster Ordnung in der Arithmetik zweiter Ordnung definiert werden. Diese Formel kann jedoch nur die Wahrheit für Aussagen der Arithmetik erster Ordnung definieren, und nicht die Wahrheit allgemeinerer Aussagen der Arithmetik zweiter Ordnung. Um ein Wahrheitsprädikat zu definieren, würde die Metasprache eine höhere Metametasprache erfordern, und so weiter.

Der gerade formulierte Satz ist eine Folgerung aus dem Satz von Post über die arithmetische Hierarchie, der einige Jahre nach Tarskis Beweis obigen Satzes bewiesen wurde. Eine semantische Herleitung des Satzes von Tarski aus dem Satz von Post erhält man wie folgt durch Widerspruch. Wäre eine solche Wahrheitsformel $W^{*}$ arithmetisch definierbar, so gäbe es eine natürliche Zahl $n$, so dass $W^{*}$ zur Stufe $\Sigma _{n}^{0}$ der arithmetischen Hierarchie gehört. Aber $W^{*}$ ist $\Sigma _{k}^{0}$-schwer für alle $k$, so dass die arithmetische Hierarchie zur $n$-Hierarchie kollabieren müsste, was aber dem Satz von Post widerspräche. Daher kann es keine solche Formel $W^{*}$ geben.

Verallgemeinerung

Tarski bewies einen stärkeren Satz als den oben angegebenen. Der von Tarski bewiesene Satz gilt für Sprachen, welche Negation und genügende Selbstreferenzialität aufweisen, was insbesondere von der Arithmetik erster Ordnung erfüllt ist.

Tarskis Undefinierbarkeitssatz (in verallgemeinerter Form): Sei $(L,N)$ eine interpretierte Formensprache, die eine Negation beinhaltet und eine Gödelnummerierung $g(x)$ hat, so dass es für jede $L$-Formel $A(x)$ eine Formel $B$ gibt, so dass $B\Leftrightarrow A(g(B))$ in $N$ gilt. Sei $T$ die Menge der Gödelnummern von $L$-Sätzen, die in $N$ wahr sind. Dann gibt es keine $L$-Formel $W(n)$, die $T^{*}$ definiert. Das heißt, es gibt keine $L$-Formel $A$, so dass $W(g(A))\Leftrightarrow A$ in $N$ selbst wahr ist.

Der Beweis für Tarskis Undefinierbarkeitssatz in dieser Form ist wieder durch Widerspruch. Angenommen, eine $L$-Formel $W(n)$ definiert $T^{*}$. Für einen arithmetischen Satz $A$ ist dann insbesondere $W(g(A))$ genau dann wahr wenn $A$ in $N$ wahr ist. Also ist dann auch der Tarski $T$-Satz $W(g(A))\Leftrightarrow A$ in $N$ wahr. Mit Hilfe des Fixpunkttheorems lässt sich nun ein Gegenbeispiel zu dieser Äquivalenz konstruieren, weil aus ihm die Existenz einer $L$-Formel $S$ folgt, so dass $S\Leftrightarrow \neg W(g(S))$ in $N$ gilt. Also kann es keine solche $L$-Formel $W(n)$ geben.

Umgekehrt folgt aus der Existenz einer solchen $L$-Formel $W(n)$, dass $L$ die Funktion $g(x)$ nicht ausdrücken kann. Die Sprache hätte nicht genug Selbstreferenz. In dieser Form ist der Satz auf entscheidbare Axiomensysteme wie die der Euklidischen Geometrie oder der reell abgeschlossenen Körper anwendbar.

Tarskis Undefinierbarkeitssatz liefert einige bekannte sich aus Gödels Unvollständigkeitstsätzen ergebenden Eigenschaften der Arithmetik erster Ordnung. Aber Tarskis Satz impliziert nicht die Sätze Gödels und auch bei der Umkehrung ist keine Implikation möglich.

Diskussion

Tarskis Theorem impliziert eine inhärente Beschränkung jeder formalen Sprache. Voraussetzung ist nur, dass die formale Sprache genügend Selbstreferenz erlaubt, dass das Fixpunkttheorem anwendbar ist. Daher argumentiert Smullyan (1991, 2001), dass ein großer Teil der Bedeutung der den Unvollständigkeitssätzen beigemessen wird, eigentlich Tarskis Undefinierbarkeitssatz gebührt.

Literatur

• A. Tarski: Der Wahrheitsbegriff in den formalisierten Sprachen. In: Studia Philosophica. Band 1, 1936, S. 261–405 (archive.org [PDF; abgerufen am 18. Februar 2019]). 
• Alfred Tarski: Truth and proof. In: L'age de la Science. Band 1, 1969, S. 279–301. 
• Wolfgang Stegmüller, Matthias Varga von Kibéd: Teil C, Selbstreferenz, Tarski-Sätze und die Undefinierbarkeit der arithmetischen Wahrheit (= Strukturtypen der Logik. Band III). 
• R. Smullyan, 1991. Gödel's Incompleteness Theorems. Oxford Univ. Press.
• R. Smullyan, 2001. Gödel’s Incompleteness Theorems. In L. Goble, ed., The Blackwell Guide to Philosophical Logic, Blackwell, 72–89.