Senior Schreiberling
Date of registration: Jul 5th 2003
Location: Malaga
Occupation: Senior Cloud Solution Engineer bei Oracle
Quoted
Seit F = ...
Dann ist C(F) = ... nicht rekursiv.
Quoted
Korollar: Sei F wie oben. Dann ist C(F) nicht entscheidbar
Quoted
Beispiel: Formeln über L*:
Guru
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Ist dasselbe.Quoted
Original von Sinan
"rekursiv" und "entscheidbar" sind doch zwei Begriffe für eins und dasselbe! oder sehe ich da was nicht?
Es hat niemand behauptet, daß diese Formel wahr ist (also ein sogenannter Satz ist). Es wurde lediglich behauptet, daß es sich um Formeln handelt (also daß die syntaktische Korrektheit gewährleistet ist).Quoted
2. Seite 7:
Quoted
Beispiel: Formeln über L*:
die zweite Formel: wieso existiert da nicht so ein z?
This post has been edited 1 times, last edit by "Joachim" (Jul 26th 2007, 7:17pm)
Senior Schreiberling
Date of registration: Jul 5th 2003
Location: Malaga
Occupation: Senior Cloud Solution Engineer bei Oracle
Quoted
Original von Joachim
Es hat niemand behauptet, daß diese Formel wahr ist (also ein sogenannter Satz ist).
Quoted
Die Formeln (*) aus obigem Beispiel sind Sätze.
Guru
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Sorry, da hab ich ewas durcheinander gebracht. Jetzt aber korrekt:Quoted
Original von Sinan
Oder hat der Begriff "Satz" hier eine Doppelbedeutung? Es wurde im Skript auch definiert: "ein Satz ist eine Formel ohne freie Variablen".
This post has been edited 1 times, last edit by "Joachim" (Jul 27th 2007, 10:32am)
Senior Schreiberling
Date of registration: Jul 5th 2003
Location: Malaga
Occupation: Senior Cloud Solution Engineer bei Oracle
Guru
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
OK, fangen wir vorne an.Quoted
Original von Sinan
[Eine ganze Menge Fragen]
This post has been edited 3 times, last edit by "Joachim" (Jul 27th 2007, 11:11pm)
Senior Schreiberling
Date of registration: Jul 5th 2003
Location: Malaga
Occupation: Senior Cloud Solution Engineer bei Oracle
Quoted
Original von Joachim
Ist M eine Interpretation und F ein Satz, so ist F unter M entweder wahr oder falsch. (Frage an dich: Warum? Und wovon hängt es ab, ob F unter M wahr oder falsch ist?)
Quoted
Es gibt dann also Sätze über L*, von denen mittels Gamma weder bewiesen werden kann, daß sie in N* wahr sind, noch daß sie in N* falsch sind. (Frage an dich: Warum ist das so?)
Quoted
Andererseits kann es aber auch sein, daß Gamma widersprüchlich ist, daß heißt, daß Gamma sowohl einen Satz F als auch seine Negation NOT F enthält. In diesem Fall wäre Gamma^(|-) identisch mit der Menge aller Sätze über L* (Frage an dich: Warum?).
Quoted
Man beachte: Vollständigkeit von Mengen von Sätzen ist etwas anderes als Vollständigkeit von Theorien. (Frage an dich: Was ist der Unterschied?)
Quoted
Man kann zeigen, daß für jede Interpretation M gilt, daß Th(M) vollständig ist. (Frage an dich: Warum ist das so?)
Quoted
Mit den Definitionen von oben wissen wir nun auch, was ein vollständiges Axiomensystem ist. (Frage an dich: Nämlich was?)
Quoted
Leider trat Mitte der 1930er-Jahre Kurt Gödel auf die Bühne der Mathematik und bewies, daß es kein Axiomensystem für Th(N*) gibt, also daß Th(N*) nicht axiomatisierbar ist.
Quoted
Das bedeutet also: Für jedes Axiomensystem Gamma über L* gilt: Entweder ist Gamma unvollständig oder Gamma^(|-) ist eine echte Obermenge von Th(N*) und damit widersprüchlich. (Frage an dich: Warum ist Gamma^(|-) in diesem Fall widersprüchlich?)
Quoted
Gödel hat sogar gezeigt, daß sogar eine vereinfachte Form von Th(N*) nicht axiomatisierbar ist. (Das ist die Menge Q, die Du als die Menge der rationalen Zahlen gelesen hat. Wirf mal einen Blick auf Seite 22 im Skript, dort wird Q definiert.)
This post has been edited 4 times, last edit by "Sinan" (Jul 28th 2007, 8:09pm)
This post has been edited 3 times, last edit by "absynth" (Aug 9th 2007, 3:37pm)
Guru
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Exakt.Quoted
Original von absynth
[EDIT: Oder ist das so, weil ein jeder arithmetischer Satz entweder wahr oder falsch sein muß und nicht beides sein kann?]
This post has been edited 1 times, last edit by "Joachim" (Aug 10th 2007, 11:50am)
Quoted
Original von Joachim
Exakt.Quoted
Original von absynth
[EDIT: Oder ist das so, weil ein jeder arithmetischer Satz entweder wahr oder falsch sein muß und nicht beides sein kann?]
Quoted
(n_1, ..., n_k) element aus M gdw. F(n_1, ..., n_k) gilt.
This post has been edited 7 times, last edit by "Informatik Minister" (Aug 22nd 2007, 12:04pm)
Quoted
Original von Informatik Minister
So meine Auffassung, bzw. kürzer: durch das Unterstreichen wird (verkürzt) das Symbol einer Konstante von ihrer Interpretation unterschieden, Symbol 3, Interpretation 3.
Quoted
Original von absynth
Und nun noch einmal zurück zu S.16 bzw. n_k vs. n_k: n_k ist das Symbol, n_k die vereinfachende Schreibweise für die Interpretation unter N*?
This post has been edited 5 times, last edit by "Informatik Minister" (Aug 22nd 2007, 12:12pm)
Guru
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Die Definition von |- beruht auf besagten Schlußregeln, damit auch die von Dir genannten Sätze. Diese Sätze sind jedoch nicht für beliebige Sammlungen von Schlußregeln wahr. Es gibt allerdings eine Sammlung einfacher Schlußregeln (dies wird in der Vorlesung nicht thematisiert), mit denen |- so definiert werden kann, daß die von Dir genannten Sätze wahr sind.Quoted
Original von absynth
Gelten Korrektheits- und Gödelscher Vollständigkeitssatz
a) aufeinander aufbauend, also mit beiden gelte Gamma |- F <-> Gamma |= F? Sind doch beide Richtungen durch Sätze definiert...
b) Nur bei spezieller Definition von |- S.15 ganz unten als Überleitung zu den Sätzen) mit Schlußregeln?
Quoted
Original von Joachim
Die Definition von |- beruht auf besagten Schlußregeln, damit auch die von Dir genannten Sätze. Diese Sätze sind jedoch nicht für beliebige Sammlungen von Schlußregeln wahr. Es gibt allerdings eine Sammlung einfacher Schlußregeln (dies wird in der Vorlesung nicht thematisiert), mit denen |- so definiert werden kann, daß die von Dir genannten Sätze wahr sind.Quoted
Original von absynth
Gelten Korrektheits- und Gödelscher Vollständigkeitssatz
a) aufeinander aufbauend, also mit beiden gelte Gamma |- F <-> Gamma |= F? Sind doch beide Richtungen durch Sätze definiert...
b) Nur bei spezieller Definition von |- S.15 ganz unten als Überleitung zu den Sätzen) mit Schlußregeln?
Guru
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Ja, steht doch so im Skript.Quoted
Original von absynth
Und Gamma |- F <=> Gamma |= F? Folgt das (unter den oben erwähnten Schlußregeln) aus den beiden Sätzen?
This post has been edited 1 times, last edit by "Joachim" (Aug 22nd 2007, 2:56pm)