Kurs:Einführung in die mathematische Logik (Osnabrück 2018)/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
{}
{

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
\mavergleichskette
{\vergleichskette
{y }
{ = }{a_d x^d +a_{d-1}x^{d-1} + \cdots + a_1x+a_0 }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} \definitionsverweis {arithmetisch repräsentiert}{}{} wird.

}
{} {}

\inputaufgabe
{}
{

Zeige, dass eine \definitionsverweis {lineare Abbildung}{}{} \zusatzklammer {im Sinne von verträglich mit der Addition und mit der Skalarmultiplikation} {} {} \maabbdisp {F} {\N^r} { \N^s } {} \definitionsverweis {arithmetisch repräsentierbar}{}{} ist.

}
{} {}

\inputaufgabe
{}
{

Zeige, dass eine \definitionsverweis {polynomiale Abbildung}{}{} \zusatzklammer {mit Koeffizienten aus $\N$} {} {} \maabbeledisp {F} {\N^r} { \N } { \left( x_1 , \, \ldots , \, x_n \right) } { F(x_1 , \ldots , x_n) } {,} \definitionsverweis {arithmetisch repräsentierbar}{}{} ist.

}
{} {}

\inputaufgabegibtloesung
{}
{

Zeige, dass die Abbildung \maabbeledisp {f} {\N^3} { \N } {(x,y,z)} {xy^2-z^2 + 2z^3 } {,} \zusatzklammer {wohldefiniert und} {} {} \definitionsverweis {arithmetisch repräsentierbar}{}{} ist.

}
{} {}

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

}
{} {}

\inputaufgabegibtloesung
{}
{

Es sei \maabbdisp {F} {\N^r} {\N^s } {} eine \definitionsverweis {arithmetisch repräsentierbare}{}{} Abbildung. Zeige, dass zu jedem Punkt
\mathl{P \in \N^s}{} die \definitionsverweis {Faser}{}{}
\mavergleichskettedisp
{\vergleichskette
{F^{-1}(P) }
{ \subseteq} { \N^r }
{ } { }
{ } { }
{ } { }
} {}{}{} \definitionsverweis {arithmetisch repräsentierbar}{}{} ist.

}
{} {}

\inputaufgabe
{}
{

Es sei \maabbdisp {\varphi} {\N^r} {\N^s } {} eine \definitionsverweis {arithmetisch repräsentierbare}{}{} Abbildung und es sei
\mavergleichskette
{\vergleichskette
{ T }
{ \subseteq }{ \N^s }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} eine \definitionsverweis {arithmetisch repräsentierbare}{}{} Relation. Zeige, dass das \definitionsverweis {Urbild}{}{}
\mavergleichskettedisp
{\vergleichskette
{ \varphi^{-1} (T) }
{ \subseteq} {\N^r }
{ } { }
{ } { }
{ } { }
} {}{}{} arithmetisch repräsentierbar ist.

}
{} {}

\inputaufgabe
{}
{

Wir betrachten das Registerprogramm mit drei Registern \zusatzklammer {bei leerem dritten Register berechnet es die Summe der ersten beiden Registerinhalte} {} {} \aufzaehlungfuenf{
\mathl{C(2,5)}{} }{$1+$ }{$2-$ }{
\mathl{C(3,1)}{} }{Halte an }

a) Erstelle die Programmabbildung für dieses Programm.

b) Welche Beziehung besteht zwischen der Programmabbildung und der Additionsabbildung \maabbeledisp {} {\N \times \N} {\N } {(x,y)} {x+y } {?}

c) Erstelle eine arithmetische Repräsentierung für dieses Programm.

}
{} {}

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

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

Zeige, dass die \definitionsverweis {Abbildung}{}{} \maabbeledisp {F} {\N \times \N_+ } { \N } {(x,y)} { \left \lfloor { \frac{ x }{ y } } \right \rfloor } {,} \definitionsverweis {arithmetisch repräsentierbar}{}{} ist.

}
{} {}

\inputaufgabe
{5}
{

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

}
{} {}

\inputaufgabe
{2}
{

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

}
{} {}