Gödels erster Unvollständigkeitssatz besagt
Jede effektiv generierte Theorie, die in der Lage ist, elementare Arithmetik auszudrücken, kann nicht sowohl konsistent als auch vollständig sein. Insbesondere gibt es für jede konsistente, effektiv generierte formale Theorie, die bestimmte grundlegende arithmetische Wahrheiten beweist, eine arithmetische Aussage, die wahr, aber in der Theorie nicht beweisbar ist (Kleene 1967, S. 250).
Was sind die philosophischen Implikationen dieses Theorems? Gibt es insbesondere möglicherweise allgemeinere Analoga dieses Theorems – notwendigerweise „unbeweisbare Wahrheiten“ innerhalb anderer Arten von formalen Systemen?
Jedes effektiv axiomatisierte formale System, das eine sehr grundlegende Theorie der formalen Arithmetik namens Robinson-Arithmetik (Q) erweitert, enthält einen unentscheidbaren Satz. Ganz allgemein lässt sich die syntaktische Version des Ersten Unvollständigkeitssatzes wie folgt formulieren:
(G1T) Für jede effektiv axiomatisierte Theorie T, die Q erweitert, gibt es einen T-Satz G, so dass: (i) Wenn T konsistent ist, dann kann T G nicht beweisen (ii) Wenn T omega-konsistent ist, dann kann T ¬G nicht beweisen.
Dies ist eine möglichst allgemeine Aussage des Theorems. Beachten Sie, dass Kleene - in Ihrem Zitat - über die semantische Version des Theorems spricht . Was Gödel ursprünglich bewiesen hat, beinhaltete jedoch keine semantischen Begriffe wie Wahrheit, arithmetische Wahrheit usw. Ob Sie G als wahr sehen / erkennen / anerkennen können oder nicht, hängt vom semantischen / intensionalen Verständnis von G ab - es ist ein weit verbreitetes Missverständnis, das Gödel beweisen wollte Die Grenzen der arithmetischen Wahrheit. Der Hintergrund, vor dem er arbeitete, war der Hilbertsche Formalismus – sein Hauptanliegen war es also, die rein syntaktischen Beschränkungen formaler Systeme aufzuzeigen. In voller syntaktischer Allgemeinheit sagt (G1T) also (informell), dass keine angemessene Manipulation von Symbolen in irgendeinem formalen System, das kompliziert genug ist, um etwas Arithmetik zu enthalten, mit G enden wird.
Sie können also sehen, dass (G1T) für eine Vielzahl von formalen Systemen gilt. Ob Sie sich dafür entscheiden, die erhaltenen Gs als „unbeweisbare Wahrheiten “ anzusehen, hängt von Ihrer Semantik ab/ davon, ob Ihr T eine beabsichtigte Interpretation hat und so weiter. Aber in den meisten Fällen wird diese Art von Schlussfolgerung als gerechtfertigt angesehen. Aber es entsteht nur wegen des unterschwelligen syntaktischen Fehlers, den (G1T) sicherstellt.
Nun, was die philosophischen Implikationen betrifft, so ist die Literatur immens. Ich werde einige relevante Probleme erwähnen:
Abschließend möchte ich sagen, dass unzählige philosophisch denkende Autoren/Denker/Hacks sich Gödels Theorem angeeignet haben, um zu versuchen, Punkte über Selbstreferenz/Schleifen/Gott/Metaphysik/Umweltbewusstsein und Gott weiß was noch zu machen. Die drei Schlussfolgerungen, die ich angesprochen habe, mögen trocken und akademisch erscheinen, aber sie sind auch präzise, gut studiert und frei von Übertreibungen. Es besteht kein Zweifel, dass Gödels Theoreme unser Verständnis formaler Systeme vorangetrieben haben – und damit auch unser Verständnis der philosophischen Stärken und Schwächen formalen Denkens.
Ich möchte hier innehalten, um zunächst den Satz von Gödel genau zu formulieren und zu beweisen . Die ursprüngliche Präsentation ist vor der Erfindung des Computers und ist kompliziert. Aber wir leben 80 Jahre später, wo Computer vertraut sind.
Erstens spricht man in Gödels Theorem immer von einem axiomatischen System S. Das ist ein logisches System, in dem man Theoreme durch ein Computerprogramm beweisen kann, man sollte an Peano-Arithmetik, oder ZFC, oder jede andere Theorie erster Ordnung mit a denken berechenbares Axiomenschema (Axiome, die von einem festen Computerprogramm aufgelistet werden können).
Es wird angenommen, dass ein solches Axiomensystem einen Computer zu jeder endlichen Zeit beschreiben kann. Der Speicherinhalt eines Computers ist eine Reihe von Bits, eine große Ganzzahl M, und die Manipulationen am Speicher durch Ausführen eines Schritts sind eine sehr einfache Funktion, die etwas aus dem Befehlssatz macht und den Speicher ändert. Wenn Sie dies endlich oft tun, erhalten Sie einen neuen Speicherzustand M'. Die Grundannahme zu S ist folgende:
S kann einem Computerprogramm folgen: Bei einem gegebenen festen universellen Computer mit Anfangsgedächtnis M wird er beweisen, dass das Gedächtnis zur Zeit t für jede endliche Zeit t M' ist.
In der Peano-Arithmetik ist dies trivial, da Sie den Speicher eines Computers auf sehr einfache Weise codieren können, und die Axiome ohne Induktion, nur die Axiome zum Berechnen von Dingen, sagen Ihnen, was das Ergebnis einer endlichen Berechnung ist. Das gilt also in der Peano-Arithmetik ohne Induktion und ohne Quantoren. Es ist sehr einfach, von einem Axiomensystem zu verlangen, dass es einer Berechnung folgen und beweisen kann, dass das Ergebnis zu einer endlichen Zeit korrekt ist.
Als nächstes nehmen wir an, dass S Dinge sagen kann wie „Programm P hält nicht an“. Dies erfordert einen Quantifizierer
Ich gehe davon aus, dass S konsistent ist. Die Aussage „S ist konsistent“ bedeutet, dass, wenn S beweist, dass „P nicht anhält“, P tatsächlich nicht anhält. Denn wenn P anhält, würde S ihm folgen, bis es anhält, und dies dann auch beweisen. Beachten Sie, dass S „P hält an“ beweisen kann, ohne dass P tatsächlich anhält, es kann nur nicht beweisen „P hält nicht an“, wenn dies eine Lüge ist.
Satz: Betrachten Sie ein solches Axiomensystem S. Es gibt ein Programm P, das nicht anhält, für das S nicht beweisen kann, dass „P nicht anhält“:
Beweis: Schreiben Sie das Computerprogramm SPITE, um Folgendes zu tun:
Wenn Sie eine halbe Sekunde darüber nachdenken, hält SPITE in dem Moment, in dem S beweist, dass "SPITE nicht anhält", an (konstruktionsbedingt) und macht S zu einem Lügner. Der Selbstverweis steht in der ersten Zeile --- Drucken Sie Ihren eigenen Code in eine Variable, und dass dies möglich ist, ist eine Übung für Programmierer im Grundstudium.
Das ist die vollständige Konstruktion und der vollständige Beweis.
Gödel 2: S kann sich nicht als konsistent erweisen
Der Beweis lautet wie folgt: Wenn S konsistent ist, kann SPITE nicht anhalten, weil wir sehen, dass dies impliziert, dass S inkonsistent ist. Wenn S also dieses Argument formalisieren kann und sich als konsistent erweist, beweist es, dass SPITE nicht anhält (was unmöglich ist).
Das ist der vollständige Beweis. Es erfordert Vertrautheit mit der Logik, um zu sehen, dass für angemessenes S die informelle Schlussfolgerung „S ist konsistent impliziert, dass SPITE nicht anhält“ in S formalisiert werden kann, aber wenn es nicht möglich wäre, intuitive logische Schlussfolgerungen wie diese zu formalisieren, würden wir es tun Ich werde S überhaupt nicht verwenden.
Rosser: Das Problem mit Godel1 und Godel2 (die bis auf eine triviale Wahl eines kanonischen Beispiels im Wesentlichen derselbe Satz sind) ist, dass S immer noch vollständig, aber falsch sein könnte . Mit anderen Worten, Gödels Beweis zeigte nicht, dass es ein Programm P gibt, dessen Anhalten überhaupt nicht vorhergesagt wird. Vielleicht entscheidet S, dass alle Programme entweder anhalten oder nicht anhalten, aber es macht es nicht richtig --- es sagt Ihnen, dass einige nicht anhaltende Programme anhalten. Wenn es Ihnen sagen würde, dass ein anhaltendes Programm nicht angehalten wurde, wäre dies ein Widerspruch in S (nach genügend Zeit), aber es kann Ihnen sagen, dass ein nicht anhaltendes Programm ohne Widerspruch anhält (dies ist offensichtlich, aber subtil).
Also schreib ROSSER:
Nun kann S weder „ROSSER druckt“ noch die Negation „ROSSER druckt nicht“ beweisen. Wenn also ein zweites Programm Rosser folgt und anhält, wenn ROSSER druckt, wird dieses Programm weder als anhaltend noch als nicht anhaltend bewiesen.
Die wichtigste philosophische Implikation ist die wichtigste in der Geschichte der Philosophie (das ist keine Übertreibung):
Es existiert ein universeller Begriff des Rechnens, der unabhängig vom Axiomensystem ist.
Dies ist das Hauptergebnis von Gödels Arbeit, obwohl es einige Jahre später erst in Turings Version vollständig verstanden wurde. Aber Gödel tastete sich danach, da er nach dem Beweis des Theorems sehr schnell verstand, dass dies wahr war, und er erkannte, dass Turing die Erklärung geliefert hatte, und gab seinen eigenen Berechnungsansatz zugunsten von Turings auf. Der Grund, warum ich mit einem solchen Beweis wie oben durchkommen kann, liegt darin, dass wir alle mit den Begriffen „ein Computer“ und „ein Computerprogramm“ vertraut sind und wir alle wissen, dass jeder präzise Algorithmus auf einem Computer programmiert werden kann, und so weiter Ein Computer ist so gut wie der andere.
Unmittelbare philosophische Implikationen:
Es gibt eine übereinstimmende Vorstellung davon, was es bedeutet, ein genau definiertes Regelwerk zu haben.
Sie können tatsächlich eine Maschine bauen, die jedes andere genau definierte Regelwerk simulieren kann.
Jegliche zwei solcher Maschinen sind äquivalent – A kann B simulieren und B kann A simulieren.
Wenn Physik existiert (wenn es einen genauen Satz von Regeln gibt, sogar Wahrscheinlichkeitsregeln, um die Natur zu modellieren), kann die universelle Maschine (ausgestattet mit einem Zufallszahlengenerator) alles in der Natur simulieren.
Daraus folgt:
Das gesamte Verhalten des Menschen kann durch einen universellen Computer simuliert werden.
Mit der plausiblen logisch positivistischen Annahme bedeutet dies das
Ein Computer ist eine Maschine, die denken kann.
Diese Einsicht ist Turing zu verdanken. Von Neumann hat folgende Einsicht:
Ein Computer ist eine Maschine, die in der Lage ist, das Verhalten biologischer Systeme zu modellieren. Gödels Theorem ist analog zur Selbstreplikation.
Dies sind mit Abstand die wichtigsten philosophischen Erkenntnisse aller Zeiten. Der Vorläufer dazu ist der Versuch von Liebnitz, eine philosophische Maschine zu bauen, die mechanisch schlussfolgern könnte. Leibnitz verstand einige der Implikationen eines Computers.
Gödels Theorem zeigte, dass es, wenn man die philosophische Position einnimmt, dass die Aussage „Programm P hält nicht an“ absolut bedeutungsvoll ist, kein festes Axiomatiksystem gibt, das in der Lage wäre, all diese bedeutungsvollen Wahrheiten zu beweisen. Das ist irgendwie offensichtlich – das aus den Axiomen abgeleitete Programm kann widerspruchsfrei nicht zu viel über sich selbst beweisen.
Aber was noch wichtiger ist, es zeigt Ihnen, wie Sie stärkere Systeme produzieren können – indem Sie das Axiom „S ist konsistent“ anhängen, erhalten Sie ein neues System, das das System stärker macht. Das bedeutet, dass jedes Axiomensystem ein stärkeres hat, die Gödel-Reflexion
S + "S ist konsistent"
ist strikt stärker als S.
Sie können dieses Verfahren wiederholen, indem Sie die Gödel-Reflexion wiederholen. Es gibt keine Barriere im Unendlichen --- Sie können das System, das die unendlichste Gödel-Reflexion ist, als die Vereinigung aller auf der n-ten Stufe bewiesenen Theoreme betrachten (es gibt ein spezielles Programm, das die Ableitungen ausdruckt --- Sie brauchen keine Mengenlehre, um die Iteration präzise zu machen, zumindest nicht für unendlich kleine Ordinalzahlen). Der Prozess der Iteration von Gödels Reflexion reproduziert Cantors Ordinalzahlen.
Dies beantwortet die Frage der mathematischen Philosophie
Warum sind Ordnungszahlen notwendig?
Es rechtfertigt Cantors Mengenlehre vollständig. Cantors Mengenlehre ist erforderlich, um Gödel Reflexionen über Theorien nach Omega zu geben. Es rechtfertigt jedoch nicht die ganze Metaphysik, sondern nur die Ordnungszahlen hinter den ganzen Zahlen.
Wenn Sie die Ordnungszahlliste nach oben gehen, werden die Ordnungszahlen immer kompliziertere Computerprogramme (jede Ordnungszahl ist ein „Prozess“ in Paul Cohens Worten). Traditionell kann man den Grenzwert aller Ordnungszahlen definieren, die auf einem Computer innerhalb einer Mengentheorie dargestellt werden können, und dies wird als Chuch-Kleene-Ordnungszahl bezeichnet. Sie können sich der Church-Kleene-Ordnungszahl in der Komplexität nur annähern.
Nach Gödel bewies Gentzen die Konsistenz der Peano-Arithmetik innerhalb eines sehr begrenzten axiomatischen Systems (PRA – ein schwaches Fragment von PA) mit der zusätzlichen Annahme
Die Ordnungszahl Epsilon-Null ist wohlbegründet
Von diesem Zeitpunkt an war klar, dass Konsistenzbeweise komplizierter Theorien aus einfachen Theorien mit der einzigen komplexen Annahme der Fundiertheit einer bestimmten zählbaren berechenbaren Ordinalzahl erbracht werden können. Für PA war die Ordnungszahl nicht einmal allzu kompliziert, sodass es Fragen gibt (wie das Paris-Harrington-Problem oder das Hydra-Problem oder das Goodstein-Theorem), die der Fundiertheit von Epsilon-Null entsprechen, und so weiter innerhalb von PA nicht bewiesen werden können, aber der Konsistenz von PA äquivalent sind, also in jeder Theorie beweisbar sind, die die Konsistenz von PA beweisen kann.
Der Gegenstand der Ordinalbeweistheorie versucht, jeder mathematischen Theorie eine möglichst eindeutig beschreibbare Ordinalzahl zuzuordnen. Dieses Programm hat Erfolg mit bestimmten Mengentheorien, und es gibt kein Hindernis dafür, die Konsistenz jeder Theorie zu beweisen, egal wie unendlich. Also eine andere Implikation ist
Es ist möglich, Hilberts Programm zu vervollständigen und die Konsistenz von unzählbar unendlichen mathematischen Systemen zu beweisen, indem nur zählbare berechenbare Ordinalzahlen verwendet werden, die auf einem Computer dargestellt werden können.
Dieses Programm ist heute aktiv, hat aber noch nicht die Konstanz von ZF bewiesen. Dies liegt zum Teil daran, dass viele Leute weiterhin sagen, dass dies aufgrund des Satzes von Gödel nicht möglich ist.
Die Hauptannahme bei diesen Ideen ist, dass der Prozess der Erzeugung von Ordnungszahlen, die sich der Ordnungszahl von Church Kleene annähern, irgendwie verstanden werden kann, obwohl er nicht als Computerprogramm formalisierbar ist. Dieser Prozess ist ein Gewinn an Komplexität analog zur biologischen Evolution, und wie weit wir innerhalb unserer menschlichen Grenzen gehen können, ist nicht verstanden.
Es gibt viele falsche Implikationen von Gödels Theorem
Wir sind mehr als Computer
Diese Interpretation ergibt sich aus der Tatsache, dass wir verstehen können, dass ein Programm P nicht anhält (nämlich SPITE für ein gegebenes formales System), obwohl das formale System dies nicht kann. Um zu sehen, dass dies eine falsche Schlussfolgerung ist, müssen Sie sich nur ansehen, was SPITE tut: Es simuliert das System, sucht nach der Vorhersage und trotzt ihm! Es gibt keinen Grund, warum Sie das einer Person nicht antun können:
Wenn Sie eine Person simulieren können, können Sie ihre Wahl vorhersagen und trotz ihrer Entscheidung – so dass Sie nur dann eine Million Dollar in Box A legen können, wenn die Person Box B wählt.
Dies ist das genaue Analogon von Gödels Theorem im menschlichen Bereich, und es ist ein berühmtes philosophisches Problem. Es gibt auch Aussagen
John Searle kann diese Aussage nicht konsequent glauben
die genau analog sind, und die John Searle nicht glauben kann, obwohl es wahr ist. Um daraus eine logische Aussage erster Ordnung über Arithmetik zu machen, müssen Sie jedoch ein Rechenmodell von Searles Überzeugungen angeben, was aufgrund der Zufälligkeit möglicherweise nicht möglich ist. Aber die Idee ist dieselbe – die Dinge, die das Axiomensystem nicht wissen kann, aber wir wissen können, sind Dinge über das System selbst.
Es gibt weitere Konstruktionen aufgrund von Chaitin, die den Unvollständigkeitssatz wie folgt umformulieren
Kein Programm kann beweisen, dass eine beliebige Zeichenfolge eine Kolmogorov-Komplexität hat, die größer ist als die Länge des Programms plus eine feste Konstante
Aber in einer rechnerischen Sicht auf Menschen bedeutet dies nur, dass kein Mensch beweisen kann, dass eine Zeichenfolge eine Kolmogorov-Komplexität hat, die größer ist als die Komplexität eines Programms, das diesen Menschen simuliert. Da wir es selbst mit kleiner Kolmogorov-Komplexität so schwer haben, ist dies eine sichere Vorhersage.
Es gibt also keine Konsequenzen aus Gödels Theorem, die implizieren, dass die Computational Theory of Mind falsch ist. Es gibt andere Ideen
Der Satz von Gödel besagt, dass Semantik nicht formalisierbar ist
Das ist auch nicht ganz richtig – Gödels Theorem besagt, dass die Semantik des Anhaltens von Computerprogrammen nur annähernd axiomatisierbar ist, indem Systeme verstärkt werden, und der Prozess der Stärkung ist am oberen Ende nicht-algorithmisch. Aber die genaue Natur der Nicht-Algorithmik könnte so einfach sein wie die Benennung immer größerer berechenbarer zählbarer Ordinalzahlen, die sich der Church-Kleene-Ordnungszahl annähern, und dies könnte evolutionär auf vernünftige Weise möglich sein.
Der Satz von Gode tötet das Programm von Hilbert
insofern als Hilberts Programm eine Ordinalanalyse als Antwort auf Gödels Theorem entwickelt hat, ist dies nicht wahr. Es macht zwar eine naive Implementierung von Hilberts Programm unmöglich, aber die ordinalanalytische Sichtweise ist keineswegs naiv und genau die Art von Grundlagen, die man für eine unendlich reiche und unendlich komplexe Mathematik erwarten kann.
Ich denke, es gibt auch einige Konsequenzen für die Philosophie der Mathematik, insbesondere für die radikale formalistische Sichtweise, die Mathematik als ein rein formales Spiel ohne eigentliche Bedeutung betrachtet. Diese Ansicht hat ein Problem mit Gödels Ergebnis: Das Theorem zeigt tatsächlich, dass wir in der Lage sind, mathematische Schlussfolgerungen außerhalb jeder möglichen festen (und ausreichend starken) formalen Umgebung zu ziehen. Wenn Mathematik also nur „mit formalen Regeln spielt“, ist es nicht klar, wie man sie identifiziert diese Regeln auf vernünftige Weise, da alle möglichen Regeln, die Sie bereitstellen können, aufgrund von Gödels Ergebnis unangemessen schwach sind.
Keine Messung innerhalb des beobachteten Systems kann informativ vollständig sein.
Benutzer21820