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

Übungsaufgaben

Aufgabe Referenznummer erstellen

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

Aufgabe Referenznummer erstellen

Diskutiere Metasprache und Objektsprache anhand der Formulierung „im Widerspruch zur Widerspruchsfreiheit“ aus dem Beweis zu Lemma 15.1.

Aufgabe Referenznummer erstellen

Es sei ${}S$ ein Symbolalphabet (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 „natürlich“ und Relationssymbole willkürlich interpretiert.

Aufgabe Referenznummer erstellen

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

Aufgabe Referenznummer erstellen

Es sei ${}\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.

Aufgabe * Referenznummer erstellen

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

Aufgabe * Aufgabe 15.7 ändern

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

Aufgabe Referenznummer erstellen

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

„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“.

„6.22 Die Logik der Welt, die die Sätze der Logik in den Tautologien zeigen, zeigt die Mathematik in den Gleichungen“.

„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“.

„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“.

„6.24 Die Methode der Mathematik, zu ihren Gleichungen zu kommen, ist die Substitutionsmethode“. (...)

Wir besprechen den für die Konstruktion eines Modells (zum Satz von Henkin) wichtigen Begriff einer Äquivalenzrelation anhand einiger Aufgaben.

Aufgabe Referenznummer erstellen

Wir betrachten die ganzen Zahlen ${}\mathbb {Z}$ und eine fixierte natürliche Zahl ${}a\geq 0$. Zeige, dass auf ${}\mathbb {Z}$ durch

$x\sim y,{\text{ wenn die Differenz }}x-y{\text{ ein Vielfaches von }}a{\text{ ist}},$

eine Äquivalenzrelation definiert wird. Wie viele Äquivalenzklassen gibt es?

Aufgabe Referenznummer erstellen

Es sei ${}K$ ein Körper, ${}V$ ein ${}K$- Vektorraum und ${}U\subseteq V$ ein Untervektorraum. Wir betrachten die Relation auf ${}V$, die durch

$v_{1}\sim v_{2}{\text{ genau dann, wenn }}v_{1}-v_{2}\in U$

definiert ist. Zeige, dass diese Relation eine Äquivalenzrelation ist.

Aufgabe Referenznummer erstellen

Es sei ${}K$ ein Körper und ${}V$ ein ${}K$- Vektorraum. Zeige, dass die Relation auf ${}V$, die durch

$v\sim w,{\text{ falls es ein }}\lambda \in K,\lambda \neq 0,{\text{ mit }}v=\lambda w{\text{ gibt }}$

eine Äquivalenzrelation ist. Was sind die Äquivalenzklassen?

Aufgabe * Referenznummer erstellen

Betrachte auf ${}\mathbb {Z} \times (\mathbb {Z} \setminus \{0\})$ die Relation

$(a,b)\sim (c,d),\,{\text{ falls }}ad=bc{\text{ ist}}.$

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

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

c) Es sei ${}M$ die Menge der Äquivalenzklassen dieser Äquivalenzrelation. Wir definieren eine Abbildung

$\varphi \colon \mathbb {Z} \longrightarrow M,\,z\longmapsto [(z,1)].$

Zeige, dass ${}\varphi$ injektiv ist.

d) Definiere auf ${}M$ (aus Teil c) eine Verknüpfung ${}+$ derart, dass ${}M$ mit dieser Verknüpfung und mit ${}[(0,1)]$ als neutralem Element eine Gruppe wird, und dass für die Abbildung ${}\varphi$ die Beziehung

${}\varphi (z_{1}+z_{2})=\varphi (z_{1})+\varphi (z_{2})\,$

für alle ${}z_{1},z_{2}\in \mathbb {Z}$ gilt.

Aufgabe * Referenznummer erstellen

Es seien ${}M$ und ${}N$ Mengen und sei ${}f\colon M\rightarrow N$ eine Abbildung. Zeige, dass durch die Festlegung

${}x\sim y\,,$

wenn

${}f(x)=f(y)\,,$

eine Äquivalenzrelation auf ${}M$ definiert wird.

Aufgabe * Referenznummer erstellen

Es sei ${}M$ die Menge der zweimal stetig differenzierbaren Funktionen von ${}\mathbb {R}$ nach ${}\mathbb {R}$. Definiere auf ${}M$ eine Relation durch

$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 Ä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.

Aufgabe Referenznummer erstellen

Es sei ${}U\subseteq \mathbb {R} ^{n}$ eine Teilmenge mit der induzierten Metrik. Betrachte die Relation ${}R$ auf ${}U$, wobei ${}xRy$ bedeutet, dass es eine stetige Abbildung

$\gamma \colon [0,1]\longrightarrow \mathbb {R} ^{n},\,t\longmapsto \gamma (t),$

mit ${}\gamma (0)=x$ und ${}\gamma (1)=y$ gibt. Zeige, dass dies eine Äquivalenzrelation auf ${}U$ ist.

Aufgabe Referenznummer erstellen

Es sei ${}M$ eine Menge und ${}\sim$ eine Äquivalenzrelation auf ${}M$ mit den Äquivalenzklassen ${}[x]$. Es sei ${}I$ die Menge aller Äquivalenzklassen. Zeige folgende Aussagen.

1. Es ist ${}x\sim y$ genau dann, wenn ${}[x]=[y]$ ist, und dies gilt genau dann, wenn ${}[x]\cap [y]\neq \emptyset$.
2. ${}M=\bigcup _{x\in I}[x]$ ist eine disjunkte Vereinigung.

Aufgaben zum Abgeben

Aufgabe (2 Punkte)Referenznummer erstellen

Wir betrachten für je zwei Teilmengen ${}A,B\subseteq \mathbb {N}$ die symmetrische Differenz

${}A\triangle B:=(A\setminus B)\cup (B\setminus A)\,.$

Wir setzen ${}A\sim B$, falls ${}A\triangle B$ endlich ist. Zeige, dass dadurch eine Äquivalenzrelation auf ${}{\mathfrak {P}}\,(\mathbb {N} )$ definiert wird.

Aufgabe (2 Punkte)Referenznummer erstellen

Es sei ${}S$ ein Symbolalphabet einer Sprache erster Stufe, ${}T$ die Menge der ${}S$- Terme und ${}I$ eine ${}S$- Interpretation. Zeige, dass auf ${}T$ durch

$s\sim t,{\text{ falls }}I(s)=I(t),$

eine Äquivalenzrelation definiert wird.

Aufgabe (4 Punkte)Referenznummer erstellen

Es seien ${}s,t$ nicht identische ${}S$- Terme. Zeige, dass es ein endliches ${}S$- Modell mit

${}I(s)\neq I(t)\,$

gibt.

Aufgabe (3 Punkte)Referenznummer erstellen

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

Aufgabe (4 Punkte)Aufgabe 15.21 ändern

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

Aufgabe (4 Punkte)Aufgabe 15.22 ändern

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