Aussagenvariablen/Gleichung mit Variablen/Einbettung/Aufgabe/Lösung

1. Wir definieren die Abbildung ${}\Psi$ rekursiv über den Aufbau von ${}L$. Für eine Aussagenvariable ${}p_{i}$ setzen wir

   ${}\Psi (p_{i}):=\beta _{i}\,.$

   Für

   ${}\alpha =\neg \beta \,$

   setzen wir

   ${}\Psi (\alpha )=\neg \Psi (\beta )\,$

   und für

   ${}\alpha =\alpha _{1}\wedge \alpha _{2}\,$

   setzen wir

   ${}\Psi (\alpha )=\Psi (\alpha _{1})\wedge \Psi (\alpha _{1})\,$

   und entsprechend für ${}\rightarrow$.

2. Wir beweisen die Injektivität in der Form, dass sich aus

   ${}\alpha \neq \alpha '\,$

   die Verschiedenheit

   ${}\Psi (\alpha )\neq \Psi (\alpha ')\,$

   ergibt, und zwar durch Induktion über den Aufbau von ${}\alpha$ (simultan für alle ${}\alpha '$).

   Für

   ${}\alpha =p_{i}\,$

   ist ${}\alpha '$ entweder eine andere Aussagenvariable, sagen wir ${}p_{j}$ mit ${}i\neq j$ oder ein Ausdruck, der zumindest einen aussagenlogischen Junktor enthält. Im ersten Fall ist

   ${}\Psi (p_{j})=(x_{j}=c)\neq (x_{i}=c)=\Psi (p_{i})\,$

   und im zweiten Fall enthält ${}\Psi (\alpha ')$ mindestens einen Junktor und ist deshalb von ${}\Psi (p_{i})$ verschieden.

   Es sei nun

   ${}\alpha =\neg \beta \,$

   und dies sei von ${}\alpha '$ verschieden. Wenn ${}\alpha '$ keine Negation ist, so ist auch ${}\Psi (\alpha ')$ keine Negation und damit von ${}\Psi (\alpha )=\neg \Psi (\beta )$ verschieden. Wenn hingegen ${}\alpha '$ eine Negation ist, so ist ${}\alpha '=\neg \beta '$ und wegen der Verschiedenheit ist ${}\beta \neq \beta '$. Nach Induktionsvoraussetzung ist

   ${}\Psi (\beta )\neq \Psi (\beta ')\,$

   und dies überträgt sich auf die negierten Ausdrücke.

   Es sei nun

   ${}\alpha =\alpha _{1}\wedge \alpha _{2}\,$

   und dies sei von ${}\alpha '$ verschieden. Wenn ${}\alpha '$ kein konjugierter Ausdruck ist, so ist auch ${}\Psi (\alpha ')$ kein konjugierter Ausdruck und damit ist ${}\Psi (\alpha )\neq \Psi (\alpha ')$. Wenn hingegen ${}\alpha '$ ebenfalls ein konjugierter Ausdruck ist, so ist ${}\alpha '=\alpha _{1}'\wedge \alpha _{2}'$ und wegen der Verschiedenheit ist ${}\alpha _{1}\neq \alpha _{1}'$ oder ${}\alpha _{2}\neq \alpha _{2}'$. Sagen wir der erste Fall liegt vor. Nach Induktionsvoraussetzung ist dann

   ${}\Psi (\alpha _{1})\neq \Psi (\alpha _{1}')\,$

   und dies überträgt sich auf die konjugierten Ausdrücke.

3. Die Abbildung ist nicht surjektiv, da der Ausdruck ${}c=c$ nicht zum Bild gehört, da jedes ${}\alpha$ mindestens eine Aussagenvariable ${}p_{i}$ und somit ${}\Psi (p_{i})$ mindestens eine Variable ${}x_{i}$ enthält.
4. Es gelte zunächst

   $\vdash \alpha .$

   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 ${}p_{i}$ durch ${}\beta _{i}$ 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 ${}\Psi (\alpha )$ und somit ist ${}\vdash \Psi (\alpha )$.

   Wenn hingegen

   $\not \vdash \alpha$

   gilt, so ist ${}\alpha$ nach dem Vollständigkeitssatz der Aussagenlogik nicht allgemeingültig. Es gibt also eine Wahrheitsbelegung ${}\lambda$ für die Aussagenvariablen derart, dass ${}\alpha$ unter der zugehörigen (aussagenlogischen) Interpretation ${}I^{\lambda }$ den Wahrheitswert ${}0$ bekommt. Es sei nun ${}M=\{a,b\}$ eine zweielementige Menge. Wir definieren eine ${}S$-Interpretation ${}J$ auf ${}M$ durch

   ${}c^{M}=a\,$

   und

   ${}x_{i}^{M}:={\begin{cases}a,{\text{ falls }}\lambda (p_{i})=1\,,\\b,{\text{ falls }}\lambda (x_{i})=0\,.\end{cases}}\,$

   Mit dieser Festlegung ist ${}I^{\lambda }\vDash p_{i}$ genau dann, wenn ${}J\vDash \beta _{i}$ ist. Da die aussagenlogischen Junktoren unter ${}I^{\lambda }$ und ${}J$ gleichermaßen interpretiert werden, ist wegen ${}I^{\lambda }\not \vDash \alpha$ auch ${}J\not \vDash \Psi (\alpha )$. Daher ist ${}\Psi (\alpha )$ nicht allgemeingültig und kann wegen der Korrektheit des Ableitungkalküls für die Prädikatenlogik auch nicht ableitbar sein. Also ${}\not \vdash \Psi (\alpha )$.

Zur gelösten Aufgabe