Kurs:Einführung in die mathematische Logik (Osnabrück 2021)/Arbeitsblatt 20
- Übungsaufgaben
Zeige, dass die folgenden Teilmengen der natürlichen Zahlen arithmetisch repräsentierbar sind.
- Eine konkrete endliche Menge .
- Die Menge aller Vielfachen von .
- Die Menge der Primzahlen.
- Die Menge der Quadratzahlen.
- Die Menge der Zahlen, in deren Primfaktorzerlegung jeder Exponent maximal ist.
- Zeige, dass die Teilmenge der natürlichen Zahlen, die man als Summe von drei Quadraten schreiben kann, arithmetisch repräsentierbar ist.
- Formuliere in der arithmetischen Sprache, dass die keine Summe von drei Quadraten ist.
Zeige, dass die folgenden Abbildungen arithmetisch repräsentierbar sind.
- Die Addition
- Die Multiplikation
- Die eingeschränkte Subtraktion
die bei den Wert besitzt.
- Die Restfunktion
die den Rest (zwischen und ) bei Division von durch angibt.
Es sei
eine Polynomfunktion mit mit Koeffizienten . Zeige, dass durch den Ausdruck arithmetisch repräsentiert wird.
Zeige, dass eine lineare Abbildung (im Sinne von verträglich mit der Addition und mit der Skalarmultiplikation)
Es sei
eine arithmetisch repräsentierbare Abbildung. Zeige, dass das Bild arithmetisch repräsentierbar ist.
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.
Es sei
eine arithmetisch repräsentierbare Abbildung und es sei eine arithmetisch repräsentierbare Relation. Zeige, dass das Urbild
arithmetisch repräsentierbar ist.
Wir betrachten das Registerprogramm mit drei Registern (bei leerem dritten Register berechnet es die Summe der ersten beiden Registerinhalte)
- 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.
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)
Aufgabe (2 Punkte)
Es sei die Menge der geraden Zahlen , die die Goldbach-Vermutung erfüllen. Ist diese Menge arithmetisch repräsentierbar?
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 2021) | >> |
---|