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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle L} kann jedoch eine solche Formel Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle W^*} arithmetisch definierbar, so gäbe es eine natürliche Zahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} , so dass Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle W^*} zur Stufe Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Sigma _{n}^{0}} der arithmetischen Hierarchie gehört. Aber Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle W^*} ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Sigma _{k}^{0}} -schwer für alle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k} , so dass die arithmetische Hierarchie zur Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} -Hierarchie kollabieren müsste, was aber dem Satz von Post widerspräche. Daher kann es keine solche Formel Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (L, N)} eine interpretierte Formensprache, die eine Negation beinhaltet und eine Gödelnummerierung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g(x)} hat, so dass es für jede Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle L} -Formel Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A(x)} eine Formel Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle B} gibt, so dass Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle B\Leftrightarrow A(g(B))} in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle N} gilt. Sei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle T} die Menge der Gödelnummern von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle L} -Sätzen, die in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle N} wahr sind. Dann gibt es keine Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle L} -Formel Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle W(n)} , die Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle T^*} definiert. Das heißt, es gibt keine Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle L} -Formel Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A} , so dass Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle W(g(A))\Leftrightarrow A} in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle N} selbst wahr ist.

Der Beweis für Tarskis Undefinierbarkeitssatz in dieser Form ist wieder durch Widerspruch. Angenommen, eine Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle L} -Formel Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle W(n)} definiert Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle T^*} . Für einen arithmetischen Satz Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A} ist dann insbesondere Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle W(g(A))} genau dann wahr wenn Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A} in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle N} wahr ist. Also ist dann auch der Tarski Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle T} -Satz Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle W(g(A))\Leftrightarrow A} in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle N} wahr. Mit Hilfe des Fixpunkttheorems lässt sich nun ein Gegenbeispiel zu dieser Äquivalenz konstruieren, weil aus ihm die Existenz einer Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle L} -Formel Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S} folgt, so dass Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S\Leftrightarrow \neg W(g(S))} in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle N} gilt. Also kann es keine solche Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle L} -Formel Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle W(n)} geben.

Umgekehrt folgt aus der Existenz einer solchen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle L} -Formel Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle W(n)} , dass Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle L} die Funktion Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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.