Kurs:Einführung in die mathematische Logik (Osnabrück 2011-2012)/Arbeitsblatt 10

Aus Wikiversity
Zur Navigation springen Zur Suche springen

Aufgabe

Zeige, dass die folgenden Teilmengen der natürlichen Zahlen arithmetisch repräsentierbar sind.

  1. Eine konkrete endliche Menge .
  2. Die Menge aller Vielfachen von .
  3. Die Menge der Primzahlen.
  4. Die Menge der Quadratzahlen.
  5. Die Menge der Zahlen, in deren Primfaktorzerlegung jeder Exponent maximal ist.


Aufgabe

Zeige, dass die folgenden Abbildungen arithmetisch repräsentierbar sind.

  1. Die Addition
  2. Die Multiplikation
  3. Die eingeschränkte Subtraktion

    die bei den Wert besitzt.

  4. Die Restfunktion

    die den Rest (zwischen und ) bei Division von durch angibt.


Aufgabe

Es sei

eine Abbildung. Zeige, dass genau dann arithmetisch repräsentierbar ist, wenn sämtliche Komponentenfunktionen , , arithmetisch repräsentierbar sind.


Aufgabe

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


Aufgabe

Zeige, dass die -Funktion arithmetisch repräsentierbar ist.



<< | Kurs:Einführung in die mathematische Logik (Osnabrück 2011-2012) | >>

PDF-Version dieses Arbeitsblattes

Zur Vorlesung (PDF)