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,\dots ,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 $\phi :{\mathbb{N}}^r\to \mathbb{N}$ arithmetisch repräsentierbar sind.

1. Die Addition

   ${\mathbb{N}}^2⟶\mathbb{N},(x,y)⟼x+y.$

2. Die Multiplikation

   ${\mathbb{N}}^2⟶\mathbb{N},(x,y)⟼x\cdot y.$

3. Die eingeschränkte Subtraktion

   ${\mathbb{N}}^2⟶\mathbb{N},(x,y)⟼{\max }_{}^{}(x-y,0),$

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

4. Die Restfunktion

   ${\mathbb{N}}^2⟶\mathbb{N},(n,t)⟼r(n,t),$

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

Aufgabe

Zeige, dass die Abbildung

$F:\mathbb{N}⟶\mathbb{N}$

mit

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

arithmetisch repräsentierbar ist.

Aufgabe

Es sei

$\phi :{\mathbb{N}}^r⟶{\mathbb{N}}^s$

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

$\Gamma =\{(n_1,\dots ,n_{r+s})\mid \phi (n_1,\dots ,n_r)=(n_{r+1},\dots ,n_{r+s})\}.$

Zeige, dass $\phi$ 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

$\phi :{\mathbb{N}}^r⟶{\mathbb{N}}^s$

eine Abbildung. Zeige, dass $\phi$ genau dann arithmetisch repräsentierbar ist, wenn sämtliche Komponentenfunktionen ${\phi }_i$, $1\le i\le 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.