Korrektheit und Vollständigkeit

Zwei Fragen an den Kalkül des Kurses

Die Einheit über die Ableitung hat den Kalkül des Kurses festgelegt: die Axiomenschemata A1, A2 und A3 von Łukasiewicz und zwei Regeln, den Modus ponens (MP) und die Ersetzung der doppelten Negation (EDN), die die Lektion über die vier Ableitungstechniken hinzugefügt hat, nachdem sie die doppelte Negation bewiesen hatte. Eine Ableitung aus einer Menge $\Gamma$ ist eine endliche Folge von Formeln, in der jede ein Axiom ist, ein Element von $\Gamma$, das Ergebnis des Modus ponens, angewandt auf zwei frühere Formeln, oder das Ergebnis von EDN, angewandt auf eine frühere; $\Gamma \vdash \varphi$ bedeutet, dass es eine Ableitung aus $\Gamma$ gibt, deren letzte Formel $\varphi$ ist. Die Einheit über die Semantik ihrerseits hat in der Lektion über semantische Folgerung und Äquivalenz die Relation $\Gamma \models \varphi$ definiert: Jede Belegung, die alle Formeln von $\Gamma$ erfüllt, erfüllt $\varphi$. Beide Relationen werden nach demselben Muster geschrieben, eine Menge links und eine Formel rechts; ihre Natur ist jedoch entgegengesetzt. Die erste ist syntaktisch und existenziell: Sie behauptet, dass es ein endliches Objekt gibt, eine Ableitung, das sich Zeichen für Zeichen prüfen lässt. Die zweite ist semantisch und universell: Sie behauptet etwas über alle Belegungen, deren es unendlich viele gibt und von denen jede unendlich vielen Variablen einen Wert gibt.

Zwei Fragen stellen sich daher an den Kalkül. Die erste: Leitet er nur ab, was er soll? Der Kalkül heißt korrekt, wenn für jede Menge $\Gamma$ und jede Formel $\varphi$ aus $\Gamma \vdash \varphi$ folgt, dass $\Gamma \models \varphi$: Was aus gegebenen Prämissen abgeleitet wird, ist unter jeder Belegung wahr, die die Prämissen wahr macht. Die zweite: Leitet er alles ab, was er soll? Der Kalkül heißt vollständig, wenn aus $\Gamma \models \varphi$ folgt, dass $\Gamma \vdash \varphi$. Die Vollständigkeit lässt drei Grade zu, je nach den Prämissenmengen, die sie umfasst:

• schwache Vollständigkeit: Wenn $\models \varphi$, dann $\vdash \varphi$; jede Tautologie ist ein Theorem;
• Vollständigkeit für endliche Prämissenmengen: Wenn $\{\gamma_{1}, \ldots, \gamma_{k}\} \models \varphi$, dann $\{\gamma_{1}, \ldots, \gamma_{k}\} \vdash \varphi$;
• starke Vollständigkeit: Wenn $\Gamma \models \varphi$, dann $\Gamma \vdash \varphi$, für eine beliebige Menge $\Gamma$, auch eine unendliche.

Diese Lektion beweist die Korrektheit und die beiden ersten Grade der Vollständigkeit. Der dritte wird in der Lektion über den Kompaktheitssatz bewiesen, und der Grund für diese Aufteilung wird am Ende der Lektion erklärt.

Was man nicht sagen sollte

Im Spanischen nennt man die Korrektheit mitunter „solvencia“, eine Lehnübersetzung des englischen soundness; der spanische Ausdruck ist „corrección“, und ihn verwendet der Kurs auf Spanisch. Ebenso wenig darf man sie als die Eigenschaft des Kalküls definieren, „einen Ausdruck aus einer Menge von Ausdrücken zu erschließen“, denn das ist die Ableitbarkeit selbst und keine Eigenschaft des Kalküls. Die sachlichen Fehler sind jedoch zwei andere.

Der erste besteht in der Behauptung, Korrektheit und Vollständigkeit „ließen sich auseinander erschließen“. Sie sind unabhängige Eigenschaften: Der Łukasiewicz-Kalkül ohne die Regel EDN ist korrekt (der Beweis dieser Lektion zeigt es, wenn man einen Fall streicht) und nicht vollständig (die Lektion über formale Deduktionssysteme hat eine Tautologie vorgeführt, die er nicht ableitet); und ein Kalkül, der alle Formeln als Axiome annähme, wäre vollständig, ohne korrekt zu sein. Die gelöste Aufgabe 2 untersucht beide Beispiele.

Der zweite Fehler ist schwerer, weil er ein zirkuläres Argument als Beweis der Vollständigkeit ausgibt. Er lautet im Kern: Wenn $\varphi \nvdash \psi$, dann nach dem Deduktionstheorem $\nvdash (\varphi \rightarrow \psi)$; „nach der Korrektheit“ $\not\models (\varphi \rightarrow \psi)$; und nach dem semantischen Deduktionstheorem $\varphi \not\models \psi$. Nun besagt die Korrektheit, dass das Ableitbare allgemeingültig ist, und ihre Kontraposition, dass das nicht Allgemeingültige nicht ableitbar ist:

Der Schritt des Arguments geht in die andere Richtung, von $\nvdash \chi$ zu $\not\models \chi$, und das ist die Kontraposition von $\models \chi \Rightarrow \vdash \chi$, also der schwachen Vollständigkeit. Wenn dem so ist, setzt das Argument voraus, was es beweisen will. Daraus folgt, dass sich die Vollständigkeit nicht „auf einfache Weise erschließen“ lässt: Sie ist das tiefste Ergebnis des Kurses, und ihr Beweis nimmt den größten Teil dieser Lektion ein. Schließlich ist es ungenau, die Vollständigkeit mit den Worten zusammenzufassen, „alle wahren Ausdrücke haben einen Beweis“; einen Beweis hat das Allgemeingültige, das unter jeder Belegung wahr ist, nicht das unter irgendeiner Wahre: Die Variable $v_{1}$ ist unter vielen Belegungen wahr und ist kein Theorem.