Logik/Vollständigkeitssatz/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

Γ ⊢ p

die Folgerungsbeziehung

Γ ⊨ 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.

Der Satz von Henkin

Definition

Eine Menge $Γ$ an $S$ -Ausdrücken (über einem Symbolalphabet $S$ ) heißt maximal widerspruchsfrei, wenn sie widerspruchsfrei ist und wenn jede Hinzunahme eines jeden Ausdrucks $α \notin Γ$ die Menge widersprüchlich macht.

Definition

Man sagt, dass eine Menge $Γ$ an $S$ -Ausdrücken (über einem Symbolalphabet $S$ ) Beispiele enthält, wenn es für jeden Ausdruck der Form $\exists x α$ einen $S$ -Term $t$ derart gibt, dass

\exists x α \to α \frac{t}{x}

zu $Γ$ gehört.

Diese beiden Begriffe sind durch folgende Aussage motiviert.

Lemma

Es sei $S$ ein Symbolalphabet und $I$ eine $S$ -Interpretation auf einer Menge $M$ , wobei die Terminterpretation surjektiv sei.

Dann ist die Gültigkeitsmenge $Γ = I^{⊨}$ maximal widerspruchsfrei und enthält Beispiele.

Beweis

Zunächst ist $Γ = I^{⊨}$ aufgrund des Korrektheitssatzes abgeschlossen unter Ableitungen. Für jeden $S$ -Ausdruck $α$ gilt die Alternative: Entweder $α \in Γ$ oder $\neg α \in Γ$ . Insbesondere ist $Γ$ widerspruchsfrei. Wenn $α \notin Γ$ ist, so ist $\neg α \in Γ$ und daher ist $Γ \cup {α}$ widersprüchlich. Also ist $Γ$ maximal widerspruchsfrei.
Wir betrachten nun einen Ausdruck der Form $α = \exists x β$ . Wenn $α \notin Γ$ gilt, so gilt $\exists x β \to β \frac{t}{x}$ in $I$ für jeden Term $t$ , da ja der Vordersatz nicht gilt. Wenn hingegen $α \in Γ$ gilt, so gibt es aufgrund des semantischen Aufbaus der Gültigkeitbeziehung ein $m \in M$ derart, dass $I \frac{m}{x} ⊨ β$ gilt. Wegen der vorausgesetzten Surjektivität der Belegung gibt es einen Term $t$ , der durch $m$ interpretiert wird. Daher gilt nach dem Substitutionslemma $β \frac{t}{x}$ in $I$ . Also gilt $\exists x β \to β \frac{t}{x}$ in $I$ .

◻

Lemma

Es sei $Γ$ eine Menge an $S$ -Ausdrücken (über einem Symbolalphabet $S$ ), die maximal widerspruchsfrei ist. Dann gelten folgende Eigenschaften.

Für jeden Ausdruck $α$ ist entweder $α \in Γ$ oder $\neg α \in Γ$ .

Aus $Γ ⊢ α$ folgt $α \in Γ$ , d.h. $Γ$ ist abgeschlossen unter Ableitungen.

Für Ausdrücke $α, β$ ist $α \land β \in Γ$ genau dann, wenn $α \in Γ$ und $β \in Γ$ ist.

Beweis

(1). Wegen der Widerspruchsfreiheit kann nicht sowohl $α$ als auch $\neg α$ zu $Γ$ gehören. Wenn weder $α$ noch $\neg α$ zu $Γ$ gehören, so ist entweder $Γ \cup {α}$ oder $Γ \cup {\neg α}$ widerspruchsfrei. Wären nämlich beide widersprüchlich, so würde für einen beliebigen Ausdruck $β$ sowohl

Γ \cup {α} ⊢ β

als auch

Γ \cup {\neg α} ⊢ β

gelten. Dies bedeutet

Γ ⊢ α \to β

und

Γ ⊢ \neg α \to β,

woraus aufgrund der Fallunterscheidungsregel

Γ ⊢ β

folgt. Dies bedeutet aber, dass $Γ$ widersprüchlich ist.
(2). Es sei $Γ ⊢ α$ . Nach (1) ist $α \in Γ$ oder $\neg α \in Γ$ . Das zweite kann nicht sein, da sich daraus sofort ein Widerspruch ergeben würde. Also ist $α \in Γ$ .
(3). Die Richtung von links nach rechts folgt aus (2). Es seien also $α, β \in Γ$ . Da $α \to (β \to α \land β)$ nach Aufgabe eine Tautologie ist, folgt $α \land β \in Γ$ nach Teil (2).

