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

Es sei ein Symbolalphabet ${}S$ ${{}} S$ einer Sprache erster Stufe gegeben und es seien ${}x_{1},\ldots ,x_{k}$ ${}x_{1},\ldots ,x_{k}$ paarweise verschiedene Variablen und ${}t_{1},\ldots ,t_{k}$ ${}t_{1},\ldots ,t_{k}$ fixierte ${}S$ ${{}} S$ -Terme. Es sei eine ${}S$ ${{}} S$ -Interpretation ${}I$ ${{}} 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 .$
Es sei ${}S$ ein Symbolalphabet, ${}\Gamma$ eine Menge an ${}S$ -Ausdrücken und ${}\alpha$ ein weiterer ${}S$ -Ausdruck. Dann gilt ${}\Gamma \vDash \alpha$ genau dann, wenn es eine endliche Teilmenge ${}\Gamma _{e}\subseteq \Gamma$ gibt mit ${}\Gamma _{e}\vDash \alpha$ .
Die Menge
${\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
${}R$ -entscheidbar.
Es sei ${}\Gamma \subseteq L^{\rm {Ar}}$ eine Menge von arithmetischen Ausdrücken, die Repräsentierungen erlaube. Dann gibt es zu jedem ${}\alpha \in L_{1}^{\rm {Ar}}$ einen Satz ${}q\in L_{0}^{\rm {Ar}}$ mit
$\Gamma \vdash q\longleftrightarrow \alpha (GN(q)).$

This article is issued from Wikiversity. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.