Kurs:Einführung in die mathematische Logik (Osnabrück 2021)/Arbeitsblatt 21/latex
\setcounter{section}{21}
\zwischenueberschrift{Übungsaufgaben}
\inputaufgabe
{}
{
Beschreibe für die in Vorlesung 18 besprochenen Registerprogramme die Konfigurationsfolge bei Nulleingabe.
}
{} {}
\inputaufgabe
{}
{
Erstelle für das \definitionsverweis {Registerprogramm}{}{} \zusatzklammer {mit keinem Register und leerer Anfangsbelegung} {} {} \aufzaehlungeins {Halte an } den zugehörigen arithmetischen Ausdruck, der die Anhalteeigenschaft beschreibt.
}
{} {}
\inputaufgabe
{}
{
Erstelle für das
\definitionsverweis {Registerprogramm}{}{}
\zusatzklammer {mit zwei Registern
\mathl{R_1,R_2}{} und leerer Anfangsbelegung} {} {}
\aufzaehlungdrei{$1+$
}{
\mathl{2-}{}
}{Halte an
}
den zugehörigen arithmetischen Ausdruck, der die Anhalteeigenschaft beschreibt.
}
{} {}
\inputaufgabe
{}
{
Es sei $S$ ein
\definitionsverweis {Symbolalphabet}{}{}
und $L^ S$ die zugehörige
\definitionsverweis {Sprache erster Stufe}{}{,} wobei die Sprache zumindest eine Variable besitzen möge. Es sei
\mathl{T \subseteq L^S_0}{} eine Theorie.
Zeige, dass
\mathl{T}{} genau dann
\definitionsverweis {widersprüchlich}{}{}
ist, wenn
\mathl{T= L^S_0}{} ist.
}
{} {}
\inputaufgabe
{}
{
Kann es ein Entscheidungsverfahren für mathematisch relevante Untertheorien
\mathl{T \subseteq L^{\rm Ar}_0}{} geben?
}
{} {}
\inputaufgabe
{}
{
Kann es ein Entscheidungsverfahren für die Symbolalphabete
\mathl{\{0,1,+\}}{} bzw.
\mathl{\{0,1,\cdot\}}{}
\zusatzklammer {jeweils mit Variablen} {} {}
geben? Wo geht bei der Arithmetisierung der Registerprogramme die Addition und wo die Multiplikation ein?
}
{} {}
\inputaufgabe
{}
{
Gibt es offene zahlentheoretische Probleme, die ohne Bezug auf die Addition oder ohne Bezug auf die Multiplikation formuliert werden können?
}
{} {}
\inputaufgabe
{}
{
Kann es mathematische Probleme innerhalb entscheidbarer Theorien geben?
}
{} {}
\inputaufgabe
{}
{
Zeige, dass eine \definitionsverweis {endlich axiomatisierbare}{}{} Theorie auch durch einen einzigen Ausdruck axiomatisierbar ist.
}
{} {}
\inputaufgabe
{}
{
Es sei
\mathl{T \subseteq L^S}{} eine
\definitionsverweis {aufzählbar axiomatisierbare Theorie}{}{}
und
\mathl{\alpha_1 , \ldots , \alpha_n \in L^S}{.} Zeige, dass dann auch
\mavergleichskettedisp
{\vergleichskette
{T'
}
{ =} { { \left( T \cup \{ \alpha_1 , \ldots , \alpha_n \} \right) }^\vdash
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
aufzählbar axiomatisierbar ist.
}
{} {}
\inputaufgabe
{}
{
Es seien
\mavergleichskette
{\vergleichskette
{T_1, T_2
}
{ \subseteq }{L^S
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
\definitionsverweis {aufzählbar axiomatisierbare Theorien}{}{.}
Zeige, dass dann auch
\mathl{(T_1 \cup T_2)^\vdash}{}
\definitionsverweis {aufzählbar}{}{}
ist.
}
{} {}
\inputaufgabegibtloesung
{}
{
Zeige, dass die erststufige Peano-Arithmetik $PA$ eine vollständige widerspruchsfreie erststufige Erweiterung $M$, also
\mavergleichskette
{\vergleichskette
{PA
}
{ \subseteq }{M
}
{ \subseteq }{L^{\rm Ar}_0
}
{ }{
}
{ }{
}
}
{}{}{,}
besitzt, die von $\N^\vDash_0$ verschieden ist.
}
{} {}
\inputaufgabe
{}
{
Entwerfe ein $R$-Entscheidungsverfahren dafür, ob die \definitionsverweis {Goldbach-Vermutung}{}{} aus der \definitionsverweis {erststufigen Peano-Arithmetik}{}{} ableitbar ist.
}
{} {Tipp: Verwende
Aufgabe 19.10,
Aufgabe 21.15
und
Lemma 21.9.}
\zwischenueberschrift{Aufgaben zum Abgeben}
\inputaufgabe
{4}
{
Erstelle für das
\definitionsverweis {Registerprogramm}{}{}
\zusatzklammer {mit zwei Registern
\mathl{R_1,R_2}{} und leerer Anfangsbelegung} {} {}
\aufzaehlungdrei{$1+$
}{
\mathl{C(2,1)}{}
}{Halte an
}
den zugehörigen arithmetischen Ausdruck, der die Anhalteeigenschaft beschreibt.
}
{} {}
\inputaufgabe
{3}
{
Begründe, dass die \zusatzklammer {durch die erststufigen \definitionsverweis {Peano-Axiome}{}{} definierte} {} {} Peano-Arithmetik \definitionsverweis {aufzählbar-axiomatisierbar}{}{} ist.
}
{} {}
\inputaufgabe
{3}
{
Zeige, dass es zwischen der \definitionsverweis {erststufigen Peano-Arithmetik}{}{} und der \definitionsverweis {Standardarithmetik}{}{} unendlich viele Theorien gibt.
}
{} {}