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

Unterscheide zwischen den verschiedenen Bedeutungen von Gleichheit. \aufzaehlungdrei{Gleichheit von Elementen in einer Menge. }{Gleichheit von Zeichenketten. }{Das Gleichheitssymbol in einer erststufigen Sprache. }

}
{} {}

\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
{}
{

Es sei $S$ ein \definitionsverweis {Symbolalphabet}{}{} einer Sprache erster Stufe. Es seien $S$-\definitionsverweis {Terme}{}{} $s,t$ mit
\mathdisp {\vdash s = t} { }
gegeben. Zeige, dass es sich bei $s$ und $t$ um eine identische Zeichenreihe handelt.

}
{} {}

\inputaufgabe
{}
{

Es sei $\alpha \in L^S$ ein \definitionsverweis {atomarer Ausdruck}{}{,} der zugleich eine Tautologie ist, also
\mathl{\vdash \alpha}{.} Zeige, dass $\alpha$ gleich
\mathl{s= s}{} mit einem $S$-\definitionsverweis {Term}{}{} $s$ ist.

}
{} {}

\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
{}
{

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}{. (...)}

}
{} {}

Wir besprechen den für die Konstruktion eines Modells \zusatzklammer {zum Satz von Henkin} {} {} wichtigen Begriff einer Äquivalenzrelation anhand einiger Aufgaben.

\inputaufgabe
{}
{

Wir betrachten die ganzen Zahlen $\Z$ und eine fixierte natürliche Zahl $a \geq 0$. Zeige, dass auf $\Z$ durch
\mathdisp {x \sim y, \text{ wenn die Differenz } x-y \text{ ein Vielfaches von } a \text { ist}} { , }
eine \definitionsverweis {Äquivalenzrelation}{}{} definiert wird. Wie viele \definitionsverweis {Äquivalenzklassen}{}{} gibt es?

}
{} {}

\inputaufgabe
{}
{

Es sei $K$ ein \definitionsverweis {Körper}{}{,} $V$ ein $K$-\definitionsverweis {Vektorraum}{}{} und
\mavergleichskette
{\vergleichskette
{U }
{ \subseteq }{V }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} ein \definitionsverweis {Untervektorraum}{}{.} Wir betrachten die \definitionsverweis {Relation}{}{} auf $V$, die durch
\mathdisp {v_1 \sim v_2 \text{ genau dann, wenn } v_1 - v_2 \in U} { }
definiert ist. Zeige, dass diese Relation eine \definitionsverweis {Äquivalenzrelation}{}{} ist.

}
{} {}

\inputaufgabe
{}
{

Es sei $K$ ein \definitionsverweis {Körper}{}{} und $V$ ein $K$-\definitionsverweis {Vektorraum}{}{.} Zeige, dass die \definitionsverweis {Relation}{}{} auf $V$, die durch
\mathdisp {v \sim w, \text{ falls es ein } \lambda \in K, \lambda \neq 0, \text{ mit } v = \lambda w \text{ gibt }} { }
eine \definitionsverweis {Äquivalenzrelation}{}{} ist. Was sind die Äquivalenzklassen?

}
{} {}

\inputaufgabegibtloesung
{}
{

Betrachte auf $\Z \times (\Z \setminus \{0\})$ die \definitionsverweis {Relation}{}{}
\mathdisp {(a,b) \sim (c,d),\, \text{ falls } ad = bc \text{ ist}} { . }

a) Zeige, dass $\sim$ eine \definitionsverweis {Äquivalenzrelation}{}{} ist.

b) Zeige, dass es zu jedem $(a,b)$ ein äquivalentes Paar $(a',b')$ mit
\mavergleichskette
{\vergleichskette
{ b' }
{ > }{0 }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} gibt.

c) Es sei $M$ die Menge der \definitionsverweis {Äquivalenzklassen}{}{} dieser Äquivalenzrelation. Wir definieren eine Abbildung \maabbeledisp {\varphi} {\Z} {M } {z} { [ (z,1)] } {.} Zeige, dass $\varphi$ \definitionsverweis {injektiv}{}{} ist.

d) Definiere auf $M$ \zusatzklammer {aus Teil c} {} {} eine \definitionsverweis {Verknüpfung}{}{} $+$ derart, dass $M$ mit dieser Verknüpfung und mit $[(0,1)]$ als neutralem Element eine \definitionsverweis {Gruppe}{}{} wird, und dass für die Abbildung $\varphi$ die Beziehung
\mavergleichskettedisp
{\vergleichskette
{ \varphi(z_1 + z_2) }
{ =} {\varphi(z_1) + \varphi(z_2) }
{ } { }
{ } { }
{ } { }
} {}{}{} für alle
\mavergleichskette
{\vergleichskette
{ z_1,z_2 }
{ \in }{ \Z }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} gilt.

}
{} {}

