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


Es sei , , eine (surjektive, aber nicht notwendigerweise injektive) Aufzählung der Aussagenvariablen. Die Voraussetzung bedeutet, dass keinen Widerspruch enthält. Wir konstruieren eine (endliche oder abzählbar unendliche) Folge von aufsteigenden widerspruchsfreien Teilmengen , wobei in für jede Variable , , die Alternative entweder oder gilt. Das Konstruktionsverfahren definieren und diese Aussage beweisen wir durch Induktion über . Für ist dies richtig. Es sei schon konstruiert. Bei oder setzen wir

Wegen der Widerspruchsfreiheit von können nicht sowohl als auch zu gehören. Wenn weder noch zu gehören, so setzen wir

(man könnte genauso gut hinzunehmen). Nach Konstruktion ist abgeschlossen unter der Ableitungsbeziehung und erfüllt die (Oder)-Alternative für alle Variablen , . Wenn widersprüchlich wäre, so gelte insbesondere . Dann würde aber auch gelten und somit nach der Fallunterscheidungsregel auch , also 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

Diese Menge ist widerspruchsfrei, da andernfalls schon eines der einen Widerspruch enthalten würde, und auch abgeschlossen unter Ableitungen, da dies für die einzelnen gilt und eine Ableitung nur endlich viele Voraussetzungen besitzt. Ferner gilt für jedes die Alternative oder . Damit sind die Voraussetzungen von Fakt

erfüllt und ist maximal widerspruchsfrei.