Kurs:Einführung in die mathematische Logik (Osnabrück 2018)/Arbeitsblatt 20

Aus Wikiversity
Zur Navigation springen Zur Suche springen



Übungsaufgaben

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 Polynomfunktion mit mit Koeffizienten . Zeige, dass durch den Ausdruck arithmetisch repräsentiert wird.


Aufgabe

Zeige, dass eine lineare Abbildung

arithmetisch repräsentierbar ist.


Aufgabe

Zeige, dass eine polynomiale Abbildung (mit Koeffizienten aus )

arithmetisch repräsentierbar ist.


Aufgabe *

Zeige, dass die Abbildung

(wohldefiniert und) arithmetisch repräsentierbar ist.


Aufgabe

Zeige, dass die Abbildung

mit

arithmetisch repräsentierbar ist.


Aufgabe

Es sei

eine Abbildung und der zugehörige Graph, also die Menge

Zeige, dass genau dann arithmetisch repräsentierbar ist, wenn (als Relation) arithmetisch repräsentierbar ist.


Aufgabe *

Es sei

eine arithmetisch repräsentierbare Abbildung. Zeige, dass zu jedem Punkt die Faser

arithmetisch repräsentierbar ist.


Aufgabe

Es sei

eine arithmetisch repräsentierbare Abbildung und es sei eine arithmetisch repräsentierbare Relation. Zeige, dass das Urbild

arithmetisch repräsentierbar ist.


Aufgabe

Wir betrachten das Registerprogramm mit drei Registern (bei leerem dritten Register berechnet es die Summe der ersten beiden Registerinhalte)

  1. Halte an


a) Erstelle die Programmabbildung für dieses Programm.


b) Welche Beziehung besteht zwischen der Programmabbildung und der Additionsabbildung


c) Erstelle eine arithmetische Repräsentierung für dieses Programm.


Aufgabe

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




Aufgaben zum Abgeben

Aufgabe (2 Punkte)

Es sei

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


Aufgabe (4 Punkte)

Zeige, dass die Abbildung

arithmetisch repräsentierbar ist.


Aufgabe (5 Punkte)

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


Aufgabe (2 Punkte)

Zeige, dass es nur abzählbar viele arithmetisch repräsentierbare Relationen gibt.



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

PDF-Version dieses Arbeitsblattes

Zur Vorlesung (PDF)