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

Übungsaufgaben

Aufgabe

Definiere auf der Menge der Wörter zum einelementigen Alphabet $A=\{\mid \}$ ein Dedekind-Peano-Modell. Worauf beruht die Gültigkeit der Dedekind-Peano-Axiome?

Aufgabe *

Zeige ausgehend von den Dedekind-Peano-Axiomen, dass jedes Element $n\in \mathbb{N}$, $n\ne 0$, einen Vorgänger besitzt.

Aufgabe

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

${\mathbb{N}}_{\ge n}=\{x\in \mathbb{N}\mid x\ge n\}$

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

Aufgabe

Man gebe Beispiele $(M,0{,}^{\prime })$ für Mengen mit einem ausgezeichneten Element $0\in M$ und einer Abbildung $\text{'}:M\to M$ an, die je zwei der Dedekind-Peano-Axiome erfüllen, aber nicht das dritte.

Aufgabe *

Es sei $(\mathbb{N},0{,}^{\prime })$ ein Dedekind-Peano-Modell der natürlichen Zahlen. Zeige, dass die Addition durch die Bedingungen

$x+0=x\text{ für alle }x\in \mathbb{N}\text{ und }x+y^{\prime }=(x+y{)}^{\prime }\text{ für alle }x,y\in \mathbb{N}$

eindeutig bestimmt ist.

Aufgabe

Zeige, dass die Addition auf den natürlichen Zahlen kommutativ und assoziativ ist und dass die Abziehregel (d.h., dass aus $n+k=m+k$ für ein $k$ stets $n=m$ folgt) gilt.

Aufgabe

Es seien $N_1$ und $N_2$ Dedekind-Peano-Modelle der natürlichen Zahlen. Es sei

$\phi :N_1⟶N_2$

der eindeutig bestimmte Isomorphismus mit  $\phi (0_1)=0_2$  und  $\phi (n^{\prime })=(\phi (n){)}^{\prime }$  für alle $n\in N_1$. Zeige, dass $\phi$ die Addition respektiert, dass also

$\phi (m+n)=\phi (m)+\phi (n)$

für alle $m,n\in N_1$ gilt.

Aufgabe

Wie verhält sich die über die Nachfolgerbeziehung eingeführte Addition auf den natürlichen Zahlen (das Umlegungsmodell) zu dem Vereinigungsmodell, dass die Summe $a+b$ zweier natürlichen Zahlen sich als Anzahl von Objekten (Äpfel) ergibt, wenn man eine Menge von $a$ Objekten und eine Menge von (dazu disjunkten) $b$ Objekten zusammenschmeißt.

Aufgabe

Begründe, dass die Addition von natürlichen Zahlen im Dezimalsystem (das schriftliche Addieren) das Umlegungsprinzip respektiert und auch die $0$ richtig verarbeitet. Schließe daraus, dass die schriftliche Addition korrekt ist.

Aufgabe

Es sei $(\mathbb{N},0{,}^{\prime })$ ein Dedekind-Peano-Modell der natürlichen Zahlen. Zeige, dass die Multiplikation durch die Bedingungen

$x\cdot 0=0\text{ für alle }x\in \mathbb{N}\text{ und }x\cdot y^{\prime }=x\cdot y+x\text{ für alle }x,y\in \mathbb{N}$

eindeutig bestimmt ist.

Aufgabe

Definiere auf einem Dedekind-Peano-Modell $(\mathbb{N},0{,}^{\prime })$ für die natürlichen Zahlen die Abbildung $Q:\mathbb{N}\to \mathbb{N}$ rekursiv durch die Bedingungen (die Addition sei mit den wesentlichen Eigenschaften etabliert)

$Q(0)=0$

und

$Q(n^{\prime })=Q(n)+n+n+1.$

Zeige

$Q(n)=n\cdot n.$

Aufgabe *

1. Bestimme die kleinste natürliche Zahl, die größer als die ersten drei Quadratzahlen ist.
2. Beschreibe die Bedingung (und zwar so, dass die Bedingung erkennbar ist) aus (1) durch einen prädikatenlogischen arithmetischen Ausdruck (also mit dem Symbolalphabet $+,\cdot ,0,1$ und Variablen) in der einen freien Variablen $x$.
3. Beschreibe das Ergebnis aus (1) durch einen einfachen prädikatenlogischen Ausdruck in der einen freien Variablen $x$.

Aufgabe

Wir definieren auf ${\mathbb{N}}_{+}$ eine neue Relation $R$ durch folgende Vorschrift: Für zwei Zahlen  $n,m\in {\mathbb{N}}_{+}$  mit  $n=2^{k}t$  und  $m=2^{\ell }u$  mit $t,u$ ungerade sei

$nRm\text{ falls }t<u\text{ gilt oder falls zugleich }t=u\text{ und }k\le \ell \text{ gilt}$

(rechts wird auf die natürliche Ordnung in $\mathbb{N}$ Bezug genommen).

1. Zeige, dass $R$ eine totale Ordnung auf ${\mathbb{N}}_{+}$ ergibt und beschreibe exemplarisch diese Ordnung.
2. Zeige, dass es zu jedem  $n\in {\mathbb{N}}_{+}$  ein wohldefiniertes Element $n^{\star }\in {\mathbb{N}}_{+}$, $n^{\star }\ne n$, derart gibt, dass $nR{n}^{\star }$ gilt und dass es zwischen $n$ und $n^{\star }$ keine weiteren Elemente gibt (diese Formulierung ist zu präzisieren).
3. Erfüllt die Menge $({\mathbb{N}}_{+},1,\star )$ die Dedekind-Peano-Axiome?

Aufgabe

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

$(a,b{)}^{\prime }:=(a,b^{\prime })$

und der sogenannten lexikographische Ordnung, für die

$(a_1,b_1)\le (a_2,b_2)$

genau dann gilt, wenn $a_1<a_2$ oder $a_1=a_2$ und $b_1\le b_2$ ist. Zeige folgende Aussagen.

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

   $x^{\prime }\ge 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

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)?

