Diskussion:Gödelscher Vollständigkeitssatz

Nicht ganz korrekt

Die Definition am Anfang ist nicht ganz korrekt bzw. zumindest missverständlich. "jeder Satz, der gemäß der logischen Schlussregeln aus einer Aussage folgt, lässt sich auf Grund der Ableitungsregeln der Sprache des Systems herleiten und umgekehrt" klingt so, als ließe sich ein Satz, der semantisch aus einer Aussage folgt, syntaktisch "einfach so", d.h. ohne diese Aussage herleiten. Zudem klingt es so, als müsse jeder Satz aus genau einer Aussage folgen. Ich würde eher eine Formulierung dieser Art wählen: "Alle semantisch gültigen Argumente sind auch syntaktisch gültig (herleitbar) (und -je nach Formulierung- umgekehrt)." --GottschallCh 12:21, 12. Dez 2005 (CET)

Unverständlich

Zumindestens die Bedeutung von $\vDash$ und $\vdash$ würde ich an dieser Stelle gern wissen. Der Artikel ist ja vor allem für Nicht-Logiker interessant. Galaxy07 15:49, 22. Nov 2004 (CET)

Dem stimme ich zu, die Konzepte von semantischer und syntaktischer Gültigkeit sollten erklärt oder verlinkt werden (ich habe aber kein geeignetes Linkziel gefunden). Ich halte weiter Ausschau bzw. schreibe notfalls etwas Eigenes. --GottschallCh 12:17, 12. Dez 2005 (CET)

Zu beachten ist, dass dies nicht für jedes formale System gilt: Gödel zeigte in seinem Unvollständigkeitssatz, dass Systeme, die mächtig genug sind, nicht gleichzeitig widerspruchsfrei und vollständig sein können.

Da fehlt wohl was. Mächtig genug, um ???

--zeno 00:06, 15. Feb 2005 (CET)

Mäöchtig genug u.a. um arithemtische "Tatsachen" auszudrücken. Vollständig in diesem Sinne sind nur "schwächere" Systeme. Gödel hat erst die Vollständigkeit der schwächeren Systeme gezeigt (was erwartet wurde, aber nicht bewiesen war, m.a. an einer Klasse von bestimmten Logiksystemen (Logiksprachen), nämlich der sog. Prädikatenlogik 1. Stufe mit einigen Einschränkungen) und dann die Unvollständigkeit von stärkeren Systemen.

Kann sich bitte ein Mathematiker nochmal dieses Artikel annehmen und auch die "dagger": "ist ableitbar, gdw. folgt logisch besser erklären?

Martin

Ein Mathematiker sagt dazu: Mächtig genug, um den Gödelsatz zu beweisen ;)

Also ich hab jetzt leider nicht die Zeit mich des Artikels anzunehmen, aber ich kann ja mal ein paar "Duftmarken" legen, vielleicht lässt sich jemand bei Gelegenheit davon inspirieren. Statt mächtig sollte man aber lieber "ausdrucksstark" sagen, weil Mächtigkeit in der Mathematik üblicherweise in einem anderen Kontext verwendet wird.

Genauer gesagt betrifft der Gödelsatz solche Systeme, die man als "rekursiv enumerable Erweiterungen der PRA (primitiv rekursive Arithmetik)" bezeichnet. Die PRA ist eine etwas abgeschwächte Form der Peanoarithmetik. Nicht-Mathematiker, die sich nicht so ins Detail hineinsteigern möchten sollten sich darunter der Einfachheit halber am besten "die Arithmetik" vorstellen (bitte aber mit den Gänsefüßchen;), d.h. man "kennt" die Natürlichen Zahlen und die "wichtigsten" Funktionen darauf, z.B. Addition und Multiplikation, uva. Diese "wichtigen" Funktionen sind genau diejenigen, die man "primitiv rekursiv" nennt, was ich hier nicht genauer erläutern will. Das sind die Werkzeuge die wir brauchen, um den Gödelsatz zu beweisen. Warum brauchen wir die? Nun, der Gödelsatzt sagt ja quasi "innerhalb" des Systems etwas über das "Ausserhalb" aus, d.h. die ganzen "äußeren" sprachlichen Mittel (die Funktionen, die Prädikate etc.) müssen irgendwie "innerhalb" des Systems ausgedrückt werden, und das geschieht indem man sie als Natürliche Zahlen codiert. Damit man innerhalb des Systems "vernünftig" mit diesen Codes arbeiten kann, muss natürlich auch die Codierung mit den Mitteln des Systems "ausgerechnet" werden können, d.h. in unserem Fall eine primitiv rekursive Funktion sein. Wie diese Codierung genau vor sich geht ist dabei nicht wichtig, es sind unzählig viele denkbar, und für den Beweis des Gödelsatzes genügt es zu wissen, dass sich die "gewählte" Codierung mittels einer primitiv rekursiven Funktion berechnen lässt.

Bei schwächeren Systemen gibt es z.B. die Arithmetik Q (Robinson Arithmetik), die das Induktionsschema komplett weglässt. Auch hier lässt sich der Unvollständigkeitssatz anwenden. Für die Pressburger Arithmetik, in der es die Addition, aber keine Multiplikation gibt, lässt sich die Vollständikeit beweisen.

Vollständigkeit ist nicht Korrektheit

