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

\setcounter{section}{13}

\zwischenueberschrift{Übungsaufgaben}

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

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

Zeige, dass in einem \definitionsverweis {Peano-Halbring}{}{} die Addition assoziativ ist.

}
{} {}

\inputaufgabe
{}
{

Zeige, dass in einem \definitionsverweis {Peano-Halbring}{}{} die Multiplikation kommutativ und assoziativ ist und dass $1$ das neutrale Element ist.

}
{} {}

\inputaufgabegibtloesung
{}
{

Man gebe ein Beispiel für einen \definitionsverweis {kommutativen Halbring}{}{,} der kein \definitionsverweis {Peano-Halbring}{}{} ist.

}
{} {}

\inputaufgabe
{}
{

Zeige, dass in einem \definitionsverweis {Peano-Halbring}{}{} die Kürzungseigenschaft gilt, d.h. dass aus $xz=yz$ mit
\mathl{z \neq 0}{} die Gleichheit
\mathl{x=y}{} folgt.

}
{} {}

\inputaufgabe
{}
{

Zeige, dass in einem \definitionsverweis {Peano-Halbring}{}{} die Ordnungsrelation mit der Addition und der Multiplikation verträglich ist.

}
{} {}

\inputaufgabe
{}
{

Zeige, dass in einem \definitionsverweis {Peano-Halbring}{}{} der Ausdruck
\mathdisp {\forall x \forall y { \left( x \leq y \wedge y \leq x+1 \rightarrow { \left( y = x \vee y = x+1 \right) } \right) }} { }
gilt.

}
{} {}

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

}
{} {}

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

}
{} {}

\inputaufgabe
{}
{

Zeige, dass die Division mit Rest aus der Menge der \definitionsverweis {erststufigen Peano-Axiome}{}{} \definitionsverweis {ableitbar}{}{} ist.

}
{} {}

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

}
{} {}

\zwischenueberschrift{Aufgaben zum Abgeben}

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

Es sei $\N$ ein \definitionsverweis {Peano-Dedekind-Modell}{}{} der natürlichen Zahlen und $M$ ein \definitionsverweis {Peano-Halbring}{}{.} Zeige, dass es eine eindeutig bestimmte Abbildung \maabbdisp {\varphi} {\N} {M } {} mit
\mathl{\varphi(0)=0}{} und
\mathl{\varphi(n')= \varphi(n) + 1}{} gibt. Zeige ferner, dass $\varphi$ \definitionsverweis {injektiv}{}{} ist und die Addition und die Multiplikation respektiert.

}
{} {}

\inputaufgabe
{}
{

Zeige, dass in einem \definitionsverweis {Peano-Halbring}{}{} das Distributivgesetz gilt.

}
{} {}

\inputaufgabe
{}
{

Zeige, dass $\R_{\geq 0}$ mit
\mathl{0,1}{} und der natürlichen Addition und Multiplikation die ersten sechs \definitionsverweis {Peano-Axiome}{}{} erfüllt, aber nicht das Induktionsaxiom.

}
{} {}