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

Übungsaufgaben

Aufgabe Referenznummer erstellen

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 Referenznummer erstellen

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 Referenznummer erstellen

Es sei

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

eine Polynomfunktion mit ${}f(n)=a_{d}n^{d}+a_{d-1}n^{d-1}+\cdots +a_{1}n+a_{0}$ mit Koeffizienten ${}a_{i}\in \mathbb {N}$. Zeige, dass ${}f$ durch den Ausdruck ${}y=a_{d}x^{d}+a_{d-1}x^{d-1}+\cdots +a_{1}x+a_{0}$ arithmetisch repräsentiert wird.

Aufgabe Referenznummer erstellen

Zeige, dass eine lineare Abbildung (im Sinne von verträglich mit der Addition und mit der Skalarmultiplikation)

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

arithmetisch repräsentierbar ist.

Aufgabe Aufgabe 20.5 ändern

Zeige, dass eine polynomiale Abbildung (mit Koeffizienten aus ${}\mathbb {N}$)

$F\colon \mathbb {N} ^{r}\longrightarrow \mathbb {N} ,\,\left(x_{1},\,\ldots ,\,x_{n}\right)\longmapsto F(x_{1},\ldots ,x_{n}),$

arithmetisch repräsentierbar ist.

Aufgabe * Referenznummer erstellen

Zeige, dass die Abbildung

$f\colon \mathbb {N} ^{3}\longrightarrow \mathbb {N} ,\,(x,y,z)\longmapsto xy^{2}-z^{2}+2z^{3},$

(wohldefiniert und) arithmetisch repräsentierbar ist.

Aufgabe Referenznummer erstellen

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 Referenznummer erstellen

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 * Referenznummer erstellen

Es sei

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

eine arithmetisch repräsentierbare Abbildung. Zeige, dass zu jedem Punkt ${}P\in \mathbb {N} ^{s}$ die Faser

${}F^{-1}(P)\subseteq \mathbb {N} ^{r}\,$

arithmetisch repräsentierbar ist.

Aufgabe Referenznummer erstellen

Es sei

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

eine arithmetisch repräsentierbare Abbildung und es sei ${}T\subseteq \mathbb {N} ^{s}$ eine arithmetisch repräsentierbare Relation. Zeige, dass das Urbild

${}\varphi ^{-1}(T)\subseteq \mathbb {N} ^{r}\,$

arithmetisch repräsentierbar ist.

Aufgabe Referenznummer erstellen

Wir betrachten das Registerprogramm mit drei Registern (bei leerem dritten Register berechnet es die Summe der ersten beiden Registerinhalte)

1. ${}C(2,5)$
2. ${}1+$
3. ${}2-$
4. ${}C(3,1)$
5. Halte an

a) Erstelle die Programmabbildung für dieses Programm.

b) Welche Beziehung besteht zwischen der Programmabbildung und der Additionsabbildung

$\mathbb {N} \times \mathbb {N} \longrightarrow \mathbb {N} ,\,(x,y)\longmapsto x+y?$

c) Erstelle eine arithmetische Repräsentierung für dieses Programm.

Aufgabe Referenznummer erstellen

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

Aufgaben zum Abgeben

Aufgabe (2 Punkte)Referenznummer erstellen

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 (4 Punkte)Referenznummer erstellen

Zeige, dass die Abbildung

$F\colon \mathbb {N} \times \mathbb {N} _{+}\longrightarrow \mathbb {N} ,\,(x,y)\longmapsto \left\lfloor {\frac {x}{y}}\right\rfloor ,$

arithmetisch repräsentierbar ist.

Aufgabe (5 Punkte)Referenznummer erstellen

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

Aufgabe (2 Punkte)Referenznummer erstellen

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