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

Übungsaufgaben

Aufgabe

Zeige, dass die folgenden Teilmengen ${}T$ der natürlichen Zahlen arithmetisch repräsentierbar sind.

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

Aufgabe

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

1. Die Addition

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

2. Die Multiplikation

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

3. Die eingeschränkte Subtraktion

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

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

4. Die Restfunktion

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

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

Aufgabe

Zeige, dass die Abbildung

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

mit

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

arithmetisch repräsentierbar ist.

Aufgabe

Es sei

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

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

${}\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 ${}\varphi$ genau dann arithmetisch repräsentierbar ist, wenn ${}\Gamma$ (als Relation) arithmetisch repräsentierbar ist.

Aufgabe

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

Aufgaben zum Abgeben

Aufgabe (2 Punkte)

Es sei

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

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

Aufgabe (5 Punkte)

Zeige, dass die ${}\beta$- Funktion arithmetisch repräsentierbar ist.

Aufgabe (2 Punkte)

Zeige, dass es nur abzählbar viele arithmetisch repräsentierbare Relationen gibt.