Benutzer:Jürgen-Michael Glubrecht/Aussagenlogik

Vollständigkeit der Aussagenlogik

Die Korrektheit des Kalküls besagt, dass nur gültige Sequenzen abgeleitet werden können. Von grosser Bedeutung ist, dass auf diese Weise alle logischen Folgerungen abgeleitet werden können! Es gilt also auch die Umkehrung der Korrektheit:

Das Ableiten ist ein maschinell prüfbares Verfahren, das in endlich vielen Schritten aus endlich vielen Formeln eine korrekte Folgerung erzeugt. Das ist genau das, was in der Mathematik als Beweis gilt. Der Satz besagt also, dass sich alle logischen Folgerungen auf diese Weise beweisen lassen.

Wir beweisen den Satz nach einer Idee des amerikanischen Logikers Leon Henkin. Dazu nehmen wir an, dass $\Gamma \nvdash \Delta$ gilt und konstruieren ein Bewertung ${\mathcal {J}}$, die $\Gamma \nvDash \Delta$ zeigt: ${\mathcal {J}}$ macht also alle Formeln aus $\Gamma$ wahr und alle Formeln aus $\Delta$ falsch. Wir vergrössern $\Gamma$ und $\Delta$ zu $\Gamma ^{*}$ und $\Delta ^{*}$, so dass diese maximal sind aber weiterhin $\Gamma ^{*}\nvdash \Delta ^{*}$ gilt. Mit diesen Formelmengen wird dann die Bewertung definiert.

Beweis:

Wir zeigen die Kontraposition. Sei also $\Gamma \nvdash \Delta$, d.h. aus $\Gamma$ ist $\Delta$ nicht ableitbar, und $\kappa$ die Mächtigkeit der Sprache. Weiterhin sei $\phi _{i}$ mit $i\leq \kappa$ eine Aufzählung aller Formeln. Wir definieren rekursiv $\Gamma _{i}$ und $\Delta _{i}$ für $i\leq \kappa$.

• $\Gamma _{0}:=\Gamma$ und $\Delta _{0}:=\Delta$.
• Für Limeszahlen $\lambda$ sei: $\Gamma _{\lambda }:=\bigcup \{\Gamma _{i}\,|\,i<\lambda \}$ und $\Delta _{i}:=\bigcup \{\Delta _{i}\,|\,i<\lambda \}$.
• Für Nachfolgerzahlen $i+1$ werden drei Fälle unterschieden:
  
  • wenn $\Gamma _{i},\phi _{i}\nvdash \Delta _{i}$, dann $\Gamma _{i+1}:=\Gamma _{i}\cup \{\phi _{i}\}$ und $\Delta _{i+1}:=\Delta _{i}$
  • wenn $\Gamma _{i},\phi _{i}\vdash \Delta _{i}$ und $\Gamma _{i}\nvdash \phi _{i},\Delta$, dann $\Gamma _{i+1}:=\Gamma _{i}$ und $\Delta _{i+1}:=\Delta _{i}\cup \{\phi _{i}\}$
  • wenn $\Gamma _{i},\phi _{i}\vdash \Delta _{i}$ und $\Gamma _{i}\vdash \phi _{i},\Delta$, dann $\Gamma _{i+1}:=\Gamma _{i}$ und $\Delta _{i+1}:=\Delta _{i}$

Wir werden später sehen, dass der letzte Fall nicht auftritt und setzen nun: $\Gamma ^{*}:=\Gamma _{\kappa }$ und $\Delta ^{*}:=\Delta _{\kappa }$

Beweis: Durch Induktion über $\kappa$ folgt: $\Gamma _{i}\nvdash \Delta _{i}$ für alle $i\leq \kappa$. Für $i=0$ gilt das nach Voraussetzung undfür Nachfolgerzahlen nach Konstruktion. Gälte für Limeszahlen $\Gamma _{\lambda }\vdash \Delta _{\lambda }$, dann gälte $\Gamma _{i}\vdash \Delta _{i}$ für ein $i<\lambda$, denn für die Ableitung werden nur endlich viele Formeln aus $\Gamma _{\lambda }$ und $\Delta _{\lambda }$ benötigt. Das widerspricht aber der Induktionsvoraussetzung für $\lambda$.

