Moderne Termlogik: Standardsemantik der Termlogik: Korrektheit und Vollständigkeit

Hoch zum Inhaltsverzeichnis

Moderne Termlogik

Standardsemantik der Termlogik

Korrektheit und Vollständigkeit

Es gibt jetzt zwei unterschiedliche Folgerungsbegriffe: Die syntaktische Folgerung $\vdash$, die auf dem Kalkül mit Zeichenketten beruht, und die semantische Folgerung $\models$, die mit der Mengenlehre arbeitet. Es ist nicht verwunderlich, dass wir die genauen Zusammenhänge zwischen diesen beiden Begriffen untersuchen wollen. Dazu werden zwei wichtige Begriffe eingeführt.

Definition: Ein Kalkül (mit dem die syntaktische Folgerung $\vdash$ definiert wird), zusammen mit einer Semantik (durch die man die semantische Folgerung $\models$ definiert) heisst korrekt, wenn gilt:

Aus $\Phi \vdash p$ folgt $\Phi \models p$.

Definition: Ein Kalkül (mit dem die syntaktische Folgerung $\vdash$ definiert wird), zusammen mit einer Semantik (durch die man die semantische Folgerung $\models$ definiert) heisst vollständig, wenn gilt:

Aus $\Phi \models p$ folgt $\Phi \vdash p$.

Nun lässt sich der Hauptsatz beweisen, durch den die Bedeutung der klaren Unterscheidung zwischen Syntax und Semantik deutlich wird:

Satz: Der Kalkül der Termlogik, zusammen mit der Semantik der nichtleeren Mengen, ist korrekt und vollständig.

*Beweis: Korrektheit. Gegeben sei eine Menge $\Phi$ von Aussagen. Wir nehmen an, dass mit Hilfe des Regelsystems des Kalküls eine syntaktische Folgerung $p$ gewonnen wurde, dass also $\Phi \vdash p$ gilt. Wir müssen zeigen, dass auch $\Phi \models p$ gilt. Dazu gehen wir alle vier Grundregeln durch. Nehmen wir z.B. an, bei der Ableitung sei die Regel $R_{1}$, $Axy\rightarrow Iyx$ benutzt worden; d.h. es gibt Terme $a,b$, so dass $p=Iba$ gilt, und dass $Aab\in \Phi$. Anders ausgedrückt: Aus $Aab$ wird $p=Iba$ abgeleitet. Wir können nun zeigen, dass auch $Aab\models Iba$ gilt: Sei ${\mathfrak {I}}=\left({\mathfrak {i,U}}\right))$ ein beliebiges Modell von $Aab$; d.h. es gelte $A={\mathfrak {i}}(a)\subset B={\mathfrak {i}}(b)$. Dann ist $A\cap B=A$, und es gilt auf jeden Fall $A\cap B\neq \emptyset$. Das bedeutet, dass tatsächlich $\Phi \models p$ gilt. -- Mit der gleichen Methode kann man die Korrektheit der anderen drei Regeln beweisen (was wir hier nicht ausführen, sondern als Übungsaufgabe stellen). Da sich alle syntaktischen Ableitungen aus diesen vier Regeln nacheinander ausführen lassen, ist damit die Korrektheit des Kalküls und der Semantik bewiesen.

*Beweis: Vollständigkeit. Wie gewöhnlich ist der Beweis der Vollständigkeit schwieriger. Hier müssen wir beweisen, dass aus $\Phi \models p$ $\Phi \vdash p$ folgt.

Um den Beweis übersichtlich zu halten, werden wir den Beweisschritt 1 gesondert in einem Hilfssatz im Anschluss beweisen. Ein wichtiger Begriff ist der der Konsistenz einer Aussagenmenge: Eine Aussagenmenge heisst konsistent, wenn es keine Aussgae $p$ gibt mit $\Phi \vdash p$ und $\Phi \vdash C(p)$.

Beweisschritt 1. Es gelte $\Phi \models p$. Dann ist $\Phi \cup {C(p)}$ inkonsistent.

Beweisschritt 2. Die Inkonsistenz von $\Phi \cup {C(p)}$ bedeutet, dass es eine Aussage $q$ gibt mit $\Phi \cup {C(p)}\vdash q$ und $\Phi \cup {C(p)}\vdash C(q)$. Die Beweismethode des indirekten Beweises ergibt, dass $\Phi \vdash p$ gilt, was zu beweisen war.

Zum Beweisschritt 1: Wir werden den folgenden Hilfssatz jetzt (noch nicht) beweisen, da er einige sehr "technische" Hilfsmittel erfordert, sondern den beweis im Anhang des Buches führen. Hier ist es wichtiger, die Stellung dieses wichtigen Ergebnisses im Kontext des Vollständigkeitsbeweises zu verstehen.

Hilfssatz. Für jede konsistente Menge $\Psi$ von Aussagen gibt es ein Modell; d.h. eine Interpretation ${\mathfrak {I}}=\left({\mathfrak {i,U}}\right))$, die alle Aussagen von $\Psi$ wahr macht.

Der Beweisschritt 1 ergibt sich nun aus dem Hilfssatz wie folgt: Sei $\Psi =\Phi \cup {C(p)}$ im Gegensatz zur Folgerung im Beweisschritt 1 konsistent. Nach dem Hilfssatz gibt es dann ein Modell für $\Psi$, d.h eine Interpretation ${\mathfrak {I}}=\left({\mathfrak {i,U}}\right))$, die sowhl alle Aussagen von $\Phi$ als auch $C(p)$ wahr macht; d.h. ${\mathfrak {I}}$ interpretiert $\Phi$ als wahr, aber $p$ als falsch. Daher ist $\Phi \models p$ nicht richtig im Gegensatz zur Annahme von Beweisschritt 1.