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

\setcounter{section}{21}

\zwischenueberschrift{Übungsaufgaben}

\inputaufgabe
{}
{

Es sei ein konkretes Registerprogramm $P$ gegeben. Ist es grundsätzlich menschenmöglich, zu entscheiden, ob dieses anhält oder nicht? Was bedeutet das für die Churchsche These?

}
{} {}

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

}
{} {}

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

}
{} {}