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
.
Es 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
-
![{\displaystyle {}\alpha =\neg \beta \,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a8fc69b5fe280ddc3042118bbe0fcfd5a6d3af07)
ergibt sich die Äquivalenz aus der Induktionsvoraussetzung
(
hat kleineren Rang als
)
und
Fakt (1).
Bei
-
![{\displaystyle {}\alpha =\beta _{1}\wedge \beta _{2}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/915c1c0812e26fcc5d4a040cac88af92569ae342)
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
-
![{\displaystyle {}\alpha =\exists x\beta \,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/af1fc9d4352f24039a4eaf43d47b1405257789bd)
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.