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

\setcounter{section}{12}

\zwischenueberschrift{Übungsaufgaben}

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

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

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

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

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

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

}
{} {}

Wir erinnern an die Definition eines algebraisch abgeschlossenen Körpers. Die komplexen Zahlen ${\mathbb C}$ sind algebraisch abgeschlossen \zusatzklammer {Fundamentalsatz der Algebra} {} {,} die reellen Zahlen $\R$ nicht.

Ein \definitionsverweis {Körper}{}{} $K$ heißt \definitionswort {algebraisch abgeschlossen}{,} wenn jedes nichtkonstante \definitionsverweis {Polynom}{}{}
\mavergleichskette
{\vergleichskette
{F }
{ \in }{K[X] }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} eine Nullstelle in $K$ besitzt.

\inputaufgabe
{}
{

Definiere über der Symbolmenge
\mathl{\{0,1,+,\cdot\}}{} einen \definitionsverweis {algebraisch abgeschlossenen Körper}{}{} mit Hilfe eines Axiomenschemas.

}
{} {}

\zwischenueberschrift{Aufgaben zum Abgeben}

\inputaufgabe
{}
{

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

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

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.

}
{} {}