Mathematik für Faule: Logik/Die Vollständigkeit der Deduktionsregeln

Beweis: Wir führen eine iterative Deduktion über die Komplexitätszahl der Formel durch.

6. Es sei zunächst ${\mathfrak {H}}_{\Gamma }\vDash \exists x\varphi$. Nach dem letzten Schritt gilt dann

${\mathfrak {H}}_{\Gamma }\vDash \exists x\varphi \Leftrightarrow \exists {\overline {t}}\in |{\mathfrak {H}}_{\Gamma }|:\varphi {\frac {\overline {t}}{x}}\Rightarrow \Gamma \vdash \varphi {\frac {\overline {t}}{x}}$,

und dann können wir einen Existenzquantor einführen. Umgekehrt sei $\Gamma \vdash \exists x\varphi$. Da $\Gamma$ Zeugen enthält, folgt fast sofort, dass ${\mathfrak {H}}_{\Gamma }\vDash \exists x\varphi$. $\Box$

Proposition (Konsistente Erweiterung durch unbenutzte Variablen):

Es sei $L^{S}$ eine Logiksprache, $\Gamma$ eine Menge von Sätzen in dieser Sprache, $\varphi$ ein beliebiger Satz und $z$ eine Variable, die in $\Gamma$ und $\varphi$ nicht vorkommt. Dann ist

$\Gamma \cup \left\{\exists x\varphi \rightarrow \varphi {\frac {z}{x}}\right\}$

konsistent.

Beweis: Angenommen $\Gamma \cup \left\{\exists x\varphi \rightarrow \varphi {\frac {z}{x}}\right\}$ wäre inkonsistent, also $\Gamma \cup \left\{\exists x\varphi \rightarrow \varphi {\frac {z}{x}}\right\}\vdash \bot$. Dann

und $\Gamma$ ist ebenfalls inkonsistent, im Widerspruch zur Annahme. $\Box$

Proposition (Existenz von Obermengen mit Zeugen):

Es sei $L^{S}$ eine Logiksprache und $\Gamma$ eine konsistente Menge von Sätzen. Dann kann man $L^{S}$ durch Variablen so zu einer größeren Sprache $L_{\infty }^{S}$ erweitern, dass es eine konsistente Obermenge $\Gamma _{\infty }$ von $\Gamma$ in der erweiterten Sprache gibt, welche zeugenangereichert ist. Des weiteren ist die Kardinalität sowohl von $\Gamma _{\infty }$ als auch von $L_{\infty }^{S}$ gleich der von $L^{S}$.

Beweis: Wir definieren eine Folge von Logiksprachen und Satzmengen wie folgt:

$L_{0}^{S}:=L^{S}$ und $\Gamma _{0}:=\Gamma$

und falls $L_{n}^{S}$ und $\Gamma _{n}$ schon definiert sind, dann definieren wir $L_{n+1}^{S}$ dadurch, dass wir für jeden Satz $\psi$ in $L_{n}^{S}$ eine neue Variable $z_{\psi }$ zu $L_{n+1}^{S}$ hinzufügen. Danach definieren wir $\Gamma _{n+1}$ dadurch, dass wir für jedes $\psi$ in $L_{n}^{S}$ den Satz $\exists x\psi \rightarrow \psi {\frac {z_{\psi }}{x}}$ zu $\Gamma$ hinzufügen.

Jedes $\Gamma _{n}$ ist konsistent, wie wir durch iterative Deduktion beweisen können: $\Gamma _{0}$ ist nach Annahme konsistent, und falls $\Gamma _{n+1}$ inkonsistent wäre, so gäbe es endlich viele Sätze der Form $\exists x\psi \rightarrow \psi {\frac {z_{\psi }}{x}}$ mit $\psi \in L_{n}^{S}$, aus denen man einen Widerspruch herleiten könnte. Aber mit iterativer Deduktion und dem vorhergehenden Satz kann man zeigen, dass $\Gamma _{n}$ vereinigt mit diesen Sätzen doch konsistent ist, ein Widerspruch.

Dann definieren wir

$L_{\infty }^{S}:=\bigcup _{n\in \mathbb {N} }L_{n}^{S}$ und $\Gamma _{\infty }:=\bigcup _{n\in \mathbb {N} }\Gamma _{n}$. $\Box$

Proposition (Existenz von Henkinobermengen):