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

\setcounter{section}{15}

\zwischenueberschrift{Übungsaufgaben}

\inputaufgabe
{}
{

Warum sind mathematische Beweise schwierig, obwohl sie \zusatzklammer {zumindest für erststufige Aussagen} {} {} aufgrund des Vollständigkeitssatzes mit einem sehr begrenzten und übersichtlichen formalen Regelwerk durchgeführt werden können?

}
{} {}

\inputaufgabe
{}
{

Diskutiere Metasprache und Objektsprache anhand der Formulierung \anfuehrung{im Widerspruch zur Widerspruchsfreiheit}{} aus dem Beweis zu Lemma 15.1.

}
{} {}

\inputaufgabe
{}
{

Es sei $S$ ein \definitionsverweis {Symbolalphabet}{}{} \zusatzklammer {das mindestens eine Variable enthalte} {} {} einer Sprache erster Stufe und $T$ die zugehörige Termmenge. Zeige, dass man $T$ als Grundmenge einer Interpretation von $S$ nehmen kann, indem man Variablen, Konstanten und Funktionssymbole \anfuehrung{natürlich}{} und Relationssymbole willkürlich interpretiert.

}
{} {}

\inputaufgabe
{}
{

Zeige, dass es eine widerspruchsfreie, unter Ableitungen abgeschlossene Ausdrucksmenge $\Gamma \subseteq L^S$ geben kann, wobei die Variablenmenge aus
\mathbed {x_n} {}
{n \in \N} {}
{} {} {} {,} besteht, derart, dass es einen Ausdruck $\alpha$ mit
\mathl{\exists x_0 \alpha \in \Gamma}{} und
\mathl{\neg \alpha { \frac{ x_n }{ x_0 } } \in \Gamma}{} für alle
\mathl{n \in \N}{} gibt.

}
{} {}

\inputaufgabe
{}
{

Es sei $PA$ die Menge der aus den erststufigen Peano-Axiomen für die Addition und Multiplikation ableitbaren Ausdrücken. Es sei $\alpha$ der erststufige Ausdruck, der die Goldbach-Vermutung ausdrückt. Was kann man über die Widerspruchsfreiheit von
\mathl{PA \cup \{ \alpha \}}{} bzw. von
\mathl{PA \cup \{ \neg \alpha \}}{} sagen? Was bedeutet dies für das in Lemma 15.5 beschriebene Verfahren?

}
{} {}

\inputaufgabe
{}
{

Es sei
\mathl{\Gamma \subseteq L^S}{} eine Ausdrucksmenge, die über beliebig großen endlichen Grundmengen erfüllbar ist. Zeige, dass $\Gamma$ auch über einer unendlichen Menge erfüllbar ist.

}
{} {}

\inputaufgabe
{}
{

Es sei $S$ ein \definitionsverweis {Symbolalphabet}{}{,} das allein aus der einzigen Variablen $x$ besteht. Zeige, dass die Menge aller $S$-\definitionsverweis {Tautologien}{}{} \definitionsverweis {maximal widerspruchsfrei}{}{} ist und \definitionsverweis {Beispiele enthält}{}{.}

}
{} {}

\inputaufgabe
{}
{

Es sei $S$ ein \definitionsverweis {Symbolalphabet}{}{,} das nur aus Variablen besteht. Es sei
\mavergleichskettedisp
{\vergleichskette
{ \Delta }
{ =} { \{ x = y \} }
{ } { }
{ } { }
{ } { }
} {}{}{,} wobei $x,y$ verschiedene Variablen seien, und sei
\mavergleichskettedisp
{\vergleichskette
{\Gamma }
{ =} { \Delta^\vdash }
{ } { }
{ } { }
{ } { }
} {}{}{.} Zeige, dass $\Gamma$ \definitionsverweis {maximal widerspruchsfrei}{}{} ist und \definitionsverweis {Beispiele enthält}{}{.}

}
{} {}

