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

\setcounter{section}{13}

\zwischenueberschrift{Übungsaufgaben}

\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 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 einem \definitionsverweis {Peano-Halbring}{}{} das \stichwort {Lemma von Bezout} {} in der Form gilt, dass es zu zwei teilerfremden \zusatzklammer {das ist zu definieren} {} {} Elementen
\mathl{x,y}{} Elemente
\mathl{a,b}{} mit
\mavergleichskettedisp
{\vergleichskette
{ax }
{ =} {1+by }
{ } { }
{ } { }
{ } { }
} {}{}{} gibt.

}
{} {}

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

}
{} {}

\inputaufgabe
{}
{

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

}
{} {}

\inputaufgabe
{}
{

Es sei
\mavergleichskettedisp
{\vergleichskette
{M }
{ =} { \Q_{\geq 0} }
{ } { }
{ } { }
{ } { }
} {}{}{} die Menge der nichtnegativen rationalen Zahlen mit der $0$ und der Abbildung
\mavergleichskettedisp
{\vergleichskette
{N(x) }
{ =} {x+1 }
{ } { }
{ } { }
{ } { }
} {}{}{.} Welche der \definitionsverweis {Peano-Axiome für den Nachfolger}{}{} gelten für $M$, welche nicht?

}
{} {}

\inputaufgabe
{}
{

Es sei $M$ die disjunkte Vereinigung aus zwei Kopien von $\N$ zusammen mit dem ausgezeichneten Element $0=0_1$ \zusatzklammer {aus der ersten Kopie} {} {} und der Abbildung $N$, die auf beiden Kopien die übliche Nachfolgerabbildung ist. Welche der \definitionsverweis {Peano-Axiome für den Nachfolger}{}{} gelten für $M$, welche nicht?

}
{} {}

\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 der \definitionsverweis {arithmetischen Sprache erster Stufe}{}{} mit den Konstanten
\mathl{0,1}{,} dem Nachfolgersymbol $N$ und den zweistelligen Funktionssymbolen \mathkor {} {+} {und} {\cdot} {} nur abzählbar viele Teilmengen von $\N$ \anfuehrung{adressierbar}{} sind und dass daher das zweitstufige Induktionsaxiom der \definitionsverweis {Dedekind-Peano-Axiome}{}{} nicht in dieser Sprache formulierbar ist.

}
{} {}

\inputaufgabe
{}
{

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

}
{\zusatzklammer {Dies bedeutet aber weder, dass für jede Struktur einer solchen Axiomatik jede Teilmenge adressierbar ist, noch, dass das zweitstufige Induktionsaxiom, das eine Aussage über alle Teilmengen macht, erststufig formulierbar ist} {} {.}} {}

\zwischenueberschrift{Aufgaben zum Abgeben}

\inputaufgabe
{4}
{

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

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

}
{} {}

\inputaufgabe
{3}
{

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

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.

}
{} {}