Kurs:Einführung in die mathematische Logik (Osnabrück 2014)/Arbeitsblatt 20

Zeige, dass die folgenden Teilmengen ${\displaystyle {}T}$ der natürlichen Zahlenarithmetisch repräsentierbar sind.

1. Eine konkrete endliche Menge ${\displaystyle {}\{n_{1},\ldots ,n_{k}\}}$.
2. Die Menge aller Vielfachen von ${\displaystyle {}5}$.
3. Die Menge der Primzahlen.
4. Die Menge der Quadratzahlen.
5. Die Menge der Zahlen, in deren Primfaktorzerlegung jeder Exponent maximal ${\displaystyle {}1}$ ist.

Zeige, dass die folgenden Abbildungen${\displaystyle {}\varphi \colon \mathbb {N} ^{r}\rightarrow \mathbb {N} }$arithmetisch repräsentierbarsind.

1. Die Addition

   ${\displaystyle \mathbb {N} ^{2}\longrightarrow \mathbb {N} ,\,(x,y)\longmapsto x+y.}$

2. Die Multiplikation

   ${\displaystyle \mathbb {N} ^{2}\longrightarrow \mathbb {N} ,\,(x,y)\longmapsto x\cdot y.}$

3. Die eingeschränkte Subtraktion

   ${\displaystyle \mathbb {N} ^{2}\longrightarrow \mathbb {N} ,\,(x,y)\longmapsto \operatorname {max} _{}^{}{\left(x-y,0\right)},}$

   die bei ${\displaystyle {}y>x}$ den Wert ${\displaystyle {}0}$ besitzt.

4. Die Restfunktion

   ${\displaystyle \mathbb {N} ^{2}\longrightarrow \mathbb {N} ,\,(n,t)\longmapsto r(n,t),}$

   die den Rest(zwischen${\displaystyle {}0}$ und ${\displaystyle {}t-1}$)bei Division von ${\displaystyle {}n}$ durch ${\displaystyle {}t}$ angibt.

Zeige, dass die Abbildung

${\displaystyle F\colon \mathbb {N} \longrightarrow \mathbb {N} }$

mit

${\displaystyle {}F(n)={\begin{cases}{\sqrt {n}}\,,{\text{ falls }}{\sqrt {n}}\in \mathbb {N} \,,\\0{\text{ sonst}}\,,\end{cases}}\,}$

arithmetisch repräsentierbarist.

Es sei

${\displaystyle \varphi \colon \mathbb {N} ^{r}\longrightarrow \mathbb {N} ^{s}}$

eine Abbildung und${\displaystyle {}\Gamma \subseteq \mathbb {N} ^{r}\times \mathbb {N} ^{s}}$ der zugehörigeGraph,also die Menge

${\displaystyle {}\Gamma ={\left\{(n_{1},\ldots ,n_{r+s})\mid \varphi (n_{1},\ldots ,n_{r})=(n_{r+1},\ldots ,n_{r+s})\right\}}\,.}$

Zeige, dass ${\displaystyle {}\varphi }$ genau dannarithmetisch repräsentierbarist, wenn ${\displaystyle {}\Gamma }$(als Relation)arithmetisch repräsentierbarist.

Zeige explizit, dass die in Vorlesung 18 besprochenen Registerprogramme (also ihre zugehörigen Programmabbildungen) arithmetisch repräsentierbarsind.

Es sei

${\displaystyle \varphi \colon \mathbb {N} ^{r}\longrightarrow \mathbb {N} ^{s}}$

eine Abbildung. Zeige, dass ${\displaystyle {}\varphi }$ genau dannarithmetisch repräsentierbarist, wenn sämtliche Komponentenfunktionen${\displaystyle {}\varphi _{i}}$, ${\displaystyle {}1\leq i\leq s}$, arithmetisch repräsentierbar sind.

Zeige, dass die${\displaystyle {}\beta }$-Funktionarithmetisch repräsentierbar ist.

Zeige, dass es nurabzählbarvielearithmetisch repräsentierbareRelationen gibt.