Kurs:Einführung in die mathematische Logik (Osnabrück 2018)/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
{}
{

Im Kalkül der Prädikatenlogik sei
\mathl{\vdash \alpha \rightarrow \beta}{} \definitionsverweis {ableitbar}{}{.} Zeige, dass dann auch
\mathdisp {\vdash \exists x \alpha \rightarrow \exists x \beta} { }
ableitbar ist.

}
{} {}

\inputaufgabe
{}
{

Zeige, dass in der Prädikatenlogik
\mathdisp {\vdash \exists x \alpha \leftrightarrow \exists x \neg \neg \alpha} { }
\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.

}
{} {}