Mathematische Logik/Gemischte Satzabfrage/2/Aufgabe/Lösung

${\displaystyle {}S}$

${\displaystyle {}x_{1},\ldots ,x_{k}}$

${\displaystyle {}t_{1},\ldots ,t_{k}}$

${\displaystyle {}S}$

${\displaystyle {}S}$

${\displaystyle {}I}$

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

   ${\displaystyle {}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 ${\displaystyle {}S}$-Ausdruck ${\displaystyle {}\alpha }$ gilt

   ${\displaystyle 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 .}$

${\displaystyle {\left\{n\in \mathbb {N} \mid n{\text{ ist die Nummer eines Registerprogramms }}P{\text{ und }}P(0){\text{ hält an}}\right\}}}$

ist nicht

${\displaystyle {}R}$

${\displaystyle {}\Gamma \subseteq L^{\rm {Ar}}}$

${\displaystyle {}\alpha \in L_{1}^{\rm {Ar}}}$

${\displaystyle {}q\in L_{0}^{\rm {Ar}}}$

${\displaystyle \Gamma \vdash q\longleftrightarrow \alpha (GN(q)).}$