Aufgaben zum Abgeben

Aufgabe (5 Punkte)

Es sei $A=\{0,1,2,3,4,5,6,7,8,9\}$ das Ziffernalphabet. Definiere die Teilmenge $N\subseteq A^{\ast }$, die aus den korrekt gebildeten Zifferndarstellungen einer natürlichen Zahl besteht. Definiere auf $N$ eine Nachfolgerabbildung und zeige, dass $N$ zu einem Dedekind-Peano-Modell wird. Worauf beruht die Gültigkeit der Dedekind-Peano-Axiome?

Aufgabe (7 Punkte)

Es sei $(\mathbb{N},0{,}^{\prime })$ ein Dedekind-Peano-Modell der natürlichen Zahlen mit der in Definition 12.7 festgelegten Multiplikation. Zeige die folgenden Aussagen.

1. $0\cdot n=0=n\cdot 0$

   für alle $n$.

2. $1\cdot n=n=n\cdot 1$

   für alle $n$, d.h.  $1=0^{\prime }$  ist das neutrale Element für die Multiplikation.

3. $k^{\prime }\cdot n=k\cdot n+n$

   für alle  $n,k\in \mathbb{N}$. 

4. Die Multiplikation ist kommutativ.
5. Die Multiplikation ist assoziativ.
6. Aus einer Gleichung  $n\cdot k=m\cdot k$  mit  $k\ne 0$  folgt  $n=m$  (Kürzungsregel).
7. Für beliebige  $k,m,n\in \mathbb{N}$  gilt

   $k\cdot (m+n)=k\cdot m+k\cdot n$

   (Distributivgesetz).

Aufgabe (3 Punkte)

Es seien $N_1$ und $N_2$ Dedekind-Peano-Modelle der natürlichen Zahlen. Es sei

$\phi :N_1⟶N_2$

der eindeutig bestimmte Isomorphismus mit  $\phi (0_1)=0_2$  und  $\phi (n^{\prime })=(\phi (n){)}^{\prime }$  für alle $n\in N_1$. Zeige, dass $\phi$ die Multiplikation respektiert, dass also

$\phi (m\cdot n)=\phi (m)\cdot \phi (n)$

für alle $m,n\in N_1$ gilt.

Aufgabe (3 Punkte)

Es sei $(N,0{,}^{\prime })$ ein Dedekind-Peano-Modell der natürlichen Zahlen. Zeige, dass das erststufige Axiomenschema für die Induktion in $N$ gilt.

Fußnoten