» Der Gödelsche Unvollständigkeitssatz ist einer der wichtigsten Sätze der modernen Logik. Er beschäftigt sich mit der Ableitbarkeit von Aussagen in Formalen Sprachen. Der Satz zeigt die Grenzen der formalen Systeme ab einer bestimmten Mächtigkeit auf und weist nach, dass es in hinreichend mächtigen Systemen (wie der Arithmetik) Aussagen gibt – und geben muss – die man weder formal beweisen, noch widerlegen kann.



In der Wissenschaftstheorie und in Gebieten, die sich mit dem Phänomen von bewussten Entscheidungen im Unterschied zu berechenbaren auseinandersetzen, sowie anderen philosophischen Disziplinen, die auf deren Erkenntnisse aufbauen, zählt der Satz zu den meistrezipierten der Mathematik. Das Buch Gödel Escher Bach und die Werke von John Randolph Lucas, der versuchte eine Theorie der Menschenrechte mit der Aussage zu zeigen, werden in dem Zusammenhang, zusammen mit ihren ebenso zahlreichen Kritikern, gern exemplarisch herausgehoben. Der Satz wurde zuerst in der Arbeit von Kurt Gödel formuliert und bewiesen: Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I. in: Monatshefte für Mathematik und Physik 38 (1931), S. 173 ff.





Grundbegriffe



Aussagen sind dabei Folgen von Zeichen, die ähnlich wie ein Programm einer Programmiersprache einer gewissen Syntax genügen müssen und die mittels einer Semantik eine Bedeutung erhalten und sich dadurch in wahre und falsche Aussagen unterteilen lassen (wobei zu einer gegebenen Aussage nicht unbedingt sofort klar ist, ob sie wahr oder falsch ist). Für gewöhnlich lassen sich dabei zu einer Aussage auch leicht komplementäre Aussagen derart konstruieren, dass entweder die Aussage selbst oder die komplementäre Aussage wahr ist, aber niemals beide zugleich.



Die Aufgabe einer formalen Theorie ist es dann, aus bestimmten Grundaussagen (Axiome), die generell als wahr angenommen werden, über allgemein akzeptierte Ableitungsregeln weitere wahre Aussagen abzuleiten. Eine Folge solcher Ableitungen nennt man dann Beweis der entsprechenden abgeleiteten Aussage, da sie die Allgemeingültigkeit der Aussage zeigt (siehe Gödelscher Vollständigkeitssatz). Im Idealfall wünscht man sich, dass aus der Menge der Grundaussagen und den Ableitungsregeln alle wahren Aussagen abgeleitet, also bewiesen werden können. Ein derartiges System nennt man dann vollständig (andernfalls unvollständig). Eine formale Theorie sollte zudem auch widerspruchsfrei sein, das heißt, es lassen sich keine falschen Aussagen ableiten. Genauer formuliert, lassen sich nicht gleichzeitig eine Aussage und eine dazu (im obigen Sinne) komplementäre Aussage ableiten. Eine formale Theorie, die dem nicht genügt, nennt man widersprüchlich.





Gödels Satz



Satz



Der Mathematiker Kurt Gödel wies mit seinem im Jahre 1931 veröffentlichten Unvollständigkeitssatz nach, dass man in (hier stets als rekursiv aufzählbar vorausgesetzten) Systemen wie der Arithmetik nicht alle Aussagen formal beweisen oder widerlegen kann. Sein Satz besagt:

• Jedes hinreichend mächtige formale System ist entweder widersprüchlich oder unvollständig.

Eine einfache Formulierung des ersten Unvollständigkeitssatzes sowie des daraus unmittelbar folgenden zweiten Gödelschen Unvollständigkeitssatzes lautet:

• In jedem formalen System der Zahlen, das zumindest eine Theorie der Arithmetik der natürlichen Zahlen (\N) enthält, gibt es einen unentscheidbaren Satz, also einen Satz, der nicht beweisbar und dessen Negierung ebenso wenig beweisbar ist. (1. Gödelscher Unvollständigkeitssatz).

Daraus folgt unmittelbar, dass kein formales System der Zahlen, das zumindest eine Theorie der natürlichen Zahlen (\N) samt Addition und Multiplikation enthält, sich innerhalb seiner selbst als widerspruchsfrei beweisen lässt (2. Gödelscher Unvollständigkeitssatz).





Beweis des 1. Unvollständigkeitssatzes



Gödels Argumentation läuft auf eine Abzählung aller Sätze innerhalb des formalen Systems hinaus, jeder Satz erhält eine eigene Nummer. Er konstruiert dann mit Hilfe einer Diagonalisierung eine Aussage der Form: „Der Satz mit der Nummer x ist nicht ableitbar“ und zeigt, dass es eine Einsetzung für x gibt, so dass x die Nummer dieser Aussage ist. Insgesamt erhält er einen Satz der Form „Ich bin nicht ableitbar“. Es gibt nun zwei Möglichkeiten: Entweder dieser „Satz x“ ist wahr, dann ist er nicht ableitbar (genau das ist sein Inhalt: Ich bin nicht ableitbar!). Oder „Satz x“ ist falsch, dann muss der Satz ableitbar sein. Ein formales System, aus dem ein falscher Satz abgeleitet werden kann, ist aber widersprüchlich. Demnach kann dieser Satz nur wahr sein, wenn das formale System unvollständig ist, oder falsch, wenn das formale System widersprüchlich ist (siehe hierfür auch das klassische Problem des Lügner-Paradox).



