Kurs:Einführung in die mathematische Logik (Osnabrück 2021)/Arbeitsblatt 12/latex
\setcounter{section}{12}
\zwischenueberschrift{Übungsaufgaben}
\inputaufgabe
{}
{
Erläutere Vor- und Nachteile des axiomatischen Aufbaus der Mathematik.
}
{} {}
\inputaufgabe
{}
{
Definiere auf der Menge der Wörter zum einelementigen Alphabet
\mathl{A=\{ {{|}} \}}{} ein
\definitionsverweis {Dedekind-Peano-Modell}{}{.}
Worauf beruht die Gültigkeit der Dedekind-Peano-Axiome?
}
{} {}
\inputaufgabegibtloesung
{}
{
Zeige ausgehend von den
\definitionsverweis {Dedekind-Peano-Axiomen}{}{,}
dass jedes Element
\mathl{n \in {\mathbb N}}{,} $n \neq 0$, einen Vorgänger besitzt.
}
{} {}
\inputaufgabe
{}
{
Es sei $\N$ die Menge der natürlichen Zahlen und $n \in \N$. Zeige, dass die Menge
\mavergleichskettedisp
{\vergleichskette
{ \N_{\geq n }
}
{ =} {{ \left\{ x \in \N \mid x \geq n \right\} }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
ebenfalls die
\definitionsverweis {Dedekind-Peano-Axiome}{}{}
\zusatzklammer {mit welchem ausgezeichneten Element und mit welcher Nachfolgerabbildung} {?} {}
erfüllt.
}
{} {}
\inputaufgabe
{}
{
Man gebe Beispiele $(M,0,')$ für Mengen mit einem ausgezeichneten Element $0 \in M$ und einer Abbildung \maabb {'} {M} {M } {} an, die je zwei der \definitionsverweis {Dedekind-Peano-Axiome}{}{} erfüllen, aber nicht das dritte.
}
{} {}
\inputaufgabe
{}
{
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {NachfolgermitSchleife.png} }
\end{center}
\bildtext {} }
\bildlizenz { NachfolgermitSchleife.png } {} {Mgausmann} {Commons} {CC-by-sa 4.0} {}
Es sei
\mavergleichskette
{\vergleichskette
{N_1
}
{ = }{(\N, 0, \prime)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und es sei $N_2$ die rechts angegebene Menge mit dem Startsymbol oben links und der durch die Pfeile ausgedrückten Nachfolgerabbildung. An welcher Stelle bricht der Beweis von
Satz 12.3
in dieser Situation zusammen?
}
{} {}
\inputaufgabe
{}
{
Es sei $n$ eine natürliche Zahl. Auf wie viele Arten kann $n$ als eine Summe von zwei natürlichen Zahlen dargestellt werden? Inwiefern muss man diese Fragestellung präzisieren?
}
{} {}
\inputaufgabe
{}
{
Wir zählen
\mathdisp {\text{ heute},\, \text{ morgen},\, \text{ übermorgen}, \, \text{überübermorgen}, \, \text{überüberübermorgen}, \ldots} { }
und wollen mit diesen Zahlen addieren.
\aufzaehlungfuenf{Welche alltagssprachliche Formulierung besitzt die Addition in diesem Zählmodell?
}{Welche sprachlichen Formulierungen drücken aus, das heute das neutrale Element der Addition ist.
}{Was ist morgen plus morgen?
}{Was ist übermorgen plus übermorgen?
}{Was ist überübermorgen plus überüberübermorgen?
}
}
{} {}
\inputaufgabegibtloesung
{}
{
Wir zählen
\mathdisp {\text{ ich},\, \text{ Mama},\, \text{ Oma}, \, \text{Uroma}, \, \text{Ururoma}, \ldots} { . }
\aufzaehlungvier{Was ist die Mama der Urururoma?
}{Was ist die Uroma der Uroma?
}{Was ist die Oma der Oma der Oma?
}{Was ist die Ururoma der Uroma?
}
}
{} {}
\inputaufgabegibtloesung
{}
{
Es sei
\mathl{(\N,0,^\prime)}{} ein
\definitionsverweis {Dedekind-Peano-Modell}{}{}
der natürlichen Zahlen. Zeige, dass die Addition durch die Bedingungen
\mathdisp {x + 0 =x \text { für alle } x \in \N \text{ und } x + y' = (x + y )' \text { für alle } x,y \in \N} { }
eindeutig bestimmt ist.
}
{} {}
\inputaufgabe
{}
{
Zeige, dass die \definitionsverweis {Addition}{}{} auf den natürlichen Zahlen \definitionsverweis {kommutativ}{}{} und \definitionsverweis {assoziativ}{}{} ist und dass die Abziehregel \zusatzklammer {d.h., dass aus $n+k=m+k$ für ein $k$ stets $n= m$ folgt} {} {} gilt.
}
{} {}
\inputaufgabe
{}
{
Es seien
\mathkor {} {N_1} {und} {N_2} {}
\definitionsverweis {Dedekind-Peano-Modelle}{}{}
der natürlichen Zahlen. Es sei
\maabbdisp {\varphi} {N_1} {N_2
} {}
der eindeutig bestimmte Isomorphismus mit
\mavergleichskette
{\vergleichskette
{\varphi(0_1)
}
{ = }{0_2
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{ \varphi(n')
}
{ = }{ (\varphi(n))'
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
für alle $n \in N_1$. Zeige, dass $\varphi$ die Addition respektiert, dass also
\mavergleichskettedisp
{\vergleichskette
{ \varphi (m+n)
}
{ =} { \varphi(m) + \varphi(n)
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
für alle
\mathl{m,n \in N_1}{} gilt.
}
{} {}
\inputaufgabe
{}
{
Wie verhält sich die über die Nachfolgerbeziehung eingeführte
\definitionsverweis {Addition}{}{}
auf den natürlichen Zahlen
\zusatzklammer {das \stichwort {Umlegungsmodell} {}} {} {}
zu dem \stichwort {Vereinigungsmodell} {,} dass die Summe
\mathl{a+b}{} zweier natürlichen Zahlen sich als Anzahl von Objekten
\zusatzklammer {Äpfel} {} {}
ergibt, wenn man eine Menge von $a$ Objekten und eine Menge von
\zusatzklammer {dazu disjunkten} {} {}
$b$ Objekten zusammenschmeißt.
}
{} {}
\inputaufgabe
{}
{
Begründe, dass die Addition von natürlichen Zahlen im Dezimalsystem \zusatzklammer {das \stichwort {schriftliche Addieren} {}} {} {} das \definitionsverweis {Umlegungsprinzip}{}{} respektiert und auch die $0$ richtig verarbeitet. Schließe daraus, dass die schriftliche Addition korrekt ist.
}
{} {}
\inputaufgabe
{}
{
Es sei $(\N,0,')$ ein
\definitionsverweis {Dedekind-Peano-Modell}{}{}
der natürlichen Zahlen. Zeige, dass die Multiplikation durch die Bedingungen
\mathdisp {x \cdot 0=0 \text { für alle } x \in \N \text{ und } x \cdot y' = x \cdot y +x \text { für alle } x,y \in \N} { }
eindeutig bestimmt ist.
}
{} {}
\inputaufgabe
{}
{
Definiere auf einem
\definitionsverweis {Dedekind-Peano-Modell}{}{}
\mathl{(\N,0,^\prime)}{} für die natürlichen Zahlen die Abbildung
\maabb {Q} {\N} {\N
} {}
rekursiv durch die Bedingungen
\zusatzklammer {die Addition sei mit den wesentlichen Eigenschaften etabliert} {} {}
\mavergleichskettedisp
{\vergleichskette
{Q(0)
}
{ =} {0
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
und
\mavergleichskettedisp
{\vergleichskette
{Q(n')
}
{ =} { Q(n) +n+n+1
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Zeige
\mavergleichskettedisp
{\vergleichskette
{Q(n)
}
{ =} {n \cdot n
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
}
{} {}
\inputaufgabegibtloesung
{}
{
\aufzaehlungdrei{Bestimme die kleinste natürliche Zahl, die größer als die ersten drei Quadratzahlen ist.
}{Beschreibe die Bedingung
\zusatzklammer {und zwar so, dass die Bedingung erkennbar ist} {} {}
aus (1) durch einen prädikatenlogischen arithmetischen Ausdruck
\zusatzklammer {also mit dem Symbolalphabet
\mathl{+,\cdot,0,1}{} und Variablen} {} {}
in der einen freien Variablen $x$.
}{Beschreibe das Ergebnis aus (1) durch einen einfachen prädikatenlogischen Ausdruck in der einen freien Variablen $x$.
}
}
{} {}
\inputaufgabe
{}
{
Wir definieren auf $\N_+$ eine neue
\definitionsverweis {Relation}{}{}
$R$ durch folgende Vorschrift: Für zwei Zahlen
\mavergleichskette
{\vergleichskette
{ n,m
}
{ \in }{ \N_+
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit
\mavergleichskette
{\vergleichskette
{ n
}
{ = }{ 2^kt
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{ m
}
{ = }{ 2^\ell u
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit $t,u$ ungerade sei
\mathdisp {n R m \text{ falls } t < u \text{ gilt oder falls zugleich } t=u \text{ und } k \leq \ell \text{ gilt}} { }
\zusatzklammer {rechts wird auf die natürliche Ordnung in $\N$ Bezug genommen} {} {.}
\aufzaehlungdrei{Zeige, dass $R$ eine
\definitionsverweis {totale Ordnung}{}{}
auf $\N_+$ ergibt und beschreibe exemplarisch diese Ordnung.
}{Zeige, dass es zu jedem
\mavergleichskette
{\vergleichskette
{ n
}
{ \in }{ \N_+
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ein wohldefiniertes Element
\mathbed {n^\star \in \N_+} {}
{n^\star \neq n} {}
{} {} {} {,}
derart gibt, dass $nRn^\star$ gilt und dass es zwischen
\mathkor {} {n} {und} {n^\star} {}
keine weiteren Elemente gibt
\zusatzklammer {diese Formulierung ist zu präzisieren} {} {.}
}{Erfüllt die Menge $(\N_+,1,\star)$ die
\definitionsverweis {Dedekind-Peano-Axiome}{}{?}
}
}
{} {}
\inputaufgabe
{}
{
Betrachte die Produktmenge
\mathl{\N \times \N}{} mit der Nachfolgerfunktion
\mavergleichskettedisp
{\vergleichskette
{(a,b)'
}
{ \defeq} { (a,b')
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
und der sogenannten
\betonung{lexikographische Ordnung}{,} für die
\mathdisp {(a_1,b_1) \leq (a_2,b_2)} { }
genau dann gilt, wenn
\mathl{a_1 < a_2}{} oder
\mathl{a_1=a_2}{} und $b_1 \leq b_2$ ist. Zeige folgende Aussagen.
\aufzaehlungfuenf{Es handelt sich um eine
\definitionsverweis {totale Ordnung}{}{.}
}{Es ist
\mavergleichskettedisp
{\vergleichskette
{x'
}
{ \geq} {x
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
für alle
\mathl{x \in \N \times \N}{.}
}{
\mathl{(0,0)}{} ist das kleinste Element.
}{Es liegt eine
\definitionsverweis {Wohlordnung}{}{}
\zusatzklammer {nach unten} {} {}
vor.
}{Diese Menge mit der Nachfolgerfunktion erfüllt nicht das
\definitionsverweis {Dedekind-Peano-Induktionsaxiom}{}{}
}
}
{} {}
\inputaufgabe
{}
{
Es sei $M$ die \definitionsverweis {disjunkte Vereinigung}{}{} aus $\N$ und aus $\Z$\zusatzfussnote {Dabei muss man darauf achten, die Elemente aus $\N$ nicht mit denen aus $\Z_{\geq 0}$ zu verwechseln. Beispielsweise kann man die Elemente einerseits mit $5$ und andererseits mit $5_\Z$ bezeichnen} {.} {.} Wir definieren auf $M$ eine Nachfolgerfunktion, die auf den beiden Bestandteilen durch den üblichen Nachfolger gegeben ist \zusatzklammer {also durch $+1$} {} {,} und wir betrachten die $0 \in \N$ als die Null von $M$.
a) Zeige, dass $M$ die ersten beiden Axiome aus den \definitionsverweis {erststufigen Peano-Axiomen für die Nachfolgerfunktion}{}{} erfüllt.
b) Zeige, dass es keine Addition auf $M$ gibt, die mit den Additionen auf $\N$ und auf $\Z$ übereinstimmt und für die die Abziehregel gilt.
c) Gilt das \definitionsverweis {erststufige Induktionsaxiom}{}{} \zusatzklammer {formuliert für die Nachfolgerfunktion} {} {\zusatzfussnote {Diese Aufgabe ist wohl schwierig} {.} {?}}
}
{} {}
\inputaufgabe
{}
{
Zeige, dass in einer
\definitionsverweis {Struktur}{}{,}
die die
\definitionsverweis {Peano-Axiome für den Nachfolger}{}{}
erfüllt, die Aussage
\mathdisp {\forall x { \left( x = 0 \vee x = N 0 \vee \exists y { \left( NNy = x \right) } \right) }} { }
gilt.
}
{} {}
\inputaufgabegibtloesung
{}
{
Zeige, dass die Vorgängereigenschaft
\mathdisp {\forall x { \left( x \neq 0 \rightarrow \exists y (x = N y) \right) }} { }
aus der Menge der
\definitionsverweis {Peano-Axiome für den Nachfolger}{}{}
folgt.
}
{} {}
\inputaufgabe
{}
{
Zeige, dass die Vorgängereigenschaft
\mathdisp {\forall x { \left( x \neq 0 \rightarrow \exists y (x = y+1) \right) }} { }
aus der Menge der
\definitionsverweis {erststufigen Peano-Axiome}{}{}
\definitionsverweis {ableitbar}{}{}
ist.
}
{} {}
\zwischenueberschrift{Aufgaben zum Abgeben}
\inputaufgabe
{5}
{
Es sei $A=\{0,1,2,3,4,5,6,7,8,9\}$ das Ziffernalphabet. Definiere die Teilmenge
\mathl{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
\definitionsverweis {Dedekind-Peano-Modell}{}{}
wird. Worauf beruht die Gültigkeit der Dedekind-Peano-Axiome?
}
{} {}
\inputaufgabe
{7}
{
Es sei $(\N,0,')$ ein
\definitionsverweis {Dedekind-Peano-Modell}{}{}
der natürlichen Zahlen mit der in
Definition 12.7
festgelegten Multiplikation. Zeige die folgenden Aussagen.
\aufzaehlungsieben{
\mavergleichskettedisp
{\vergleichskette
{ 0 \cdot n
}
{ =} { 0
}
{ =} { n \cdot 0
}
{ } {
}
{ } {
}
}
{}{}{}
für alle $n$.}{
\mavergleichskettedisp
{\vergleichskette
{ 1 \cdot n
}
{ =} { n
}
{ =} { n \cdot 1
}
{ } {
}
{ } {
}
}
{}{}{}
für alle $n$, d.h.
\mavergleichskette
{\vergleichskette
{ 1
}
{ = }{ 0'
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist das
\definitionsverweis {neutrale Element}{}{}
für die Multiplikation.
}{
\mavergleichskettedisp
{\vergleichskette
{ k' \cdot n
}
{ =} { k \cdot n + n
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
für alle
\mavergleichskette
{\vergleichskette
{ n,k
}
{ \in }{ \N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}{Die Multiplikation ist
\definitionsverweis {kommutativ}{}{.}
}{Die Multiplikation ist
\definitionsverweis {assoziativ}{}{.}
}{Aus einer Gleichung
\mavergleichskette
{\vergleichskette
{ n \cdot k
}
{ = }{ m \cdot k
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit
\mavergleichskette
{\vergleichskette
{ k
}
{ \neq }{ 0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
folgt
\mavergleichskette
{\vergleichskette
{ n
}
{ = }{ m
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
\zusatzklammer {\stichwort {Kürzungsregel} {}} {} {.}
}{Für beliebige
\mavergleichskette
{\vergleichskette
{ k,m,n
}
{ \in }{ \N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gilt
\mavergleichskettedisp
{\vergleichskette
{ k \cdot (m+n)
}
{ =} { k \cdot m + k \cdot n
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
\zusatzklammer {Distributivgesetz} {} {.}
}
}
{} {}
\inputaufgabe
{3}
{
Es seien
\mathkor {} {N_1} {und} {N_2} {}
\definitionsverweis {Dedekind-Peano-Modelle}{}{}
der natürlichen Zahlen. Es sei
\maabbdisp {\varphi} {N_1} {N_2
} {}
der eindeutig bestimmte Isomorphismus mit
\mavergleichskette
{\vergleichskette
{\varphi(0_1)
}
{ = }{0_2
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{ \varphi(n')
}
{ = }{ (\varphi(n))'
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
für alle $n \in N_1$. Zeige, dass $\varphi$ die Multiplikation respektiert, dass also
\mavergleichskettedisp
{\vergleichskette
{ \varphi (m \cdot n)
}
{ =} { \varphi(m) \cdot \varphi(n)
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
für alle
\mathl{m,n \in N_1}{} gilt.
}
{} {}
\inputaufgabe
{3}
{
Es sei $(N,0,')$ ein \definitionsverweis {Dedekind-Peano-Modell}{}{} der natürlichen Zahlen. Zeige, dass das erststufige Axiomenschema für die Induktion in $N$ gilt.
}
{} {}