Prädikatenlogik/Vollständigkeitssatz/Erläuterung/Beweisandeutung/Textabschnitt

Im Laufe der Einführung des syntaktischen Prädikatenkalküls haben wir gesehen, dass die in ihm ableitbaren Ausdrücke allgemeingültig sind, dass also sämtliche durch den Prädikatenkalkül generierten formalen Tautologien auch semantische Tautologien sind. Daraus ergibt sich insbesondere, dass sich aus der Ableitbarkeitsbeziehung

$\Gamma \vdash p$

die Folgerungsbeziehung

$\Gamma \vDash p$

ergibt. Diese Aussage nennt man auch den Korrektheitssatz. Der entworfene Kalkül produziert also nur korrekte mathematische Aussagen.

Die Umkehrung ist deutlich schwieriger: Es geht um die Frage, ob der Kalkül jeden allgemeingültigen Ausdruck formal ableiten kann, ob es also für jeden mathematischen Beweis eines Ausdrucks einer Sprache erster Stufe auch einen formalen Beweis gibt. Es ist die Frage, ob der Kalkül vollständig ist. Dies ist in der Tat der Fall. Für diesen Vollständigkeitssatz, der auf Gödel zurückgeht, geben wir nur eine kurze Beweisidee.

Satz

Es sei ${}S$ ein Symbolalphabet, ${}\Gamma$ eine Menge an ${}S$-Ausdrücken und ${}\alpha$ ein weiterer ${}S$-Ausdruck.

Dann gilt ${}\Gamma \vDash \alpha$ genau dann, wenn ${}\Gamma \vdash \alpha$ gilt.

Beweis

Die Implikation von rechts nach links, dass also ein aus ${}\Gamma$ ableitbarer Ausdruck auch aus ${}\Gamma$ folgt, beruht auf der Korrektheit des Prädikatenkalküls. Die umgekehrte Richtung wird durch Kontraposition bewiesen. Es sei also ${}p$ ein Ausdruck, der nicht aus ${}\Gamma$ ableitbar ist. Man muss dann zeigen, dass er auch nicht aus ${}\Gamma$ folgt. D.h. man muss zeigen, dass es eine Interpretation ${}I$

(also insbesondere eine ${}S$-Struktur) gibt, unter der ${}\Gamma$ gilt, aber nicht ${}p$. Wegen der Unableitbarkeit kann man aus der Ausdrucksmenge ${}\Gamma \cup \{\neg p\}$ keinen Widerspruch ableiten. Daher muss man zu einer (syntaktisch) widerspruchsfreien Ausdrucksmenge ein erfüllendes Modell konstruieren. Die Grundidee dazu ist, auf der Menge der ${}S$-Terme eine Äquivalenzrelation unter Berücksichtigung der Ausdrucksmenge einzuführen und die resultierende Quotientenmenge

als Grundmenge der Struktur zu nehmen. Dahinter stecken aber einige Feinheiten, die wir hier nicht ausführen.

$\Box$

Das folgende Korollar, der sogenannte Endlichkeitssatz, demonstriert, dass der Vollständigkeitssatz keineswegs selbstverständlich ist. Es sei eine Folgerungsbeziehung ${}\Gamma \vDash p$ bewiesen, also gezeigt, dass jede Interpretation, die ${}\Gamma$ erfüllt, auch ${}p$ erfüllen muss. Dabei sei ${}\Gamma$ unendlich, man denke etwa an ein unendliches Axiomenschema, wie es im Induktionsschema der erststufigen Peano-Arithmetik vorliegt. Ist es vorstellbar, dass in einem Beweis irgendwie auf all diese unendlich vielen Voraussetzungen Bezug genommen wird?

Korollar

Es sei ${}S$ ein Symbolalphabet, ${}\Gamma$ eine Menge an ${}S$-Ausdrücken und ${}\alpha$ ein weiterer ${}S$-Ausdruck.

Dann gilt ${}\Gamma \vDash \alpha$ genau dann, wenn es eine endliche Teilmenge ${}\Gamma _{e}\subseteq \Gamma$ gibt mit ${}\Gamma _{e}\vDash \alpha$.

Beweis

Dies folgt direkt aus Fakt, da die Endlichkeitsbeziehung für das Ableiten nach Definition gilt.

$\Box$