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

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

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

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

Es sei ${\displaystyle {}(\mathbb {N} ,0,^{\prime })}$ einDedekind-Peano-Modellder natürlichen Zahlen. Zeige, dass die Addition durch die Bedingungen

${\displaystyle 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.

Zeige, dass dieAdditionauf den natürlichen Zahlen kommutativund assoziativist und dass die Abziehregel(d.h., dass aus ${\displaystyle {}n+k=m+k}$ für ein ${\displaystyle {}k}$ stets ${\displaystyle {}n=m}$ folgt)gilt.

Es sei ${\displaystyle {}(\mathbb {N} ,0,')}$ ein Dedekind-Peano-Modellder natürlichen Zahlen. Zeige, dass die Multiplikation durch die Bedingungen

${\displaystyle 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.

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

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

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

${\displaystyle 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 ${\displaystyle {}\mathbb {N} }$ Bezug genommen).

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

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

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

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

Es sei ${\displaystyle {}(\mathbb {N} ,0,')}$ ein Dedekind-Peano-Modellder natürlichen Zahlen mit der inDefinition 12.7festgelegten Multiplikation. Zeige die folgenden Aussagen.

1. ${\displaystyle 0\cdot n=0=n\cdot 0}$

   für alle ${\displaystyle {}n}$.

2. ${\displaystyle 1\cdot n=n=n\cdot 1}$

   für alle ${\displaystyle {}n}$, d.h. ${\displaystyle {}1=0'}$ ist das neutrale Elementfür die Multiplikation.

3. ${\displaystyle k'\cdot n=k\cdot n+n}$

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

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

   ${\displaystyle k\cdot (m+n)=k\cdot m+k\cdot n}$

   (Distributivgesetz).

Es sei ${\displaystyle {}(N,0,')}$ ein Dedekind-Peano-Modellder natürlichen Zahlen. Zeige, dass das erststufige Axiomenschema für die Induktionin ${\displaystyle {}N}$ gilt.