Kurs:Einführung in die mathematische Logik/17/Klausur mit Lösungen

Aufgabe	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	${}\sum$
Punkte	3	3	2	2	2	2	5	2	3	7	2	8	4	5	3	3	2	2	4	64

Aufgabe (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Eine maximal widerspruchsfreie prädikatenlogische Ausdrucksmenge ${}\Gamma \subseteq L^{S}$.
2. Ein topologischer Filter auf einem topologischen Raum ${}X$.
3. Die Interpretation der Terme zu einem Symbolalphabet ${}S$ in einer gegebenen ${}S$- Interpretation auf einer Grundmenge ${}M$.
4. Eine funktional abgeschlossene Teilmenge ${}T\subseteq M$ einer ${}S$- Struktur ${}M$, wobei ${}S$ ein erststufiges Symbolalphabet bezeichnet.
5. Eine vollständige Theorie ${}T\subseteq L_{0}^{S}$.
6. Ein modallogisches Modell.

Lösung

1. Die Menge ${}\Gamma$ heißt maximal widerspruchsfrei, wenn sie widerspruchsfrei ist und wenn jede Hinzunahme eines jeden Ausdrucks ${}\alpha \not \in \Gamma$ die Menge widersprüchlich macht.
2. Ein System ${}F$ aus offenen Teilmengen von ${}X$ heißt Filter, wenn folgende Eigenschaften gelten ($U,V$ seien offen).
   1. ${}X\in F$.
   2. Mit ${}U\in F$ und ${}U\subseteq V$ ist auch ${}V\in F$.
   3. Mit ${}U\in F$ und ${}V\in F$ ist auch ${}U\cap V\in F$.
3. Die Terminterpretation ${}I(t)\in M$ wird induktiv über den Aufbau der Terme für jeden ${}S$- Term ${}t$ definiert.
   1. Für jede Konstante ${}c$ und jede Variable ${}x$ ist die Terminterpretation durch die Interpretation bzw. die Belegung direkt gegeben, also ${}I(c)=c^{M}$ und ${}I(x)=x^{M}$.
   2. Wenn ${}t_{1},\ldots ,t_{n}$ Terme mit Interpretationen ${}I(t_{1}),\ldots ,I(t_{n})$ sind und wenn ${}f$ ein ${}n$-stelliges Funktionssymbol ist, so wird der Term ${}ft_{1}\ldots t_{n}$ als ${}f^{M}(I(t_{1}),\ldots ,I(t_{n}))$ interpretiert.
4. Die Teilmenge ${}T$ heißt funktional abgeschlossen, wenn für jede Konstante ${}c\in S$ das Element ${}c^{M}$ zu ${}T$ gehört und für jedes ${}k$-stellige Funktionssymbol ${}f$ und beliebige Elemente ${}m_{1},\ldots ,m_{k}\in T$ auch ${}f^{M}(m_{1},\ldots ,m_{k})$ zu ${}T$ gehört.
5. Die Theorie ${}T$ heißt vollständig, wenn für jeden Satz ${}\alpha \in L_{0}^{S}$ gilt ${}\alpha \in T$ oder ${}\neg \alpha \in T$.
6. Unter einem modallogischen Modell versteht man einen gerichteten Graphen ${}(M,R)$ zusammen mit einer Wahrheitsbelegung ${}\mu$ für die Aussagenvariablen für jeden Knotenpunkt ${}w\in M$.

Aufgabe (3 Punkte)

Formuliere die folgenden Sätze.

1. Der Satz von Henkin.
2. Der Satz über das Halteproblem.
3. Die Unentscheidbarkeit der Arithmetik.

Lösung

1. Es sei ${}\Gamma$ eine Menge an ${}S$- Ausdrücken (über einem Symbolalphabet ${}S$), die maximal widerspruchsfrei ist und Beispiele enthält. Dann ist die durch die kanonische Termidentifizierung gegebene Interpretation ein Modell für ${}\Gamma$.
2. Die Menge

   ${\left\{n\in \mathbb {N} \mid n{\text{ ist die Nummer eines Registerprogramms }}P{\text{ und }}P(0){\text{ hält an}}\right\}}$

   ist nicht ${}R$-

   entscheidbar.
3. Die Menge der wahren arithmetischen Ausdrücke (ohne freie Variablen) ist nicht ${}R$- entscheidbar.

Aufgabe (2 Punkte)

${}E$ wurde ermordet. Es gelten folgende Sachverhalte.

1. Der Mörder ist ${}A$ oder ${}B$ oder ${}C$ oder ${}D$.
2. Wenn ${}C$ der Mörder ist, dann ist ${}D$ nicht der Mörder oder ${}A$ ist der Mörder.
3. ${}A,B,C,D$ sind alle verschieden.
4. Es gibt genau einen Mörder.
5. Wenn ${}A$ nicht der Mörder ist, dann ist ${}D$ nicht der Mörder.
6. ${}A$ ist genau dann der Mörder, wenn ${}B$ der Mörder ist.

Wer ist der Mörder?

Lösung

Aus (6), (3) und (4) folgt, dass ${}A$ und ${}B$ beide nicht der Mörder sind, denn sonst wären beide der Mörder. Nach (5) ist somit auch ${}D$ nicht der Mörder. Wegen (1) muss also ${}C$ der Mörder sein. ((2) wird nicht verwendet.)

Aufgabe (2 Punkte)

Finde einen möglichst einfachen aussagenlogischen Ausdruck, der die folgende tabellarisch dargestellte Wahrheitsfunktion ergibt.

${}p$ ${}q$ ${}r$ ${}?$ w w w w w w f f w f w w w f f f f w w f f w f w f f w f f f f w

Lösung

$p\leftrightarrow r.$

Aufgabe (2 Punkte)

Erläutere die Beziehung zwischen dem Modus ponens und

$\vdash \alpha \wedge {\left(\alpha \rightarrow \beta \right)}\rightarrow \beta .$

Lösung Modus ponens/Interne Version/Erläuterung/Aufgabe/Lösung

Aufgabe (2 Punkte)

Es sei ${}\Gamma \subseteq L^{V}$ eine Ausdrucksmenge in der Sprache der Aussagenlogik zu einer Aussagenvariablenmenge ${}V$. Begründe die Widerspruchsregel für die Ableitungsbeziehung: Wenn ${}\Gamma \vdash \alpha$ und ${}\Gamma \vdash \neg \alpha$, dann ist auch ${}\Gamma \vdash \beta$.

Lösung

Es gilt

$\vdash \neg \alpha \wedge \alpha \rightarrow \beta$

nach Axiom 3.8 (Einführung in die mathematische Logik (Osnabrück 2021))   (5). Nach der Voraussetzung und Lemma 4.2 (Einführung in die mathematische Logik (Osnabrück 2021))  (5) ergibt sich daraus ${}\vdash \beta$.

Aufgabe (5 (2+2+1) Punkte)

Es sei ${}N$ ein einstelliges Funktionssymbol, ${}F$ und ${}G$ seien zweistellige Funktionssymbole und ${}x,y$ seien Variablen.

Wir betrachten die folgenden Modelle (wobei ${}M$ die Grundmenge bezeichnet).

a) ${}M=\mathbb {R}$, ${}N$ ist die Quadrierung, ${}F$ die Addition und ${}G$ die Multiplikation.

