Vollständigkeitssatz, Kompaktheitssatz und Unentscheidbarkeit der Prädikatenlogik Flashcards
(13 cards)
Definition 4.1: Sequenz (Skript 93)
Eine Sequenz ist ein Ausdruck GAMMA => DELTA, wobei GAMMA, DELTA endliche Mengen von Sätzen in FO(tau) sind. Eine Sequenz GAMMA => DELTA ist gültig, wenn jedes Modell von GAMMA auch ein Modell mindestens einer Formel in DELTA ist.
Axiome des Sequenzkalküls sind alle Sequenzen der Form GAMMA, DELTA => DELTA, psi.
Satz 4.3 zur Korrektheit des SQ
Jede im Sequenzenkalkül ableitbare Sequenz ist gültig.
Definition 4.4 Wann ist ein Satz psi ableitbar aus dem Axiomensystem PHI? (PHI |- psi) (Skript 97)
Sei PHI teilmenge FO(sigma) eine Menge von Sätzen. Ein Satz psi ist ableitbar aus dem Axiomensystem PHI (kurz PHI |- psi), wenn eine endliche Teilmenge GAMMA von PHI existiert, so dass die Sequenz GAMMA => psi im SQK ableitbar ist. Eine Sequenz GAMMA => DELTA ist ableitbar aus PHI, wenn es eine ableitbare Sequenz GAMMA, GAMMA’ => DELTA gibt, mit GAMMA’ teilmenge PHI.
Definition inkonsistente/konsistente Satzmenge (Skript 97)
Satzmengen PHI, aus denen jeder Satz ableitbar ist heissen inkonsistent. Wegen der Korrektheit des SQK sind inkonsistente Mengen unerfüllbar.
Wenn nicht jeder Satz aus PHI ableitbar ist, dann heisst PHI konsistent. PHI ist genau dann konsistent, wenn jede endliche Teilmenge von PHI konsistent ist.
Satz 4.6: Vollständigkeitssatz für den Sequenzenkalkül (Skript 97)
Für jede Satzmenge PHI teilmenge FO(sigma) und jeden Satz psi element FO(sigma) gilt:
i) PHI |= psi gdw. PHI |- psi
ii) PHI ist genau dann konsistent, wenn PHI erfüllbar ist.
Definition 4.7: Herbrandstruktur (Skript 99)
Eine Herbrandstruktur zu einer Signatur tau (die mindestens ein Konstantensymbol enthält) ist eine tau-Struktur H~, deren Universum die Menge aller Grundterme der Signatur tau ist und deren Funktionssymbole durch ihre natürliche Operation auf den Termen interpretiert werden: für n-stelliges f element tau ist f^H~(t1, …, tn) := f t1, .., tn.
Die Interpretation der Relationssymbole aus tau ist beliebig.
Definition 4.9: Kongruenzrelation (Skript 99)
Sei A~ eine tau-Struktur. Eine Kongruenzrelation auf A~ ist eine Äquivalenzrelation ~auf A, welche in folgendem Sinn mit den Relationen und Funktionen von A~ kompatibel ist:
1) Ist f element tau ein n-stelliges Funktionssymbol und a1, …, an , b1, …, bn element A mit a1 ~ b1, …, an ~ bn, so gilt:
f^A~(a1, …, an) ~ f^A~(b1, …, bn)
2.) Ist R element tau ein n-stelliges Relationssymbol und a1, …., an, b1, …, bn element A mit a1 ~ b1 , …, an ~ bn, so gilt:
(a1, …, an) element R^A~ gdw. (b1, …, bn) element R ^A~
Ist ~ eine Kongruenzrelation auf A~, so bezeichnen wir mit [a] := {b element A : a ~ b} die Kongruenzklasse von a unter ~.
Definition 4.10 Faktorstruktur (Skript 100)
Sei A~ eine tau-Struktur und ~ eine Kongruenzrelation auf A~. Die Faktorstruktur A~/~ ist die tau-Struktur mit Universum {[a] : a element A } (der Menge der Kongruenzklassen von ~) und der folgenden Interpretation der Relations- und Funktionssymbole.
1) Ist f element tau ein n-stelliges Funktionssymbol und a1, …, an element A, so gilt:
f^A~/~([a1], …, [an]) = [f^A~(a1, …, an)]
2) ist R element tau ein n-stelliges Relationssymbol und a1, …, an element A, so gilt:
([a1], …, [an]) element R^A~/~ gdw. (a1, …, an) element R^A~
Satz 4.20 Kompaktheitssatz der Prädikatenlogik (Skript 109)
Für jede Menge PHI teilmenge FO(tau) und jedes psi element FO(tau):
i) PHI |= psi gdw. eine endliche Teilmenge PHI_0 teilmenge PHI existiert, so dass PHI_0 |= psi
ii) PHI ist genau dann erfüllbar, wenn jede endliche Teilmenge von PHI erfüllbar ist.
Beweis: Da nach dem Vollständigkeitssatz eine Formelmenge genau dann erfüllbar ist, wenn sie konsistent ist, und die Folgerungsbeziehung |= mit der Ableitungsbeziehung |- zusammenfällt, ergeben sich die semantischen Aussagen des Kompaktheitssatzes.
Satz 4.23: Mächtigkeit der Potenzmenge (Skript 111)
Keine Menge ist gleich mächtig zu ihrer Potenzmenge
Satz 4.23 Aufsteigender Satz von Löwenheim-Skolem (skript 110)
Sei PHI teilmenge FO(tau) eine Satzmenge.
i) PHI besitze beliebig grosse endliche Modelle (d.h. für jedes n element Nat.Z. gibt es ein Modell A~ |= PHI mit endlichem A~ und |A~| >n). Dann hat PHI auch ein unendliches Modell.
ii) PHI besitze ein unendliches Modell. Dann gibt es zu jeder Menge M ein Modell D~ |= PHI über einem Universum D, welches mindestens so mächtig wie M ist.
Folgerung 4.25: Axiomatisierbarkeit der Klasse aller endlichen tau-Strukturen (Skript 112)
Die Klasse aller endlichen tau-Strukturen ist nicht FO-axiomatisierbar.
Ebenso die Klasse aller endlichen Gruppen, die Klasse aller endlichen Körper, aller endlichen Graphen etc.
Satz 4.30 (Church Turing) Entscheidbarkeit des Gültigkeitsproblems (Skript 118)
Das Gültigkeitsproblem (und damit auch das Erfüllbarkeitsproblem) der Prädikatenlogik ist unentscheidbar.
erf: Entscheide zu einer Formel, ob sie erfüllbar ist
gült: entscheide zu einer Formel, ob sie allgemeingültig ist
