Diskussion:Gödelscher Unvollständigkeitssatz

Diese Diskussionsseite dient dazu, Verbesserungen am Artikel „Gödelscher Unvollständigkeitssatz“ zu besprechen. Persönliche Betrachtungen zum Thema gehören nicht hierher. Für allgemeine Wissensfragen gibt es die Auskunft.

Füge neue Diskussionsthemen unten an:

Klicke auf Abschnitt hinzufügen, um ein neues Diskussionsthema zu beginnen.

• Diskussionsregeln
• Hilfe zu Diskussionsseiten
• Sei sachlich und freundlich!
• Greife niemanden persönlich an!
• Geh von guten Absichten aus.

Erste Diskussionsbeiträge

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.

---

Meiner Ansicht nach sind erhebliche Fehler im Absatz Grundbegriffe. Zuersteinmal steht dort etwas über "allgemein akzeptierte Ableitungsregeln". Das hört sich meiner ansicht nach sehr willkürlich an. In Wahrheit werden die Ableitungsregeln doch gerade so gewählt, dass das Kalkül vollständig ist, dass heißt, dass die Modell-Beziehung mit der Ableitungsbeziehung übereinstimmt, d.h. so dass der Gödelsche Vollständigkeitssatz gilt. Um dann die Beteutung der Worte „Vollständig“ und „Unvollständig“ im Kontext des Unvollständigkeitssatzes einzuführen, ist es Notwendig, den Begriff Modell zumindest auf irgend eine Art und Weise einzuführen, da ja die Modell-Beziehung bezüglich Axiomensystemen immer „vollständig“ ist und nur die Modell-Beziehung bezüglich Modelle dieser Axiomensysteme nicht „vollständig“ ist. (Hierbei ist die unterschiedliche Bedeutung des wortes vollständig zu beachten!) --84.44.158.175 21:57, 27. Jun 2006 (CEST)

---

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)

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)

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

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

Hast völlig recht. Erstens sagt 'Bew(x)' gar nichts, weil es noch eine freie Variable enthält und folglich gar keine Aussage ist, zweitens müsste es natürlich heißen "angenommen, 12345 wäre die Gödelnummer von ¬Bew(12345), dann ist ¬Bew(12345) eine nicht beweisbare Aussage" usw. 88.73.250.239 23:15, 1. Dez. 2006 (CET)

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

1. 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.)
2. 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.)
3. Die primitiv-rekursiven Klassenzeichen des Systems seien selbst wieder durchnummeriert, und $R_{n}$ bezeichne das $n$-te Klassenzeichen dieser Nummerierung.
4. 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.
5. 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.)
6. Da $S$ ein Klassenzeichen ist, gibt es ein $q$ mit $R_{q}=S$.
7. 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“).
8. 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 Turingmaschine). 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)

Das obige Zitat ist m.E. in der Tat in den Artikel nicht eingebunden und widerspricht oberflächlich dem Unvollständigkeitssatz. Ich vermute, dass kein Widerspruch besteht, da die konstruktive Mathematik in ihrem Anwendungsbereich "beschränkt(er)" sein dürfte.

Auch im Artikel Metamathematik erscheint mir eine neutralere Einordnung der Verdienste von Gentzen sinnvoll.

--Hans-Jürgen Streicher 22:58, 29. Aug. 2010 (CEST)

Der Gödelsche Unvollständigkeitssatz wurde im Rahmen eines bestimmten Typs von Formalismus formuliert. Es gibt davon aber laut Esslers Grundzüge der Logik Band II wenigstens drei. Der Satz besagt nicht, dass es keine vollständige und widerspruchsfreie Mathematik geben kann, er besagt nur, dass in solchen Logiktypen der Versuch, mithilfe der selben Zeichen, die die Axiome definieren, die Widerspruchsfreiheit und Vollständigkeit des ganzen Systems zu beweisen, an einem selbstreferentiellen Widerspruch, der formal konstruierbar ist (und in der PM eben nicht so formulierbar wäre), scheitern muss. Es handelte sich hierbei auch um einen Beweis mit finiten Methoden, was eine weitere Einschränkung bedeutet. Mittlerweile wurde auch der Versuch mit transfinitien Methoden eingehend thematisiert, aber in dem Artikel finde ich das alles nicht adäquat wiedergegeben, sondern vielmehr populärwissenschaftliche Auffassungen, die zu wilden Spekulationen einladen a la "Die Logik und das Universum haben eine Gagaseite". Kann ja sein, aber dafür sollte man doch bitte keine Sätze fälschen. -- ClydefrogL 12:01, 10. Feb. 2012 (CET)

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)

Vollständigkeit

Der Begriff Vollständigkeit so wie er im Abschnitt Grundbegriffe gebraucht wird entspricht nicht der Bedeutung der Vollständigkeit im Rahmen des Unvollständigkeitssatzes (Negationsvollständig), sondern dem Vollständigkeitsbegriff wie er im Vollständigkeitssatz verwendet wird. Dies ist Grundsätzlich nichts falsches aber gehört nicht auf diese Seite - sondern auf die des Vollständigkeitssatzes!

Rechtschreibung: „Gödelscher Unvollständigkeitssatz“ oder „gödelscher Unvollständigkeitssatz“?

Soeben habe ich festgestellt, dass jemand die Bezeichnung „Gödelscher Unvollständigkeitssatz“ umgeändert hat in „gödelscher Unvollständigkeitssatz“. Als Begründung wurde eine Regel aus dem DUDEN angeführt.

Das mag ja so im DUDEN stehen, aber ob es in diesem Fall sinnvoll ist, das ist eine zweite Frage. Meiner Auffassung wird „Gödelscher Unvollständigkeitssatz“ dort, wo man davon spricht, als Eigenname für einen bestimmten Satz gebraucht; weshalb „Gödelscher“ m. E. großgeschrieben werden sollte. Der DUDEN kann nicht alle zusammengesetzten Begriffe kennen, die in bestimmten Fachgebieten üblich geworden sind.

Was meint ihr? -- Irene1949 12:39, 19. Mär 2006 (CET)

Du hast die Wahl: Entweder schreibst du „Gödel'scher Unvollständigkeitssatz“ oder „gödelscher Unvollständigkeitssatz“. Das Apostroph macht den Unterschied. Siehe auch die amtliche Regelung Deutsche Rechtschreibung: Regeln und Wörterverzeichnis, § 62: „Kleingeschrieben werden adjektivische Ableitungen von Eigennamen auf -(i)sch, außer wenn die Grundform eines Personennamens durch einen Apostroph verdeutlicht wird, ferner alle adjektivischen Ableitungen mit anderen Suffixen.“ (Seite 66). --jpp ?! 17:56, 19. Mär 2006 (CET)

Zufällig stolpere ich jetzt doch noch über diese Frage. Damit ist wohl meine Änderung gemeint, allerdings habe ich nicht den Artikel auf neue Rechtschreibung umgestellt, sondern diese Änderung von jemand anderem rückgängig gemacht: Ich habe keine besondere Präferenz für die eine oder andere Schreibweise, aber ich finde, man muss nicht noch 2006 die neue und seit zehn Jahren geltende Schreibung aktiv auf die alte und nicht mehr korrekte ändern.

Das offizielle Regelwerk ist jedenfalls eindeutig, siehe z.B. diesen Link.

Viele Grüße, --GottschallCh 08:35, 21. Mär 2006 (CET)

Wir sind nicht verpflichtet, alles so zu machen, wie es im Duden steht. Nach Angaben von Pill tun die deutschsprachigen Presseagenturen das ja auch nicht.

Und auch in Wikipedia richtet man sich nicht immer nach dem Duden. Für biblische Namen gibt es beispielsweise die Regel: „Für Eigennamen in der Bibel erwähnter Personen, Bücher, Landschaften etc. verwendet die Wikipedia das Ökumenische Verzeichnis der biblischen Eigennamen nach den Loccumer Richtlinien (ÖVBE).“ (Wikipedia:Namensgebung biblische Namen).

Dabei wäre es viel sinnvoller, sich bei der Schreibung biblischer Namen nach dem Duden zu richten, weil der Duden sich dabei nach dem allgemeinen Sprachgebrauch richtet. Während der Duden sich mit der Forderung, das „Ohmsche/ohmsche Gesetz“ (und entsprechend wohl den Gödelschen/gödelschen Unvollständigkeitssatz) mit kleinen Anfangsbuchstaben oder mit Apostroph zu schreiben, in Gegensatz zum allgemeinen Sprachgebrauch setzt.

Eindeutig ist die Duden’sche Regelung übrigens nicht: „Großgeschrieben wird auch, wenn die Fügung als Ganzes ein Eigenname ist (vgl. R 56). die Meyersche Verlagsbuchhandlung; der Halleysche Komet“ (Duden, 21. Auflage, auf der Grundlage der neuen amtlichen Rechtschreibregeln, R 94) So wenig der Halleysche Komet ein Eigentum des Herrn Halley ist, so wenig ist der Gödelsche Unvollständigkeitssatz ein Eigentum des Herrn Gödel; Herr Gödel ist, ebenso wie Herr Halley, nur der Entdecker. Der „Gödelsche Unvollständigkeitssatz“ bezeichnet nicht einen bestimmten Satz, den Herr Gödel mal in einer bestimmten Formulierung zu Papier gebracht hat – vielmehr bezeichnet er eine bestimmte Erkenntnis, die heute vielfach ganz anders formuliert wird. Für den Satz gilt etwas anderes als für die Formulierung: Die gödelsche Formulierung des bekannten Satzes hat sich nicht in der gleichen Weise verselbstständigt, und da sähe ich keinen Grund, „gödelsche“ großzuschreiben. -- Irene1949 15:38, 21. Mär 2006 (CET)

Die Unterscheidung zwischen einer gödelschen Formulierung und dem gödelschen Unvollständigkeitssatz ist das Entscheidungskriterium der alten Rechtschreibung. Die neue Rechtschreibung lässt dieses Kriterium weg und sieht durchgängig Kleinschreibung vor, außer es handelt sich um Eigennamen (die auch bisher groß geschrieben wurden); will man den Namen besonders hervorheben, darf man das ohnedies durch Großschreibung plus Apostroph ("eine Gödel'sche Formulierung").

Den Hinweis aufs Eigentum kann ich nicht so recht interpretieren, denn Eigennamen haben ja nichts mit Eigentum zu tun, sondern benennen eine natürliche oder juristische Person ("Gödelsche Verlagsbuchhandlung"), einen (geographischen) Ort im weitesten Sinn ("Gödelscher Komet") oder ein Werk ("Faust II"). "Halleyscher Komet" ist der Eigenname eines Himmelskörpers, "Gödelsche Satzverwertungsgesellschaft" ein Firmenname, und schließlich könnte es sogar ein Buch des Titels "Gödelscher Unvollständigkeitssatz" geben, das den gödelschen Unvollständigkeitssatz behandeln würde. Dass ein Sprachausdruck genau einen Gegenstand benennt, macht ihn aber nicht zum Eigennamen im grammatikalischen Sinn, sonst müsste man z.B. auch "Gegenwärtige Bundeskanzlerin Deutschlands" schreiben. Ich finde die vom Duden gebrachten Beispiele "Halleyscher Komet" versus "ohmsches Gesetz" ohnedies recht illustrativ. Wenn es aber der gödelsche Unvollständigkeitssatz in Person sein soll, dann habe ich hier nur den "Brockhaus in Text und Bild 2006", darin ist "gšödelscher UnvollstŠndigkeitssatz" ein Lemma. Viele Grüße, --GottschallCh 03:38, 23. Mär 2006 (CET)

Nach den Empfehlungen des Rats für deutsche Rechtschreibung, S. 17, soll man Verbindungen wie "das Schwarze Brett" wieder großschreiben dürfen. Es wäre sinnvoll, diese Regelung auch auf das Ohmsche Gesetz und den Gödelschen Unvollständigkeitssatz auszudehnen.

Normalerweise bin ich ja ein Fan der neuen Rechtschreibung, aber in ein paar Einzelheiten sind die Regelungen der alten Rechtschreibung entschieden vorzuziehen. Viele Grüße -- Irene1949 19:06, 23. Mär 2006 (CET)

Die Preisfrage lautet also: Ist der Gödel'sche Satz ein Eigenname? Da ich ihn im Studium ohnehin eher als „Satz von Gödel“ kennengelernt habe, denke ich, dass er kein Eigenname ist. --jpp ?! 08:43, 24. Mär 2006 (CET) PS: Vielleicht sollten wir den Artikel in „Unvollständigkeitssatz von Gödel“ umbenennen um diesen fruchtlosen Disput zu beenden? ;-)

Nee, bitte nicht umbenennen. Es gibt Dutzende von Links auf den Artikel.

Wir können den Disput auch einfach so beenden. -- Irene1949 15:05, 24. Mär 2006 (CET)

Frage

Hat der Gödelsche Unvollständigkeitssatz Relevanz für die Kantsche Philosophie? (Widerlegung/Bestätigung); Ich beziehe mich auf "Kritik der reinen Vernunft"

Viel wichtiger ist doch der Unverständlichkeitssatz!

Wie? Ihr kennt ihn nicht, denn Knödelschen Unverständlichkeitssatz? --Wutzofant (✉✍) 13:29, 26. Jun 2006 (CEST)

begriff der mächtigkeit

im artikel wird der begriff "mächtigkeit" zweideutig verwendet: einmal soll er wohl ausdrucksstärke einer sprache, ein ander mal im sinne von kardinalität bedeuten.

Genau. Im Sinne von Kardinalität wird der Begriff hier nur an einer Stelle verwendet, beim Satz von Löwenheim-Skolem. Ich habe deshalb in der Einführung den Link von "Mächtigkeit" auf "Mächtigkeit (Mathematik)" entfernt.

Vielleicht fällt ja jemandem eine bessere Formulierung bzw. ein anderes Wort statt "Mächtigkeit" ein. Wenn ich mich nicht täusche, dann geht es nicht nur um die Ausdrucksstärke der Sprache, sondern auch darum, dass, wenn man das Beweisen geeignet kodiert, genügend Sätze über das Beweisen aus der Theorie ableitbar sind. Oder ist das in "Ausdrucksstärke" schon enthalten?--Digamma 20:44, 14. Dez. 2006 (CET)

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

Verzeihung, aber so funktioniert das doch nicht! Damit „¬B(12345)“ der Aussage entspräche „Ich bin nicht ableitbar“, müsste „12345“ doch die Gödelzahl von „¬B(12345)“ sein, und nicht die Gödelzahl von B(x)! 195.23.188.181 19:09, 6. Mär. 2007 (CET)egibiedermann

Das sehe ich genauso. Im zitierten Artikelteil wird ja die Diagonalisierung d(x) gar nicht verwendet, und die ist doch der Clou des Beweises. So müsste es stimmen:

"Besagt" der Ausdruck B(x) also, dass die Formel mit der Gödelnummer d(x) nicht ableitbar ist, und ist zum Beispiel 12345 die Gödelnummer von B(x), so ist B(12345) eine nicht ableitbare Aussage. Diese Aussage besagt dann nämlich: Die Formel mit der Gödelnummer d(12345) ist nicht ableitbar. 12345 ist aber die Gödelnummer von B(x), also d(12345) die Gödelnummer von B(12345). Also sagt B(12345): Ich bin nicht ableitbar. --Usc 21:32, 2. Nov. 2007 (CET)

In der deutschen Übersetzung von Hofstadters Metamagikum wird der Begriff leistungsstark statt mächtig verwendet. Ich halte das für eine gute Wortwahl, weil die Verwechslung mit Kardinalität damit ausgeschlossen ist, und habe im Artikel entsprechend geändert. --Mussklprozz (Diskussion) 21:15, 15. Mär. 2012 (CET)

Einleitung

Ich habe versucht, aus dem ersten Abschnitt so etwas wie eine Einleitung zu machen. Das Zitat darüber, daß sich jede Antinomie verwenden ließe, paßte weder dorthin noch sonstwo im aktuellen Artikel. Die "Diagonalisierung" interessiert in der Einleitung nicht und ist daher in den Beweis verschoben. Ob allerdings der Link auf Cantors zweites Digonalargument überhaupt hilfreich ist, wage ich zu bezweifeln.--Pangloss Diskussion 15:42, 29. Dez. 2007 (CET)

Satz stimmt so nicht

Die Formulierungen der beiden Sätze sind so nicht ganz korrekt. Es stimmt nicht, dass es keine vollständigen Formalen Systeme gibt, beispielsweise ist ja für jedes Modell N die Theorie Th(N) vollständig (oder auch Vervollständigungen über die Aufzählung von Sätzen). Der Satz gilt nur unter der zusätzlichen Voraussetzung, dass die Eigenschaft "Beweis sein" entscheidbar ist, nur dann lassen sich nämlich die Diagonalsätze überhaupt formulieren. --160.45.44.237 10:22, 17. Mär. 2008 (CET)

Fehler im Abschnitt "Genauere Formulierung"

Momentan steht

Viel Verwirrung entsteht aus dem Zusammenhang der Gödelschen Unvollständigkeitssätze mit dem Gödelschen Vollständigkeitssatz. Der Gödelsche Vollständigkeitssatz besagt, dass in der Prädikatenlogik erster Stufe (PL1) alle ableitbaren Sätze wahr, und umgekehrt alle wahren Sätze ableitbar sind, und damit, dass Syntax und Semantik für die PL1 zusammenfallen.

Im Gegensatz dazu wird in den Unvollständigkeitssätzen bereits ein Modell betrachtet, die Struktur der natürlichen Zahlen, die Peano-Arithmetik. Die Unvollständigkeitssätze sagen dann aus, dass in diesem Modell wahre Sätze existieren, die in der Prädikatenlogik erster Stufe nicht abgeleitet werden können. Da sie wahr sind in PA, zeigt dies auch, dass die Peano-Arithmetik nicht in PL1 (bis auf Isomorphie) formalisiert werden kann.

Hier haben sich gleich zwei Fehler eingeschlichen.

1. Der Volltändigkeitssatz besagt nicht, dass "wahr => ableitbar", sondern "semantisch ableitbar => syntaktisch ableitbar", d.h. wenn in jedem Modell einer Formelmenge S eine eine Formel F auch gilt, dann findet man einen Beweis von F aus S. Eine wahre Aussage muss dagegen nicht ableitbar sein, dass ist gerade eine Konsequenz des Unvollständigkeitssatzes.

2. Die Peano-Arithmetik (vielleicht sollte man hier sowieso einen anderen Namen wählen, da "Peano-Arithmetik" schon für ein bestimmtes formales Sytem in first order logic belegt ist und damit per definitionem formalisierbar ist, siehe [[2]]) ist durchaus in der Prädikatenlogik erster Stufe formalisierbar, man nimmt einfach die Menge aller Formeln, für die die natürlichen Zahlen ein Modell sind. Was man dabei aber verliert ist die Entscheidbarkeit der Formelmenge, die eben auch wichtig ist und in der Formulierung des Unvollständigkeitssatzes immer wieder vergessen wird.

Des weiteren habe ich die Formulierung PL1 noch nie gesehen, wird die wirkliche gebraucht?

--Godfatherofpolka 09:41, 7. Mai 2008 (CEST)

Fehlende Quellenangabe "Für jedes hinreichend mächtige..."

"Jedes hinreichend mächtige formale System ist entweder widersprüchlich oder unvollständig." dem beschreibungstext nach kommt das zitat wohl aus dem 1931 erschienenen aufsatz: "Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I"

hier als volltext zu lesen: http://www.springerlink.com/content/p03501kn35215860

kann darin aber nirgends den zitierten satz finden. wo kommt er her? hat gödel ihn überhaupt mal so geschrieben?

Unentscheidbarkeit

Im Artikel kommt der Begriff "entscheidbar " in zwei verschiedenen Bedeutungen vor. Problematisch. Siehe auch Diskussion:Kurt Gödel. --AlfonsGeser 22:44, 12. Jun. 2008 (CEST)

Bezugnehmend auf die folgenden Sätze im Abschnitt 'Genauere Formulierung'

       „Paul Cohen bewies ..., dass  ... die Kontinuumshypothese  ... formal unentscheidbar ... . 
        Er fand damit die ersten Beispiele mathematisch bedeutsamer unentscheidbarer Sätze,
        deren Existenz Gödel bewiesen hatte.“ 

würde ich gern wissen, wie man folgendem Einwand begegnet:

        Die Unentscheidbarkeit der Kontinuumshypothese (bezüglich der ZF-Axiome) wird (nicht nur) hier
        als das Beispiel für den 1. Unvollständigkeitssatz (UVS) gepriesen. 	
        Aber nur, wenn die Kontinuumshypothese nicht nur unentscheidbar, sondern auch wahr wäre, 
        wenn also die Kontinuumshypothese eine These wäre, (davon kann aber wohl keine Rede sein),
        dann erst läge ein Beispiel für den UVS vor; 
        dann hätten wir den spektakulären Fall der Unvollständigkeit (im Sinne des UVS) einer Theorie, 	
        in der (wie es das primäre Resultat von Gödels Beweis sagt) 
        nicht alle wahren Sätze bewiesen werden können. 
        Nur unentscheidbare Aussagen zu finden, ist kein Problem; davon gibt es unendlich viele.

        Es gilt zwar:  wahr und nicht beweisbar   impliziert unentscheidbar.
               Für eine Aussage A 
               und mit der auch in Gödels Beweis verwendeten Beziehung    beweisbar(A) impliziert A 
               gilt    [ A und  nicht beweisbar(A) ] impliziert unentscheidbar(A)  
        Aber der Umkehrschluß gilt i.allg. nicht!

                                                                    -- Jürgen Gruel 13:39, 5. Jul. 2008 (CEST)

Klassifikation der unbeweisbaren Sätze

Der Gödelsche Unvollständigkeitssatz ist sehr allgemein. Die Frage ist, ob man überhaupt beweisen kann, daß ein konkreter Satz unbeweisbar ist. Oder beißt sich hier die Katze in den Schwanz? Betrachten wir das leidige Beispiel Riemannsche Vermutung. Einige (wenige) Mathematiker sind der Meinung, daß diese sich nicht beweisen läßt. Aber beweisen können sie das nicht! Vielleicht ist ja der Satz "die RV ist unbeweisbar" nicht beweisbar.

Andererseits stellt sich die Frage welche Elemente der Mathematik man nehmen muß, um überhaupt in Gebiete von möglicherweise unbeweisbaren Sätzen zu kommen? Gibt es denn in der Zahlentheorie und der Cauchyschen Funktionentheorie über komplexen Zahlen überhaupt unbeweisbare Sätze? Ein naheliegendes Beispiel ist vielleicht das Collatz-Problem. Hier geht es aber schon um Existenzfragen ob bei jeder Startzahl nach endlich vielen Schritten die 1 erreicht wird. --Skraemer 17:48, 5. Jul. 2009 (CEST)

Abschnitt Satz: "entweder" widersprüchlich oder unvollständig - das ist doch falsch !?

Im Artikel steht unter Grundbegriffe: "Jedes hinreichend mächtige formale System ist entweder widersprüchlich oder unvollständig."

Das "entweder" ist hier doch falsch !? Es ist zwar richtig, dass ein hinreichend mächtiges System nicht zugleich vollständig und widerspruchsfrei sein kann, ABER: Ein hinreichend mächtiges System könnte doch zugleich widersprüchlich und unvollständig sein? (einfach weil ein widerprüchliches System potentiell jede Eigenschaft haben kann).

Ist es nicht besser stattdessen im Artikel die beiden Unvollständigkeitssätze aufzuführen:

1. Unvollständigkeitssatz Jedes hinreichend mächtige (und widerspruchsfreie) System ist unvollständig. 2. Unvollständigkeitssatz Kann aus einem System dessen Widerspruchsfreiheit abgeleitet werden, so ist es widersprüchlich. --GG1958 21:46, 24. Jan. 2010 (CET)

Jedes widersprüchliche System ist auch gleichzeitig vollständig. Das liegt daran, dass man aus Falsum alles andere ableiten kann. (Aus a und aus non a folgt jede beliebige Aussage. Damit kann man also alles beweisen. Und damit ist es vollständig.) --Eulenspiegel1 17:09, 26. Jan. 2010 (CET)

Im Endeffekt ist ein widersprüchliches formales System eigentlich gar kein formales System, weil es nicht funktioniert, oder? --stfn 21:14, 18. Jun. 2010 (CEST)

"Funktionieren" ist keine Voraussetzung für ein formales System. Kurz gesagt ist ein formales Sytsem erstens ein System und zweitens formal. Wenn man Widerspruchsfreiheit in die Definition des Begriffs aufnehmen wollte, hätte man das Problem, dass man von viel zu wenigen Systemen wüsste, ob es sich um ein formles System handelt.--Hagman 21:41, 18. Jun. 2010 (CEST)

Die Unmöglichkeit von Gödels selbsreferenter Formel

Bei alledem bleibt es doch ein Faktum, dass im System P der Principia Math. keine Formel ihre eigene Gödelnummer enthalten kann. Die Gn einer Formel mit z.B. 100 Symbolen ist das Produkt der ersten 100 Primzahlen, die noch dazu mit diversen Exponenten versehen sind. Diese Zahl ist weit größer als 10 hoch 100. Im System P und mit Gödels Forderung in seiner Fußnote 6, dass keine Definitionen oder Abkürzungen verwendet werden dürfen, ist dies eine fff. . .0 - Sequenz mit derart vielen f - Symbolen. Eine solche Sequenz kann nicht einmal in unserem ganzen Universum mit seinen ca 10 hoch 80 Elementarteilchen existieren, geschweige denn innerhalb der Formel mit ihren 100 Symbolen enthalten sein. --Egibiedermann 14:40, 7. Jun. 2010 (CEST)

Die Beschränkungen unseres kümmerlichen Universums sind irrelevant. Außerdem muss nicht die Gödelnummer als Literal enthalten sein, sondern eine eindeutige Beschreibung. So wäre ffff0*ffff0 statt fffffffffffffffffffffffff0 zulässig.--Hagman 21:03, 18. Jun. 2010 (CEST)

Dieser Vorschlag steht aber im Gegensatz zu Gödels Anspruch (siehe seine Fußnote 6 ) daß keine Definitionen benutz werden dürfen, daß eine Formel im System P ausschließlich aus den Grundsymbolen besteht, und dass eine Zahl nie etwas anderes ist als eine fff-0 sequenz! Freilich benutzt Gödel für die Konstruktion seiner Formel G dann selbst die Definitionen Sb(x,x,x) für die Substitutionsfunktion, und Z(x) für die Gödelzahl der Zahl x. Für diese Definitionen hat er aber keine Gödelzahlen, und somit hängt seine ganze Formel G in der Luft. E.Biedermann Egibiedermann 12:33, 29. Jun. 2010 (CEST)

Ich füge noch hinzu: Gödels Beweis ist dem Lügnerparadoxon nachempfunden. Dieses "dieser satz ist falsch" beruht aber mathematisch gesehen auf der Gleichsetzung von 2 = 4 . Und Gödels Beweis beruht daher zwangsläufig ebenfalls auf der Gleichsetzung zweier verschiedener "Dinge" ! Dies geschieht in der so hoch gelobten "Diagonalisierung", in der Gleicchsetzung " x = Gödelzahl von A(x)" , also einmal x = freie Variable in A(x) und gleichzeitig = Gödelzahl von A(x) . Wenn ich in dem Ansatz "x = Gödelzahl von A/x)" die freie Variable an beiden Stellen gleichzeitig durch eine Ziffer, z.B. die 1 einsetze, wie ich das bei jedem korrekt gebildeten mathematischen Ansatz immer darf, dann erhalte ich die unsinnige Gleichung " 1 = Gödelzahl von A(1) " . Dabei sind die beiden Gödelzahlen völlig undefiniert, die Funktion A() ist nicht definiert, ebenso wie die zu wählende Art der Gödelisierung. Es kann also nicht behauptet werden, "Gödelzahl von A(x)" sei ganz einfach eine Zahl. -- Egibiedermann 11:16, 12. Jul. 2010 (CEST)

Ich stimme der Auffassung zu, dass ein Satz, der seine eigene Gödelnummer als Argument enthielte, in der Typentheorie unzulässig ist, wenn die Gödelnummer des Satzes so verwendet wird wie die Gödelnummer innerhalb des Satzes. Die Gödelnummer außerhalb spricht über den Satz und steht damit logisch eine Stufe über dem Satz. Die Gödelnummer innerhalb des Satzes wird als Argument des Satzes verwendet und ist damit ein Bestandteil des Satzes und folglich mindestens in der Ebene des Thematisierten enthalten, also jedenfalls eine Stufe unter der Gödelnummer außen. Ich bin mir nicht ganz sicher, ob wir in der PM selbstreferentiell logische Verkettungen zulassen wollen wie "kann abgeleitet werden", aber wenn wir die Klammerkonvention der Typentheorien akzeptieren, müsste der Satz so formuliert werden.

G_2(A(G_1))

oder auf verwandte Weise und es gilt: G_2 nicht identisch G_1. Ob die Substitutionsregel und Z(x) in der Luft hängen, habe ich noch nicht überprüft, werde dies aber und bedanke mich für den Hinweis. -- ClydefrogL 11:52, 10. Feb. 2012 (CET)

Einige Änderungen

Ich habe an dem Artikel einige Änderungen vorgenommen, die ich hier begründe:

1. Ändern der Passage "und in Gebieten, die sich mit dem Phänomen von bewussten Entscheidungen im Unterschied zu berechenbaren auseinandersetzen, sowie anderen philosophischen Disziplinen, die auf deren Erkenntnisse aufbauen " zu "und in anderen Gebieten der Philosophie" .