b) ${}M=C^{\infty }(\mathbb {R} ,\mathbb {R} )={\left\{f:\mathbb {R} \rightarrow \mathbb {R} \mid f{\text{ unendlich oft differenzierbar}}\right\}}$, ${}N$ ist das Differenzieren von Funktionen, ${}F$ die Multiplikation und ${}G$ die Addition von Funktionen. Bestimme, ob in diesen Modellen die folgenden Aussagen wahr werden.

1. $\forall x\forall y{\left(NFxy=GFxNyFNxy\right)}.$

2. $\forall y\exists x{\left(NFxy=GFxNyFNxy\right)}.$

3. $\exists y\forall x{\left(NFxy=GFxNyFNxy\right)}.$

Lösung

Im ersten Modell ist ${}NFxy$ als ${}(x+y)^{2}$ und ${}GFxNyFNxy$ als ${}(x+y^{2})\cdot (x^{2}+y)$ zu interpretieren, wobei ${}x,y$ reelle Zahlen sind.

1. Die Gleichung

   ${}(x+y)^{2}=(x+y^{2})\cdot (x^{2}+y)\,$

   gilt in ${}\mathbb {R}$ definitiv nicht für alle reelle Zahlen, beispielsweise gilt sie für ${}x=1$ und ${}y=2$ nicht.

