Kurs:Einführung in die mathematische Logik (Osnabrück 2016)/Arbeitsblatt 22/latex

\setcounter{section}{22}

\zwischenueberschrift{Übungsaufgaben}

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

}
{} {}

\inputaufgabe
{6}
{

Es sei $\Gamma$ eine korrekte entscheidbare arithmetische Ausdrucksmenge, die die Peano-Arithmetik umfasse. Es sei
\mathl{\alpha(x)}{} das \definitionsverweis {Ableitungsprädikat}{}{} zu $\Gamma$ und es sei $q$ ein Fixpunkt zum negierten Ableitungsprädikat, also
\mathdisp {\Gamma \vdash \neg \alpha (GN(q)) \leftrightarrow q} { . }
Zeige, dass aus den in Bemerkung 23.7 angeführten Eigenschaften man
\mathdisp {\Gamma \vdash \neg \alpha (GN( p \wedge \neg p)) \rightarrow \neg \alpha(GN(q))} { }
erhalten kann, wobei $p$ ein beliebiger Ausdruck ist.

}
{} {}