Der hier verlinkte Begriff der Berechenbarkeit bezieht sich, auch laut dem verlinkten Artikel, auf Funktionen von Teilmengen von $\mathbb {N} ^{k}$ nach $\mathbb {N}$. Es ist somit sinnlos, von berechenbaren Entscheidungen zu sprechen. Auch ansonsten erscheint mir die Formulierung unglücklich. Ich gehe davon aus, dass das Verhältnis von in irgendeinem Sinne freien und vorausbestimmten Entscheidungen gemeint ist, wobei natürlich beide Arten bewusst sein könnten, wage das aber nicht mit Bestimmtheit zu beurteilen. Zur Löschung ist m.E. oben genanntes Problem schon Grund genug. Da später Beispiele genannt werden, die wohl diese Passage stützen sollen, habe ich sie durch den obigen vage gehaltenen Text ersetzt, statt sie zu löschen. Das kann ja durch jemanden präzisiert werden, der weiß, wo genau die im Artikel folgenden Beispiele einzuordnen sind.

2. Überarbeitung des Abschnitts "Grundbegriffe"

In diesem Abschnitt wurde ein missverständliches Konzept von Wahrheit von formalen Aussagen vermittelt: "Aussagen sind dabei Folgen von Zeichen, [...] die mittels einer Semantik eine Bedeutung erhalten und sich dadurch in wahre und falsche Aussagen unterteilen lassen" Für eine Aussage wird nicht allgemein festgelegt, ob sie wahr oder falsch ist. Vielmehr definiert man, wann eine Aussage in einer gegebenen Struktur(Struktur im Sinne der Modelltheorie) wahr ist. Im allgemeinen gibt es Aussagen, die in manchen Strukturen wahr, in anderen falsch sind. Die neue Version trägt dem nun Rechnung.

Im unteren Teil der alten Version wird der Begriff "allgemeingültig" falsch verwendet(Aussagen, die aus einem Axiomensystem wie etwa PA folgen, sind nicht automatisch allgemeingültig. Allgemeingültig sind nur die, die schon aus der leeren Theorie folgen).

Die Darstellung ist in meinen Augen auch nicht ganz neutral. "Im Idealfall wünscht man sich, dass aus der Menge der Grundaussagen und den Ableitungsregeln alle wahren Aussagen abgeleitet, also bewiesen werden können." Damit wird ein realistischer(im Sinne der Einteilung der verschiedenen Positionen in der Philosophie der Mathematik) Standpunkt bezogen, indem von Wahrheit unabhängig von einem zugrundeliegenden Axiomensystem gesprochen wird. (Es sei denn, es wird nur der Versuch thematisiert, die Theorie einer Struktur wie etwa der der natürlichen Zahlen durch ein Axiomensystem zu beschreiben oder möglichst gut zu beschreiben. In dem Fall wären die Ausführungen an der Stelle wohl neutral, aber dass dieser Blickwinkel eingenommen würde, geht aus dem Text jedenfalls nicht klar hervor; der Auszug "aus bestimmten Grundaussagen (Axiome), die generell als wahr angenommen werden" legt sogar eher die Realismus-Deutung nahe.) (nicht signierter Beitrag von 79.216.153.118 (Diskussion) 22:45, 23. Jul 2010 (CEST))

Außerdem hat die bisherige Version den Begriff der Negation vermieden und etwas schleierhaft von "komplementären Aussagen" gesprochen. Ich denke, der Begriff "Negation", oder zumindest "Verneinung", ist allgemein geläufig.

Zusätzlich habe ich Erklärungen zu verschiedenen Folgerungsbegriffen eingeflochten.

Kann bitte jemand meine Definition von Vollständigkeit vervollständigen? Ich kenne den Begriff so, dass er die Widerspruchsfreiheit mit fordert, bin mir aber nicht sicher, ob das allgemein üblich ist. Um das Problem zu umgehen, habe ich nur definiert, wann eine widerspruchsfreie Theorie vollständig ist. Wäre gut, wenn jemand, der sich mit den Standards auskennt, das noch ausbessert.

-- Makor (20:14, 23. Jul 2010 (CEST), Datum/Uhrzeit nachträglich eingefügt, siehe Hilfe:Signatur)

Hab ein paar Leerzeichen spendiert, einen Satz der Verständlichkeit halber leicht umgestellt und aus einem "formalen Beweisbegriff" einen "formalisierten Beweisbegriff" gemacht (in erster Linie um "Formalisierung" verlinken zu können, denke der Sinn bleibt bei dieser Umformulierung bewahrt). "Vollständig" und "korrekt" wollte ich eigentlich auch verlinken, allerdings ist mir nicht ganz klar ob der Artikel Vollständigkeit (Logik) richtig und gut ist (ich finde ihn trotz Kenntnis des Themas verwirrend). Freue mich über Feedback zu letztem Punkt. Gruß --stfn 22:52, 23. Jul. 2010 (CEST)

Literaturverzeichnis

Soll es hier irgendeine Ordnung geben? (Alphabet/Erscheinungsjahr?) --Hans-Jürgen Streicher 23:03, 29. Aug. 2010 (CEST)

Lemma

Den Gödelschen Unvollständigkeitssatz gibt es nicht. Es gibt zwei Sätze, die beide Gödelscher Unvollständigkeitssatz heißen:

• Der erste Gödelschen Unvollständigkeitssatz sagt, grob gesprochen, dass jedes rekursvie Axiomensystem der Prädikatenlogik der ersten Stufe, das die Peano-Arithmetik umfasst, unvollständig ist.
• Der zweite Gödelsche Unvollständigkeitssatz folgt aus dem ersten, aber ohne ein einfaches Korollar zu sein. Er besagt, dass ein Axiomensystem, das so ausdrucksstark ist wie das der Peano-Arthmetik der ersten Stufe, nicht in der Lage ist, seine eigene Widerspruchsfreiheit zu beweisen.

Der Artikel behandelt im Wesentlichen den ersten Satz. Es ist aber der zweite, der der Hilbertsche Programm scheitern lässt. -- Digamma 14:56, 29. Dez. 2010 (CET)

Variablenbezeichnung

Im letzten Satz des Abschnittes Gödelscher Unvollständigkeitssatz: Grundbegriffe wird zweimal ein A verwendet. Sollten jene zwei Variablen nicht unabhängig sein?

-- 91.36.242.161 23:06, 11. Jul. 2011 (CEST)

Wenn du den Satz meinst:

Eine Theorie T heißt genau dann vollständig, wenn für alle Aussagen A aus T die Aussage A oder deren Negation folgt

, dann: Nein. --Daniel5Ko 23:44, 11. Jul. 2011 (CEST)

Typenfreie Logik

Hallo,

ich habe, so wie der Satz hier präsentiert wird, schwerwiegende Einwände.

Erstens zeigt Gödels Satz nicht, dass die Mathematik widersprüchlich oder unvollständig ist. Die Begriffe Widersprüchlichkeit und Vollständigkeit beziehen sich auf die Ableitbarkeit in Formalen Systemem.

Gödels Satz zeigt aber eine Lücke (welche in der Logik nicht unter Unvollständigkeit fällt).

Also: Nehmen wir an, wir wollten Hilberts Programm durchziehen mithilfe eines logischen Systems, das a) Quantorenlogik b) Abstraktionsregeln

enthält aber nicht

c) eine typentheoretische Abstufung

wie der UP vor mir bereits angemerkt hat, ist Russells Principia Mathematica eine Typentheorie und wird von Gödels Satz nicht tangiert.

Wir reden nun über ein System wie die Zermelo Fraenkel Mengenlehre (die nicht Russells Mengenlehre ist). Nun versuche ich, mithilfe der Kalkülregeln zu zeigen, dass ich jeden wahren Satz ableiten kann. Da ich keine Typentheorie kenne, kann ich meine eigene Theorie nun mithilfe der Schlussregeln wie ein Objekt dieser Theorie behandeln (Selbstreferenz) und ich kann auch Sätze wie "Kann abgeleitet werden" als Prädikate gebrauchen. Wenn ich das mache, dann kann ich im nächsten Schritt Gödels Satz ableiten - sonst eben nicht.