2. Wir schreiben die Gleichung als

   ${}y^{3}+x^{2}y^{2}+x^{3}+xy-x^{2}-2xy-y^{2}=0\,.$

   Für ein beliebiges aber fixiertes ${}x$ ist der Ausdruck links ein normiertes Polynom vom Grad ${}3$ in ${}y$. Dieses besitzt nach dem Zwischenwertsatz eine Nullstelle, deshalb ist die Aussage wahr.

3. Zu jedem ${}y$ ist der Ausdruck links aus (2) ein Polynom in ${}x$ vom Grad ${}3$, also definitiv nicht das Nullpolynom, die Aussage ist also falsch.

Im zweiten Modell ist ${}NFxy$ als ${}(x\cdot y)'$ und ${}GFxNyFNxy$ als ${}(x'\cdot y)+(x\cdot y')$ zu interpretieren, wobei ${}x,y$ unendlich oft differenzierbare Funktionen sind. Dies ist die Produktregel für die Ableitung, also wahr für beliebige ${}x,y$. Damit gilt insbesondere auch (2) und (3), da es ja unendlich oft differenzierbare Funktionen gibt.

Aufgabe (2 Punkte)

Es sei ein Symbolalphabet ${}S$ erster Stufe mit der Variablenmenge

${}V=\{x,y,z,w\}\,$

gegeben und eine ${}S$- Interpretation ${}I$ in der Menge ${}\mathbb {R}$ mit

$I(x)=5,\,I(y)=\pi ,\,I(z)=-{\sqrt {2}},\,I(w)=-3.$

Bestimme die Werte von ${}x,y,z,w$ bei der Interpretation ${}J:=I{\frac {e,-{\sqrt {2}},{\frac {4}{7}},I(x)}{x,z,x,y}}$ auf ${}V$.

Lösung

Es ist

${}J:=I{\frac {e,-{\sqrt {2}},{\frac {4}{7}},I(x)}{x,z,x,y}}=I{\frac {e,-{\sqrt {2}},{\frac {4}{7}},5}{x,z,x,y}}\,.$

Ferner ist dieser Ausdruck von innen nach außen, bzw. von links nach rechts zu lesen, also als

${\left({\left({\left(I{\frac {e}{x}}\right)}{\frac {-{\sqrt {2}}}{z}}\right)}{\frac {\frac {4}{7}}{x}}\right)}{\frac {5}{y}}.$

Daher ist

$J(x)={\frac {4}{7}},\,J(y)=5,\,J(z)=-{\sqrt {2}},\,J(w)=-3.$

Aufgabe (3 Punkte)

Es seien ${}x,y,z$ Variablen (mit der angegebenen Reihenfolge), ${}c$ eine Konstante und ${}f$ ein einstelliges Funktionssymbol.

1. Bestimme

   $(\exists x(x=c)){\frac {z}{x}}.$

2. Bestimme

   $(\exists x(x=c)){\frac {x}{x}}.$

3. Bestimme

   $(\exists x(x=c)){\frac {fx}{x}}.$

Lösung

Die zu substituierende Variable ${}x$ kommt im Ausdruck ${}\exists x(x=c)$ nicht frei vor. Somit ist jedenfalls für den jeweiligen Term ${}t$

${}(\exists x(x=c)){\frac {t}{x}}=\exists v((x=c){\frac {v}{x}})\,.$

Da die relevante Termmenge leer ist, ist

${}v=x\,$

Also ist

1. ${}(\exists x(x=c)){\frac {z}{x}}=\exists x((x=c)){\frac {x}{x}})=\exists x(x=c)\,.$