Der Vollständigkeitssatz zeigt meines Wissens nach die Vollständigkeit und nicht die Korrektheit (ist die umgekehrte Richtung)

Das hängt vom Autoren ab. Die Korrektheit wird häufig in der Vollständigkeit mit eingeschlossen. Man bedenke, dass ein Kalkül, der nicht korrekt ist, alles herzuleiten gestattet, und somit trivialerweise vollständig ist. EIn Vollständigkeitsbegriff macht also ohne die Voraussetzung der Korrektheit nicht sonderlich viel Sinn.

Stichwort parakonsistente Logik, die Vollständigkeit eines nicht korrekten Kalküls wir erst trivial, wenn der Kalkül auch die Ex Falso Quodlibet Regel enthält. Die parakonsistente Logik befast sich genau damit, nicht widerspruchsfreie, nicht triviale Kalküle zu untersuchen. Tatsächlich enthält die hier wiedergegebene Formulierung ein 'genau dann wenn' und beschreibt somit sowohl Vollständigkeit (Wenn etwas semantisch folgt, dann ist es beweisbar) als auch die Korrektheit (Wenn etwas beweisbar ist, dann folgt es auch semantisch [ist es wahr]).

Vollständigkeit vs. Unvollständigkeit

Ich glaube, dass der im Artikel dargestellte Gegensatz zwischen Vollständigkeit und Unvollständigkeit falsch ist. Soweit ich weiß, bezieht sich der Vollständigkeitssatz auf Allgemeingültigkeit, während die Unvollständigkeit sich auf die Gültigkeit in einem bestimmten Modell bezieht. D.h. der gödelsche Vollständigkeitssatz sagt z.B. etwas über die Prädikatenlogik im allgemeinen aus, während der gödelsche Unvollständigkeitssatz etwas über z.B. das Standardmodell der Natürlichen Zahlen aussagt. Weiss da jemand genauer bescheid?

Hallo, der Artikel vermischt 2 verschiedene Bedeutungen von "vollständig", nämlich
1. Alles, was semantisch aus einer Satzmenge folgt, lässt sich auch im System ableiten.
2. Eine Satzmenge S hat die Eigenschaft, dass für jede beliebige Formal A gilt: A folgt aus S oder nicht-A folgt aus S.
Der Gödelsche Vollständigkeitssatz bezieht sich auf (1), der Unvollständigkeitssatz auf (2).
Alles, was sich auf (2) bezieht, sollte daher aus dem Artikel getilgt werden (hab selber aber momentan auch wenig Zeit, vielleicht später). Gruß von Wasseralm 14:14, 12. Dez 2005 (CET)

Hallo! Der Begriff "vollständig" ist tatsächlich mehrdeutig, aber der erste Unvollständigkeitssatz von Gödel bezieht sich eigentlich doch auf (1). Nur ein Zitat:

"Ist U ein Bereich, der die natürlichen Zahlen enthält, und L eine Sprache, in der die Arithmetik der natürlichen Zahlen ausdrückbar ist, so ist jedes in L formulierte Axiomensystem A [...] in dem Sinn unvollständig, dass nicht alle in U wahren Aussagen aus A abgeleitet werden können" (Meyers Kleine Enzyklopädie Mathematik, 1995, S. 773)

Wenn du das genau durchliest, müßtest du eigentlich sehen, dass es nichts mit (1) zu tun hat. Wasseralm

Noch ein (rhetorisches) Gegenargument: Vollständigkeit im Sinn von (2) wäre für ein formales System im Allgemeinen gar nicht wünschenswert - wenn man in der Prädikatenlogik tatsächlich jeden Satz oder seine Negation herleiten könnte, dann könnte man insbesondere entweder ein(x,F(x))→alle(x,F(x)) ("Wenn es einen rosa Elefanten gibt, dann sind alle Dinge rosa Elefanten") oder seine Negation ¬(ein(x,F(x))→alle(x,F(x))), die äquivalent ist mit ein(x,F(x))∧ein(x,¬F(x)) ("Es gibt Dinge, die rosa Elefanten sind, und es gibt Dinge, die keine rosa Elefanten sind") herleiten. Es ist aber keiner dieser beiden Sätze allgemeingültig.

In diesem Sinn fände ich den Hinweis im Artikel schon gut, dass zwar die Prädikatenlogik im Sinn von (1) vollständig ist, dass es aber durchaus auch formale Systeme gibt, die im Sinn von (1) unvollständig sind.

Viele Grüße, --GottschallCh 23:39, 18. Jan 2006 (CET)

Ich habe vor, den Artikel noch weiter auszubauen, und auch auf den Unvollständigkeitssatz kurz einzugehen, damit die Zusammenhänge klarer werden. Bitte Geduld. Gruß von Wasseralm 08:32, 19. Jan 2006 (CET)

Sorry, ich habe zur falschen Tageszeit und ohne ausreichendes Nachdenken geschrieben und dabei Gödel und Tarski zusammengeworfen. ;-) Die Formulierung im Meyer ("wahr") war auch nicht sehr hilfreich. Mein zweiter Einwand ist damit inhaltlich natürlich auch gegenstandslos und kann höchstens noch als Indiz dafür gelten, in welche Richtung man das missverstehen kann. Insofern wäre ein Kapitel, in dem die Zusammenhange explizit angesprochen werden, sicher eine Hilfe. Viele Grüße, --GottschallCh 14:46, 19. Jan 2006 (CET)