Prädikatenlogik/Substitutionslemma/Fakt

Substitutionslemma

Es sei ein Symbolalphabet ${}S$ einer Sprache erster Stufe gegeben und es seien ${}x_{1},\ldots ,x_{k}$ paarweise verschiedene Variablen und ${}t_{1},\ldots ,t_{k}$ fixierte ${}S$-Terme. Es sei eine ${}S$-Interpretation ${}I$ gegeben. Dann gelten folgende Aussagen.

1. Für jeden ${}S$-Term ${}s$ gilt

   ${}I{\left(s{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}\right)}={\left(I{\frac {I(t_{1}),\ldots ,I(t_{k})}{x_{1},\ldots ,x_{k}}}\right)}(s)\,.$

2. Für jeden ${}S$-Ausdruck ${}\alpha$ gilt

   $I\vDash \alpha {\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}{\text{ genau dann, wenn }}{\left(I{\frac {I(t_{1}),\ldots ,I(t_{k})}{x_{1},\ldots ,x_{k}}}\right)}\vDash \alpha .$

Zum Beweis, Alternativen Beweis erstellen