Insbesondere gilt also $\Gamma _{\kappa }=\Gamma ^{*}\nvdash \Delta ^{*}=\Delta _{\kappa }$.✔

Beweis: Die eine Richtung ($\Rightarrow$) folgt mit der Nichtableitbarkeit nach Lemma 1.

Sei $\phi \notin \Gamma ^{*}$ und $i$ der Index von $\phi$ in der Aufzählung aller Formeln. Dann ist $\Gamma _{i},\phi \vdash \Delta _{i}$, sonst wäre $\phi \in \Gamma _{i+1}\subseteq \Gamma ^{*}$. Also gilt $\Gamma ^{*},\phi \vdash \Delta ^{*}$.

Sei nun $\phi \notin \Delta ^{*}$. Ist $\phi \in \Gamma ^{*}$, dann folgt mit der Annahmenregel $\Gamma ^{*}\vdash \phi ,\Delta ^{*}$. Sei also $\phi \notin \Gamma ^{*}$ und $i$ der Index von $\phi$. Dann ist $\Gamma _{i},\phi \vdash \Delta _{i}$ und $\Gamma _{i}\vdash \phi ,\Delta _{i}$, sonst wäre $\phi \in \Delta _{i+1}\subseteq \Delta ^{*}$. Also gilt auch in diesem Fall $\Gamma ^{*}\vdash \phi ,\Delta ^{*}$. ✔

Beweis:

1. folgt mit der Annahmenregel und Lemma 1.
2. ergibt sich mit den Regeln für Verum und Falsum, sowie Lemma 1.
3. Sei $\phi \notin \Delta ^{*}$. Mit Lemma 2 folgt $\Gamma ^{*}\vdash \phi ,\Delta ^{*}$ und mit der Linken Negationsregel $\Gamma ^{*},\neg \phi \vdash \Delta ^{*}$. Erneut mit Lemma 2 folgt $\neg \phi \notin \Gamma ^{*}$.
4. Sei $\phi \notin \Gamma ^{*}$. Mit Lemma 2 folgt $\Gamma ^{*},\phi \vdash \Delta ^{*}$ und mit der Rechten Negationsregel $\Gamma ^{*}\vdash \neg \phi ,\Delta ^{*}$. Erneut mit Lemma 2 folgt $\neg \phi \notin \Delta ^{*}$.
5. Sei $\phi \notin \Gamma ^{*}$ oder $\psi \notin \Gamma ^{*}$. Mit Lemma 2 folgt $\Gamma ^{*},\phi \vdash \Delta ^{*}$ oder $\Gamma ^{*},\psi \vdash \Delta ^{*}$, also mit Verdünnung auch $\Gamma ^{*},\phi ,\psi \vdash \Delta ^{*}$. Mit der Linken Konjunktionsregel folgt $\Gamma ^{*},\phi \land \psi \vdash \Delta ^{*}$ und wieder mit Lemma 2: $\phi \land \psi \notin \Gamma ^{*}$.
6. Sei $\phi \notin \Delta ^{*}$ und $\psi \notin \Delta ^{*}$. Mit Lemma 2 folgt $\Gamma ^{*}\vdash \phi ,\Delta ^{*}$ und $\Gamma ^{*}\vdash \psi ,\Delta ^{*}$. Mit der Rechten Konjunktionsregel folgt $\Gamma ^{*}\vdash \psi \land \psi ,\Delta ^{*}$ und erneut mit Lemma 2: $\phi \lor \psi \notin \Delta ^{*}$.
7. Sei $\phi \notin \Gamma ^{*}$ und $\psi \notin \Gamma ^{*}$. Mit Lemma 2 folgt $\Gamma ^{*},\phi \vdash \Delta ^{*}$ und $\Gamma ^{*},\psi \vdash \Delta ^{*}$. Mit der Linken Disjunktionsregel folgt $\Gamma ^{*},\phi \lor \psi \vdash \Delta ^{*}$ und mit Lemma 2; $\phi \lor \psi \notin \Gamma ^{*}$.
8. Sei $\phi \notin \Delta ^{*}$ oder $\psi \notin \Delta ^{*}$. Mit Lemma 2 folgt $\Gamma ^{*}\vdash \phi ,\Delta ^{*}$ oder $\Gamma ^{*}\vdash \psi ,\Delta ^{*}$ und mit Verdünnng $\Gamma ^{*}\vdash \phi ,\psi ,\Delta ^{*}$. Mit der Rechten Disjunktionsregel folgt $\Gamma ^{*}\vdash \phi \lor \psi ,\Delta ^{*}$ und mit Lemma 2: $\phi \lor \psi \notin \Delta ^{*}$.

