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

Übungsaufgaben

Aufgabe Referenznummer erstellen

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

Aufgabe * Referenznummer erstellen

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

Aufgabe Referenznummer erstellen

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 Referenznummer erstellen

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

Aufgabe * Aufgabe 12.5 ändern

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'=(x+y)'{\text{ für alle }}x,y\in \mathbb {N}$

eindeutig bestimmt ist.

Aufgabe Aufgabe 12.6 ändern

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 Referenznummer erstellen

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 Referenznummer erstellen

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 Referenznummer erstellen

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 Aufgabe 12.10 ändern

Es sei ${}(\mathbb {N} ,0,')$ 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'=x\cdot y+x{\text{ für alle }}x,y\in \mathbb {N}$

eindeutig bestimmt ist.

Aufgabe Referenznummer erstellen

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

${}Q(0)=0\,$

und

${}Q(n')=Q(n)+n+n+1\,.$

Zeige

${}Q(n)=n\cdot n\,.$

Aufgabe * Referenznummer erstellen

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 Referenznummer erstellen

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\leq \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 }\neq n$, derart gibt, dass ${}nRn^{\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 Referenznummer erstellen

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

Aufgabe Referenznummer erstellen

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)Referenznummer erstellen

Es sei ${}A=\{0,1,2,3,4,5,6,7,8,9\}$ das Ziffernalphabet. Definiere die Teilmenge ${}N\subseteq A^{*}$, 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)Aufgabe 12.17 ändern

Es sei ${}(\mathbb {N} ,0,')$ 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'$ ist das neutrale Element für die Multiplikation.

3. ${}k'\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\neq 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)Referenznummer erstellen

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 (3 Punkte)Referenznummer erstellen

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

Fußnoten