Arithmetisch repräsentierbar/Abbildung und Graph/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.

Eine Lösung erstellen