Kurs:Einführung in die mathematische Logik (Osnabrück 2018)/Arbeitsblatt 13/latex
\setcounter{section}{13}
\zwischenueberschrift{Übungsaufgaben}
\inputaufgabegibtloesung
{}
{
Zeige, dass in einem
\definitionsverweis {kommutativen Halbring}{}{}
die Beziehung
\mavergleichskette
{\vergleichskette
{0 \cdot 0
}
{ = }{0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gilt.
}
{} {}
\inputaufgabe
{}
{
Es sei $R$ ein
\definitionsverweis {kommutativer Halbring}{}{.}
Zeige, dass
\mavergleichskettedisp
{\vergleichskette
{0 \cdot { \left( 1+1 + \cdots + 1 \right) }
}
{ =} {0
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
ist
\zusatzklammer {mit einer beliebig langen Summe von Einsen} {} {.}
}
{} {}
\inputaufgabegibtloesung
{}
{
Man definiere auf der dreielementigen Menge
\mathl{\{0,1,u\}}{} die Struktur eines
\definitionsverweis {kommutativen Halbringes}{}{,}
bei dem
\mavergleichskette
{\vergleichskette
{ 0 \cdot u
}
{ \neq }{0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gilt.
}
{} {}
\inputaufgabe
{}
{
Da man die natürlichen Zahlen zum Zählen von endlichen Mengen nimmt, es aber auch unendliche Mengen gibt, denkt sich Gabi Hochster, dass man die natürlichen Zahlen $\N$ um ein weiteres Symbol $\infty$
\zusatzklammer {sprich unendlich} {} {}
erweitern sollte. Diese neue Menge bezeichnet sie mit $\N^\infty$. Sie möchte die Ordnungsstruktur, die Addition und die Multiplikation der natürlichen Zahlen auf ihre neue Menge ausdehnen, und zwar so, dass möglichst viele vertraute Rechengesetze erhalten bleiben.
\aufzaehlungacht{Wie legt Gabi die Ordnung fest?
}{Wie legt sie die Nachfolgerabbildung fest? Gelten die Peano-Axiome?
}{Wie legt sie die Addition fest? Sie möchte ja nur mit dem einzigen neuen Symbol $\infty$ arbeiten.
}{Gilt mit dieser Addition die Abziehregel?
}{Zuerst denkt sie an die Festlegung
\mavergleichskettedisp
{\vergleichskette
{ 0 \cdot \infty
}
{ =} {1
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{,}
doch dann stellt sie fest, dass sich das mit dem Distributivgesetz beißt. Warum?
}{Gabi möchte nun, dass für die neue Menge die Eigenschaften aus
Fakt *****
und aus
Satz 9.4 (Grundkurs Mathematik (Osnabrück 2016-2017))
nach wie vor gelten. Wie legt sie die Verknüpfungen fest?
}{Handelt es sich bei
\mathl{\N^\infty}{} mit den Festlegungen aus Teil (6) um einen
\definitionsverweis {kommutativen Halbring}{}{?}
}{Gilt die Kürzungsregel?
}
}
{} {}
\inputaufgabegibtloesung
{}
{
Es sei
\mavergleichskette
{\vergleichskette
{R
}
{ = }{ \mathfrak {P} \, (M )
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
die
\definitionsverweis {Potenzmenge}{}{}
zu einer Menge $M$. Zeige, dass $R$ mit der
\definitionsverweis {Vereinigung}{}{}
$\cup$ als Addition und der
\definitionsverweis {leeren Menge}{}{}
als $0$ und mit dem
\definitionsverweis {Durchschnitt}{}{}
$\cap$ als Multiplikation und der Gesamtmenge $M$ als $1$ ein
\definitionsverweis {kommutativer Halbring}{}{}
ist.
}
{} {}
\inputaufgabe
{}
{
Es sei $R$ ein
\definitionsverweis {kommutativer Halbring}{}{}
und
\mathl{f , a_i, b_j \in R}{.} Zeige die folgenden Gleichungen:
\mathdisp {\sum_{ i = 0 }^{ n } a_{ i } f^{ i} + \sum_{ j = 0 }^{ m } b_{ j } f^{ j} = \sum_{k=0}^{ \max ( n,m) } ( a _{ k}+b _{ k} ) f^{ k }} { }
und
\mathdisp {{ \left( \sum_{ i = 0 }^{ n } a_{ i } f^{ i} \right) } \cdot { \left( \sum_{ j = 0 }^{ m } b_{ j } f^{ j} \right) } = \sum_{ k = 0 }^{ n+m } c_{ k } f^{ k} \text{ mit } c_{ k} =\sum_{ r= 0}^{ k } a_{ r } b_{ k - r }} { . }
}
{} {}
\inputaufgabegibtloesung
{}
{
Beweise das \stichwort {allgemeine Distributivgesetz} {} für einen kommutativen Halbring.
}
{} {}
\inputaufgabegibtloesung
{}
{
Beweise die folgende Form des allgemeinen Distributivgesetzes für einen kommutativen Halbring $R$ durch Induktion über $k$, wobei der Fall
\mavergleichskette
{\vergleichskette
{k
}
{ = }{2
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
verwendet werden darf
\zusatzklammer {dabei sind
\mathl{n_1 , \ldots , n_k}{} natürliche Zahlen und
\mathl{a_{j,i} \in R}{}} {} {.}
\mavergleichskettealign
{\vergleichskettealign
{ { \left( \sum_{i_1 = 1}^{n_1} a_{1, i_1} \right) } \cdot { \left( \sum_{i_2 = 1}^{n_2} a_{2, i_2} \right) } \cdots { \left( \sum_{i_k = 1}^{n_k} a_{k, i_k} \right) }
}
{ =} { \sum_{ (i_1, i_2 , \ldots , i_k) \in \{ 1 , \ldots , n_1 \} \times \{ 1 , \ldots , n_2 \} \times \cdots \times \{ 1 , \ldots , n_k \} } a_{1,i_1} \cdot a_{2,i_2} \cdots a_{k, i_k}
}
{ } {
}
{ } {
}
{ } {}
}
{}
{}{.}
}
{} {}
\inputaufgabe
{}
{
Zeige, dass in einem
\definitionsverweis {kommutativen Halbring}{}{}
durch
\mathdisp {x \geq y \text{ genau dann, wenn } \exists z (x= y+z)} { }
eine
\definitionsverweis {reflexive}{}{}
und
\definitionsverweis {transitive}{}{}
Relation gegeben ist. Zeige durch geeignete Beispiele, dass diese weder
\definitionsverweis {antisymmetrisch}{}{}
noch
\definitionsverweis {total}{}{}
sein muss.
}
{} {}
In den folgenden Aufgaben besprechen wir Teilbarkeitskonzepte für einen kommutativen Halbring.
Eine
\definitionsverweis {Nichteinheit}{}{}
$p$ in einem
\definitionsverweis {kommutativen Halbring}{}{}
heißt \definitionswort {irreduzibel}{} (oder \definitionswort {unzerlegbar}{),} wenn eine Faktorisierung
\mathl{p=ab}{} nur dann möglich ist, wenn einer der Faktoren eine Einheit ist.
Diese Eigenschaft charakterisiert im Halbring $\N$ gerade die Primzahlen.
Eine
\definitionsverweis {Nichteinheit}{}{}
\mathl{p \neq 0}{} in einem
\definitionsverweis {kommutativen Halbring}{}{}
$R$ heißt \definitionswort {prim}{}
\zusatzklammer {oder ein \definitionswort {Primelement}{}} {} {,}
wenn folgendes gilt: Teilt $p$ ein Produkt
\mathbed {ab} {mit}
{a,b \in R} {}
{} {} {} {,}
so teilt es einen der Faktoren.
\inputaufgabe
{}
{
Formalisiere in der \zusatzklammer {erststufigen} {} {} Sprache der \definitionsverweis {kommutativen Halbringe}{}{} die Konzepte Einheit, Teilt, irreduzibel, Primelement.
}
{} {}
\inputaufgabe
{}
{
Es sei $R$ ein \definitionsverweis {kommutativer Halbring}{}{,} der die \definitionsverweis {Kürzungsregel}{}{} erfüllt. Zeige, dass ein \definitionsverweis {Primelement}{}{} stets \definitionsverweis {irreduzibel}{}{} ist.
}
{} {}
\inputaufgabe
{}
{
Zeige, dass für $\N$ die Konzepte \definitionsverweis {Primelement}{}{} und \definitionsverweis {irreduzibel}{}{} zusammenfallen.
}
{} {}
\inputaufgabe
{}
{
Man gebe Beispiele für \definitionsverweis {kommutative Halbringe}{}{,} in denen die Konzepte \definitionsverweis {Primelement}{}{} und \definitionsverweis {irreduzibel}{}{} auseinanderfallen.
}
{} {}
\inputaufgabe
{}
{
Gilt für die Vereinigung von Mengen die \anfuehrung{Abziehregel}{,} d.h. kann man aus
\mavergleichskette
{\vergleichskette
{A \cup C
}
{ = }{B \cup C
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
auf
\mavergleichskette
{\vergleichskette
{A
}
{ = }{B
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
schließen?
}
{} {}
\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.
}
{} {}
\inputaufgabegibtloesung
{}
{
Zeige, dass in einem
\definitionsverweis {Peano-Halbring}{}{}
$M$ zu
\mavergleichskette
{\vergleichskette
{d
}
{ \geq }{1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
die
Division mit Rest
eindeutig ist.
}
{} {}
\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 $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
{}
{
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?
}
{} {}
\inputaufgabegibtloesung
{}
{
Es sei
\mavergleichskettedisp
{\vergleichskette
{M
}
{ =} {\{0\} \cup \Q_{\geq 1}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
\aufzaehlungsechs{Zeige, dass $M$ ein
\definitionsverweis {kommutativer Halbring}{}{}
ist.
}{Zeige, dass in $M$ die Relationen
\mathdisp {a \text{ teilt } b \text{ oder } a = 0} { }
und
\mathdisp {a \leq b \text{ oder } b = 0} { }
zueinander äquivalent sind.
}{Zeige, dass
\mathl{{ \frac{ 6 }{ 5 } }}{} nicht
\definitionsverweis {irreduzibel}{}{}
in $M$ ist.
}{Zeige, dass es in $M$ keine irreduziblen Elemente gibt.
}{Es sei $\alpha$ die Aussage
\mathdisp {x = 0 \vee \exists y (x = y+ 1)} { . }
Zeige, dass in $M$ die Aussage
\mathdisp {\alpha { \frac{ 0 }{ x } } \wedge { \left( \alpha \rightarrow \alpha { \frac{ x+1 }{ x } } \right) }} { }
wahr ist.
}{Zeige, dass $M$ kein
\definitionsverweis {Peano-Halbring}{}{}
ist.
}
}
{} {}
\inputaufgabe
{}
{
Zeige, dass in
\mavergleichskette
{\vergleichskette
{M
}
{ \subseteq }{\Z[V]
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
aus
Beispiel 13.9
jedes Element
\mathl{\neq 0}{} einen eindeutig bestimmten Vorgänger besitzt.
}
{} {}
\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.
}
{} {}
\zwischenueberschrift{Die Aufgabe zum Aufgeben}
\inputaufgabe
{5}
{
Man gebe einen Ausdruck $\alpha \in L^ {\rm Ar}$ aus der arithmetischen Sprache erster Stufe
\zusatzklammer {also mit
\mathl{0,1,+,\cdot}{}} {} {}
mit einer freien Variablen $x$ an, der über den ganzen Zahlen $\Z$ folgende Eigenschaft besitzt: Es gilt
\mathdisp {\Z { \frac{ m }{ x } } \vDash \alpha} { }
genau dann, wenn
\mathl{m \in \N}{} ist
\zusatzklammer {der Ausdruck gilt also genau für die natürlichen Zahlen} {} {.}
}
{} {}
| << | Kurs:Einführung in die mathematische Logik (Osnabrück 2018) | >> |
|---|