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

1. Man sagt, dass ${}\alpha$ aus ${}\Gamma$ ableitbar ist, wenn es endlich viele Ausdrücke ${}\alpha _{1},\ldots ,\alpha _{n}\in \Gamma$ derart gibt, dass

   $\vdash \alpha _{1}\wedge \ldots \wedge \alpha _{n}\rightarrow \alpha$

   gilt.

2. Unter einer ${}n$-stelligen Relation ${}R$ auf ${}M$ versteht man eine Teilmenge der ${}n$-fachen Produktmenge ${}M\times \cdots \times M$.
3. Man sagt, dass ${}\alpha$ aus ${}\Gamma$ folgt, wenn für jede ${}S$-Interpretation ${}I$ mit ${}I\vDash \Gamma$ auch ${}I\vDash \alpha$ gilt.
4. Die Termsubstitution ${}s{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}$ wird rekursiv folgendermaßen definiert.
   1. Für eine Variable ${}x$ ist

      ${}x{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}:={\begin{cases}x,{\text{ falls }}x\neq x_{i}{\text{ für alle }}i\,,\\t_{i},{\text{ falls }}x=x_{i}\,.\end{cases}}\,$

   2. Für eine Konstante ${}c$ ist

      ${}c{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}:=c\,.$

   3. Für ein ${}n$-stelliges Funktionssymbol ${}f$ und ${}n$ Terme ${}s_{1},\ldots ,s_{n}$ ist

      ${}fs_{1}\ldots s_{n}{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}:=fs_{1}{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}\ldots s_{n}{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}\,.$

5. Die Addition ${}n+k$ wird über die Addition ${}\alpha _{n}$ mit festem ${}n$ definiert, wobei ${}\alpha _{n}$ die eindeutig bestimmte Abbildung

   $\alpha _{n}\colon \mathbb {N} \longrightarrow \mathbb {N} ,\,k\longmapsto \alpha _{n}(k),$

   ist, für die

   $\alpha _{n}(0)=n{\text{ und }}\alpha _{n}(k')=(\alpha _{n}(k))'{\text{ für alle }}k\in \mathbb {N}$

   gilt.

6. Die Teilmenge ${}T$ heißt Register-entscheidbar, wenn es ein Programm ${}P$ für eine Registermaschine gibt, die bei jeder Eingabe anhält und für die die Äquivalenz

   $n\in T{\text{ genau dann, wenn }}P(n){\text{ die Ausgabe }}0{\text{ besitzt}}$

   gilt.

Zur gelösten Aufgabe