Kurs:Einführung in die mathematische Logik (Osnabrück 2011-2012)/Arbeitsblatt 12

Aufgabe

Zeige, dass eine widersprüchliche Ausdrucksmenge ${}\Gamma \subseteq L^{\rm {Ar}}$ Repräsentierungen erlaubt.

Aufgabe

Es sei ${}\Gamma \subseteq L^{\rm {ar}}$ eine Ausdrucksmenge, die Repräsentierungen erlaube. Zeige, dass jede größere Ausdrucksmenge ${}\Gamma '\supseteq \Gamma$ ebenfalls Repräsentierungen erlaubt.

Aufgabe

Es sei ${}\Gamma \subseteq L^{\rm {ar}}$ eine widerspruchsfreie und ${}R$-entscheidbare Ausdrucksmenge.

a) Zeige, dass jede in ${}\Gamma$ repräsentierbare Relation ${}R\subseteq \mathbb {N} ^{r}$ ${}R$-entscheidbar ist.

b) Zeige, dass jede in ${}\Gamma$ repräsentierbare Abbildung

$\varphi \colon \mathbb {N} ^{r}\longrightarrow \mathbb {N} ^{s}$

${}R$-berechenbar ist.

Aufgabe *

Zeige, dass in der erststufigen Peano-Arithmetik die Addition von natürlichen Zahlen repräsentierbar ist.

<< | Kurs:Einführung in die mathematische Logik (Osnabrück 2011-2012) | >> PDF-Version dieses Arbeitsblattes Zur Vorlesung (PDF)