1. Goedelscher Unvollständigkeitssatz
-
http://en.wikipedia.org/wiki/Gödel's_incompleteness_theorems#cite_ref-0
Was heißt denn hier "wahr" bezüglich eines Axiomensystems? Und warum definiert man nicht genau die Aussagen als wahr, die aus den Axiomen ableitbar, d.h. beweisbar sind?
-
Heißt "wahr" vielleicht, dass die Negation nicht beweisbar ist? (vgl. http://en.wikipedia.org/wiki/Complete_theory)
-
Interessuerter schrieb:
http://en.wikipedia.org/wiki/Gödel's_incompleteness_theorems#cite_ref-0
Was heißt denn hier "wahr" bezüglich eines Axiomensystems? Und warum definiert man nicht genau die Aussagen als wahr, die aus den Axiomen ableitbar, d.h. beweisbar sind?
Das tut man doch. Und genau dafür braucht man das "bezüglich eines Axiomensystems". Wenn man so definiert was wahr sein soll, muß man natürlich auch immer brav dazusagen welches Axiomensystem man gerade meint.
-
Jester schrieb:
Interessuerter schrieb:
http://en.wikipedia.org/wiki/Gödel's_incompleteness_theorems#cite_ref-0
Was heißt denn hier "wahr" bezüglich eines Axiomensystems? Und warum definiert man nicht genau die Aussagen als wahr, die aus den Axiomen ableitbar, d.h. beweisbar sind?
Das tut man doch. Und genau dafür braucht man das "bezüglich eines Axiomensystems". Wenn man so definiert was wahr sein soll, muß man natürlich auch immer brav dazusagen welches Axiomensystem man gerade meint.
Aber die Aussage des 1. Unvollständigkeitssatzes ist doch (oder verstehe ich das falsch?):
Gegeben ein konsistentes und genügend mächtiges Axiomensystem. Dann gibt es eine bezüglich dessen wahre, aber nicht beweisbare Aussage.
-
Interessierter schrieb:
Jester schrieb:
Interessuerter schrieb:
http://en.wikipedia.org/wiki/Gödel's_incompleteness_theorems#cite_ref-0
Was heißt denn hier "wahr" bezüglich eines Axiomensystems? Und warum definiert man nicht genau die Aussagen als wahr, die aus den Axiomen ableitbar, d.h. beweisbar sind?
Das tut man doch. Und genau dafür braucht man das "bezüglich eines Axiomensystems". Wenn man so definiert was wahr sein soll, muß man natürlich auch immer brav dazusagen welches Axiomensystem man gerade meint.
Aber die Aussage des 1. Unvollständigkeitssatzes ist doch (oder verstehe ich das falsch?):
Gegeben ein konsistentes und genügend mächtiges Axiomensystem. Dann gibt es eine bezüglich dessen wahre, aber nicht beweisbare Aussage.
Eine geschlossene Formel "phi" ist wahr bezüglich eines Axiomensystems, wenn "phi" in jedem Modell dieses Axiomen-Systems wahr ist.
Ein Axiomen-System ist erstmal nur eine Sammlung von geschlossenen Formeln, die bestimmte Funktionen und Konstanten benutzen. Zum Beispiel hat ein Axiomen-System für die natürlichen Zahlen oft eine einstellige Funktion "Nachfolger" und eine Konstante "0". Ein Modell ist dann etwas konkretes, wo diese abstrakten Funktionen über irgendwelchen geeigneten Trägermengen interpretiert werden. Zum Beispiel könnte man "Nachfolger(n)" interpretieren als "InterpretationVon(n) + 1" auf der Trägermenge ℕ.
Man sagt "M ist ein Modell des Axiomensystems A", wenn jede Formel aus A bzgl. M wahr ist.
Im allgemeinen hat ein Axiomensystem mehr als ein Modell. Wenn man sich z.B. in Logik erster Stufe bewegt, hat ein Axiomemsystem, dass mindestens ein unendliches Modell hat, automatisch unendlich viele Modelle.
"phi ist bzgl. des Axiomensystems wahr" bedeutet also "Für alle Modelle M des Axiomensystems gilt: phi ist wahr bzgl. M." oder anders gesagt:
Sei M ein beliebiges Modell des Axiomensystems, dann gilt: "phi ist bzgl. M wahr."Und "phi ist wahr bzgl. eines Modells" ist schließlich rekursiv über die Struktur der Formeln definiert. Unter anderem hat man z.B.:
"phi ∧ psi" ist wahr genau dann, wenn "phi" und "psi" wahr sind.
"∀x. phi[x]" ist wahr genau dann, wenn "phi[x]" wahr ist für alle x aus der Trägermenge (wobei "phi" jetzt eine Formel mit einer freien Variablen ist, und "phi[x]" diese eine Variable mit x belegt).
"∃x. phi[x]" ist wahr genau dann, wenn "phi[x]" wahr ist für mindestens ein x aus der Trägermenge.Die Basisfälle dieser rekursiven Definition sind z.B. "x = y", was wahr ist genau dann, wenn x und y auf der Trägermenge das gleiche Element bezeichnen. Je nach Axiomensystem hat man auch noch Prädikate als Basisfälle; in den natürlichen Zahlen wäre ein Prädikat z.B. "istNull(x)".
Damit kann man "eine Formel ist wahr bzgl. eines Axiomensystems" definieren, ohne auf Beweise Rücksicht nehmen zu müssen.
Man kann es auch so sehen:
"phi ist wahr" ist eine Aussage über die Semantik, während "phi ist beweisbar" eine Aussage über die Syntax ist.
-
Super Erklärung
-
Interessuerter schrieb:
Was heißt denn hier "wahr" bezüglich eines Axiomensystems?
"wahr" heißt vereinfacht gesagt, daß die Aussage für alle Belegungen stimmt, es also sozusagen kein Gegenbeispiel gibt. "Beweisbar" heißt, daß es einen axiomatisch-deduktiven Beweis gibt.
Es gibt nach Gödel Aussagen, die nicht durch eine Belegung widerlegt werden können, und dennoch nicht beweisbar sind. Solange die Fermatsche Vermutung nicht bewiesen war, hätte man glauben können, diese wäre eine solche Behauptung, die für alle Belegungen wahr, aber nicht beweisbar ist. Inzwischen weiß man es besser.
Demzufolge ist der gewöhnliche Aussagenkalkül und mithin jeder Kalkül, der mindestens so aussagekräftig wie der gewöhnliche Aussagenkalkül (in welchem man die Gesetze der Arithmetik formulieren kann) ist, "unvollständig". Traurig, aber wahr (im beweisbaren Sinne :D).
-
Eine Alternative waere natuerlich die Widerspruchsfreiheit aufzugeben um nichtbeweisbare Wahrheiten als Axiome mit aufzunehmen. Nicht sehr verlockend.
-
knivil schrieb:
Eine Alternative waere natuerlich die Widerspruchsfreiheit aufzugeben um nichtbeweisbare Wahrheiten als Axiome mit aufzunehmen. Nicht sehr verlockend.
Eine nicht beweisbare Aussage kannst Du doch bequem als Axiom aufnehmen. Dadurch handelst Du Dir keine Widersprüche ein -- ein Widerspruch wäre ja nichts anderes als ein Widerspruchsbeweis für Deine Aussage. Die war ja aber nicht beweisbar.
Allerdings hilft Dir das auch nicht weiter. Schließlich verspricht Gödel Dir wieder ne neue Aussage, die wahr aber nicht beweisbar ist.
In Probleme mit der Widerspruchsfreiheit läufst Du erst, wenn Du versuchst alle nicht beweisbaren Wahrheiten auf einmal dazuzunehmen. Immer brav eine nach der anderen ist kein Problem.
-
Jester schrieb:
In Probleme mit der Widerspruchsfreiheit läufst Du erst, wenn Du versuchst alle nicht beweisbaren Wahrheiten auf einmal dazuzunehmen. Immer brav eine nach der anderen ist kein Problem.
Soweit ich weiss, fuehrt z.B. die Koninuumshypothese als auch ihre Negation in ZFC nicht zu einem Widerspruch, was ist, wenn ich die beide brav nacheinander aufnehme?
-
XFame schrieb:
Jester schrieb:
In Probleme mit der Widerspruchsfreiheit läufst Du erst, wenn Du versuchst alle nicht beweisbaren Wahrheiten auf einmal dazuzunehmen. Immer brav eine nach der anderen ist kein Problem.
Soweit ich weiss, fuehrt z.B. die Koninuumshypothese als auch ihr Negation in ZFC nicht zu einem Widerspruch, was ist, wenn ich die beide brav nacheinander aufnehme?
Dann machst du zwei Schritte ("Cont" sei die Kontinuums-Hypothese):
1. "ZFC" -> "ZFC mit Cont"
2. "ZFC mit Cont" -> "ZFC mit Cont und mit ~Cont".Schritt 1 ist dadurch gerechtfertigt, dass "Cont" unabhängig von "ZFC" ist.
Schritt 2 kannst du nicht rechtfertigen, weil "~Cont" nicht mehr unabhängig von "ZFC mit Cont" ist.
-
Ah stimmt, danke.
-
Vergesst mal die Vorausetzung "effektiv Axiomatisierbar" nicht. Sonst währe [; Th(\mathcal{N})
ein einfaches Gegenbeispiel zu Gödel's erstem Unvollständigkeitssatz.
-
mazal schrieb:
"effektiv Axiomatisierbar"
[; Th(\mathcal{N})
Was heißt das?
-
[; \mathcal{N}
== Standardmodell der Arithmetik.
[; Th(\mathcal{N}) == Theorie der Arithmetik.
-
und "effektiv Axiomatisierbar" ?
-
Axiome endlich + rekursiv aufzählbar.