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

Übungsaufgaben

Aufgabe

Es sei ${}\mathbb {N}$ die Menge der natürlichen Zahlen und ${}n\in \mathbb {N}$. Zeige, dass die Menge

${}\mathbb {N} _{\geq n}={\left\{x\in \mathbb {N} \mid x\geq n\right\}}\,$

ebenfalls die Dedekind-Peano-Axiome (mit welchem ausgezeichneten Element und mit welcher Nachfolgerabbildung?) erfüllt.

Aufgabe

Es seien ${}N_{1}$ und ${}N_{2}$ Dedekind-Peano-Modelle der natürlichen Zahlen. Es sei

$\varphi \colon N_{1}\longrightarrow N_{2}$

der eindeutig bestimmte Isomorphismus mit ${}\varphi (0_{1})=0_{2}$ und ${}\varphi (n')=(\varphi (n))'$ für alle ${}n\in N_{1}$. Zeige, dass ${}\varphi$ die Addition respektiert, dass also

${}\varphi (m+n)=\varphi (m)+\varphi (n)\,$

für alle ${}m,n\in N_{1}$ gilt.

Aufgabe

Zeige, dass in einem Peano-Halbring die Addition assoziativ ist.

Aufgabe

Zeige, dass in einem Peano-Halbring die Multiplikation kommutativ und assoziativ ist und dass ${}1$ das neutrale Element ist.

Aufgabe *

Man gebe ein Beispiel für einen kommutativen Halbring, der kein Peano-Halbring ist.

Aufgabe

Zeige, dass in einem Peano-Halbring die Kürzungseigenschaft gilt, d.h. dass aus ${}xz=yz$ mit ${}z\neq 0$ die Gleichheit ${}x=y$ folgt.

Aufgabe

Zeige, dass in einem Peano-Halbring die Ordnungsrelation mit der Addition und der Multiplikation verträglich ist.

Aufgabe

Zeige, dass in einem Peano-Halbring der Ausdruck

$\forall x\forall y{\left(x\leq y\wedge y\leq x+1\rightarrow {\left(y=x\vee y=x+1\right)}\right)}$

gilt.

Aufgabe

Zeige, dass in einer Struktur, die die Peano-Axiome für den Nachfolger erfüllt, die Aussage

$\forall x{\left(x=0\vee x=N0\vee \exists y{\left(NNy=x\right)}\right)}$

gilt.

Aufgabe

Es sei ${}M$ die disjunkte Vereinigung aus ${}\mathbb {N}$ und aus ${}\mathbb {Z}$. Wir definieren auf ${}M$ eine Nachfolgerfunktion, die auf den beiden Bestandteilen durch den üblichen Nachfolger gegeben ist (also durch ${}+1$), und wir betrachten die ${}0\in \mathbb {N}$ als die Null von ${}M$.

a) Zeige, dass ${}M$ die ersten beiden Axiome aus den erststufigen Peano-Axiomen für die Nachfolgerfunktion erfüllt.

b) Zeige, dass es keine Addition auf ${}M$ gibt, die mit den Additionen auf ${}\mathbb {N}$ und auf ${}\mathbb {Z}$ übereinstimmt und für die die Abziehregel gilt.

c) Gilt das erststufige Induktionsaxiom (formuliert für die Nachfolgerfunktion)?

Aufgabe

Zeige, dass die Vorgängereigenschaft

$\forall x{\left(x\neq 0\rightarrow \exists y(x=y+1)\right)}$

aus der Menge der erststufigen Peano-Axiome ableitbar ist.

Aufgabe

Zeige, dass die Division mit Rest aus der Menge der erststufigen Peano-Axiome ableitbar ist.

Aufgabe

Betrachte die Produktmenge ${}\mathbb {N} \times \mathbb {N}$ mit der Nachfolgerfunktion

${}(a,b)':=(a,b')\,$

und der sogenannten lexikographische Ordnung, für die

$(a_{1},b_{1})\leq (a_{2},b_{2})$

genau dann gilt, wenn ${}a_{1}<a_{2}$ oder ${}a_{1}=a_{2}$ und ${}b_{1}\leq b_{2}$ ist. Zeige folgende Aussagen.

1. Es handelt sich um eine totale Ordnung.
2. Es ist

   ${}x'\geq x\,$

   für alle ${}x\in \mathbb {N} \times \mathbb {N}$.

3. ${}(0,0)$ ist das kleinste Element.
4. Es liegt eine Wohlordnung (nach unten) vor.
5. Diese Menge mit der Nachfolgerfunktion erfüllt nicht das Dedekind-Peano-Induktionsaxiom

Aufgaben zum Abgeben

Aufgabe (3 Punkte)

Es seien ${}N_{1}$ und ${}N_{2}$ Dedekind-Peano-Modelle der natürlichen Zahlen. Es sei

$\varphi \colon N_{1}\longrightarrow N_{2}$

der eindeutig bestimmte Isomorphismus mit ${}\varphi (0_{1})=0_{2}$ und ${}\varphi (n')=(\varphi (n))'$ für alle ${}n\in N_{1}$. Zeige, dass ${}\varphi$ die Multiplikation respektiert, dass also

${}\varphi (m\cdot n)=\varphi (m)\cdot \varphi (n)\,$

für alle ${}m,n\in N_{1}$ gilt.

Aufgabe (4 Punkte)

Es sei ${}\mathbb {N}$ ein Peano-Dedekind-Modell der natürlichen Zahlen und ${}M$ ein Peano-Halbring. Zeige, dass es eine eindeutig bestimmte Abbildung

$\varphi \colon \mathbb {N} \longrightarrow M$

mit ${}\varphi (0)=0$ und ${}\varphi (n')=\varphi (n)+1$ gibt. Zeige ferner, dass ${}\varphi$ injektiv ist und die Addition und die Multiplikation respektiert.

Aufgabe (4 Punkte)

Zeige, dass in einem Peano-Halbring das Distributivgesetz gilt.

Aufgabe (3 Punkte)

Zeige, dass ${}\mathbb {R} _{\geq 0}$ mit ${}0,1$ und der natürlichen Addition und Multiplikation die ersten sechs Peano-Axiome erfüllt, aber nicht das Induktionsaxiom.

Fußnoten