Diskussion:Gödelscher Unvollständigkeitssatz
Es gibt zwei Gödelsche Unvollständigkeitssätze. Siehe englische Wikipedia. --zeno 18:25, 6. Jul 2003 (CEST)
Ideen zur Ergänzung:
- Theorie erklärt nicht den speziellen Gebrauch im Kontext: eine Theorie hier ist (soll sein) eine deduktiv abgeschlossene Menge von Formeln.
- Deutlicher darauf hinweisen, dass man es mit der Prädikatenlogik Logik erster Stufe zu tun hat (PL1).
- Beispiele für mathematisch sinnvolle unentscheidbare Resultate geben, zB Version des Theorems von Ramsey... siehe englische Version.
- Die Unvollständigkeitssätze vom Vollständigeitssatz abgrenzen.
- Nichtstandardmodelle.
- Minimale Voraussetzungen der Unvollständigkeit beschreiben (Robinson's Arithmetik Q).
- Auf philosophische Mißverständnisse hinweisen.
- Modale Beweislogiken im zshg mit 2. Unvollständidkeitssatz.
Wäre auch toll, wenn man den Text etwas auflockern könnte und z. B. Unterüberschriften einbauen könnte. Vielleicht auch eine Einleitung für den Laien ("Nicht alles Wahre lässt sich beweisen")? Stern 21:49, 21. Feb 2004 (CET)
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)
Nicht in jedem formalen System sind alle Sätze beweisbar oder widerlegbar, selbst wenn man das System erweitert heisst nur, dass es unvollständige Systeme gibt. Es geht ja aber grade darum, dass ALLE hinreichend mächtigen Systeme unvollständig sind.
- 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)
Beispiel
Vielleicht hab ich da ja was falsch verstanden, aber das angegebene Beispiel des Verschlüsselungsverfahrens hat doch mit Unvollständigkeitssatz gar nichts zu tun, oder? -- 240 Bytes (Diskussion) 13:48, 30. Mai 2004 (CEST)
- Ich denke schon. Wenn ich einen Zustand mm bekomme, und dann nicht mehr rückverfolgen kann, ob das mm aus einem mm entstanden ist, oder aus einem ml dann habe ich einen Widerspruch, ich kann hinterher nicht mehr sagen, ob mm oder ml der Verursacher war.
Wenn ich diesen Umstand nun zu vermeiden suche, indem ich ein neues Zeichen einführe, dann bekomme ich mindestens einen neuen Widerspruch:
Kam n@ aus nn oder aus mz
Dieser Widerspruch lässt sich auch durch ein weiteres Zeichen nicht beseitigen. Ich kann natürlich die Aussage machen, das @=27 unveränderbar ist.
Damit ist aber das System Verschlüsselungsverfahren unvollständig, denn bei weiteren Durchläufen ändert sich das @ nicht mehr:
hammer -> hbn@gt -> hco@iv
Beim Rückentschlüsseln hat man das Problem sagen zu können, ob hco@iv -> hbn@gt oder hco@iv -> hbnngt zutrifft.
im Falle von hbnngt würde hamldq zurückübersetzt werden.
Es ist halt ein Beispiel für ein System, an der man den Gödelschen Unvollständigkeitssatz sehr gut nachvollziehen kann. --Arbol01 14:13, 30. Mai 2004 (CEST)
Nachsatz: Necrophorus hat mich dazu animiert, die Verschlüsselung als Beispiel einzuarbeiten. --Arbol01 14:13, 30. Mai 2004 (CEST)
- Die Verschlüsselungsfunktion ist nicht eindeutig umkehrbar, soviel ist klar - aber der Unvollständigkeitssatz macht doch keine Aussage darüber, ob eine Funktion reversibel ist oder nicht. Ich denke, dass Du da den Begriff unvollständig auf ein anderes System beziehst, nicht auf Gödels Satz. Der besagt nicht, dass es unvollständige System gibt (das wusste man schon länger), sondern dass jedes axiomatische formale System unvollständig ist, weil es Aussagen ermöglicht, die mit Hilfe dieses Systems nicht beweisbar sind - das ist doch etwas anderes, viel weiter gehendes. Leider ist es schon etwas länger her, dass ich den Hofstädter gelesen habe, aber ich glaube, dort könnte man ein besseres (und passenderes) Beispiel finden. Dein Beispiel würde eher zu einem Artikel über Falltüfunktionen o. ä. passen. -- 240 Bytes (Diskussion) 16:18, 30. Mai 2004 (CEST)
"Der besagt nicht, dass es unvollständige System gibt (das wusste man schon länger), sondern dass jedes axiomatische formale System unvollständig ist, weil es Aussagen ermöglicht, die mit Hilfe dieses Systems nicht beweisbar sind". Das ist mir auch bekannt. Aber mein Beispiel zeigt, wie man so etwas verstehen kann. Jedes System hat seine eigenen Fallstricke. Es ist viel schwieriger zu zeigen, das ein System formal unvollständig ist, als seine Widersprüche aufzudecken, oder anders gesagt, wenn das RSA-Verfahren widerspruchsfrei ist, wo ist dann seine Unvollständigkeit? --Arbol01 16:32, 30. Mai 2004 (CEST)
- Ein unvollständiges System kann man genauso trivial konstruieren wie ein widersprüchliches (da gäbe es durchaus einfachere Beispiele als deins). Das hilft aber beim Thema dieses Artikels nicht weiter. -- Fuzzy 19:16, 31. Mai 2004 (CEST)