Gödels Unvollständigkeitssätze - Gödel's incompleteness theorems

"Bew" leitet hier weiter. Für andere Verwendungen siehe Bew (Begriffsklärung) .

Gödels Unvollständigkeitssätze sind zwei Sätze der mathematischen Logik , die sich mit den Grenzen der Beweisbarkeit in formalen axiomatischen Theorien befassen. Diese 1931 von Kurt Gödel veröffentlichten Ergebnisse sind sowohl für die mathematische Logik als auch für die Philosophie der Mathematik von Bedeutung . Die Theoreme werden weithin, aber nicht allgemein, so interpretiert, dass sie zeigen, dass Hilberts Programm zum Auffinden eines vollständigen und konsistenten Satzes von Axiomen für die gesamte Mathematik unmöglich ist.

Der erste Unvollständigkeitssatz besagt, dass kein konsistentes System von Axiomen, dessen Sätze durch ein effektives Verfahren (dh einen Algorithmus ) aufgelistet werden können , in der Lage ist, alle Wahrheiten über die Arithmetik natürlicher Zahlen zu beweisen . Für ein solches konsistentes formales System wird es immer Aussagen über natürliche Zahlen geben, die zwar wahr, aber innerhalb des Systems nicht beweisbar sind. Der zweite Unvollständigkeitssatz, eine Erweiterung des ersten, zeigt, dass das System seine eigene Konsistenz nicht beweisen kann.

Unter Verwendung eines diagonalen Arguments waren Gödels Unvollständigkeitssätze der erste von mehreren eng verwandten Sätzen über die Beschränkungen formaler Systeme. Sie wurden von gefolgt Tarskis Undefinierbarkeit Satz auf der formalen Undefinierbarkeit der Wahrheit, Kirche ist der Beweis , dass Hilberts Entscheidungsproblem ist unlösbares und Turing 's Theorem , dass es keinen Algorithmus , um das zu lösen Halteproblem .

Formale Systeme: Vollständigkeit, Konsistenz und effektive Axiomatisierung

Die Unvollständigkeitssätze gelten für formale Systeme , die ausreichend komplex sind, um die grundlegende Arithmetik der natürlichen Zahlen auszudrücken, und die konsistent und effektiv axiomatisiert sind, wobei diese Konzepte weiter unten detailliert werden. Formale Systeme werden insbesondere im Kontext der Logik erster Ordnung auch als formale Theorien bezeichnet . Im Allgemeinen ist ein formales System ein deduktiver Apparat, der aus einem bestimmten Satz von Axiomen zusammen mit Regeln der symbolischen Manipulation (oder Inferenzregeln) besteht, die die Ableitung neuer Theoreme aus den Axiomen ermöglichen. Ein Beispiel für ein solches System ist die Peano-Arithmetik erster Ordnung , ein System, in dem alle Variablen natürliche Zahlen bezeichnen sollen. In anderen Systemen, wie der Mengenlehre , drücken nur einige Sätze des formalen Systems Aussagen über die natürlichen Zahlen aus. Bei den Unvollständigkeitssätzen geht es eher um formale Beweisbarkeit innerhalb dieser Systeme als um "Beweisbarkeit" im informellen Sinne.

Es gibt mehrere Eigenschaften, die ein formales System haben kann, darunter Vollständigkeit, Konsistenz und das Vorhandensein einer effektiven Axiomatisierung. Die Unvollständigkeitssätze zeigen, dass Systeme, die genügend Arithmetik enthalten, nicht alle drei dieser Eigenschaften besitzen können.

Effektive Axiomatisierung

Ein formales System heißt effektiv axiomatisiert (auch effektiv generiert genannt ), wenn seine Satzmenge eine rekursiv aufzählbare Menge ist ( Franzén 2005 , S. 112) .

Dies bedeutet, dass es ein Computerprogramm gibt, das im Prinzip alle Sätze des Systems aufzählen könnte, ohne irgendwelche Aussagen aufzulisten, die keine Sätze sind. Beispiele für effektiv generierte Theorien sind die Peano-Arithmetik und die Zermelo-Fraenkel-Mengentheorie (ZFC).

Die als wahre Arithmetik bekannte Theorie besteht aus allen wahren Aussagen über die Standard-Ganzzahlen in der Sprache der Peano-Arithmetik. Diese Theorie ist konsistent und vollständig und enthält eine ausreichende Menge an Arithmetik. Es besitzt jedoch keinen rekursiv aufzählbaren Satz von Axiomen und erfüllt somit nicht die Hypothesen der Unvollständigkeitssätze.

Vollständigkeit

Eine Menge von Axiomen ist ( syntaktisch oder Negation- ) vollständig, wenn für irgendeine Aussage in der Sprache der Axiome diese Aussage oder ihre Negation aus den Axiomen beweisbar ist ( Smith 2007 , S. 24) . Dies ist der Begriff, der für Gödels ersten Unvollständigkeitssatz relevant ist. Sie ist nicht mit semantischer Vollständigkeit zu verwechseln , was bedeutet, dass die Menge der Axiome alle semantischen Tautologien der gegebenen Sprache beweist. Gödel hat in seinem Vollständigkeitssatz bewiesen , dass die Logik erster Ordnung semantisch vollständig ist. Aber es ist syntaktisch nicht vollständig, da es Sätze gibt, die in der Sprache der Logik erster Ordnung ausdrückbar sind, die allein mit den Axiomen der Logik weder bewiesen noch widerlegt werden können.

In einem rein logischen System wäre es absurd, syntaktische Vollständigkeit zu erwarten. Aber in einem mathematischen System hatten Denker wie Hilbert geglaubt, dass es nur eine Frage der Zeit ist, eine solche Axiomatisierung zu finden, die es einem ermöglicht, jede einzelne mathematische Formel entweder zu beweisen oder zu widerlegen (durch den Beweis ihrer Negation).

Ein formales System kann vom Design her syntaktisch unvollständig sein, wie es Logiken im Allgemeinen sind. Oder es kann unvollständig sein, einfach weil nicht alle notwendigen Axiome entdeckt oder aufgenommen wurden. Zum Beispiel ist die euklidische Geometrie ohne das Parallelpostulat unvollständig, weil einige Aussagen in der Sprache (wie das Parallelpostulat selbst) nicht aus den verbleibenden Axiomen bewiesen werden können. In ähnlicher Weise ist die Theorie dichter linearer Ordnungen nicht vollständig, sondern wird mit einem zusätzlichen Axiom vervollständigt, das besagt, dass es keine Endpunkte in der Ordnung gibt. Die Kontinuumshypothese ist eine Aussage in der Sprache von ZFC , die innerhalb von ZFC nicht beweisbar ist, daher ist ZFC nicht vollständig. In diesem Fall gibt es keinen offensichtlichen Kandidaten für ein neues Axiom, das das Problem löst.

Die Theorie der Peano-Arithmetik erster Ordnung scheint konsistent zu sein. Angenommen, dies ist tatsächlich der Fall, beachten Sie, dass es eine unendliche, aber rekursiv aufzählbare Menge von Axiomen hat und genug Arithmetik für die Hypothesen des Unvollständigkeitssatzes kodieren kann. Somit ist die Peano-Arithmetik nach dem ersten Unvollständigkeitssatz nicht vollständig. Der Satz gibt ein explizites Beispiel für eine arithmetische Aussage, die in Peanos Arithmetik weder beweisbar noch widerlegbar ist. Außerdem trifft diese Aussage im üblichen Modell zu . Außerdem kann keine effektiv axiomatisierte, konsistente Erweiterung der Peano-Arithmetik vollständig sein.

Konsistenz

Eine Menge von Axiomen ist (einfach) konsistent, wenn es keine Aussage gibt, so dass sowohl die Aussage als auch ihre Negation aus den Axiomen beweisbar sind, andernfalls inkonsistent .

Peano-Arithmetik ist nachweislich konsistent von ZFC, aber nicht von sich aus. In ähnlicher Weise ist ZFC von sich aus nicht beweisbar konsistent, aber ZFC + "es existiert ein unzugänglicher Kardinal " beweist, dass ZFC konsistent ist, denn wenn κ der kleinste solcher Kardinal ist, dann ist V κ, das innerhalb des von Neumann-Universums sitzt, ein Modell von ZFC, und Eine Theorie ist genau dann konsistent, wenn sie ein Modell hat.

Nimmt man alle Aussagen in der Sprache der Peano-Arithmetik als Axiome, dann ist diese Theorie vollständig, hat eine rekursiv aufzählbare Menge von Axiomen und kann Addition und Multiplikation beschreiben. Es ist jedoch nicht konsistent.

Weitere Beispiele inkonsistenter Theorien ergeben sich aus den Paradoxien , die sich ergeben, wenn in der Mengenlehre das Axiomenschema des uneingeschränkten Verstehens angenommen wird.

Systeme, die Arithmetik enthalten

Die Unvollständigkeitssätze gelten nur für formale Systeme, die eine ausreichende Faktensammlung über die natürlichen Zahlen beweisen können. Eine ausreichende Sammlung ist die Menge der Theoreme von Robinson Arithmetik Q . Einige Systeme, wie die Peano-Arithmetik, können Aussagen über natürliche Zahlen direkt ausdrücken. Andere, wie die ZFC-Mengentheorie, sind in der Lage, Aussagen über natürliche Zahlen in ihre Sprache zu interpretieren. Jede dieser Optionen ist für die Unvollständigkeitssätze geeignet.

Die Theorie algebraisch abgeschlossener Körper einer gegebenen Eigenschaft ist vollständig, konsistent und hat eine unendliche, aber rekursiv aufzählbare Menge von Axiomen. Es ist jedoch nicht möglich, die ganzen Zahlen in diese Theorie zu kodieren, und die Theorie kann die Arithmetik von ganzen Zahlen nicht beschreiben. Ein ähnliches Beispiel ist die Theorie der reellen geschlossenen Körper , die im Wesentlichen äquivalent zu Tarskis Axiomen für die euklidische Geometrie ist . Die euklidische Geometrie selbst (in Tarskis Formulierung) ist also ein Beispiel für eine vollständige, konsistente, effektiv axiomatisierte Theorie.

Das System der Presburger Arithmetik besteht aus einer Menge von Axiomen für die natürlichen Zahlen mit nur der Additionsoperation (Multiplikation entfällt). Presburger Arithmetik ist vollständig, konsistent und rekursiv aufzählbar und kann die Addition, aber nicht die Multiplikation natürlicher Zahlen kodieren, was zeigt, dass man für Gödels Sätze die Theorie braucht, um nicht nur Addition, sondern auch Multiplikation zu kodieren.