2. ${}(\exists x(x=c)){\frac {x}{x}}=\exists x((x=c){\frac {x}{x}})=\exists x(x=c)\,.$

3. ${}(\exists x(x=c)){\frac {fx}{x}}=\exists x((x=c){\frac {x}{x}})=\exists x(x=c)\,.$

Aufgabe (7 Punkte)

Zeige, dass die Existenzeinführung im Antezedens eine korrekte Regel ist.

Lösung

Es sei ${}\alpha {\frac {y}{x}}\rightarrow \beta$ allgemeingültig, d.h.

$I\vDash \alpha {\frac {y}{x}}\rightarrow \beta$

für jede ${}S$- Interpretation ${}I$. Wir müssen zeigen, dass dann auch ${}\exists x\alpha \rightarrow \beta$ allgemeingültig ist (unter den gegebenen Voraussetzungen). Es sei dazu ${}I$ eine Interpretation mit

$I\vDash \exists x\alpha .$

Aufgrund der Modellbeziehung bedeutet dies, dass es ein ${}m\in M$ (aus der Grundmenge der Interpretation) mit

$I{\frac {m}{x}}\vDash \alpha$

gibt. Die Variable ${}y$ kommt nach Voraussetzung in ${}\exists x\alpha$ nicht frei vor, d.h. bei ${}y\neq x$, dass ${}y$ in ${}\alpha$ nicht frei vorkommt. Wir können daher das Koinzidenzlemma anwenden und erhalten

${\left(I{\frac {m}{x}}\right)}{\frac {m}{y}}\vDash \alpha .$

Diese Aussage gilt trivialerweise auch bei ${}x=y$. Damit gilt auch

${\left(I{\frac {m}{y}}\right)}{\frac {m}{x}}\vDash \alpha .$

Wir schreiben dies (etwas künstlich) als

${\left(I{\frac {m}{y}}\right)}{\frac {{\left(I{\frac {m}{y}}\right)}(y)}{x}}\vDash \alpha .$

Darauf können wir das Substitutionslemma (für die Interpretation ${}J=I{\frac {m}{y}}$ und den Term ${}y$) anwenden und erhalten

$I{\frac {m}{y}}\vDash \alpha {\frac {y}{x}}.$

Wegen der vorausgesetzten Allgemeingültigkeit von ${}\alpha {\frac {y}{x}}\rightarrow \beta$ folgt

$I{\frac {m}{y}}\vDash \beta .$

Da ${}y$ in ${}\beta$ nicht frei vorkommt, liefert das Koinzidenzlemma

$I\vDash \beta .$

Aufgabe (2 Punkte)

Zeige, dass in einem kommutativen Halbring die Beziehung ${}0\cdot 0=0$ gilt.

Lösung

Dies ergibt sich aus

${}0\cdot 0=0\cdot 0+0=0\cdot 0+0\cdot 1=0\cdot (0+1)=0\cdot 1=0\,.$

Aufgabe (8 (1+2+3+2) Punkte)

Es sei ${}S$ ein Symbolalphabet und ${}L^{S}$ die zugehörige Sprache erster Stufe. Es sei ${}I$ eine ${}S$- Interpretation mit der Grundmenge ${}N$ und es sei ${}\Gamma :=I^{\vDash }$ mit der zugehörigen Äquivalenzrelation ${}\sim$ auf der Termmenge ${}T$.

