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

\setcounter{section}{23}

\zwischenueberschrift{Übungsaufgaben}

\inputaufgabe
{}
{

Epimenides der Kreter sagte: \anfuehrung{Alle Kreter sind Lügner}{.} Ist diese Aussage ein Widerspruch?

}
{} {}

\inputaufgabe
{}
{

Eine Person sagt: \anfuehrung{Ich lüge (jetzt)}{.} Kann das wahr sein?

}
{} {}

\inputaufgabe
{}
{

In der \stichwort {Russellsche Antinomie} {} wird die Definition
\mavergleichskettedisp
{\vergleichskette
{M }
{ =} { { \left\{ N \mid N \text{ ist eine Menge, die sich nicht selbst enthält} \right\} } }
{ } { }
{ } { }
{ } { }
} {}{}{} betrachtet. Kann $M$ eine Menge sein?

}
{} {}

\inputaufgabe
{}
{

Betrachte die Aussage: \anfuehrung{Der Barbier von Sevilla rasiert alle Männer, die sich nicht selbst rasieren}{.} Rasiert er sich selbst?

}
{} {}

\inputaufgabegibtloesung
{}
{

Es sei $M$ eine beliebige Menge. Zeige, dass es keine \definitionsverweis {surjektive Abbildung}{}{} von $M$ in die \definitionsverweis {Potenzmenge}{}{} $\mathfrak {P} \, (M )$ geben kann.

}
{} {}

\inputaufgabe
{}
{

Die Klasse 8c hat an jedem Wochentag eine Stunde mathematische Logik. Der Lehrer sagt am Freitag: \anfuehrung{nächste Woche werden wir eine Klassenarbeit schreiben, und das wird eine Überraschung sein}{.} Begründe, dass der Lehrer lügt.

}
{} {}

\inputaufgabe
{}
{

Das Brennersche Putzparadoxon besagt: \anfuehrung{Immer wenn ich putze, sieht es danach so aus, wie bei einer durchschnittlichen Hausfrau vor dem Putzen}{.} Ist dies ein Widerspruch, eine Antinomie, ein Paradoxon, oder einfach nur mangelndes Talent?

}
{} {}

\inputaufgabe
{}
{

Eine natürliche Zahl heißt \stichwort {besonders} {,} wenn sie eine für sie spezifische, benennbare Eigenschaft erfüllt. Die $0$ ist als neutrales Element der Addition und die $1$ ist als neutrales Element der Multiplikation besonders. Die $2$ ist die erste Primzahl, die $3$ ist die kleinste ungerade Primzahl, die $4$ ist die erste echte Quadratzahl, die $5$ ist die Anzahl der Finger einer Hand, die $6$ ist die kleinste aus verschiedenen Faktoren zusammengesetzte Zahl, die $7$ ist die Anzahl der Zwerge im Märchen, u.s.w., diese Zahlen sind also alle besonders. Gibt es eine Zahl, die nicht besonders ist? Gibt es eine kleinste Zahl, die nicht besonders ist?

}
{} {}

\inputaufgabe
{}
{

Es sei $\Gamma$ eine korrekte entscheidbare arithmetische Ausdrucksmenge, die die Peano-Arithmetik umfasse. Es sei
\mathl{\alpha(x)}{} das zugehörige \definitionsverweis {Ableitungsprädikat}{}{.} Zeige aus den in Bemerkung 23.7 aufgeführten Eigenschaften für einen Fixpunkt $q$ mit
\mathdisp {\Gamma \vdash \neg \alpha (GN(q)) \leftrightarrow q} { , }
dass weder
\mathl{\Gamma \vdash q}{} noch
\mathl{\Gamma \vdash \neg q}{} gilt.

}
{} {}

\inputaufgabe
{}
{

Es sei $\Gamma$ eine korrekte entscheidbare arithmetische Ausdrucksmenge, die die Peano-Arithmetik umfasse. Es sei
\mathl{\alpha(x)}{} das zugehörige Beweisbarkeitsprädikat und es sei $q$ ein Fixpunkt zum negierten Ableitungsprädikat, also
\mathdisp {\Gamma \vdash \neg \alpha (GN(q)) \leftrightarrow q} { . }
\aufzaehlungdrei{Welche Eigenschaften aus Bemerkung 23.7 gelten in $\N$? }{Gilt
\mathdisp {\neg \alpha (GN(q)) \leftrightarrow q} { }
in $\N$? }{Welche der Ausdrücke $q, \neg q , \alpha (GN(q)) ,\neg \alpha (GN(q))$ gelten in $\N$? }

}
{} {}

\inputaufgabegibtloesung
{}
{

Es sei $\Gamma$ eine arithmetische Ausdrucksmenge und
\mathl{\alpha}{} ein einstelliges Prädikat mit
\mathdisp {\Gamma \vdash \alpha (n)} { }
für alle
\mathl{n \in \N}{.} Zeige, dass es einen Satz $q$ mit
\mathdisp {\Gamma \vdash \alpha(GN(q)) \leftrightarrow q} { }
gibt.

}
{} {}