Dan Willard  ( 2001 ) hat einige schwache Familien von arithmetischen Systemen untersucht, die genug Arithmetik als Relationen erlauben, um die Gödel-Nummerierung zu formalisieren, die aber nicht stark genug sind, um eine Multiplikation als Funktion zu haben, und daher den zweiten Unvollständigkeitssatz nicht beweisen können; diese Systeme sind konsistent und können ihre eigene Konsistenz beweisen (siehe selbstverifizierende Theorien ).

Widersprüchliche Ziele

Bei der Auswahl einer Menge von Axiomen besteht ein Ziel darin, möglichst viele richtige Ergebnisse beweisen zu können, ohne falsche Ergebnisse zu beweisen. Zum Beispiel könnten wir uns eine Menge wahrer Axiome vorstellen, die es uns erlauben, jede wahre arithmetische Behauptung über die natürlichen Zahlen zu beweisen ( Smith 2007 , S. 2) . Im Standardsystem der Logik erster Ordnung beweist ein inkonsistenter Satz von Axiomen jede Aussage in ihrer Sprache (dies wird manchmal als Explosionsprinzip bezeichnet ) und ist somit automatisch vollständig. Ein Satz von Axiomen, der sowohl vollständig als auch konsistent ist, beweist jedoch einen maximalen Satz nicht widersprüchlicher Sätze ( Hinman 2005 , S. 143) .

Das in den vorherigen Abschnitten dargestellte Muster mit Peano-Arithmetik, ZFC und ZFC + "es existiert ein unzugänglicher Kardinal" kann im Allgemeinen nicht durchbrochen werden. Hier kann ZFC + "es existiert ein unzugänglicher Kardinal" nicht von sich aus konsequent bewiesen werden. Es ist auch nicht vollständig, wie die in ZFC + "es existiert eine unzugängliche Kardinaltheorie" ungelöste Kontinuumshypothese veranschaulicht.

Das erste Unvollständigkeitstheorem zeigt, dass in formalen Systemen, die grundlegende Arithmetik ausdrücken können, niemals eine vollständige und konsistente endliche Liste von Axiomen erstellt werden kann: Jedes Mal, wenn eine zusätzliche, konsistente Aussage als Axiom hinzugefügt wird, gibt es andere wahre Aussagen, die es immer noch nicht können auch mit dem neuen Axiom bewiesen werden. Wenn jemals ein Axiom hinzugefügt wird, das das System vervollständigt, geschieht dies auf Kosten der Inkonsistenz des Systems. Es ist nicht einmal möglich, dass eine unendliche Liste von Axiomen vollständig, konsistent und effektiv axiomatisiert ist.

Erster Unvollständigkeitssatz

Siehe auch: Beweisskizze für Gödels ersten Unvollständigkeitssatz

Gödels erster Unvollständigkeitssatz erschien erstmals als "Theorem VI" in Gödels 1931 erschienenem Aufsatz " On Formally Undecidable Propositions of Principia Mathematica and Related Systems I". Die Hypothesen des Theorems wurden kurz darauf von J. Barkley Rosser ( 1936 ) mit Rossers Trick verbessert . Das resultierende Theorem (das Rossers Verbesserung beinhaltet) kann im Englischen wie folgt umschrieben werden, wobei "formales System" die Annahme beinhaltet, dass das System effektiv erzeugt wird.

Erster Unvollständigkeitssatz : "Jedes konsistente formale System F, in dem ein gewisses Maß an elementarer Arithmetik durchgeführt werden kann, ist unvollständig, dh es gibt Aussagen der Sprache von F, die in F weder bewiesen noch widerlegt werden können ." (Raatikainen 2015)

Die unbeweisbar Aussage G F durch den Satz wird oft bezeichnet als „der Gödel Satz“ für das System F . Der Beweis konstruiert einen bestimmten Gödel-Satz für das System F , aber es gibt unendlich viele Aussagen in der Sprache des Systems, die dieselben Eigenschaften teilen, wie die Konjunktion des Gödel-Satzes und jedes logisch gültigen Satzes.

Jedes effektiv generierte System hat seinen eigenen Gödel-Satz. Es ist möglich, ein größeres System F' zu definieren  , das die Gesamtheit von F plus G F als zusätzliches Axiom enthält. Dies führt nicht zu einem vollständigen System, da der Satz von Gödel auch für F' gilt und somit auch F' nicht vollständig sein kann. In diesem Fall ist G F tatsächlich ein Satz in F' , weil es ein Axiom ist. Da G F nur sagt, dass es in F nicht beweisbar ist, wird durch seine Beweisbarkeit in F' kein Widerspruch präsentiert . Da jedoch der Unvollständigkeitssatz für F' gilt , wird es eine neue Gödel-Aussage G F′ für F' geben , die zeigt, dass auch F' unvollständig ist. G F ' wird von dem abweichen , G F in diesem G F' wird beziehen F‘ , anstatt  F .

Syntaktische Form des Gödel-Satzes

Der Gödel-Satz soll sich indirekt auf sich selbst beziehen. Der Satz besagt, dass, wenn eine bestimmte Sequenz von Schritten verwendet wird, um einen anderen Satz zu konstruieren, dieser konstruierte Satz in F nicht beweisbar ist . Die Schrittfolge ist jedoch so, dass sich der konstruierte Satz als G F selbst herausstellt . Damit legt der Gödel-Satz G F indirekt seine eigene Unbeweisbarkeit innerhalb von F fest ( Smith 2007 , S. 135) .

Um den ersten Unvollständigkeitssatz zu beweisen, demonstrierte Gödel, dass der Begriff der Beweisbarkeit innerhalb eines Systems rein durch arithmetische Funktionen ausgedrückt werden kann, die auf Gödel-Satzzahlen des Systems operieren . Daher kann das System, das bestimmte Tatsachen über Zahlen beweisen kann, indirekt auch Tatsachen über seine eigenen Aussagen beweisen, sofern es effektiv erzeugt wird. Fragen nach der Beweisbarkeit von Aussagen innerhalb des Systems werden als Fragen nach den arithmetischen Eigenschaften von Zahlen selbst dargestellt, die bei Vollständigkeit vom System entscheidbar wären.

Obwohl sich der Gödel-Satz also indirekt auf Sätze des Systems F bezieht, bezieht sich der Gödel-Satz , wenn er als arithmetische Aussage gelesen wird, direkt nur auf natürliche Zahlen. Sie behauptet, dass keine natürliche Zahl eine bestimmte Eigenschaft hat, wenn diese Eigenschaft durch eine primitive rekursive Beziehung gegeben ist ( Smith 2007 , S. 141) . Als solcher kann der Gödel-Satz in der Sprache der Arithmetik mit einer einfachen syntaktischen Form geschrieben werden. Insbesondere kann es als Formel in der Sprache der Arithmetik ausgedrückt werden, die aus einer Reihe von führenden universellen Quantoren gefolgt von einem quantorenfreien Körper besteht (diese Formeln befinden sich auf der Ebene der arithmetischen Hierarchie ). Über das MRDP-Theorem kann der Gödel-Satz als Aussage umgeschrieben werden , dass ein bestimmtes Polynom in vielen Variablen mit ganzzahligen Koeffizienten niemals den Wert Null annimmt, wenn seine Variablen durch ganze Zahlen ersetzt werden ( Franzén 2005 , S. 71) .

Wahrheit des Gödel-Satzes

Der erste Unvollständigkeitssatz zeigt, dass der Gödel-Satz G F einer geeigneten formalen Theorie F in F unbeweisbar ist . Da diese Unbeweisbarkeit, als Aussage über die Arithmetik interpretiert, genau das ist, was der Satz (indirekt) behauptet, ist der Gödel-Satz tatsächlich wahr ( Smoryński 1977 , S. 825 ; siehe auch Franzén 2005 , S. 28–33 ) . Aus diesem Grund wird der Satz G F oft als "wahr, aber nicht beweisbar" bezeichnet. ( Raatikainen 2015 ) . Da der Gödel-Satz seine beabsichtigte Interpretation jedoch nicht selbst formal spezifizieren kann, kann die Wahrheit des Satzes G F nur über eine systemfremde Metaanalyse ermittelt werden. Im Allgemeinen kann diese Metaanalyse innerhalb des schwachen formalen Systems, das als primitive rekursive Arithmetik bekannt ist, durchgeführt werden , was die Implikation Con( F )→ G F beweist , wobei Con( F ) ein kanonischer Satz ist, der die Konsistenz von F behauptet ( Smoryński 1977 , S. 840 , Kikuchi & Tanaka 1994 , S. 403 ).

Obwohl der Gödel-Satz einer konsistenten Theorie als Aussage über die beabsichtigte Interpretation der Arithmetik wahr ist , wird der Gödel-Satz in einigen nicht standardisierten Modellen der Arithmetik als Folge des Gödels Vollständigkeitssatzes falsch sein ( Franzén 2005 , S. 135) . Dieser Satz zeigt, dass, wenn ein Satz von einer Theorie unabhängig ist, die Theorie Modelle hat, in denen der Satz wahr ist, und Modelle, in denen der Satz falsch ist. Wie bereits beschrieben, ist der Gödel-Satz eines Systems F eine arithmetische Aussage, die behauptet, dass keine Zahl mit einer bestimmten Eigenschaft existiert. Der Unvollständigkeitssatz zeigt, dass diese Behauptung unabhängig vom System F ist , und die Wahrheit des Gödel-Satzes folgt aus der Tatsache, dass keine natürliche Standardzahl die fragliche Eigenschaft besitzt. Jedes Modell, in dem der Gödel-Satz falsch ist, muss ein Element enthalten, das die Eigenschaft innerhalb dieses Modells erfüllt. Ein solches Modell muss „nicht standardisiert“ sein – es muss Elemente enthalten, die keiner natürlichen Standardzahl entsprechen ( Raatikainen 2015 , Franzén 2005 , S. 135 ).

Beziehung zum Lügnerparadox

Gödel zitiert ausdrücklich Richards Paradox und das Lügnerparadox als semantische Analoga zu seinem syntaktischen Unvollständigkeitsergebnis im einleitenden Abschnitt von „ On Formally Undecidable Propositions in Principia Mathematica and Related Systems I “. Das Lügnerparadox ist der Satz "Dieser Satz ist falsch". Eine Analyse des Lügnersatzes zeigt, dass er weder wahr sein kann (denn dann, wie er behauptet, falsch ist), noch falsch sein kann (denn dann ist er wahr). Ein Gödel-Satz G für ein System F macht eine ähnliche Behauptung wie der Lügnersatz, aber mit der Wahrheit durch Beweisbarkeit ersetzt: G sagt " G ist im System F nicht beweisbar ". Die Analyse der Wahrheit und Beweisbarkeit von G ist eine formalisierte Version der Analyse der Wahrheit des Lügnersatzes.

