Logik/Vollständigkeitssatz/Henkin/Fakt/Beweis

Aus Wikiversity
Zur Navigation springen Zur Suche springen
Beweis

Es sei das konstruierte Modell zu und die zugehörige Interpretation mit der natürlichen Belegung für die Variablen. Wir zeigen die Äquivalenz

für alle Ausdrücke , durch Induktion über den Rang der Ausdrücke. Zum Induktionsanfang sei der Rang von gleich , also atomar. D.h. ist entweder von der Form oder . Im ersten Fall ist äquivalent zu bzw. in . Dies ist nach Fakt äquivalent zu und das bedeutet .

Im zweiten Fall ist - nach Konstruktion von und - äquivalent zu , und dies ist äquivalent zu .

Sei nun die Aussage für alle Ausdrücke vom Rang bewiesen und sei ein Ausdruck vom Rang . Wir betrachten die mögliche Struktur von gemäß Definition. Bei

ergibt sich die Äquivalenz aus der Induktionsvoraussetzung ( hat kleineren Rang als ) und Fakt  (1). Bei

besitzen die beiden Bestandteile kleineren Rang als . Die Zugehörigkeit ist nach Fakt  (3) äquivalent zur gemeinsamen Zugehörigkeit . Nach Induktionsvoraussetzung bedeutet dies und . Dies bedeutet wiederum aufgrund der Modellbeziehung. Bei

besitzt wieder einen kleineren Rang. Die Zugehörigkeit ist aufgrund der Eigenschaft, Beispiele zu enthalten und aufgrund von Axiom äquivalent zur Existenz eines Terms und der Zugehörigkeit . Die Substitution von nach verändert nach Aufgabe nicht den Rang. Wir können also auf die Induktionsvoraussetzung anwenden und erhalten die Äquivalenz zu . Nach dem Substitutionslemma ist dies äquivalent zu bzw. wegen Fakt. Dies ist äquivalent zu aufgrund der Modellbeziehung und der Surjektivität der Termabbildung.

Zur bewiesenen Aussage