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

}
{} {}