◻

Wir werden nun umgekehrt zu Fakt zeigen, dass man zu einer jeden maximal widerspruchsfreien Ausdrucksmenge $Γ$ , die Beispiele enthält, eine Interpretation konstruieren kann, deren Gültigkeitsmenge mit $Γ$ übereinstimmt. Diese Konstruktion, die wir die kanonische Termidentifizierung nennen, geht folgendermaßen.

Konstruktion

Es sei $Γ$ eine Menge an $S$ -Ausdrücken (über einem Symbolalphabet $S$ ), die abgeschlossen unter Ableitungen ist. Dann definiert man auf der Menge aller $S$ -Terme eine Äquivalenzrelation durch

t \sim s genau dann, wenn der Ausdruck t = s zu Γ gehört .

Es sei $M$ die Menge der Termklassen (also die Menge der Äquivalenzklassen zu dieser Äquivalenzrelation). Auf $M$ definiert man für jedes $n$ -stellige Relationssymbol $R$ eine $n$ -stellige Relation $R^{M}$ durch

R^{M} ([t_{1}], [t_{2}], \dots, [t_{n}]) genau dann, wenn der Ausdruck R t_{1} t_{2} \dots t_{n} zu Γ gehört

und für jedes $n$ -stellige Funktionssymbol $f$ eine $n$ -stellige Funktion $f^{M}$ durch

f^{M} ([t_{1}], [t_{2}], \dots, [t_{n}]) := [f t_{1} t_{2} \dots t_{n}] .

Konstanten werden als

c^{M} := [c]

interpretiert.

Wir müssen natürlich zunächst zeigen, dass wirklich eine Äquivalenzrelation vorliegt und dass die Relationen und Funktionen wohldefiniert sind.

Lemma

Es sei $Γ$ eine Menge an $S$ -Ausdrücken (über einem Symbolalphabet $S$ ), die abgeschlossen unter Ableitungen ist.

Dann liefert die in Fakt beschriebene Konstruktion eine Äquivalenzrelation auf der Menge aller Terme und wohldefinierte Relationen bzw. Funktionen auf der Menge der Termklassen.

Beweis

Eine Äquivalenzrelation liegt aufgrund von Axiom (1) und Fakt (1), (2) vor, da ja $Γ$ nach Voraussetzung abgeschlossen unter Ableitungen ist und insbesondere alle syntaktischen Tautologien enthält.

Es sei $M$ die Menge der Äquivalenzklassen, die wir in diesem Zusammenhang Termklassen nennen. Es sei $R$ ein $n$ -stelliges Relationssymbol. Es sei $([s_{1}], \dots, [s_{n}])$ ein $n$ -Tupel aus Termklassen, die einerseits durch das Termtupel $(s_{1}, \dots, s_{n})$ und andererseits durch das Termtupel $(t_{1}, \dots, t_{n})$ repräsentiert werde. Es gilt also $s_{i} \sim t_{i}$ bzw. $s_{i} = t_{i} \in Γ$ . Wenn nun $R s_{1} \dots s_{n}$ zu $Γ$ gehört, so folgt aus Fakt (4) auch $R t_{1} \dots t_{n} \in Γ$ . Unter den gleichen Voraussetzungen folgt mit Fakt (3) die Zugehörigkeit $f s_{1} \dots s_{n} = f t_{1} \dots t_{n} \in Γ$ und somit

[f s_{1} \dots s_{n}] = [f t_{1} \dots t_{n}],

also die Wohldefiniertheit der Funktion.

◻

Lemma

Es sei $Γ$ eine Menge an $S$ -Ausdrücken (über einem Symbolalphabet $S$ ), die abgeschlossen unter Ableitungen ist.

Dann gilt für die Interpretation $(M, β)$ , wobei $M$ die in Fakt beschriebene Menge aus Termklassen (mit der natürlichen Interpretation $I$ von Konstanten, Funktionssymbolen und Relationssymbolen) und $β$ die natürliche Belegung $β (x) = [x]$ für Variablen ist, die Beziehung

$I (t) = [t]$

für alle Terme $t$ .

Beweis

Wir führen Induktion über den Aufbau der Terme, wobei der Induktionsanfang unmittelbar durch die natürliche Belegung gesichert ist. Die Aussage gelte nun für Terme $t_{1}, \dots, t_{n}$ und $f$ sei ein $n$ -stelliges Funktionssymbol. Dann ist

