Unvollständigkeit am Beispiel der Goldbachvermutung |
| 06.04.2026, 18:28 | Malcang | Auf diesen Beitrag antworten » | ||
Unvollständigkeit am Beispiel der Goldbachvermutung
ich habe mich bisher zu wenig mit Unvollständigkeit beschäftigt, zugegeben. Aber ich möchte das gerne einmal diskutieren. Wer Lust hat mir da auf die Sprünge zu helfen ist herzlich eingeladen
Bewegen wir uns doch mal in den natürlichen Zahlen und legen die Peano-axiome zugrunde. Nun gibt es nach Gödel Aussagen, die wahr, falsch oder unentscheidbar sind. Hier ist vielleicht schon meine erste Frage: ist "unentscheidbar" das selbe wie "wahr, aber nicht beweisbar?". Meine Intuition sagt mir nein, denn das wäre ja "wahr". Nehmen wir doch mal die Goldbach'sche Vermutung. Ist sie wahr? Dann muss ich sie beweisen. Ist sie falsch? Dann brauche ich ein Gegenbeispiel. Bisher wissen wir es ja nicht. Sie kann durchaus wahr sein. Es ist aber auch möglich, das sie nicht beweisbar ist. Aber das macht sie ja dann nicht falsch. Sie bleibt also wahr oder falsch, unabhängig davon, ob sie entscheidbar ist oder nicht. Ich merke schon beim Formulieren dass mir das Thema wirklich nicht zugänglich ist. Aber bestimmt hilft mir euer Input auf die Sprünge, selbst wenn es nur zum besseren Formulieren führt. |
||||
| 07.04.2026, 06:45 | Elvis | Auf diesen Beitrag antworten » | ||
Wenn die Goldbachvermutung falsch ist, dann muss man nur so lange rechnen, bis man ein Gegenbeispiel gefunden hat. Das heißt: Wenn die Goldbachvermutung falsch ist, dann ist sie entscheidbar. Logisch äquivalent: Wenn die Goldbachvermutung nicht entscheidbar ist, dann ist sie wahr. Wir wissen noch nicht, ob sie wahr oder falsch ist. Wir wissen noch nicht, ob sie unentscheidbar oder entscheidbar ist. Wir wissen noch nicht, ob sie unbeweisbar oder beweisbar ist. Wir wissen noch nicht, ob ihre Negation beweisbar oder unbeweisbar ist. Anmerkung: Das formale System, das durch die Peano Axiome definiert wird, ist vollständig. Wenn man zusätzlich die Addition rekursiv definiert, kommt man zur Pressburger Arithmetik; diese ist ebenfalls vollständig. Erst wenn man Addition und Multiplikation zusätzlich zu den Peano Axiomen definiert, erhält man die unvollständige Peano Arithmetik (PA). Diese ist ein Teilsystem des Systems der Principia Mathematica (PM), deren Unvollständigkeit Gödel bewiesen hat. |
||||
| 07.04.2026, 10:56 | willyengland | Auf diesen Beitrag antworten » | ||
Was ist der Unterschied zwischen unbeweisbar und unentscheidbar? |
||||
| 07.04.2026, 14:28 | Elvis | Auf diesen Beitrag antworten » | ||
Beweisbarkeit: Eine Aussage in einem formalen System ist genau dann ein beweisbarer Satz in diesem System, wenn es einen Beweis in diesem System gibt. Entscheidbarkeit: Eine Aussage in einem formalen System ist genau dann entscheidbar, wenn sie bewiesen oder widerlegt werden kann. Wenn eine Aussage entscheidbar ist, dann gibt es entweder einen Beweis für die Aussage oder es gibt einen Beweis für die Negation der Aussage. |
||||
| 07.04.2026, 16:16 | willyengland | Auf diesen Beitrag antworten » | ||
Für mich wäre die Widerlegung der Goldbach Vermutung genauso ein Beweis, wie ein Beweis ihrer Richtigkeit. Also Entscheidbar = Beweis. Oder ich verstehe den Unterschied immer noch nicht. |
||||
| 07.04.2026, 19:52 | Elvis | Auf diesen Beitrag antworten » | ||
Die Goldbachvermutung ist entweder entscheidbar oder nicht entscheidbar. Sie ist genau dann entscheidbar, wenn ihre Negation entscheidbar ist. Wenn sie entscheidbar sind, dann ist entweder die Goldbachvermutung beweisbar oder es ist ihre Negation beweisbar. Wenn sie nicht entscheidbar sind, dann kann die Goldbachvermutung nicht bewiesen werden, und ihre Negation kann auch nicht bewiesen werden. Die Widerlegung der Goldbachvermutung ist dasselbe wie der Beweis ihrer Negation und umgekehrt. Wenn die Goldbachvermutung beweisbar ist, dann ist ihre Negation nicht beweisbar. Wenn aber die Negation beweisbar ist, dann ist die Goldbachvermutung nicht beweisbar. Wir sehen, dass eine Aussage genau dann entscheidbar ist, wenn ihre Negation entscheidbar ist. Wir sehen, dass eine Aussage nicht beweisbar ist, wenn ihre Negation beweisbar ist. Also ist entscheidbar nicht gleich beweisbar. |
||||
| Anzeige | ||||
|
|
||||
| 08.04.2026, 07:35 | willyengland | Auf diesen Beitrag antworten » | ||
Es gibt also immer 3 Möglichkeiten: 1. Eine Aussage ist beweisbar. 2. Das Gegenteil der Aussage ist beweisbar. 3. Die Aussage ist nicht entscheidbar. Man könnte sie als weiteres Axionm ansehen. Es muss aber bewiesen werden, dass sie nicht entscheidbar ist. 1 und 2 bedeuten entscheidbar. Interessant dabei ist, dass 2 nicht bedeutet, dass man z.B. bei der Goldbachvermutung wirklich ein Gegenbeispiel hat. Genauso wie man z.B. bei der Kontinuumshypothese kein Gegenbeispiel hat. Das empfinde ich als eine gewisse Unvollkommenheit. Aber so ist es eben. |
||||
| 08.04.2026, 09:24 | Elvis | Auf diesen Beitrag antworten » | ||
Wie immer im Leben gibt es noch viel mehr Möglichkeiten. Schon in der einfachsten Logik, nämlich der Aussagenlogik gilt: 1. Eine Aussage ist entweder wahr oder falsch. 2. Eine Aussage ist entweder beweisbar oder unbeweisbar. 3. Eine Aussage ist entweder entscheidbar oder nicht entscheidbar. Das sind Eigenschaften von Aussagen, keine Axiome, denn man kann nicht per Axiom festlegen, ob eine Aussage die eine oder andere Eigenschaft hat oder nicht hat. Die drei Eigenschaften sind voneinander unabhängig, also gibt es für jede Aussage 8 verschiedene Möglichkeiten solange man sie nicht entschieden, bewiesen oder widerlegt, als wahr oder falsch erkannt hat. Bei der Goldbachvermutung weiß man nicht, ob sie in der Peano-Arithmetik entscheidbar ist, ob sie in ders Peano-Arithmetik beweisbar ist, ob sie in den natürlichen Zahlen wahr ist. Wenn sie in PA entscheidbar ist, dann ist sie oder ihre Negation in PA beweisbar. Wenn sie in PA beweisbar ist, dann ist sie in N wahr. Bei der Kontinuumshypothese weiß man, dass sie in der ZFC-Mengenlehre nicht entscheidbar ist. Es gibt Modelle, in denen sie wahr ist, und es gibt Modelle, in denen sie falsch ist. Also ist weder die Kontinuumshypothese noch ihre Negation in ZFC beweisbar. |
||||
| 08.04.2026, 11:02 | willyengland | Auf diesen Beitrag antworten » | ||
8 Möglichkeiten? Aber die sind ja nicht unabhängig. Kann die Goldbachvermutung wahr sein, aber nicht beweisbar? Damit man weiß, dass sie wahr ist, muss man ja einen Beweis dafür haben. |
||||
| 08.04.2026, 16:15 | Elvis | Auf diesen Beitrag antworten » | ||
Wahrheit ist nicht abhängig von Beweisbarkeit. Entscheidbarkeit, Beweisbarkeit und Wahrheit ist nicht ganz unabhängig - weil eine nicht entscheidbare Aussage nicht beweisbar ist. Da hast du Recht, es verbleiben meines Erachtens sechs statt acht Möglichkeiten. Wissen hat nichts mit Entscheidbarkeit, Beweisbarkeit oder Wahrheit zu tun. Wenn wir Wissen dazunehmen, stellt sich die Frage, wer etwas weiß oder nicht weiß - damit multipliziert sich die Anzahl der sechs Möglichkeiten mit der Anzahl der Subjekte, die Wissen haben oder nicht haben können. Die Goldbachvermutung für die natürlichen Zahlen kann sein 1. nicht entscheidbar, also nicht beweisbar, wahr 2. nicht entscheidbar, also nicht beweisbar, falsch 3. entscheidbar, beweisbar, wahr 4. entscheidbar, nicht beweisbar, falsch Für eine Aussage, die in einem Modell wahr und in einem anderen falsch sein kann, kommen noch die folgenden Möglichkeiten dazu 5. entscheidbar, beweisbar, falsch 6. entscheidbar, nicht beweisbar, wahr Nachtrag: Ganz sicher bin ich mir dabei auch nicht... Man sollte zu jeder Kombination ein gutes Beispiel haben... Vielleicht kann noch jemand etwas mehr dazu sagen. Eventuell ist die Goldbachvermutung in natürlichen Zahlen vom Typ (3.) und in einem algebraischen Zahlkörper vom Grad 5876863 vom Typ (5.) ODER in natürlichen Zahlen vom Typ (4.) und in einem algebraischen Zahlkörper vom Grad 87545368753 vom Typ (6.). "Kann sein, kann auch nicht sein." sagt Elvis bei "Hallo Spencer". |
||||
| 11.04.2026, 08:32 | Malcang | Auf diesen Beitrag antworten » | ||
Danke Elvis. Ich glaube eine Sache habe ich noch nicht verstanden. Soweit ich das bisher verstehe gibt es außer wahr und falsch auch "nicht entscheidbar". Aber auch eine nicht entscheidbare Aussage ist doch entweder wahr oder falsch ? ( |
||||
| 11.04.2026, 10:44 | Elvis | Auf diesen Beitrag antworten » | ||
Das sehe ich auch so. Das sind die beiden von mir genannten Fälle 1. nicht entscheidbar, also nicht beweisbar, wahr 2. nicht entscheidbar, also nicht beweisbar, falsch |
||||
| 13.04.2026, 09:22 | Elvis | Auf diesen Beitrag antworten » | ||
Stewart Shapiro, Philosophy of Mathematics: Structure and Ontology, Oxford University Press, 1997, Seite 72 "My structuralist program is a realism in ontology and a realism in truth-value — once the requisite notions of object and objectivity are on the table. Structuralists hold that a nonalgebraic field like arithmetic is about a realm of objects — numbers — that exist independently of the mathematician, and they hold that arithmetic assertions have nonvacuous, bivalent, objective truth-values in reference to this domain." Wenn man eine andere Philosophie der Mathematik oder auch nur eine andere Logik benutzt, kann man ganz andere Meinungen zur Arithmetik, Zahlen, Aussagen und Wahrheit haben und glauben. |
||||
| 13.04.2026, 17:50 | IfindU | Auf diesen Beitrag antworten » | ||
| RE: Unvollständigkeit am Beispiel der Goldbachvermutung Um es vielleicht etwas aus der Mathematik zu heben. Nehmen wir an du hast die Peano-Axiome. Ich definiere was ein Mensch ist und ich hab die Aussage: Es gibt mehr als 5 Menschen. Die Aussage ist nicht wahr oder falsch, sie ist nicht entscheidbar. Die Mathematik an der Stelle kann mit den bisherigen Informationen keine Aussage treffen, selbst nachdem wir sie formulieren können. Jetzt nehmen wir 2 weitere Axiome: Axiom 1: Das Universum zum Zeitpunkt vom Neujahr 2020 ist gültig (mit gerne ausgiebiger Beschreibung jedes Atoms/Quantenzustand) Axiom 2: Das Universum zum Zeitpunkt 5 Sekunden des Urknalls ist gültig (mit gerne ausgiebiger Beschreibung jedes Atoms/Quantenzustand). Ich vermute Physiker werden mir sagen, dass alles herrlich undefiniert und mehrdeutig ist. Aber nehmen wir es mal nicht zu genau. Wenn wir jetzt zu den Peano-Axiomen das Axiom 1 nehmen, dann ist die Aussage "Es gibt mehr als 5 Menschen" wahr. Man nehme die Definition von Mensch, vergleiche die atomare Struktur des Universums und schließe, dass es mehr als 5 Menschen gibt. Wenn wir statt Axiom 1 aber Axiom 2 nehmen, dann ist die Aussage plötzlich falsch. Wir können die Atomstruktur des Universums studieren und feststellen, dass es zu der Zeit exakt 0 Menschen gab. Die Peano-Axiome haben sich nicht geändert, die Definition von Menschen hat sich nicht geändert, aber durch die Zunahme von Axiomen wurde die Aussage entscheidbar, einmal wahr und einmal falsch. Das Problem was wir jetzt mit der Goldbachschen Vermutung haben: Wüssten wir, dass es unentscheibar ist, könnten wir (ich vermute und Elvis kann mich gerne korrigieren) das Axiom "Goldbach hat Recht" dazunehmen, und eine widerspruchfreie Mathematik weiterhin widerspruchsfrei lassen. Oder wir könnten genauso gut sagen "Goldbach hat Unrecht". In beiden Fällen sind alles was wir von der bisherigen Mathematik kennen, weiterhin korrekt. Aber wir könnten neue Aussagen beweisen, weil wir ein neues Axiom als Grundlage nehmen können. Was wir beweiesen und widerlegen könnten, hängt davon ab wie sympathisch uns Goldbach war. |
||||
| 13.04.2026, 20:27 | Elvis | Auf diesen Beitrag antworten » | ||
Das ist ein wunderbares Beispiel, direkt aus dem Leben gegriffen. Die Peano-Arithmetik kann nicht entscheiden, ob es damals oder heute mehr als fünf Menschen gab oder gibt. Du ergänzt die Peano-Arithmetik um jeweils ein Axiom und bekommst damit zwei Systeme, in denen die Aussage entscheidbar ist. In einem System ist die Aussage beweisbar, also wahr (heute). Im anderen System ist die Negation der Aussage beweisbar, also wahr, also die Aussage falsch (damals). Auf diese Art kann man jedes unvollständige System zu zwei verschiedenen Systemen ergänzen, in denen eine unentscheidbare Aussage entscheidbar entweder wahr oder falsch ist - man muss nur wissen (!), dass die Aussage im System unentscheidbar ist. Ich mache mir das Leben etwas leichter, weil ich in dem damaligen Modell weiß, dass die Aussage falsch war und im heutigen Modell weiß, dass die Aussage wahr ist. Daraus kann ich umgekehrt schließen, dass die Aussage in der Peano-Arithmetik nicht entscheidbar ist. Die Goldbachvermutung kann man auf diese Art nicht behandeln. Du weißt nicht, ob sie entscheidbar ist oder nicht, deswegen kannst du sie oder ihre Negation nicht als Axiom wählen. Ich habe kein Modell, in dem ich weiß, ob sie wahr oder falsch ist. Also habe ich erst recht keine zwei Modelle in denen sie einmal wahr und einmal falsch ist, deswegen weiß ich nicht, ob sie entscheidbar ist oder nicht. |
||||
| 09.05.2026, 17:10 | Malcang | Auf diesen Beitrag antworten » | ||
| RE: Unvollständigkeit am Beispiel der Goldbachvermutung Hallo zusammen, vielen Dank für die schöne Diskussion hier. Es sind interessante, aber auch schwer verdauliche Punkte dabei. Ich bleibe dran
Das finde ich sehr schwer zu verstehen. Denn sagen wir, es ist unentscheidbar. Dann nehme ich als Axiom "goldbach hat Recht" zu den peano axiomen hinzu. Dann könnte es aber doch trotzdem sein, das wir irgendwann ein riesengroßes Gegenbeispiel finden. Damit wäre die Aussage ja falsch, und damit entscheidbar. Wo ist mein Denkfehler? |
||||
| 09.05.2026, 18:37 | Elvis | Auf diesen Beitrag antworten » | ||
Du hast keinen Denkfehler, was du sagst ist genau das was ich schon zu IfindU gesagt habe. Solange man nicht weiß, dass eine Aussage nicht entscheidbar ist, kann man sie oder ihre Negation nicht immer zu einem Axiom machen. IfindU hat in seinem Beitrag vorausgesetzt, dass die Vermutung nicht entscheidbar ist. Unter dieser Annahme glaubt er, man kann man einmal die Vermutung zum Axiom machen und einmal ihre Negation zu einem Axiom machen. Das glaube ich nicht. Ich glaube nicht, dass man voraussetzen darf, dass die Goldbachvermutung nicht entscheidbar ist. Wäre sie nicht entscheidbar, dann könnte man nicht beweisen, dass sie wahr ist und man könnte nicht beweisen, dass sie falsch ist. 1. Wenn sie falsch ist, dann muss es ein Gegenbeispiel geben, und ein Gegenbeispiel kann man nach endlich vielen Schritten in endlicher Zeit berechnen, womit bewiesen wäre, dass sie falsch ist, also wäre sie entscheidbar. (falsch entscheidbar)(nicht entscheidbar wahr). 2. Wenn sie wahr ist, dann ist sie entscheidbar oder nicht entscheidbar. 2a. Wenn sie wahr und entscheidbar ist, dann kann man beweisen, dass sie wahr ist. 2b. Wenn sie wahr und nicht entscheidbar ist, dann kann man nicht beweisen, dass sie wahr ist. Also gibt es nur die Möglichkeiten (wahr, entscheidbar), (wahr, nicht entscheidbar), (falsch, entscheidbar). Unter der Annahme, dass die Goldbachvermutung nicht entscheidbar ist, kann ihre Negation nicht wahr sein, macht man diese Negation zu einem Axiom, dann wird das System widersprüchlich. Ergänzung: Ich setze voraus, dass wir über eine Logik reden, in der es überhaupt Aussagen gibt, die nicht entscheidbar sind. In der ZFC Mengenlehre mit PL1 und Standardsemantik gibt es das nicht, denn die ist nach Gödel vollständig. Allerdings kann man darin nicht über "die" natürlichen Zahlen sprechen, denn nach Löwenheim-Skolem gibt es zu jeder unendlichen Kardinalität ein Modell der natürlichen Zahlen, und ich kann mir nicht vorstellen, was die Goldbachvermutung dann sagen will. In der Dedekind-Peano-Arithmetik mit PL2 gibt es nicht entscheidbare Aussagen, denn die ist nach Gödel unvollständig. Dedekind hat gezeigt, dass diese Theorie kategorisch ist, d.h. die natürlichen Zahlen sind bis auf Isomorphie eindeutig. Alles was ich oben gesagt habe bezieht sich auf PA mit PL2. |
||||
| 10.05.2026, 16:54 | IfindU | Auf diesen Beitrag antworten » | ||
"Kann" man schon, wäre aber witzlos. Wenn die Aussage entscheidbar ist, dann hat man mit dem Axiom entweder Redundanz geschaffen, weil es aus den anderen Axiomen folgt, oder man hat einen Widerspruch geschaffen. Ich kenne die formale Definition nicht, aber sinnig fände ich: Eine Aussage X ist nicht entscheidbar im Axiomsystem A, wenn sowohl als auch widerspruchsfrei sind. Was ich mich Frage: Kann es Aussage geben, wo die Widerspruchsfreiheit von oder nicht-entscheidbar wäre? Und impliziert das, die Unentscheidbarkeit von selbst? |
||||
| 10.05.2026, 20:26 | Elvis | Auf diesen Beitrag antworten » | ||
Wenn sowohl als auch widerspruchsfrei sind, dann ist X in diesem System nicht entscheidbar. Genau das nutzt man oft beim Forcing aus, wo man entsprechende Modelle nachweisen kann und daraus auf die Widerspruchsfreiheit der beiden Systeme schließt. X ist dann unabhängig von A, also in A nicht entscheidbar. Gödels zweiter Unvollständigkeitssatz lehrt uns, dass kein hinreichend mächtiges System seine eigene Widerspruchsfreiheit beweisen kann. Da die Arithmetik A ihre Widerspruchsfreiheit nicht beweisen kann, kann sie erst recht nicht beweisen, dass oder widerspruchsfrei sind, ganz egal welche Eigenschaften X hat. Daraus kann man also nichts über X schließen. Folgerung: Entscheidbarkeit kann man nicht über Widerspruchsfreiheit definieren. Definition: Eine Aussage X ist genau dann in einem logischen System S entscheidbar, wenn entweder X oder in S beweisbar ist. (Der Fall, dass X und in S beweisbar sind, interessiert mich weniger, weil S dann nicht widerspruchsfrei ist.) |
||||
| 11.05.2026, 17:07 | IfindU | Auf diesen Beitrag antworten » | ||
Fairer Punkt. 
Forcing war auch das woran ich dachte, aber falsch dargestellt habe.Das deutsche Wikipedia nennt das was ich eigentlich meinte "relativ konsistent":
|
||||
| 12.05.2026, 10:03 | Elvis | Auf diesen Beitrag antworten » | ||
Ich bevorzuge den eindeutig definierten Begriff widerspruchsfrei, weil der Begriff konsistent je nach Autor und Logik unterschiedliche Bedeutungen haben kann. Manchmal meint konsistent die syntaktische Eigenschaft widerspruchsfrei (keine Aussage und ihre Negation ist beweisbar), Shapiro definiert konsistent syntaktisch so, dass eine zulässige Formel existiert, die nicht ableitbar ist, manchmal meint konsistent die semantische Eigenschaft erfüllbar (es gibt ein Modell). Die Entwicklung der Logik von 1870 bis heute war sehr verschlungen und verwirrend, so dass auch heute noch längst nicht alle Begriffe einheitlich definiert sind. In jedem Buch, Paper und Artikel muss man sehr genau aufpassen, wer worüber spricht. Wikipedia darf in diesem Artikel "relativ konsistent" sagen, weil vorher "konsistent" mit "widerspruchsfrei" identifiziert wird. |
||||
|
|
Verwandte Themen
| Die Beliebtesten » |
| Die Größten » |
| Die Neuesten » |