Kurs:Einführung in die mathematische Logik (Osnabrück 2021)/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.
}
}
{} {}
\inputaufgabegibtloesung
{}
{
\aufzaehlungzwei {Zeige, dass die Teilmenge der natürlichen Zahlen, die man als Summe von drei Quadraten schreiben kann, \definitionsverweis {arithmetisch repräsentierbar}{}{} ist. } {Formuliere in der arithmetischen Sprache, dass die $7$ keine Summe von drei Quadraten 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
\definitionsverweis {arithmetisch repräsentierbare}{}{}
Abbildung. Zeige, dass das
\definitionsverweis {Bild}{}{}
\mavergleichskette
{\vergleichskette
{\varphi (\N^r)
}
{ \subseteq }{ \N^s
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
\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
{2}
{
Es sei
\mavergleichskette
{\vergleichskette
{G
}
{ \subseteq }{\N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
die Menge der geraden Zahlen $\geq 4$, die die
\definitionsverweis {Goldbach-Vermutung}{}{}
erfüllen. Ist diese Menge
\definitionsverweis {arithmetisch repräsentierbar}{}{?}
}
{} {}
\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.
}
{} {}