Kapitel 5
Ungelöste Rätsel

7    Unentscheidbarkeit und Wahrheit



Wenn es keine Gegenbeispiele gibt

In diesem Kapitel möchte ich einer Frage nachgehen, die mich immer wieder beschäftigt hat und die ich zunächst recht verwirrend finde:

Vermutung:

  • Betrachten wir eine Aussage, die behauptet, dass es kein Objekt mit einer bestimmten Eigenschaft \(P\) gibt. Viele Fragen im Rahmen der Zahlentheorie sind solche Aussagen, beispielsweise die Goldbachsche Vermutung. Was geschieht, wenn sich diese Aussage nun als unentscheidbar herausstellt? Nun, dann kann man jedenfalls kein Gegenbeispiel finden, denn dann wäre die Aussage ja entscheidbar. Also muss die Aussage wahr sein.

Andererseits folgt aus der Unentscheidbarkeit aber, dass es neben Modellen, in denen die Aussage wahr ist, auch Modelle geben muss, in denen die Aussage falsch ist. Genau so beweist man ja typischerweise die Unentscheidbarkeit einer Aussage. Wäre die Aussage in allen Modellen wahr, so müsste sie nach Gödels Vollständigkeitssatz auch beweisbar sein (siehe Kapitel 4.4 ).

In einem Modell, in dem die Aussage falsch ist, muss es ein Gegenbeispiel geben. Aber oben hatten wir doch gerade behauptet, dass es kein Gegenbeispiel geben könne, denn damit wäre die Aussage ja entscheidbar. Wie passt das zusammen? Wie kann man oben behaupten, dass die Aussage wahr ist?

Ein Lösungsansatz wäre: Ja, es gibt in bestimmten Modellen Gegenbeispiele, aber das formale System, das wir hier modellieren, weiß davon nichts. Anders gesagt: Das Gegenbeispiel ist zwar da, kann aber mit den Mitteln des formalen Systems nicht konstruiert oder bewiesen werden. Das Gegenbeispiel existiert im speziellen Modell, seine Existenz kann aber nicht aus den Axiomen des formalen Systems abgeleitet werden. Es befindet sich damit außerhalb der deduktiven Reichweite des formalen Systems.

Etwas Ähnliches ist uns bereits bei Skolems Paradoxon in Kapitel 4.4 begegnet. Dort hatten wir gelernt, dass es abzählbare Modelle der Mengenlehre gibt, dass aber die Mengenlehre zugleich beweisen kann, dass sie überabzählbare Mengen umfasst. Im Modell gibt es nur abzählbare Mengen, aber diese Erkenntnis entzieht sich dem formalen System, das darin modelliert wird. Es gibt im Modell keine bijektive Modellfunktion zwischen der Modellmenge für die natürlichen und der für die reellen Zahlen. Im Prinzip gibt es schon eine solche Funktion, aber diese ist keine Interpretation (Modell) einer Funktion aus dem formalen System, das hier modelliert wird.

Unsere Lösungsidee könnte also in die richtige Richtung führen. Dieser Verdacht verstärkt sich, wenn wir uns an Kapitel 3.1 erinnern, in dem es um Gödels unentscheidbare Aussage \(G\) und um übernatürliche Zahlen ging. Dort hatten wir die Situation, dass in der Peano-Arithmetik für jede natürliche Zahl \(g\) die Aussage \( \neg B(m,g) \) beweisbar war, dass wir aber dennoch die dort unentscheidbare Aussage \( \exists y: B(m,y) \) zur Peano-Arithmetik hinzufügen konnten (das ist die Aussage \( \neg G \) ). In den natürlichen Zahlen ist also dieses \(y\) nicht zu finden – es liegt außerhalb der Reichweite der natürlichen Zahlen. Wir sprachen daher von übernatürlichen Zahlen.

Ok – irgendwie haben wir also eine grobe Idee, was hier los sein könnte. Versuchen wir, diese Idee zu präzisieren:



Unentscheidbarkeit und Wahrheit in der Zahlentheorie

Kehren wir zurück zu unserem Ausgangspunkt, also zu der Aussage, dass es kein Objekt mit einer bestimmten Eigenschaft \(P\) gibt. Als formales System setzen wir die Peano-Arithmetik voraus, also das formale System, das versucht, die natürlichen Zahlen zu beschreiben (siehe Kapitel 2.1 ). Unsere Aussage \(A\) lautet dann: \[ A: \quad \neg \exists x : P(x) \] oder vollkommen gleichwertig dazu: \[ A: \quad \forall x : \neg P(x) \] Es gibt also kein \(x\) mit der Eigenschaft \(P(x)\). Dabei soll \(P(x)\) in der Peano-Arithmetik entscheidbar sein, d.h. bei jedem gegebenem \(x\) kann man in endlich vielen Schritten in der Peano-Arithmetik ableiten, ob \(P(x)\) gilt oder nicht. Ein Beispiel für \(P(x)\) wäre die folgende Eigenschaft, die der berühmten Goldbachschen Vermutung aus Kapitel 5.5 entspricht:

Die Goldbachsche Aussage \(A\), d.h. \(\neg \exists x : P(x)\), sagt also, dass es kein \(x\) gibt, dass gerade ist und nicht als Summe zweier Primzahlen geschrieben werden kann. Für die zweite Version der Aussage \(A\) ist auch \( \neg P(x) \) interessant:

Die zweite Version der Goldbachschen Aussage \(A\), d.h. \(\forall x : \neg P(x)\), sagt also, dass alle \(x\) entweder ungerade sind oder als Summe zweier Primzahlen geschrieben werden können.

Nehmen wir an, wir könnten für jede einzelne natürliche Zahl \(n\) (also für jeden \(n\)-fachen Nachfolger der Null) in der Peano-Arithmetik einzeln zeigen, dass \(n\) nicht die Eigenschaft \(P(n)\) hat. Für jedes \(n\) wäre also \( \neg P(n) \) beweisbar (ganz analog zu \( \neg B(m,g) \) von oben). Können wir daraus in der Peano-Arithmetik die Aussage \( A: \; \forall x : \neg P(x) \) ableiten? Von der Diskussion zu Gödels \(B(m,g)\) von oben wissen wir, dass das nicht geht, denn es könnte ja eine übernatürliche Zahl \(x\) geben, die die Eigenschaft \(P(x)\) aufweist.

Für die Goldbachsche Vermutung bedeutet das: Selbst wenn wir für jede einzelne gerade natürliche Zahl \(n\) in der Peano-Arithmetik beweisen könnten, dass sie als Summe zweier Primzahlen geschrieben werden kann, so können wir in der Peano-Arithmetik daraus nicht folgern, dass das für alle geraden Zahlen \(x\) gilt (wegen der Möglichkeit übernatürlicher Zahlen). Wenn also die Goldbachsche Vermutung für alle natürlichen Zahlen wahr ist, so können wir das in der Peano-Arithmetik nicht unbedingt allgemein beweisen (es mag möglich sein, aber es kann auch anders kommen).

Nehmen wir umgekehrt an, es gäbe eine natürliche Zahl \(n\), die die Eigenschaft \(P(n)\) aufweist. Für die Goldbachsche Vermutung hieße das, dass wir eine natürliche Zahl \(n\) hätten, die gerade ist und nicht als Summe zweier Primzahlen geschrieben werden kann. Das wäre dann ein Gegenbeispiel zur Goldbachschen Vermutung. In der Peano-Arithmetik wäre dann die Formel \(P(n)\) für dieses \(n\) ableitbar, und ebenfalls ableitbar wäre der Ausdruck \( \neg A: \; \exists x : P(x) \). Das ist der entscheidende Punkt!

Fassen wir zusammen (siehe auch K.Podnieks: Incompleteness Theorems. Related Results ):

Man kann es auch so ausdrücken:

  • Wenn es unter den natürlichen Zahlen ein Gegenbeispiel zur Aussage \(A\) gibt, dann bekommt die Peano-Arithmetik das auch mit, d.h. sie kann die Aussage \( \neg A \) beweisen. Wenn also die Goldbachsche Vermutung falsch ist, dann gibt es in der Peano-Arithmetik auch einen Beweis dazu.

Was geschieht nun, wenn die Aussage \(A\) in der Peano-Arithmetik unentscheidbar ist? Dann kann es kein Gegenbeispiel zu \(A\) in den natürlichen Zahlen geben, denn sonst könnte die Peano-Arithmetik beweisen, dass \(A\) falsch ist, und \(A\) wäre damit entscheidbar. Also muss \(A\) für natürliche Zahlen wahr sein, d.h. mögliche Gegenbeispiele gibt es formal nur außerhalb der natürlichen Zahlen.

