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

Übungsaufgaben

Aufgabe *

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

Aufgabe

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

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 *

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

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

Zeige, dass in der arithmetischen Sprache erster Stufe mit den Konstanten ${}0,1$, dem Nachfolgersymbol ${}N$ und den zweistelligen Funktionssymbolen ${}+$ und ${}\cdot$ nur abzählbar viele Teilmengen von ${}\mathbb {N}$ „adressierbar“ sind und dass daher das zweitstufige Induktionsaxiom der Dedekind-Peano-Axiome nicht in dieser Sprache formulierbar ist.

Aufgabe

Zeige, dass man für jede Teilmenge ${}T\subseteq \mathbb {N}$ die arithmetische Sprache erster Stufe um ein einstelliges Relationssymbol ${}R_{T}$ und die erststufigen Peano-Axiome um geeignete Axiome ergänzen kann, derart, dass diese neue Axiomatik in der Standardinterpretation ${}\mathbb {N}$ genau dann gilt, wenn ${}R_{T}$ als ${}T$ interpretiert wird. Man folgere daraus, dass mit überabzählbar vielen Relationssymbolen alle Teilmengen der natürlichen Zahlen „adressierbar“ sind.

(Dies bedeutet aber weder, dass für jede Struktur einer solchen Axiomatik jede Teilmenge adressierbar ist, noch, dass das zweitstufige Induktionsaxiom, das eine Aussage über alle Teilmengen macht, erststufig formulierbar ist).

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

Wir erinnern an die Definition eines algebraisch abgeschlossenen Körpers. Die komplexen Zahlen ${}{\mathbb {C} }$ sind algebraisch abgeschlossen (Fundamentalsatz der Algebra), die reellen Zahlen ${}\mathbb {R}$ nicht.

Ein Körper ${}K$ heißt algebraisch abgeschlossen, wenn jedes nichtkonstante Polynom ${}F\in K[X]$ eine Nullstelle in ${}K$ besitzt.

Aufgabe

Definiere über der Symbolmenge ${}\{0,1,+,\cdot \}$ einen algebraisch abgeschlossenen Körper mit Hilfe eines Axiomenschemas.

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^{*}$, 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,')$ 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 (4 Punkte)

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