Kurs:Einführung in die mathematische Logik (Osnabrück 2021)/Arbeitsblatt 22/latex
\setcounter{section}{22}
\zwischenueberschrift{Übungsaufgaben}
\inputaufgabe
{}
{
Zeige, dass für
\mavergleichskette
{\vergleichskette
{\Gamma
}
{ = }{ \N^\vDash
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
die beiden Repräsentierungskonzepte zusammenfallen.
}
{} {}
\inputaufgabegibtloesung
{}
{
Es sei
\mavergleichskettedisp
{\vergleichskette
{T
}
{ =} { \N 2
}
{ \subseteq} {\N
}
{ } {
}
{ } {
}
}
{}{}{}
die Menge der geraden natürlichen Zahlen. Es sei $\Gamma$ die Ausdrucksmenge, die besagt, dass $+$ eine assoziative, kommutative Verknüpfung mit $0$ als neutralem Element ist. Es sei
\mavergleichskettedisp
{\vergleichskette
{\psi
}
{ =} { \exists y (x = y+y)
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Zeige, dass $T$ durch $\psi$ in $\Gamma$
\definitionsverweis {schwach repräsentiert}{}{}
wird, aber nicht stark.
}
{} {}
\inputaufgabe
{}
{
Es sei
\mavergleichskettedisp
{\vergleichskette
{T
}
{ =} { \N 2
}
{ \subseteq} {\N
}
{ } {
}
{ } {
}
}
{}{}{}
die Menge der geraden natürlichen Zahlen. Es sei $\Gamma$ die Ausdrucksmenge, die besagt, dass $+$ eine assoziative, kommutative Verknüpfung mit $0$ als neutralem Element ist. Es sei
\mavergleichskettedisp
{\vergleichskette
{ \varphi
}
{ =} {\exists y (x = y+y) \rightarrow \forall z \neg ( x+1 = z+z)
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
und
\mavergleichskettedisp
{\vergleichskette
{\Delta
}
{ =} { \Gamma \cup \{ \varphi \}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Es sei
\mavergleichskettedisp
{\vergleichskette
{\psi
}
{ =} { \exists y (x = y+y)
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Zeige, dass $T$ durch $\psi$ in $\Delta$
\definitionsverweis {repräsentiert}{}{}
wird.
}
{} {}
\inputaufgabe
{}
{
Zeige, dass eine
\definitionsverweis {widersprüchliche}{}{}
Ausdrucksmenge
\mathl{\Gamma \subseteq L^{\rm Ar}}{}
\definitionsverweis {Repräsentierungen}{}{}
erlaubt.
}
{} {}
\inputaufgabe
{}
{
Es sei
\mathl{\Gamma \subseteq L^{\rm ar}}{} eine Ausdrucksmenge, die
\definitionsverweis {Repräsentierungen erlaube}{}{.}
Zeige, dass jede größere Ausdrucksmenge
\mathl{\Gamma' \supseteq \Gamma}{} ebenfalls Repräsentierungen erlaubt.
}
{} {}
\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 {Quadratzahlen}{}{} in der \definitionsverweis {erststufigen Peano-Arithmetik}{}{} \definitionsverweis {repräsentiert}{}{} werden kann.
}
{} {}
\inputaufgabe
{}
{
Es sei
\mathl{\Gamma \subseteq L^{\rm ar}}{} eine
\definitionsverweis {widerspruchsfreie}{}{} und
$R$-\definitionsverweis {entscheidbare}{}{} Ausdrucksmenge.
a) Zeige, dass jede in $\Gamma$
\definitionsverweis {repräsentierbare Relation}{}{}
\mathl{R \subseteq \N^r}{}
$R$-\definitionsverweis {entscheidbar}{}{}
ist.
b) Zeige, dass jede in $\Gamma$ \definitionsverweis {repräsentierbare Abbildung}{}{} \maabbdisp {\varphi} {\N^r} {\N^s } {} $R$-\definitionsverweis {berechenbar}{}{} ist.
}
{} {}
\inputaufgabegibtloesung
{}
{
Es sei
\mathl{\Gamma \subseteq L^{\rm Ar}}{} eine arithmetische Ausdrucksmenge ohne freie Variablen und
\mathl{R \subseteq \N}{} eine Relation. Es seien
\mathl{\alpha, \beta \in L^{\rm Ar}}{} Ausdrücke in einer freien Variablen $x$. Zeige, dass aus
\mathdisp {\Gamma \vdash \alpha \leftrightarrow \beta} { }
folgt, dass $\alpha$ in $\Gamma$ die Relation $R$ genau dann
\definitionsverweis {repräsentiert}{}{,}
wenn
\mathl{\beta}{} in $\Gamma$ die Relation $R$ repräsentiert.
}
{} {}
\inputaufgabegibtloesung
{}
{
Es sei
\mathl{\Gamma \subseteq L^{\rm Ar}}{} eine arithmetische Ausdrucksmenge und
\mathl{R \subseteq \N}{} eine Relation. Es seien
\mathl{\alpha, \beta \in L^{\rm Ar}}{} Ausdrücke in einer freien Variablen $x$. Zeige, dass aus
\mathdisp {\Gamma \vdash \alpha \leftrightarrow \beta} { }
\betonung{nicht}{} folgt, dass $\alpha$ in $\Gamma$ die Relation $R$ genau dann
\definitionsverweis {repräsentiert}{}{,}
wenn
\mathl{\beta}{} in $\Gamma$ die Relation $R$ repräsentiert.
}
{} {}
Für die folgende Aufgabe siehe auch Aufgabe 11.12.
\inputaufgabegibtloesung
{}
{
Zeige, dass in der \definitionsverweis {erststufigen Peano-Arithmetik}{}{} die Addition von natürlichen Zahlen \definitionsverweis {repräsentierbar}{}{} ist.
}
{} {}
\inputaufgabe
{}
{
Es sei
\mathl{s_1,s_2,s_3, \ldots}{} eine Aufzählung einer abzählbar-unendlichen Symbolmengen. Berechne die zu Wörtern über diesem Alphabet zugehörige Zahl im Sinne der Primzahlkodierung und umgekehrt.
\aufzaehlungsieben{
\mathl{s_1s_2s_1s_3s_3s_2}{,}
}{
\mathl{s_{13}s_{12} s_1s_4s_4s_4}{,}
}{
\mathl{s_{2}s_{2} s_2s_2s_2s_2}{,}
}{ $2^1 3^3 5^{17} 7^1$,
}{ $2^1 3^1 5^{1} 7^1 11^1$,
}{ $2^3 3^3 5^{3}7^3 11^3$,
}{ $1728$.
}
}
{} {}
\inputaufgabe
{}
{
Es sei
\mathl{n \in \N}{} eine fixierte natürliche Zahl und
\mavergleichskettedisp
{\vergleichskette
{ \alpha (x)
}
{ \defeq} { x = n
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{,}
wobei $n$ durch die $n$-fache Summe der $1$ mit sich selbst realisiert werde. Zeige direkt, dass es Sätze
\mathl{p,q \in L^{\rm Ar}_0}{} mit
\mathdisp {\vdash \alpha(GN(p)) \leftrightarrow p} { }
und mit
\mathdisp {\vdash \neg \alpha(GN(q)) \leftrightarrow q} { }
gibt.
}
{} {}
\zwischenueberschrift{Aufgaben zum Abgeben}
\inputaufgabe
{4}
{
Zeige, dass die Menge der \definitionsverweis {Primzahlen}{}{} in der \definitionsverweis {erststufigen Peano-Arithmetik}{}{} \definitionsverweis {repräsentiert}{}{} werden kann.
}
{} {}
\inputaufgabe
{4}
{
Es sei
\mathl{s_1,s_2,s_3, \ldots}{} eine Aufzählung einer abzählbar-unendlichen Symbolmengen. Berechne die zu Wörtern über diesem Alphabet zugehörige Zahl im Sinne der Primzahlkodierung und umgekehrt.
\aufzaehlungvier{
\mathl{s_3 s_2 s_1 s_1 s_2 s_3}{,}
}{
\mathl{s_{20} s_{17} s_{1} s_4 s_{19}}{,}
}{ $2^1 3^2 5^{3}7^4 11^5$,
}{ $10!$.
}
}
{} {}
\inputaufgabe
{4}
{
Zeige, dass in der \definitionsverweis {erststufigen Peano-Arithmetik}{}{} die Multiplikation von natürlichen Zahlen \definitionsverweis {repräsentierbar}{}{} ist.
}
{} {}
\inputaufgabe
{6}
{
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.
}
{} {}