Diskussion:Gödelscher Unvollständigkeitssatz

Ich Habe den Eindruck, dass die für einen Nichtfachmann zentrale Aussage 'Die Unvollständigkeitssätze sagen dann aus, dass in diesem Modell wahre Sätze existieren, die in der Prädikatenlogik erster Stufe nicht bewiesen werden können.' (Es gibt in der Arithmetik wahre unbeweisbare Sätze) in den technischen Details untergeht.

Es gibt zwei Gödelsche Unvollständigkeitssätze. Siehe englische Wikipedia. --zeno 18:25, 6. Jul 2003 (CEST)

Ideen zur Ergänzung:

Theorie erklärt nicht den speziellen Gebrauch im Kontext: eine Theorie hier ist (soll sein) eine deduktiv abgeschlossene Menge von Formeln.
Deutlicher darauf hinweisen, dass man es mit der Prädikatenlogik Logik erster Stufe zu tun hat (PL1).
Beispiele für mathematisch sinnvolle unentscheidbare Resultate geben, zB Version des Theorems von Ramsey... siehe englische Version.
Die Unvollständigkeitssätze vom Vollständigeitssatz abgrenzen.
Nichtstandardmodelle.
Minimale Voraussetzungen der Unvollständigkeit beschreiben (Robinson's Arithmetik Q).
Auf philosophische Mißverständnisse hinweisen.
Modale Beweislogiken im zshg mit 2. Unvollständidkeitssatz.

Wäre auch toll, wenn man den Text etwas auflockern könnte und z. B. Unterüberschriften einbauen könnte. Vielleicht auch eine Einleitung für den Laien ("Nicht alles Wahre lässt sich beweisen")? Stern 21:49, 21. Feb 2004 (CET)

Nein, Gödels Unvollständigkeitssatz sagt:

∀ formale Arithmetik P: ∃ wahre Aussage G: G ist in P unentscheidbar

das ist nicht dasselbe wie

∃ wahre Aussage G: ∀ formale Arithmetik P: G ist in P unentscheidbar

d.h. „jede formale Arithmetik ist unvollständig“, aber nicht „Es gibt arithmetische Wahrheiten, die sich in keiner Arithmetik beweisen lassen“. Auch würde eine solche Formulierung missverstanden werden als Behauptung: Es gibt andere und mächtigere Wege, arithmetische Wahrheiten zu erkennen als die Arithmetik – eine außermathematische Interpretation des Beweises von Gödel, die ich so bestreiten würde.

Ich hab mal versucht, den Satz in einer etwas allgemeinverständlicheren Form darzustellen und in einen historischen Kontext zu stellen (Hilberts Programm). Meines Erachtens kommt es wesentlich darauf an, dass man das System auch nicht einfach erweitern kann. Bei solchen Formulierungen muss man immer sehr vorsichtig sein, da Wortbedeutungen ja vielschichtig sind und man sehr leicht falsche Assoziationen weckt. Daber bitte eventuell kritisch prüfen Hubi 08:13, 24. Mär 2004 (CET)

jeder Satz erhält eine eigene Nummer. Er konstruiert dann eine Aussage der Form: "Der Satz mit der Nummer 1 ist nicht beweisbar". Die Abzählung wird dann so definiert, dass dieser Satz die Nummer 1 erhält. Insgesamt erhält er einen Satz der Form "Ich bin nicht beweisbar".

Ähem! Man konstruiert eine Aussage mit einer freien Variablen und setzt dann für diese Variable genau die Aussage selbst ein. Daher "x". Du versuchst die Abzählung so zu definieren, dass "Nummer 1" eine Variable ist... -- Fuzzy 23:36, 28. Mai 2004 (CEST)Beantworten

Hmm, eigentlich geht es doch darum, an die Variable x einen bestimmten Wert zu binden. Und zwar ist dieser Wert die Nummer der Aussage selbst. Alle anderen möglichen Belegungen von x interessieren uns in dem Fall nicht. Wenn man die Variable bindet, erzeugt man eigentlich eine neue Aussage, einen neuen Satz. Ich habe als Wert halt einfach 1 gewählt, es ist aber völlig egal. Der springende Punkt ist doch der dass wir eine Aussage der Form "Ich bin nicht beweisbar", also den Selbstbezug, konstruieren. Wozu da noch die freie Variable? Verkompliziert den Fall doch nur unnötig. Oder sehe ich da etwas falsch? -- Dishayloo 01:47, 29. Mai 2004 (CEST)Beantworten

Ja - versuch doch mal, den Beweis so durchzuführen. --Fuzzy 03:33, 29. Mai 2004 (CEST)Beantworten

Diskussion aus dem Review

Nachdem der mal vor einiger Zeit auf der Kandidatenliste gescheitert stelle ich den Artikel hier ein, denn ich denke er hat Potential! Damaliges Problem war wohl die Unverständlichkeit. [1] -- Dishayloo [ +] 18:54, 29. Jul 2004 (CEST)
Die Unvollständigkeitssätze sagen dann aus, dass in diesem Modell wahre Sätze existieren, die in der Prädikatenlogik erster Stufe nicht bewiesen werden können. - Ich denke mal, dass es "formuliert" statt "bewiesen" heißen müsste. --zeno 15:43, 30. Jul 2004 (CEST)
- Nein, sie können ja formuliert werden, sind aber weder beweis- noch wiederlegbar. Konkret gab ja Gödel als Beweis eine Konstruktionsvorschrift zur Erzeugung solcher Sätze an. -- Dishayloo [ +] 15:47, 30. Jul 2004 (CEST)
Sorry, habe mal wieder PL1 und Aussagenlogik verwechselt ... --zeno 12:55, 31. Jul 2004 (CEST)
Der letzte Absatz "Interessantes" sollte m. E. eher am Anfang des Artikels stehen, immerhin erläutert er Sinn und Zweck der Übung. Unter "Interessantes" könnte stattdessen etwas expliziter auf "Gödel, Escher, Bach" verwiesen werden, in der Literaturliste ist er doch etwas versteckt. Nur son Vorschlag,--Janneman 21:13, 6. Aug 2004 (CEST)

Ich habe den Abschnitt nicht nach oben verschoben, da er schon einiges aus den vorhergehenden Teilen vorraussetzt und auch teilweise nicht so relevant ist. Ich habe aber oben noch einen Satz eingefügt, der ein bisschen besser die Zielrichtung des Artikels erläutert. Den Hinweis auf das Buch habe ich eingebaut. -- Dishayloo [ +] 01:15, 7. Aug 2004 (CEST)

Verständnisfrage

Hier ein Auszug aus dem Text:

"Besagt" der Ausdruck Bew(x) also, dass x beweisbar ist, und ist zum Beispiel 12345 die Gödelnummer von Bew(x), so ist ¬Bew(12345) eine unbeweisbare Aussage. Diese Aussage besagt dann nämlich: Die Formel mit der Gödelnummer 12345 ist nicht beweisbar. 12345 ist aber die Gödelnummer von Bew(x). Also sagt ¬Bew(12345): Ich bin nicht beweisbar. Wenn PA korrekt ist, so ist dieser Satz wahr, aber nicht beweisbar.

Ich verstehe nicht den Schluß, daß ¬Bew(12345) bedeuten soll: Ich bin nicht beweisbar. Die Aussage ist doch: der Satz mit der Nummer 12345 ist nicht beweisbar - und das ist doch Bew(x). Wenn ich ein Satz haben möchte der aussagt: Ich bin nicht beweisbar, muss doch die Gödelisierung für diesen Ausdruck gerade die Identität sein, also ¬Bew(y) = y. Erst dann spricht der Satz doch wirklich über sich selbst, oder nicht ????

wäre echt dankbar wenn mir jemand meinen Denkfehler erklären kann

Christian Köhler

Antwort: Im formalen System selbst lässt sich kein ¬Bew(y)=y zeigen, schon weil metamathematische Aussagen über „Sätze“ nicht unbedingt im formalen System ausgedrückt werden können; eine Formel hat kein „Ich“, auf das sie sich beziehen kann, sondern bezieht sich auf arithmetische Eigenschaften von Zahlen.

In der Metamathematik, also auf der Ebene, auf der Gödels Beweis geführt wird, und die (allein mangels Notwendigkeit) nicht so weit formalisiert wird, lässt sich aber zeigen: ¬Bew(y) ⇔ Formel Nr. y ist nicht beweisbar.

Also „besagt“ die Formel nicht direkt etwas über sich selbst, aber das wir diese Äquivalenz metamathematisch zeigen konnten, können wir metamathematisch sagen: Die Formel ist Äquivalent zu einer Aussage über die Formel.

Siehe auch meine Skizze unten. --136.199.8.128 17:39, 26. Jul 2005 (CEST)

Vielleicht hat meine Verständnisfrage etwas damit zu tun

Im Artikel heißt es:

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 eine Aussage der Form: "Der Satz mit der Nummer x ist nicht beweisbar" und setzt für x die Nummer dieser Aussage ein. Insgesamt erhält er einen Satz der Form "Ich bin nicht beweisbar".

Was ich nicht verstehe:

"Der Satz mit der Nummer x ist nicht beweisbar" ist doch eigentlich keine Aussage, sondern eine Aussageform; mit anderen Worten, es ist eine Funktion, die jedem Wert x', den x annehmen könnte, eine Aussage über diesen Wert x' zuordnet. Aus dem Satz "Der Satz mit der Nummer x ist nicht beweisbar" wird also erst eine Aussage, wenn man für x einen bestimmten Wert einsetzt, oder wenn man etwas davor schreibt wie "Für alle x gilt:" oder "Es gibt ein x, für das gilt:".

Meine erste Verständnisfrage lautet: Soll die "Abzählung aller Sätze", von der in meinem Zitat die Rede ist, nur Aussagen enthalten oder auch Aussageformen?

Antwort: Alle Sätze, Aussageformen, Formeln und auch alle nichtwohlgeformten Zeichenketten werden nummeriert. Gödel nummeriert im Zuge seines Beweises außerdem Ableitungen (also Folgen von Sätzen) und Klassenzeichen (das sind Aussageformen mit genau einer freien Variablen).

Im ersten Fall, wenn nur Aussagen enthalten sind und keine Aussageformen, würde "Der Satz mit der Nummer x ist nicht beweisbar" nicht vorkommen und hätte folglich keine Nummer.

Im zweiten Fall jedoch, wenn eine Aussageform "Der Satz mit der Nummer x ist nicht beweisbar" vorkommt und auch eine Nummer hat, würde dadurch, dass man diese Nummer einsetzt, etwas völlig anderes daraus, nämlich eine Aussage über diese spezielle Nummer; eine Aussage, die wiederum eine Nummer hätte, die aber m. E. nicht mit der Nummer der ursprünglichen Aussageform übereinstimmen könnte. So käme jedenfalls kein Satz heraus, der sich auf sich selbst bezieht.

Auch wenn man davon ausgeht, dass es in der Aufzählung für jedes x einen Satz gibt, der "Der Satz mit der Nummer x ist nicht beweisbar" lautet, sehe ich nicht, warum einer dieser Sätze die Nummer x haben sollte.

Habe ich vielleicht irgendetwas missverstanden? 29.6.2005 Irene1949

Antwort: Das „Einsetzen“ ist im System repräsentierbar; man konstruiert also ein Klassenzeichen (eine Aussageform mit genau einer freien Variablen)

S(n)

, das *äquivalent* ist zu „das Klassenzeichen Nr. n ist, wenn man n einsetzt, nicht beweisbar.“ In dieses S(n) – und nicht in ¬Bew(x) – wird nun eingesetzt.

Diese *Äquivalenz* besteht aber nicht mehr im untersuchten formalen System selbst, sondern lässt sich „nur“ außerhalb, metamathematisch zeigen.

Vielleicht hilft auch die folgende Skizze:

Skizze von Gödels Beweis

Nicht nur die Sätze sind durchnummeriert, sondern alle Wörter des formalen Systems (sogar solche, die keine Aussagen darstellen, sondern nur Aussageformen, arithmetische Ausdrücke und völlig unsinnige Zeichenketten) und damit auch die Aussageformen. (Die Aufzählung, die Gödel angegeben hat, ist im Artikel Gödel-Isomorphismus als 2. Beispiel beschrieben.)
Eine (primitiv-rekursive) Aussageform $K$ des Systems mit genau einer freien Variablen nennt Gödel „Klassenzeichen“ (weil es eine Klasse von Zahlen definiert: Die Klasse aller Zahlen $n$ , für die $K(n)$ gilt). Alle primitiv-rekursiven Klassenzeichen sind in den untersuchten Systemen, da sie die Arithmetik beinhalten, repräsentierbar. (Ich bin fast, aber nicht völlig sicher, ob ich hier primitiv-rekursiv schreiben darf; Gödel hat diesen Begriff nicht benutzt, weil er ihn noch nicht kannte.)
Die primitiv-rekursiven Klassenzeichen des Systems seien selbst wieder durchnummeriert, und $R_{n}$ bezeichne das $n$ -te Klassenzeichen dieser Nummerierung.
Die „Beweisbarkeit“, d.h. Ableitbarkeit einer Formel mit der Gödelnummer $n$ entspricht einem im System ausdrückbaren Klassenzeichen $Bew(n)$ . Die Gödelnummerierung ist ebenfalls im System repräsentierbar; das rechtfertigt folgende Vereinbarung: $[R_{n};\,m]$ sei die Formel, die sich ergibt, wenn im Klassenzeichen $R_{n}$ für die freie Variable das Zahlzeichen der Zahl $m$ eingesetzt wird.
Nun gibt es ein Klassenzeichen $S$ , sodass $S(n)\equiv \neg Bew([R_{n};\,n])$ (≡ logische Äquivalenz im System) (Entspricht in Worten der Definition: $S(n)$ ⇔ es ist nicht beweisbar, dass das $n$ -te Klassenzeichen, wenn für die freie Variable wiederum $n$ eingesetzt wird, gilt.)
Da $S$ ein Klassenzeichen ist, gibt es ein $q$ mit $R_{q}=S$ .
Nun setzen wir $q$ in $R_{q}$ ein und erhalten eine Formel, die wir mit $[R_{q};\,q]$ angeben. (Entspricht in Worten: es ist nicht beweisbar, dass das $q$ -te Klassenzeichen, wenn für die freie Variable wiederum $q$ eingesetzt wird, gilt; also: die Aussage $R_{q}(q)$ gilt ⇔ die Aussage $R_{q}(q)$ ist nicht beweisbar. Daher kommt die Interpretation „Ich bin nicht beweisbar“).
Ist nun $R_{q}(q)$ ableitbar? Falls ja, wäre auch das logisch äquivalente $S(q)\equiv \neg Bew([R_{q};\,q])$ ableitbar, das besagt: Es ist nicht beweisbar, dass $R_{q}(q)$ gilt. Ist $R_{q}(q)$ widerlegbar? Falls ja, würde gelten: $\neg Bew([R_{q};\,q])\equiv S(q)\equiv R_{q}(q)$ und damit würde $R_{q}(q)$ gleichzeitig beweisbar und widerlegbar sein. Beides w[rde bedeutet einen Widerspruch im formalen System bedeuten.

Es wird also in ein Klassenzeichen $R_{q}$ – wobei $R_{q}(n)$ wahr ist gdw. die Aussage $R_{n}(n)$ unbeweisbar ist, $q$ eingesetzt und gezeigt, dass, falls $R_{q}(q)$ im System entscheidbar ist, das System widersprüchlich ist.

Dabei muss man beachten, dass Teile dieses Beweises „metamathematisch“ sind, das heißt im System nicht ausdrückbar sind: Zum Beispiel ist „ $S(n)$ ⇔ es ist nicht beweisbar, dass das $n$ -te Klassenzeichen, wenn für die freie Variable wiederum $n$ eingesetzt wird, gilt“ ein Satz der Metamathematik. Auch die Äquivalenz zwischen $Bew(x)$ und „Die Formel Nr. $x$ ist beweisbar“ ist eine metamathematische. Die Trennung dieser Ebenen – formales System einerseits, Metamathematik andererseits – wird oft zurecht betont; vielleicht sollten wir das im Artikel auch stärker betonen?

(Quelle: Die einleitende Zusammenfassung Gödels in seinem Aufsatz Über formal unentscheidbare Sätze... (1931))

--136.199.8.128 17:39, 26. Jul 2005 (CEST)

konstruktive Mathematik?

Im Artikel steht folgendes:

Übrigens konnte Gerhard Gentzen zeigen, dass eine konstruktive Mathematik und Logik durchaus widerspruchsfrei ist. Hier zeigt sich ein Grundlagenstreit der Mathematik. Der Philosoph Paul Lorenzen hat eine widerspruchsfreie Logik und Mathematik erarbeitet (Methodischer Konstruktivismus), und sein Buch Metamathematik (1962) eigens geschrieben, um zu zeigen, dass der Gödelsche Unvollständigkeitssatz keinen Einwand gegen einen widerspruchsfreien Aufbau der Mathematik darstellt.

Also, soweit ich das verstehe, steht das in keinem Widerspruch zum Unvollständigkeitssatz - auch die "normale" Arithmetik ist Widerspruchsfrei - nur ist sie eben nicht vollständig. Auch gibt es Systeme, die vollständig und widerspruchsfrei sind (z.B. die Aussagenlogik) - nur sind diese weniger mächtig als die Arithmetik (bzw. eine Turinmaschine). Interessant wäre doch zu erfahren, ob Gentzen ein System gefunden hat, dass a) widerspruchsfrei, b) vollständig und c) die Arithmetik abbilden kann - das stünde im Widerspruch zu Gödelschen Unvollständigkeitssatz.

In konstruktive Mathematik steht:

Formal betrachtet handelt es sich um ein axiomatisches System, das weniger expressiv ist als die Mathematik.

Scheint mir also mit dem Unvollständigkeitssatz kompatibel zu sein. Kennt sich damit jemand aus? Der entsprechende Absatz sollte entweder ausgebaut und erläutert werden, oder aber entfernt - so ist er nur irreführend. -- D. Dÿsentrieb ⇌ 23:34, 21. Aug 2005 (CEST)

Lesenswerte-diskussion

Pro Antifaschist 666 00:43, 17. Okt 2005 (CEST)

Contra --Elian Φ 02:52, 21. Okt 2005 (CEST)
Kontra--Sentry 23:15, 21. Okt 2005 (CEST)
Kontra Wird sind hier zwar nicht bei den exzellenten, aber der Artikel verscheucht die gute alte Oma ja schon in der Einleitung. Hier Gödel selbst zu zitieren ist definitiv nicht förderlich für den Leser. Außerdem erscheint mir die Gliederung etwas komisch. Die Grundbegriffe würde ich nicht extern abhandeln, sondern an der Stelle wo sie gebraucht werden in den Text einbauen. Und auch wenn ich es nicht genauer spezifizieren kann: Der Text liest sich dafür dass er lesenswert sein sollte recht holprig... Regnaron 23:11, 24. Okt 2005 (CEST)