I (f t_{1} \dots t_{n}) = f^{M} (I (t_{1}), \dots, I (t_{n})) = f^{M} ([t_{1}], \dots, [t_{n}]) = [f t_{1} \dots t_{n}] .

◻

Die folgende Aussage heißt Satz von Henkin . Er wird durch Induktion über den sogenannten Rang eines Ausdrucks bewiesen.

Satz

Es sei $Γ$ eine Menge an $S$ -Ausdrücken (über einem Symbolalphabet $S$ ), die maximal widerspruchsfrei ist und Beispiele enthält.

Dann ist die in Fakt gegebene Interpretation ein Modell für $Γ$ .

Insbesondere ist $Γ$ erfüllbar.

Beweis

Es sei $M$ das konstruierte Modell zu $Γ$ und $I$ die zugehörige Interpretation mit der natürlichen Belegung für die Variablen. Wir zeigen die Äquivalenz

α \in Γ genau dann, wenn I ⊨ α

für alle Ausdrücke $α$ , durch Induktion über den Rang der Ausdrücke. Zum Induktionsanfang sei der Rang von $α$ gleich $0$ , also $α$ atomar. D.h. $α$ ist entweder von der Form $s = t$ oder $R t_{1} \dots t_{n}$ . Im ersten Fall ist $s = t \in Γ$ äquivalent zu $s \sim t$ bzw. $[s] = [t]$ in $M$ . Dies ist nach Fakt äquivalent zu $I (s) = I (t)$ und das bedeutet $I ⊨ s = t$ .

Im zweiten Fall ist $R t_{1} \dots t_{n} \in Γ$ - nach Konstruktion von $M$ und $R^{M}$ - äquivalent zu $R^{M} ([t_{1}], \dots, [t_{n}])$ , und dies ist äquivalent zu $I ⊨ R t_{1} \dots t_{n}$ .

Es sei nun die Aussage für alle Ausdrücke vom Rang $\leq r$ bewiesen und sei $α$ ein Ausdruck vom Rang $r + 1$ . Wir betrachten die mögliche Struktur von $α$ gemäß Definition. Bei

α = \neg β

ergibt sich die Äquivalenz aus der Induktionsvoraussetzung ( $β$ hat kleineren Rang als $α$ ) und Fakt (1). Bei

α = β_{1} \land β_{2}

besitzen die beiden Bestandteile kleineren Rang als $α$ . Die Zugehörigkeit $α \in Γ$ ist nach Fakt (3) äquivalent zur gemeinsamen Zugehörigkeit $β_{1}, β_{2} \in Γ$ . Nach Induktionsvoraussetzung bedeutet dies $I ⊨ β_{1}$ und $I ⊨ β_{2}$ . Dies bedeutet wiederum $I ⊨ β_{1} \land β_{2}$ aufgrund der Modellbeziehung. Bei

α = \exists x β

besitzt wieder $β$ einen kleineren Rang. Die Zugehörigkeit $α \in Γ$ ist aufgrund der Eigenschaft, Beispiele zu enthalten und aufgrund von Axiom äquivalent zur Existenz eines Terms $t$ und der Zugehörigkeit $β \frac{t}{x} \in Γ$ . Die Substitution von $β$ nach $β \frac{t}{x}$ verändert nach Aufgabe nicht den Rang. Wir können also auf $β \frac{t}{x}$ die Induktionsvoraussetzung anwenden und erhalten die Äquivalenz zu $I ⊨ β \frac{t}{x}$ . Nach dem Substitutionslemma ist dies äquivalent zu $I \frac{I (t)}{x} ⊨ β$ bzw. $I \frac{[t]}{x} ⊨ β$ wegen Fakt. Dies ist äquivalent zu $I ⊨ \exists x β$ aufgrund der Modellbeziehung und der Surjektivität der Termabbildung.

◻

Auffüllungsstrategien

