Aussagenlogik/Vollständigkeitssatz/Abzählbar/Auffüllungsstrategie/Fakt/Beweis/Aufgabe/Lösung

Es sei $p_n$, $n\in {\mathbb{N}}_{+}$, eine (surjektive, aber nicht notwendigerweise injektive) Aufzählung der Aussagenvariablen. Die Voraussetzung bedeutet, dass  ${\Gamma }_0:={\Gamma }^{⊢}$  keinen Widerspruch enthält. Wir konstruieren eine (endliche oder abzählbar unendliche) Folge von aufsteigenden widerspruchsfreien Teilmengen  ${\Gamma }_n\subseteq {\Gamma }_{n+1}$,  wobei in ${\Gamma }_n$ für jede Variable $p_i$, $1\le i\le n$, die Alternative entweder  $p_i\in {\Gamma }_n$  oder $\mathrm{\neg }{p}_i\in {\Gamma }_n$  gilt. Das Konstruktionsverfahren definieren und diese Aussage beweisen wir durch Induktion über  $n\in \mathbb{N}$.  Für ${\Gamma }_0$ ist dies richtig. Es sei ${\Gamma }_n$ schon konstruiert. Bei  $p_{n+1}\in {\Gamma }_n$  oder  $\mathrm{\neg }{p}_{n+1}\in {\Gamma }_n$  setzen wir

${\Gamma }_{n+1}:={\Gamma }_n.$

Wegen der Widerspruchsfreiheit von ${\Gamma }_n$ können nicht sowohl $p_{n+1}$ als auch $\mathrm{\neg }{p}_{n+1}$ zu ${\Gamma }_n$ gehören. Wenn weder $p_{n+1}$ noch $\mathrm{\neg }{p}_{n+1}$ zu ${\Gamma }_n$ gehören, so setzen wir

${\Gamma }_{n+1}:={({\Gamma }_n\cup p_{n+1})}^{⊢}$

(man könnte genauso gut $\mathrm{\neg }{p}_{n+1}$ hinzunehmen). Nach Konstruktion ist ${\Gamma }_{n+1}$ abgeschlossen unter der Ableitungsbeziehung und erfüllt die (Oder)-Alternative für alle Variablen $p_i$, $i\le n+1$. Wenn ${\Gamma }_{n+1}$ widersprüchlich wäre, so gelte insbesondere ${\Gamma }_n\cup \{p_{n+1}\}⊢\mathrm{\neg }{p}_{n+1}$. Dann würde aber auch ${\Gamma }_n⊢p_{n+1}\to \mathrm{\neg }{p}_{n+1}$ gelten und somit nach der Fallunterscheidungsregel auch ${\Gamma }_n⊢\mathrm{\neg }{p}_{n+1}$, also  $\mathrm{\neg }{p}_{n+1}\in {\Gamma }_n$  im Widerspruch zu dem Fall, in dem wir uns befinden. Daher liegt für die Aussagenvariablen auch die Entweder-Oder-Alternative vor.

Mit dieser induktiven Definition setzen wir

${\Gamma }^{\prime }:=\bigcup _{n\in \mathbb{N}}{\Gamma }_n.$

Diese Menge ${\Gamma }^{\prime }$ ist widerspruchsfrei, da andernfalls schon eines der ${\Gamma }_n$ einen Widerspruch enthalten würde, und auch abgeschlossen unter Ableitungen, da dies für die einzelnen ${\Gamma }_n$ gilt und eine Ableitung nur endlich viele Voraussetzungen besitzt. Ferner gilt für jedes  $n\in \mathbb{N}$  die Alternative $p_n\in {\Gamma }^{\prime }$ oder $\mathrm{\neg }{p}_n\in {\Gamma }^{\prime }$. Damit sind die Voraussetzungen von Fakt

erfüllt und ${\Gamma }^{\prime }$ ist maximal widerspruchsfrei.

Zur gelösten Aufgabe