Kurs:Einführung in die mathematische Logik (Osnabrück 2021)/Arbeitsblatt 21



Übungsaufgaben

Beschreibe für die in Vorlesung 18 besprochenen Registerprogramme die Konfigurationsfolge bei Nulleingabe.



Erstelle für das Registerprogramm (mit keinem Register und leerer Anfangsbelegung)

  1. Halte an

den zugehörigen arithmetischen Ausdruck, der die Anhalteeigenschaft beschreibt.



Erstelle für das Registerprogramm (mit zwei Registern und leerer Anfangsbelegung)

  1. Halte an

den zugehörigen arithmetischen Ausdruck, der die Anhalteeigenschaft beschreibt.



Es sei ein Symbolalphabet und die zugehörige Sprache erster Stufe, wobei die Sprache zumindest eine Variable besitzen möge. Es sei eine Theorie. Zeige, dass genau dann widersprüchlich ist, wenn ist.



Kann es ein Entscheidungsverfahren für mathematisch relevante Untertheorien geben?



Kann es ein Entscheidungsverfahren für die Symbolalphabete bzw. (jeweils mit Variablen) geben? Wo geht bei der Arithmetisierung der Registerprogramme die Addition und wo die Multiplikation ein?



Gibt es offene zahlentheoretische Probleme, die ohne Bezug auf die Addition oder ohne Bezug auf die Multiplikation formuliert werden können?



Kann es mathematische Probleme innerhalb entscheidbarer Theorien geben?



Zeige, dass eine endlich axiomatisierbare Theorie auch durch einen einzigen Ausdruck axiomatisierbar ist.



Es sei eine aufzählbar axiomatisierbare Theorie und . Zeige, dass dann auch

aufzählbar axiomatisierbar ist.



Es seien aufzählbar axiomatisierbare Theorien. Zeige, dass dann auch aufzählbar ist.



Zeige, dass die erststufige Peano-Arithmetik eine vollständige widerspruchsfreie erststufige Erweiterung , also , besitzt, die von verschieden ist.



Entwerfe ein -Entscheidungsverfahren dafür, ob die Goldbach-Vermutung aus der erststufigen Peano-Arithmetik ableitbar ist.

Tipp: Verwende Aufgabe 19.10, Aufgabe 21.15 und Lemma 21.9.



Aufgaben zum Abgeben

Aufgabe (4 Punkte)

Erstelle für das Registerprogramm (mit zwei Registern und leerer Anfangsbelegung)

  1. Halte an

den zugehörigen arithmetischen Ausdruck, der die Anhalteeigenschaft beschreibt.



Aufgabe (3 Punkte)

Begründe, dass die (durch die erststufigen Peano-Axiome definierte) Peano-Arithmetik aufzählbar-axiomatisierbar ist.



Aufgabe (3 Punkte)

Zeige, dass es zwischen der erststufigen Peano-Arithmetik und der Standardarithmetik unendlich viele Theorien gibt.



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

PDF-Version dieses Arbeitsblattes

Zur Vorlesung (PDF)