\inputaufgabegibtloesung
{}
{

Es seien \mathkor {} {M} {und} {N} {} Mengen und sei \maabb {f} {M} {N } {} eine Abbildung. Zeige, dass durch die Festlegung
\mavergleichskettedisp
{\vergleichskette
{x }
{ \sim} {y }
{ } { }
{ } { }
{ } { }
} {}{}{,} wenn
\mavergleichskettedisp
{\vergleichskette
{f(x) }
{ =} {f(y) }
{ } { }
{ } { }
{ } { }
} {}{}{,} eine \definitionsverweis {Äquivalenzrelation}{}{} auf $M$ definiert wird.

}
{} {}

\inputaufgabegibtloesung
{}
{

Es sei $M$ die Menge der zweimal stetig differenzierbaren Funktionen von $\R$ nach $\R$. Definiere auf $M$ eine Relation durch
\mathdisp {f \sim g \text{ falls } f(0)=g(0),\, f'(0)=g'(0) \text{ und } f^{\prime \prime}(1) = g^{\prime \prime} (1)} { . }

a) Zeige, dass dies eine \definitionsverweis {Äquivalenzrelation}{}{} ist.

b) Finde für jede Äquivalenzklasse dieser Äquivalenzrelation einen polynomialen Vertreter.

c) Zeige, dass diese Äquivalenzrelation mit der Addition von Funktionen verträglich ist.

d) Zeige, dass diese Äquivalenzrelation nicht mit der Multiplikation von Funktionen verträglich ist.

}
{} {}

\inputaufgabe
{}
{

Es sei
\mavergleichskette
{\vergleichskette
{U }
{ \subseteq }{ \R^n }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} eine Teilmenge mit der induzierten \definitionsverweis {Metrik}{}{.} Betrachte die \definitionsverweis {Relation}{}{} $R$ auf $U$, wobei $xRy$ bedeutet, dass es eine \definitionsverweis {stetige Abbildung}{}{} \maabbeledisp {\gamma} {[0,1]} {\R^n } {t} { \gamma(t) } {,} mit \mathkor {} {\gamma(0)=x} {und} {\gamma(1)=y} {} gibt. Zeige, dass dies eine \definitionsverweis {Äquivalenzrelation}{}{} auf $U$ ist.

}
{} {}

\inputaufgabe
{}
{

Es sei $M$ eine Menge und $\sim$ eine \definitionsverweis {Äquivalenzrelation}{}{} auf $M$ mit den \definitionsverweis {Äquivalenzklassen}{}{} $[x]$. Es sei $I$ die Menge aller Äquivalenzklassen. Zeige folgende Aussagen. \aufzaehlungzwei {Es ist $x\sim y$ genau dann, wenn $[x]=[y]$ ist, und dies gilt genau dann, wenn $[x] \cap [y] \neq \emptyset$. } {$M = \bigcup_{x\in I} [x]$ ist eine disjunkte Vereinigung.}

}
{} {}

\zwischenueberschrift{Aufgaben zum Abgeben}

\inputaufgabe
{}
{

Wir betrachten für je zwei Teilmengen
\mavergleichskette
{\vergleichskette
{A,B }
{ \subseteq }{\N }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} die \definitionsverweis {symmetrische Differenz}{}{}
\mavergleichskettedisp
{\vergleichskette
{ A \triangle B }
{ \defeq} {(A \setminus B) \cup (B \setminus A) }
{ } { }
{ } { }
{ } { }
} {}{}{.} Wir setzen
\mavergleichskette
{\vergleichskette
{A }
{ \sim }{B }
{ }{ }
{ }{ }
{ }{ }
} {}{}{,} falls
\mathl{A \triangle B}{} \definitionsverweis {endlich}{}{} ist. Zeige, dass dadurch eine \definitionsverweis {Äquivalenzrelation}{}{} auf
\mathl{\mathfrak {P} \, (\N )}{} definiert wird.

}
{} {}

\inputaufgabe
{}
{

Es sei $S$ ein \definitionsverweis {Symbolalphabet}{}{} einer Sprache erster Stufe, $T$ die Menge der $S$-\definitionsverweis {Terme}{}{} und $I$ eine $S$-\definitionsverweis {Interpretation}{}{.} Zeige, dass auf $T$ durch
\mathdisp {s \sim t, \text{ falls } I(s)=I(t)} { , }
eine \definitionsverweis {Äquivalenzrelation}{}{} definiert wird.

}
{} {}

\inputaufgabe
{}
{

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
{}
{

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
{}
{

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.

}
{} {}

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

}
{} {Tipp=Betrache Ausdrücke der Form
\mathl{x \not = 1+1 + \cdots + 1}{.}}