# Arithmetik/Repräsentierungen/Textabschnitt
## Definition

Es sei $\Gamma$ eine Menge von arithmetischen Ausdrücken. Eine Relation $T\subseteq \mathbb {N} ^{r}$ heißt repräsentierbar in $\Gamma$, wenn es einen $L^{\rm {Ar}}$-Ausdruck $\psi$ in $r$ freien Variablen derart gibt, dass für alle $r$-Tupel $(n_{1},\ldots ,n_{r})\in \mathbb {N} ^{r}$ die beiden Eigenschaften
* Wenn $(n_{1},\ldots ,n_{r})\in T$, so ist $\Gamma \vdash \psi (n_{1},\ldots ,n_{r})$,
* Wenn $(n_{1},\ldots ,n_{r})\notin T$, so ist $\Gamma \vdash \neg \psi (n_{1},\ldots ,n_{r})$,
gelten.

## Definition

Es sei $\Gamma$ eine Menge von arithmetischen Ausdrücken. Eine Funktion
    $F\colon \mathbb {N} ^{r}\longrightarrow \mathbb {N} ^{s}$
heißt repräsentierbar in $\Gamma$, wenn es einen $L^{\rm {Ar}}$-Ausdruck $\psi$ in $r+s$ freien Variablen derart gibt, dass für alle $(r+s)$-Tupel $(n_{1},\ldots ,n_{r+s})\in \mathbb {N} ^{r+s}$ die folgenden Eigenschaften
* Wenn $F(n_{1},\ldots ,n_{r})=(n_{r+1},\ldots ,n_{r+s})$, so ist $\Gamma \vdash \psi (n_{1},\ldots ,n_{r+s})$,
* Wenn $F(n_{1},\ldots ,n_{r})\neq (n_{r+1},\ldots ,n_{r+s})$, so ist $\Gamma \vdash \neg \psi (n_{1},\ldots ,n_{r+s})$,
* $\Gamma \vdash \exists !x_{r+1}\ldots \exists !x_{r+s}\psi (n_{1},\ldots ,n_{r},x_{r+1},\ldots ,x_{r+s})$,
gelten.
Die dritte Eigenschaft besagt, dass die Ausdrucksmenge beweisen kann, dass es sich um eine Funktion handelt. Diese Eigenschaft folgt nicht aus den beiden ersten Eigenschaften.

## Definition

Es sei $\Gamma$ eine Menge von arithmetischen Ausdrücken. Man sagt, dass $\Gamma$ Repräsentierungen erlaubt, wenn $\Gamma$ jede $R$-berechenbare Relation und jede $R$-berechenbare Funktion repräsentiert.

## Korollar

Die natürliche Arithmetik, also die Menge der in $\mathbb {N}$ wahren Ausdrücke $\mathbb {N} ^{\vDash }$,
erlaubt Repräsentierungen.

### Beweis

Es sei $T\subseteq \mathbb {N} ^{r}$ eine $R$-entscheidbare Relation und es sei $P$ ein Registerprogramm mit den Registern $R_{0},R_{1},\ldots ,R_{m}$ das diese Relation entscheidet. Aufgrund von Fakt gibt es einen arithmetischen Ausdruck $\psi _{P}$ in $2m$ freien Variablen, der den Programmablauf arithmetisch modelliert. Es gilt also $(n_{1},\ldots ,n_{r})\in T$ genau dann, wenn $P$, angesetzt auf $(n_{1},\ldots ,n_{r})$ (strenggenommen angesetzt auf $(1,n_{1},\ldots ,n_{r},0,\ldots ,0)$, wenn man die vollständige Registerbelegung angibt) anhält mit der Ausgabe $0$ (d.h. $(h,0,n'_{2},\ldots ,n'_{m})$; andernfalls wird mit der Ausgabe $1$ angehalten), genau dann, wenn $\mathbb {N} \vDash \psi _{P}(n_{1},\ldots ,n_{r},0,\ldots ,0,0,n'_{2},\ldots ,n'_{m})$ gilt.
Wegen der Vollständigkeit von $\mathbb {N}$ bedeutet dies, dass
    $\theta _{P}=\exists y_{2}\ldots \exists y_{m}\psi _{P}(x_{1},\ldots ,x_{r},0,\ldots ,0,0,y_{2},\ldots ,y_{m})\,$
die Relation repräsentiert. Es sei
    $F\colon \mathbb {N} ^{r}\longrightarrow \mathbb {N} ^{s}$
eine $R$-berechenbare Abbildung und es sei $P$ ein Registerprogramm, dass $F$ berechnet. Aufgrund von Fakt gibt es einen arithmetischen Ausdruck $\psi _{P}$ in $2m$ freien Variablen, der den Programmablauf arithmetisch modelliert. D.h. für jedes $(r+s)$-Tupel $n_{1},\ldots ,n_{r+s}$ gilt
    $F(n_{1},\ldots ,n_{r})=(n_{r+1},\ldots ,n_{r+s})\,$
genau dann, wenn das Programm $P$ bei jeder Eingabe anhält und angesetzt auf $(n_{1},\ldots ,n_{r})$ (in den ersten $r$ Registern, die Eingabe ist also $(1,n_{1},\ldots ,n_{r},0,\ldots ,0)$) die Ausgabe $(n_{r+1},\ldots ,n_{r+s})$ (also $(h,n_{r+1},\ldots ,n_{r+s},\ell _{m+s+1},\ldots ,\ell _{2m})$) besitzt, genau dann, wenn
    $\mathbb {N} \vDash \psi (n_{1},\ldots ,n_{r},0,\ldots ,0,n_{r+1},\ldots ,n_{r+s},\ell _{m+s+1},\ldots ,\ell _{2m})$
gilt. Von daher ist der Ausdruck (in den freien Variablen $x_{1},\ldots ,x_{r},x_{r+1},\ldots ,x_{r+s}$)
    $\Theta =\exists z_{m+s+1}\ldots \exists z_{2m}\Psi (x_{1},\ldots ,x_{r},0,\ldots ,0,x_{r+1},\ldots ,x_{r+s},z_{m+s+1},\ldots ,z_{2m})\,$
Da eine Funktion vorliegt und $\mathbb {N} ^{\vDash }$ vollständig ist, gilt auch
    $\mathbb {N} \vDash \exists !x_{r+1}\ldots \exists !x_{r+s}\Theta (n_{1},\ldots ,n_{r},x_{r+1},\ldots ,x_{r+s}).$
$\Box$