Gödelsche Unvollständigkeitssätze

Kurt Gödel

Kurt Gödel war ein Mathematiker des 20.Jahrhunderts, der sich viel mit der Lehre der Logik in der Mathematik beschäftigte. So suchte er auch nach Antworten auf Hilberts Probleme und Fragen. Als Antwort auf das zweite Problem, "Sind die arithmetischen Axiome widerspruchsfrei?", entstanden die Unvollständigkeitssätze Gödels, auf welche im weiteren eingegangen wird.

Gödelsche Unvollständigkeitssätze

Veröffentlicht im Jahr 1931 besagen die Unvollständigkeitssätze als ganzes, dass es in hinreichend starken Systemen (Bsp. Arithmetik) Aussagen geben kann, von denen man weder beweisen, dass sie wahr sind, noch diese widerlegen kann. So besagt Gödels erster Unvollständigkeitssatz, dass es in allen widerspruchsfreien Systemen Aussagen gibt, deren Wahrheitsgehalt weder be- noch wiederlegt werden kann. Der zweite Satz besagt, dass man in widerspruchsfreien und hinreichend starken Systemen deren Widerspruchsfreiheit nicht beweisen kann.

Wir legen im folgenden den Fokus auf den ersten Unvollständigkeitssatz. Betrachtet man die Aussage dessen, so stellt sich die Frage: Was mache ich, wenn ich an einer wahren Aussage forsche, aber nicht weiß, ob sie überhapt belegbar ist? Hierzu ein kurzer geschichtlicher Abriss.

Bisheriges Verständnis

Wahr und Falsch

Seit dem antiken Griechenland ist man davon ausgegangen, dass alles mathematisch Wahre, auch innerhalb der Mathematik bewiesen werden kann. Gödel hat jedoch mit seinen Unvollständigkeitssätzen gezeigt, dass Wahr und Beweisbar nicht zwingend zusammenhängen müssen. Ein Beispiel dafür, dass man nicht sagen, oder besser beweisen kann, was wahr und was falsch ist, können wir aus unserem Alltag konstruieren. Betrachtet man ein Blatt Papier und schreibt auf die eine Seite, “Die andere Seite des Papiers ist wahr”, und auf jene angesprochene andere Seite, “Die andere Seite der Papiers ist falsch”, so findet man sich beim Versuch zu ergründen, welche Aussage nun stimmt, in einem Dilemma wieder, da man nicht sagen kann, welche Seite des Papiers nun “Recht” hat. Dies ist für uns im Alltag kein Problem, da wir nicht davon ausgehen, dass alle Aussagen wahr oder falsch sein müssen, oder sogar beweisbar wahr sind. Gödel sagt jedoch, dass ein solches Dilemma auch in der Mathematik auftreten kann - nun wird daraus in der Mathematik tatsächlich ein Problem. Denn wir verlangen von mathematischen Systemen Konsistenz, das heißt, dass jede Aussage entweder wahr oder falsch ist. In anderen Worten sollen mathematische Systeme widerspruchsfrei sein. Gödel hinterfragt also die Vollständigkeit der Mathematik und zeigt letztendlich, dass ausreichend komplexe mathematische Systeme unter Annahme von Konsistenz nicht vollständig sein können.

Wie bereits erwähnt, war dieser Tatbestand der Vollständigkeit der Mathematik eines der Probleme Hilberts: “Prove Math is consistent” Kurt Gödel hat dieses Problem mit seinem Unvollständigkeitssatz gelöst, oder besser gesagt widerlegt, indem er beweisen hat, dass Mathematik nicht vollständig ist.

Doch genug der Geschichtsstunde, betrachten wir nun, was Gödel eigentlich herausgefunden hat.

Versuchte Erklärung der Beweisidee