Dieses Ergebnis bestätigt unsere Ausgangsvermutung und zugleich auch unseren Lösungsansatz, beides bezogen auf die Zahlentheorie. Dabei wird die Ausgangsvermutung entsprechend präzisiert:

Unentscheidbarkeit und Wahrheit in der Zahlentheorie:

  • Betrachten wir eine Aussage \(A\) der Peano-Arithmetik, die behauptet, dass es keine Zahl mit einer bestimmten entscheidbaren Eigenschaft \(P\) gibt: \[ A: \; \neg \exists x : P(x) \] Wenn diese Aussage \(A\) unentscheidbar in der Peano-Arithmetik ist, dann gibt es kein Gegenbeispiel in den natürlichen Zahlen, denn ein solches Gegenbeispiel führt dazu, dass man \( \neg A \) in der Peano-Arithmetik beweisen kann und \(A\) damit entscheidbar wäre. Also muss die Aussage \(A\) für die natürlichen Zahlen wahr sein.

Wenn \(A\) unentscheidbar ist, so gibt es Modelle der Peano-Arithmetik, in denen \(A\) falsch ist. Aber auch in diesen Modellen ist \(A\) für alle natürlichen Zahlen (also für allen \(n\)-fachen Nachfolger der Null) wahr, d.h. alle \(n\)-fachen Nachfolger der Null haben nicht die Eigenschaft \(P(n)\). Das war genau unser Lösungsansatz von oben: Ja, es gibt in diesen Modellen Gegenbeispiele, aber die Peano-Arithmetik weiß davon nichts, denn die Gegenbeispiele kann man mit den Mitteln der Peano-Arithmetik nicht konstruieren – sie sind keine \(n\)-fachen Nachfolger der Null, also keine natürlichen Zahlen.