1. Zeige, dass ${}s\sim t$ genau dann gilt, wenn ${}I(s)=I(t)$ gilt.
2. Zeige, dass es eine injektive Abbildung

   $\psi \colon T/\sim \longrightarrow N$

   mit

   ${}\psi ([t])=I(t)\,$

   gibt.

3. Zeige, dass ${}\psi$ ein ${}S$- Homomorphismus ist, wenn die Quotientenmenge ${}T/\sim$ mit der kanonischen ${}S$- Struktur versehen wird.
4. Es sei ${}J$ die kanonische Interpretation auf ${}T/\sim$. Es sei vorausgesetzt, dass die Terminterpretation für ${}N$ surjektiv sei. Zeige, dass ${}I\vDash \alpha$ genau dann gilt, wenn ${}J\vDash \alpha$ gilt.

Lösung

1. Es ist ${}s\sim t$ genau dann, wenn ${}s=t\in \Gamma =I^{\vDash }$ ist, und dies ist genau dann der Fall, wenn ${}I\vDash s=t$ gilt, was nach Definition ${}I(s)=I(t)$ bedeutet.
2. Die Termabbildung

   $I\colon T\longrightarrow N,\,t\longmapsto I(t),$

   besitzt nach Teil (1) die Eigenschaft, dass äquivalente Terme auf das gleiche Element abgebildet werden. Dies bedeutet nach Lemma 11.13 (Diskrete Mathematik (Osnabrück 2020)), dass es eine Abbildung

   $\psi \colon T/\sim \longrightarrow N$

   mit ${}\psi ([t])=I(t)$ gibt. Da nichtäquivalente Terme nach Teil (1) unter ${}I$ auf verschiedene Elemente abgebildet werden, werden verschiedene Klassen unter ${}\psi$ auf verschiedene Elemente abgebildet und somit ist ${}\psi$ injektiv.

3. Sei

   ${}M=T/\sim \,.$

   Für eine Konstante ${}c\in T$ ist

   ${}\psi (c^{M})=\psi ([c])=I(c)=c^{N}\,.$

   Für ein ${}n$-stelliges Funktionssymbol ${}f$ und ${}n$ Termklassen ${}[t_{1}],\ldots ,[t_{n}]$ ist

   ${}{\begin{aligned}\psi (f^{M}([t_{1}],\ldots ,[t_{n}]))&=\psi ([ft_{1}\ldots t_{n}])\\&=I(ft_{1}\ldots t_{n})\\&=f^{N}(I(t_{1}),\ldots ,I(t_{n}))\\&=f^{N}(\psi ([t_{1}]),\ldots ,\psi ([t_{n}])).\end{aligned}}$

   Es sei nun eine ${}n$-stellige Relation ${}R$ und ${}n$ Termklassen ${}[t_{1}],\ldots ,[t_{n}]$ gegeben und sei die Gültigkeit von ${}R^{M}[t_{1}],\ldots ,[t_{n}]$ in ${}M$ vorausgesetzt. Dies bedeutet, dass ${}Rt_{1}\ldots t_{n}\in \Gamma =I^{\vDash }$ ist. Somit ist ${}I\vDash Rt_{1}\ldots t_{n}$, was ${}R^{N}(I(t_{1}),\ldots ,I(t_{n}))$ bedeutet. Somit ist ${}R^{N}(\psi ([t_{1}]),\ldots ,\psi ([t_{n}]))$. Es liegt also ein ${}S$- Homomorphismus vor.

4. Nach Definition von ${}\Gamma$ ist ${}\alpha \in \Gamma$ genau dann, wenn ${}I\vDash \alpha$ gilt. Nach Lemma 14.5 (Einführung in die mathematische Logik (Osnabrück 2021)) ist ${}\Gamma$ maximal widerspruchsfrei und enthält Beispiele und nach dem Satz von Henkin ist

   ${}\Gamma =J^{\vDash }\,.$

