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

Übungsaufgaben

Aufgabe Referenznummer erstellen

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

Aufgabe Referenznummer erstellen

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 * Referenznummer erstellen

Zeige, dass die Gleichheit von natürlichen Zahlen (also die Diagonalrelation in ${}\mathbb {N} ^{2}$ ) durch den Ausdruck ${}x=y$ in der erststufigen Peano-Arithmetik repräsentierbar ist.

Aufgabe Referenznummer erstellen

Es sei ${}\Gamma \subseteq L^{\rm {Ar}}$ das Axiomensystem eines kommutativen Halbringes. Zeige, dass die Gleichheit von natürlichen Zahlen (also die Diagonalrelation in ${}\mathbb {N} ^{2}$ ) durch den Ausdruck ${}x=y$ in ${}\Gamma$ nicht repräsentiert wird.

Aufgabe Referenznummer erstellen

Es sei ${}\Gamma \subseteq L^{\rm {Ar}}$ das Axiomensystem eines kommutativen Halbringes. Zeige, dass ${}\Gamma$ keine Repräsentierungen erlaubt.

Insbesondere erlauben die erststufigen Peano-Axiome ohne das Induktionsschema keine Repräsentierungen.

Aufgabe Referenznummer erstellen

Es sei ${}k\in \mathbb {N}$ und sei

{}\alpha :=\exists y(y+\cdots +y=x)\,,

wobei ${}k$ -mal der Summand ${}y$ vorkommt. Zeige, dass ${}\mathbb {N} k\subseteq \mathbb {N}$ , also die Menge der Vielfachen von ${}k$ , in der erststufigen Peano-Arithmetik durch ${}\alpha$ 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 ${}\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 * Referenznummer erstellen

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 * Referenznummer erstellen

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.

Aufgabe Referenznummer erstellen

Es sei ${}s_{1},s_{2},s_{3},\ldots$ 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.

${}s_{1}s_{2}s_{1}s_{3}s_{3}s_{2}$ ,
${}s_{13}s_{12}s_{1}s_{4}s_{4}s_{4}$ ,
${}s_{2}s_{2}s_{2}s_{2}s_{2}s_{2}$ ,
${}2^{1}3^{3}5^{17}7^{1}$ ,
${}2^{1}3^{1}5^{1}7^{1}11^{1}$ ,
${}2^{3}3^{3}5^{3}7^{3}11^{3}$ ,
${}1728$ .

Aufgabe Referenznummer erstellen

Es sei ${}n\in \mathbb {N}$ eine fixierte natürliche Zahl und

{}\alpha (x):=x=n\,,

wobei ${}n$ durch die ${}n$ -fache Summe der ${}1$ mit sich selbst realisiert werde. Zeige direkt, dass es Sätze ${}p,q\in L_{0}^{\rm {Ar}}$ mit

\vdash \alpha (GN(p))\leftrightarrow p

und mit

\vdash \neg \alpha (GN(q))\leftrightarrow q

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 ${}s_{1},s_{2},s_{3},\ldots$ 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.

${}s_{3}s_{2}s_{1}s_{1}s_{2}s_{3}$ ,
${}s_{20}s_{17}s_{1}s_{4}s_{19}$ ,
${}2^{1}3^{2}5^{3}7^{4}11^{5}$ ,
${}10!$ .

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

f\colon \mathbb {N} \longrightarrow \mathbb {N}

eine Polynomfunktion mit ${}f(n)=a_{d}n^{d}+a_{d-1}n^{d-1}+\cdots +a_{1}n+a_{0}$ mit Koeffizienten ${}a_{i}\in \mathbb {N}$ . Zeige, dass ${}f$ durch den Ausdruck ${}y=a_{d}x^{d}+a_{d-1}x^{d-1}+\cdots +a_{1}x+a_{0}$ in der erststufigen Peano-Arithmetik repräsentiert wird.

Aufgabe (6 Punkte)Aufgabe 22.17 ändern

Es sei ${}\Gamma$ eine korrekte entscheidbare arithmetische Ausdrucksmenge, die die Peano-Arithmetik umfasse. Es sei ${}\alpha (x)$ das Ableitungsprädikat zu ${}\Gamma$ und es sei ${}q$ ein Fixpunkt zum negierten Ableitungsprädikat, also