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

}
{} {}

\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!$. }

}
{} {}

\inputaufgabegibtloesung
{4}
{

Zeige, dass in der \definitionsverweis {erststufigen Peano-Arithmetik}{}{} die Addition 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.

}
{} {}