Kurs:Einführung in die mathematische Logik (Osnabrück 2016)/Arbeitsblatt 22/kontrolle
- Übungsaufgaben
Aufgabe Referenznummer erstellen
Zeige, dass eine widersprüchliche Ausdrucksmenge Repräsentierungen erlaubt.
Aufgabe Referenznummer erstellen
Es sei eine Ausdrucksmenge, die Repräsentierungen erlaube. Zeige, dass jede größere Ausdrucksmenge ebenfalls Repräsentierungen erlaubt.
Aufgabe * Referenznummer erstellen
Zeige, dass die Gleichheit von natürlichen Zahlen (also die Diagonalrelation in ) durch den Ausdruck in der erststufigen Peano-Arithmetik repräsentierbar ist.
Aufgabe Referenznummer erstellen
Es sei das Axiomensystem eines kommutativen Halbringes. Zeige, dass die Gleichheit von natürlichen Zahlen (also die Diagonalrelation in ) durch den Ausdruck in nicht repräsentiert wird.
Aufgabe Referenznummer erstellen
Es sei das Axiomensystem eines kommutativen Halbringes. Zeige, dass keine Repräsentierungen erlaubt.
Insbesondere erlauben die erststufigen Peano-Axiome ohne das Induktionsschema keine Repräsentierungen.
Aufgabe Referenznummer erstellen
Es sei und sei
wobei -mal der Summand vorkommt. Zeige, dass , also die Menge der Vielfachen von , in der erststufigen Peano-Arithmetik durch repräsentiert wird.
Aufgabe Referenznummer erstellen
Zeige, dass die Menge der Quadratzahlen in der erststufigen Peano-Arithmetik repräsentiert werden kann.
Aufgabe Referenznummer erstellen
Es sei eine widerspruchsfreie und - entscheidbare Ausdrucksmenge.
a) Zeige, dass jede in repräsentierbare Relation - entscheidbar ist.
b) Zeige, dass jede in repräsentierbare Abbildung
- berechenbar ist.
Aufgabe * Referenznummer erstellen
Es sei eine arithmetische Ausdrucksmenge ohne freie Variablen und eine Relation. Es seien Ausdrücke in einer freien Variablen . Zeige, dass aus
folgt, dass in die Relation genau dann repräsentiert, wenn in die Relation repräsentiert.
Aufgabe * Referenznummer erstellen
Es sei eine arithmetische Ausdrucksmenge und eine Relation. Es seien Ausdrücke in einer freien Variablen . Zeige, dass aus
nicht folgt, dass in die Relation genau dann repräsentiert, wenn in die Relation repräsentiert.
Aufgabe Referenznummer erstellen
Es sei eine Aufzählung einer abzählbar-unendlichen Symbolmengen. Berechne die zu Wörtern über diesem Alphabet zugehörige Zahl im Sinne der Primzahlkodierung und umgekehrt.
- ,
- ,
- ,
- ,
- ,
- ,
- .
Aufgabe Referenznummer erstellen
Es sei eine fixierte natürliche Zahl und
wobei durch die -fache Summe der mit sich selbst realisiert werde. Zeige direkt, dass es Sätze mit
und mit
gibt.
- Aufgaben zum Abgeben
Aufgabe (4 Punkte)Referenznummer erstellen
Zeige, dass die Menge der Primzahlen in der erststufigen Peano-Arithmetik repräsentiert werden kann.
Aufgabe (4 Punkte)Referenznummer erstellen
Es sei eine Aufzählung einer abzählbar-unendlichen Symbolmengen. Berechne die zu Wörtern über diesem Alphabet zugehörige Zahl im Sinne der Primzahlkodierung und umgekehrt.
- ,
- ,
- ,
- .
Aufgabe * (4 Punkte)Aufgabe 22.15 ändern
Zeige, dass in der erststufigen Peano-Arithmetik die Addition von natürlichen Zahlen repräsentierbar ist.
Aufgabe (6 Punkte)Referenznummer erstellen
Es sei
eine Polynomfunktion mit mit Koeffizienten . Zeige, dass durch den Ausdruck in der erststufigen Peano-Arithmetik repräsentiert wird.
Aufgabe (6 Punkte)Aufgabe 22.17 ändern
Es sei eine korrekte entscheidbare arithmetische Ausdrucksmenge, die die Peano-Arithmetik umfasse. Es sei das Ableitungsprädikat zu und es sei ein Fixpunkt zum negierten Ableitungsprädikat, also
Zeige, dass aus den in Bemerkung 23.7 angeführten Eigenschaften man
erhalten kann, wobei ein beliebiger Ausdruck ist.
<< | Kurs:Einführung in die mathematische Logik (Osnabrück 2016) | >> |
---|