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

\setcounter{section}{12}

\zwischenueberschrift{Übungsaufgaben}

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

}
{} {}

\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} {.} {?}}

}
{} {}

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

}
{} {}