Kurs:Einführung in die mathematische Logik (Osnabrück 2016)/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 *

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

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

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

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

Zeige, dass die Menge der Quadratzahlen in der erststufigen Peano-Arithmetik repräsentiert werden kann.

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 *

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.

Aufgabe

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.

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

Aufgabe

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)

Zeige, dass die Menge der Primzahlen in der erststufigen Peano-Arithmetik repräsentiert werden kann.

Aufgabe (4 Punkte)

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.

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

Aufgabe * (4 Punkte)

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

Aufgabe (6 Punkte)

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)

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

$\Gamma \vdash \neg \alpha (GN(q))\leftrightarrow q.$

Zeige, dass aus den in Bemerkung 23.7 angeführten Eigenschaften man

$\Gamma \vdash \neg \alpha (GN(p\wedge \neg p))\rightarrow \neg \alpha (GN(q))$

erhalten kann, wobei ${}p$ ein beliebiger Ausdruck ist.