\inputaufgabegibtloesung
{}
{

Es sei $S$ ein \definitionsverweis {Symbolalphabet}{}{} und
\mavergleichskette
{\vergleichskette
{\Gamma }
{ \subseteq }{L^S }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} eine \definitionsverweis {Ausdrucksmenge}{}{.} Begründe, warum man im Allgemeinen bei der Hinzunahme von Beispielen \zusatzklammer {innerhalb des Beweises des Vollständigkeitssatzes} {} {} nicht für alle Existenzaussagen
\mathl{\exists x \alpha \in L^S}{} mit einer einzigen neuen Variablen $z$ arbeiten kann.

}
{} {}

\inputaufgabe
{}
{

Es sei $S$ ein \definitionsverweis {Symbolalphabet}{}{} und
\mavergleichskette
{\vergleichskette
{\Gamma }
{ \subseteq }{L^S }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} eine \definitionsverweis {Ausdrucksmenge}{}{.} Zeige
\mavergleichskettedisp
{\vergleichskette
{ \Gamma^\vdash }
{ =} { \bigcap_{I \vDash \Gamma} I^\vDash }
{ } { }
{ } { }
{ } { }
} {}{}{.}

}
{} {}

\inputaufgabegibtloesung
{}
{

Zeige, dass es einen \definitionsverweis {Peano-Halbring}{}{} $M$ mit der Eigenschaft gibt, dass es darin ein Element
\mavergleichskette
{\vergleichskette
{x }
{ \in }{M }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} gibt, das größer als jede natürliche Zahl in $M$ \zusatzklammer {also Zahlen der Form
\mathl{1+1 + \cdots + 1}{}} {} {} ist.

}
{} {}

\inputaufgabe
{}
{

Man mache sich Gedanken zu den folgenden Zitaten aus Ludwig Wittgensteins Tractatus logico-philosophicus.

\anfuehrung{6.2 Die Mathematik ist eine logische Methode. Die Sätze der Mathematik sind Gleichungen, also Scheinsätze. 6.21 Der Satz der Mathematik drückt keinen Gedanken aus}{.}

\anfuehrung{6.22 Die Logik der Welt, die die Sätze der Logik in den Tautologien zeigen, zeigt die Mathematik in den Gleichungen}{.}

\anfuehrung{6.2321 Und, dass die Sätze der Mathematik bewiesen werden können, heißt ja nichts anderes, als dass ihre Richtigkeit einzusehen ist, ohne dass das, was sie ausdrücken, selbst mit den Tatsachen auf seine Richtigkeit hin verglichen werden muss}{.}

\anfuehrung{6.234 Die Mathematik ist eine Methode der Logik.

6.2341 Das Wesentliche der mathematischen Methode ist es, mit Gleichungen zu arbeiten. Auf dieser Methode beruht es nämlich, dass jeder Satz der Mathematik sich von selbst verstehen muss}{.}

\anfuehrung{6.24 Die Methode der Mathematik, zu ihren Gleichungen zu kommen, ist die Substitutionsmethode}{. (...)}

}
{} {}

\zwischenueberschrift{Aufgaben zum Abgeben}

\inputaufgabe
{4}
{

Es seien
\mathl{s,t}{} nicht identische $S$-\definitionsverweis {Terme}{}{.} Zeige, dass es ein endliches $S$-\definitionsverweis {Modell}{}{} mit
\mavergleichskettedisp
{\vergleichskette
{I(s) }
{ \neq} { I(t) }
{ } { }
{ } { }
{ } { }
} {}{}{} gibt.

}
{} {}

\inputaufgabe
{3}
{

Man gebe ein Beispiel für eine \definitionsverweis {widerspruchsfreie}{}{,} unter \definitionsverweis {Ableitungen}{}{} abgeschlossene Ausdrucksmenge
\mathl{\Gamma \subseteq L^S}{} derart, dass für die \definitionsverweis {konstruierte Interpretation}{}{} $I$ nicht
\mathl{\Gamma \subseteq I^\vDash}{} gilt.

}
{} {}

\inputaufgabe
{4}
{

Es sei
\mathl{\Gamma \subseteq L^S}{} eine \definitionsverweis {abzählbare}{}{} widerspruchsfreie Ausdrucksmenge. Zeige, dass $\Gamma$ ein \definitionsverweis {erfüllendes Modell}{}{} mit abzählbar vielen Elementen besitzt.

}
{} {}

\inputaufgabe
{4}
{

Zeige, dass man die natürlichen Zahlen nicht erststufig festlegen kann.

}
{} {}