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

\setcounter{section}{20}

\zwischenueberschrift{Übungsaufgaben}

\inputaufgabe
{}
{

Zeige, dass die folgenden Teilmengen $T$ der natürlichen Zahlen \definitionsverweis {arithmetisch repräsentierbar}{}{} sind. \aufzaehlungfuenf{Eine konkrete endliche Menge
\mathl{\{n_1 , \ldots , n_k\}}{.} }{Die Menge aller Vielfachen von $5$. }{Die Menge der Primzahlen. }{Die Menge der Quadratzahlen. }{Die Menge der Zahlen, in deren Primfaktorzerlegung jeder Exponent maximal $1$ ist. }

}
{} {}

\inputaufgabe
{}
{

Zeige, dass die folgenden Abbildungen \maabb {\varphi} {\N^r} {\N } {} \definitionsverweis {arithmetisch repräsentierbar}{}{} sind. \aufzaehlungvier{Die Addition \maabbeledisp {} {\N^2} {\N } {(x,y)} {x+y } {.} }{Die Multiplikation \maabbeledisp {} {\N^2} {\N } {(x,y)} {x \cdot y } {.} }{Die eingeschränkte Subtraktion \maabbeledisp {} {\N^2} {\N } {(x,y)} {\operatorname{ max}_{ } ^{ } { \left( x - y, 0 \right) } } {,} die bei
\mathl{y> x}{} den Wert $0$ besitzt. }{Die Restfunktion \maabbeledisp {} {\N^2} {\N } {(n,t)} {r(n,t) } {,} die den Rest \zusatzklammer {zwischen \mathkor {} {0} {und} {t-1} {}} {} {} bei Division von $n$ durch $t$ angibt. }

}
{} {}

\inputaufgabe
{}
{

Zeige, dass die Abbildung \maabbdisp {F} {\N} {\N } {} mit
\mavergleichskettedisp
{\vergleichskette
{F(n) }
{ =} {\begin{cases} \sqrt{n} \, ,\text{ falls } \sqrt{n} \in \N \, ,\\ 0 \text{ sonst} \, , \end{cases} }
{ } { }
{ } { }
{ } { }
} {}{}{} \definitionsverweis {arithmetisch repräsentierbar}{}{} ist.

}
{} {}

\inputaufgabe
{}
{

Es sei \maabbdisp {\varphi} {\N^r} {\N^s } {} eine Abbildung und
\mavergleichskette
{\vergleichskette
{\Gamma }
{ \subseteq }{\N^r \times \N^s }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} der zugehörige \definitionsverweis {Graph}{}{,} also die Menge
\mavergleichskettedisp
{\vergleichskette
{ \Gamma }
{ =} { { \left\{ (n_1 , \ldots , n_{r+s} ) \mid \varphi(n_{ 1} , \ldots , n_{r }) = ( n_{r+1} , \ldots , n_{r+s} ) \right\} } }
{ } { }
{ } { }
{ } { }
} {}{}{.} Zeige, dass $\varphi$ genau dann \definitionsverweis {arithmetisch repräsentierbar}{}{} ist, wenn $\Gamma$ \zusatzklammer {als Relation} {} {} \definitionsverweis {arithmetisch repräsentierbar}{}{} ist.

}
{} {}

\inputaufgabe
{}
{

Zeige explizit, dass die in Vorlesung 18 besprochenen Registerprogramme \zusatzklammer {also ihre zugehörigen Programmabbildungen} {} {} \definitionsverweis {arithmetisch repräsentierbar}{}{} sind.

}
{} {}

\zwischenueberschrift{Aufgaben zum Abgeben}

\inputaufgabe
{}
{

Es sei \maabbdisp {\varphi} {\N^r} {\N^s } {} eine Abbildung. Zeige, dass $\varphi$ genau dann \definitionsverweis {arithmetisch repräsentierbar}{}{} ist, wenn sämtliche \definitionsverweis {Komponentenfunktionen}{}{} $\varphi_i$,
\mathl{1 \leq i \leq s}{,} arithmetisch repräsentierbar sind.

}
{} {}

\inputaufgabe
{}
{

Zeige, dass die $\beta$-\definitionsverweis {Funktion}{}{} \definitionsverweis {arithmetisch repräsentierbar}{}{} ist.

}
{} {}

\inputaufgabe
{}
{

Zeige, dass es nur \definitionsverweis {abzählbar}{}{} viele \definitionsverweis {arithmetisch repräsentierbare}{}{} Relationen gibt.

}
{} {}