Um den Beweis von Gödel zu verstehen, müssen wir zuerst einen kurzen Blick auf die generelle Beweisstruktur der heutigen Mathematik werfen. Die Grundlage der verwendeten Mathematik sind festgelegte Axiome, wie z.B.: “a+b=b+a”. Hat man nun eine mathematische Aussage, so versucht man diese aus den festgelegten Axiomen zu beweisen oder zu widerlegen. Findet man dabei etwas, das immer gültig ist, jedoch nicht bewiesen werden kann, so macht man es zu einem neuen Axiom, einem als Wahr angesehenen Grundbaustein der Mathematik. Bisher war man also der Ansicht, dass wenn man nur genügend Axiome hat, alle Aussagen beweisbar sind, oder besser gesagt irgendwann alle Axiome gefunden sind und alles bewiesen werden kann. Kurzum man ist davon ausgegangen, dass die Mathematik irgendwann vollständig abgeschlossen ist.

Betrachten wir nun, was Gödel in seinem Beweis macht. Seine Idee war es, die Mathematik in Zahlen umzuformen und dann, durch beispielsweise Primfaktorzerlegung, allen Aussagen Nummern zuzuordnen, die unfehlbar nach Dekodierung, auf die Nummern der Axiome zurückführen, und somit die Aussagen beweisen. Als erstes führt er hierfür den sogenannten Gödelcode, oder auch Gödelnumbering ein, womit er jedem Axiom und jeder Aussage, nach einem festgelegten Prinzip eine Nummer, die Gödelnummer, zuordnet. Diese Nummern werden dabei sehr groß, da jede Aussage ihre eigene individuelle Gödelnummer bekommt. Ein Beispiel aus der heutigen technologisierten Welt ist der Ascii-Code, der jedem Buchstaben, Sonderzeichen oder Smiley eine bestimmte vom Computer auslesbare Kombination gibt. Wie auch beim Ascii-Code sorgt eine Zusammensetzung der einzelnen Axiome oder auch Aussagen für eine größere Nummer. So kann beispielsweise ein Smiley durch Kombination mit einer Farbe in unterschiedlichen Gesichtsfarben dargestellt werden. Damit hat Gödel sein Primärziel erreicht. Er kann nun mit Mathematik, als festgelegtes äußeres System Aussagen über die in Gödelnummern festgelegte Mathematik treffen. Vereinfacht gesagt, man kann aus den Nummern bestimmen, ob eine Aussage aus den Axiomsnummern zusammengesetzt werden und damit bewiesen werden kann oder nicht.

Hier lohnt es sich ein kurzes Beispiel anzusehen. In dem System von Gödel das von Nagel und Newman verwendet wird, ist die 0 eine 6 und das Ist-Gleich-Zeichen die 5. Will man also 0=0 in dem System schreiben so findet sich das unter der Nummer 2⁶ * 3⁵ * 5⁶ = 243,000,000.

Kommen wir nun zu einer Aussage, die das ganze problematisch werden lässt und zeigt, dass Mathematik eben doch nicht vollständig ist und es weitergeführt auch niemals sein wird. Diese Aussage lautet: “Diese Aussage kann nicht aus den Axiomen bewiesen werden”. Gehen wir nun als erstes davon aus, dass diese Aussage falsch ist, so muss sie aus den Axiomen beweisbar sein. Dies wäre aber ein Widerspruch, denn wir nehmen an, dass in widerspruchsfreien Systemen nur wahre Aussage bewiesen werden können. Ist dies nicht der Fall, so muss die Aussage, da sie mit Mathematik beschrieben wurde zwingend richtig sein, da es nach unserem Verständnis in der Mathematik beim rechnen, in diesem Fall mit den Gödelnummern, nur Richtig oder Falsch gibt. Wir haben also in unserem mathematischen System eine Aussage gefunden, die zwar richtig ist, jedoch nicht aus den Axiomen nachgewiesen werden kann. Wichtig hierbei ist, dass wir diese Aussage nur als Wahr klassifizieren können, da wir die Mathematik von außerhalb mit sich selbst betrachtet haben. In dem eigentlich betrachteten System, der in den Gödelnummern festgelegten Mathematik, in dem die Aussage “lebt”, kann diese weder widerlegt noch bewiesen werden, obwohl wir von Außerhalb wissen, dass sie wahr ist. Wir haben also eine Aussage wahren Inhalts gefunden, die innerhalb eines abgeschlossenen mathematischen Systems nicht bewiesen werden kann. Wir haben bereits erwähnt, dass eine solche Aussage dann als Axiom festgelegt wird. Wenn wir erneut eine solche Aussage finden, dann wird auch diese als Axiom mit aufgenommen, bis es nicht mehr möglich ist eine derartige Aussage zu finden. Nun hat Gödel gezeigt, dass es unendlich viele Aussagen dieses Typus gibt, also die Mathematik niemals vollständig sein kann. Damit wird es immer Aussagen geben die zwar wahr sind, jedoch nicht bewiesen werden können.

Bedeutung für Mathematiker heute

Betrachtet man nun die Auswirkungen von Gödels Unvollständigkeitssätzen auf die heutige Zeit, so fällt auf, dass diese obwohl sie die Mathematik in ihren Grundfesten erschüttert haben, man kann nicht mehr davon ausgehen für alles eine Lösung zu finden und die Mathematik wird niemals fertig sein, für die eigentliche Forschung an aktuellen Problemen nur bedingte Auswirkung hat. Dies ist auch gut so, denn wenn beispielsweise jeder Mathematiker nach einer Woche sagen würde, "Das Forschungsgebiet taugt nichts, das ist doch wahrscheinlich nicht beweisbar", dann würde die Mathematik als solche keine Fortschritte mehr machen. Somit ändert Gödels Feststellung der unvollständigen Mathematik an der aktuellen Forschung und Problemlösung nur in sofern etwas, dass man immer im Kopf behalten sollte, dass es möglicherweise in letzter Konsequenz doch keinen Beweis der These gibt, und man vielleicht in Betracht ziehen sollte zu überprüfen, ob die These überhaupt beweisbar ist. Auf der anderen Seite hat Gödel jedoch damit ein neues umso unvorhersehbareres Forschungsgebiet eröffnet, welches in der Vergangenheit bereits erstaunliche Ergebnisse geliefert hat und dies hoffentlich auch in Zukunft noch tun wird.

Neue Beweismethode

Eine Folge Gödels Ergebnisse, welche man vielleicht als etwas seltsam bezeichnen könnte ist die Möglichkeit zu beweisen, dass etwas innerhalb von einem Axiomsystem nicht widerlegbar oder nicht beweisbar ist. Dies ermöglicht eine neue Beweismethode. Sollte man zum Beispiel beweisen können, dass Die Riemannsche Vermutung innerhalb unseres Axiomsystems nicht entscheidbar ist, würde dies allgemein implizieren, dass die Vermutung wahr sein muss. Denn wäre sie falsch, dann gäbe es sofort eine implementierbare Methode in unserem System, welche ein Gegenbeispiel, eine nichttriviale Null außer den kritischen Streifen, finden kann.

Beispiele für Gödels Sätze

Nachdem wir nun den Inhalt, sowie das Konzept der Unvollständigkeitssätze betrachtet haben, möchten wir abschließend noch den Blick auf zwei Beispiele für das unvorhersagbare, oder auch unbeweisbare liefern.

Kontinuumshypothese

Die Frage

Die Kontinuumshypothese wurde in 1878 vom Mathematiker Georg Cantor aufgestellt und beinhaltet eine Vermutung über die Mächtigkeit des Kontinuums, alse der Menge der reellen Zahlen.

In der einfachen Formulierung besagt die Hypothese, dass es keine Menge gibt, deren Mächtigkeit zwischen der Mächtigkeit der natürlichen Zahlen und der Mächtigkeit der reellen Zahlen liegt.

Lösung aber keine Antwort

Gödel beweis in 1938, dass die Kontinuumshypothese zur Zermelo-Fraenkel-Mengenlehre mit Auswahlaxiom (ZFC) widerspruchsfrei ist. (Unter der Annahme dass ZFC widerspruchsfrei ist) Also dass man im Rahmen der ZFC die Kontinuumshypothese nicht widerlegen kann. Ungefähr zwanzig Jahre später zeigte Paul Cohen das Gegenteil, dass man mit ZFC die Kontinuumshypothese nicht beweisen kann. Insgesamt war somit die Lösung Cantors Fragestellung, dass die Kontinuumshypothese im Rahmen von ZFC nicht lösbar ist. Da sowohl die Kontinuumshypothese und ihre Negation beide ohne Widerspruch als neue Axiome ZFC erweitern konnten. Damit ist sie eines der ersten relevanten Beispiele für Gödels ersten Unvollständigkeitssatz.

Qual der Wahl

Die Arbeit um die Kontinuumshypothese war damit aber längst nicht fertig. Denn Frage welche in der Kontinuumshypothese an sich gestellt wurde, blieb immer noch. Was ist die genaue Mächtigkeit des Kontinuums? Und da ZFC als eine nicht ausreichende Liste an Axiomen, um diese Frage zu beantworten sich herausgestellt hat, mit welchen Axiomen soll ZFC ergänzt werden, um die Frage beantworten zu können. Das ist ein gutes Beispiel für die Auswirkungen Gödels Gesetzte. Nur weil eine Frage innerhalb eines Axiomensystems nicht beantwortet werden kann, muss nicht heißen, dass keine Antwort existiert. “The axioms do not settle these problems so we must extend them to a richer axiom system.” - Menachem Magidor Hier fängt aber die Diskussion an, womit das System ergänzt werden soll. Die suche nach “richtigen” Axiomen stellt sich als besonders schwer. Denn -- als Gödel bewiesen hat -- jedes ausreichend komplexes Axiomensystem wird unvollständig sein. Somit gibt es keine “richtigen” Axiomen und die Auswahl zwischen zwei besonders guten Vorschlägen kann sehr schwer sein. Im Fall der Kontinuumshypothese ist das ein aktuelles, offenes Problem.

Neuer Fortschritt

Zwei gute Axiome haben sich herausgestellt, das “Martin’s maximum++” und “(*)”. Jedoch hat die beide Axiomen bisher als sich gegenseitig ausschließend verstanden. Nun gaben die kürzliche Ergebnisse von Ralf Schindler und David Asperó, einen Grund um anders zu denken. Die beide Mathematiker behaupten, die könnten eine Implikation zwischen den beiden Axiomen beweisen. Sollte der Versuch gelingen, würden sich die Axiomen nicht widersprechen und man könnte eins wählen, ohne die Vorteile des anderen aufgeben zu müssen. Sollte das passieren und das neue Axiom aufgenommen sein, so wäre die Mächtigkeit der Kontinuums als Aleph 2 festgelegt. Auf der anderen Seite arbeitet Hugh Woodin auf einer Lösung welche die Mächtigkeit auf Aleph 1 setzen würde. Sein sogenanntes “Ultimate L” Modell sollte eine Verallgemeinerung Gödels Mengenlehre.

Game of Life

Grundlagen

Ein weiteres Beispiel wäre das “Game of Life” von John Horton Conway, bei diesem "Kein Spieler Spiel", gibt es ein unendliches Spielbrett, auf welchem zu Beginn beliebig Spielsteine platziert werden können. Dann wird das Spiel oder die “Simulation” gestartet. Jede Runde entstehen oder verschwinden die Spielsteine. Hierbei wird ein Feld, auf welchem ein Spielstein liegt, als lebend und ein Feld ohne Spielstein als tot bezeichnet. Nun verändert sich das Spielfeld, bzw. die Verteilung der Stein zu Beginn jeder Runde nach folgenden Regeln:

Eine totes Feld mit genau drei lebenden Nachbarn wird in der folgenden Runde neu “geboren”, also mit einem Spielstein besetzt.
Lebende Felder mit weniger als zwei lebenden Nachbarn sterben in der folgenden Runde an Einsamkeit, also wird der Spielstein entfernt.
Ein “lebendiges” Feld mit zwei oder drei lebenden Nachbarfeldern bleibt in der Folgegeneration am Leben. Es passiert also nichts mit dem Feld.
Lebende Felder mit mehr als drei lebenden Nachbarfeldern sterben in der Folgegeneration an Überbevölkerung, also wird der Spielstein entfernt.
Tote Felder ohne Nachbarn bleiben tot.

Jede Runde ist im übertragenen Sinne eine Generation. Nun wird das Spiel gestartet und das Spielfeld verändert sich in jeder Runde. Hierbei können aus unterschiedlichen Anfangskonstellationen unterschiedliche Formationen entstehen. Dabei gibt es prinzipiell drei mögliche Ausgänge der Simulation.

Es entstehen konstante Konstellationen, die nach einer gewissen Anzahl wieder in einer bereits durchlaufenen Konstellation auftauchen. Diese können statisch sein, oder sich über das Feld bewegen.
Es werden immer mehr Felder besetzt.
Es sterben immer mehr Zellen, bis das Spielfeld letztlich leer/tot ist.

Beispiele:

Konstante Konstellationen:

Statische:
Statische Konstellationen
Statische Konstellation 1
Statische Konstellation 2
Statische Konstellation 3
Statische Konstellation 4
Statische Konstellation 5
Statische Konstellation 6

Oszillierende:
Blinker
2 Laser
Fontäne
Pulsator

Wandernde/Raumschiffe:
Gleiter

Segler

Erzeugende Konstellationen

Gleiterkanone:
Gleiterkanone mit Gleiterfresser

Sterbende Konstellationen

Verschiedene Möglichkeiten, Beispiel einfaches Feld

Das unvorhersagbare an diesem Beispiel ist, dass man aus der Anfangskonstellation nicht vorhersagen kann was passieren wird, ausgenommen bereits bekannte Konstellationen. Um also herauszufinden was mit einer bestimmten Konstellation passiert, muss diese solang laufen lassen, bis man eine statische oder oszillierende, eine nach festem Prinzip wachsende, oder eine nicht mehr existente Konstellation gefunden hat. Hierbei bringt es nichts einfach zu sagen, diese Konstellation hat jetzt 100 Generationen Überlebt, deshalb überlebt sie für immer. So kann eine riesige Konstellation die nach einer Millionen Lebenszyklen noch lebt, nach beispielsweise einer weiteren Millionen Generationen vollständig verschwunden sein.

Hierfür ein Beispiel, das auch der Intuition widerspricht ist das r-Pentomino, welches am Anfang ein chaotisch wachsendes Muster aufweißt und nach 1103 Generationen dann ein fast vollständig statisch oder oszillierendes Spielfeld hinterlässt, Ausnahme sind ein paar wegfliegende Gleiter.

R-Pentomino
Animation über 1200 Generationen

Wer möchte kann es hier selbst versuchen: Game of Life spielen

Was das Game of Life kann

Eine letzte interessante Information ist noch, dass man inzwischen festgestellt hat, dass es möglich ist, in Conways Game of Life, Schaltungen wie "und" und "oder" zu bauen, und es sogar gelungen ist das Game of Life im Game of Life zu bauen, was bedeutet, dass das Game of Life "Turing complete" ist. Dies geht nun aber tatsächlich weit über das eigentliche Thema der Unvollständigkeitssätze hinaus. Deshlab wollen wir das Thema hiermit beenden.