Logik/Vollständigkeitssatz/Maximalisierung/Abzählbarer Fall/Fakt/Beweis

Beweis

Da ${}S$ abzählbar ist, ist auch ${}L^{S}$ abzählbar. Es sei ${}\alpha _{n}$, ${}n\in \mathbb {N}$, eine Abzählung sämtlicher Ausdrücke aus ${}L^{S}$. Wir definieren induktiv eine aufsteigende Folge ${}\Gamma _{n}$ von Ausdrucksmengen durch ${}\Gamma _{0}=\Gamma$ und

${}\Gamma _{n+1}={\begin{cases}\Gamma _{n}\cup \{\alpha _{n+1}\},\,{\text{ falls dies widerspruchsfrei ist}}\,,\\\Gamma _{n}{\text{ sonst}}\,.\end{cases}}\,$

Wir setzen

${}\Gamma '=\bigcup _{n\in \mathbb {N} }\Gamma _{n}\,.$

Diese Menge ist widerspruchsfrei, da andernfalls schon eines der ${}\Gamma _{n}$ widersprüchlich wäre, was aufgrund der induktiven Definition nicht der Fall ist. Um zu zeigen, dass ${}\Gamma '$ maximal widerspruchsfrei ist, sei ${}\alpha \notin \Gamma '$. Da ${}\alpha$ in der Abzählung der Ausdrücke vorkommt, ist ${}\alpha =\alpha _{n}$ für ein gewisses ${}n$. Im ${}n$-ten Konstruktionsschritt wurde ${}\alpha _{n}$ nicht hinzugenommen, sonst wäre ${}\alpha _{n}\in \Gamma _{n}\subseteq \Gamma '$. Also ist ${}\Gamma _{n-1}\cup \{\alpha _{n}\}$ widersprüchlich und damit ist auch ${}\Gamma '\cup \{\alpha \}$ widersprüchlich.

Zur bewiesenen Aussage