Der Gödelsatz zeigt also, dass wenn ich ein solches typenfreies System mit seinen eigenen Vorschriften bearbeite, ich entweder Sätze nicht ableiten kann oder Widersprüche vorkommen (denn der Gödelsatz formuliert einen syntaktisch wohlgebildeten Selbstwiderspruch auf der semantischen Ebene, denn da kommt raus: Entweder er ist wahr (dann ist Gamma nicht ableitbar) oder er ist falsch (dann ist Gamma ableitbar, aber das bedeutet: Gamma ist wahr).

Dass die Formulierung am Ende Entweder A oder B ist entspricht also in dem Formalismus der Behauptung Entweder ein Satz ist wahr oder seine Verneinung falsch (tertium non datur, siehe Zermelo-Fraenkel ...).

Ich überarbeite das mal am Wochenende und bis dain ist ja noch Zeit, hierauf zu antworten.

Ich verweise hierfür übrigens auf Essler / Brendel Grundzüge der Logik II, Seite 291 - 295 (ich schau morgen nochmal die Ausgabe nach)

Viele Grüße

Clydefrog

ps: Ich füge hinzu:

"By the theory of simple types I mean the doctrine which says that the objects of thought (or, in another interpretation, the symbolic expressions) are divided into types, namely: individuals, properties of individuals, relations between individuals, properties of such relations, etc. (with a similar hierarchy for extensions), and that sentences of the form: " a has the property φ ", " b bears the relation R to c ", etc. are meaningless, if a, b, c, R, φ are not of types fitting together. Mixed types (such as classes containing individuals and classes as elements) and therefore also transfinite types (such as the class of all classes of finite types) are excluded. That the theory of simple types suffices for avoiding also the epistemological paradoxes is shown by a closer analysis of these. (Cf. Ramsey 1926 and Tarski 1935, p. 399).".[25]

He concluded the (1) theory of simple types and (2) axiomatic set theory, "permit the derivation of modern mathematics and at the same time avoid all known paradoxes" (Gödel 1944:126) http://en.wikipedia.org/wiki/Type_theory#Russell.27s_doubts

[25]Gödel 1944:126 footnote 17: "Russell's mathematical logic" appearing in Kurt Gödel: Collected Works: Volume II Publications 1938-1974, Oxford University Press, New York NY, ISBN-13 978-0-19-514721-6(v.2.pbk).

Es wäre nun natürlich noch zu ermitteln, wie Gödel nun das Verhältnis seines Satzes zur PM genau sieht, ich recherchiere das.

-- ClydefrogL 01:24, 10. Feb. 2012 (CET)

Hallo ClydefrogL, du hast vermutlich nicht bemerkt, dass du beim Anfügen deines PS die Antwort von Mini-floh gelöscht hast. Ich füge sie wieder ein. Sie bezieht sich auf deinen ursprünglichen Beitrag (vor dem ps.):

Bloß zur Gaudi und um Dir Arbeit zu ersparen: Der originale Titel der Arbeit von Gödel heißt

"Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I." (in: Monatshefte für Mathematik und Physik. Akademische Verlagsgesellschaft, Leipzig 38.1931, S. 173–198.)

Da die Principia Mathematica gerade Russels Typentheorie enthalten dürfte der größte Teil Deiner Ausführungen gegenstandslos sein. Im übrigen glaube ich, dass Du den Begriff "Vollständigkeit", wie er in der mathematischen Logik verwendet wird, nicht ganz verstanden hast.

--Mini-floh 09:23, 9. Feb. 2012 (CET)

--Digamma 15:40, 10. Feb. 2012 (CET)

Hallo Digamma, ich habe ihn aufgrund der unsachlichen Behauptungen entfernt:

1. Aus dem Titel einer Arbeit lässt sich nicht auf die Gültigkeit eines Satzes innerhalb der Arbeit für ein Element des Titels schließen.

2. Die Behauptung, ich hätte Vollständigkeit nicht verstanden, ist einfach unsachlich. Ich weise das von mir, vor allem, da keinerlei Begründung folgt. Wieso du das verteidigst, bleibt mir schleierhaft. Es ist einfach kein guter Stil, einfach zu behaupten, der Meinungsgegner verstünde etwas nicht, ohne auszuführen, wie es denn richtig wäre. 3. Dass die PM Russells Typentheorie enthalten, ist mir wohl bekannt. 4. Meine verschobene Angabe der Ausgabe bezog sich nicht auf Gödels Paper, sondern auf Esslers Buch. Man braucht mir also nicht "zur Gaudi" Arbeit zu ersparen. Ich habe mir Gödels Paper nochmal vorgelegt und schreibe dazu mehr, sobald ich wieder durch sein werde. Bis dahin kannst du diesen unsachlich geführten Angriff natürlich stehenlassen. Mich ficht das nicht an, jedoch sollte Mini-floh mal darüber nachdenken, zu wessen Beschädigung ein solcher Stil wirklich gereicht. -- ClydefrogL 15:56, 10. Feb. 2012 (CET)

Es tut mir leid, wenn Du meine Aussage als "unsachlich geführten Angriff" verstanden hast. Tatsächlich aber wird im Zusammenhang mit formalen Systemen -- und um die geht es hier -- der Begriff "Vollständigkeit]" so verstanden, dass für jeden Satz $\phi$ der Sprache entweder $\phi$ oder $\neg \phi$ ableitbar ist. Wenn Du sagst: "Gödels Satz zeigt aber eine Lücke (welche in der Logik nicht unter Unvollständigkeit fällt)", dann verlässt Du den in der mathematischen Logik in diesem Zusammenhang üblichen Sprachgebrauch. --Mini-floh 17:49, 10. Feb. 2012 (CET)

Was ich meinte ist dies, lassen wir den anderen Disput bei Seite, Schwamm drüber. Vielleicht wird es das Beste sein, wenn ich dir zuerst darlege, wie ich den Satz sehe, ich stütze mich hierbei auch auf Gödels Paper, wobei ich eben dies gerade nochmal durchgehe und noch nicht am Ende angelangt bin, und auf diverse .pdf (google mal Gödelscher Unvollständigkeitssatz Beweis, da müsste ein Koblaschewsky oder so ähnlich bei sei ein Dresdner Paper, du siehst das dann) und auf den Essler. Ich gebe nun wieder, wie ich diese Autoren verstehe und sage im Anschluss, wieso dies dem Artikel widerspricht:

Ein formales System ist unvollständig, wenn einer semantisch abgeleiteten Wahrheit nicht eine syntaktische Ableitung entspricht. Inkorrekt, wenn einer syntakischen Ableitung nicht eine wahre Aussage entspricht. Die Frage sehe ich nun darin: Kann ich beweisen, dass jede wahre Aussage innerhalb der Arithmetik mithilfe eines finiten Kalküls (in Form eines n-stufigen Algorithmus) auch abgeleitet werden kann. Respektive und weiter gefasst:

Kann ich von jeder semantisch wahren oder falschen Aussagen eine syntaktische Ableitung aus endlich vielen Axiomen finden, die mir sagt, dass $\not {\vdash }_{S}p$. In S. Wobei die "syntaktische Ableitung" , die ich dafür verwende, durch mein Axiomensystem eingerahmt wird.

Kann ich also diese Ableitung durch Wahl eines geeigneten Algorithmus stets finden?

Gödels Unvollständigkeitssatz zeigt, dass eine solche Demonstration unmöglich ist. Das Ergebnis einer solchen Demonstration wird laut Gödel mit finiten Methoden stets der Gödelsche UVS sein.

Ich würde demnach analytisch dazwischen unterscheiden, was passiert, wenn man den Ansatz macht, die Ableitung der Vollständigkeit in dem Formalen System zu finden, dann entsteht dieser Satz. Und was passiert, wenn man das formale System betrachtet, ohne dieses in sich selber zu analysieren. Dieses so erweitert gedachte Formale System ist Opfer des Gödelsatzes, aber nicht das ursprüngliche System. Oder wie es auch auf der englischen Wikiseite formuliert ist: (siehe century problems)

Prove that the axioms of arithmetic are consistent. There is no consensus on whether results of Gödel and Gentzen give a solution to the problem as stated by Hilbert. Gödel's second incompleteness theorem, proved in 1931, shows that no proof of its consistency can be carried out within arithmetic itself. Gentzen's consistency proof (1936) shows that the consistency of arithmetic follows from the well-foundedness of the ordinal ε0.

Es wird jedoch in dem Artikel stets darauf abgehoben, dass die Mathematik(!) unvollständig oder widersprüchlich ist. Dies erscheint mir zu weit zu gehen, da dies nur einen Versuch, die Vollständigkeit und Widerspruchsfreiheit der Arithmetik mithilfe einer fiten Arithmetik selber zu zeigen, betrifft. Oder wie siehst du das ? -- ClydefrogL 23:49, 10. Feb. 2012 (CET)

Ein Antwortversuch von mir:

Es gibt in der Logik zwei verschiedene Vollständigkeitsbegriffe (siehe Vollständigkeit (Logik)).

• Der erste (dort Punkt 2: Vollständigkeit von Sequenzenkalkülen) bezieht sich auf die Ableitbarkeit in formalen (Beweis-)Systemen, also (z.B.) in einem Kalkül. Ein solches System heißt vollständig, wenn jeder Satz, der in allen möglichen Modellen einer Satzmenge gilt (d.h. der im semantischen Sinn aus der Satzmenge folt) auch aus der Satzmenge formal ableitbar ist. Äquivalent dazu ist die folgende Formulierung: Jede Satzmenge, aus der sich formal kein Widerspruch ableiten lässt (also widerspruchsfrei ist), besitzt ein Modell (ist also erfüllbar). Die Logik erster Stufe mit den üblichen Ableitungsregeln ist in diesem Sinn vollständig. Dies ist die Aussage des Gödelschen Vollständigkeitssatzes.
• Der zweite bezieht sich auf Axiomensysteme. Ein Axiomensystem ist vollständig, wenn jeder Satz, der in der formalen Sprache formuliert werden kann, in dem Axiomensystem bewiesen oder widerlegt werden kann. Ein Axiomensystem der Arithmetik ist demnach vollständig, wenn jeder in der Sprache der Arithmetik (Sprache erster Stufe mit den Funktionssymbolden + und * und den Konstantensymbolen 0 und 1) formulierbare Satz in diesem Axiomensystem bewiesen oder widerlegt werden kann. So ein Axiomensystem gibt es trivialerweise: Man nimmt einfach alle in der Arithmetik (d. h in $\mathbb {N}$) wahren Sätze. Dieses triviale Axiomensystem ist jedoch nicht hilfreich, es verlagert das Problem, einen zahlentheoretischen Satz zu beweisen, nur dahin, zu entscheiden, ob er Element dieses (riesigen) Axiomensystems ist.

Gesucht ist also ein Axiomensystem, das erstens vollständig ist, und zweitens rekursiv, d.h. entscheidbar. Ein rekursives Axiomensystem ist z.B. das Axiomensystem der Peano-Arithmetik der ersten Stufe. Aber dieses ist nicht vollständig (in diesem zweiten Sinn).

Dies ist die Aussage des ersten Gödelschen Unvollständigkeitssatzes: Kein Axiomensystem der Arithmetik ist sowohl rekursiv also auch vollständig.

Aus dem ersten Gödelschen Unvollständigkeitssatz folgt sogar noch mehr: Jedes rekursive Axiomensystem, in das sich die Arithmetik einbetten lässt, ist unvollständig. Dies gilt insbesondere für jedes Axiomensystem der Mengenlehre (in dem sich die Existenz einer unendlichen Menge beweisen lässt), also insbesondere für ZFC.

Und ich denke, dass das genauso für jede Typenmengenlehre gilt. --Digamma 11:58, 11. Feb. 2012 (CET)

Hallo Digamma,

diesen Unterschied habe ich ja in meinem Post, glaube ich, impliziert. Nämlich folgendes: Deine Vollständigkeit(1) wird ja durch den Gödelsatz nicht beeinträchtigt. Bei dem zweiten Fall hakt es allerdings für mich. Ich stimme dir in deiner Charakterisierung der Vollständigkeit zu. Wobei nun natürlich eine Rolle spielt, wie beispielsweise der Satz gelesen wird: "Ein Axiomensystem ist vollständig, wenn jeder Satz, der in der formalen Sprache formuliert werden kann, in dem Axiomensystem bewiesen oder widerlegt werden kann." Genau darum geht es. Nehmen wir uns einen Satz Kalkülregeln (1) - (N) eine Objektmenge ($\mathbb {N}$), deren Untermenge eine Axiomenmenge sei, und einen Zeichensatz ($+,\cdot ,\rightarrow ,\wedge ,\forall$) etc. und einen Satz verschiedenstelliger Prädikate $p\in P$.

Unsere Regeln werden uns sagen dass $p^{n}(x_{1},\dots ,x_{k},a_{1},\dots ,a_{l})$ eine Aussage des Kalküles ist. Nun fragen wir uns: Gegeben ein Satz A wohlgebildet. Existiert in dieser Sprache eine Rekursionsformel, so dass wir entscheiden können, dass dieser Satz aus den Axiomen abgeleitet wurde? Wir nehmen nun den Satz S:

Die Aussage A ist in dem Kalkül bewiesen, gdw. eine Ableitung von A aus einer Axiomenmenge 

$\alpha$ durch Anwendung der Kalkülregeln gefunden werden kann. Widerlegt, gdw. eine Ableitung von nicht A aus ...

Satz T: Jede Aussage des Kalküls ist beweisbar.

Dieser Satz ist kein Bestandteil des Kalküls. Ich wüsste nicht, wo er in dem Kalkül auftauchen sollte, da dieser Satz der Metasprache angehört. Anscheinend wird nun aber für Gödels Satz folgendes angenommen: Der Satz S ist ein Axiom der Arithmetik in der selben Weise, in der die Peano Axiomatik ein Teil der Arithmetik ist. Dies ist aber allem Anschein nach unrichtig, da die Peanoaxiomatik Kalkülregeln angibt (1+1+1...) und Prädikate vergibt (Successoreigenschaft) an die Objektmenge und dadurch Aussagen generiert. Gemäß PA ist also die Aussage 1+1+1 ... wohlgeformt und die PA sind ja ein Teil der Arithmetikaxiome.

Wenden wir uns nun dem Satz S' zu: Der Satz S ist in dem Kalkül bewiesen, gdw. eine Ableitung von S aus einer Axiomenmenge .....

Man fordert also dann einen Beweis für den Satz T, indem man ihn für einen Teil der Axiomatik der Arithmetik erklärt wie die PA. Man setzt also den Satz S als Objekt in den Satz S selber ein und generiet so S'. Der Satz S ist offenbar selbst wiederum a) Bestandteil des Kalküls b) führt bei seiner eigenen Analyse innerhalb der kalkulatorischen Regeln des Kalküls auf den Gödelsatz folglich nicht-T oder widersprüchlich.

Woran ich mich aufhalte ist dies: Ich bin unschlüssig, den Satz "Ein logisches System heißt vollständig gdw. ... " als Axiom innerhalb des logischen Systemes anzutragen oder als wohlgeformte Aussage innerhalb des Systems anzuerkennen. Daher kamen wohl auch Wittgensteins Schmerzen. Ich glaube, der Wert des Gödelsatzes besteht auch im Wesentlichen darin, gezeigt zu haben, dass genau eine solche Analyse unlösbare Probleme aufwirft (für Wittgensteinianer übrigens kein Wunder) und dass die Beweisführung der Vollständigkeit und Widersprüchlichkeit selbst problematisch wird. Deshalb hatte ich auch oben kryptisch von einem erweitert vorgestellten Logischen System gesprochen, da der Satz "Eine Logik ist vollständig, gdw ... " eben kein Satz innerhalb des Kalküls ist, sondern ein Satz über den Kalkül, sich also nach Wittgenstein (und ich nehme mal an: Auch Russell) in dem Kalkül auch gar nicht aufstellen lässt (weshalb die Stufung so wichtig ist, aber es ist eben eine andere Art von Stufung als die typentheoretische im Prädikatensinn). Folglich sagt der Gödelsatz also, dass wir mit der in dem Kalkül formulierten Sprache und ihrer Beweistechniken den Satz "Der Kalkül ist vollständig" nicht analysieren können, ohne die Konstruktion des Gödelsatzes zuzulassen. Wir kommen also nicht umhin, einzuräumen, dass wir die Vollständigkeit und Widerspruchsfreiheit des Kalküls mithilfe der rekursiv in dem Kalkül definierten Beweisverfahren (n-fache Anwendung der Kalkülregeln) nicht beweisen können. Aus der Unmöglichkeit, diesen Beweis zu führen, können wir jedoch nur auf die Unvollständigkeit schließen, wenn wir diesen Beweis als notwendigen Bestandteil des Systems auffassen und damit den Satz "Der Kalkül ist vollständig .." ebenfalls. Diese Aussagen erscheinen mir jedoch keine Aussagen der Arithmetik zu sein. Es wäre also so gesehen sogar unrichtig, dass jedes hinreichend mächtige formale System entweder ws oder uvs ist. Es sei eben denn, vollständig würde bedeuten, dass das System seine eigene Vollständigkeit mithilfe seines eigenen Kalküls beweisen könnte. Gödel hat ja eben gezeigt, dass dies unrichtig ist. Der Satz hat also einen massiven Kontext, der mir in dem einfach hingeschriebenen Satz "Jedes hinreichend mächtige formale System ist entweder uvs oder ws." verloren geht. Bevor ich die Sache noch irritierender mache, warte ich mal -- ClydefrogL 02:58, 12. Feb. 2012 (CET)

Hallo. Ich glaube, Du machst Dir hier an der falschen Stelle Probleme. Vollständigkeit in dem hier verwendeten Sinn heißt doch: für jeden wohlgeformten Satz $\phi$ der Sprache ist $\phi$ oder $\neg \varphi$ in S anbleitbar (aber nicht beides, weil S sonst widersprüchlich ist). Wenn ich alle Sätze durchgehe und finde, dass ich einen Satz angeben kann, bei dem weder $\phi$ noch $\neg \varphi$ in S ableitbar ist, habe ich gezeigt, dass S unvollständig ist. Das kann ich dann von außen über das S sagen und darum geht es schließlich, denn ich selbst arbeite ja in der Metatheorie. Zu fordern, dass im System S selbst ein Satz der Art Das System S ist unvollständig beweisen werden soll ist m.E. eine Stufe zu viel. --Mini-floh 22:44, 12. Feb. 2012 (CET)

Oder konkret: Man finde einen Beweis (in der nomralen Peano-Arithmetik) oder widerlege: ¬∃b:∃c:∃d:〈∃e:∃f:∃g:〈a=((((((e+ f)+ g)· ((e+ f)+ g))· ((e+ f)+ g))+ ((e+ f)· (e+ f)))+ e) ∧ ∃h:∃i:〈〈∃j:h=(j· Si) ∧ 〈∃j:h=(d+ (j· S(i· Sg))) ∧ ∃j:(d+ j)=(i· Sg)〉〉 ∧ ∀j:〈∃k:S(j+ k)=g ⇒ ∀k:∀l:〈〈〈∃m:h=(k+ (m· S(i· Sj))) ∧ ∃m:(k+ m)=(i· Sj)〉 ∧ 〈∃m:e=(l+ (m· S(f· Sj))) ∧ ∃m:(l+ m)=(f· Sj)〉〉 ⇒ 〈〈¬l=SSSSSSSSSS0 ⇒ 〈〈∃m:h=S(k+ (m· S(i· SSj))) ∧ ∃m:S(k+ m)=(i· SSj)〉 ∧ 〈∃m:b=(l+ (m· S(c· Sj))) ∧ ∃m:(l+ m)=(c· Sj)〉〉〉 ∧ 〈l=SSSSSSSSSS0 ⇒ 〈〈〈∃m:h=S((a+ k)+ (m· S(i· SSj))) ∧ ∃m:S((a+ k)+ m)=(i· SSj)〉 ∧ 〈∃m:b=SSSSSSSSS(m· S(c· S(a+ k))) ∧ ∃m:SSSSSSSSSm=(c· S(a+ k))〉〉 ∧ ∀m:〈∃n:S(m+ n)=a ⇒ 〈∃n:b=SSSSSSSS(n· S(c· S(m+ k))) ∧ ∃n:SSSSSSSSn=(c· S(m+ k))〉〉〉〉〉〉〉〉〉 ∧ ∃e:∃f:∃g:∃h:∃i:〈〈〈〈〈∃j:i=(j· Sf) ∧ ∃j:i=(j· S(f· Sg))〉 ∧ ∀j:∀k:∀l:〈〈〈∃m:S(j+ m)=g ∧ 〈∃m:i=(k+ (m· S(f· Sj))) ∧ ∃m:(k+ m)=(f· Sj)〉〉 ∧ 〈∃m:i=(l+ (m· S(f· SSj))) ∧ ∃m:(l+ m)=(f· SSj)〉〉 ⇒ 〈k=l ∨ 〈∃m:e=(m· S(f· Sj)) ∧ 〈k=Sl ∨ l=Sk〉〉〉〉〉 ∧ ∀j:〈∃k:S(j+ k)=g ⇒ ∀k:∀l:∀m:∀n:〈〈〈〈〈∃o:e=(k+ (o· S(f· Sj))) ∧ ∃o:(k+ o)=(f· Sj)〉 ∧ 〈∃o:h=(l+ (o· S(f· Sj))) ∧ ∃o:(l+ o)=(f· Sj)〉〉 ∧ 〈∃o:h=(m+ (o· S(f· SSj))) ∧ ∃o:(m+ o)=(f· SSj)〉〉 ∧ 〈∃o:h=(n+ (o· S(f· SS(m+ j)))) ∧ ∃o:(n+ o)=(f· SS(m+ j))〉〉 ⇒ 〈〈〈〈〈〈∃o:((j+ l)+ o)=g ∧ 〈∃o:SSSSSSSSSo=k ⇒ l=S0〉〉 ∧ 〈〈〈k=0 ∨ k=SSSSSSS0〉 ∨ k=SSSSSSSS0〉 ⇒ l=Sm〉〉 ∧ 〈〈〈〈〈〈k=S0 ∨ k=SS0〉 ∨ k=SSS0〉 ∨ k=SSSS0〉 ∨ k=SSSSS0〉 ∨ k=SSSSSS0〉 ⇒ 〈l=S(m+ n) ∧ ∀o:〈〈∃p:〈∃q:S(p+ q)=m ∧ 〈∃q:e=(o+ (q· S(f· SS(j+ p)))) ∧ ∃q:(o+ q)=(f· SS(j+ p))〉〉 ∧ ∃p:〈∃q:S(p+ q)=n ∧ 〈∃q:e=(o+ (q· S(f· SS((m+ j)+ p)))) ∧ ∃q:(o+ q)=(f· SS((m+ j)+ p))〉〉〉 ⇒ 〈〈∀p:¬〈〈∃q:S(p+ q)=m ∧ 〈∃q:e=SSSSSS(q· S(f· SS(j+ p))) ∧ ∃q:SSSSSSq=(f· SS(j+ p))〉〉 ∧ 〈∃q:e=(o+ (q· S(f· SSS(j+ p)))) ∧ ∃q:(o+ q)=(f· SSS(j+ p))〉〉 ∨ ∀p:¬〈〈∃q:S(p+ q)=n ∧ 〈∃q:e=SSSSSS(q· S(f· SS((m+ j)+ p))) ∧ ∃q:SSSSSSq=(f· SS((m+ j)+ p))〉〉 ∧ 〈∃q:e=(o+ (q· S(f· SSS((m+ j)+ p)))) ∧ ∃q:(o+ q)=(f· SSS((m+ j)+ p))〉〉〉 ⇒ ∀p:¬〈〈∃q:S(p+ q)=(m+ n) ∧ 〈∃q:e=SSSSSS(q· S(f· SS(j+ p))) ∧ ∃q:SSSSSSq=(f· SS(j+ p))〉〉 ∧ 〈∃q:e=(o+ (q· S(f· SSS(j+ p)))) ∧ ∃q:(o+ q)=(f· SSS(j+ p))〉〉〉〉〉〉〉 ∧ ∀o:〈〈∃p:e=(o+ (p· S(f· SSj))) ∧ ∃p:(o+ p)=(f· SSj)〉 ⇒ 〈〈〈〈〈〈k=0 ∨ k=S0〉 ∨ k=SS0〉 ∨ k=SSSSSSS0〉 ⇒ 〈〈〈〈o=S0 ∨ o=SS0〉 ∨ o=SSS0〉 ∨ o=SSSSSS0〉 ∨ o=SSSSSSS0〉〉 ∧ 〈〈〈〈k=SSS0 ∨ k=SSSS0〉 ∨ k=SSSSS0〉 ∨ k=SSSSSSSS0〉 ⇒ 〈〈o=SSSS0 ∨ o=SSSSS0〉 ∨ ∃p:SSSSSSSSp=o〉〉〉 ∧ 〈k=SSSSSS0 ⇒ ∃p:SSSSSSSSSSp=o〉〉〉〉 ∧ ∀o:〈〈∃p:e=(o+ (p· S(f· SS(m+ j)))) ∧ ∃p:(o+ p)=(f· SS(m+ j))〉 ⇒ 〈〈〈k=0 ⇒ k=o〉 ∧ 〈〈〈k=S0 ∨ k=SS0〉 ∨ k=SSSSSS0〉 ⇒ 〈〈〈〈o=S0 ∨ o=SS0〉 ∨ o=SSS0〉 ∨ o=SSSSSS0〉 ∨ o=SSSSSSS0〉〉〉 ∧ 〈〈〈k=SSS0 ∨ k=SSSS0〉 ∨ k=SSSSS0〉 ⇒ 〈〈o=SSSS0 ∨ o=SSSSS0〉 ∨ ∃p:SSSSSSSSp=o〉〉〉〉〉 ∧ 〈j=0 ⇒ k=0〉〉〉〉〉 ∧ ∃j:〈〈〈g=S(j+ d) ∧ ∃k:e=(k· S(f· Sj))〉 ∧ ∀k:¬〈〈∃l:S(k+ l)=d ∧ 〈∃l:b=SSSSSS(l· S(c· Sk)) ∧ ∃l:SSSSSSl=(c· Sk)〉〉 ∧ ∃l:b=(l· S(c· SSk))〉〉 ∧ ∀k:∀l:〈〈∃m:S(k+ m)=d ∧ 〈∃m:b=(l+ (m· S(c· Sk))) ∧ ∃m:(l+ m)=(c· Sk)〉〉 ⇒ 〈∃m:e=(l+ (m· S(f· SS(j+ k)))) ∧ ∃m:(l+ m)=(f· SS(j+ k))〉〉〉〉 ∧ ∀j:∀k:〈〈∃l:e=(l· S(f· Sj)) ∧ 〈∃l:h=(k+ (l· S(f· SSj))) ∧ ∃l:(k+ l)=(f· SSj)〉〉 ⇒ 〈〈〈〈∃l:e=SSSSSS(l· S(f· SSj)) ∧ ∃l:SSSSSSl=(f· SSj)〉 ∧ 〈∃l:e=SSSSSSSSSS(l· S(f· SSSj)) ∧ ∃l:SSSSSSSSSSl=(f· SSSj)〉〉 ∧ 〈〈〈〈〈〈∃l:e=SSSSSSS(l· S(f· SSSSj)) ∧ ∃l:e=SSS(l· S(f· SSSSSj))〉 ∧ ∃l:e=SSSSSSSS(l· S(f· SSSSSSj))〉 ∧ ∃l:e=SSSSSSSSSS(l· S(f· SSSSSSSj))〉 ∧ ∃l:e=SSSSSSSSS(l· S(f· SSSSSSSSj))〉 ∨ 〈〈〈∃l:e=SSS(l· S(f· SSSSj)) ∧ ∃l:e=SSSSSSSSSS(l· S(f· SSSSSSj))〉 ∧ ∃l:e=SSSSSSSSS(l· S(f· SSSSSSSj))〉 ∧ 〈〈∃l:e=SSSS(l· S(f· SSSSSj)) ∧ ∃l:e=SSSSSSSSSS(l· S(f· SSSSSSSSj))〉 ∨ 〈∃l:e=SSSSS(l· S(f· SSSSSj)) ∧ ∃l:e=SSSSSSSSS(l· S(f· SSSSSSSSj))〉〉〉〉 ∨ 〈〈〈〈〈〈〈〈∃l:e=SSSSSS(l· S(f· SSSSj)) ∧ ∃l:e=SSSSSSSSSSS(l· S(f· SSSSSj))〉 ∧ ∃l:e=SSS(l· S(f· SSSSSSj))〉 ∧ ∃l:e=SSSSSSSSSS(l· S(f· SSSSSSSSj))〉 ∧ ∃l:e=SSSSSSSS(l· S(f· SSSSSSSSSj))〉 ∧ ∃l:e=SSSSSSSSSSS(l· S(f· SSSSSSSSSSj))〉 ∧ ∃l:e=SSSSSSSSSS(l· S(f· SSSSSSSSSSSSSj))〉 ∧ ∃l:e=SSSSSSSSSSS(l· S(f· SSSSSSSSSSSSSSj))〉 ∧ 〈〈〈∃l:e=SSSS(l· S(f· SSSSSSSj)) ∧ ∃l:e=SSSSSSSS(l· S(f· SSSSSSSSSSSj))〉 ∧ ∃l:e=SSSS(l· S(f· SSSSSSSSSSSSj))〉 ∨ 〈〈〈∃l:e=SSSSS(l· S(f· SSSSSSSj)) ∧ ∃l:e=SSSS(l· S(f· SSSSSSSSSSSj))〉 ∧ 〈∃l:e=SSSSS(l· S(f· SSSSSSSSSSSSj)) ∧ ∃l:SSSSSl=(f· SSSSSSSSSSSSj)〉〉 ∧ ∃l:e=SSSSSSSSSS(l· S(f· SSSSSSSSSSSSSSSj))〉〉〉〉〉 ∨ ∃l:∃m:〈〈〈〈∃n:S(l+ n)=j ∧ ∃n:e=(n· S(f· Sl))〉 ∧ 〈∃n:h=(m+ (n· S(f· SSl))) ∧ ∃n:(m+ n)=(f· SSl)〉〉 ∧ ∀n:∀o:∀p:〈〈〈〈∃q:i=(n+ (q· S(f· SSl))) ∧ ∃q:(n+ q)=(f· SSl)〉 ∧ ∃q:((l+ o)+ q)=j〉 ∧ 〈∃q:i=(p+ (q· S(f· SS(l+ o)))) ∧ ∃q:(p+ q)=(f· SS(l+ o))〉〉 ⇒ ∃q:(p+ q)=n〉〉 ∧ 〈〈〈〈〈〈〈〈〈〈〈∀n:∀o:〈〈∃p:S(n+ p)=m ∧ 〈∃p:e=(o+ (p· S(f· SS(n+ j)))) ∧ ∃p:(o+ p)=(f· SS(n+ j))〉〉 ⇒ ∃p:e=(o+ (p· S(f· SS(n+ l))))〉 ∨ 〈〈〈∃n:e=SSS(n· S(f· SSj)) ∧ ∃n:SSSn=(f· SSj)〉 ∧ k=m〉 ∧ ∃n:∃o:〈〈S(n+ o)=k ∧ ∀p:∀q:〈〈∃r:S(p+ r)=o ∧ 〈∃r:e=(q+ (r· S(f· SSS(p+ j)))) ∧ ∃r:(q+ r)=(f· SSS(p+ j))〉〉 ⇒ ∃r:e=(q+ (r· S(f· SSS(p+ (l+ n)))))〉〉 ∧ ∀p:∀q:〈〈∃r:S(p+ r)=n ∧ 〈∃r:e=(q+ (r· S(f· SSS(p+ (j+ o))))) ∧ ∃r:(q+ r)=(f· SSS(p+ (j+ o)))〉〉 ⇒ ∃r:e=(q+ (r· S(f· SSS(p+ l))))〉〉〉〉 ∨ 〈〈〈∃n:e=SSSSSSS(n· S(f· SSj)) ∧ ∃n:SSSSSSSn=(f· SSj)〉 ∧ k=SSm〉 ∧ ∀n:∀o:〈〈∃p:S(n+ p)=m ∧ 〈∃p:e=(o+ (p· S(f· SSSS(n+ j)))) ∧ ∃p:(o+ p)=(f· SSSS(n+ j))〉〉 ⇒ 〈∃p:e=(o+ (p· S(f· SS(n+ l)))) ∧ ∃p:(o+ p)=(f· SS(n+ l))〉〉〉〉 ∨ 〈〈〈∃n:e=SSSSSSS(n· S(f· SSl)) ∧ ∃n:SSSSSSSn=(f· SSl)〉 ∧ m=SSk〉 ∧ ∀n:∀o:〈〈∃p:S(n+ p)=k ∧ 〈∃p:e=(o+ (p· S(f· SSSS(n+ l)))) ∧ ∃p:(o+ p)=(f· SSSS(n+ l))〉〉 ⇒ 〈∃p:e=(o+ (p· S(f· SS(n+ j)))) ∧ ∃p:(o+ p)=(f· SS(n+ j))〉〉〉〉 ∨ ∃n:∃o:〈〈〈〈〈〈∃p:h=(n+ (p· S(f· SSSl))) ∧ ∃p:(n+ p)=(f· SSSl)〉 ∧ S(n+ o)=m〉 ∧ 〈∃p:e=SSSSSSSS(p· S(f· SSSj)) ∧ ∃p:SSSSSSSSp=(f· SSSj)〉〉 ∧ 〈∃p:e=SSSSSSSS(p· S(f· SSSS(j+ n))) ∧ ∃p:SSSSSSSSp=(f· SSSS(j+ n))〉〉 ∧ ∀p:∀q:〈〈∃r:S(p+ r)=n ∧ 〈∃r:e=(q+ (r· S(f· SSSS(p+ j)))) ∧ ∃r:(q+ r)=(f· SSSS(p+ j))〉〉 ⇒ 〈∃r:e=(q+ (r· S(f· SSS(p+ l)))) ∧ ∃r:(q+ r)=(f· SSS(p+ l))〉〉〉 ∧ ∀p:∀q:〈〈∃r:S(p+ r)=o ∧ 〈∃r:e=(q+ (r· S(f· SSSSS(p+ (j+ n))))) ∧ ∃r:(q+ r)=(f· SSSSS(p+ (j+ n)))〉〉 ⇒ 〈∃r:e=(q+ (r· S(f· SSS(p+ (l+ n))))) ∧ ∃r:(q+ r)=(f· SSS(p+ (l+ n)))〉〉〉〉 ∨ ∃n:∃o:〈〈〈〈〈〈∃p:h=(n+ (p· S(f· SSSj))) ∧ ∃p:(n+ p)=(f· SSSj)〉 ∧ S(n+ o)=k〉 ∧ 〈∃p:e=SSSSSSSS(p· S(f· SSSl)) ∧ ∃p:SSSSSSSSp=(f· SSSl)〉〉 ∧ 〈∃p:e=SSSSSSSS(p· S(f· SSSS(l+ n))) ∧ ∃p:SSSSSSSSp=(f· SSSS(l+ n))〉〉 ∧ ∀p:∀q:〈〈∃r:S(p+ r)=n ∧ 〈∃r:e=(q+ (r· S(f· SSSS(p+ l)))) ∧ ∃r:(q+ r)=(f· SSSS(p+ l))〉〉 ⇒ 〈∃r:e=(q+ (r· S(f· SSS(p+ j)))) ∧ ∃r:(q+ r)=(f· SSS(p+ j))〉〉〉 ∧ ∀p:∀q:〈〈∃r:S(p+ r)=o ∧ 〈∃r:e=(q+ (r· S(f· SSSSS(p+ (l+ n))))) ∧ ∃r:(q+ r)=(f· SSSSS(p+ (l+ n)))〉〉 ⇒ 〈∃r:e=(q+ (r· S(f· SSS(p+ (j+ n))))) ∧ ∃r:(q+ r)=(f· SSS(p+ (j+ n)))〉〉〉〉 ∨ 〈〈∃n:e=SS(n· S(f· SSl)) ∧ ∃n:SSn=(f· SSl)〉 ∧ ∀n:∀o:〈〈∃p:S(n+ p)=k ∧ 〈∃p:e=(o+ (p· S(f· SS(n+ j)))) ∧ ∃p:(o+ p)=(f· SS(n+ j))〉〉 ⇒ ∃p:e=(o+ (p· S(f· SSS(n+ l))))〉〉〉 ∨ ∃n:〈〈〈∃o:h=(n+ (o· S(f· SSSl))) ∧ ∃o:(n+ o)=(f· SSSl)〉 ∧ 〈∃o:e=SS(o· S(f· SSl)) ∧ ∃o:SSo=(f· SSl)〉〉 ∧ ∀o:∀p:〈〈∃q:S(o+ q)=k ∧ 〈∃q:e=(p+ (q· S(f· SS(o+ j)))) ∧ ∃q:(p+ q)=(f· SS(o+ j))〉〉 ⇒ ∃q:e=(p+ (q· S(f· SSS(o+ (l+ n)))))〉〉〉 ∨ 〈k=SSm ∧ ∃n:∃o:〈〈〈〈S(n+ o)=m ∧ 〈∃p:e=S(p· S(f· SSj)) ∧ ∃p:Sp=(f· SSj)〉〉 ∧ 〈∃p:e=S(p· S(f· SSl)) ∧ ∃p:Sp=(f· SSl)〉〉 ∧ ∀p:∀q:〈〈∃r:S(p+ r)=o ∧ 〈∃r:e=(q+ (r· S(f· SSSSS(p+ (j+ n))))) ∧ ∃r:(q+ r)=(f· SSSSS(p+ (j+ n)))〉〉 ⇒ ∃r:e=(q+ (r· S(f· SSS(p+ l))))〉〉 ∧ ∀p:∀q:〈〈∃r:S(p+ r)=n ∧ 〈∃r:e=(q+ (r· S(f· SSSS(p+ j)))) ∧ ∃r:(q+ r)=(f· SSSS(p+ j))〉〉 ⇒ ∃r:e=(q+ (r· S(f· SSS(p+ (l+ o)))))〉〉〉〉 ∨ ∃n:∃o:∃p:∃q:〈〈〈m=SSq ∧ 〈∃r:e=SSSSSS(r· S(f· SSl)) ∧ ∃r:SSSSSSr=(f· SSl)〉〉 ∧ 〈∃r:e=(n+ (r· S(f· SSSl))) ∧ ∃r:(n+ r)=(f· SSSl)〉〉 ∧ 〈∀r:〈∃s:〈∃t:S(s+ t)=p ∧ 〈∃t:e=(r+ (t· S(f· S(o+ s)))) ∧ ∃t:(r+ t)=(f· S(o+ s))〉〉 ⇒ ∀s:¬〈〈∃t:S(s+ t)=q ∧ 〈∃t:e=SSSSSS(t· S(f· SSSS(l+ s))) ∧ ∃t:SSSSSSt=(f· SSSS(l+ s))〉〉 ∧ 〈∃t:e=(r+ (t· S(f· SSSSS(l+ s)))) ∧ ∃t:(r+ t)=(f· SSSSS(l+ s))〉〉〉 ∧ ∃r:∃s:〈〈∃t:r=(t· Ss) ∧ 〈∃t:r=(k+ (t· S(s· Sq))) ∧ ∃t:(k+ t)=(s· Sq)〉〉 ∧ ∀t:∀u:∀v:∀w:〈〈〈〈∃x:S(t+ x)=q ∧ 〈∃x:r=(u+ (x· S(s· St))) ∧ ∃x:(u+ x)=(s· St)〉〉 ∧ 〈∃x:r=(v+ (x· S(s· SSt))) ∧ ∃x:(v+ x)=(s· SSt)〉〉 ∧ 〈∃x:e=(w+ (x· S(f· SSSS(l+ t)))) ∧ ∃x:(w+ x)=(f· SSSS(l+ t))〉〉 ⇒ 〈〈¬w=n ⇒ 〈〈∃x:e=(w+ (x· S(f· SS(j+ u)))) ∧ ∃x:(w+ x)=(f· SS(j+ u))〉 ∧ v=Su〉〉 ∧ 〈w=n ⇒ 〈∀x:∀y:〈〈∃z:S(x+ z)=p ∧ 〈∃z:e=(y+ (z· S(f· S(o+ x)))) ∧ ∃z:(y+ z)=(f· S(o+ x))〉〉 ⇒ 〈∃z:e=(y+ (z· S(f· SS((x+ u)+ j)))) ∧ ∃z:(y+ z)=(f· SS((x+ u)+ j))〉〉 ∧ v=(p+ u)〉〉〉〉〉〉〉〉 ∨ ∃n:〈∀o:〈〈〈∃p:S(o+ p)=j ∧ ∃p:e=(p· S(f· So))〉 ∧ ∀p:∀q:∀r:〈〈〈〈∃s:i=(q+ (s· S(f· So))) ∧ ∃s:(q+ s)=(f· So)〉 ∧ 〈∃s:i=(r+ (s· S(f· SS(p+ o)))) ∧ ∃s:(r+ s)=(f· SS(p+ o))〉〉 ∧ ∃s:S((o+ p)+ s)=j〉 ⇒ ∃s:S(q+ s)=r〉〉 ⇒ ∀p:¬〈〈〈∃q:h=(p+ (q· S(f· So))) ∧ ∃q:(p+ q)=(f· So)〉 ∧ ∃q:〈∃r:S(q+ r)=p ∧ 〈∃r:e=(n+ (r· S(f· S(o+ q)))) ∧ ∃r:(n+ r)=(f· S(o+ q))〉〉〉 ∧ ∀q:¬〈〈∃r:S(q+ r)=p ∧ 〈∃r:e=SSSSSS(r· S(f· S(o+ q))) ∧ ∃r:SSSSSSr=(f· S(o+ q))〉〉 ∧ 〈∃r:e=(n+ (r· S(f· SS(o+ q)))) ∧ ∃r:(n+ r)=(f· SS(o+ q))〉〉〉〉 ∧ 〈〈〈∃o:e=SSSSSS(o· S(f· SSj)) ∧ ∃o:SSSSSSo=(f· SSj)〉 ∧ 〈∃o:e=(n+ (o· S(f· SSSj))) ∧ ∃o:(n+ o)=(f· SSSj)〉〉 ∧ ∀o:∀p:〈〈∃q:S(o+ q)=m ∧ 〈∃q:e=(p+ (q· S(f· SSSS(o+ j)))) ∧ ∃q:(p+ q)=(f· SSSS(o+ j))〉〉 ⇒ 〈∃q:e=(p+ (q· S(f· SS(o+ l)))) ∧ ∃q:(p+ q)=(f· SS(o+ l))〉〉〉〉〉 ∨ ∃n:∃o:〈〈〈〈∃p:S(n+ p)=j ∧ ∃p:e=(p· S(f· Sn))〉 ∧ 〈∃p:h=(o+ (p· S(f· SSn))) ∧ ∃p:(o+ p)=(f· SSn)〉〉 ∧ ∀p:∀q:∀r:〈〈〈〈∃s:i=(p+ (s· S(f· SSn))) ∧ ∃s:(p+ s)=(f· SSn)〉 ∧ ∃s:((n+ q)+ s)=j〉 ∧ 〈∃s:i=(r+ (s· S(f· SS(n+ q)))) ∧ ∃s:(r+ s)=(f· SS(n+ q))〉〉 ⇒ ∃s:(r+ s)=p〉〉 ∧ 〈〈〈〈〈〈〈∃p:e=SS(p· S(f· SSj)) ∧ ∃p:SSp=(f· SSj)〉 ∧ ∀p:∀q:〈〈∃r:S(p+ r)=m ∧ 〈∃r:e=(q+ (r· S(f· SSS(p+ j)))) ∧ ∃r:(q+ r)=(f· SSS(p+ j))〉〉 ⇒ ∃r:e=(q+ (r· S(f· SS(p+ l))))〉〉 ∧ ∀p:∀q:〈〈∃r:S(p+ r)=o ∧ 〈∃r:e=(q+ (r· S(f· SSS(p+ (j+ m))))) ∧ ∃r:(q+ r)=(f· SSS(p+ (j+ m)))〉〉 ⇒ ∃r:e=(q+ (r· S(f· SS(p+ n))))〉〉 ∨ 〈〈〈∃p:e=S(p· S(f· SSl)) ∧ ∃p:Sp=(f· SSl)〉 ∧ ∀p:∀q:〈〈∃r:S(p+ r)=o ∧ 〈∃r:e=(q+ (r· S(f· SSS(p+ l)))) ∧ ∃r:(q+ r)=(f· SSS(p+ l))〉〉 ⇒ 〈∃r:e=(q+ (r· S(f· SS(p+ n)))) ∧ ∃r:(q+ r)=(f· SS(p+ n))〉〉〉 ∧ ∀p:∀q:〈〈∃r:S(p+ r)=k ∧ 〈∃r:e=(q+ (r· S(f· SS(p+ j)))) ∧ ∃r:(q+ r)=(f· SS(p+ j))〉〉 ⇒ 〈∃r:e=(q+ (r· S(f· SSS(p+ (l+ o))))) ∧ ∃r:(q+ r)=(f· SSS(p+ (l+ o)))〉〉〉〉 ∨ 〈〈∃p:e=SSS(p· S(f· SSj)) ∧ ∃p:SSSp=(f· SSj)〉 ∧ ∃p:∃q:∃r:〈〈〈〈〈S(p+ q)=k ∧ S(p+ r)=m〉 ∧ S(r+ q)=o〉 ∧ ∀s:∀t:〈〈∃u:S(s+ u)=p ∧ 〈∃u:e=(t+ (u· S(f· SSS(s+ j)))) ∧ ∃u:(t+ u)=(f· SSS(s+ j))〉〉 ⇒ ∃u:e=(t+ (u· S(f· SSS(s+ l))))〉〉 ∧ ∀s:∀t:〈〈∃u:S(s+ u)=r ∧ 〈∃u:e=(t+ (u· S(f· SSS(s+ n)))) ∧ ∃u:(t+ u)=(f· SSS(s+ n))〉〉 ⇒ 〈∃u:e=(t+ (u· S(f· SSS(s+ (l+ p))))) ∧ ∃u:(t+ u)=(f· SSS(s+ (l+ p)))〉〉〉 ∧ ∀s:∀t:〈〈∃u:S(s+ u)=q ∧ 〈∃u:e=(t+ (u· S(f· SSS(s+ (j+ p))))) ∧ ∃u:(t+ u)=(f· SSS(s+ (j+ p)))〉〉 ⇒ ∃u:e=(t+ (u· S(f· SSS(s+ (n+ r)))))〉〉〉〉 ∨ ∃p:〈〈〈〈〈〈〈〈∃q:e=SSSSSS(q· S(f· SSj)) ∧ ∃q:SSSSSSq=(f· SSj)〉 ∧ 〈∃q:e=(p+ (q· S(f· SSSj))) ∧ ∃q:(p+ q)=(f· SSSj)〉〉 ∧ 〈∃q:e=SSSSSS(q· S(f· SSn)) ∧ ∃q:SSSSSSq=(f· SSn)〉〉 ∧ 〈∃q:e=(p+ (q· S(f· SSSn))) ∧ ∃q:(p+ q)=(f· SSSn)〉〉 ∧ 〈∃q:e=S(q· S(f· SSSSn)) ∧ ∃q:Sq=(f· SSSSn)〉〉 ∧ ∀q:∀r:〈〈∃s:S(q+ s)=m ∧ 〈∃s:e=(r+ (s· S(f· SSSS(q+ j)))) ∧ ∃s:(r+ s)=(f· SSSS(q+ j))〉〉 ⇒ 〈∃s:e=(r+ (s· S(f· SSSSS(q+ n)))) ∧ ∃s:(r+ s)=(f· SSSSS(q+ n))〉〉〉 ∧ ∀q:∀r:∀s:〈〈〈∃t:S(q+ t)=m ∧ 〈∃t:e=(r+ (t· S(f· SS(l+ q)))) ∧ ∃t:(r+ t)=(f· SS(l+ q))〉〉 ∧ 〈∃t:e=(s+ (t· S(f· SSSS(j+ q)))) ∧ ∃t:(s+ t)=(f· SSSS(j+ q))〉〉 ⇒ 〈〈s=p ⇒ r=SSSSSSSSS0〉 ∧ 〈¬s=p ⇒ r=s〉〉〉〉 ∧ ∃q:∃r:〈〈∃s:q=SSSS((m+ l)+ (s· S(r· SSSSj))) ∧ ∃s:SSSS((m+ l)+ s)=(r· SSSSj)〉 ∧ ∀s:∀t:∀u:∀v:∀w:〈〈〈〈〈∃x:S(s+ x)=m ∧ 〈∃x:q=(t+ (x· S(r· SSSS(j+ s)))) ∧ ∃x:(t+ x)=(r· SSSS(j+ s))〉〉 ∧ 〈∃x:q=(u+ (x· S(r· SSSSS(j+ s)))) ∧ ∃x:(u+ x)=(r· SSSSS(j+ s))〉〉 ∧ 〈∃x:e=(v+ (x· S(f· SSSS(j+ s)))) ∧ ∃x:(v+ x)=(f· SSSS(j+ s))〉〉 ∧ 〈∃x:e=(w+ (x· S(f· St))) ∧ ∃x:(w+ x)=(f· St)〉〉 ⇒ 〈〈v=p ⇒ 〈〈u=SSt ∧ 〈∃x:e=(p+ (x· S(f· SSt))) ∧ ∃x:(p+ x)=(f· SSt)〉〉 ∧ w=SSSSSSSS0〉〉 ∧ 〈¬v=p ⇒ 〈u=St ∧ w=v〉〉〉〉〉〉〉 ∨ 〈∃p:〈〈〈S(n+ o)=j ∧ 〈∃q:i=(p+ (q· S(f· Sl))) ∧ ∃q:(p+ q)=(f· Sl)〉〉 ∧ 〈∃q:i=(p+ (q· S(f· SSj))) ∧ ∃q:(p+ q)=(f· SSj)〉〉 ∧ ∀q:∀r:〈〈∃s:S((l+ q)+ s)=j ∧ 〈∃s:i=(r+ (s· S(f· SS(l+ q)))) ∧ ∃s:(r+ s)=(f· SS(l+ q))〉〉 ⇒ ∃s:S(p+ s)=r〉〉 ∧ 〈〈〈∃p:e=S(p· S(f· SSj)) ∧ ∃p:Sp=(f· SSj)〉 ∧ ∀p:∀q:〈〈∃r:S(p+ r)=m ∧ 〈∃r:e=(q+ (r· S(f· SSS(p+ j)))) ∧ ∃r:(q+ r)=(f· SSS(p+ j))〉〉 ⇒ 〈∃r:e=(q+ (r· S(f· SS(p+ l)))) ∧ ∃r:(q+ r)=(f· SS(p+ l))〉〉〉 ∧ ∀p:∀q:〈〈∃r:S(p+ r)=o ∧ 〈∃r:e=(q+ (r· S(f· SS(p+ n)))) ∧ ∃r:(q+ r)=(f· SS(p+ n))〉〉 ⇒ 〈∃r:e=(q+ (r· S(f· SSS(p+ (j+ m))))) ∧ ∃r:(q+ r)=(f· SSS(p+ (j+ m)))〉〉〉〉〉〉〉〉〉〉〉〉 --Hagman 17:55, 14. Feb. 2012 (CET)

Sehr nett! (Was ist eigentlich die Gödelnummer davon?) Aber kannst Du das wirklich lesen? Oder anders ausgedrückt (Slang der Peanuts): "Hints! We need more hints!" --Mini-floh 19:00, 14. Feb. 2012 (CET)

@ClydefrogL: Du sagst Aus der Unmöglichkeit, diesen Beweis zu führen, können wir jedoch nur auf die Unvollständigkeit schließen, wenn wir diesen Beweis als notwendigen Bestandteil des Systems auffassen und damit den Satz "Der Kalkül ist vollständig .." ebenfalls. Diese Aussagen erscheinen mir jedoch keine Aussagen der Arithmetik zu sein. Wenn ich dich richtig verstehe, äußerst Du Bedenken, die in der Literatur auch schon geäußert wurden. Es gibt zwar eine arithmetische Aussage die in einem intuitiven Sinne die Vollständigkeit ausdrückt [etwa so: $\forall x(aussage(x)\rightarrow \exists d(beweis(d,x)\vee beweis(d,negation(x)))$ wobei die deutschen Namen für die Arithmetisierungen von primitiv rekursiven Relationen/Funktionen stehen], aber es ist zunächst nicht klar, dass dieser Satz wirklich die intendierte Bedeutung hat, da es auch Nichtstandard-Modelle der Arithmetik gibt, in denen er "fälschlicherweise" wahr ist. Vielleicht beruhigt Dich aber folgende Tatsache: Es gibt einee arithmetische Formel A = "x ist Gödelnummer einer vollständigen rekursiv aufzählbaren Theorie", sodass A genau dann in $\mathbb {N}$ gilt, wenn mann für x die Nummer einer (rekursiv aufzählbaren) vollständigen Axiomenmenge einsetzt. Setzt man eine Gödelnummer für die Arithmetik ein, wird die Aussage falsch, nimmt man eine schwache, vollständige Axiomatisierung, wird die Formel wahr. In dem Sinne kann die Arithmetik schon verlässlich über die eigene Vollständigkeit reden. Grüße--Schreiber ✉ 20:15, 19. Feb. 2012 (CET)

Verschiebung eines Artikelteils von "Axiomensystem" hierher

Im Artikel Axiomensystem ist ein längerer Teil, der dort in dieser Ausführlichkeit nicht wirklich passt:

===Axiomatisches System und Gödelscher Unvollständigkeitssatz [Bearbeiten]===

Die Gödelschen Unvollständigkeitssätze von 1931 sprechen über höchstens rekursiv aufzählbar axiomatisierte Theorien, die in der Logik erster Stufe formuliert sind. Es wird ein vollständiger und korrekter Beweiskalkül vorausgesetzt. Der erste Satz sagt aus: Falls die Axiome der Arithmetik widerspruchsfrei sind, dann ist die Arithmetik unvollständig. Es gibt also mindestens einen Satz ΦG, so dass weder ΦG noch seine Negation ¬ΦG in der Arithmetik beweisbar sind. Des Weiteren lässt sich zeigen, dass jede Erweiterung der Axiome, die rekursiv aufzählbar bleibt, ebenfalls unvollständig ist. Damit ist die Unvollständigkeit der Arithmetik ein systematisches Phänomen und lässt sich nicht durch eine einfache Erweiterung der Axiome beheben. Der zweite Unvollständigkeitssatz sagt aus, dass sich insbesondere die Widerspruchsfreiheit der Arithmetik nicht im axiomatischen System der Arithmetik beweisen lässt.

Die Unvollständigkeitssätze werden in der Literatur gerne fehlinterpretiert. Dies wird im Folgenden kommentiert:

Es ist möglich, die Arithmetik vollständig zu axiomatisieren. Die Theorie $T=\{\Phi \in {\mathcal {L}}_{\operatorname {PA} };\ \mathbb {N} \models \Phi \}$ ist eine vollständige, widerspruchsfreie Erweiterung der bekannten Peano-Axiome. Infolge der Unvollständigkeitssätze ist diese Theorie aber nicht rekursiv aufzählbar.

Es gibt vollständige, widerspruchsfreie, rekursiv aufzählbare Axiomensysteme, Diese können aber keine Erweiterung der Arithmetik sein; insbesondere ist es in derartigen Systemen nicht möglich, über dieses System selbst zu reden. Sie sind damit nicht so ausdrucksstark, wie die volle Arithmetik mit 0, Nachfolger, Addition und Multiplikation. Ein einfaches Beispiel für ein derartiges, schwaches System ist die Arithmetik nur mit 0 und Nachfolger.

Die Nichtbeweisbarkeit der eigenen Widerspruchsfreiheit in der Arithmetik ist keine absolute Grenze des formalen Denkens. So hat etwa Gerhard Gentzen gezeigt, dass man die Widerspruchsfreiheit der Arithmetik beweisen kann (in einem formalen System), wenn man die Möglichkeiten des Systems etwas erweitert. Damit zeigen die Unvollständigkeitssätze lediglich, dass man ein stärkeres System benötigt, um die Widerspruchsfreiheit eines schwächeren Systemes zu beweisen.

Die Voraussetzung der Widerspruchsfreiheit für die Unvollständigkeitssätze ist wesentlich. Zum einen kann sie innerhalb der Arithmetik nicht bewiesen werden; zum anderen würde aus der Inkonsistenz der Axiome sofort folgen, dass jeder Satz beweisbar wäre. Damit wäre die Arithmetik vollständig und insbesondere wäre auch der Satz, der die Widerspruchsfreiheit der Arithmetik aussagt, bewiesen.

Setzt man die Mengenlehre voraus, kann man mit den Natürlichen Zahlen \mathbb N ein Modell der Arithmetik angeben. Damit ist die Widerspruchsfreiheit der Arithmetik gezeigt. Jedoch ist die Mengenlehre ihrerseits ein axiomatisches System, das ausdrucksstärker als die Arithmetik ist. Damit ist sie selbst wieder unvollständig und sie kann wiederum ihrerseits nicht ihre eigene Konsistenz beweisen.

Hier noch einige Beispiele aus der Literatur:

Nach dem 1931 von Gödel bewiesenem Gödel-Theorem (auch: Unvollständigkeitssatz) ist es für ein mathematisches formales System „unmöglich, zugleich dessen Vollständigkeit und Widerspruchsfreiheit zu beweisen“ [Schülerduden, Philosophie (2002), Satz vom (verbotenen) Widerspruch]. "Kein adäquates Axiomensystem der Theorie eines unentscheidbaren Kalküls ist absolut-vollständig."[Lorenzen, Logik, 4. Aufl. (1970), S. 136]

Die Gödelschen Unvollständigkeitssätze "beweisen die Grenzen formalistischen Denkens und die Grenzen unseres Erkenntnisvermögens" [Zoglauer, Einführung (1999), S. 115] und zeigen eine „absolute Grenze“ der formalen Logik".[Hoyningen-Huene, Logik (1998), S. 272]

„Die angesprochene Unvollständigkeit der Arithmetik beispielsweise bedeutet folgendes: Für jede nur denkbare Formalisierung der elementaren Arithmetik gilt, dass es in ihr Sätze gibt, die in dieser Formulierung weder beweisbar noch widerlegbar sind. Mit anderen Worten: Es gibt in jeder dieser Formalisierungen Sätze A mit der Eigenschaft, dass sich weder A noch ¬ A beweisen lässt."[Hoyningen-Huene, Logik (1998), S. 272]

Ich hatte dort in Diskussion:Axiomensystem vorgeschlagen, diesen ganz zu löschen (und durch eine kurze Zusammenfassung samt Link hierher zu ersetzen). Ich frage hier als Alternative: Soll man den Abschnitt ab "Die Unvollständigkeitssätze werden in der Literatur gerne fehlinterpretiert" hierher, also nach "Gödelscher Unvollständigkeitssatz" verschieben? Man könnte einen eigenen Unterabschnitt daraus machen und nach und nach alle Hinweise, die im Text ja hier vorhanden sind, in diesen Abschnitt einbauen. --Mini-floh 22:16, 10. Feb. 2012 (CET)

Entweder hat sich der Artikel verändert oder meine Rezeption. Die Behauptung der Widersprüchlichkeit oder Unvollständigkeit der Mathematik sehe ich nicht mehr. So finde ich den Artikel in Ordnung, wundere mich aber gerade, was ich ursprünglich gelesen hatte Oo.

-- ClydefrogL 03:08, 11. Feb. 2012 (CET)

(Dies ist zugleich eine Antwort auf die Frage, die Du unter "Typenfreie Logik" gestellt hast) Das ist einer der Gründe, warum ich inzwischen an "Verschieben" dieses ganzen Abschnittes denke und hier einen eigenen Abschnitt "Mögliche Fehlinterpretationen" bilden möchte. Ich gebe zu, dass mir beim ersten schnellen Lesen ähnliche Gedanken kamen wie Dir. Ich habe aber zum Glück gleich ein zweites Mal gelesen und dabei bemerkt, dass ich hier falsch assoziiert hatte. Daher finde ich jetzt, dass eine solche Zusammenfassung der möglichen Fehlinterpretationen vielleicht beim Lesen hilft.

Ich möchte dabei klarstellen, dass ich durchaus nicht der Meinung bin, dass der verschobene Abschnitt unverändert bleiben sollte. Die vielen hier schon vorhandenen Hinweise auf Fehlinterpretationen sollte auf jeden Fall damit "koordiniert" werden. Auch finde ich aus dem Zusammenhang gerissene Zitate immer problematisch.

Zum Artikel hier: für mich wäre er einfacher zu lesen, wenn man "systaktische Folgerung" immer durch "Ableitung" ersetzt. Diese Terminologie wird ja in einem Teil des Artikels schon verwendet.--Mini-floh 10:05, 11. Feb. 2012 (CET)

Gödelsche Unvollständigkeitssätze

Hat jemand was dagegen, wenn ich den Artikel nach Gödelsche Unvollständigkeitssätze verschiebe? Es gibt ja zwei, und die englische WP hat als Lemma auch Gödel's incompleteness theorems. Grüße--Schreiber ✉ 19:49, 19. Feb. 2012 (CET)

Prinzipiell ist das natürlich richtig, aber für die Nichtfachleute, und für die ist das hier ja gedacht, ist immer nur "der" Unvollständigkeitssatz bekannt. Insofern müsste man abwägen: Korrektheit des Titels gegen leichte Auffindbarkeit. Das lässt sich vielleicht mit entsprechender Weiterleitungsseite auffangen. Aber wäre es nicht besser, unter dem jetzigen Titel anzufangen "Die beiden Gödelschen Unvollständigkeitssätze..." Oder: "Eigentlich hat Gödel 2 USätze formuliert ..."

Ich bin also nicht gegen eine Umbenennung, ich denke nur (aus eigener Erfahrung in anderen Bereichen, wo ich z.T. mit Volltextsuche arbeiten muss, um den von Fachleuten als "korrekt" empfundenen Titel zu finden), dass man das berücksichtigen sollte.--Mini-floh 08:21, 20. Feb. 2012 (CET)

Auf jeden Fall sollte aus dem Text des Artikels klar hervorgehen, dass es zwei Gödelsche Unvollständigkeitssätze gibt. Das ist bislang nicht der Fall. Das Lemma kann dann auch im Singular stehen. --Digamma 10:35, 20. Feb. 2012 (CET)

Okay, hab mal einen Hinweis eingebaut und lass die Verschiebung sein. Grüße--Schreiber ✉ 14:14, 20. Feb. 2012 (CET)

Neuer Hauptartikel: "Beweise des Gödelschen Unvollständigkeitssatzes"?

Hallo! Es ist sehr verdienstvoll, wenn die wesentlichen Teile des Beweises hier dargestellt werden. Trotzdem habe ich den Eindruck, dass das hier etwas "exzessiv" ist. (Vergleicht mal den Umfang, den die Teile mit "Beweis" einnehmen mit dem Rest.

Mein Vorschlag: die Teile "Genaue Formulierung" und "Beweis" zusammen mit dem ganzen Teil "alternative Beweise" in einen eigenen Hauptartikel zu verschieben. Dann beim Abschnitt "Beweisskizze" (der ja vorhanden ist) dorthin verweisen. Ich würde mir nämlich wünschen, dass auch ein "normaler Leser" noch bis zu "Häufige Fehlschlüsse" und eventuell "Beispiele für Unvollständigkeit" kommt! Vielleicht könnte man sich dann darauf konzentrieren, den übrig gebliebenen Teil so zu gestalten, dass er korrekt und verständlich ist.

(Ich hatte eigentlich angekündigt, einen Teil aus "Axiomensystem" hierher zu verschieben, weil ich dort als zu umfangreich empfand; aber so hat das gar keinen Platz hier: IMHO liest kaum jemand, den es angehen würde, den Artikel so weit, dass er darauf trifft!)--Mini-floh 15:58, 26. Feb. 2012 (CET)

Hallo Mini-floh, stimme dir vollkommen zu, dass das etwas exzessiv geworden ist. Ich erledig das gleich mal. Grüße--Schreiber ✉ 16:51, 26. Feb. 2012 (CET)

Hab jetzt das Plurallemma genommen (Beweise der Gödelschen Unvollständigkeitssätze), weil man den Artikel sowieso nur über den Link finden wird, also die Auffindbarkeit egal sein sollte. Der Abschnitt aus "Axiomensystem" passt jetzt sicher gut in den Artikel. Grüße--Schreiber ✉ 17:25, 26. Feb. 2012 (CET)

Der Artikel sieht so viel leserfreundlicher aus. Also: Beifall!

Die Pluralform finde ich hier oK, da man ja wahrscheinlich meist über den Link dahin geführt wird.

Für die Einfügung des anderen Teils muss ich mir jetzt nur noch einen Überblick verschaffen, an welchen Stellen man sinnvollerweise den Text des Artikels ändert, damit nicht allzu viele Doubletten entstehen. Ich habe die bisherigen Doubletten erst mal stehen lassen.--Mini-floh 18:49, 26. Feb. 2012 (CET)

Freut mich! Ich denke, den anderen Teil kann man erst mal in den Abschnitt "Häufige Fehlschlüsse" kopieren, um die Doubletten kann man sich danach noch kümmern (vor allem der "Bedeutungs"-Abschnitt, den ich aus dem englsichen Artikel übernomenn habe, hat einige Überschneidungen). Grüße--Schreiber ✉ 19:05, 26. Feb. 2012 (CET)

Über „Fehlschlüsse“ und andere Doubletten

Ich habe in einer ersten Runde den aus Axiomensystem eingefügten Abschnitt und seine Umgebung so bearbeitet, dass sich innerhalb dieses Bereichs keine allzu starken Überschneidungen ergeben. Ich habe im Augenblick noch nichts unternommen, um Doubletten insgesamt zu entfernen. Die Tatsache, dass man innerhalb des Systems ... nicht die Widerspruchsfreiheit beweisen kann, wird auch im vorderen Teil des Artikels noch mehrfach erwähnt. Ich weiß nicht, wie oft „gut“ ist? Andererseits scheint mir eine „Sammlung“ der Fehlschlüsse auch sinnvoll.

@Schreiber: Ich finde einen Abschnitt zur Geschichte etc. sehr sinnvoll. Vielleicht kann man einen Teil der „Vorgeschichte“ bei Axiomensysteme sinnvoll unterbringen? Ich habe ja dort schon angemerkt, dass die Vorstellungen von Hilbert &Co dargestellt werden müssten.--Mini-floh (Diskussion) 22:24, 2. Mär. 2012 (CET)

Hm, ich bin mir auch noch nicht ganz sicher, wie wir das mit den Doubletten machen sollen. Ich werd mal Teile des "Bedeutungs"-Abschnitts in die Fehlschlüsse einbauen. Um die Geschichte und einen Abschnitt für "Axiomensystem" werd ich mich auch demnächst kümmern.--Schreiber ✉ 10:36, 3. Mär. 2012 (CET)

Geklapper in der Einleitung

„Das Buch Gödel, Escher, Bach und die Werke von John Randolph Lucas, der versuchte, eine Theorie der Menschenrechte mit der Aussage zu zeigen, werden in dem Zusammenhang, zusammen mit ihren ebenso zahlreichen Kritikern, gern exemplarisch herausgehoben.“

• der versuchte, eine Theorie der Menschenrechte mit der Aussage zu zeigen: Stimmt inhaltlich nicht; ist bestenfalls zu eng gefasste Interpretation seiner Thesen. Vgl. Lucas' Aufsatz The Godelian Arguments; der Begriff human rights kommt darin nicht vor.
• In dem Zusammenhang ist eine überflüssige Floskel. „In welchem sonst?“ schreibt Wolf Schneider in Deutsch für junge Profis
• zusammen mit ihren ebenso zahlreichen Kritikern: Ebenso zahlreich wie wer? Wie Lucas und Hofstadter? Also nur zwei Kritiker? Außerdem hat jedes philosophische Werk Kritiker; die braucht man dem Leser nicht in jedem Einzelfall unter die Nase zu reiben. „Das Geheimnis zu langweilen besteht darin, alles zu sagen“ (Voltaire).

--Mussklprozz (Diskussion) 10:36, 9. Apr. 2012 (CEST)

Stimmt!--Schreiber ✉ 11:17, 9. Apr. 2012 (CEST)

Der Bezug sowohl von Gödel, Escher, Bach wie auch Lucas zum vorliegenden Lemma ist bestenfalls skuril-esoterisch. Ich würde den Satz komplett entfernen. --Boobarkee (Diskussion) 11:37, 9. Apr. 2012 (CEST)

Weder Hofstadter noch Lucas halte ich für esoterisch oder skurril. --Mussklprozz (Diskussion) 11:52, 9. Apr. 2012 (CEST)

Das habe ich auch nicht behauptet. Ich spreche von dem nicht bzw. nur mangelhaften Bezug zum Artikel. Ein derart vage angedeuteter Bezug zwischen Unvollständigkeitssatz und Menschenrechten ist mMn durchaus esoterisch-skuril. --Boobarkee (Diskussion) 11:54, 9. Apr. 2012 (CEST)

Danke für die Klarstellung. Den Satz mit den Menschenrechten habe ich schon rausgeschmissen. Gruß, --Mussklprozz (Diskussion) 12:13, 9. Apr. 2012 (CEST)

Beweisbarkeit der unbeweisbaren Aussage

Die folgenden Beiträge bis 17:34, 1. Mai 2012 sind von Benutzer_Diskussion:Eulenspiegel1#Gödel kopiert.--Schreiber ✉ 17:36, 1. Mai 2012 (CEST)

Hallo Eulenspiegel1, Mussklprozz und ich haben Deine Änderungen bei Gödelscher Unvollständigkeitssatz reviertiert, weil es sich da um ungünstige FOrmulierungen oder eventuell ein Missverständnis handelt. Du schreibst

Dieser Beweis findet jedoch auf der Meta-Ebene statt. Es existiert jedoch kein Beweis im strengen Sinne, in dem sich der Satz mittels Kalkülen innerhalb der verwendeten Logik ableiten lässt.

und in einem früheren Edit, dass es nicht innerhalb der Prädikatenlogik erster Stufe geht. Ich weiß nicht genau, was du mit "innerhalbd er verwendeten Logik" meinst. Natürlich gibt es im betrachteten Axiomensystem keinen Beweis für "Ich bin nicht beweisbar". Sehr wohl exisitiert aber darin ein Beweis für "Wenn das System konsistent ist, bin ich nicht beweisbar" (siehe Beweise_der_Gödelschen_Unvollständigkeitssätze#Zweiter_Unvollständigkeitssatz für eine Ableitung dieser Aussage in der Peano-Arithmetik). Um "Ich ich bin in der Arithmetik (oder was für ein System man betrachten will) nicht beweisbar" zu zeigen, genügt ein anderes Axiomensysteme in Logik erster Stufe, beispielsweise Arithmetik+transfinite Induktion bis ε₀ oder die Mengenlehre. Der Beweis erfordert zwar dann Axiome, die das betrachtete System nicht hatte, aber der Beweis ist vollkommen formal und findet in einem normalen Kalkül der Prädikatenlogik statt. Grüße--Schreiber ✉ 14:19, 1. Mai 2012 (CEST)

Es kann schon daher nicht in der verwendeten Logik beweisbar sein, da es in der Prädikatenlogik 1. Stufe kein Symbol für "beweisbar" gibt. Das Symbol für "beweisbar" ist $\vdash$. Das heißt, formal aufgeschrieben lautet der Satz "p ist im Modell $\Gamma$ nicht beweisbar": $\neg (\Gamma \vdash p)$. Und der komplette Satz, den es zu beweisen gilt, lautet: Es gibt eine wahre Aussage, die nicht beweisbar ist, oder eine falsche Aussage, die beweisbar ist. Und das formal aufgeschrieben ist:

$\exists p:\,\left(\Gamma \vDash p\wedge \Gamma \not \vdash p\right)\,\lor \,\left(\Gamma \not \vDash p\wedge \Gamma \vdash p\right)$

Und dieser Satz ist weder Prädikatenlogik noch 1. Stufe: In der Prädikatenlogik kommen die Symbole $\vDash ,\vdash$ nicht vor. Sie werden als Metazeichen verwendet, sind selber aber keine Symbole der Prädikatenlogik. Und in der 1. Stufe sind Quantoren nur über Variablen bzw. über Leerstellen von Prädikaten zulässig. In dem Augenblick, in dem man Quantoren über ganze Prädikate macht, erhalten wir die Prädikatenlogik zweiter Stufe.

Es lässt sich zwar mit dem Trick der Gödelisierung aus einem Satz der Prädikatenlogik 2. Stufe ein Satz der Prädikatenlogik 1. Stufe machen. Und dann kann man den Satz der Prädikatenlogik 1. Stufe innerhalb der Prädikatenlogik 1. Stufe beweisen. Aber der Beweis, dass der Satz der Prädikatenlogik 1. Stufe äquivalent ist mit dem Satz der Prädikatenlogik 2. Stufe verläuft wiederum in der 2. Stufe. Grundsätzlich kann man mit der 1. Stufe niemals Sätze beweisen, die in der 2. Stufe aufgeschrieben sind. Und bei dem Beweis des 1. Gödelschen Satzes fällt außerdem auf, dass die Symbole $\vDash ,\vdash$ überhaupt keine Gödelnummer bekommen haben. Damit wurden die beiden Symbole auch nicht in die Prädikatenlogik 1. Stufe eingebettet und verbleiben auf der Meta-Ebene. --Eulenspiegel1 (Diskussion) 16:27, 1. Mai 2012 (CEST)

die formulierung mit dem "vertrauen" finde ich auch nicht so schoen, ich habe den satz nochmal umgeschrieben, ohne inhaltlich etwas zu aendern. wie waere es, die ganze diskussion hier auf die artikeldisk zu kopieren? --Mario d 17:29, 1. Mai 2012 (CEST)

Hab ich gemacht.--Schreiber ✉ 17:36, 1. Mai 2012 (CEST)

(Bearbeitungskonflikt) Du schreibst:

Und der komplette Satz, den es zu beweisen gilt, lautet: Es gibt eine wahre Aussage, die nicht beweisbar ist, oder eine falsche Aussage, die beweisbar ist. Und das formal aufgeschrieben ist:

$\exists p:\,\left(\Gamma \vDash p\wedge \Gamma \not \vdash p\right)\,\lor \,\left(\Gamma \not \vDash p\wedge \Gamma \vdash p\right)$

Das ist nicht richtig, denn das wäre ein Widerspruch gegen den Vollständigkeitssatz, der besagt, dass $\Gamma \vDash \phi$ und $\Gamma \vdash \phi$ äquivalent sind.

Nebenbei (das ist zwar hier nicht entscheidend, aber als Bemerkung):

Es lässt sich zwar mit dem Trick der Gödelisierung aus einem Satz der Prädikatenlogik 2. Stufe ein Satz der Prädikatenlogik 1. Stufe machen.

Naja, mit der Gödelisierung kann man Formeln in der Logik erster Stufe betrachten, aber nicht (im Allgemeinen) Prädikate. Über Formeln kann man in der Logik zweiter Stufe auch nicht direkt reden.

Und bei dem Beweis des 1. Gödelschen Satzes fällt außerdem auf, dass die Symbole $\vDash ,\vdash$ überhaupt keine Gödelnummer bekommen haben. Damit wurden die beiden Symbole auch nicht in die Prädikatenlogik 1. Stufe eingebettet und verbleiben auf der Meta-Ebene.

Naja, $\vdash$ wird durch ein arithmetisches erststufiges Prädikat Bew(x) repräsentiert (Beweise_der_Gödelschen_Unvollständigkeitssätze#Die_Beweisbarkeitsrelation), im folgenden Sinne: Bew(Gφ) ist genau dann im System beweisbar, wenn φ im System beweisbar ist. Diese Äquivalenz ist in der Tat in dieser Form eine Meta-Aussage weil $\vdash$ zunächst auf der Meta-Ebene existiert, aber Bew(x) verhält sich genauso wie $\vdash$, d.h. man kann innerhalb des Systems verlässlich über Beweisbarkeit reden. Grüße--Schreiber ✉ 17:34, 1. Mai 2012 (CEST)

Also die korrekte Aussage lautet z.B.:

$\Gamma \vdash \bot \vee \exists \phi (\neg (\Gamma \vdash \phi )\wedge \neg (\Gamma \vdash \neg \phi ))$

Mit Gödelisierung und dem Bew(x)-Prädikat kann man das leicht zu einer arithmetischen Formel machen.--Schreiber ✉ 17:41, 1. Mai 2012 (CEST)

Dass sich $\vdash$ und Bew() identisch verhalten, ist wiederum eine Aussage auf Meta-Ebene und lässt sich nicht in der Prädikatenlogik 1. Stufe beweisen. Und OK, in Logiken, in denen Tertium non datur gilt, ist deine Aussage äquivalent zum 1. Gödelschen Unvollständigkeitssatz. Was aber auf Meta-Ebene bewiesen werden muss, ist, dass dein Satz äquivalent ist zu:

$Bew(\bot )\vee \exists G_{\phi }(\neg Bew(G_{\phi })\wedge \neg Bew(\neg G_{\phi }))$

Und anschließend muss man auch noch das Diagonallemma anwenden, das besagt: $\forall F\exists p:\,p\leftrightarrow F(G(p))$. Und das Diagonallemma ist ebenfalls Bestandteil der Logik höherer Stufe. Den Allquantor über F könnte man noch wegbekommen, da man das Diagonallemma nicht für alle Formeln sondern nur für eine ganz bestimmte Formel benötigt. Aber den Existenzquantor über p bekommt man nicht weg. --Eulenspiegel1 (Diskussion) 18:23, 1. Mai 2012 (CEST)

Zitat:

Dass sich $\vdash$ und Bew() identisch verhalten, ist wiederum eine Aussage auf Meta-Ebene und lässt sich nicht in der Prädikatenlogik 1. Stufe beweisen. [...] Was aber auf Meta-Ebene bewiesen werden muss, ist, dass dein Satz äquivalent ist zu:

Du kannst $\vdash$ als Prädikat hinzufügen und die mathematische Logik z.B. innerhalb der Mengenlehre in Logik erster Stufe formalisieren. Dann kannst du die Äquivalenz der beiden Prädikate formal in der Prädikatenlogik beweisen. Du könntest einwenden, das $\vdash$ in der formalisierten Logik verhalte sich dann ja nur "zufällig" wie das intuitive $\vdash$ und um deren Äquivalenz zu beweisen, brauche man wieder die Meta-Ebene. Aber das ist dann genau das gleiche Problem, dass man bei jeder Formalisierung mathematischer Aussagen hat. Ebenso wie man eine Aussage über Zahlen in der Arithmetik erster Stufe beweisen kann, kann man eine Aussage über mathematische Logik innerhalb eines geeigneten Systems wie der Mengenlehre beweisen. Ebenso wie man nur auf der Meta-Ebene beweisen kann, dass die formalen Repräsentationen von Zahlen den intuitiven Zahlen entsprechen, kann man natürlich nur auf der Meta-Ebene beweisen, dass das intuitive und das formalisierte $\vdash$ das Gleiche bedeuten. Aber das Gleiche gilt eben bei jeder anderen Formalisierung eines Beweises. Und dennoch würde man wohl kaum behaupten 1+1=2 lasse sich nur auf der Meta-Ebene beweisen, weil die Zahlen nur Objekte der Meta-Ebene sind. Mit dem Unvollständigkeitssatz ist es nicht anders.

Und das Diagonallemma ist ebenfalls Bestandteil der Logik höherer Stufe.[...]

Wie gesagt, in Logik höherer Stufe kann man genauso wenig direkt über Formeln reden wie in der Logik erster Stufe. Man braucht immer irgendeine Art von Gödelisierung (durch Zahlen, Mengen, Funktionen, ...). Aber wie gesagt, das ist bei der Formalisierung immer so. Über "1" kann man in der Arirthmetik auch nicht reden, nur über ein formales Objekt, das wir intuitiv als 1 deuten. Bei den Formeln ist das nicht anders. Grüße--Schreiber ✉ 19:16, 1. Mai 2012 (CEST)