Aufgabe (4 Punkte)

Bestimme die Äquivalenzklassen zur elementaren Äquivalenz in der Gruppe ${}\mathbb {Z} /(2)\times \mathbb {Z} /(3)$ zum Symbolalphabet ${}S=\{0,+\}$.

Lösung

Die Äquivalenzklassen sind

$\{(0,0)\},\,\{(1,0)\},\,\{(0,1),(0,2)\},\,\{(1,1),(1,2)\}.$

Nach (dem Zusatz zu) Satz 16.7 (Einführung in die mathematische Logik (Osnabrück 2021)) sind Elemente, die unter einem Automorphismus aufeinander abgebildet werden, zueinander elementar äquivalent. Die Abbildung, die in der ersten Komponente die Identität und in der zweiten Komponente ${}1$ und ${}2$ vertauscht, ist ein Automorphismus. Daher sind die in den zweielementigen Klassen angegebenen Elemente zueinander elementar äquivalent. Es ist also noch zu zeigen, dass die vier Klassen voneinander trennbar sind. Die in der angegebenen Sprache formulierbare Eigenschaft ${}x=0$ wird nur durch das neutrale Element erfüllt und ist somit ein charakterisierender Ausdruck für ${}\{(0,0)\}$. Die Eigenschaft

$x\neq 0\wedge x+x=0$

charakterisiert die zweite Klasse. Die Eigenschaft

$x\neq 0\wedge x+x+x=0$

charakterisiert die dritte Klasse. Die Eigenschaft

$x+x\neq 0\wedge x+x+x\neq 0\wedge x+x+x+x+x+x=0$

(der letzte Teil der Konjunktion ist nicht nötig) charakterisiert die vierte Klasse.

Aufgabe (5 Punkte)

Man entwerfe ein Programm für eine Registermaschine, das bei der Eingabe ${}n$ im ersten Register den Rest bei der Division mit Rest von ${}n$ durch ${}5$ ausgibt.

Lösung Registermaschine/Modulo 5/Rest/Aufgabe/Lösung

Aufgabe (3 (2+1) Punkte)

1. Zeige, dass die Teilmenge der natürlichen Zahlen, die man als Summe von drei Quadraten schreiben kann, arithmetisch repräsentierbar ist.
2. Formuliere in der arithmetischen Sprache, dass die ${}7$ keine Summe von drei Quadraten ist.

Lösung

1. Wir betrachten die Ausdruck

   ${}\Psi =\exists u\exists v\exists w(x=u\cdot u+v\cdot v+w\cdot w)\,$

   in der einen freien Variablen ${}x$. Offenbar kann man eine natürliche Zahl ${}n$ genau dann als Summe von drei Quadraten schreiben, wenn innerhalb von ${}\mathbb {N}$ der Ausdruck ${}\Psi (n)$ gilt.

2. Eine Formulierung ist

   $\forall u\forall v\forall w\neg (1+1+1+1+1+1+1=u\cdot u+v\cdot v+w\cdot w).$

Aufgabe (3 Punkte)

Beweise den ersten Gödelschen Unvollständigkeitssatz mit dem Unvollständigkeitslemma.

Lösung

 Wir nehmen an, dass ${}\Gamma ^{\vdash }$ vollständig ist. Da ${}\Gamma$ aufzählbar ist, ist ${}\Gamma ^{\vdash }$ nach Lemma 21.9 (Einführung in die mathematische Logik (Osnabrück 2021)) aufzählbar und nach Satz 21.10 (Einführung in die mathematische Logik (Osnabrück 2021)) auch entscheidbar. Da ${}\Gamma$ Repräsentierungen erlaubt, ist insbesondere ${}\Gamma ^{\vdash }$ repräsentierbar. Daher sind die Voraussetzungen von Lemma 23.1 (Einführung in die mathematische Logik (Osnabrück 2021)) erfüllt und es ergibt sich ein Widerspruch zur angenommenen Vollständigkeit.