\inputaufgabe
{}
{

Es sei $\Gamma$ eine arithmetische Ausdrucksmenge und
\mathl{\alpha}{} ein einstelliges Prädikat mit
\mathdisp {\Gamma \vdash \neg \alpha (n)} { }
für alle
\mathl{n \in \N}{.} Zeige, dass es einen Satz $q$ mit
\mathdisp {\Gamma \vdash \alpha(GN(q)) \leftrightarrow q} { }
gibt.

}
{} {}

\inputaufgabe
{}
{

Wir setzen
\mavergleichskettedisp
{\vergleichskette
{ \alpha (x) }
{ \defeq} {\exists y { \left( x = y+y \right) } }
{ } { }
{ } { }
{ } { }
} {}{}{} und es sei die Gödelisierung mit Primzahlen vorausgesetzt. Zeige \zusatzklammer {ohne den Fixpunktsatz zu verwenden} {} {,} dass es einen Satz
\mathl{q \in L^{\rm Ar}_0}{} mit
\mathdisp {PA \vdash \alpha(GN(q)) \leftrightarrow q} { }
gibt.

}
{} {}

\inputaufgabe
{}
{

Es sei $k$ eine fixierte positive natürliche Zahl und es sei
\mavergleichskettedisp
{\vergleichskette
{ \alpha (x) }
{ \defeq} {\exists y { \left( x = k y \right) } }
{ } { }
{ } { }
{ } { }
} {}{}{,} wobei $ky$ als die $k$-fache Addition von $y$ mit sich selbst realisiert werde. Es sei die Gödelisierung mit Primzahlen vorausgesetzt. Zeige \zusatzklammer {ohne den Fixpunktsatz zu verwenden} {} {,} dass es einen Satz
\mathl{q \in L^{\rm Ar}_0}{} mit
\mathdisp {PA \vdash \alpha(GN(q)) \leftrightarrow q} { }
gibt.

}
{} {}

\zwischenueberschrift{Aufgaben zum Abgeben}

\inputaufgabe
{4}
{

Es seien
\mathl{n_1 , \ldots , n_r}{} natürliche Zahlen und sei
\mavergleichskettedisp
{\vergleichskette
{ \alpha (x) }
{ \defeq} { { \left( x = n_1 \right) } \wedge \ldots \wedge { \left( x = n_r \right) } }
{ } { }
{ } { }
{ } { }
} {}{}{,} wobei $n_j$ durch die $n_j$-fache Summe der $1$ mit sich selbst realisiert werde. Zeige, 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.

}
{} {}

\inputaufgabe
{3}
{

Folgere aus dem ersten Gödelschen Unvollständigkeitssatz die Unentscheidbarkeit der Arithmetik.

}
{} {}

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

}
{} {}

\inputaufgabe
{4}
{

Es sei $\Gamma$ eine korrekte entscheidbare arithmetische Ausdrucksmenge, die die Peano-Arithmetik umfasse. Es sei
\mathl{\alpha(x)}{} das zugehörige Beweisbarkeitsprädikat und es sei $q$ ein Fixpunkt zum negierten \definitionsverweis {Ableitungsprädikat}{}{,} also
\mathdisp {\Gamma \vdash \neg \alpha (GN(q)) \leftrightarrow q} { . }
Zu einem beliebigen Ausdruck $p$ betrachten wir
\mathl{\neg \alpha (GN( p \wedge \neg p))}{.} Welche der Ausdrücke
\mathdisp {\neg \alpha (GN( p \wedge \neg p)),\, \neg \alpha(GN(q)) ,\, \neg \alpha (GN( p \wedge \neg p)) \rightarrow \neg \alpha(GN(q))} { }
gelten in $\N$?

}
{} {}

\inputaufgabe
{4 (2+2)}
{

Es sei $\Gamma$ eine arithmetische Ausdrucksmenge und
\mathl{\alpha}{} ein einstelliges Prädikat. \aufzaehlungzwei {Es gelte
\mathdisp {\Gamma \vdash \alpha (n)} { }
für endlich viele
\mathl{n \in \N}{} und für alle übrigen natürlichen Zahlen gelte
\mathdisp {\Gamma \vdash \neg \alpha (n)} { . }
Zeige, dass es einen Satz $q$ mit
\mathdisp {\Gamma \vdash \alpha(GN(q)) \leftrightarrow q} { }
gibt. } {Es gelte
\mathdisp {\Gamma \vdash \neg \alpha (n)} { }
für endlich viele
\mathl{n \in \N}{} und für alle übrigen natürlichen Zahlen gelte
\mathdisp {\Gamma \vdash \alpha (n)} { . }
Zeige, dass es einen Satz $q$ mit
\mathdisp {\Gamma \vdash \alpha(GN(q)) \leftrightarrow q} { }
gibt. }

}
{} {}