Damit ist der Beweis beendet. ✔

Die eben gezeigten Eigenschaften reichen aus, um eine Bewertung ${\mathcal {J^{*}}}$ zu definieren, die $\Gamma ^{*}\nvDash \Delta ^{*}$ beweist:.

Definition der Bewertung ${\mathcal {J^{*}}}$:

Für alle Aussagenkonstanten $\alpha$ sei ${\mathcal {J^{*}}}(\alpha )$ Wahr genau dann, wenn $\alpha \in \Gamma ^{*}$.

Beweis durch Induktion über den Aufbau der Formeln:

• Für Aussagenkonstanten gilt die Behauptung nach Definition von ${\mathcal {J^{*}}}$.
• Für Verum und Falsum gilt die Behauptung wegen Lemma 3 Punkt 2.
• Gelte $\neg \phi \in \Gamma ^{*}$. Dann gilt nach Lemma 3 Punkt 3. $\phi \in \Delta ^{*}$ und nach Induktionsvoraussetzung ist ${\mathcal {J^{*}}}(\phi )$ Falsch. Also ist ${\mathcal {J^{*}}}(\neg \phi )$ Wahr.
  Ist $\neg \phi \in \Delta ^{*}$, ist nach Lemma 3 Punkt 4. $\phi \in \Gamma ^{*}$ und somit ${\mathcal {J^{*}}}(\phi )$ Wahr. Also ist ${\mathcal {J^{*}}}(\neg \phi )$ Falsch.
• Gelte $\phi \land \psi \in \Gamma ^{*}$. Nach Lemma 3 Punkt 5. und Induktionsvorraussetzung sind dann ${\mathcal {J^{*}}}(\phi )$ Wahr und ${\mathcal {J^{*}}}(\psi )$ Wahr. Also ist auch ${\mathcal {J^{*}}}(\phi \land \psi )$ Wahr.
  Ist $\phi \land \psi \in \Delta ^{*}$, ist nach Lemma 3 Punkt 6. und der Induktionsvoraussetzung ${\mathcal {J^{*}}}(\phi )$ Falsch oder ${\mathcal {J^{*}}}(\psi )$ Falsch. Damit ist auch ${\mathcal {J^{*}}}(\phi \land \psi )$ Wahr.
• Gelte $\phi \lor \psi \in \Gamma ^{*}$. Nach Lemma 3 Punkt 7. und Induktionsvorraussetzung ist dann ${\mathcal {J^{*}}}(\phi )$ Wahr oder ${\mathcal {J^{*}}}(\psi )$ Wahr. Also ist auch ${\mathcal {J^{*}}}(\phi \lor \psi )$ Wahr.
  Ist $\phi \lor \psi \in \Delta ^{*}$, sind nach Lemma 3 Punkt 8. und der Induktionsvoraussetzung ${\mathcal {J^{*}}}(\phi )$ Falsch und ${\mathcal {J^{*}}}(\psi )$ Falsch. Daher ist auch ${\mathcal {J^{*}}}(\phi \lor \psi )$ Falsch.

Damit ist Lemma 4 bewiesen. ✔

Da ja $\Gamma \subseteq \Gamma ^{*}$ und $\Delta \subseteq \Delta ^{*}$ gilt auch:

Zusammen mit der Korrektheit des Kalküls gilt also: