Die Unvollständigkeitslehrsätze von Gödel sind zwei Lehrsätze der mathematischen Logik, die innewohnende Beschränkungen von allen außer den meisten trivialen axiomatischen Systemen gründen, die dazu fähig sind, Arithmetik zu tun. Die Lehrsätze, die von Kurt Gödel 1931 bewiesen sind, sind sowohl in der mathematischen Logik als auch in der Philosophie der Mathematik wichtig. Die zwei Ergebnisse sind weit, aber nicht allgemein, interpretiert als Vertretung, dass das Programm von Hilbert, um eine ganze und konsistente Menge von Axiomen für die ganze Mathematik zu finden, unmöglich ist, eine negative Antwort auf das zweite Problem von Hilbert gebend.

Der erste Unvollständigkeitslehrsatz stellt fest, dass kein konsequentes System von Axiomen, deren Lehrsätze durch ein "wirksames Verfahren" verzeichnet werden können (z.B, ein Computerprogramm, aber konnte es jede Sorte des Algorithmus sein), dazu fähig ist, alle Wahrheiten über die Beziehungen der natürlichen Zahlen (Arithmetik) zu beweisen. Für jedes solches System wird es immer Behauptungen über die natürlichen Zahlen geben, die wahr sind, aber die innerhalb des Systems unbeweisbar sind. Der zweite Unvollständigkeitslehrsatz, eine Folgeerscheinung des ersten, zeigt, dass solch ein System seine eigene Konsistenz nicht demonstrieren kann.

Hintergrund

Weil Behauptungen einer formellen Theorie in der symbolischen Form geschrieben werden, ist es möglich mechanisch nachzuprüfen, dass ein formeller Beweis von einem begrenzten Satz von Axiomen gültig ist. Diese Aufgabe, die als automatische Probeüberprüfung bekannt ist, ist nah mit dem automatisierten Lehrsatz-Beweis verbunden. Der Unterschied ist, dass, anstatt einen neuen Beweis zu bauen, der Beweis verifier einfach überprüft, dass ein zur Verfügung gestellter formeller Beweis (oder, in einigen Fällen, Instruktionen, denen gefolgt werden kann, um einen formellen Beweis zu schaffen) richtig ist. Dieser Prozess ist nicht bloß hypothetisch; Systeme wie Isabelle werden heute verwendet, um Beweise zu formalisieren und dann ihre Gültigkeit zu überprüfen.

Viele Theorien von Interesse schließen einen unendlichen Satz von Axiomen jedoch ein. Um einen formellen Beweis nachzuprüfen, wenn der Satz von Axiomen unendlich ist, muss es möglich sein zu bestimmen, ob eine Behauptung, die, wie man fordert, ein Axiom ist, wirklich ein Axiom ist. Dieses Problem entsteht in den ersten Ordnungstheorien der Arithmetik wie Arithmetik von Peano, weil der Grundsatz der mathematischen Induktion als ein unendlicher Satz von Axiomen (ein Axiom-Diagramm) ausgedrückt wird.

Wie man

sagt, wird eine formelle Theorie effektiv erzeugt, wenn sein Satz von Axiomen rekursiv enumerable Satz ist. Das bedeutet, dass es ein Computerprogramm gibt, das im Prinzip alle Axiome der Theorie aufzählen konnte, ohne irgendwelche Behauptungen zu verzeichnen, die nicht Axiome sind. Das ist zur Existenz eines Programms gleichwertig, das alle Lehrsätze der Theorie aufzählt, ohne irgendwelche Behauptungen aufzuzählen, die nicht Lehrsätze sind. Beispiele effektiv erzeugter Theorien mit unendlichen Sätzen von Axiomen schließen Arithmetik von Peano und Zermelo-Fraenkel Mengenlehre ein.

In der Auswahl einer Reihe von Axiomen ist eine Absicht im Stande zu sein, so viele richtige Ergebnisse wie möglich zu beweisen, ohne irgendwelche falschen Ergebnisse zu beweisen. Eine Reihe von Axiomen ist abgeschlossen, wenn, für Behauptung auf der Sprache der Axiome, entweder diese Behauptung oder seine Ablehnung von den Axiomen nachweisbar sind. Eine Reihe von Axiomen ist (einfach) konsequent, wenn es keine solche Behauptung gibt, dass sowohl die Behauptung als auch seine Ablehnung von den Axiomen nachweisbar sind. Im Standardsystem der Logik der ersten Ordnung wird ein inkonsequenter Satz von Axiomen jede Behauptung auf seiner Sprache beweisen (das wird manchmal den Grundsatz der Explosion genannt), und ist so automatisch abgeschlossen. Eine Reihe von Axiomen, der sowohl abgeschlossen als auch jedoch konsequent ist, beweist einen maximalen Satz von nichtwidersprechenden Lehrsätzen. Die Unvollständigkeitslehrsätze von Gödel zeigen, dass in bestimmten Fällen es nicht möglich ist, eine effektiv erzeugte, ganze, konsequente Theorie zu erhalten.

Der erste Unvollständigkeitslehrsatz

Der erste Unvollständigkeitslehrsatz von Gödel stellt dass fest:

: Jede effektiv erzeugte Theorie, die dazu fähig ist, elementare Arithmetik auszudrücken, kann nicht sowohl konsequent als auch abgeschlossen sein. Insbesondere für jedes konsequente effektiv erzeugte formelle Theorie, die bestimmte grundlegende arithmetische Wahrheiten beweist, gibt es eine arithmetische Behauptung, die wahr, aber in der Theorie nicht nachweisbar ist (Kleene 1967, p. 250).

Die wahre, aber unbeweisbare Behauptung, die auf durch den Lehrsatz verwiesen ist, wird häufig "den Satz von Gödel" für die Theorie genannt. Der Beweis baut einen spezifischen Satz von Gödel für jede effektiv erzeugte Theorie, aber es gibt ungeheuer viele Behauptungen auf der Sprache der Theorie, die das Eigentum teilen, wahr, aber unbeweisbar zu sein. Zum Beispiel wird die Verbindung des Satzes von Gödel und jedes logisch gültigen Satzes dieses Eigentum haben.

Für jede konsequente formelle Theorie T, die den erforderlichen kleinen Betrag der Zahlentheorie hat, verurteilen entsprechende Gödel G behauptet:" G kann innerhalb der Theorie T nicht bewiesen werden". Diese Interpretation von G führt zur folgenden informellen Analyse. Wenn G unter den Axiomen und Regeln der Schlussfolgerung von T nachweisbar wären, dann würde T einen Lehrsatz, G haben, der sich effektiv widerspricht, und so die Theorie T inkonsequent sein würde. Das bedeutet, dass, wenn die Theorie T dann entspricht, G innerhalb ihrer nicht bewiesen werden kann, und so ist die Theorie T unvollständig. Außerdem macht die Forderung G über seinen eigenen unprovability ist richtig. In diesem Sinn ist G nicht nur unbeweisbar, aber wahr, und provability innerhalb der Theorie T ist nicht dasselbe als Wahrheit. Diese informelle Analyse kann formalisiert werden, um einen strengen Beweis des Unvollständigkeitslehrsatzes, wie beschrieben, in der Abteilung "Probeskizze für den ersten Lehrsatz" unten zu machen. Der formelle Beweis offenbart genau die Hypothesen, die für die Theorie T in der Größenordnung von der widersprüchlichen Natur von G erforderlich sind, zu einem echten Widerspruch zu führen.

Jede effektiv erzeugte Theorie hat seine eigene Behauptung von Gödel. Es ist möglich, eine größere Theorie T zu definieren', die ganzen T plus G als ein zusätzliches Axiom enthält. Das wird auf keine ganze Theorie hinauslaufen, weil der Lehrsatz von Gödel auch für T gelten wird', und so T' nicht abgeschlossen sein kann. In diesem Fall ist G tatsächlich ein Lehrsatz in T', weil es ein Axiom ist. Da G nur feststellt, dass es in T nicht nachweisbar ist, wird kein Widerspruch durch seinen provability in T präsentiert'. Jedoch, weil der Unvollständigkeitslehrsatz für T gilt': Es wird eine neue Behauptung G von Gödel' für T geben', zeigend, dass T' auch unvollständig ist. G' wird sich von G unterscheiden, in dem sich G' auf T', aber nicht T beziehen wird.

Um den ersten Unvollständigkeitslehrsatz zu beweisen, hat Gödel Behauptungen durch Zahlen vertreten. Dann beweist die Theorie in der Nähe, die, wie man annimmt, bestimmte Tatsachen über Zahlen beweist, auch Tatsachen über seine eigenen Behauptungen, vorausgesetzt, dass sie effektiv erzeugt wird. Fragen über den provability von Behauptungen werden als Fragen über die Eigenschaften von Zahlen vertreten, die durch die Theorie entscheidbar sein würden, wenn es abgeschlossen wäre. In diesen Begriffen stellt der Satz von Gödel fest, dass keine natürliche Zahl mit einem bestimmten, fremden Eigentum besteht. Eine Zahl mit diesem Eigentum würde einen Beweis der Widersprüchlichkeit der Theorie verschlüsseln. Wenn es solch eine Zahl dann gäbe, würde die Theorie gegen die Konsistenz-Hypothese inkonsequent sein. Also, unter der Annahme, dass die Theorie entspricht, gibt es keine solche Zahl.

Bedeutung des ersten Unvollständigkeitslehrsatzes

Der erste Unvollständigkeitslehrsatz von Gödel zeigt, dass jedes konsequente wirksame formelle System, das genug von der Theorie der natürlichen Zahlen einschließt, unvollständig ist: Es gibt wahre Behauptungen expressible auf seiner Sprache, die unbeweisbar sind. So kann kein formelles System (die Hypothesen des Lehrsatzes befriedigend), der zum Ziel hat, die natürlichen Zahlen zu charakterisieren, wirklich so tun, weil es wahre mit der Zahl theoretische Behauptungen geben wird, die dieses System nicht beweisen kann. Wie man manchmal denkt, hat diese Tatsache strenge Folgen für das Programm von logicism, der von Gottlob Frege und Bertrand Russell vorgeschlagen ist, der zum Ziel gehabt hat, die natürlichen Zahlen in Bezug auf die Logik zu definieren (Hellman 1981, p. 451-468). Einige (wie Bob Hale und Crispin Wright) behaupten, dass es nicht ein Problem für logicism ist, weil die Unvollständigkeitslehrsätze ebenso für die zweite Ordnungslogik gelten, wie sie zur Arithmetik tun. Sie behaupten, dass nur diejenigen, die glauben, dass die natürlichen Zahlen in Bezug auf die erste Ordnungslogik definiert werden sollen, dieses Problem haben.

Die Existenz eines unvollständigen formellen Systems ist an sich nicht besonders überraschend. Ein System kann einfach unvollständig sein, weil nicht alle notwendigen Axiome entdeckt worden sind. Zum Beispiel ist die Euklidische Geometrie ohne das parallele Postulat unvollständig; es ist nicht möglich, das parallele Postulat von den restlichen Axiomen zu beweisen oder zu widerlegen.

Der Lehrsatz von Gödel zeigt, dass in Theorien, die einen kleinen Teil der Zahlentheorie einschließen, eine ganze und konsequente begrenzte Liste von Axiomen, noch sogar eine unendliche Liste nie geschaffen werden kann, die durch ein Computerprogramm aufgezählt werden kann. Jedes Mal, wenn eine neue Behauptung als ein Axiom hinzugefügt wird, gibt es andere wahre Behauptungen, die noch sogar mit dem neuen Axiom nicht bewiesen werden können. Wenn ein Axiom jemals hinzugefügt wird, der das System abgeschlossen macht, tut es so auf Kosten des Bildens des inkonsequenten Systems.

Es gibt ganze und konsequente Liste von Axiomen für die Arithmetik, die durch ein Computerprogramm nicht aufgezählt werden kann. Zum Beispiel könnte man alle wahren Behauptungen über die natürlichen Zahlen nehmen, um Axiome zu sein (und keine falschen Angaben), der die als "wahre Arithmetik bekannte Theorie" gibt. Die Schwierigkeit besteht darin, dass es keine mechanische Weise gibt, in Anbetracht einer Behauptung über die natürlichen Zahlen zu entscheiden, ob es ein Axiom dieser Theorie ist, und so es keine wirksame Weise gibt, einen formellen Beweis in dieser Theorie nachzuprüfen.

Viele Logiker glauben, dass die Unvollständigkeitslehrsätze von Gödel einen Todesstoß zum zweiten Problem von David Hilbert geschlagen haben, das um einen finitary Konsistenz-Beweis um die Mathematik gebeten hat. Der zweite Unvollständigkeitslehrsatz wird häufig insbesondere als das Bilden des unmöglichen Problems angesehen. Nicht alle Mathematiker stimmen mit dieser Analyse jedoch überein, und der Status des zweiten Problems von Hilbert wird noch nicht entschieden (sieh "Moderne Gesichtspunkte auf dem Status des Problems").

Beziehung zum Lügner-Paradox

Das Lügner-Paradox ist der Satz "Dieser Satz ist falsch." Eine Analyse des Lügner-Satzes zeigt, dass es nicht wahr sein kann (für dann, wie es behauptet, ist es falsch), noch es kann falsch sein (für dann, es ist wahr). Ein Gödel-Satz-G für eine Theorie T macht eine ähnliche Behauptung zum Lügner-Satz, aber mit der durch provability ersetzten Wahrheit: G sagt "G ist in der Theorie nicht nachweisbar T." Die Analyse der Wahrheit und provability von G ist eine formalisierte Version der Analyse der Wahrheit des Lügner-Satzes.

Es ist nicht möglich, "nicht nachweisbar" durch "den falschen" in einem Satz von Gödel zu ersetzen, weil das Prädikat "Q die Zahl von Gödel einer falschen Formel ist", kann als eine Formel der Arithmetik nicht vertreten werden. Dieses Ergebnis, das als der undefinability Lehrsatz von Tarski bekannt ist, wurde unabhängig von Gödel entdeckt (als er am Beweis des Unvollständigkeitslehrsatzes arbeitete), und durch Alfred Tarski.

Ursprüngliche Behauptungen

Der erste Unvollständigkeitslehrsatz ist zuerst als "Lehrsatz VI" in der 1931-Zeitung von Gödel Auf Formell Unentscheidbaren Vorschlägen in Principia Mathematica und Related Systems I erschienen. Der zweite Unvollständigkeitslehrsatz ist als "Lehrsatz XI" in derselben Zeitung erschienen.

Erweiterungen des ursprünglichen Ergebnisses von Gödel

Gödel hat die Unvollständigkeit der Theorie von Principia Mathematica, einer besonderen Theorie der Arithmetik demonstriert, aber eine parallele Demonstration konnte für jede wirksame Theorie eines bestimmten Ausdrucksvollen gegeben werden. Gödel hat sich über diese Tatsache in der Einführung in sein Papier geäußert, aber hat den Beweis auf ein System für die Greifbarkeit eingeschränkt. In modernen Behauptungen des Lehrsatzes ist es üblich, die Wirksamkeit und Ausdrucksvoll-Bedingungen als Hypothesen für den Unvollständigkeitslehrsatz festzusetzen, so dass es auf keine besondere formelle Theorie beschränkt wird. Die Fachsprache, die verwendet ist, um diese Bedingungen festzusetzen, wurde 1931 noch nicht entwickelt, als Gödel seine Ergebnisse veröffentlicht hat.

Die ursprüngliche Behauptung von Gödel und Beweis des Unvollständigkeitslehrsatzes verlangen die Annahme, dass die Theorie nicht nur, aber ω-consistent entspricht. Eine Theorie ist ω-consistent, wenn es nicht ω-inconsistent ist, und ω-inconsistent ist, wenn es ein Prädikat P solch gibt, dass für jede spezifische natürliche Zahl n die Theorie ~P (n) beweist, und noch die Theorie auch beweist, dass dort eine natürliche Zahl n solch dass P (n) besteht. D. h. die Theorie sagt, dass eine Zahl mit dem Eigentum P besteht, während sie bestreitet, dass es jeden spezifischen Wert hat. Der ω-consistency einer Theorie bezieht seine Konsistenz ein, aber Konsistenz bezieht ω-consistency nicht ein. J. Barkley Rosser (1936) hat den Unvollständigkeitslehrsatz gestärkt, indem er eine Schwankung des Beweises gefunden hat (der Trick von Rosser), der nur die Theorie verlangt, aber nicht ω-consistent zu entsprechen. Das ist größtenteils vom technischen Interesse seit allen wahren formellen Theorien der Arithmetik (Theorien, deren Axiome alle wahren Behauptungen über natürliche Zahlen sind), sind ω-consistent, und so gilt der Lehrsatz von Gödel, wie ursprünglich festgesetzt, für sie. Die stärkere Version des Unvollständigkeitslehrsatzes, der nur Konsistenz, aber nicht ω-consistency annimmt, ist jetzt als der Unvollständigkeitslehrsatz von Gödel und als der Gödel-Rosser Lehrsatz allgemein bekannt.

Der zweite Unvollständigkeitslehrsatz

Der zweite Unvollständigkeitslehrsatz von Gödel kann wie folgt festgesetzt werden:

: Für jede formelle effektiv erzeugte Theorie T einschließlich grundlegender arithmetischer Wahrheiten und sind auch bestimmte Wahrheiten über formellen provability, wenn T eine Behauptung seiner eigenen Konsistenz dann T einschließt, inkonsequent.

Das stärkt den ersten Unvollständigkeitslehrsatz, weil die im ersten Unvollständigkeitslehrsatz gebaute Behauptung nicht direkt ausdrücklich die Konsistenz der Theorie tut. Der Beweis des zweiten Unvollständigkeitslehrsatzes wird durch das Formalisieren des Beweises des ersten Unvollständigkeitslehrsatzes innerhalb der Theorie selbst erhalten.

Eine technische Subtilität im zweiten Unvollständigkeitslehrsatz ist, wie man die Konsistenz von T als eine Formel auf der Sprache von T ausdrückt. Es gibt viele Weisen, das zu tun, und nicht sie alle führen zu demselben Ergebnis. Insbesondere verschiedene Formalisierungen des Anspruchs, dass T entspricht, können inequivalent in T sein, und einige können sogar nachweisbar sein. Zum Beispiel kann Arithmetik von Peano (PA) der ersten Ordnung beweisen, dass die größte konsequente Teilmenge des PAPAS entspricht. Aber da PAPA entspricht, ist die größte konsequente Teilmenge des PAPAS gerade PAPA, so in diesem Sinn-PAPA "beweist, dass sie entspricht". Was PAPA nicht beweist, ist, dass die größte konsequente Teilmenge des PAPAS, tatsächlich, ganzer PAPA ist. (Der Begriff "größte konsequente Teilmenge des PAPAS" ist technisch zweideutig, aber was gemeint wird, ist hier das größte konsequente anfängliche Segment der Axiome des gemäß einigen Kriterien befohlenen PAPAS; zum Beispiel, durch "Zahlen von Gödel", die Zahlen, die die Axiome laut des Schemas verschlüsseln, das von Gödel verwendet ist, der oben erwähnt ist).

Für die Peano Arithmetik oder irgendwelchen vertraut ausführlich axiomatized Theorie T ist es möglich, eine Formel Con (T) das Ausdrücken der Konsistenz von T kanonisch zu definieren; diese Formel drückt das Eigentum aus, dass "dort keine natürliche Zahl besteht, die eine Folge von Formeln, solch codiert, dass jede Formel entweder der Axiome von T, eines logischen Axioms oder einer unmittelbaren Folge ist, Formeln ordnungsmäßig der Schlussfolgerung der Logik der ersten Ordnung, und solch voranzugehen, dass die letzte Formel ein Widerspruch ist".

Die Formalisierung von Con (T) hängt von zwei Faktoren ab: Das Formalisieren des Begriffs eines Satzes, der von einer Reihe von Sätzen ableitbar ist und den Begriff formalisiert, ein Axiom von T zu sein. Das Formalisieren derivability kann auf die kanonische Mode getan werden: In Anbetracht einer arithmetischen Formel (x) das Definieren einer Reihe von Axiomen kann man ein Prädikat Prov (P) kanonisch bilden, der ausdrückt, dass P vom Satz von Axiomen nachweisbar ist, die durch (x) definiert sind.

Außerdem nimmt der Standardbeweis des zweiten Unvollständigkeitslehrsatzes an, dass Prov (P) diesen Hilbert-Bernays provability Bedingungen befriedigt. Das Lassen # (P) vertritt die Zahl von Gödel einer Formel P, die derivability Bedingungen sagen:

1. Wenn T P beweist, dann beweist T Prov (# (P)).
2. T erweist sich 1.; d. h. T beweist dass, wenn T P beweist, dann beweist T Prov (# (P)). Mit anderen Worten beweist T, dass Prov (# (P)) Prov (# (Prov (# (P)))) einbezieht.
3. T beweist, dass, wenn T beweist, dass (P  Q) und T P dann beweist, T Q beweist. Mit anderen Worten beweist T, dass Prov (# (P  Q)) und Prov (# (P)) Prov (# (Q)) einbeziehen.

Implikationen für Konsistenz-Beweise

Der zweite Unvollständigkeitslehrsatz von Gödel deutet auch an, dass eine Theorie T, die die technischen Bedingungen befriedigt, die oben entworfen sind, die Konsistenz keiner Theorie T beweisen kann, die die Konsistenz von T beweist. Das ist, weil solch eine Theorie T dass beweisen kann, wenn T die Konsistenz von T beweist, dann entspricht T tatsächlich. Für den Anspruch, dass T entspricht, hat Form "für alle Nummern n, n hat das entscheidbare Eigentum, ein Code für einen Beweis des Widerspruchs in T nicht zu sein". Wenn T tatsächlich inkonsequent wären, dann würde T für einen n beweisen, dass n der Code eines Widerspruchs in T ist. Aber wenn T auch bewiese, dass T entspricht (d. h. dass es keinen solchen n gibt), dann würde es selbst inkonsequent sein. Dieses Denken kann in T formalisiert werden, um dass zu zeigen, wenn T entspricht, dann entspricht T. Seitdem, durch den zweiten Unvollständigkeitslehrsatz, beweist T seine Konsistenz nicht, es kann die Konsistenz von T auch nicht beweisen.

Diese Folgeerscheinung des zweiten Unvollständigkeitslehrsatzes zeigt, dass es keine Hoffnung auf den Beweis, zum Beispiel, die Konsistenz der Arithmetik von Peano gibt, die irgendwelche Finitistic-Mittel verwendet, die in einer Theorie formalisiert werden können, deren Konsistenz in der Arithmetik von Peano nachweisbar ist. Zum Beispiel entspricht die Theorie der primitiven rekursiven Arithmetik (PRA), die als eine genaue Formalisierung der finitistic Mathematik weit akzeptiert wird, nachweisbar im PAPA. So kann PRA nicht die Konsistenz des PAPAS beweisen. Wie man allgemein sieht, deutet diese Tatsache an, dass das Programm von Hilbert, das zum Ziel gehabt hat, den Gebrauch "des Ideales" (infinitistic) mathematische Grundsätze in den Beweisen von "echten" (finitistic) mathematischen Behauptungen durch das Geben eines finitistic Beweises zu rechtfertigen, dass die idealen Grundsätze entsprechen, nicht ausgeführt werden kann.

Die Folgeerscheinung zeigt auch die erkenntnistheoretische Relevanz des zweiten Unvollständigkeitslehrsatzes an. Es würde wirklich keine interessante Auskunft geben, wenn eine Theorie T seine Konsistenz bewiese. Das ist, weil inkonsequente Theorien alles einschließlich ihrer Konsistenz beweisen. So würde ein Konsistenz-Beweis von T in T uns keinen Hinweis betreffs geben, ob T wirklich entspricht; keine Zweifel über die Konsistenz von T würden durch solch einen Konsistenz-Beweis aufgelöst. Das Interesse an Konsistenz-Beweisen liegt in der Möglichkeit, die Konsistenz einer Theorie T in einer Theorie T zu beweisen', die in einem Sinn ist, der weniger zweifelhaft ist als T selbst zum Beispiel schwächer als T. Für viele natürlich vorkommende Theorien T und T', wie T = Zermelo-Fraenkel Mengenlehre und T' = primitive rekursive Arithmetik, ist die Konsistenz von T' in T nachweisbar, und so T' kann die Konsistenz von T durch die obengenannte Folgeerscheinung des zweiten Unvollständigkeitslehrsatzes nicht beweisen.

Der zweite Unvollständigkeitslehrsatz schließt Konsistenz-Beweise zusammen, nur Konsistenz-Beweise nicht aus, die in der Theorie formalisiert werden konnten, die konsequent bewiesen wird. Zum Beispiel hat Gerhard Gentzen die Konsistenz der Arithmetik von Peano (PA) in einer verschiedenen Theorie bewiesen, die ein Axiom einschließt behauptend, dass die Ordnungszahl gerufen hat, ist ε wohl begründet; sieh den Konsistenz-Beweis von Gentzen. Der Lehrsatz von Gentzen hat die Entwicklung der Ordnungsanalyse in der Probetheorie gespornt.

Beispiele von unentscheidbaren Behauptungen

Es gibt zwei verschiedene Bedeutungen des Wortes, die in der Mathematik und Informatik "unentscheidbar" sind. Der erste von diesen ist der probetheoretische Sinn, der in Bezug auf die Lehrsätze von Gödel, diese einer Behauptung verwendet ist, die ist weder nachweisbar ist noch in einem angegebenen deduktiven System widerlegbar ist. Der zweite Sinn, der hier nicht besprochen wird, wird in Bezug auf die Berechenbarkeitstheorie verwendet und gilt nicht für Behauptungen, aber für Entscheidungsprobleme, die zählbar unendliche Reihen von Fragen jedes Verlangen ja oder keine Antwort sind. Wie man sagt, ist solch ein Problem unentscheidbar, wenn es keine berechenbare Funktion gibt, die richtig auf jede Frage im Problem-Satz antwortet (sieh unentscheidbares Problem).

Wegen der zwei Bedeutungen des unentscheidbaren Wortes wird der unabhängige Begriff manchmal statt des unentscheidbaren für "weder nachweisbarer noch widerlegbarer" Sinn gebraucht. Der Gebrauch von "unabhängigen" ist auch jedoch zweideutig. Etwas Gebrauch es, um gerade "nicht nachweisbar" zu bedeuten, offen lassend, ob eine unabhängige Behauptung widerlegt werden könnte.

Die Unentscheidbarkeit einer Behauptung in einem besonderen deduktiven System tut nicht, in und von sich, richtet die Frage dessen, ob der Wahrheitswert der Behauptung bestimmt ist, oder ob es durch andere Mittel bestimmt werden kann. Unentscheidbarkeit deutet nur an, dass das besondere deduktive System, das wird betrachtet, die Wahrheit oder Unehrlichkeit der Behauptung nicht beweist. Ob dort so genannte "absolut unentscheidbare" Behauptungen bestehen, deren Wahrheitswert nie bekannt sein kann oder schlecht-angegeben wird, ist ein umstrittener Punkt in der Philosophie der Mathematik.

Die vereinigte Arbeit von Gödel und Paul Cohen hat zwei konkrete Beispiele von unentscheidbaren Behauptungen (in der ersten Bedeutung des Terminus) angeführt: Die Kontinuum-Hypothese kann weder bewiesen noch in ZFC (der Standard axiomatization der Mengenlehre) widerlegt werden, und das Axiom der Wahl kann weder bewiesen noch in ZF widerlegt werden (der alle ZFC Axiome außer dem Axiom der Wahl ist). Diese Ergebnisse verlangen den Unvollständigkeitslehrsatz nicht. Gödel hat 1940 bewiesen, dass keine dieser Behauptungen in ZF oder ZFC Mengenlehre widerlegt werden konnte. In den 1960er Jahren hat Cohen bewiesen, dass keiner von ZF nachweisbar ist, und die Kontinuum-Hypothese von ZFC nicht bewiesen werden kann.

1973, wie man zeigte, war das Problem von Whitehead in der Gruppentheorie in der ersten Bedeutung des Terminus in der Standardsatz-Theorie unentscheidbar.

1977 hat Paris und Harrington bewiesen, dass der Grundsatz des Paris-Harrington, eine Version des Lehrsatzes von Ramsey, in der ersten Ordnung axiomatization von der Arithmetik genannt die Arithmetik von Peano unentscheidbar ist, aber im größeren System der Arithmetik der zweiten Ordnung bewiesen werden kann. Kirby und Paris hat später den Lehrsatz von Goodstein, eine Behauptung über Folgen von natürlichen Zahlen gezeigt, die etwas einfacher sind als der Grundsatz des Paris-Harrington, um in der Arithmetik von Peano unentscheidbar zu sein.

Der Baumlehrsatz von Kruskal, der Anwendungen in der Informatik hat, ist auch von der Arithmetik von Peano unentscheidbar, aber in der Mengenlehre nachweisbar. Tatsächlich ist der Baumlehrsatz von Kruskal (oder seine begrenzte Form) in einem viel stärkeren System unentscheidbar, das die Grundsätze annehmbar gestützt auf einer Philosophie genannten predicativism der Mathematik kodifiziert. Der zusammenhängende, aber allgemeinere Graph geringer Lehrsatz (2003) hat Folgen für die rechenbetonte Kompliziertheitstheorie.

Gregory Chaitin hat unentscheidbare Behauptungen in der algorithmischen Informationstheorie erzeugt und hat einen anderen Unvollständigkeitslehrsatz in dieser Einstellung bewiesen. Der Unvollständigkeitslehrsatz von Chaitin stellt fest, dass für jede Theorie, die genug Arithmetik vertreten kann, es einen oberen gebundenen solchen c gibt, dass keine spezifische Zahl in dieser Theorie bewiesen werden kann, Kompliziertheit von Kolmogorov zu haben, die größer ist als c. Während der Lehrsatz von Gödel mit dem Lügner-Paradox verbunden ist, ist das Ergebnis von Chaitin mit dem Paradox von Berry verbunden.

Beschränkungen der Lehrsätze von Gödel

Die Beschlüsse der Lehrsätze von Gödel werden nur für die formellen Theorien bewiesen, die die notwendigen Hypothesen befriedigen. Nicht alle Axiom-Systeme befriedigen diese Hypothesen, selbst wenn diese Systeme Modelle haben, die die natürlichen Zahlen als eine Teilmenge einschließen. Zum Beispiel gibt es erste Ordnung axiomatizations der Euklidischen Geometrie, echter geschlossener Felder, und der Arithmetik, in der Multiplikation nicht nachweisbar ganz ist; keiner von diesen entspricht die Hypothesen der Lehrsätze von Gödel. Die Schlüsseltatsache ist, dass diese axiomatizations nicht ausdrucksvoll genug sind, um den Satz von natürlichen Zahlen zu definieren oder grundlegende Eigenschaften der natürlichen Zahlen zu entwickeln. Bezüglich des dritten Beispiels hat Dan E. Willard (Willard 2001) viele schwache Systeme der Arithmetik studiert, die die Hypothesen des zweiten Unvollständigkeitslehrsatzes nicht befriedigen, und die entsprechen und dazu fähig sind, ihre eigene Konsistenz zu beweisen (sieh Selbstüberprüfen-Theorien).

Die Lehrsätze von Gödel gelten nur für effektiv erzeugten (d. h. rekursiv enumerable) Theorien. Wenn alle wahren Behauptungen über natürliche Zahlen als Axiome für eine Theorie genommen werden, dann ist diese Theorie eine konsequente, ganze Erweiterung der Arithmetik von Peano (hat wahre Arithmetik genannt), wegen dessen keiner der Lehrsätze von Gödel auf eine bedeutungsvolle Weise gilt, weil diese Theorie nicht rekursiv enumerable ist.

Der zweite Unvollständigkeitslehrsatz zeigt nur, dass die Konsistenz von bestimmten Theorien von den Axiomen jener Theorien selbst nicht bewiesen werden kann. Es zeigt nicht, dass die Konsistenz von anderen (konsequenten) Axiomen nicht bewiesen werden kann. Zum Beispiel kann die Konsistenz der Arithmetik von Peano in der Zermelo-Fraenkel Mengenlehre (ZFC), oder in Theorien der Arithmetik bewiesen werden, die mit der transfiniten Induktion, als im Konsistenz-Beweis von Gentzen vermehrt ist.

Beziehung mit der Berechenbarkeit

Der Unvollständigkeitslehrsatz ist nah mit mehreren Ergebnissen über unentscheidbare Sätze in der recursion Theorie verbunden.

Stephen Cole Kleene (1943) hat einen Beweis des Unvollständigkeitslehrsatzes von Gödel mit grundlegenden Ergebnissen der Berechenbarkeitstheorie präsentiert. Ein solches Ergebnis zeigt, dass das stockende Problem unentscheidbar ist: Es gibt kein Computerprogramm, das in Anbetracht eines Programms P, wie eingegeben, richtig bestimmen kann, ob P schließlich, wenn geführt, mit einem gegebenen Eingang hinkt. Kleene hat gezeigt, dass die Existenz einer ganzen wirksamen Theorie der Arithmetik mit bestimmten Konsistenz-Eigenschaften das stockende Problem zwingen würde, ein Widerspruch entscheidbar zu sein. Diese Methode des Beweises ist auch von Shoenfield vorgelegt worden (1967, p. 132); Charlesworth (1980); und Hopcroft und Ullman (1979).

Franzén (2005, p. 73) erklärt, wie die Lösung von Matiyasevich des 10. Problems von Hilbert verwendet werden kann, um einen Beweis zum ersten Unvollständigkeitslehrsatz von Gödel zu erhalten. Matiyasevich hat bewiesen, dass es keinen Algorithmus gibt, dass, in Anbetracht eines multivariate Polynoms p (x, x..., x) mit Koeffizienten der ganzen Zahl, bestimmt, ob es eine Lösung der ganzen Zahl der Gleichung p = 0 gibt. Weil Polynome mit Koeffizienten der ganzen Zahl und ganze Zahlen selbst, direkt expressible auf der Sprache der Arithmetik sind, wenn eine multivariate Polynom-Gleichung der ganzen Zahl p = 0 wirklich eine Lösung in den ganzen Zahlen dann hat, wird jede genug starke Theorie der Arithmetik T das beweisen. Außerdem, wenn die Theorie T ω-consistent ist, dann wird es nie beweisen, dass eine polynomische Gleichung eine Lösung wenn tatsächlich hat, gibt es keine Lösung in den ganzen Zahlen. So, wenn T abgeschlossen wären und ω-consistent, würde es möglich sein, algorithmisch zu bestimmen, ob eine polynomische Gleichung eine Lösung durch das bloße Aufzählen von Beweisen von T hat, bis entweder "p eine Lösung" oder "p hat, hat keine Lösung" wird im Widerspruch zum Lehrsatz von Matiyasevich gefunden. Außerdem, für jede konsequente effektiv erzeugte Theorie T, ist es möglich, ein multivariate Polynom p über die solche ganzen Zahlen effektiv zu erzeugen, dass die Gleichung p = 0 keine Lösungen über die ganzen Zahlen hat, aber der Mangel an Lösungen kann in T (Davis 2006:416, Jones 1980) nicht bewiesen werden.

Smorynski (1977, p. 842) zeigt, wie die Existenz rekursiv untrennbarer Sätze verwendet werden kann, um den ersten Unvollständigkeitslehrsatz zu beweisen. Dieser Beweis wird häufig erweitert, um zu zeigen, dass Systeme wie Arithmetik von Peano im Wesentlichen unentscheidbar sind (sieh Kleene 1967, p. 274).

Der Unvollständigkeitslehrsatz von Chaitin gibt eine verschiedene Methode, unabhängige Sätze zu erzeugen, die auf der Kompliziertheit von Kolmogorov gestützt sind. Wie der Beweis, der von Kleene präsentiert ist, der oben erwähnt wurde, gilt der Lehrsatz von Chaitin nur für Theorien mit dem zusätzlichen Eigentum, dass alle ihre Axiome im Standardmodell der natürlichen Zahlen wahr sind. Der Unvollständigkeitslehrsatz von Gödel ist durch seine Anwendbarkeit auf konsequente Theorien bemerkenswert, die dennoch Behauptungen einschließen, die im Standardmodell falsch sind; diese Theorien sind als ω-inconsistent bekannt.

Probeskizze für den ersten Lehrsatz

Der Beweis durch den Widerspruch hat drei wesentliche Teile. Um zu beginnen, wählen Sie ein formelles System, das den vorgeschlagenen Kriterien entspricht:

1. Behauptungen im System können durch natürliche Zahlen (bekannt als Zahlen von Gödel) vertreten werden. Die Bedeutung davon besteht darin, dass Eigenschaften von Behauptungen — wie ihre Wahrheit und Lüge — zur Bestimmung gleichwertig sein werden, ob ihre Zahlen von Gödel bestimmte Eigenschaften und das haben, können Eigenschaften der Behauptungen deshalb durch das Überprüfen ihrer Zahlen von Gödel demonstriert werden. Dieser Teil kulminiert im Aufbau einer Formel, die die Idee ausdrückt, dass "Behauptung S im System" nachweisbar ist (der auf jede Behauptung "S" im System angewandt werden kann).
2. Im formellen System ist es möglich, eine Zahl zu bauen, deren Zusammenbringen der Behauptung, wenn interpretiert, Selbstverweisungs-ist und im Wesentlichen sagt, dass es (d. h. die Behauptung selbst) unbeweisbar ist. Das wird mit genanntem "diagonalization" einer Technik (so genannt wegen seiner Ursprünge als das diagonale Argument des Kantoren) getan.
3. Innerhalb des formellen Systems erlaubt diese Behauptung eine Demonstration, dass es weder nachweisbar noch im System widerlegbar ist, und deshalb das System ω-consistent nicht tatsächlich sein kann. Folglich ist die ursprüngliche Annahme, dass das vorgeschlagene System den Kriterien entsprochen hat, falsch.

Arithmetization der Syntax

Das Hauptproblem darin, den Beweis mit Fleisch zu versehen, der oben beschrieben ist, besteht darin, dass es zuerst scheint, dass, eine Behauptung p zu bauen, die zu "p gleichwertig ist, nicht bewiesen werden kann" würde p irgendwie eine Verweisung auf p enthalten müssen, der eine unendliche Rückwärtsbewegung leicht verursachen konnte. Die geniale Technik von Gödel soll zeigen, dass Behauptungen mit Zahlen verglichen werden können (häufig hat den arithmetization der Syntax genannt) auf solche Art und Weise, dass "der Beweis einer Behauptung" durch die "Prüfung ersetzt werden kann, ob eine Zahl ein gegebenes Eigentum hat". Das erlaubt einer Selbstverweisungsformel, in einem Weg gebaut zu werden, der jede unendliche Rückwärtsbewegung von Definitionen vermeidet. Dieselbe Technik wurde später von Alan Turing in seiner Arbeit an Entscheidungsproblem verwendet.

In einfachen Begriffen kann eine Methode ausgedacht werden, so dass jede Formel oder Behauptung, die im System formuliert werden kann, eine einzigartige Zahl, genannt seine Zahl von Gödel auf solche Art und Weise bekommen, dass es möglich ist, sich hin und her zwischen Formeln und Zahlen von Gödel mechanisch umzuwandeln. Die beteiligten Zahlen könnten tatsächlich sehr lang sein (in Bezug auf die Zahl von Ziffern), aber das ist nicht eine Barriere; alles, was Sachen sind, dass solche Zahlen gebaut werden können. Ein einfaches Beispiel ist der Weg, auf den Englisch als eine Folge von Zahlen im Computerverwenden ASCII oder Unicode versorgt wird:

:* Das Wort wird durch 72-69-76-76-79 Verwenden-Dezimalzahl ASCII, d. h. die Nummer 7269767679 vertreten.

:* Die logische Behauptung wird durch 120-061-121-032-061-062-032-121-061-120 verwendende Oktal-ASCII, d. h. die Nummer 120061121032061062032121061120 vertreten.

Im Prinzip, wie man zeigen kann, ist der Beweis einer Behauptung wahr oder falsch zum Beweis gleichwertig, dass die Zahl, die die Behauptung vergleicht, tut oder kein gegebenes Eigentum hat. Weil das formelle System stark genug ist, um das Denken über Zahlen im Allgemeinen zu unterstützen, kann es das Denken über Zahlen unterstützen, die Formeln und Behauptungen ebenso vertreten. Entscheidend, weil das System das Denken über Eigenschaften von Zahlen unterstützen kann, sind die Ergebnisse zum Denken über provability ihrer gleichwertigen Behauptungen gleichwertig.

Aufbau einer Behauptung über "provability"

Gezeigt, dass im Prinzip das System Erklärungen über provability, durch das Analysieren von Eigenschaften jener Zahlen indirekt abgeben kann, die Behauptungen vertreten, die es jetzt möglich ist zu zeigen, wie man eine Behauptung schafft, die wirklich das tut.

Eine Formel F (x), die genau eine freie Variable x enthält, wird eine Behauptungsform oder Klassenzeichen genannt. Sobald x durch eine spezifische Zahl ersetzt wird, verwandelt sich die Behauptungsform in eine ehrliche Behauptung, und es ist dann im System entweder nachweisbar, oder nicht. Für bestimmte Formeln kann man zeigen, dass für jede natürliche Zahl n F (n) wahr ist, wenn, und nur wenn es bewiesen werden kann (ist die genaue Voraussetzung im ursprünglichen Beweis, aber für den Beweis schwächer, eine Skizze machen, wird das genügen). Insbesondere das ist für jede spezifische arithmetische Operation zwischen einer begrenzten Zahl von natürlichen Zahlen, solcher als "2×3=6" wahr.

Behauptungsformen selbst sind nicht Behauptungen und können deshalb nicht bewiesen oder widerlegt werden. Aber jede Behauptung formt sich F (x) kann eine Zahl von Gödel zugeteilt werden, die durch G (F) angezeigt ist. Die Wahl der freien Variable, die in der Form F (x) verwendet ist, ist für die Anweisung von Gödel Nummer G (F) nicht wichtig.

Jetzt kommt der Trick: Der Begriff von provability selbst kann auch durch Zahlen von Gödel folgendermaßen verschlüsselt werden. Da ein Beweis eine Liste von Behauptungen ist, die bestimmten Regeln folgen, kann die Zahl von Gödel eines Beweises definiert werden. Jetzt, für jede Behauptung p, kann man fragen, ob eine Nummer x die Zahl von Gödel seines Beweises ist. Die Beziehung zwischen der Zahl von Gödel von p und x, der potenziellen Zahl von Gödel seines Beweises, ist eine arithmetische Beziehung zwischen zwei Zahlen. Deshalb gibt es eine Behauptungsform Bew (y), der diese arithmetische Beziehung verwendet, um festzustellen, dass eine Zahl von Gödel eines Beweises von y besteht:

:Bew (y) =  x (y ist die Zahl von Gödel einer Formel und x, ist die Zahl von Gödel eines Beweises der Formel, die durch y verschlüsselt ist).

Der Name Bew ist für beweisbar, das deutsche Wort für "den nachweisbaren" kurz; dieser Name wurde von Gödel ursprünglich verwendet, um die provability gerade beschriebene Formel anzuzeigen. Bemerken Sie, dass "Bew (y)" bloß eine Abkürzung ist, die eine Einzelheit, sehr lange, Formel auf der ursprünglichen Sprache von T vertritt; wie man fordert, ist die Schnur "Bew" selbst nicht ein Teil dieser Sprache.

Eine wichtige Eigenschaft der Formel, die Bew (y) ist, dass, wenn eine Behauptung p im System dann nachweisbar ist, Bew (G (p)) auch nachweisbar ist. Das ist, weil jeder Beweis von p eine entsprechende Zahl von Gödel haben würde, deren Existenz Bew (G (p)) veranlasst, zufrieden zu sein.

Diagonalization

Der nächste Schritt im Beweis soll eine Behauptung erhalten, die sagt, dass es unbeweisbar ist. Obwohl Gödel diese Behauptung direkt gebaut hat, folgt die Existenz von mindestens einer solcher Behauptung aus dem diagonalen Lemma, das sagt, dass für jedes genug starke formelle System und jede Behauptung F bilden, gibt es eine solche Behauptung p, dass das System beweist

:p  F (G (p)).

Indem

er F die Ablehnung von Bew (x) sein lässt, wird p erhalten: p stellt grob fest, dass seine eigene Zahl von Gödel die Zahl von Gödel einer unbeweisbaren Formel ist.

Die Behauptung p ist ~Bew (G (p)) nicht wörtlich gleich; eher stellt p fest, dass, wenn eine bestimmte Berechnung durchgeführt wird, die resultierende Zahl von Gödel die einer unbeweisbaren Behauptung sein wird. Aber wenn diese Berechnung durchgeführt wird, erweist sich die resultierende Zahl von Gödel, die Zahl von Gödel von p selbst zu sein. Das ist dem folgenden Satz in Englisch ähnlich:

: "wenn vorangegangen, allein in Notierungen, ist unbeweisbar." wenn vorangegangen, allein in Notierungen, ist unbeweisbar.

Dieser Satz bezieht sich auf sich nicht direkt, aber wenn die festgesetzte Transformation gemacht wird, wird der ursprüngliche Satz infolgedessen erhalten, und so behauptet dieser Satz seinen eigenen unprovability. Der Beweis des diagonalen Lemmas verwendet eine ähnliche Methode.

Beweis der Unabhängigkeit

Nehmen Sie jetzt an, dass das formelle System ω-consistent ist. Lassen Sie p die in der vorherigen Abteilung erhaltene Behauptung sein.

Wenn p nachweisbar wären, dann würde Bew (G (p)), wie diskutiert, oben nachweisbar sein. Aber p behauptet die Ablehnung von Bew (G (p)). So würde das System inkonsequent sein, sich sowohl eine Behauptung als auch seine Ablehnung erweisend. Dieser Widerspruch zeigt, dass p nicht nachweisbar sein kann.

Wenn die Ablehnung von p nachweisbar wäre, dann würde Bew (G (p)) nachweisbar sein (weil p gebaut wurde, um zur Ablehnung von Bew (G (p))) gleichwertig zu sein. Jedoch, für jede spezifische Nummer x, x kann nicht die Zahl von Gödel des Beweises von p sein, weil p (aus dem vorherigen Paragrafen) nicht nachweisbar ist. So einerseits der Systembetreuungsaufbau einer Zahl mit einem bestimmten Eigentum (dass es die Zahl von Gödel des Beweises von p ist), aber andererseits, für jede spezifische Nummer x, kann es bewiesen werden, dass die Zahl dieses Eigentum nicht hat. Das ist in einem ω-consistent System unmöglich. So ist die Ablehnung von p nicht nachweisbar.

So ist die Behauptung p unentscheidbar: Es kann weder bewiesen noch innerhalb des gewählten Systems widerlegt werden. So ist das gewählte System entweder inkonsequent oder unvollständig. Diese Logik kann auf jedes formelle System angewandt werden, das den Kriterien entspricht. Der Beschluss besteht darin, dass alle formellen Systeme, die den Kriterien entsprechen, entweder inkonsequent oder unvollständig sind. Es sollte bemerkt werden, dass p nicht nachweisbar (und so wahr ist) in jedem konsequenten System. Die Annahme von ω-consistency ist nur für die Ablehnung von p erforderlich, nicht nachweisbar zu sein. So:

• In einem ω-consistent formellen System können weder p noch seine Ablehnung bewiesen werden, und so ist p unentscheidbar.
• In einem konsequenten formellen System kommt entweder dieselbe Situation vor, oder die Ablehnung von p kann bewiesen werden; im späteren Fall ist eine Behauptung ("nicht p") falsch, aber nachweisbar.

Bemerken Sie dass, wenn man versucht, das "das Hinzufügen der fehlenden Axiome" zu befestigen, um die Unentscheidbarkeit des Systems zu vermeiden, dann muss man entweder p oder "nicht p" als Axiome hinzufügen. Aber das schafft dann ein neues formelles System (altes System + p), auf den genau derselbe Prozess angewandt werden kann, bildet das Schaffen einer neuen Behauptung Bew (x) für dieses neue System. Wenn das diagonale Lemma auf diese neue Form Bew angewandt wird, wird eine neue Behauptung p erhalten; diese Behauptung wird von der vorherigen verschieden sein, und diese neue Behauptung wird im neuen System unentscheidbar sein, wenn es ω-consistent ist, so zeigend, dass System ebenso inkonsequent ist. So das Hinzufügen von Extraaxiomen kann das Problem nicht befestigen.

Beweis über das Paradox der Beere

George Boolos (1989) Skizzen ein alternativer Beweis des ersten Unvollständigkeitslehrsatzes, der das Paradox von Berry aber nicht das Lügner-Paradox verwendet, um eine wahre, aber unbeweisbare Formel zu bauen. Eine ähnliche Probemethode wurde von Saul Kripke unabhängig entdeckt (Boolos 1998, p. 383). Der Probeerlös von Boolos durch das Konstruieren, für irgendwelchen berechenbar enumerable setzt S von wahren Sätzen der Arithmetik, ein anderer Satz, der wahr, aber in S nicht enthalten ist. Das gibt den ersten Unvollständigkeitslehrsatz als eine Folgeerscheinung. Gemäß Boolos ist dieser Beweis interessant, weil er eine "verschiedene Sorte des Grunds" für die Unvollständigkeit von wirksamen, konsequenten Theorien der Arithmetik zur Verfügung stellt (Boolos 1998, p. 388).

Formalisierte Beweise

Formalisierte Beweise von Versionen des Unvollständigkeitslehrsatzes sind von Natarajan Shankar 1986 mit Nqthm (Shankar 1994) und von Russell O'Connor 2003 mit Coq (O'Connor 2005) entwickelt worden.

Probeskizze für den zweiten Lehrsatz

Die Hauptschwierigkeit, den zweiten Unvollständigkeitslehrsatz zu beweisen, soll zeigen, dass verschiedene Tatsachen über im Beweis des ersten Unvollständigkeitslehrsatzes verwendeten provability innerhalb des Systems mit einem formellen Prädikat für provability formalisiert werden können. Sobald das getan wird, folgt der zweite Unvollständigkeitslehrsatz durch das Formalisieren des kompletten Beweises des ersten Unvollständigkeitslehrsatzes innerhalb des Systems selbst.

Lassen Sie p für den unentscheidbaren Satz eintreten, der oben gebaut ist und annehmen, dass die Konsistenz des Systems aus dem System selbst bewiesen werden kann. Die Demonstration zeigt oben dass, wenn das System entspricht, dann ist p nicht nachweisbar. Der Beweis dieser Implikation kann innerhalb des Systems formalisiert werden, und deshalb ist die Behauptung "p nicht nachweisbar", oder "nicht P (p)" kann im System bewiesen werden.

Aber diese letzte Behauptung ist zu p selbst gleichwertig (und diese Gleichwertigkeit kann im System bewiesen werden), so kann p im System bewiesen werden. Dieser Widerspruch zeigt, dass das System inkonsequent sein muss.

Diskussion und Implikationen

Die Unvollständigkeitsergebnisse betreffen die Philosophie der Mathematik, besonders Versionen des Formalismus, die eine einzelne formale Systemlogik verwenden, um ihre Grundsätze zu definieren. Man kann den ersten Lehrsatz sagend, dass der folgende paraphrasieren:

:An, der axiomatisches System vollumfasst, kann nie gefunden werden, dass das im Stande ist, alle mathematischen Wahrheiten, aber keine Lügen zu beweisen.

Andererseits von einer strengen Formalist-Perspektive würde diese Paraphrase sinnlos betrachtet, weil sie voraussetzt, dass mathematische "Wahrheit" und "Lüge" in einem absoluten Sinn, aber nicht hinsichtlich jedes formellen Systems bestimmt sind.

Das folgende Neuformulieren des zweiten Lehrsatzes ist zu den Fundamenten der Mathematik noch mehr beunruhigend:

:If, wie man beweisen kann, entspricht ein axiomatisches System aus sich dann, ist es inkonsequent.

Deshalb, um die Konsistenz eines Systems S zu gründen, muss man ein anderes stärkeres System T verwenden, aber ein Beweis in T ist nicht völlig überzeugend, wenn die Konsistenz von T bereits nicht gegründet worden ist, ohne S zu verwenden.

Theorien wie Arithmetik von Peano, für die irgendwelcher berechenbar enumerable konsequente Erweiterung unvollständig ist, werden im Wesentlichen unentscheidbar oder im Wesentlichen unvollständig genannt.

Meinungen und Maschinen

Autoren einschließlich J. R. Lucas haben debattiert, was, wenn irgendetwas die Unvollständigkeitslehrsätze von Gödel über die menschliche Intelligenz einbeziehen. Viele der Debatte-Zentren darauf, ob der Menschenverstand zu einer Maschine von Turing, oder durch die Kirch-Turing-These, eine begrenzte Maschine überhaupt gleichwertig ist. Wenn es ist, und wenn die Maschine entspricht, dann würden die Unvollständigkeitslehrsätze von Gödel dafür gelten.

Hilary Putnam (1960) hat vorgeschlagen, dass, während die Lehrsätze von Gödel auf Menschen nicht angewandt werden können, da sie Fehler machen und deshalb inkonsequent sind, es auf die menschliche Fakultät der Wissenschaft oder Mathematik im Allgemeinen angewandt werden kann. Das Annehmen, dass es, entweder seine Konsistenz entspricht, kann nicht bewiesen werden, oder es kann durch eine Maschine von Turing nicht vertreten werden.

Avi Wigderson (2010) hat vorgeschlagen, dass das Konzept mathematischen "knowability" auf der rechenbetonten Kompliziertheit aber nicht logischen Entscheidbarkeit basieren sollte. Er schreibt, dass, "wenn knowability durch moderne Standards nämlich über die rechenbetonte Kompliziertheit interpretiert wird, die Phänomene von Gödel sehr viel mit uns sind."

Parakonsequente Logik

Obwohl die Lehrsätze von Gödel gewöhnlich im Zusammenhang der klassischen Logik studiert werden, haben sie auch eine Rolle in der Studie der parakonsequenten Logik und von von Natur aus widersprechenden Behauptungen (dialetheia). Priester von Graham (1984, 2006) behauptet, dass das Ersetzen des Begriffs des formellen Beweises im Lehrsatz von Gödel mit dem üblichen Begriff des informellen Beweises verwendet werden kann, um zu zeigen, dass naive Mathematik inkonsequent ist, und das als Beweise für dialetheism verwendet. Die Ursache dieser Widersprüchlichkeit ist die Einschließung eines Wahrheitsprädikats für eine Theorie innerhalb der Sprache der Theorie (Priester 2006:47). Stewart Shapiro (2002) gibt eine mehr Mischabschätzung der Anwendungen der Lehrsätze von Gödel zu dialetheism. Carl Hewitt (2008) hat vorgeschlagen, dass (inkonsequente) parakonsequente Logik, die ihre eigenen Sätze von Gödel beweist, Anwendungen in der Softwaretechnik haben kann.

Bitten an die Unvollständigkeitslehrsätze in anderen Feldern

Bitten und Analogien werden manchmal zu den Unvollständigkeitslehrsätzen zur Unterstutzung Argumente gemacht, die Mathematik und Logik übertreffen. Mehrere Autoren haben negativ solche Erweiterungen und Interpretationen, einschließlich Torkel Franzén (2005) kommentiert; Alan Sokal und Jean Bricmont (1999); und Ophelia Benson und Jeremy Stangroom (2006). Bricmont und Stangroom (2006, p. 10), zum Beispiel hat das Zitat aus den Kommentaren von Rebecca Goldstein zur Verschiedenheit zwischen Gödel Platonism bekannt, und der Antirealist verwendet, zu dem seine Ideen manchmal gestellt werden. Sokal und Bricmont (1999, p. 187) kritisieren die Beschwörung von Régis Debray des Lehrsatzes im Zusammenhang der Soziologie; Debray hat diesen Gebrauch als metaphorisch (ibd.) verteidigt..

Die Rolle der Selbstverweisung

Torkel Franzén (2005, p. 46) beobachtet:

Der Beweis von Gödel des ersten Unvollständigkeitslehrsatzes und die gestärkte Version von Rosser haben vielen den Eindruck gegeben, dass der Lehrsatz nur durch das Konstruieren von Selbstverweisungsbehauptungen [...] oder sogar bewiesen werden kann, dass, wie man bekannt, nur fremde Selbstverweisungsbehauptungen in der elementaren Arithmetik unentscheidbar sind.

Um solchen Eindrücken entgegenzuwirken, müssen wir nur eine verschiedene Art des Beweises des ersten Unvollständigkeitslehrsatzes einführen.

Er schlägt dann die Beweise vor, die auf der Berechenbarkeit, oder auf der Informationstheorie, wie beschrieben, früher in diesem Artikel als Beispiele von Beweisen gestützt sind, die solchen Eindrücken "entgegenwirken sollten".

Geschichte

Nachdem Gödel seinen Beweis des Vollständigkeitslehrsatzes als seine Doktorthese 1929 veröffentlicht hat, hat er sich einem zweiten Problem für seinen habilitation zugewandt. Seine ursprüngliche Absicht war, eine positive Lösung des zweiten Problems von Hilbert zu erhalten (Dawson 1997, p. 63). Zurzeit waren Theorien der natürlichen Zahlen und der Arithmetik der zweiten Ordnung ähnlichen reellen Zahlen als "Analyse" bekannt, während Theorien der natürlichen Zahlen allein als "Arithmetik" bekannt waren.

Gödel war nicht die einzige Person, die am Konsistenz-Problem arbeitet. Ackermann hatte einen fehlerhaften Konsistenz-Beweis für die Analyse 1925 veröffentlicht, in der er versucht hat, die Methode von von Hilbert ursprünglich entwickeltem ε-substitution zu verwenden. Später in diesem Jahr ist von Neumann im Stande gewesen, den Beweis für eine Theorie der Arithmetik ohne irgendwelche Axiome der Induktion zu korrigieren. Vor 1928 hatte Ackermann einen modifizierten Beweis Bernays mitgeteilt; dieser modifizierte Beweis hat Hilbert dazu gebracht, seinen Glauben 1929 bekannt zu geben, dass die Konsistenz der Arithmetik demonstriert worden war, und dass ein Konsistenz-Beweis der Analyse wahrscheinlich bald folgen würde. Nachdem die Veröffentlichung der Unvollständigkeitslehrsätze gezeigt hat, dass der modifizierte Beweis von Ackermann falsch sein muss, hat von Neumann ein konkretes Beispiel erzeugt zeigend, dass seine Haupttechnik ungesund war (Zach 2006, p. 418, Zach 2003, p. 33).

Im Laufe seiner Forschung hat Gödel entdeckt, dass, obwohl ein Satz, der seine eigene Lüge behauptet, zu Paradox führt, ein Satz, der seinen eigenen non-provability behauptet, nicht tut. Insbesondere Gödel war des Ergebnisses bewusst jetzt hat den indefinability Lehrsatz von Tarski genannt, obwohl er es nie veröffentlicht hat. Gödel hat seinen ersten Unvollständigkeitslehrsatz zu Carnap, Feigel und Waismann am 26. August 1930 bekannt gegeben; alle vier würden einer Schlüsselkonferenz in Königsberg die nächste Woche beiwohnen.

Ansage

Die 1930-Konferenz von Königsberg war eine gemeinsame Sitzung von drei akademischen Gesellschaften mit vielen der Schlüssellogiker der Zeit Dienst habend. Carnap, Heyting und von Neumann haben einstündige Adressen auf den mathematischen Philosophien von logicism, intuitionism, und Formalismus beziehungsweise geliefert (Dawson 1996, p. 69). Die Konferenz hat auch die Ruhestandsadresse von Hilbert eingeschlossen, weil er seine Position an der Universität von Göttingen verließ. Hilbert hat die Rede verwendet, um seinen Glauben zu diskutieren, dass alle mathematischen Probleme behoben werden können. Er hat seine Adresse beendet, indem er, gesagt

hat

: "Für den Mathematiker gibt es keinen Ignorabimus, und nach meiner Meinung überhaupt nicht für die Naturwissenschaft auch.... Der wahre Grund, warum [keiner] geschafft hat, ein unlösbares Problem zu finden, ist nach meiner Meinung, dass es kein unlösbares Problem gibt. Im Gegensatz zu dummem Ignoramibus behauptet unser Kredo: Wir müssen wissen. Wir werden wissen!"

Diese Rede ist schnell bekannt als eine Zusammenfassung des Glaubens von Hilbert auf der Mathematik geworden (seine sechs Endwörter, "Wir müssen wissen. Wir werden wissen!" wurden als die Grabinschrift von Hilbert 1943 verwendet). Obwohl Gödel Dienst habend für die Adresse von Hilbert wahrscheinlich war, haben sich die zwei nie von Angesicht zu Angesicht getroffen (Dawson 1996, p. 72).

Gödel hat seinen ersten Unvollständigkeitslehrsatz auf einer Round-Tablediskussionssitzung am dritten Tag der Konferenz bekannt gegeben. Die Ansage hat wenig Aufmerksamkeit abgesondert von diesem von von Neumann gelenkt, der Gödel beiseite für das Gespräch gezogen hat. Später in diesem Jahr, unabhängig mit Kenntnissen des ersten Unvollständigkeitslehrsatzes arbeitend, hat von Neumann einen Beweis des zweiten Unvollständigkeitslehrsatzes erhalten, den er Gödel in einem Brief datiert am 20. November 1930 bekannt gegeben hat (Dawson 1996, p. 70). Gödel hatte den zweiten Unvollständigkeitslehrsatz unabhängig erhalten und ihn in sein vorgelegtes Manuskript eingeschlossen, das durch Monatshefte für Mathematik am 17. November 1930 erhalten wurde.

Das Papier von Gödel wurde in Monatshefte 1931 laut des Titels Über formeller unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I (Auf Formell Unentscheidbaren Vorschlägen in Principia Mathematica und Related Systems I) veröffentlicht. Da der Titel einbezieht, hat Gödel ursprünglich geplant, einen zweiten Teil des Papiers zu veröffentlichen; es wurde nie geschrieben.

Generalisation und Annahme

Gödel hat eine Reihe von Vorträgen auf seinen Lehrsätzen an Princeton in 1933-1934 zu einem Publikum gegeben, das Kirche, Kleene und Rosser eingeschlossen hat. Zu diesem Zeitpunkt hatte Gödel ergriffen, dass das Schlüsseleigentum, das seine erforderlichen Lehrsätze sind, dass die Theorie wirksam sein muss (zurzeit wurde der Begriff "allgemeiner rekursiver" gebraucht). Rosser hat 1936 bewiesen, dass die Hypothese von ω-consistency, der ein integraler Bestandteil des ursprünglichen Beweises von Gödel war, durch die einfache Konsistenz ersetzt werden konnte, wenn der Satz von Gödel auf eine passende Weise geändert wurde. Diese Entwicklungen haben die Unvollständigkeitslehrsätze in im Wesentlichen ihrer modernen Form verlassen.

Gentzen hat seinen Konsistenz-Beweis für die Arithmetik der ersten Ordnung 1936 veröffentlicht. Hilbert hat diesen Beweis als "finitary" akzeptiert, obwohl (weil hatte sich der Lehrsatz von Gödel bereits gezeigt), es innerhalb des Systems der Arithmetik nicht formalisiert werden kann, die konsequent bewiesen wird.

Der Einfluss der Unvollständigkeitslehrsätze auf dem Programm von Hilbert wurde schnell begriffen. Bernays hat einen vollen Beweis der Unvollständigkeitslehrsätze im zweiten Volumen von Grundlagen der Mathematik (1939), zusammen mit zusätzlichen Ergebnissen von Ackermann auf der ε-substitution Methode und dem Konsistenz-Beweis von Gentzen der Arithmetik eingeschlossen. Das war der erste volle veröffentlichte Beweis des zweiten Unvollständigkeitslehrsatzes.

Kritik

Im September 1931 hat Ernst Zermelo Gödel geschrieben, um bekannt zu geben, was er als eine "wesentliche Lücke" im Argument von Gödel (Dawson:76) beschrieben hat. Im Oktober hat Gödel mit einem 10-seitigen Brief (Dawson:76, Grattan-Guinness:512-513) geantwortet. Aber Zermelo hat nicht nachgegeben und hat seine Kritiken im Druck mit "einem ziemlich verletzenden Paragrafen auf seinem jungen Mitbewerber" (Grattan-Guinness:513) veröffentlicht. Gödel hat entschieden, dass, die Sache zu verfolgen, weiter sinnlos war, und Carnap (Dawson:77) zugestimmt hat. Viel nachfolgende Arbeit von Zermelo ist mit der Logik verbunden gewesen, die stärker ist als Logik der ersten Ordnung, mit der er gehofft hat, sowohl die Konsistenz als auch categoricity von mathematischen Theorien zu zeigen.

Paul Finsler (1926) hat eine Version des Paradoxes von Richard verwendet, um einen Ausdruck zu bauen, der falsch, aber in einem besonderen, informellen Fachwerk unbeweisbar war, das er entwickelt hatte. Gödel hat dieses Papier nicht gewusst, als er die Unvollständigkeitslehrsätze bewiesen hat (Gesammelte Arbeiten Vol. IV., p. 9). Finsler hat Gödel 1931 geschrieben, um ihn über dieses Papier zu informieren, das Finsler gefühlt hat, hatte Vorrang für einen Unvollständigkeitslehrsatz. Die Methoden von Finsler haben sich auf formalisierten provability nicht verlassen, und hatten nur eine oberflächliche Ähnlichkeit mit der Arbeit von Gödel (van Heijenoort 1967:328). Gödel hat das Papier gelesen, aber hat es tief rissig gemacht gefunden, und seine Antwort Finsler hat Sorgen über den Mangel an der Formalisierung (Dawson:89) angelegt. Finsler hat fortgesetzt, für seine Philosophie der Mathematik zu argumentieren, die sich Formalisierung für den Rest seiner Karriere enthalten hat.

Wittgenstein und Gödel

Ludwig Wittgenstein hat mehrere Durchgänge über die Unvollständigkeitslehrsätze geschrieben, die postum in seinen 1953 Bemerkungen auf den Fundamenten der Mathematik veröffentlicht wurden. Gödel war ein Mitglied des Wiener Kreises während der Periode, in der die frühe ideale Sprachphilosophie von Wittgenstein und Tractatus Logico-Philosophicus das Denken des Kreises beherrscht haben. Schriften im Nachlass von Gödel drücken den Glauben aus, dass Wittgenstein absichtlich seine Ideen falsch gelesen hat.

Vielfache Kommentatoren haben Wittgenstein als Missverständnis von Gödel gelesen (Rodych 2003), obwohl Juliet Floyd und Hilary Putnam (2000), sowie Priester von Graham (2004) Textlesungen zur Verfügung gestellt haben behauptend, dass der grösste Teil des Kommentars Wittgenstein missversteht. Auf ihrer Ausgabe haben Bernays, Dummett und Kreisel getrennte Rezensionen über die Bemerkungen von Wittgenstein geschrieben, von denen alle (Berto 2009:208) äußerst negativ waren. Die Einmütigkeit dieser Kritik hat die Bemerkungen von Wittgenstein auf den Unvollständigkeitslehrsätzen veranlasst, wenig Einfluss auf die Logikgemeinschaft zu haben. 1972, Gödel, hat festgesetzt: "Hat Wittgenstein Verstand verloren? Hat er es ernstlich vor?" (Wang 1996:197) Und hat Karl Menger geschrieben, dass die Anmerkungen von Wittgenstein ein eigenwilliges Missverständnis des Unvollständigkeitslehrsatz-Schreibens demonstrieren:

: "Es ist von den Durchgängen klar Sie zitieren diesen Wittgenstein hat [den ersten Unvollständigkeitslehrsatz] (oder vorgegeben "nicht" verstanden, um es nicht zu verstehen). Er hat es als eine Art logisches Paradox interpretiert, während tatsächlich gerade das Gegenteil, nämlich ein mathematischer Lehrsatz innerhalb eines absolut unverfänglichen Teils der Mathematik (finitary Zahlentheorie oder combinatorics) ist." (Wang 1996:197)

Seit der Veröffentlichung des Nachlass von Wittgenstein 2000,

eine Reihe von Papieren in der Philosophie hat sich bemüht zu bewerten, ob die ursprüngliche Kritik der Bemerkungen von Wittgenstein gerechtfertigt wurde. Floyd und Putnam (2000) behaupten, dass Wittgenstein ein mehr ganzes Verstehen des Unvollständigkeitslehrsatzes hatte, als es vorher angenommen wurde. Sie sind besonders mit der Interpretation eines Satzes von Gödel für eine ω-inconsistent Theorie als wirklicher Ausspruch beschäftigt "Von mir bin nicht nachweisbar", da die Theorie keine Modelle hat, in denen das provability Prädikat wirklichem provability entspricht. Rodych (2003) behauptet, dass ihre Interpretation von Wittgenstein nicht historisch gerechtfertigt wird, während Buchten (2004) gegen Floyd und die philosophische Analyse von Putnam des provability Prädikats argumentieren. Berto (2009) erforscht die Beziehung zwischen dem Schreiben von Wittgenstein und Theorien der parakonsequenten Logik.

Siehe auch

• Der Vollständigkeitslehrsatz von Gödel
• Der Beschleunigungslehrsatz von Gödel
• Der Lehrsatz von Löb
• Logik von Provability
• Münchhausen Trilemma
• Sondermodell der Arithmetik
• Der undefinability Lehrsatz von Tarski
• Meinungen, Machines und Gödel
• Das dritte Mann-Argument

Referenzen

Artikel durch Gödel

• 1931, Über formeller unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, ich. Monatshefte für Mathematik und Physik 38: 173-98.
• 1931, Über formeller unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I. und Auf formell unentscheidbaren Vorschlägen von Principia Mathematica und verwandten Systemen I in Solomon Feferman, Hrsg., 1986. Arbeiten von Kurt Gödel Collected, Vol. Ich. Presse der Universität Oxford: 144-195. Der ursprüngliche Deutsche mit einer liegenden englischen Übersetzung, die durch ein sehr leuchtendes einleitendes Zeichen durch Kleene vorangegangen ist.
• Hirzel, Martin, 2000, Auf formell unentscheidbaren Vorschlägen von Principia Mathematica und verwandten Systemen I. Eine moderne Übersetzung durch Hirzel.
• 1951, Einige grundlegende Lehrsätze auf den Fundamenten der Mathematik und ihrer Implikationen in Solomon Feferman, Hrsg., 1995. Arbeiten von Kurt Gödel Collected, Vol. III. Presse der Universität Oxford: 304-23.

Übersetzungen, während seiner Lebenszeit, des Papiers von Gödel ins Englisch

Keiner des folgenden stimmt in allen übersetzten Wörtern und in der Typografie zu. Die Typografie ist eine ernste Sache, weil Gödel ausdrücklich "jene metamathematical Begriffe hat betonen wollen, die in ihrem üblichen Sinn vorher definiert worden waren..." (van Heijenoort 1967:595). Drei Übersetzungen bestehen. Des ersten John Dawsons stellt dass fest: "Die Übersetzung von Meltzer war ernstlich unzulänglich und hat eine verheerende Rezension in der Zeitschrift der Symbolischen Logik erhalten; "Gödel hat sich auch über den Kommentar von Braithwaite (Dawson 1997:216) beklagt." Glücklich wurde die Übersetzung von Meltzer bald durch eine bessere verdrängt, die von Elliott Mendelson zur Anthologie von Martin Davis Das Unentscheidbare bereit ist... er hat die Übersetzung "nicht ganz so gut" gefunden, wie er erwartet hatte... [aber wegen zeitlicher Einschränkungen hat er] seiner Veröffentlichung" (ibd.) zugestimmt. (In einem Kommentar stellt Dawson fest, dass "er seinen Gehorsam bedauern würde, weil das veröffentlichte Volumen überall durch die schlampige Typografie und zahlreichen Druckfehler" (ibd.) beschädigt wurde). Dawson stellt fest, dass "Die Übersetzung, dass bevorzugter Gödel dass durch Jean van Heijenoort" (ibd.) war. Für den ernsten Studenten besteht eine andere Version als eine Reihe von Vortrag-Zeichen, die von Stephen Kleene und J. B. Rosser "während Vorträge registriert ist, die von Gödel an zum Institut für die Fortgeschrittene Studie während des Frühlings 1934 gegeben sind" (vgl Kommentar von Davis 1965:39 und auf p beginnend. 41); diese Version wird "Auf Unentscheidbaren Vorschlägen von Formellen Mathematischen Systemen" betitelt. In ihrer Ordnung der Veröffentlichung:

• B. Meltzer (Übersetzung) und R. B. Braithwaite (Einführung), 1962. Auf Formell Unentscheidbaren Vorschlägen von Principia Mathematica und Related Systems, Veröffentlichungen von Dover, New York (Ausgabe 1992 von Dover), internationale Standardbuchnummer 0-486-66980-7 (pbk). Das enthält eine nützliche Übersetzung der deutschen Abkürzungen von Gödel auf Seiten 33-34. Wie bemerkt, oben, Typografie, Übersetzung und Kommentar ist Verdächtiger. Leider wurde diese Übersetzung mit seinem ganzen verdächtigen Inhalt durch nachgedruckt

:*Stephen-Falknerei-Redakteur, 2005. Gott hat die Ganzen Zahlen Geschaffen: Die Mathematischen Durchbrüche Der Geänderte Geschichte, Presse, Philadelphia, internationale Standardbuchnummer 0-7624-1922-9 Führend. Das Papier von Gödel scheint Start-auf p. 1097, mit dem Kommentar der Falknerei, der auf p anfängt. 1089.

• Redakteur von Martin Davis, 1965. Das Unentscheidbare: Grundlegende Papiere auf Unentscheidbaren Vorschlägen, Unlösbaren Problemen und Berechenbaren Funktionen, Rabe-Presse, New York, beginnt kein Papier von Gödel der internationalen Standardbuchnummer auf der Seite 5, die durch eine Seite des Kommentars vorangegangen ist.
• Redakteur von Jean van Heijenoort, 1967, 3. Ausgabe 1967. Von Frege bis Gödel: Ein Quellbuch in der Mathematischen Logik, 1979-1931, Universität von Harvard Presse, Masse von Cambridge. internationale Standardbuchnummer 0-674-32449-8 (pbk). van Heijenoort hat die Übersetzung getan. Er stellt fest, dass "Professor Gödel die Übersetzung genehmigt hat, die in vielen Plätzen an seine Wünsche angepasst wurde." (p. 595). Das Papier von Gödel beginnt auf p. 595; der Kommentar von van Heijenoort beginnt auf p. 592.
• Redakteur von Martin Davis, 1965, ibd. "Auf Unentscheidbaren Vorschlägen von Formellen Mathematischen Systemen." Eine Kopie mit den Korrekturen von Gödel von Errata und den zusätzlichen Zeichen von Gödel beginnt auf der Seite 41, die durch zwei Seiten des Kommentars von Davis vorangegangen ist. Bis Davis das in sein Volumen eingeschlossen hat, hat dieser Vortrag nur als vervielfältigte Zeichen bestanden.

Artikel durch andere

• George Boolos, 1989, "Ein Neuer Beweis des Gödel Unvollständigkeitslehrsatzes", Benachrichtigungen der amerikanischen Mathematischen Gesellschaft v. 36, Seiten 388-390 und p. 676, nachgedruckt in Boolos, 1998, Logik, Logik und Logik, Harvard Univ. Drücken. Internationale Standardbuchnummer 0-674-53766-1
• Arthur Charlesworth, 1980, "Ein Beweis des Lehrsatzes von Godel in Bezug auf Computerprogramme," Mathematik-Zeitschrift, v. 54 n. 3, Seiten 109-121. JStor
• Martin Davis, "Der Unvollständigkeitslehrsatz", in Benachrichtigungen des AMS vol. 53 Nr. 4 (April 2006), p. 414.
• Jean van Heijenoort, 1963. "Der Lehrsatz von Gödel" in Edwards, Paul, Hrsg., Enzyklopädie der Philosophie, Vol. 3. Macmillan: 348-57.
• Geoffrey Hellman, Wie zu Gödel ein Frege-Russell: Incompleteness Theorems von Gödel und Logicism. Noûs, Vol. 15, Nr. 4, Sonderausgabe auf der Philosophie der Mathematik. (November 1981), Seiten 451-468.
• David Hilbert, 1900, "Mathematische Probleme." Englische Übersetzung eines Vortrags geliefert vor dem Internationalen Kongress von Mathematikern an Paris, die Behauptung von Hilbert seines Zweiten Problems enthaltend.
• Stephen Cole Kleene, 1943, "Rekursive Prädikate und quantifiers," nachgedruckt von Transaktionen der amerikanischen Mathematischen Gesellschaft, v. 53 n. 1, Seiten 41-73 in Martin Davis 1965, Das Unentscheidbare (lokale Nummer cit.) Seiten 255-287.
• John Barkley Rosser, 1936, "Erweiterungen von einigen Lehrsätzen von Gödel und Kirche," nachgedruckt aus der Zeitschrift der Symbolischen Logik vol. 1 (1936) Seiten 87-91, in Martin Davis 1965, Das Unentscheidbare (lokale Nummer cit.) Seiten 230-235.
• John Barkley Rosser, 1939, "Eine Informelle Ausstellung von Beweisen des Lehrsatzes von Gödel und des Lehrsatzes der Kirche", Nachgedruckt aus der Zeitschrift der Symbolischen Logik, vol. 4 (1939) Seiten 53-60, in Martin Davis 1965, Das Unentscheidbare (lokale Nummer cit.) Seiten 223-230
• C. Smoryński, "Die Unvollständigkeitslehrsätze", in J. Barwise, Hrsg., Handbuch der Mathematischen Logik, internationale 1982-Standardbuchnummer von Nordholland 978-0-444-86388-1, Seiten 821-866.
• Dan E. Willard (2001), "Axiom-Systeme, den Unvollständigkeitslehrsatz und die Zusammenhängenden Nachdenken-Grundsätze", Zeitschrift der Symbolischen Logik, v. 66 n Selbstnachprüfend. 2, Seiten 536-596.
• Richard Zach, 2005, "Papier auf den Unvollständigkeitslehrsätzen" in Grattan-Guinness, I., Hrsg., Merklichen Schriften in der Westmathematik. Elsevier: 917-25.

Bücher über die Lehrsätze

• Francesco Berto. Es gibt Etwas über Gödel: Das Ganze Handbuch zu Incompleteness Theorem John Wiley and Sons. 2010.
• Domeisen, Norbert, 1990. Logik der Antinomien. Bern: Peter Lang. 142 S. 1990. Internationale Standardbuchnummer 3-261-04214-1. Zentralblatt MATHEMATIK
• Torkel Franzén, 2005. Der Lehrsatz von Gödel: Ein Unvollständiges Handbuch zu seinem Gebrauch und Missbrauch. A.K. Peters. Internationale Standardbuchnummer 1-56881-238-8
• Douglas Hofstadter, 1979. Gödel, Escher, Junggeselle: Eine Ewige Goldene Flechte. Weinlesebücher. Internationale Standardbuchnummer 0-465-02685-0. 1999-Nachdruck: Internationale Standardbuchnummer 0-465-02656-7.
• Douglas Hofstadter, 2007. Ich Bin eine Fremde Schleife. Grundlegende Bücher. Internationale Standardbuchnummer 978-0-465-03078-1. Internationale Standardbuchnummer 0-465-03078-5.
• Stanley Jaki, OSB, 2005. Das Drama der Mengen. Echte Ansicht-Bücher.
• Pro Lindström, 1997, Aspekte der Unvollständigkeit, Vortrag-Zeichen in der Logik v. 10.
• J.R. Lucas, FBA, 1970. Die Freiheit des Willens. Clarendon Press, Oxford, 1970.
• Ernest Nagel, James Roy Newman, Douglas Hofstadter, 2002 (1958). Der Beweis von Gödel, revidierte internationale Hrsg.-Standardbuchnummer 0-8147-5816-9.
• Rudy Rucker, 1995 (1982). Unendlichkeit und die Meinung: Die Wissenschaft und Philosophie des Unendliches. Princeton Univ. Drücken.
• Schmied, Peter, 2007. Eine Einführung in die Lehrsätze von Gödel. Universität von Cambridge Presse. MathSciNet
• N. Shankar, 1994. Metamathematics, Maschinen und der Beweis von Gödel, Band 38 von Flächen von Cambridge in der theoretischen Informatik. Internationale Standardbuchnummer 0-521-58533-3
• Raymond Smullyan, 1991. Die Unvollständigkeitslehrsätze von Godel. Oxford Univ. Drücken.
• — 1994. Diagonalization und Self-Reference. Oxford Univ. Drücken.
• Hao Wang, 1997. Eine Logische Reise: Von Gödel bis Philosophie. MIT Presse. Internationale Standardbuchnummer 0-262-23189-1

Verschiedene Verweisungen

• Francesco Berto. "Das Gödel Paradox und die Gründe von Wittgenstein" Philosophia Mathematica (III) 17. 2009.
• John W. Dawson der Jüngere. 1997. Logische Dilemmas: Das Leben und die Arbeit von Kurt Gödel, A.K. Peters, Wellesley Masse, internationaler Standardbuchnummer 1-56881-256-6.
• Goldstein, Rebecca, 2005, Unvollständigkeit: der Beweis und das Paradox von Kurt Gödel, W. W. Norton & Company. Internationale Standardbuchnummer 0-393-05169-2
• Juliet Floyd und Hilary Putnam, 2000, "Ein Zeichen auf dem 'Notorischen Paragrafen von Wittgenstein' Über den Gödel Lehrsatz", Zeitschrift der Philosophie v. 97 n. 11, Seiten 624-632.
• Carl Hewitt, 2008, "Verlangt Groß angelegte Organisatorische Computerwissenschaft Ungeschichtetes Nachdenken und Starke Parakonsistenz", Koordination, Organisationen, Einrichtungen und Normen in Reagenz-Systemen III, Springer-Verlag.
• David Hilbert und Paul Bernays, Grundlagen der Mathematik, Springer-Verlag.
• John Hopcroft und Jeffrey Ullman 1979, Einführung in die Automaten-Theorie, Addison-Wesley, internationale Standardbuchnummer 0 201 02988 X
• James P. Jones, Unentscheidbare Diophantine Gleichungen, Meldung der amerikanischen Mathematischen Gesellschaft v. 3 n. 2, 1980, Seiten 859-862.
• Stephen Cole Kleene, 1967, Mathematische Logik. Nachgedruckt durch Dover, 2002. Internationale Standardbuchnummer 0-486-42533-9
• Russell O'Connor, 2005, "Wesentliche Unvollständigkeit der durch Coq Nachgeprüften Arithmetik", Vortrag-Zeichen in der Informatik v. 3603, Seiten 245-260.
• Priester von Graham, 2006, im Widerspruch: Eine Studie von Transconsistent, Presse der Universität Oxford, internationaler Standardbuchnummer 0-19-926329-9
• Priester von Graham, 2004, die Bemerkungen von Wittgenstein auf dem Lehrsatz von Gödel in Max Kölbel, Hrsg., anhaltender Bedeutung von Wittgenstein, Psychologie-Presse, Seiten 207-227.
• Priester von Graham, 1984, "Logik des Wieder besuchten Paradoxes", Zeitschrift der Philosophischen Logik, v. 13,` n. 2, Seiten 153-179
• Hilary Putnam, 1960, Meinungen und Maschinen in Sidney Hook, Hrsg., Dimensionen der Meinung: Ein Symposium. New Yorker Universität Presse. Nachgedruckt in Anderson, A. R., Hrsg., 1964. Meinungen und Maschinen. Prentice-Saal: 77.

.

• Victor Rodych, 2003, "Gödel Missverstehend: Neue Argumente über Wittgenstein und Neue Bemerkungen durch Wittgenstein", Dialectica v. 57 n. 3, Seiten 279-313.
• Stewart Shapiro, 2002, "Unvollständigkeit und Widersprüchlichkeit", Meinung, v. 111, Seiten 817-32.
• Alan Sokal und Jean Bricmont, 1999, Modischer Quatsch: Der Missbrauch der postmodernen Intellektuellen der Wissenschaft, Pikadors. Internationale Standardbuchnummer 0-312-20407-8
• Joseph R. Shoenfield (1967), Mathematische Logik. Nachgedruckt von A.K. Peters für die Vereinigung der Symbolischen Logik, 2001. Internationale Standardbuchnummer 978-1-56881-135-2
• Jeremy Stangroom und Ophelia Benson, Warum Wahrheitssachen, Kontinuum. Internationale Standardbuchnummer 0-8264-9528-1
• George Tourlakis, Vorträge in Logik und Mengenlehre, Band 1, Mathematischer Logik, Universität von Cambridge Presse, 2003. Internationale Standardbuchnummer 978-0-521-75373-9
• Hao Wang, 1996, Eine Logische Reise: Von Gödel bis Philosophie, Die MIT-Presse, den Magister artium von Cambridge, internationale Standardbuchnummer 0-262-23189-1.
• Richard Zach, 2006, "das Programm von Hilbert dann und jetzt", in der Philosophie der Logik, Dale Jacquette (Hrsg.). Handbuch der Philosophie der Wissenschaft, v. 5. Elsevier, Seiten 411-447.

Links

• Enzyklopädie von Stanford der Philosophie: "Kurt Gödel" - durch Juliette Kennedy.
• Lebensbeschreibungen von MacTutor:
• Kurt Gödel.
• Gerhard Gentzen.
• Was Mathematics:Gödel's Lehrsatz und Ringsherum durch Karlis Podnieks ist. Ein kostenloses Online-Buch.
• Kürzeste Erklärung in der Welt des Lehrsatzes von Gödel mit einer Druckmaschine als ein Beispiel.
• Oktober 2011 Episode von RadioLab über/einschließend den Unvollständigkeitslehrsatz von Gödel