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

1. Ein Element ${}x\in I$ heißt maximal, wenn es kein Element ${}y\in I$, ${}y\neq x$, mit ${}x\preccurlyeq y$ gibt.
2. 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}}}\,.$

3. Der Rang ${}\rho$ von ${}\alpha$ wird rekursiv durch
   1. ${}\rho (\alpha )=0$, falls ${}\alpha$ atomar ist.
   2. ${}\rho (\alpha )=\rho (\beta )+1$, falls ${}\alpha =\neg (\beta )$ ist.
   3. ${}\rho (\alpha )=\rho (\beta )+\rho (\gamma )+1$, falls ${}\alpha =(\beta )\circ (\gamma )$ mit ${}\circ =\wedge ,\,\vee ,\,\rightarrow ,\leftrightarrow$ ist.
   4. ${}\rho (\alpha )=\rho (\beta )+1$, falls ${}\alpha =\exists x\beta$ oder ${}\alpha =\forall x\beta$ ist.

   definiert.

4. Die beiden ${}S$-Strukturen ${}M$ und ${}N$ heißen elementar äquivalent, wenn jeder ${}S$-Satz, der in ${}M$ gilt, auch in ${}N$ gilt.
5. Die Funktion

   $F\colon \mathbb {N} ^{k}\longrightarrow \mathbb {N}$

   heißt ${}R$-berechenbar, wenn es ein Programm ${}P$ für eine Registermaschine gibt, die bei jeder Eingabe ${}(r_{1},\ldots ,r_{k})$ (in den ersten ${}k$ Registern) anhält und ${}F(r_{1},\ldots ,r_{k})$ als (einzige) Ausgabe besitzt.

6. Unter der ${}\beta$-Funktion versteht man die Abbildung

   $\mathbb {N} ^{3}\longrightarrow \mathbb {N} ,\,(p,n,i)\longmapsto \beta (p,n,i),$

   die folgendermaßen festgelegt ist. ${}\beta (p,n,i)$ ist die kleinste Zahl ${}a\in \mathbb {N}$, die die Bedingung erfüllt, dass es natürliche Zahlen ${}b_{0},b_{1},b_{2}$ gibt, die die folgenden Eigenschaften erfüllen:

   1. ${}n=b_{0}+b_{1}{\left((i+1)+ap+b_{2}p^{2}\right)}$.
   2. ${}a<p$.
   3. ${}b_{0}<b_{1}$.
   4. ${}b_{1}$ ist eine Quadratzahl.
   5. Alle Teiler ${}d\neq 1$ von ${}b_{1}$ sind ein Vielfaches von ${}p$.

   Wenn kein solches ${}a$ existiert, so ist ${}\beta (p,n,i)=0$.

Zur gelösten Aufgabe