Kurs:Einführung in die mathematische Logik (Osnabrück 2011-2012)/Arbeitsblatt 10/latex
\setcounter{section}{10}
\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 {\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 explizit, dass die in Vorlesung 8 besprochenen Registerprogramme \zusatzklammer {also ihre zugehörigen Programmabbildungen} {} {} \definitionsverweis {arithmetisch repräsentierbar}{}{} sind.
}
{} {}
\inputaufgabe
{}
{
Zeige, dass die $\beta$-\definitionsverweis {Funktion}{}{} \definitionsverweis {arithmetisch repräsentierbar}{}{} ist.
}
{} {}
| << | Kurs:Einführung in die mathematische Logik (Osnabrück 2011-2012) | >> |
|---|