Man beachte: Falls das formale System nicht widersprüchlich ist, ist der Satz mit Nummer x und der Bedeutung „Satz x ist nicht ableitbar“ damit gezeigt. Wir vertrauen auf diesen „Beweis“, obwohl es innerhalb des Systems keine Ableitung gibt, die zu diesem Satz führt.



Damit obiger Ansatz funktioniert, muss das zugrundegelegte formale System also mindestens Zählungen und eine Multiplikation mit einer Konstanten größer als 1 (für Kodierungszwecke) erlauben. Für zu einfache Systeme gilt der Unvollständigkeitssatz daher nicht. Die Möglichkeit von Addition und Multiplikation sind ganz wesentliche Eigenschaften in vielen Theorien, so dass hier dieser Satz gilt. Insbesondere muss aber eine Substitution wie im Beweis Gödels möglich sein. Es gibt sehr einfache Systeme, für die diese Bedingungen erfüllt sind.



Nun könnte man sich dadurch behelfen, dass man für alle Sätze, die weder bewiesen noch widerlegt werden können, einfach festlegt, ob sie als wahr oder falsch gelten. Das formale System würde dann durch diese zusätzlichen Axiome erweitert. Lesen wir jedoch erneut den Unvollständigkeitssatz, so sehen wir, dass auch hier die Voraussetzungen erfüllt sind und somit auch das erweiterte System unvollständig bleibt, da stets unbeweisbare Sätze übrigbleiben.





Bedeutung des Unvollständigkeitssatzes



Gödel versetzte mit seinem Unvollständigkeitssatz einem Ansatz von David Hilbert zur vollständigen Begründung und Formalisierung der Mathematik einen schweren Schlag. Dieser Ansatz ist als Hilbertprogramm bekannt geworden und wurde von ihm im Jahre 1921 veröffentlicht. Hilbert hatte vorgeschlagen, die Widerspruchsfreiheit von komplexeren Systemen durch diejenige einfacherer Systeme nachzuweisen. Hintergrund ist der, dass einem Beweis zur Widerspruchsfreiheit eines Systems, der in diesem System selbst gegeben ist, nicht getraut werden kann. Der Grund ist, dass sich aus einem Widerspruch heraus alles beweisen lässt (Ex falso quodlibet), also ließe sich aus einem Widerspruch im System auch die Widerspruchsfreiheit des Systems beweisen. Daher sollte die Widerspruchsfreiheit in einem einfacheren System bewiesen werden.



Eine streng formalisierte Prädikatenlogik erster Stufe war eines von Hilberts Konzepten. Am Ende seines Programms sollte die gesamte Mathematik auf die einfache Arithmetik zurückgeführt und auf ein axiomatisches System gestellt werden, aus dem alle mathematischen Sätze streng ableitbar sind.



Gödels Arbeit war durch Hilberts Programm motiviert. Er verwendete die von Hilbert vorgeschlagenen Methoden, um seinen Unvollständigkeitssatz zu zeigen. Gödel bewies auch den folgenden Satz

• Ein System kann nicht zum Beweis seiner eigenen Widerspruchsfreiheit verwendet werden.

Gödel hatte damit gewissermaßen Hilbert mit dessen Methoden gezeigt, dass der Vorschlag nicht funktioniert.



Die Folge daraus ist, dass man die Korrektheit von (gewissen) formalen Systemen als gegeben annehmen muss, sie lassen sich nicht beweisen.



Ein anderer Ansatz, der unüberbrückbare Lücken in Hilberts Programm nachweist, stammt von dem Mathematiker Alan Turing. Er erfand die Turingmaschine und formulierte deren Halteproblem.





Philosophische Interpretationen



Obwohl Gödel sich im Laufe seines Lebens wiederholt als Platoniker zu erkennen gab, wurde sein Unvollständigkeitssatz wiederholt in einem subjektivistischen Sinn interpretiert. Auch schien Gödels Teilnahme am Wiener Kreis eine Nähe des Unvollständigkeitssatzes mit dem logischen Positivismus nahezulegen, der dem Platonismus in vielerlei Hinsicht entgegengesetzt ist. Gödels zurückhaltende, konfliktscheue Art trug dazu bei, die Fehlinterpretationen am Leben zu erhalten.



Gödel selbst verstand seinen Satz jedoch insbesondere als einen Schlag gegen den von Hilbert propagierten Formalismus in der Mathematik, der in letzter Konsequenz die gesamte Mathematik zu einem rein formalen Gebilde ohne Bezug zur „realen Welt“ machen sollte. Für Gödel als Platoniker waren jedoch die mathematischen Objekte durchaus „real“. Sie waren zwar nicht durch Sinneswahrnehmungen zu bestätigen (wie es die Positivisten einforderten), doch waren sie der Erkenntnis zugänglich. Der Unvollständigkeitssatz zeigte für Gödel, dass man dieser Realität nicht mit rein formalen Mitteln beikommen konnte.



Obwohl Gödel sich in seiner Grundhaltung gegenüber dem damals bedeutsamen logischen Positivismus nicht sehr von Ludwig Wittgenstein unterschied, der eine Realität jenseits der möglichen Bedeutung von Sätzen anerkannte (und sie sogar für wichtiger hielt als das Sagbare), hielten Wittgenstein und Gödel Zeit ihres Lebens nicht viel voneinander. In Wittgensteins Werk wird der Unvollständigkeitssatz eher abschätzig behandelt. Für Wittgenstein taugte der Satz lediglich für „logische Kunststücke“. Gödel hingegen wies in späteren Interviews jeglichen Einfluss Wittgensteins auf sein eigenes Denken weit von sich. «