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

Übungsaufgaben

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 Primzahlen in der erststufigen Peano-Arithmetik repräsentiert werden kann.

Aufgabe

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.