Es ist nicht möglich, in einem Gödelsatz „nicht beweisbar“ durch „falsch“ zu ersetzen, da das Prädikat „Q ist die Gödelzahl einer falschen Formel“ nicht als arithmetische Formel darstellbar ist. Dieses Ergebnis, bekannt als Tarskis Undefinierbarkeitssatz , wurde unabhängig sowohl von Gödel, als er am Beweis des Unvollständigkeitssatzes arbeitete, als auch von Alfred Tarski, dem Namensgeber des Satzes, entdeckt .

Erweiterungen von Gödels ursprünglichem Ergebnis

Im Vergleich zu den Sätzen, die in Gödels Aufsatz von 1931 aufgestellt wurden, sind viele zeitgenössische Aussagen der Unvollständigkeitssätze in zweierlei Hinsicht allgemeiner. Diese verallgemeinerten Aussagen sind so formuliert, dass sie sich auf eine breitere Klasse von Systemen beziehen, und sie sind so formuliert, dass sie schwächere Konsistenzannahmen beinhalten.

Gödel demonstrierte die Unvollständigkeit des Systems der Principia Mathematica , eines besonderen Rechensystems, aber ein paralleler Beweis könnte für jedes effektive System einer bestimmten Ausdruckskraft gegeben werden. Gödel hat diesen Umstand in der Einleitung zu seiner Arbeit kommentiert, den Beweis aber für die Konkretheit auf ein System beschränkt. In modernen Aussagen des Theorems ist es üblich, die Effektivitäts- und Aussagekraftbedingungen als Hypothesen für den Unvollständigkeitssatz anzugeben, so dass dieser nicht auf ein bestimmtes formales System beschränkt ist. Die Terminologie, die verwendet wurde, um diese Bedingungen zu beschreiben, war 1931 noch nicht entwickelt, als Gödel seine Ergebnisse veröffentlichte.

Gödels ursprüngliche Aussage und der Beweis des Unvollständigkeitssatzes erfordern die Annahme, dass das System nicht nur konsistent, sondern ω-konsistent ist . Ein System ist ω-konsistent, wenn es nicht ω-inkonsistent ist, und ist ω-inkonsistent, wenn es ein Prädikat P gibt, so dass für jede spezifische natürliche Zahl m das System ~ P ( m ) beweist , und doch beweist das System auch, dass es existiert eine natürliche Zahl n , so dass P ( n ). Das heißt, das System sagt, dass eine Zahl mit der Eigenschaft P existiert, bestreitet jedoch, dass sie einen bestimmten Wert hat. Die ω-Konsistenz eines Systems impliziert seine Konsistenz, aber Konsistenz impliziert nicht ω-Konsistenz. J. Barkley Rosser  ( 1936 ) verstärkte das Unvollständigkeitstheorem, indem er eine Variation des Beweises ( Rosser-Trick ) fand, die nur erfordert, dass das System konsistent und nicht ω-konsistent ist. Dies ist vor allem von technischem Interesse, da alle echten formalen Theorien der Arithmetik (Theorien, deren Axiome alle wahre Aussagen über natürliche Zahlen sind) ω-konsistent sind und somit der ursprünglich formulierte Satz von Gödel für sie gilt. Die stärkere Version des Unvollständigkeitssatzes, die nur Konsistenz und nicht ω-Konsistenz annimmt, ist heute allgemein als Gödels Unvollständigkeitssatz und als Gödel-Rosser-Satz bekannt.

Zweiter Unvollständigkeitssatz

Für jedes formale System F, das grundlegende Arithmetik enthält, ist es möglich, kanonisch eine Formel Cons( F ) zu definieren, die die Konsistenz von F ausdrückt . Diese Formel drückt die Eigenschaft aus, dass "keine natürliche Zahl existiert, die eine formale Ableitung innerhalb des Systems F codiert, deren Schluss ein syntaktischer Widerspruch ist". Der syntaktische Widerspruch wird oft als "0=1" angenommen, in welchem ​​Fall Cons( F ) sagt: "Es gibt keine natürliche Zahl, die eine Ableitung von '0=1' aus den Axiomen von F codiert ."

Der zweite Unvollständigkeitssatz von Gödel zeigt, dass diese kanonische Konsistenzaussage Cons( F ) unter allgemeinen Annahmen in F nicht beweisbar ist . Das Theorem erschien erstmals als "Theorem XI" in Gödels 1931 erschienenem Aufsatz " On Formally Undecidable Propositions in Principia Mathematica and Related Systems I ". In der folgenden Aussage beinhaltet der Begriff "formalisiertes System" auch die Annahme, dass F effektiv axiomatisiert ist.

Zweiter Unvollständigkeitssatz : "Angenommen, F ist ein konsistentes formalisiertes System, das elementare Arithmetik enthält. Dann ." ( Raatikainen 2015 )

Dieser Satz ist stärker als der erste Unvollständigkeitssatz, da die im ersten Unvollständigkeitssatz konstruierte Aussage die Konsistenz des Systems nicht direkt ausdrückt. Der Beweis des zweiten Unvollständigkeitssatzes wird erhalten, indem der Beweis des ersten Unvollständigkeitssatzes innerhalb des Systems F selbst formalisiert wird .

Konsistenz ausdrücken

Der zweite Unvollständigkeitssatz enthält eine technische Feinheit bezüglich der Methode, die Konsistenz von F als Formel in der Sprache von F auszudrücken . Es gibt viele Möglichkeiten, die Konsistenz eines Systems auszudrücken, und nicht alle führen zum gleichen Ergebnis. Die Formel Cons( F ) aus dem zweiten Unvollständigkeitssatz ist ein besonderer Ausdruck der Konsistenz.

Andere Formalisierungen der Behauptung, dass F konsistent ist, können in F inäquivalent sein , und einige können sogar beweisbar sein. Zum Beispiel kann Peano-Arithmetik erster Ordnung (PA) beweisen, dass "die größte konsistente Teilmenge von PA" konsistent ist. Aber da PA konsistent ist, ist die größte konsistente Teilmenge von PA nur PA, also in diesem Sinne "beweist PA, dass es konsistent ist". Was PA nicht beweist, ist, dass die größte konsistente Teilmenge von PA tatsächlich die gesamte PA ist. (Der Begriff "größte konsistente Teilmenge von PA" soll hier das größte konsistente Anfangssegment der Axiome von PA unter einer bestimmten effektiven Aufzählung sein.)

Die Hilbert-Bernays-Bedingungen