Die Strategie ist nun, eine widerspruchsfreie Ausdrucksmenge zu einer maximal widerspruchsfreien Ausdrucksmenge, die Beispiele enthält, aufzufüllen, und so ein erfüllenden Modell zu bekommen. Dabei betrachten wir zunächst das Problem, Beispiele hinzuzunehmen. Es sei $Γ$ eine widerspruchsfreie Ausdrucksmenge über dem Alphabet $S$ . Zu jedem Ausdruck $φ$ müssen wir einen Ausdruck der Form $\exists φ \to \frac{t}{x}$ mit einem gewissen Term $t$ hinzunehmen. Das Problem ist hierbei, dass bei ungeeigneter Wahl von $t$ die Hinzunahme dieses Ausdrucks $Γ$ widersprüchlich machen könnte. Es gibt keine Garantie, dass es überhaupt einen $S$ -Term $t$ gibt, mit dem man $Γ$ widerspruchsfrei erweitern kann. Von daher wählt man eine andere Strategie, indem man simultan das Symbolalphabet erweitert und den hinzuzunehmenden Existenzausdruck mit einem neuen „unbelasteten“ Term ansetzt.

Lemma

Es sei $Γ$ eine widerspruchsfreie Menge an $S$ -Ausdrücken (über einem Symbolalphabet $S$ ).

Dann gibt es eine Symbolerweiterung $S^{*} \supseteq S$ und eine widerspruchsfreie $S^{*}$ -Ausdrucksmenge $Γ^{*} \supseteq Γ$ derart, dass es zu jedem Ausdruck $\exists x α \in L^{S}$ einen Term $t$ (über $S^{*}$ ) derart gibt, dass

$\exists x α \to α \frac{t}{x} \in Γ^{*}$

gilt.

Beweis

Die Menge $S^{*}$ definieren wir als disjunkte Vereinigung

S^{*} = S \cup V,

wobei $V$ eine Variablenmenge ist, die für jeden Ausdruck der Form $\exists x α \in L^{S}$ genau eine (neue) Variable enthält, die wir mit $y_{\exists x α}$ bezeichnen. Wir setzen

Γ^{*} = Γ \cup {\exists x α \to α \frac{y_{\exists x α}}{x} ∣ \exists x α \in L^{S}} .

Daher ist $Γ \subseteq Γ^{*}$ und $Γ^{*}$ enthält $S$ -Beispiele. Es bleibt also die Widerspruchsfreiheit zu zeigen. Wäre $Γ^{*}$ widerspruchsvoll, so wäre auch eine endliche Teilmenge davon widerspruchsvoll und insbesondere würde es Ausdrücke $α_{1}, \dots, α_{n} \in L^{S}$ derart geben, dass

Γ \cup {\exists x_{1} α_{1} \to α_{1} \frac{y_{\exists x_{1} α_{1}}}{x_{1}}} \cup \dots \cup {\exists x_{n} α_{n} \to α_{n} \frac{y_{\exists x_{n} α_{n}}}{x_{n}}}

widersprüchlich ist (dabei können die $x_{i}$ gleich oder verschieden sein). Da bei jeder Hinzunahme eine neue Variable $y_{\exists x_{n} α_{n}}$ verwendet wird, können wir induktiv Fakt anwenden und erhalten die Widersprüchlichkeit von $Γ$ .

◻

Lemma

Es sei $Γ$ eine widerspruchsfreie Menge an $S$ -Ausdrücken (über einem Symbolalphabet $S$ ).

Dann gibt es eine aufsteigende Folge von Symbolmengen

$S_{n} \subseteq S_{n + 1} mit S_{0} = S$

und eine Folge von aufsteigenden $S_{n}$ -Ausdrucksmengen

$Γ_{n} \subseteq Γ_{n + 1} mit Γ_{0} = Γ$

derart, dass zum Symbolalphabet $S^{'} = ⋃_{n \in ℕ} S_{n}$ die $S^{'}$ -Ausdrucksmenge

