Aussagenvariablen/Gleichung mit Variablen/Einbettung/Aufgabe/Lösung
- Wir definieren die Abbildung rekursiv über den Aufbau von . Für eine Aussagenvariable setzen wir
Für
setzen wir
und für
setzen wir
und entsprechend für .
- Wir beweisen die Injektivität in der Form, dass sich aus
die Verschiedenheit
ergibt, und zwar durch Induktion über den Aufbau von (simultan für alle ).
Für
ist entweder eine andere Aussagenvariable, sagen wir mit oder ein Ausdruck, der zumindest einen aussagenlogischen Junktor enthält. Im ersten Fall ist
und im zweiten Fall enthält mindestens einen Junktor und ist deshalb von verschieden.
Es sei nun
und dies sei von verschieden. Wenn keine Negation ist, so ist auch keine Negation und damit von verschieden. Wenn hingegen eine Negation ist, so ist und wegen der Verschiedenheit ist . Nach Induktionsvoraussetzung ist
und dies überträgt sich auf die negierten Ausdrücke.
Es sei nun
und dies sei von verschieden. Wenn kein konjugierter Ausdruck ist, so ist auch kein konjugierter Ausdruck und damit ist . Wenn hingegen ebenfalls ein konjugierter Ausdruck ist, so ist und wegen der Verschiedenheit ist oder . Sagen wir der erste Fall liegt vor. Nach Induktionsvoraussetzung ist dann
und dies überträgt sich auf die konjugierten Ausdrücke.
- Die Abbildung ist nicht surjektiv, da der Ausdruck nicht zum Bild gehört, da jedes mindestens eine Aussagenvariable und somit mindestens eine Variable enthält.
- Es gelte zunächst
Dann gibt es eine Ableitung im Aussagenkalkül für diesen Ausdruck. Diese Ableitung beruht allein auf aussagenlogischen Grundtautologien und dem Modus ponens. Wenn man in dieser Ableitung überall die Aussagenvariablen durch ersetzt, so werden aus den aussagenlogischen Grundtautologien prädikatenlogische Grundtautologien und der Modus ponens bleibt erhalten. Man erhält also durch diese Ersetzung eine prädikatenlogische Ableitung für und somit ist .
Wenn hingegen
gilt, so ist nach dem Vollständigkeitssatz der Aussagenlogik nicht allgemeingültig. Es gibt also eine Wahrheitsbelegung für die Aussagenvariablen derart, dass unter der zugehörigen (aussagenlogischen) Interpretation den Wahrheitswert bekommt. Es sei nun eine zweielementige Menge. Wir definieren eine -Interpretation auf durch
und
Mit dieser Festlegung ist genau dann, wenn ist. Da die aussagenlogischen Junktoren unter und gleichermaßen interpretiert werden, ist wegen auch . Daher ist nicht allgemeingültig und kann wegen der Korrektheit des Ableitungkalküls für die Prädikatenlogik auch nicht ableitbar sein. Also .