Gödels zweiter Unvollständigkeitssatz und die Kontinuumshypothese
BLOG: Die Sankore Schriften
Nach 26 Jahren harter Arbeit veröffentlichten Bertrand Russel und Alfred North Whitehead 1910 die Principia Mathematica, eines der einflussreichsten Bücher in der Geschichte der Mathematik. Im ersten Band dieses Werkes, für den sie allein 12 Jahre brauchten, kommen sie zu einer fundamentalen Einsicht, deren praktischen Implikationen bis heute die Gemüter bewegen.
BOAH, Wer hätte das gedacht?
Das Russell-Paradox und die Typentheorie
Ok, ganz so trivial geht es im Rest des Bandes nicht zu. Denn die Principia war eine Antwort auf und die Weiterentwicklung von Freges 1879 publizierter “Begriffsschrift”. Gottlob Frege war der Begründer eines neuen mathematikphilosophischen Programms, des Logizismus, dem zufolge die Sätze der Arithmetik sich auf logische Wahrheiten zurückführen lassen. Die in der Principia entwickelte Typentheorie war eine Antwort auf den Widerspruch, den Russell in Freges typenfreiem System entdeckt hatte – das bekannte Russell-Paradox von der Menge aller Mengen, die sich nicht selbst als Element enthalten. In der Typentheorie hat eine Menge stets einen höheren Typ als ihre Elemente. Aussagen wie „diese Menge enthält sich selbst als Element“, mit der das Russell-Paradox gebildet wird, lassen sich in dieser Theorie gar nicht formulieren. (Gelöst wurde das Russell-Paradox 1908 axiomatisch von Ernst Friedrich Ferdinand Zermelo, indem er ein System entwickelte, welches sorgfältig die Existenz und Bildung bestimmter Mengen aus anderen Mengen beschreibt.)
Gödels zweiter Unvollständigkeitssatz und die Principia Mathematica
Doch auch die Principia wies einen Mangel auf den Kurt Gödel 1931 in seiner Arbeit ¨Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I“ aufdeckte. Der zweite Unvollständigkeitssatz aus dieser Arbeit besagt, grob gesprochen: In einer ”vernünftigen“ widerspruchsfreien Theorie, die die Arithmetik umfasst, ist die Widerspruchsfreiheit dieser Theorie nicht herleitbar.
Gödels zweiter Unvollständigkeitssatz und die Kontinuumshypothese
Gödel bewies diesen Satz auf abstrakte Weise, also ohne ein konkretes Beispiel für eine solche prinzipiell unbeweisbare Aussage zu kennen. Es lag nun nahe, sich der ungelösten Mathematikprobleme aus Hilberts Programm anzunehmen und zu untersuchen, ob vielleicht eines dieser Probleme eine solche Aussage enthält. Zu Beginn des Zwanzigsten Jahrhunderts forderte David Hilbert, die Mathematik endlich auf eine ordentliche, exakte Grundlage zu stellen und zu betreiben. Auf dem zweiten internationalen Mathematiker-Kongress in Paris 1900 stellte er 23 wichtige, damals ungelöste, Probleme vor, die im kommenden Jahrhundert gelöst werden sollten. Dabei forderte er, dass ein Problem erst dann als gelöst betrachtet werden solle, wenn es entweder mit vollständiger Exaktheit auf axiomatischer Grundlage gezeigt oder aber mit vollkommener Präzision seine Unlösbarkeit bewiesen worden ist. Die Widerspruchsfreiheit der Arithmetik war das zweite Hilbertsche Problem. Hilbert wollte die gesamte „klassische“ Mathematik und Logik bewahren, ohne dabei auf Cantors Mengenlehre zu verzichten. Er sagte damals:
„Aus dem Paradies, das Cantor uns geschaffen, soll uns niemand vertreiben können.“
Gödel suchte also unter Hilberts Problemen nach einem konkreten Beispiel für seinen zweiten Unvollständigkeitssatz. Sein erster Verdächtiger war die Kontinuumshypothese, die auf Georg Cantor zurückgeht. Cantor fragte sich: “Sind alle unendlichen Mengen von gleicher Mächtigkeit, oder gibt es verschiedene Mächtigkeiten unter den unendlichen Mengen?” Dabei sind zwei Mengen gleich mächtig, wenn sich jedes Element der einen Menge eindeutig einem Element der anderen Menge zuordnen lässt, ohne dass in einer der beiden Mengen Elemente übrig bleiben. Cantor fand heraus, dass in diesem Sinn die Menge der natürlichen Zahlen und die Menge der Brüche (rationale Zahlen) gleich mächtig sind. Die reellen Zahlen sind dagegen mächtiger als die natürlichen Zahlen, denn man kann die reellen Zahlen nicht vollständig durchzählen — sie sind überabzählbar. Das kann mit Cantors zweitem Diagonalargument bewiesen werden.
Es ist nun naheliegend, die folgende Frage zu stellen: “Gibt es eine Menge, die in ihrer Mächtigkeit zwischen den natürlichen Zahlen und den reellen Zahlen (die man auch als Kontinuum bezeichnet) liegt?” Gibt es also eine Menge, die sich nicht komplett durchnummerieren lässt, die sich aber auch nicht eins-zu-eins den reellen Zahlen zuordnen lässt, ohne dass reelle Zahlen übrig bleiben? Da es Cantor nicht gelang, eine solche Menge zu konstruieren, formulierte er im Jahr 1878 seine berühmte Kontinuumshypothese:
Es gibt keine Menge, die in ihrer Mächtigkeit zwischen den natürlichen Zahlen und den reellen Zahlen (dem Kontinuum) liegt.
David Hilbert hielt die Kontinuumshypothese für so bedeutend, dass er sie in seinem berühmten Vortrag zu seinem ersten Problem machte. Gödel gelang es 1937 zu beweisen, dass sich die Kontinuumshypothese im Rahmen der Mengenlehre nicht widerlegen lässt. Sie ist also mit allen Sätzen der Mengenlehre* vereinbar.
Das heißt noch nicht, dass sie bewiesen ist. Dazu müsste man zusätzlich nachweisen, dass ihr Gegenteil mit den Sätzen der Mengenlehre nicht vereinbar ist. Gödel kam mit der Kontinuumshypothese nicht weiter. Erst 1963 konnte Paul Cohen nachweisen, dass auch ihr Gegenteil widerspruchsfrei zur Mengenlehre ist. Für diesen Beweis erhielt Cohen die Fields-Medaille. Die Kontinuumshypothese ist damit im System der Mengenlehre unentscheidbar – weder wahr noch falsch. Die Kontinuumshypothese ist also insgesamt unabhängig von der Mengenlehre. Sie ist eines der ersten konkreten Beispiele für Gödels Unvollständigkeitssatz. Cantor hatte also mit all seinen Beweisversuchen im 19. Jahrhundert nie eine Chance. Allerdings ist das Problem nicht in dem Sinne gelöst worden, wie es Hilbert erwartet hatte.
Es ist schon seltsam wir sind daran gewöhnt, zu denken: Entweder etwas existiert oder etwas existiert nicht. Eine dritte mögliche Position existiert nicht (Satz vom ausgeschlossenen Dritten, lat. principium exclusi tertii). Es ist nicht möglich, dass etwas gleichzeitig existiert und nicht existiert (Nichtwiderspruchsprinzip, lat. principium contradictionis).
Und dann hauen uns Cantor, Gödel und Cohen sowas um die Ohren…….
„Die Mathematik ist die Königin der Wissenschaften, und die Arithmetik ist die Königin der Mathematik.“
Carl Friedrich Gauß
Ergänzung für Mathefreaks
*Mit Mengenlehre ist hier die moderne axiomatische ZFC-Mengenlehre gemeint. Sie beruht auf Zermelos Axiomensystem das später durch die Hinzunahme zweier weiterer Axiome (eines von Adolf Abraham Halevi Fraenkel und eines von Ernst Friedrich Ferdinand Zermelo und John von Neumann ergänzt wurde. Seitdem ist es unter der Abkürzung ZF bekannt. Später wurde die in dem System verwendete Sprache präzisiert und durch Hinzunahme des Auswahlaxioms (axiom of choice) die Zermelo-Fraenkel-Axiomatik (ZFC) als Grundlage der heutigen Mengenlehre geschaffen. ZFC besteht aus insgesamt 10 Axiomen.
Das Extensionalitätsaxiom (EXT) beispielsweise sagt aus, dass zwei Mengen genau dann gleich sind, wenn sie die gleichen Elemente haben. Dies hört sich zwar ziemlich trivial an, muss jedoch in das Axiomensystem aufgenommen werden, da es keine Möglichkeit gäbe, diese Behauptung nur anhand der anderen Axiome zu beweisen. Ein weiteres Axiom, das Paarmengenaxiom (PA), besagt, dass zu je zwei Mengen x, y eine Menge z existiert, die genau x und y als Elemente enthält. Paul Cohen zeigte, dass das Auswahlaxiom nicht aus den Zermelo-Fraenkel-Axiomen folgt.
Schöner Beitrag
Gefällt mir 🙂
Eine kleine Anmerkung trotzdem noch zu dem “weder wahr noch falsch”. Widerspruchsfreiheit wird ja über Beweisbarkeit (Syntax) definiert, nicht über Wahrheit (Semantik). Will sagen, ein Kalkül heisst widerspruchsfrei, wenn die Beweisbarkeit von A stets die Unbeweisbakeit von ¬A impliziert. Auch Entscheidbarkeit ist normalerweise auf beweisbar/unbeweisbar bezogen (wenngleich es beliebig viele Literaturstellen geben mag, wo dabei stattdessen von wahr/falsch die Rede ist). Beweisbarkeit und Wahrheit aber zwei verschiedene Paar Stiefel.
Während Gödels 2. Theorem also etwas zur Syntax aussagt, hat es dazu tatsächlich eine Entsprechung zur Semantik: die Arithmetik kann ihre eigene Wahrheit nicht definieren. Das ist dann Tarskis Theorem über die “Undefinierbarkeit von Wahrheit”. So, arithmetically speaking, the truth is out there somewhere …
Semantik und Syntax
@Chrys Vielen Dank für deine Erläuterungen.
Diese begriffliche Unterscheidung zwischen Wahrheit und Beweisbarkeit ist wichtig für das Verständis dieser Arbeiten. Wenn ich das richtig verstande habe, dann hat sich gerade der Intuitionismus von Brouwer mit der semantischen Ebene dieser Theorien beschäftigt und sich sozusagen auf “Wahrheitssuche” begeben.
@Joe Dramiga
Das stimmt schon, in Brouwers Welt wird Wahrheit durch Beweisbarkeit definiert.
Dass Brouwers Herangehensweise allgemein wenig Rückhalt findet, liegt aber gewiss nicht nur daran, dass sie vordergründig zu einer eingeschrumpften math. Logik führt, sondern dass sie diese in eine Abhängigkeit setzt von der Antwort auf die Frage, was intuitiv einsichtig ist. Mir ist jedenfalls intuitiv einsichtig, dass man über eben diese Frage schier endlos streiten könnte, ohne auch nur einen einzigen Schritt voranzukommen. Und das wäre sehr unbefriedigend.
Pingback:Kleine und große Unendlichkeiten › Die Sankore Schriften › SciLogs - Wissenschaftsblogs