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^{\mathrm{A}\mathrm{r}}$ 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^{\mathrm{A}\mathrm{r}}$ 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 :=\mathrm{\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:\mathbb{N}⟶\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.