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

1. Wenn ${}(n_{1},\ldots ,n_{r})\in T$, so ist ${}\Gamma \vdash \psi (n_{1},\ldots ,n_{r})$,
2. 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

1. 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})$,
2. 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})$,
3. ${}\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$