Woher kann man wissen, ob \(A\) in der Peano-Arithmetik unentscheidbar ist? Innerhalb der Peano-Arithmetik kann man das jedenfalls nicht beweisen, denn sonst hätte die Peano-Arithmetik ja bewiesen, dass es keine Gegenbeispiele in den natürlichen Zahlen gibt. Man braucht eine umfassendere Metatheorie – nehmen wir wie immer die ZFC-Mengenlehre. Die Aussage \(A\) wird dazu aus der Sprache der Peano-Arithmetik in die Sprache der Mengenlehre übersetzt. In der Mengenlehre kann dann ein solcher Beweis der Unabhängigkeit der Aussage \(A\) von der Peano-Arithmetik ggf. geführt werden, beispielsweise durch Konstruktion entsprechender Modelle (siehe Kapitel 4.4 und Kapitel 5.6 ). Damit hätte die Mengenlehre allerdings zugleich die Aussage A in etwas modifizierter Form bewiesen: \[ A': \; \neg \exists x \in \mathbb{N} : P(x) \] wobei \(\mathbb{N}\) die Menge der natürlichen Zahlen ist. Konkret: Wenn man in der Mengenlehre beweisen kann, dass die Goldbachsche Vermutung unabhängig von der Peano-Arithmetik ist, dann hat man zugleich bewiesen, dass sie in den natürlichen Zahlen gilt.

Hier sehen wir wieder einmal sehr schön, dass die ZFC-Mengenlehre sehr viel mächtiger als die Peano-Arithmetik ist. Wenn es der Peano-Arithmetik nicht gelingt, eine Aussage \(A\) zu beweisen, so gelingt das vielleicht der ZFC-Mengenlehre, wobei die Aussage so konkretisiert wird, dass die Variablen wirklich nur natürliche Zahlen sein können (die Peano-Arithmetik kann das nicht). Die Goodsteinfolgen aus Kapitel 4.6 waren ein Beispiel für eine solche Aussage.

Und was wäre, wenn man in der ZFC-Mengenlehre nicht nur beweisen könnte, dass \(A\) unabhängig von der Peano-Arithmetik ist, sondern sogar unabhängig von der ZFC-Mengenlehre selbst ist? So etwas ist ja im Prinzip möglich – man denke an die Kontinuumshypothese. Im Grunde ändert das aber nichts, denn damit ist \(A\) auch unabhängig von der Peano-Arithmetik (die ZFC-Axiome umfassen ja die Peano-Arithmetik). In den natürlichen Zahlen \(\mathbb{N}\) ist \(A\) damit wahr, oder anders gesagt: die Aussage \( A': \; \neg \exists x \in \mathbb{N} : P(x) \) ist in der ZFC-Mengenlehre universell wahr. Nun wissen wir aber aus Kapitel 4.4, dass die universell wahren Aussagen genau die beweisbaren Aussagen sind (Gödels Vollständigkeitssatz). Wenn also \(A\) unentscheidbar ist, so ist \(A'\) universell wahr und damit beweisbar. Kann auch \(A'\) unentscheidbar in ZFC sein? Wenn wir diese Unentscheidbarkeit in ZFC beweisen könnten, dann wäre \(A'\) universell wahr und damit beweisbar – ein Widerspruch! Also können wir in ZFC nicht beweisen, dass \(A'\) unentscheidbar in ZFC ist! Man sagt auch, \(A'\) ist (wenn überhaupt) bösartig unentscheidbar (siehe Jan Thor: Mersenne.pdf, scheint aber leider im Internet nicht mehr auffindbar zu sein).

Die Goldbachsche Vermutung in der Form \(A'\) ist also entweder falsch – dann kann man das im Prinzip auch beweisen, oder sie ist beweisbar wahr, oder sie ist in ZFC unentscheidbar und damit ebenfalls wahr, wobei wir diese Unentscheidbarkeit aber nie in ZFC beweisen können. Damit wird verständlich, warum man in der Zahlentheorie im Normalfall nicht auf einfache unentscheidbare Aussagen trifft: Die meisten dieser Aussagen müssen bösartig unentscheidbar in ZFC sein, falls sie wirklich unentscheidbar in ZFC sind. Daher wissen wir auch normalerweise nicht, ob sie unentscheidbar in ZFC sind. Es sieht allerdings heute so aus, als sei die ZFC-Mengenlehre stark genug, um alle natürlicherweise in der Zahlentheorie auftretenden Aussagen über natürliche Zahlen entscheiden zu können. ZFC scheint bezüglich natürlicher arithmetischer Aussagen vollständig zu sein. Mit natürlich meint man Aussagen, die man nicht extra als unabhängig von der ZFC-Mengenlehre konstruiert hat, sondern die man ohne Rücksicht auf die Mengenlehre in der üblichen Zahlentheorie untersucht.

Falls eine Aussage \(A'\) wie die Goldbachsche Vermutung in ZFC unentscheidbar und damit bösartig unentscheidbar wäre, so könnte es in einer Erweiterung von ZFC dennoch gelingen, genau das zu beweisen. Damit wäre zugleich bewiesen, dass \(A'\) universell wahr ist, d.h. es muss einen Beweis für \(A'\) geben. Dieser Beweis kann dann allerdings nicht in ZFC geführt werden, denn dort ist \(A'\) ja unentscheidbar. Man benötigt die Erweiterung von ZFC für den Beweis. Eine solche Erweiterung kann beispielsweise darin bestehen, dass man die Existenz von sehr mächtigen Mengen fordert – mächtiger als alle Mengen, die mit ZFC-Mitteln erreichbar sind. Vielleicht braucht man solche Mengen zur Erfassung komplizierter divergierender Baumstrukturen im Beweis?! Mehr dazu siehe Kapitel 5.6.



Zusammenhang mit diophantischen Gleichungen

Das Standardbeispiel für Unentscheidbarkeit im Reich der natürlichen Zahlen sind die diophantischen Gleichungen, die wir in Kapitel 3.5 kennengelernt haben. Zunächst eine kurze Wiederholung:

Ein Beispiel für eine diophantische Gleichung ist die Gleichung \[ 4x^2 - 2xy + 3y^2 + 2y - 7x + 81 = 0 \] Hier gibt es zwei Variablen \(x\) und \(y\), und links steht ein Polynom vom Grad 2 in diesen beiden Variablen mit ganzzahligen Koeffizienten. Gesucht sind natürliche Zahlen für \(x\) und \(y\), so dass die Gleichung aufgeht.

Allgemeiner kann eine diophantische Gleichung auch mehr Variablen umfassen und auch höhere Potenzen. In Kapitel 3.5 hatten wir eine allgemeine diophantische Gleichung so geschrieben: \[ P(x, n, y_1, ..., y_m) = 0 \] Dabei ist \( P \) ein Polynom mit ganzzahligen Koeffizienten, \( n \) ist eine vorgegebene natürliche Zahl, die die Gestalt des Polynoms mitbestimmt, und \( x \) sowie \( y_1, ..., y_m \) sind die Variablen, für die bei gegebenem \( n \) Lösungen in den natürliche Zahlen gesucht werden. In der Schreibweise haben wir die Variable \( x \) gesondert bezeichnet, da wir die Lösungswerte für diese Variable separat in einer Menge \( D_n \) sammeln wollen, d.h. \( D_n \) ist die Menge aller Werte für \( x \) , für die es Werte der Variablen \( y_1, ..., y_m \), so dass die Gleichung \(P(...) = 0\) stimmt.

Ein entscheidendes Ergebnis war:

Man kann also jeden Algorithmus zur Erzeugung von Zahlenlisten in eine diophantische Gleichung umwandeln, die als Lösungsmenge für \(x\) dieselbe Zahlenmenge ergibt. Diese diophantische Gleichung kann man jeweils ganz konkret konstruieren, wobei allerdings sehr komplexe Gleichungen entstehen können. So hatten wir in Kapitel 3.5 eine Gleichung gesehen, die die Menge der Primzahlen als Lösungsmenge hat.

Übrigens: Jede \( \exists \)-Aussage der Peano-Arithmetik definiert eine rekursiv aufzählbare Menge und ist damit äquivalent zur Lösbarkeit einer passenden diophantischen Gleichung. Die dazu negative \( \neg \exists \)-Aussage (oder gleichwertig dazu die passende \(\forall\)-Aussage) ist dann äquivalent zur Nicht-Lösbarkeit der passenden diophantischen Gleichung. Siehe auch Solomon Fefermann: The Impact of the Incompleteness Theorems on Mathematics, Notices of the AMS Vol. 53 No. 4, S. 434.

Der externe Parameter \(n\) nummeriert alle rekursiv aufzählbaren Mengen komplett durch, d.h. die Liste aller \(D_n\) ist die Liste aller rekursiv aufzählbaren Mengen. Auf diese Liste lässt sich nun Cantors Diagonalmethode anwenden: Wir stellen für alle Werte von \(n\) die Frage, ob dieses \(n\) selbst in der zugehörigen Lösungsmenge \(D_n\) auftaucht. Falls nicht, nehmen wir es in eine Menge \(V\) auf, d.h. die Menge \(V\) ist definiert als \[ V := \{ n \in \mathbb{N} , \, n \notin D_n \} \] Diese Menge \(V\) unterscheidet sich von jeder Menge \(D_n\), denn wenn \(D_n\) die Zahl \(n\) enthält, so enthält \(V\) sie nicht und umgekehrt. Damit ist \(V\) nicht in der Liste aller \(D_n\) enthalten, ist also auch keine rekursiv aufzählbare Menge (denn die stehen alle in der Liste drin). Es gibt also kein Computerprogramm, das die Elemente der Menge \(V\) auflisten kann. Entsprechend kann kein Computerprogramm für alle natürlichen Zahlen \(n\) die Frage beantworten, ob dieses \(n\) wirklich nicht in der zugehörigen Lösungsmenge \(D_n\) auftaucht, denn sonst könnte dieses Programm ja die Menge \(V\) auflisten. Da hilft dann auch die Auflistung der Elemente von \(D_n\) nichts, denn man kann die Liste bei unendlich vielen Elementen ja nie komplett durchsuchen.

Nun war \(D_n\) die Lösungsmenge aller \(x\), für die die Gleichung \[ P(x, n, y_1, ..., y_m) = 0 \] bei geeigneten Werten für die Hilfsvariablen \(y_1, ..., y_m\) erfüllt ist. Wenn man nun nicht allgemein entscheiden kann, ob ein \(n\) zu \(D_n\) gehört, so kann man auch nicht allgemein entscheiden, ob die obige diophantische Gleichung (mit \( x = n \)) für geeignete Werte der \(y\)-Hilfsvariablen erfüllt ist, d.h. ob es passende Lösungen für die \(y\)-Hilfsvariablen gibt. Damit gibt es kein allgemeines Entscheidungsverfahren für die Lösbarkeit diophantischer Gleichungen.

Das alles kannten wir schon aus Kapitel 3.5. Wie hängt das nun mit dem Thema des aktuellen Kapitels zusammen? Dazu habe ich in Martin Davis: The Incompleteness Theorem, Notices of the AMS, Vol 53, No. 4, S.414 das Folgende gefunden:

Nach unserem Ergebnis muss es für jedes Entscheidungsverfahren mindestens ein \(n_0\) geben, das nicht zu \( D_{n_0} \) gehört und bei dem wir das mit dem Entscheidungsverfahren nicht nachweisen können. Entsprechend können wir auch nicht nachweisen, dass die zugehörige diophantische Gleichung \[ P(n_0, n_0, y_1, ..., y_m) = 0 \] für dieses \(n_0\) keine Lösungen in den \(y\)-Hilfsvariablen hat. Die Aussage \[ \forall y_1, ..., y_m : \, \neg P(n_0, n_0, y_1, ..., y_m) = 0 \] ist für das gegebene Entscheidungsverfahren für dieses \(n_0\) nicht entscheidbar. Das sieht genauso aus wie unsere Aussage \( A \) von ganz oben, nur mit mehreren Variablen statt nur mit einer, was aber keine große Rolle spielt. Insofern gilt alles, was wir oben über \(A\) bzw. \(A'\) gesagt haben, auch hier, d.h. die Aussage ist unentscheidbar und deswegen für natürliche Zahlen wahr.

Welche Werte für \(n_0\) in Frage kommen, hängt von dem Entscheidungsverfahren ab, das wir anwenden. Egal welches Verfahren wir anwenden, es gibt immer mindestens ein \(n_0\), das diesem Verfahren entschlüpft, so dass der obige Satz unentscheidbar ist.

Eine Möglichkeit für Entscheidungsverfahren sind Beweise in der Peano-Arithmetik (siehe das Representation Theorem in Kapitel 2.4 ). Eine andere mächtigere Möglichkeit sind Beweise in der ZFC-Mengenlehre. Da die ZFC-Mengenlehre sehr viel mächtiger als die Peano-Arithmetik ist, wird es Aussagen geben, die für die Peano-Arithmetik unentscheidbar sind, die aber in der ZFC-Mengenlehre entschieden werden können. Daher gilt (siehe Martin Davis: The Incompleteness Theorem, Notices of the AMS, Vol 53, No. 4, S.414):

Bei manchen diophantischen Gleichungen kann also erst die ZFC-Mengenlehre beweisen, dass sie keine Lösungen haben, während die Peano-Arithmetik dafür zu schwach ist. Erst die ZFC-Mengenlehre wird dann auch ein entsprechendes \(n_0\) ermitteln können, denn die Peano-Arithmetik wird die Unentscheidbarkeit für dieses \(n_0\) nicht sehen können.

Aber auch für die ZFC-Mengenlehre muss es mindestens ein \(n_0\) geben, so dass die obige Aussage unentscheidbar ist, wobei die ZFC-Mengenlehre ein solches \(n_0\) nicht ermitteln kann (die Werte für \(n_0\) dürften ziemlich große natürliche Zahlen sein, denn \(n_0\) kodiert gewissermaßen die Beweiskraft des formalen Systems – entsprechend komplex sind dann die diophantischen Gleichungen). Es gibt also arithmetische Aussagen (also Aussagen über natürliche Zahlen), die in ZFC unentscheidbar sind. Allerdings wäre beispielsweise eine entsprechende diophantische Gleichung sehr kompliziert und sie wäre über das Diagonalverfahren oben auch extra so konstruiert, dass sie in ZFC unentscheidbar ist (wobei man in einer geeigneten ZFC-Erweiterung noch das passende \(n_0\) ermitteln muss). Dagegen haben wir oben bereits gesagt, dass ZFC bezüglich natürlicher arithmetischer Aussagen vollständig zu sein scheint. In diesem Sinne wäre die speziell konstruierte diophantische Gleichung als unnatürlich anzusehen – eben eine Spezialkonstruktion.



Unentscheidbarkeit und Wahrheit in der ZFC-Mengenlehre

Halten wir noch einmal fest: Wenn eine Aussage der Form \( A': \; \neg \exists x \in \mathbb{N} : P(x) \) wie beispielsweise die Goldbachsche Vermutung in der ZFC-Mengenlehre unentscheidbar ist, so ist sie bösartig unentscheidbar, d.h. wir können diese Unentscheidbarkeit in ZFC nicht beweisen. Wie passt das mit ähnlichen Aussagen zusammen, von denen wir wissen, dass sie in ZFC unentscheidbar sind (Beispiel: Kontinuumshypothese)? Was unterscheidet die Kontinuumshypothese von der Goldbachschen Vermutung? Auch die Kontinuumshypothese ist ja von der Form \[ K: \; \neg \exists x : Q(x) \] Dabei ist allerdings \(x\) keine natürliche Zahl aus \(\mathbb{N}\), sondern irgendeine Menge (die man sich meist als Teilmenge der reellen Zahlen vorstellt), und \(Q(x)\) sagt, dass die Mächtigkeit dieser Menge zwischen den natürlichen und den reellen Zahlen liegt. Die Menge \(x\) ist also überabzählbar, aber bei jeder Bijektion von \(x\) in die reellen Zahlen bleiben immer reelle Zahlen übrig (siehe Kapitel 4.3 und Kapitel 5.6 ). Die Kontinuumshypothese sagt, dass es eine solche Menge zwischen den natürlichen und den reellen Zahlen nicht gibt.

Im Internet hattee ich dazu den folgenden sehr interessanten Text gefunden (kann ihn aber leider mittlerweile nicht mehr wiederfinden): Jan Thor: Mersenne.pdf. An diesem Text orientiere ich mich im Folgenden.

In der Zahlentheorie hatten wir die Voraussetzung gemacht, dass die Eigenschaft \(P(x)\) in endlich vielen Schritten entscheidbar sein muss. So kann man bei jeder natürlichen Zahl per Computer immer nachprüfen, ob sie sich als Summe zweier Primzahlen schreiben lässt – man muss nur alle kleineren Primzahlen durchprobieren. Bei der Eigenschaft \(Q(x)\) der Kontinuumshypothese ist das sehr viel weniger durchsichtig. Es hängt davon ab, wie konkret die Menge \(x\) ist. Man kann aber nicht davon ausgehen, dass man für jede denkbare Menge \(x\) mechanisch nachprüfen kann, ob ihre Mächtigkeit zwischen den natürlichen und den reellen Zahlen liegt.

Nehmen wir analog zur Zahlentheorie an, es gäbe eine Menge \(x\), die die Eigenschaft \(Q(x)\) aufweist. Das wäre dann ein Gegenbeispiel zur Kontinuumshypothese. Anders als in der Zahlentheorie ist aber unklar, ob ZFC das erkennt, d.h. ob ZFC für diese Menge \(x\) auch den Ausdruck \(Q(x)\) ableiten kann. Die Eigenschaft \(Q(x)\) ist eben nicht allgemein entscheidbar.

Man kann die denkbaren Mengen allerdings einschränken, beispielsweise indem man Gödel-Konstruierbarkeit fodert. Damit werden die Mengen so konkret, dass \(Q(x)\) entscheidbar wird. Wenn man jetzt eine konstruierbare Menge \(x\) fände, die die Eigenschaft \(Q(x)\) aufweist (also zwischen den natürlichen und reellen Zahlen liegt), dann kann ZFC auch die Aussage \( \neg K: \; \exists x : Q(x) \) ableiten, d.h. die Kontinuumshypothese wäre durch Gegenbeispiel widerlegt.

Nun weiß man aber, dass die Kontinuumshypothese unentscheidbar in ZFC ist. Daher kann es auch kein konstruierbares Gegenbeispiel geben, denn sonst wäre die Kontinuumshypothese widerlegt und damit entscheidbar. Ein mögliches Gegenbeispiel muss also so wenig greifbar sein, dass ZFC das Gegenbeispiel nicht konkretisieren kann. ZFC kann für kein konkretes \(x\) die Eigenschaft \(Q(x)\) nachweisen, denn sonst hätte ZFC die Kontinuumshypothese widerlegt und damit entschieden.

Daher ist klar, dass es unter den konkreten Mengen kein Gegenbeispiel zur Kontinuumshypothese geben kann. Immer dann, wenn man sich auf konkrete Mengen beschränkt, so gilt die Kontinuumshypothese für diese Mengen, d.h. sie wird wahr und damit für diese Mengen entscheidbar. Trotzdem scheint es sinnvoll zu sein, die Kontinuumshypothese besser als falsch anzusehen, da man sich dadurch mehr Denkfreiheit offen lässt. Man lässt also im Prinzip Gegenbeispiele zur Kontinuumshypothese zu, wobei man weiß, dass man nicht mit dem Finger auf sie zeigen kann. Mögliche Gegenbeispiele bleiben immer sehr abstrakt – mehr dazu siehe Kapitel 5.6.



Literatur:



zurück zum Inhaltsverzeichnis

© Jörg Resag, www.joerg-resag.de
last modified on 15 April 2023