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

Übungsaufgaben

Aufgabe Referenznummer erstellen

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

Aufgabe Referenznummer erstellen

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

1. Halte an

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

Aufgabe Referenznummer erstellen

Erstelle für das Registerprogramm (mit zwei Registern ${}R_{1},R_{2}$ und leerer Anfangsbelegung)

1. ${}1+$
2. ${}2-$
3. Halte an

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

Aufgabe Aufgabe 21.4 ändern

Es sei ${}S$ ein Symbolalphabet und ${}L^{S}$ die zugehörige Sprache erster Stufe, wobei die Sprache zumindest eine Variable besitzen möge. Es sei ${}T\subseteq L_{0}^{S}$ eine Theorie. Zeige, dass ${}T$ genau dann widersprüchlich ist, wenn ${}T=L_{0}^{S}$ ist.

Aufgabe Referenznummer erstellen

Kann es ein Entscheidungsverfahren für mathematisch relevante Untertheorien ${}T\subseteq L_{0}^{\rm {Ar}}$ geben?

Aufgabe Referenznummer erstellen

Kann es ein Entscheidungsverfahren für die Symbolalphabete ${}\{0,1,+\}$ bzw. ${}\{0,1,\cdot \}$ (jeweils mit Variablen) geben? Wo geht bei der Arithmetisierung der Registerprogramme die Addition und wo die Multiplikation ein?

Aufgabe Referenznummer erstellen

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

Aufgabe Referenznummer erstellen

Kann es mathematische Probleme innerhalb entscheidbarer Theorien geben?

Aufgabe Referenznummer erstellen

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

Aufgabe Referenznummer erstellen

Es sei ${}T\subseteq L^{S}$ eine aufzählbar axiomatisierbare Theorie und ${}\alpha _{1},\ldots ,\alpha _{n}\in L^{S}$. Zeige, dass dann auch

${}T'={\left(T\cup \{\alpha _{1},\ldots ,\alpha _{n}\}\right)}^{\vdash }\,$

aufzählbar axiomatisierbar ist.

Aufgabe Referenznummer erstellen

Es seien ${}T_{1},T_{2}\subseteq L^{S}$ aufzählbar axiomatisierbare Theorien. Zeige, dass dann auch ${}(T_{1}\cup T_{2})^{\vdash }$ aufzählbar ist.

Aufgabe * Referenznummer erstellen

Zeige, dass die erststufige Peano-Arithmetik ${}PA$ eine vollständige widerspruchsfreie erststufige Erweiterung ${}M$, also ${}PA\subseteq M\subseteq L_{0}^{\rm {Ar}}$, besitzt, die von ${}\mathbb {N} _{0}^{\vDash }$ verschieden ist.

Aufgabe Aufgabe 21.13 ändern

Entwerfe ein ${}R$-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)Referenznummer erstellen

Erstelle für das Registerprogramm (mit zwei Registern ${}R_{1},R_{2}$ und leerer Anfangsbelegung)

1. ${}1+$
2. ${}C(2,1)$
3. Halte an

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

Aufgabe (3 Punkte)Aufgabe 21.15 ändern

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

Aufgabe (3 Punkte)Referenznummer erstellen

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