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

\setcounter{section}{23}

\zwischenueberschrift{Übungsaufgaben}

\inputaufgabegibtloesung
{}
{

Zeige, dass die Gleichheit von natürlichen Zahlen \zusatzklammer {also die Diagonalrelation in $\N^2$} {} {} durch den Ausdruck
\mathl{x=y}{} in der \definitionsverweis {erststufigen Peano-Arithmetik}{}{} \definitionsverweis {repräsentierbar}{}{} ist.

}
{} {}

\inputaufgabe
{}
{

Es sei
\mathl{\Gamma \subseteq L^{\rm Ar}}{} das Axiomensystem eines \definitionsverweis {kommutativen Halbringes}{}{.} Zeige, dass die Gleichheit von natürlichen Zahlen \zusatzklammer {also die Diagonalrelation in $\N^2$} {} {} durch den Ausdruck
\mathl{x=y}{} in $\Gamma$ nicht \definitionsverweis {repräsentiert}{}{} wird.

}
{} {}

\inputaufgabe
{}
{

Es sei
\mathl{\Gamma \subseteq L^{\rm Ar}}{} das Axiomensystem eines \definitionsverweis {kommutativen Halbringes}{}{.} Zeige, dass $\Gamma$ keine \definitionsverweis {Repräsentierungen erlaubt}{}{.}

}
{} {} Insbesondere erlauben die erststufigen Peano-Axiome ohne das Induktionsschema keine Repräsentierungen.

\inputaufgabe
{}
{

Es sei
\mathl{k \in \N}{} und sei
\mavergleichskettedisp
{\vergleichskette
{ \alpha }
{ \defeq} { \exists y (y + \cdots + y = x) }
{ } { }
{ } { }
{ } { }
} {}{}{,} wobei $k$-mal der Summand $y$ vorkommt. Zeige, dass
\mathl{\N k \subseteq \N}{,} also die Menge der Vielfachen von $k$, in der \definitionsverweis {erststufigen Peano-Arithmetik}{}{} durch $\alpha$ \definitionsverweis {repräsentiert}{}{} wird.

}
{} {}

\inputaufgabe
{}
{

Zeige, dass die Menge der \definitionsverweis {Primzahlen}{}{} in der \definitionsverweis {erststufigen Peano-Arithmetik}{}{} \definitionsverweis {repräsentiert}{}{} werden kann.

}
{} {}

\inputaufgabe
{}
{

Es sei \maabbdisp {f} {\N} {\N } {} eine Polynomfunktion mit
\mavergleichskette
{\vergleichskette
{f(n) }
{ = }{a_d n^d +a_{d-1}n^{d-1} + \cdots + a_1n+a_0 }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} mit Koeffizienten
\mathl{a_i \in \N}{.} Zeige, dass $f$ durch den Ausdruck
\mathl{y=a_d x^d +a_{d-1}x^{d-1} + \cdots + a_1x+a_0}{} in der \definitionsverweis {erststufigen Peano-Arithmetik}{}{} \definitionsverweis {repräsentiert}{}{} wird.

}
{} {}