Der Standardbeweis des zweiten Unvollständigkeitssatzes geht davon aus, dass das Beweisbarkeitsprädikat Prov A ( P ) die Hilbert-Bernays-Beweisbedingungen erfüllt . Wenn #( P ) die Gödel-Zahl einer Formel P darstellt , sagen die Beweisbedingungen:

  1. Wenn F P beweist , dann beweist F Beweis A (#( P )).
  2. F beweist 1.; das heißt, F beweist Beweis A (#( P )) → Beweis A (#(Prov A (#(P)))).
  3. F beweist Beweis A (#( P → Q )) ∧ Beweis A (#( P )) → Beweis A (#( Q )) (analog von modus ponens ).

Es gibt Systeme wie die Robinson-Arithmetik, die stark genug sind, um die Annahmen des ersten Unvollständigkeitssatzes zu erfüllen, die aber die Hilbert-Bernays-Bedingungen nicht beweisen. Die Peano-Arithmetik ist jedoch stark genug, um diese Bedingungen zu bestätigen, wie alle Theorien stärker als die Peano-Arithmetik.

Implikationen für Konsistenznachweise

Der zweite Unvollständigkeitssatz von Gödel impliziert auch, dass ein System F 1 , das die oben skizzierten technischen Bedingungen erfüllt, die Konsistenz eines Systems F 2 nicht beweisen kann, das die Konsistenz von F 1 beweist . Dies liegt daran , ein solches System F 1 kann beweisen , dass , wenn F 2 die Konsistenz beweist F 1 , dann F 1 in der Tat im Einklang steht. Denn die Behauptung, F 1 sei konsistent, hat die Form "für alle Zahlen n hat n die entscheidbare Eigenschaft, kein Code für einen Widerspruchsbeweis in F 1 zu sein ". Wäre F 1 tatsächlich inkonsistent, dann würde F 2 für einige n beweisen, dass n der Code eines Widerspruchs in F 1 ist . Aber wenn F 2 auch bewies, dass F 1 konsistent ist (d. h. dass es kein solches n gibt ), dann wäre es selbst inkonsistent. Diese Argumentation kann in F 1 formalisiert werden, um zu zeigen, dass F 1 konsistent ist , wenn F 2 konsistent ist. Da F 1 nach dem zweiten Unvollständigkeitssatz seine Konsistenz nicht beweist, kann es auch die Konsistenz von F 2 nicht beweisen .

Diese Folgerung des zweiten Unvollständigkeitssatzes zeigt, dass es keine Hoffnung gibt, beispielsweise die Konsistenz der Peano-Arithmetik mit irgendwelchen finitistischen Mitteln zu beweisen, die in einem System formalisiert werden können, dessen Konsistenz in der Peano-Arithmetik (PA) beweisbar ist. Zum Beispiel ist das System der primitiven rekursiven Arithmetik (PRA), das weithin als genaue Formalisierung der finitistischen Mathematik akzeptiert wird, in PA nachweislich konsistent. Somit kann PRA die Konsistenz von PA nicht beweisen. Diese Tatsache wird allgemein als impliziert, dass Hilberts Programm , das darauf abzielte, die Verwendung "idealer" (infinitistischer) mathematischer Prinzipien in den Beweisen "realer" (finitistischer) mathematischer Aussagen zu rechtfertigen, indem es einen finitistischen Beweis dafür lieferte, dass die idealen Prinzipien konsistent sind, kann nicht durchgeführt werden ( Franzén 2005 , S. 106) .

Das Korollar weist auch auf die erkenntnistheoretische Relevanz des zweiten Unvollständigkeitssatzes hin. Es würde eigentlich keine interessanten Informationen liefern, wenn ein System F seine Konsistenz beweisen würde. Dies liegt daran, dass inkonsistente Theorien alles beweisen, einschließlich ihrer Konsistenz. Ein Konsistenzbeweis von F in F würde uns also keinen Hinweis darauf geben, ob F wirklich konsistent ist; Zweifel an der Konsistenz von F würden durch einen solchen Konsistenzbeweis nicht ausgeräumt. Das Interesse an Konsistenzbeweisen liegt in der Möglichkeit, die Konsistenz eines Systems F in einem System F' zu beweisen, das in gewisser Weise weniger zweifelhaft ist als F selbst, beispielsweise schwächer als F . Für viele natürlich vorkommende Theorien F und F' , wie F = Zermelo-Fraenkel-Mengentheorie und F' = primitive rekursive Arithmetik, ist die Konsistenz von F' in F beweisbar , und daher kann F' die Konsistenz von F durch das Obige nicht beweisen Korollar des zweiten Unvollständigkeitssatzes.

Der zweite Unvollständigkeitssatzes schließt nicht ganz die Möglichkeit , aus der Konsistenz etwas Theorie zu beweisen T , nur so in einer Theorie zu tun , dass T selbst konsistent erweisen kann. Zum Beispiel Gerhard Gentzen erwies sich die Konsistenz der Peano Arithmetik in einem anderen System , das ein Axiom behauptet beinhaltet , dass die Ordnungs ε genannt 0 ist gut begründet ; siehe Konsistenzbeweis von Gentzen . Der Satz von Gentzen beflügelte die Entwicklung der Ordinalanalyse in der Beweistheorie.

Beispiele für unentscheidbare Aussagen

Siehe auch: Liste der Anweisungen unabhängig von ZFC

In Mathematik und Informatik gibt es zwei unterschiedliche Bedeutungen des Wortes "unentscheidbar". Die erste davon ist der beweistheoretische Sinn, der in Bezug auf Gödels Sätze verwendet wird, der einer Aussage, die in einem bestimmten deduktiven System weder beweisbar noch widerlegbar ist . Der zweite Sinn, der hier nicht diskutiert wird, wird in Bezug auf die Berechenbarkeitstheorie verwendet und bezieht sich nicht auf Aussagen, sondern auf Entscheidungsprobleme , die abzählbar unendlich viele Fragen sind, die jeweils eine Ja- oder Nein-Antwort erfordern. Ein solches Problem heißt unentscheidbar, wenn es keine berechenbare Funktion gibt , die jede Frage der Problemmenge richtig beantwortet (siehe unentscheidbares Problem ).

Wegen der zwei Bedeutungen des Wortes unentscheidbar wird manchmal der Begriff unabhängig anstelle von unentscheidbar im Sinne von "weder beweisbar noch widerlegbar" verwendet.

Die Unentscheidbarkeit einer Aussage in einem bestimmten deduktiven System beantwortet an sich nicht die Frage, ob der Wahrheitswert der Aussage wohldefiniert ist oder auf andere Weise bestimmt werden kann. Unentscheidbarkeit impliziert nur, dass das jeweilige deduktive System, das betrachtet wird, weder die Wahrheit noch die Falschheit der Aussage beweist. Ob es sogenannte „absolut unentscheidbare“ Aussagen gibt, deren Wahrheitswert nie ermittelt werden kann oder deren Wahrheitswert schlecht spezifiziert ist, ist in der Philosophie der Mathematik umstritten .

Die gemeinsame Arbeit von Gödel und Paul Cohen hat zwei konkrete Beispiele für unentscheidbare Aussagen (im ersten Sinne des Wortes) genannt: Die Kontinuumshypothese kann in ZFC (der Standardaxiomatisierung der Mengenlehre ) weder bewiesen noch widerlegt werden , und das Axiom von Wahl kann in ZF (das sind alle ZFC-Axiome außer dem Axiom der Wahl) weder bewiesen noch widerlegt werden . Diese Ergebnisse erfordern nicht das Unvollständigkeitstheorem. Gödel bewies 1940, dass keine dieser Aussagen in der Mengenlehre von ZF oder ZFC widerlegt werden kann. In den 1960er Jahren bewies Cohen, dass beides nicht von ZF beweisbar ist und die Kontinuumshypothese nicht von ZFC bewiesen werden kann.

1973 zeigte Saharon Shelah , dass das Whitehead-Problem in der Gruppentheorie im ersten Sinne des Begriffs in der Standardmengentheorie unentscheidbar ist.

Gregory Chaitin produzierte unentscheidbare Aussagen in der algorithmischen Informationstheorie und bewies in diesem Kontext ein weiteres Unvollständigkeitstheorem. Der Unvollständigkeitssatz von Chaitin besagt, dass es für jedes System, das genügend Arithmetik darstellen kann, eine obere Schranke c gibt, so dass keine spezifische Zahl in diesem System mit einer Kolmogorov-Komplexität größer als c bewiesen werden kann . Während der Satz von Gödel mit dem Lügnerparadox zusammenhängt , hängt das Ergebnis von Chaitin mit dem Berry-Paradox zusammen .

Unentscheidbare Aussagen in größeren Systemen beweisbar

Dies sind natürliche mathematische Äquivalente des Gödel-Satzes "wahr, aber unentscheidbar". Sie können in einem größeren System bewiesen werden, das allgemein als gültige Argumentation akzeptiert wird, sind jedoch in einem begrenzteren System wie der Peano-Arithmetik unentscheidbar.

1977 bewiesen Paris und Harrington , dass das Paris-Harrington-Prinzip , eine Version des unendlichen Ramsey-Theorems , in der Peano-Arithmetik (erster Ordnung) unentscheidbar ist , aber im stärkeren System der Arithmetik zweiter Ordnung bewiesen werden kann . Kirby und Paris zeigten später, dass Goodsteins Theorem , eine etwas einfachere Aussage über Folgen natürlicher Zahlen als das Paris-Harrington-Prinzip, auch in der Peano-Arithmetik unentscheidbar ist.

Kruskals Baumsatz , der in der Informatik Anwendung findet, ist ebenfalls von der Peano-Arithmetik unentscheidbar, aber in der Mengenlehre beweisbar. Tatsächlich ist Kruskals Baumsatz (oder seine endliche Form) in einem viel stärkeren System unentscheidbar, das die akzeptablen Prinzipien basierend auf einer Philosophie der Mathematik namens Prädikativismus kodifiziert . Das verwandte, aber allgemeinere Graph-Minor-Theorem (2003) hat Konsequenzen für die Computational Complexity Theorem .

Beziehung zur Berechenbarkeit

Siehe auch: Halteproblem § Gödels Unvollständigkeitssätze

Der Unvollständigkeitssatz steht in engem Zusammenhang mit mehreren Ergebnissen über unentscheidbare Mengen in der Rekursionstheorie .

Stephen Cole Kleene  ( 1943 ) präsentierte einen Beweis für Gödels Unvollständigkeitssatz unter Verwendung grundlegender Ergebnisse der Berechenbarkeitstheorie. Ein solches Ergebnis zeigt, dass das Anhalteproblem unentscheidbar ist: Es gibt kein Computerprogramm, das bei gegebenem Programm P als Eingabe korrekt bestimmen kann , ob P schließlich anhält, wenn es mit einer bestimmten gegebenen Eingabe ausgeführt wird. Kleene zeigte, dass die Existenz eines vollständigen effektiven Arithmetiksystems mit bestimmten Konsistenzeigenschaften das Halteproblem zur Entscheidbarkeit zwingen würde, einen Widerspruch. Diese Beweismethode wurde auch von Shoenfield (1967 , S. 132) vorgestellt ; Charlesworth (1980) ; und Hopcroft & Ullman (1979) .

Franzén (2005 , S. 73) erklärt, wie Matiyasevichs Lösung des 10. Problems von Hilbert verwendet werden kann, um einen Beweis für Gödels ersten Unvollständigkeitssatz zu erhalten. Matiyasevich bewies, dass es keinen Algorithmus gibt, der bei einem gegebenen multivariaten Polynom p(x 1 , x 2 ,...,x k ) mit ganzzahligen Koeffizienten bestimmt, ob es eine ganzzahlige Lösung der Gleichung p = 0 gibt. Da Polynome mit ganzzahligen Koeffizienten und ganze Zahlen selbst sind in der Sprache der Arithmetik direkt ausdrückbar, wenn eine multivariate ganzzahlige Polynomgleichung p = 0 eine Lösung in den ganzen Zahlen hat, dann wird dies jedes hinreichend starke arithmetische System T beweisen. Wenn das System T außerdem ω-konsistent ist, wird es niemals beweisen, dass eine bestimmte Polynomgleichung eine Lösung hat, wenn es tatsächlich keine Lösung in den ganzen Zahlen gibt. Wenn also T vollständig und ω-konsistent wäre, könnte man algorithmisch bestimmen, ob eine Polynomgleichung eine Lösung hat, indem man lediglich Beweise von T aufzählt, bis entweder " p hat eine Lösung" oder " p hat keine Lösung" gefunden ist, in Widerspruch zum Satz von Matiyasevich. Daraus folgt, dass T nicht w- konsistent und vollständig sein kann. Darüber hinaus ist es für jedes konsistente effektiv generierte System T möglich, effektiv ein multivariates Polynom p über die ganzen Zahlen zu erzeugen, so dass die Gleichung p = 0 keine Lösungen über die ganzen Zahlen hat, aber das Fehlen von Lösungen in T nicht bewiesen werden kann ( Davis 2006 , S. 416 ; Jones 1980 ).

Smorynski (1977 , S. 842) zeigt, wie die Existenz rekursiv untrennbarer Mengen zum Beweis des ersten Unvollständigkeitssatzes verwendet werden kann. Dieser Beweis wird oft erweitert, um zu zeigen, dass Systeme wie die Peano-Arithmetik im Wesentlichen unentscheidbar sind (siehe Kleene 1967 , S. 274 ).

Der Unvollständigkeitssatz von Chaitin gibt eine andere Methode zur Erzeugung unabhängiger Sätze, basierend auf der Kolmogorov-Komplexität . Wie der oben erwähnte Beweis von Kleene gilt der Satz von Chaitin nur für Theorien mit der zusätzlichen Eigenschaft, dass alle ihre Axiome im Standardmodell der natürlichen Zahlen wahr sind. Gödels Unvollständigkeitssatz zeichnet sich durch seine Anwendbarkeit auf konsistente Theorien aus, die nichtsdestotrotz falsche Aussagen im Standardmodell enthalten; diese Theorien werden als ω-inkonsistent bezeichnet .

Beweisskizze für den ersten Satz

Hauptartikel: Beweisskizze für Gödels ersten Unvollständigkeitssatz

Der Widerspruchsbeweis besteht aus drei wesentlichen Teilen. Wählen Sie zunächst ein formales System, das die vorgeschlagenen Kriterien erfüllt:

  1. Aussagen im System können durch natürliche Zahlen (bekannt als Gödel-Zahlen) dargestellt werden. Die Bedeutung davon ist, dass Eigenschaften von Aussagen – wie deren Wahrheit und Falschheit – gleichbedeutend sind mit der Feststellung, ob ihre Gödel-Zahlen bestimmte Eigenschaften haben, und dass Eigenschaften der Aussagen daher durch Untersuchung ihrer Gödel-Zahlen nachgewiesen werden können. Dieser Teil gipfelt in der Konstruktion einer Formel, die die Idee ausdrückt, dass "Aussage S im System beweisbar ist" (die auf jede Aussage "S" im System angewendet werden kann).
  2. Im formalen System ist es möglich, eine Zahl zu konstruieren, deren übereinstimmende Aussage, wenn sie interpretiert wird, selbstreferenziell ist und im Wesentlichen sagt, dass sie (dh die Aussage selbst) nicht beweisbar ist. Dies geschieht mit Hilfe einer Technik namens „ Diagonalisierung “ (so genannt wegen ihres Ursprungs als Cantors diagonales Argument ).
  3. Innerhalb des formalen Systems erlaubt diese Aussage den Nachweis, dass sie im System weder beweisbar noch widerlegbar ist und daher das System tatsächlich nicht ω-konsistent sein kann. Daher ist die ursprüngliche Annahme, dass das vorgeschlagene System die Kriterien erfüllt, falsch.

Arithmetisierung der Syntax

Das Hauptproblem bei der Ausarbeitung des oben beschriebenen Beweises besteht darin, dass es zunächst scheint, dass, um eine Aussage p zu konstruieren , die äquivalent zu " p ist nicht beweisbar" ist, p irgendwie eine Referenz auf p enthalten müsste , was leicht zu ein unendlicher Rückschritt. Gödels geniale Technik besteht darin, zu zeigen, dass Aussagen mit Zahlen (oft als Arithmetisierung der Syntax bezeichnet ) so abgeglichen werden können , dass "eine Aussage beweisen" durch "Prüfen, ob eine Zahl eine bestimmte Eigenschaft hat" ersetzt werden kann . Auf diese Weise kann eine selbstreferenzielle Formel so konstruiert werden, dass jeder unendliche Regress von Definitionen vermieden wird. Dieselbe Technik wurde später von Alan Turing in seiner Arbeit zum Entscheidungsproblem verwendet .

Vereinfacht gesagt kann man sich eine Methode ausdenken, bei der jede im System formulierbare Formel oder Aussage eine eindeutige Zahl, ihre Gödel-Zahl genannt , erhält , so dass eine mechanische Umrechnung zwischen Formeln und Gödel möglich ist Zahlen. Die betreffenden Zahlen können in der Tat sehr lang sein (in Bezug auf die Anzahl der Stellen), aber dies ist kein Hindernis; Wichtig ist nur, dass solche Zahlen konstruiert werden können. Ein einfaches Beispiel ist die Art und Weise, wie Englisch als Zahlenfolge in Computern mit ASCII oder Unicode gespeichert wird :

  • Das Wort HELLOwird durch 72-69-76-76-79 mit dezimalem ASCII dargestellt , dh die Zahl 7269767679.
  • Die logische Anweisung x=y => y=xwird durch 120-061-121-032-061-062-032-121-061-120 unter Verwendung von oktalem ASCII dargestellt , dh die Zahl 120061121032061062032121061120.

Im Prinzip kann der Beweis einer Aussage als wahr oder falsch gezeigt werden, um zu beweisen, dass die Zahl, die der Aussage entspricht, eine bestimmte Eigenschaft hat oder nicht. Da das formale System stark genug ist, um das Denken über Zahlen im Allgemeinen zu unterstützen , kann es auch das Denken über Zahlen unterstützen, die Formeln und Aussagen darstellen . Da das System die Argumentation über Eigenschaften von Zahlen unterstützen kann , sind die Ergebnisse entscheidend mit der Argumentation über die Beweisbarkeit ihrer äquivalenten Aussagen äquivalent .

Konstruktion einer Aussage über "Beweisbarkeit"

Nachdem gezeigt wurde, dass das System im Prinzip indirekt Aussagen über die Beweisbarkeit treffen kann, ist es nun möglich, durch die Analyse der Eigenschaften dieser Zahlen, die Aussagen repräsentieren, zu zeigen, wie eine Aussage erstellt wird, die dies tatsächlich tut.

Eine Formel F ( x ), die genau eine freie Variable x enthält, heißt Anweisungsform oder Klassenzeichen . Sobald x durch eine bestimmte Zahl ersetzt wird, wird die Aussageform zur Bona-fide- Aussage, die dann im System beweisbar ist oder nicht. Für bestimmte Formeln kann man , dass für jede natürliche Zahl zeigen n , ist wahr , wenn und nur wenn nachgewiesen werden kann (die genaue Anforderung im ursprünglichen Beweis ist schwächer, aber für den Beweis dieses genügt Skizze). Dies gilt insbesondere für jede spezifische arithmetische Operation zwischen einer endlichen Anzahl natürlicher Zahlen, beispielsweise "2  ×  3 = 6".

Aussageformen selbst sind keine Aussagen und können daher weder bewiesen noch widerlegt werden. Aber jeder Aussageform F ( x ) kann eine Gödel-Zahl zugeordnet werden, die mit G ( F ) bezeichnet wird. Die Wahl der verwendeten freien Variablen in der Form F ( x ) ist für die Zuweisung der Gödel-Zahl G ( F ) nicht relevant .

Der Begriff der Beweisbarkeit selbst kann auch durch Gödel-Zahlen wie folgt kodiert werden: Da ein Beweis eine Liste von Aussagen ist, die bestimmten Regeln gehorchen, kann die Gödel-Zahl eines Beweises definiert werden. Nun kann man für jede Aussage p fragen, ob eine Zahl x die Gödelsche Zahl ihres Beweises ist. Die Beziehung zwischen der Gödel-Zahl von p und x , der potentiellen Gödel-Zahl ihres Beweises, ist eine arithmetische Beziehung zwischen zwei Zahlen. Daher gibt es eine Aussageform Bew( y ), die diese arithmetische Beziehung verwendet, um zu sagen, dass eine Gödel-Zahl eines Beweises von y existiert:

Bew( y ) = ∃ x ( y ist die Gödel-Zahl einer Formel und x ist die Gödel-Zahl eines Beweises der durch y codierten Formel ).

Der Name Bew ist die Abkürzung für beweisbar , das deutsche Wort für „beweisbar“; dieser Name wurde ursprünglich von Gödel verwendet, um die eben beschriebene Beweisbarkeitsformel zu bezeichnen. Beachten Sie, dass "Bew( y )" lediglich eine Abkürzung ist, die eine bestimmte, sehr lange Formel in der Originalsprache von T darstellt ; die Zeichenfolge "Bew" selbst wird nicht als Teil dieser Sprache beansprucht.

Ein wichtiges Merkmal der Formel Bew( y ) ist, dass, wenn eine Aussage p im System beweisbar ist, auch Bew( G ( p )) beweisbar ist. Dies liegt daran, dass jeder Beweis von p eine entsprechende Gödel-Zahl hätte, deren Existenz bewirkt, dass Bew( G ( p )) erfüllt ist.

Diagonale

Der nächste Schritt des Beweises besteht darin, eine Aussage zu erhalten, die indirekt ihre eigene Unbeweisbarkeit behauptet. Obwohl Gödel diese Aussage direkt konstruiert hat, folgt die Existenz mindestens einer solchen Aussage aus dem Diagonallemma , das besagt, dass es für jedes hinreichend starke formale System und jede Aussageform F eine Aussage p gibt, so dass das System beweist

p ↔ F ( G ( p )).

Indem wir F die Negation von Bew( x ) seien, erhalten wir den Satz

p ↔ ~Bew ( G ( p ))

und das dadurch definierte p sagt grob aus, dass seine eigene Gödel-Zahl die Gödel-Zahl einer nicht beweisbaren Formel ist.

Die Anweisung p ist nicht buchstäblich gleich ~Bew( G ( p )); p sagt vielmehr aus, dass, wenn eine bestimmte Rechnung durchgeführt wird, die resultierende Gödel-Zahl die einer nicht beweisbaren Aussage ist. Aber wenn diese Berechnung durchgeführt wird, stellt sich heraus, dass die resultierende Gödel-Zahl die Gödel-Zahl von p selbst ist. Dies ähnelt dem folgenden Satz auf Englisch:

", wenn in Anführungszeichen vor sich selbst steht, ist nicht beweisbar.", wenn in Anführungszeichen vor sich selbst steht, ist nicht beweisbar.

Dieser Satz bezieht sich nicht direkt auf sich selbst, aber wenn die angegebene Transformation vorgenommen wird, erhält man als Ergebnis den ursprünglichen Satz, und dieser Satz behauptet somit indirekt seine eigene Unbeweisbarkeit. Der Beweis des Diagonallemmas verwendet eine ähnliche Methode.

Nehmen wir nun an, das axiomatische System sei ω-konsistent und sei p die im vorherigen Abschnitt erhaltene Aussage.

Wäre p beweisbar, dann wäre Bew( G ( p )) beweisbar, wie oben argumentiert. Aber p behauptet die Negation von Bew( G ( p )). Somit wäre das System inkonsistent und würde sowohl eine Aussage als auch ihre Negation beweisen. Dieser Widerspruch zeigt, dass p nicht beweisbar ist.

Wäre die Negation von p beweisbar, dann wäre Bew( G ( p )) beweisbar (weil p äquivalent zur Negation von Bew( G ( p )) konstruiert wurde ). Für jede spezifische Zahl x kann x jedoch nicht die Gödel-Zahl des Beweises von p sein , da p nicht beweisbar ist (aus dem vorherigen Absatz). Damit beweist das System einerseits, dass es eine Zahl mit einer bestimmten Eigenschaft gibt (dass es die Gödel-Zahl des Beweises von p ist ), aber andererseits können wir für jede spezifische Zahl x beweisen, dass sie diese nicht hat Eigentum. Dies ist in einem ω-konsistenten System unmöglich. Somit ist die Negation von p nicht beweisbar.

Somit ist die Aussage p in unserem axiomatischen System unentscheidbar: sie kann innerhalb des Systems weder bewiesen noch widerlegt werden.

Um zu zeigen, dass p nicht beweisbar ist, bedarf es lediglich der Annahme, dass das System konsistent ist. Die stärkere Annahme der ω-Konsistenz ist erforderlich, um zu zeigen, dass die Negation von p nicht beweisbar ist. Wenn also p für ein bestimmtes System konstruiert wird:

  • Ist das System ω-konsistent, kann es weder p noch seine Negation beweisen , also ist p unentscheidbar.
  • Wenn das System konsistent ist, kann es die gleiche Situation haben oder die Negation von p beweisen . Im letzteren Fall haben wir eine falsche, aber beweisbare Aussage ("nicht p ") und das System ist nicht ω-konsistent.

Wenn man versucht, "die fehlenden Axiome hinzuzufügen", um die Unvollständigkeit des Systems zu vermeiden, muss man entweder p oder "nicht p " als Axiome hinzufügen . Aber dann ändert sich die Definition einer Aussage, "eine Gödel-Zahl eines Beweises zu sein". was bedeutet, dass die Formel Bew( x ) jetzt anders ist. Wenn wir also das Diagonallemma auf dieses neue Bew anwenden, erhalten wir eine neue Aussage p , die sich von der vorherigen unterscheidet und die im neuen System unentscheidbar ist, wenn sie ω-konsistent ist.

Beweis über Berrys Paradox

George Boolos  ( 1989 ) skizziert einen alternativen Beweis des ersten Unvollständigkeitssatzes, der das Berry-Paradoxon anstelle des Lügnerparadoxons verwendet , um eine wahre, aber nicht beweisbare Formel zu konstruieren. Eine ähnliche Beweismethode wurde unabhängig von Saul Kripke entdeckt ( Boolos 1998 , S. 383) . Der Beweis von Boolos fährt fort, indem er für jede berechenbar aufzählbare Menge S von wahren arithmetischen Sätzen einen anderen Satz konstruiert, der wahr ist, aber nicht in S enthalten ist . Dies liefert als Korollar den ersten Unvollständigkeitssatz. Dieser Beweis ist nach Boolos interessant, weil er eine "andere Art von Begründung" für die Unvollständigkeit effektiver, konsistenter Theorien der Arithmetik liefert ( Boolos 1998 , S. 388) .

Computerverifizierte Beweise

Siehe auch: Automatisiertes Theorembeweisen

Die Unvollständigkeitssätze gehören zu einer relativ kleinen Anzahl von nichttrivialen Sätzen, die in formalisierte Sätze umgewandelt wurden, die vollständig durch Beweisassistenten- Software verifiziert werden können . Gödels ursprüngliche Beweise der Unvollständigkeitssätze wurden, wie die meisten mathematischen Beweise, in natürlicher Sprache geschrieben, die für menschliche Leser gedacht war.

Computerverifizierte Beweise von Versionen des ersten Unvollständigkeitssatzes wurden 1986 von Natarajan Shankar mit Nqthm ( Shankar 1994 ) , von Russell O'Connor 2003 mit Coq ( O'Connor 2005 ) und von John Harrison 2009 mit HOL Light ( Harrison 2009 ) . Ein computerverifizierter Beweis beider Unvollständigkeitssätze wurde 2013 von Lawrence Paulson mit Isabelle angekündigt ( Paulson 2014 ) .

Beweisskizze für den zweiten Satz

Siehe auch: Hilbert-Bernays-Beweisbedingung

Die Hauptschwierigkeit beim Beweis des zweiten Unvollständigkeitssatzes besteht darin zu zeigen, dass verschiedene Tatsachen über die Beweisbarkeit, die im Beweis des ersten Unvollständigkeitssatzes verwendet werden, innerhalb eines Systems S unter Verwendung eines formalen Prädikats für die Beweisbarkeit formalisiert werden können . Danach folgt der zweite Unvollständigkeitssatz, indem der gesamte Beweis des ersten Unvollständigkeitssatzes innerhalb des Systems S selbst formalisiert wird .

Lassen Sie p für den oben konstruierten unentscheidbaren Satz stehen, und nehmen Sie zum Zweck des Erhaltens eines Widerspruchs an, dass die Konsistenz des Systems S aus dem System S selbst heraus bewiesen werden kann. Dies ist gleichbedeutend mit dem Beweis der Aussage "System S ist konsistent". Betrachten Sie nun die Aussage c , wobei c = "Wenn das System S konsistent ist, dann ist p nicht beweisbar". Der Beweis von Satz c kann innerhalb des Systems S formalisiert werden , und daher kann die Aussage c, " p ist nicht beweisbar" (oder identisch "nicht P ( p )") im System S bewiesen werden .

Beachten Sie dann, dass wenn wir beweisen können, dass das System S konsistent ist (dh die Aussage in der Hypothese von c ), dann haben wir bewiesen, dass p nicht beweisbar ist. Aber das ist ein Widerspruch , da durch den ersten Unvollständigkeitssatzes, ist dieser Satz (dh. , Was in dem Satz impliziert c „“ p „ist nicht beweisbar“) ist das, was wir nicht beweisbar sein konstruieren. Beachten Sie, dass aus diesem Grund benötigen wir die erste Unvollständigkeitssatzes in Formalisierung S : die 2. Unvollständigkeitssatzes zu beweisen, so erhalten wir einen Widerspruch mit dem 1. Unvollständigkeitssatzes das nur tun können , durch die zeigen , dass der Satz gilt in S . Wir können also nicht beweisen, dass das System S konsistent ist. Und es folgt die Aussage des 2. Unvollständigkeitssatzes.

Diskussion und Implikationen

Die Ergebnisse der Unvollständigkeit wirken sich auf die Philosophie der Mathematik aus , insbesondere auf die Versionen des Formalismus , die ein einziges System der formalen Logik verwenden, um ihre Prinzipien zu definieren.

Konsequenzen für den Logikismus und Hilberts zweites Problem

Es wird manchmal angenommen, dass das Unvollständigkeitstheorem schwerwiegende Konsequenzen für das von Gottlob Frege und Bertrand Russell vorgeschlagene Programm des Logikismus hat , das darauf abzielte, die natürlichen Zahlen in Begriffen der Logik zu definieren ( Hellman 1981 , S. 451–468) . Bob Hale und Crispin Wright argumentieren, dass dies für den Logikismus kein Problem darstellt, da die Unvollständigkeitssätze gleichermaßen für die Logik erster Ordnung gelten wie für die Arithmetik. Sie argumentieren, dass nur diejenigen dieses Problem haben, die glauben, dass die natürlichen Zahlen im Sinne der Logik erster Ordnung definiert werden müssen.

Viele Logiker glauben , dass Gödels Unvollständigkeitssätze einen tödlichen Schlag zu schlug David Hilbert ‚s zweites Problem , das für die Mathematik für eine finitäre Konsistenz Beweis gefragt. Insbesondere das zweite Unvollständigkeitstheorem wird oft so angesehen, dass es das Problem unmöglich macht. Allerdings sind nicht alle Mathematiker mit dieser Analyse einverstanden, und der Status von Hilberts zweitem Problem ist noch nicht entschieden (siehe „ Neuere Standpunkte zum Status des Problems “).

Köpfe und Maschinen

Hauptartikel: Mechanismus (Philosophie) § Gödelsche Argumente

Autoren, darunter der Philosoph JR Lucas und der Physiker Roger Penrose, haben diskutiert, was Gödels Unvollständigkeitstheoreme über die menschliche Intelligenz implizieren. Ein Großteil der Debatte dreht sich darum, ob der menschliche Geist einer Turing-Maschine oder nach der Church-Turing-These überhaupt einer endlichen Maschine entspricht. Wenn dies der Fall ist und die Maschine konsistent ist, dann gelten die Unvollständigkeitssätze von Gödel für sie.

Hilary Putnam  ( 1960 ) schlug vor, dass Gödels Theoreme zwar nicht auf Menschen angewendet werden können, da sie Fehler machen und daher inkonsistent sind, sie aber auf die menschliche Fakultät der Naturwissenschaften oder Mathematik im Allgemeinen angewendet werden können. Unter der Annahme, dass sie konsistent ist, kann ihre Konsistenz entweder nicht bewiesen oder nicht durch eine Turingmaschine repräsentiert werden.

Avi Wigderson  ( 2010 ) hat vorgeschlagen, dass das Konzept der mathematischen „Erkennbarkeit“ eher auf rechnerischer Komplexität als auf logischer Entscheidbarkeit basieren sollte . Er schreibt: "Wenn die Erkennbarkeit nach modernen Maßstäben interpretiert wird, nämlich durch Rechenkomplexität, sind die Gödel-Phänomene sehr bei uns."

Douglas Hofstadter zitiert in seinen Büchern Gödel, Escher, Bach und I Am a Strange Loop Gödels Theoreme als Beispiel für das, was er eine seltsame Schleife nennt , eine hierarchische, selbstreferenzielle Struktur, die innerhalb eines axiomatischen formalen Systems existiert. Er argumentiert, dass dies die gleiche Art von Struktur ist, die das Bewusstsein, das Ich-Gefühl im menschlichen Geist, hervorruft. Während die Selbstreferenz in Gödels Theorem aus dem Gödel-Satz stammt, der seine eigene Unbeweisbarkeit innerhalb des formalen Systems der Principia Mathematica behauptet, kommt die Selbstreferenz im menschlichen Geist aus der Art und Weise, wie das Gehirn Reize in "Symbole" abstrahiert und kategorisiert. oder Gruppen von Neuronen, die auf Konzepte reagieren, was effektiv auch ein formales System ist, was schließlich zu Symbolen führt, die das Konzept genau der Entität modellieren, die die Wahrnehmung durchführt. Hofstadter argumentiert, dass eine seltsame Schleife in einem hinreichend komplexen formalen System zu einer "unten" oder "auf den Kopf gestellten" Kausalität führen kann, einer Situation, in der die normale Hierarchie von Ursache und Wirkung auf den Kopf gestellt wird. Im Fall des Satzes von Gödel manifestiert sich dies kurz wie folgt:

„Allein aus der Kenntnis der Bedeutung der Formel kann man auf ihre Wahrheit oder Falschheit schließen, ohne sie auf altmodische Weise herleiten zu müssen, die es erfordert, von den Axiomen methodisch „aufwärts“ zu stapfen. Das ist nicht nur eigenartig, es ist erstaunlich . Normalerweise kann man sich nicht nur ansehen, was eine mathematische Vermutung sagt, und sich einfach auf den Inhalt dieser Aussage berufen, um daraus abzuleiten, ob die Aussage wahr oder falsch ist." ( Ich bin eine seltsame Schleife. )

Im Fall des Geistes, einem weitaus komplexeren formalen System, manifestiert sich diese "Abwärtskausalität" nach Ansicht Hofstadters als der unsägliche menschliche Instinkt, dass die Kausalität unseres Geistes auf der hohen Ebene von Wünschen, Konzepten, Persönlichkeiten, Gedanken und Ideen, als auf der niedrigen Ebene der Wechselwirkungen zwischen Neuronen oder sogar fundamentalen Teilchen, obwohl letztere der Physik zufolge die kausale Kraft zu besitzen scheint.

„Unsere normale menschliche Art, die Welt wahrzunehmen, hat also eine merkwürdige Umkehrung: Wir sind darauf ausgelegt, „großes Zeug“ statt „kleines Zeug“ wahrzunehmen, obwohl die Domäne des Kleinen dort zu liegen scheint, wo die eigentlichen Motoren antreiben Realität wohnen." ( Ich bin eine seltsame Schleife. )

Parakonsistente Logik

Obwohl Gödels Theoreme normalerweise im Kontext der klassischen Logik studiert werden, spielen sie auch eine Rolle bei der Erforschung der parakonsistenten Logik und von inhärent widersprüchlichen Aussagen ( Dialetheia ). Graham Priest  ( 1984 , 2006 ) argumentiert , dass das Ersetzen des Begriffs des formalen Beweises in Gödels Satz durch den üblichen Begriff des informellen Beweises verwendet werden kann , um zu zeigen , dass naive Mathematik inkonsistent ist , und verwendet dies als Beweis für den Dialetheismus . Die Ursache dieser Inkonsistenz ist die Aufnahme eines Wahrheitsprädikats für ein System in die Sprache des Systems ( Priest 2006 , S. 47) . Stewart Shapiro  ( 2002 ) bewertet die Anwendungen der Gödelschen Theoreme auf den Dialetheismus gemischter.

Appelle an die Unvollständigkeitssätze in anderen Bereichen

Manchmal werden Appelle und Analogien zu den Unvollständigkeitssätzen gemacht, um Argumente zu unterstützen, die über Mathematik und Logik hinausgehen. Mehrere Autoren haben sich negativ zu solchen Erweiterungen und Interpretationen geäußert , darunter Torkel Franzén (2005); Panu Raatikainen (2005) ; Alan Sokal und Jean Bricmont  ( 1999 ); und Ophelia Benson und Jeremy Stangroom  ( 2006 ). Bricmont & Stangroom (2006 , S. 10) zitieren beispielsweise aus Rebecca Goldsteins Kommentaren zur Diskrepanz zwischen Gödels bekennendem Platonismus und den antirealistischen Verwendungen, denen seine Ideen manchmal dienen. Sokal & Bricmont (1999 , S. 187) kritisieren Régis Debrays Aufruf des Theorems im Kontext der Soziologie; Debray hat diese Verwendung als metaphorisch verteidigt (ebd.).

Geschichte

Nachdem Gödel 1929 seinen Beweis des Vollständigkeitssatzes als Doktorarbeit veröffentlicht hatte, wandte er sich für seine Habilitation einem zweiten Problem zu . Sein ursprüngliches Ziel war es, eine positive Lösung für Hilberts zweites Problem zu finden ( Dawson 1997 , S. 63). Damals wurden Theorien der natürlichen Zahlen und reellen Zahlen , die der Arithmetik zweiter Ordnung ähnlich sind, als "Analyse" bezeichnet, während Theorien der natürlichen Zahlen allein als "Arithmetik" bekannt waren.

Gödel war nicht der einzige, der an dem Konsistenzproblem arbeitete. Ackermann hatte 1925 einen fehlerhaften Konsistenzbeweis für die Analyse veröffentlicht, in dem er versuchte, die ursprünglich von Hilbert entwickelte Methode der ε-Substitution zu verwenden . Später in diesem Jahr konnte von Neumann den Beweis für ein arithmetisches System ohne Induktionsaxiome korrigieren. Bis 1928 hatte Ackermann Bernays einen modifizierten Beweis übermittelt; Dieser modifizierte Beweis veranlasste Hilbert, 1929 seine Überzeugung zu verkünden, dass die Konsistenz der Arithmetik bewiesen sei und dass wahrscheinlich bald ein Konsistenzbeweis der Analysis folgen würde. Nachdem die Veröffentlichung der Unvollständigkeitssätze gezeigt hatte, dass Ackermanns modifizierter Beweis fehlerhaft sein muss, lieferte von Neumann ein konkretes Beispiel, das zeigt, dass seine Haupttechnik fehlerhaft war ( Zach 2007 , S. 418; Zach 2003 , S. 33).

Im Zuge seiner Forschungen entdeckte Gödel, dass ein Satz, der seine eigene Unwahrheit behauptet, zwar zum Paradox führt, ein Satz, der seine eigene Nichtbeweisbarkeit behauptet, dies jedoch nicht. Insbesondere war Gödel sich des Ergebnisses bewusst, das heute Tarskis Undefinierbarkeitssatz genannt wird , obwohl er es nie veröffentlicht hat. Gödel kündigte Carnap, Feigel und Waismann am 26. August 1930 seinen ersten Unvollständigkeitssatz an; alle vier würden an der zweiten Konferenz zur Epistemologie der exakten Wissenschaften teilnehmen , einer Schlüsselkonferenz in der folgenden Woche in Königsberg .

Bekanntmachung

Die Königsberger Konferenz 1930 war ein gemeinsames Treffen dreier akademischer Gesellschaften, an denen viele der wichtigsten Logiker der damaligen Zeit teilnahmen. Carnap, Heyting und von Neumann hielten jeweils einstündige Vorträge über die mathematischen Philosophien des Logizismus, Intuitionismus und Formalismus ( Dawson 1996 , S. 69). Die Konferenz beinhaltete auch Hilberts Ruhestandsrede, als er sein Amt an der Universität Göttingen aufgab. Hilbert benutzte die Rede, um seine Überzeugung zu begründen, dass alle mathematischen Probleme gelöst werden können. Er beendete seine Ansprache mit den Worten:

Für den Mathematiker gibt es keinen Ignorabimus und meiner Meinung nach auch gar nicht für die Naturwissenschaft. ... Der wahre Grund, warum es [niemand] gelungen ist, ein unlösbares Problem zu finden, ist meiner Meinung nach, dass es kein unlösbares Problem gibt. Im Gegensatz zum törichten Ignorabimus lautet unser Credo: Wir müssen es wissen. Wir werden es wissen!

Diese Rede wurde schnell als Zusammenfassung von Hilberts Überzeugungen zur Mathematik bekannt (seine letzten sechs Worte, " Wir müssen wissen. Wir werden wissen! ", wurden 1943 als Hilberts Grabinschrift verwendet). Obwohl Gödel wahrscheinlich zu Hilberts Ansprache anwesend war, trafen sich die beiden nie von Angesicht zu Angesicht ( Dawson 1996 , S. 72).

Gödel kündigte sein erstes Unvollständigkeitstheorem bei einer Diskussionsrunde am dritten Konferenztag an. Abgesehen von von Neumann, der Gödel zum Gespräch beiseite zog, erregte die Ankündigung wenig Aufmerksamkeit. Später in diesem Jahr erhielt von Neumann, unabhängig mit Kenntnis des ersten Unvollständigkeitssatzes, einen Beweis des zweiten Unvollständigkeitssatzes, den er Gödel in einem Brief vom 20. November 1930 mitteilte ( Dawson 1996 , S. 70). Gödel hatte das zweite Unvollständigkeitstheorem unabhängig erhalten und in sein Manuskript aufgenommen, das am 17. November 1930 bei den Monatsheften für Mathematik einging.

Gödels Aufsatz erschien 1931 in den Monatsheften unter dem Titel "Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I ". Wie der Titel vermuten lässt, plante Gödel ursprünglich, einen zweiten Teil des Papiers im nächsten Band der Monatshefte zu veröffentlichen ; die prompte Annahme des ersten Papiers war ein Grund, warum er seine Pläne änderte ( van Heijenoort 1967 , Seite 328, Fußnote 68a) .

Verallgemeinerung und Akzeptanz

Gödel hielt 1933–1934 in Princeton eine Reihe von Vorträgen über seine Theoreme vor einem Publikum, zu dem Church, Kleene und Rosser gehörten. Zu diesem Zeitpunkt hatte Gödel erkannt, dass die Schlüsseleigenschaft seiner Theoreme darin besteht, dass das System effektiv sein muss (damals wurde der Begriff "allgemein rekursiv" verwendet). Rosser bewies 1936, dass die Hypothese der ω-Konsistenz, die ein wesentlicher Bestandteil von Gödels ursprünglichem Beweis war, durch eine einfache Konsistenz ersetzt werden kann, wenn der Gödel-Satz in geeigneter Weise geändert wird. Diese Entwicklungen haben die Unvollständigkeitssätze im Wesentlichen in ihrer modernen Form hinterlassen.

Gentzen veröffentlichte 1936 seinen Konsistenzbeweis für Arithmetik erster Ordnung. Hilbert akzeptierte diesen Beweis als "finitär", obwohl er (wie Gödels Satz bereits gezeigt hatte) nicht innerhalb des zu beweisenden konsistenten Rechensystems formalisiert werden kann.

Der Einfluss der Unvollständigkeitssätze auf Hilberts Programm wurde schnell erkannt. Bernays fügte einen vollständigen Beweis der Unvollständigkeitssätze in den zweiten Band der Grundlagen der Mathematik ( 1939 ) ein, zusammen mit zusätzlichen Ergebnissen von Ackermann über die ε-Substitutionsmethode und Gentzens Konsistenzbeweis der Arithmetik. Dies war der erste vollständig veröffentlichte Beweis des zweiten Unvollständigkeitssatzes.

Kritikpunkte

Finsler

Paul Finsler  ( 1926 ) benutzte eine Version von Richards Paradox , um einen Ausdruck zu konstruieren, der falsch, aber in einem bestimmten, informellen Rahmen, den er entwickelt hatte, nicht beweisbar war. Gödel war sich dieser Arbeit nicht bewusst, als er die Unvollständigkeitssätze bewies (Collected Works Vol. IV, S. 9). Finsler schrieb 1931 an Gödel, um ihn über diese Arbeit zu informieren, die Finsler für einen Unvollständigkeitssatz vorrangig hielt. Finslers Methoden beruhten nicht auf formalisierter Beweisbarkeit und hatten nur eine oberflächliche Ähnlichkeit mit Gödels Werk ( van Heijenoort 1967 , S. 328) . Gödel las das Papier, fand es aber zutiefst fehlerhaft, und seine Antwort auf Finsler machte Bedenken hinsichtlich der fehlenden Formalisierung deutlich ( Dawson , S. 89 ). Finsler setzte sich für den Rest seiner Karriere weiterhin für seine Philosophie der Mathematik ein, die auf Formalisierung verzichtete.

Zermelo

Im September 1931 schrieb Ernst Zermelo an Gödel, um mitzuteilen, was er als „wesentliche Lücke“ in Gödels Argumentation bezeichnete ( Dawson , S. 76 ). Im Oktober antwortete Gödel mit einem 10-seitigen Brief ( Dawson , S. 76 , Grattan-Guinness , S. 512–513 ), in dem er darauf hinwies, dass Zermelo fälschlicherweise annahm, dass der Begriff der Wahrheit in einem System in diesem System definierbar sei (was nach Tarskis Undefinierbarkeitssatz im Allgemeinen nicht stimmt ). Aber Zermelo gab nicht nach und veröffentlichte seine Kritik mit "einem ziemlich vernichtenden Absatz über seinen jungen Konkurrenten" ( Grattan-Guinness , S. 513 ). Gödel entschied, dass es sinnlos sei, die Angelegenheit weiter zu verfolgen, und Carnap stimmte zu ( Dawson , S. 77 ). Ein Großteil von Zermelos nachfolgenden Arbeiten bezog sich auf Logiken, die stärker waren als die Logik erster Ordnung, mit der er hoffte, sowohl die Konsistenz als auch die Kategorisierung mathematischer Theorien zu zeigen.

Wittgenstein

Ludwig Wittgenstein schrieb mehrere Passagen über die Unvollständigkeitssätze, die posthum in seinen 1953 erschienenen Bemerkungen zu den Grundlagen der Mathematik veröffentlicht wurden , insbesondere einen Abschnitt, der manchmal als "berüchtigter Absatz" bezeichnet wird und in dem er die Begriffe "wahr" und "beweisbar" zu verwechseln scheint Russells System. Gödel war Mitglied des Wiener Kreises in der Zeit, in der Wittgensteins frühe ideale Sprachphilosophie und Tractatus Logico-Philosophicus das Denken des Kreises dominierten. Es gab einige Kontroversen darüber, ob Wittgenstein das Unvollständigkeitstheorem falsch verstanden oder sich nur unklar ausgedrückt hat. Schriften in Gödels Nachlass drücken den Glauben aus, Wittgenstein habe seine Ideen falsch verstanden.

Mehrere Kommentatoren haben Wittgenstein als Missverständnis von Gödel ( Rodych 2003 ) gelesen , obwohl Juliet Floyd und Hilary Putnam  ( 2000 ) sowie Graham Priest  ( 2004 ) Textlesungen geliefert haben, die argumentieren, dass die meisten Kommentare Wittgenstein missverstehen. Bei ihrer Freilassung schrieben Bernays, Dummett und Kreisel separate Rezensionen zu Wittgensteins Äußerungen, die alle äußerst negativ waren ( Berto 2009 , S. 208) . Die Einstimmigkeit dieser Kritik führte dazu, dass Wittgensteins Bemerkungen zu den Unvollständigkeitssätzen wenig Einfluss auf die logische Gemeinschaft hatten. Im Jahr 1972 erklärte Gödel: „? Hat verloren Wittgenstein seine Meinung Meint er es ernst Er spricht absichtlich trivialen unsinnige Aussagen“ ( Wang 1996 , S. 179) . Und schrieb an Karl Menger , dass Wittgensteins Bemerkungen ein Missverständnis der Unvollständigkeitssätze demonstrieren Schreiben:

Es ist klar , aus den Stellen Sie zitieren , dass Wittgenstein hat nicht verstehen [das erste Unvollständigkeitssatzes] (oder gaben vor , es nicht zu verstehen). Er interpretierte es als eine Art logisches Paradoxon, während es in Wirklichkeit genau das Gegenteil ist, nämlich ein mathematischer Satz innerhalb eines absolut unumstrittenen Teils der Mathematik (finitäre Zahlentheorie oder Kombinatorik). ( Wang 1996 , S. 179)

Seit der Veröffentlichung von Wittgensteins Nachlass im Jahr 2000 hat eine Reihe von philosophischen Aufsätzen versucht zu bewerten, ob die ursprüngliche Kritik an Wittgensteins Bemerkungen berechtigt war. Floyd & Putnam (2000) argumentieren, dass Wittgenstein ein umfassenderes Verständnis des Unvollständigkeitssatzes hatte als bisher angenommen. Sie befassen sich insbesondere mit der Interpretation eines Gödel-Satzes für ein ω-inkonsistentes System als eigentlich "Ich bin nicht beweisbar", da das System keine Modelle hat, in denen das Beweisbarkeitsprädikat der tatsächlichen Beweisbarkeit entspricht. Rodych (2003) argumentiert, dass ihre Interpretation von Wittgenstein historisch nicht gerechtfertigt ist, während Bays (2004) gegen Floyds und Putnams philosophische Analyse des Beweisbarkeitsprädikats argumentiert. Berto (2009) untersucht die Beziehung zwischen Wittgensteins Schrift und Theorien der parakonsistenten Logik.

Siehe auch

Verweise

Zitate

Artikel von Gödel

  • Kurt Gödel, 1931, "Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I", Monatshefte für Mathematik und Physik , v. 38 n. 1, S. 173–198. doi : 10.1007/BF01700692
  • —, 1931, "Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I", in Solomon Feferman , Hg., 1986 . ich . Oxford University Press, S. 144-195. ISBN  978-0195147209 . Das deutsche Original mit einer gegenüberstehenden englischen Übersetzung, der eine einleitende Anmerkung von Stephen Cole Kleene vorangestellt ist .
  • —, 1951, "Einige grundlegende Theoreme über die Grundlagen der Mathematik und ihre Implikationen", in Solomon Feferman , Hrsg., 1995 . III , Oxford University Press, S. 304–323. ISBN  978-0195147223 .

Zu seinen Lebzeiten Übersetzungen von Gödels Arbeit ins Englische

Keines der folgenden stimmt in allen übersetzten Wörtern und in der Typografie überein. Die Typografie ist eine ernste Angelegenheit, denn Gödel wollte ausdrücklich "die zuvor im üblichen Sinne definierten metamathematischen Begriffe . . ." hervorheben. ( van Heijenoort 1967 , S. 595) . Es existieren drei Übersetzungen. Von dem ersten sagt John Dawson: „Die Meltzer-Übersetzung war ernsthaft mangelhaft und erhielt eine verheerende Kritik im Journal of Symbolic Logic ;“ Gödel beschwerte sich auch über Braithwaites Kommentar ( Dawson 1997 , S. 216). "Glücklicherweise wurde die Meltzer-Übersetzung bald durch eine bessere ersetzt, die Elliott Mendelson für Martin Davis' Anthologie The Undecidable vorbereitet hatte ... er fand die Übersetzung "nicht ganz so gut", wie er erwartet hatte ... ] stimmte seiner Veröffentlichung zu" (ebd.). (In einer Fußnote stellt Dawson fest, dass "er seine Einhaltung bedauern würde, denn der veröffentlichte Band war durchweg durch schlampige Typografie und zahlreiche Druckfehler beeinträchtigt" (ebd.)). Dawson stellt fest, dass „die Übersetzung, die Gödel bevorzugte, die von Jean van Heijenoort war“ (ebd.). Für den ernsthaften Studenten existiert eine andere Version als eine Reihe von Vorlesungsnotizen, die von Stephen Kleene und JB Rosser "während der Vorlesungen von Gödel am Institute for Advanced Study im Frühjahr 1934" aufgezeichnet wurden (vgl. Kommentar von Davis 1965 , S. 39 und ab S. 41); diese Version trägt den Titel "Über unentscheidbare Aussagen formaler mathematischer Systeme". In ihrer Veröffentlichungsreihenfolge:

  • B. Meltzer (Übersetzung) und RB Braithwaite (Einleitung), 1962. On Formally Undecidable Propositions of Principia Mathematica and Related Systems , Dover Publications, New York (Dover Ausgabe 1992), ISBN  0-486-66980-7 (Pbk.) This enthält eine nützliche Übersetzung von Gödels deutschen Abkürzungen auf S. 33–34. Wie oben erwähnt, sind Typografie, Übersetzung und Kommentar verdächtig. Leider wurde diese Übersetzung mit all ihrem verdächtigen Inhalt nachgedruckt von
  • Stephen Hawking Herausgeber, 2005. God Created the Integers: The Mathematical Breakthroughs That Changed History , Running Press, Philadelphia, ISBN  0-7624-1922-9 . Gödels Aufsatz erscheint ab S. 1097, mit Hawkings Kommentar ab S. 1089.
  • Martin Davis Herausgeber, 1965. The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions , Raven Press, New York, keine ISBN. Gödels Aufsatz beginnt auf Seite 5, gefolgt von einer Kommentarseite.
  • Jean van Heijenoort Herausgeber, 1967, 3. Auflage 1967. Von Frege bis Gödel: A Source Book in Mathematical Logic, 1879-1931 , Harvard University Press, Cambridge Mass., ISBN  0-674-32449-8 (pbk). van Heijenoort hat die Übersetzung gemacht. "Professor Gödel hat die Übersetzung genehmigt, die an vielen Stellen seinen Wünschen entsprochen wurde." (S. 595). Gödels Aufsatz beginnt auf S. 595; van Heijenoorts Kommentar beginnt auf S. 592.
  • Martin Davis Herausgeber, 1965, ebenda. "Über unentscheidbare Aussagen formaler mathematischer Systeme." Eine Kopie mit Gödels Korrekturen von Errata und Gödels hinzugefügten Anmerkungen beginnt auf Seite 41, gefolgt von zwei Seiten von Davis' Kommentar. Bis Davis dies in seinen Band aufgenommen hatte, existierte dieser Vortrag nur als vervielfältigte Notizen.

Artikel von anderen

Bücher über die Theoreme

Sonstige Referenzen

Externe Links