Aufgabe (2 Punkte)

Zeige, dass in der ${}K$- Modallogik das Schema

$\Box \alpha \wedge \Box \neg \alpha \rightarrow \Box \beta$

ableitbar ist.

Lösung

Aus der aussagenlogischen Tautologie

$\vdash \alpha \wedge \neg \alpha \rightarrow \beta$

ergibt sich mit Lemma 24.5 (Einführung in die mathematische Logik (Osnabrück 2021))  (1)

$\vdash \Box (\alpha \wedge \neg \alpha )\rightarrow \Box \beta .$

Wegen Lemma 24.5 (Einführung in die mathematische Logik (Osnabrück 2021))  (4) gilt

$\vdash \Box \alpha \wedge \Box \neg \alpha \rightarrow \Box (\alpha \wedge \neg \alpha ).$

Der Kettenschluss liefert

$\vdash \Box \alpha \wedge \Box \neg \alpha \rightarrow \Box \beta .$

Aufgabe (2 Punkte)

Wir arbeiten mit den Aussagenvariablen ${}p,q,r$. Im Weltpunkt ${}a$ gelte

$a\vDash p,q,\neg r$

und im Weltpunkt ${}b$ gelte

$b\vDash p,\neg q,r.$

Bestimme die Wahrheitswerte von ${}\Box p\wedge \Diamond (\neg q)\rightarrow \Box r$ in den beiden Weltpunkten.

Lösung

Wegen ${}a\vDash p$ und ${}b\vDash p$ gilt ${}a\vDash \Box p$. Wegen ${}b\vDash \neg q$ gilt ${}a\vDash \Diamond \neg q$ und somit gilt in ${}a$ der Vordersatz der Aussage. Wegen ${}a\vDash \neg r$ gilt ${}a\vDash \neg \Box r$. Daher ist der Nachsatz der Aussage falsch in ${}a$ und somit ist die Gesamtaussage dort falsch.

Von ${}b$ aus ist nur ${}b$ erreichbar ist, dort gilt ${}r$ also auch ${}\Box r$. Damit gilt der Nachsatz und damit die Gesamtaussage in ${}b$.

Aufgabe (4 Punkte)

Beweise den Vollständigkeitssatz der Modallogik.

Lösung

Die Hinrichtung ergibt sich aus Lemma 26.9 (Einführung in die mathematische Logik (Osnabrück 2021)). Für die Rückrichtung nehmen wir

$\Gamma \not \vdash \alpha$

an. Dann ist

${}\Gamma '=\Gamma \cup \{\neg \alpha \}\,$

(aussagenlogisch) nicht widersprüchlich und wir müssen zeigen, dass ${}\Gamma '$ durch ein ${}\Gamma$-modallogisches Modell erfüllbar ist. Wir betrachten dazu das ${}\Gamma$- universelle modallogische Modell ${}(U_{\Gamma },R,\nu )$, in dem ${}\Gamma$ (in jedem Weltpunkt) gilt. Nach Lemma 27.1 (Einführung in die mathematische Logik (Osnabrück 2021)) gibt es eine maximal widerspruchsfreie ${}\Gamma '$-Ausdrucksmenge ${}{\tilde {\Gamma }}$, die wir als Welt ${}W={\tilde {\Gamma }}$ in ${}U_{\Gamma }$ betrachten können. Nach Lemma 27.6 (Einführung in die mathematische Logik (Osnabrück 2021)) gilt ${}W\vDash {\tilde {\Gamma }}$, was insbesondere die Gültigkeit von ${}\Gamma \cup \{\neg \alpha \}$ in ${}W$ zeigt.