$Γ^{'} = ⋃_{n \in ℕ} Γ_{n}$

widerspruchsfrei ist und Beispiele enthält.

Beweis

Wir konstruieren die Folgen $S_{n}$ und $Γ_{n}$ sukzessive mit der in Fakt beschriebenen Methode durch

S_{n + 1} = (S_{n})^{*}

und

Γ_{n + 1} = (Γ_{n})^{*} .

Wäre $Γ^{'}$ widersprüchlich, so würde sich schon aus einer endlichen Teilmenge ein Widerspruch ergeben. Dann wäre schon eines der $Γ_{n}$ widersprüchlich im Widerspruch zu Fakt.

◻

Exkurs zum Zornschen Lemma.

Lemma

Es sei $Γ$ eine widerspruchsfreie Menge an $S$ -Ausdrücken (über einem Symbolalphabet $S$ ).

Dann gibt es eine maximal widerspruchsfreie $S$ -Menge $Γ^{'}$ mit $Γ \subseteq Γ^{'}$ .

Beweis

Wir betrachten die Menge

M = {Δ ∣ Γ \subseteq Δ \subseteq L^{S}, Δ widerspruchsfreie Ausdrucksmenge}

aller widerspruchsfreien $S$ -Ausdrucksmengen oberhalb von $Γ$ . Es ist $Γ \in M$ . Es sei $N \subseteq M$ eine nichtleere total geordnete Teilmenge. Die Vereinigung $Δ^{'} = ⋃_{Δ \in N} Δ$ ist ebenfalls eine $S$ -Ausdrucksmenge, die $Γ$ umfasst. Sie ist auch widerspruchsfrei. Würde nämlich $Δ^{'} ⊢ \neg α \land α$ gelten, so könnte man schon aus einer endlichen Teilmenge $T \subseteq Δ^{'}$ einen Widerspruch ableiten. Die Elemente aus $T$ liegen jeweils in je einem $Δ \in N$ , und da diese eine Kette bilden, gibt es auch ein $\tilde{Δ}$ mit $T \subseteq \tilde{Δ}$ , also wäre $\tilde{Δ}$ widersprüchlich. Somit sind die Voraussetzungen im Lemma von Zorn erfüllt und daher gibt es eine maximale Menge $Γ^{'}$ in $M$ . Diese ist offenbar maximal widerspruchsfrei.

◻

Die folgende Aussage ist der Vollständigkeitssatz.

Satz

Es sei $S$ ein Symbolalphabet, $Γ$ eine Menge an $S$ -Ausdrücken und $α$ ein weiterer $S$ -Ausdruck.

Dann gilt $Γ ⊨ α$ genau dann, wenn $Γ ⊢ α$ gilt.

Beweis

Die Richtung von rechts nach links ist der Korrektheitssatz. Es sei umgekehrt $Γ ⊬ α$ . Um zu zeigen, dass auch $Γ ⊭ α$ gilt, müssen wir ein Modell angeben, das $Γ$ erfüllt, aber nicht $α$ . Die Nichtableitbarkeit $Γ ⊬ α$ bedeutet, dass $Γ \cup {\neg α}$ widerspruchsfrei ist, und wir müssen zeigen, dass $Γ \cup {\neg α}$ erfüllbar ist. Nach Fakt gibt es eine widerspruchsfreie Erweiterung $S \subseteq S^{'}$ des Symbolalphabets und eine Erweiterung $Γ^{'}$ von $Γ \cup {\neg α}$ , die Beispiele enthält. Nach Fakt gibt es eine maximal widerspruchsfreie $S^{'}$ -Ausdrucksmenge $Γ^{''} \supseteq Γ^{'}$ . Diese enthält mit $Γ^{'}$ ebenfalls Beispiele. Nach dem Satz von Henkin gibt es eine $S^{'}$ -Interpretation, die $Γ^{''}$ erfüllt. Diese Interpretation erfüllt erst recht $Γ \cup {\neg α}$ .

◻

Das folgende Korollar, der sogenannte Endlichkeitssatz, demonstriert, dass der Vollständigkeitssatz keineswegs selbstverständlich ist. Es sei eine Folgerungsbeziehung $Γ ⊨ p$ bewiesen, also gezeigt, dass jede Interpretation, die $Γ$ erfüllt, auch $p$ erfüllen muss. Dabei sei $Γ$ unendlich, man denke etwa an ein unendliches Axiomenschema, wie es im Induktionsschema der einstufigen 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, $Γ$ eine Menge an $S$ -Ausdrücken und $α$ ein weiterer $S$ -Ausdruck.

Dann gilt $Γ ⊨ α$ genau dann, wenn es eine endliche Teilmenge $Γ_{e} \subseteq Γ$ gibt mit $Γ_{e} ⊨ α$ .

Beweis

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

◻

Korollar

Es sei $S$ ein Symbolalphabet und $Γ$ eine Menge an $S$ -Ausdrücken. Es sei jede endliche Teilmenge $Γ_{e} \subseteq Γ$ erfüllbar.

Dann ist $Γ$ erfüllbar.

Beweis

Dies folgt aus Fakt. Für die Widerspruchsfreiheit ist die Aussage klar, da eine Ableitung eines Widerspruchs nur Bezug auf endlich viele Voraussetzungen nimmt.

◻