Arithmetik/Repräsentierungen/Textabschnitt

Aus Wikiversity
Zur Navigation springen Zur Suche springen


Definition  

Es sei eine Menge von arithmetischen Ausdrücken. Eine Relation heißt repräsentierbar in , wenn es einen -Ausdruck in freien Variablen derart gibt, dass für alle -Tupel die beiden Eigenschaften

  1. Wenn , so ist ,
  2. Wenn , so ist ,

gelten.


Definition  

Es sei eine Menge von arithmetischen Ausdrücken. Eine Funktion

heißt repräsentierbar in , wenn es einen -Ausdruck in freien Variablen derart gibt, dass für alle -Tupel die folgenden Eigenschaften

  1. Wenn , so ist ,
  2. Wenn , so ist ,
  3. ,

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 eine Menge von arithmetischen Ausdrücken. Man sagt, dass Repräsentierungen erlaubt, wenn jede -berechenbare Relation und jede -berechenbare Funktion repräsentiert.



Korollar  

Die natürliche Arithmetik, also die Menge der in wahren Ausdrücke ,

erlaubt Repräsentierungen.

Beweis  

Es sei eine -entscheidbare Relation und es sei ein Registerprogramm mit den Registern das diese Relation entscheidet. Aufgrund von Fakt gibt es einen arithmetischen Ausdruck in freien Variablen, der den Programmablauf arithmetisch modelliert. Es gilt also genau dann, wenn , angesetzt auf (strenggenommen angesetzt auf , wenn man die vollständige Registerbelegung angibt) anhält mit der Ausgabe (d.h. ; andernfalls wird mit der Ausgabe angehalten), genau dann, wenn gilt.

Wegen der Vollständigkeit von bedeutet dies, dass

die Relation repräsentiert.
Es sei

eine -berechenbare Abbildung und es sei ein Registerprogramm, dass berechnet. Aufgrund von Fakt gibt es einen arithmetischen Ausdruck in freien Variablen, der den Programmablauf arithmetisch modelliert. D.h. für jedes -Tupel gilt

genau dann, wenn das Programm bei jeder Eingabe anhält und angesetzt auf (in den ersten Registern, die Eingabe ist also ) die Ausgabe (also ) besitzt, genau dann, wenn

gilt. Von daher ist der Ausdruck (in den freien Variablen )

Da eine Funktion vorliegt und vollständig ist, gilt auch