Kurs:Einführung in die mathematische Logik (Osnabrück 2014)/Arbeitsblatt 22

Übungsaufgaben

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.

Aufgabe *

Es sei ${}\Gamma \subseteq L^{\rm {Ar}}$ eine arithmetische Ausdrucksmenge ohne freie Variablen und ${}R\subseteq \mathbb {N}$ eine Relation. Es seien ${}\alpha ,\beta \in L^{\rm {Ar}}$ Ausdrücke in einer freien Variablen ${}x$. Zeige, dass aus

$\Gamma \vdash \alpha \leftrightarrow \beta$

folgt, dass ${}\alpha$ in ${}\Gamma$ die Relation ${}R$ genau dann repräsentiert, wenn ${}\beta$ in ${}\Gamma$ die Relation ${}R$ repräsentiert.

Aufgabe *

Es sei ${}\Gamma \subseteq L^{\rm {Ar}}$ eine arithmetische Ausdrucksmenge und ${}R\subseteq \mathbb {N}$ eine Relation. Es seien ${}\alpha ,\beta \in L^{\rm {Ar}}$ Ausdrücke in einer freien Variablen ${}x$. Zeige, dass aus

$\Gamma \vdash \alpha \leftrightarrow \beta$

nicht folgt, dass ${}\alpha$ in ${}\Gamma$ die Relation ${}R$ genau dann repräsentiert, wenn ${}\beta$ in ${}\Gamma$ die Relation ${}R$ repräsentiert.