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

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

Aufgabe (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Ein maximales Element ${}x\in I$ in einer geordneten Menge ${}(I,\preccurlyeq )$.
2. Die Termsubstitution ${}s{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}$ für ${}S$-Terme ${}s$ (dabei sei ${}S$ ein Symbolalphabet einer Sprache erster Stufe, ${}x_{1},\ldots ,x_{k}$ paarweise verschiedene Variablen und ${}t_{1},\ldots ,t_{k}$ fixierte ${}S$- Terme).
3. Der Rang eines prädikatenlogischen Ausdrucks ${}\alpha$.
4. Die elementare Äquivalenz von zwei ${}S$- Strukturen ${}M$ und ${}N$ über einem erststufigen Symbolalphabet ${}S$.
5. Eine ${}R$-berechenbare Funktion

   $F\colon \mathbb {N} ^{k}\longrightarrow \mathbb {N} .$

6. Die ${}\beta$-Funktion ${}\beta (p,n,i)$.

Lösung

1. Ein Element ${}x\in I$ heißt maximal, wenn es kein Element ${}y\in I$, ${}y\neq x$, mit ${}x\preccurlyeq y$ gibt.
2. Die Termsubstitution ${}s{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}$ wird rekursiv folgendermaßen definiert.
   1. Für eine Variable ${}x$ ist

      ${}x{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}:={\begin{cases}x,{\text{ falls }}x\neq x_{i}{\text{ für alle }}i\,,\\t_{i},{\text{ falls }}x=x_{i}\,.\end{cases}}\,$

   2. Für eine Konstante ${}c$ ist

      ${}c{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}:=c\,.$

   3. Für ein ${}n$-stelliges Funktionssymbol ${}f$ und ${}n$ Terme ${}s_{1},\ldots ,s_{n}$ ist

      ${}fs_{1}\ldots s_{n}{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}:=fs_{1}{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}\ldots s_{n}{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}\,.$

3. Der Rang ${}\rho$ von ${}\alpha$ wird rekursiv durch
   1. ${}\rho (\alpha )=0$, falls ${}\alpha$ atomar ist.
   2. ${}\rho (\alpha )=\rho (\beta )+1$, falls ${}\alpha =\neg (\beta )$ ist.
   3. ${}\rho (\alpha )=\rho (\beta )+\rho (\gamma )+1$, falls ${}\alpha =(\beta )\circ (\gamma )$ mit ${}\circ =\wedge ,\,\vee ,\,\rightarrow ,\leftrightarrow$ ist.
   4. ${}\rho (\alpha )=\rho (\beta )+1$, falls ${}\alpha =\exists x\beta$ oder ${}\alpha =\forall x\beta$ ist.

   definiert.

4. Die beiden ${}S$- Strukturen ${}M$ und ${}N$ heißen elementar äquivalent, wenn jeder ${}S$- Satz, der in ${}M$ gilt, auch in ${}N$ gilt.
5. Die Funktion

   $F\colon \mathbb {N} ^{k}\longrightarrow \mathbb {N}$

   heißt ${}R$-berechenbar, wenn es ein Programm ${}P$ für eine Registermaschine gibt, die bei jeder Eingabe ${}(r_{1},\ldots ,r_{k})$ (in den ersten ${}k$ Registern) anhält und ${}F(r_{1},\ldots ,r_{k})$ als (einzige) Ausgabe besitzt.

6. Unter der ${}\beta$-Funktion versteht man die Abbildung

   $\mathbb {N} ^{3}\longrightarrow \mathbb {N} ,\,(p,n,i)\longmapsto \beta (p,n,i),$

   die folgendermaßen festgelegt ist. ${}\beta (p,n,i)$ ist die kleinste Zahl ${}a\in \mathbb {N}$, die die Bedingung erfüllt, dass es natürliche Zahlen ${}b_{0},b_{1},b_{2}$ gibt, die die folgenden Eigenschaften erfüllen:

   1. ${}n=b_{0}+b_{1}{\left((i+1)+ap+b_{2}p^{2}\right)}$.
   2. ${}a<p$.
   3. ${}b_{0}<b_{1}$.
   4. ${}b_{1}$ ist eine Quadratzahl.
   5. Alle Teiler ${}d\neq 1$ von ${}b_{1}$ sind ein Vielfaches von ${}p$.

   Wenn kein solches ${}a$ existiert, so ist ${}\beta (p,n,i)=0$.

Aufgabe (3 Punkte)

Formuliere die folgenden Sätze.

1. Der Satz von Euklid über Primzahlen.
2. Das Substitutionslemma.
3. Der Satz über die induktive Definition einer Abbildung auf einem Peano-Dedekind-Modell ${}(N,0,\prime )$.

Lösung

1. Es gibt unendlich viele Primzahlen.
2. Es sei ein Symbolalphabet ${}S$ einer Sprache erster Stufe gegeben und es seien ${}x_{1},\ldots ,x_{k}$ paarweise verschiedene Variablen und ${}t_{1},\ldots ,t_{k}$ fixierte ${}S$-Terme. Es sei eine ${}S$-Interpretation ${}I$ gegeben. Dann gelten folgende Aussagen.
   1. Für jeden ${}S$-Term ${}s$ gilt

      ${}I\left(s{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}\right)=\left(I{\frac {I(t_{1}),\ldots ,I(t_{k})}{x_{1},\ldots ,x_{k}}}\right)(s)\,.$

   2. Für jeden ${}S$-Ausdruck ${}\alpha$ gilt

      $I\vDash \alpha {\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}{\text{ genau dann, wenn }}{\left(I{\frac {I(t_{1}),\ldots ,I(t_{k})}{x_{1},\ldots ,x_{k}}}\right)}\vDash \alpha .$

3. Es sei ${}M$ eine Menge mit einem fixierten Element ${}s\in M$ und einer Abbildung ${}F\colon M\rightarrow M$. Dann gibt es genau eine Abbildung

   $\varphi \colon N\longrightarrow M,\,n\longmapsto \varphi (n),$

   die die beiden Eigenschaften

   $\varphi (0)=s{\text{ und }}\varphi (n^{\prime })=F(\varphi (n)){\text{ für alle }}n\in \mathbb {N}$

   erfüllt.

Aufgabe (4 Punkte)

Hanny, Nanny, Fanny und Sanny leben auf dem Ponyhof. Heute machen sie einen Ausflug mit den Ponies Pona, Pone, Pono und Ponu. Jedes der Mädchen sitzt dabei genau auf einem Pony, und sie reiten hintereinander. Folgende Fakten sind bekannt.

1. Fanny sitzt nicht auf Pona.
2. Pone und Ponu vertragen sich nicht so gut und laufen daher nicht direkt hintereinander.
3. Nanny sitzt auf Pone oder auf Pono.
4. Sanny reitet auf Pona oder auf Pone.
5. Nanny reitet direkt hinter Sanny.
6. Auf Ponu sitzt nicht Sanny.
7. Pona läuft direkt zwischen Pone und Pono.
8. Auf Pono sitzt weder Fanny noch Hanny.
9. Sanny reitet weiter vorne als Hanny.

Wer sitzt auf welchem Pony und in welcher Reihenfolge laufen sie?

Lösung

Nach (7) liegt der Ponyabschnitt Pone-Pona-Pono oder Pono-Pona-Pone vor. Nach (2) sind somit nur die Ponyreihenfolgen Pone-Pona-Pono-Ponu oder Ponu-Pono-Pona-Pone möglich. Nach (8) sitzt auf Pono Nanny oder Sanny, nach (4) sitzt aber Sanny auf Pona oder Pone. Deshalb sitzt Nanny auf Pono. Nach (5) reitet Nanny direkt hinter Sanny. Bei der Reihenfolge Ponu-Pono-Pona-Pone müsste also Sanny auf Ponu reiten, was nach (4) ausgeschlossen ist. Also ist die Reihenfolge Pone-Pona-Pono-Ponu und Sanny reitet auf Pona. Nach (9) reitet Hanny auf Ponu und folglich reitet Fanny auf Pone.

Reihenfolge	Pony	Reiterin
1	Pone	Fanny
2	Pona	Sanny
3	Pono	Nanny
4	Ponu	Hanny

Aufgabe (2 Punkte)

Man gebe signifikante Beispiele zum Stichwort „Fortsetzung einer Abbildung“ aus der Mathematik und aus der mathematischen Logik.

Lösung Abbildung/Fortsetzung/Mathematik und Logik/Aufgabe/Lösung

Aufgabe (4 (1+3) Punkte)

Wir betrachten Wörter über dem Alphabet ${}\{a,x\}$ und den Prozess ${}P$, der in einem solchen Wort jedes Vorkommen von ${}x$ durch das Wort ${}xax$ ersetzt.

1. Bestimme das Ergebnis von ${}axxax$ unter diesem Prozess.
2. Diesen Prozess kann man iterieren. Mit ${}P^{n}(w)$ bezeichnen wir das Ergebnis, wenn man den Prozess ${}n$-mal hintereinander auf das Startwort ${}w$ anwendet. Bestimme die Anzahl der Buchstaben in ${}P^{n}(w)$ zum Startwort ${}w=x$.

Lösung

1. Es ist

   ${}P(axxax)=axaxxaxaxax\,.$

2. Es sei

   ${}w_{n}=P^{n}(x)\,,$

   insbesondere ist ${}w_{0}=x$. Wir behaupten, dass in ${}w_{n}$ die Anzahl der ${}x$ gleich ${}2^{n}$ und die Anzahl der ${}a$ gleich ${}2^{n}-1$ und somit die Anzahl der Buchstaben gleich ${}2^{n+1}-1$ ist. Diese Aussagen beweisen wir durch Induktion über ${}n$. Für ${}n=0$ sind sie richtig. Es seien sie nun für ${}n$ bewiesen, wir wissen also, dass es in ${}w_{n}$ genau ${}2^{n}$ viele ${}x$ und ${}2^{n}-1$ viele ${}a$ gibt. Beim Ersetzungsprozess bleiben die ${}a$ stehen, und die ${}x$ werden durch ${}xax$ ersetzt. Daher ist die Anzahl der ${}x$ in ${}w_{n+1}$ gleich

   ${}2^{n}\cdot 2=2^{n+1}\,$

   und die Anzahl der ${}a$ in ${}w_{n+1}$ gleich

   ${}2^{n}-1+2^{n}=2^{n+1}-1\,.$

Aufgabe (3 Punkte)

Es sei ${}L^{V}$ die Sprache der Aussagenlogik zu einer Aussagenvariablenmenge ${}V$ und es sei ${}\lambda$ eine Wahrheitsbelegung der Variablen mit zugehöriger Interpretation ${}I$. Zeige, dass ${}I^{\vDash }$ maximal widerspruchsfrei ist.

Lösung

Sei ${}\Gamma =I^{\vDash }$. Da der Ableitungskalkül korrekt ist, ist ${}\Gamma$ abgeschlossen unter Ableitungen. Aufgrund der rekursiv definierten Wahrheitsbelegung gilt für jedes ${}\alpha \in L^{V}$ entweder ${}\alpha \in \Gamma$ oder ${}\neg \alpha \in \Gamma$. Somit ist ${}\Gamma$ widerspruchsfrei. Sobald man zu ${}\Gamma$ einen Ausdruck ${}\alpha$ hinzunimmt, hat man ${}\alpha ,\neg \alpha \in \Gamma$ und daraus kann man einen Widerspruch ableiten. Die Menge ist also maximal widerspruchsfrei.

Aufgabe (4 Punkte)

Es seien ${}A,B,C$ einstellige Relationssymbole. Erstelle eine Ableitung im Prädikatenkalkül für den Modus Disamis, also die Aussage

$(\exists x(Ax\wedge Bx)\wedge \forall x(Ax\rightarrow Cx))\rightarrow \exists x(Cx\wedge Bx).$

Lösung

Es gilt die aussagenlogische Ableitbarkeit

$\vdash (Ax\rightarrow Cx)\rightarrow (Ax\wedge Bx\rightarrow Cx\wedge Bx).$

Dies fassen wir als eine Aussage vom Typ

$\vdash p\rightarrow (q\rightarrow r)$

auf. Nach Aufgabe 11.7 (Einführung in die mathematische Logik (Osnabrück 2021)) gilt in dieser Situation auch

$\vdash \forall xp\rightarrow \forall x(q\rightarrow r).$

Nach Lemma 11.9 (Einführung in die mathematische Logik (Osnabrück 2021))  (3) ist

$\vdash \forall x(q\rightarrow r)\rightarrow {\left(\exists xq\rightarrow \exists xr\right)}.$

Dies zusammengenommen ergibt mit dem Kettenschluss

$\vdash \forall xp\rightarrow {\left(\exists xq\rightarrow \exists xr\right)},$

was im obigen Spezialfall die Ableitbarkeit

$\vdash \forall x(Ax\rightarrow Cx)\rightarrow (\exists x(Ax\wedge Bx)\rightarrow \exists x(Cx\wedge Bx))$

liefert. Eine aussagenlogische Umformulierung liefert

$\vdash (\exists x(Ax\wedge Bx)\wedge \forall x(Ax\rightarrow Cx))\rightarrow \exists x(Cx\wedge Bx).$

Aufgabe (3 Punkte)

In einem angeordneten Körper ist durch

${}\vert {x}\vert \geq \vert {y}\vert \,$

eine zweistellige Relation gegeben. Drücke diese Relation mit den üblichen Symbolen ${}0,-,\geq$, Variablen und aussagenlogischen Junktoren aus.

Lösung

Der Betrag von ${}x$ ist durch

${}\vert {x}\vert :={\begin{cases}x,{\text{ falls }}x\geq 0\\-x{\text{ sonst}}\,,\end{cases}}\,$

definiert. Daher können wir die Bedingung

${}\vert {x}\vert \geq \vert {y}\vert \,$

entlang der vier möglichen Fälle auflösen. Die Bedingung ist somit äquivalent zu

${\left(x\geq 0\wedge y\geq 0\wedge x\geq y\right)}\vee {\left(x\geq 0\wedge 0\geq y\wedge x\geq -y\right)}\vee {\left(0\geq x\wedge y\geq 0\wedge -x\geq y\right)}\vee {\left(0\geq x\wedge 0\geq y\wedge -x\geq -y\right)}.$

Aufgabe (8 Punkte)

Beweise den Satz von Henkin.

Lösung

Es sei ${}M$ das konstruierte Modell zu ${}\Gamma$ und ${}I$ die zugehörige Interpretation mit der natürlichen Belegung für die Variablen. Wir zeigen die Äquivalenz

$\alpha \in \Gamma {\text{ genau dann, wenn }}I\vDash \alpha$

für alle Ausdrücke ${}\alpha$, durch Induktion über den Rang der Ausdrücke. Zum Induktionsanfang sei der Rang von ${}\alpha$ gleich ${}0$, also ${}\alpha$ atomar. D.h. ${}\alpha$ ist entweder von der Form ${}s=t$ oder ${}Rt_{1}\ldots t_{n}$. Im ersten Fall ist ${}s=t\in \Gamma$ äquivalent zu ${}s\sim t$ bzw. ${}[s]=[t]$ in ${}M$. Dies ist nach Lemma 14.9 (Einführung in die mathematische Logik (Osnabrück 2021)) äquivalent zu ${}I(s)=I(t)$ und das bedeutet ${}I\vDash s=t$.

Im zweiten Fall ist ${}Rt_{1}\ldots t_{n}\in \Gamma$ - nach Konstruktion von ${}M$ und ${}R^{M}$ - äquivalent zu ${}R^{M}([t_{1}],\ldots ,[t_{n}])$, und dies ist äquivalent zu ${}I\vDash Rt_{1}\ldots t_{n}$.

Es sei nun die Aussage für alle Ausdrücke vom Rang ${}\leq r$ bewiesen und sei ${}\alpha$ ein Ausdruck vom Rang ${}r+1$. Wir betrachten die mögliche Struktur von ${}\alpha$ gemäß Definition .. Bei

${}\alpha =\neg \beta \,$

ergibt sich die Äquivalenz aus der Induktionsvoraussetzung (${}\beta$ hat kleineren Rang als ${}\alpha$) und Lemma 14.6 (Einführung in die mathematische Logik (Osnabrück 2021))  (1). Bei

${}\alpha =\beta _{1}\wedge \beta _{2}\,$

besitzen die beiden Bestandteile kleineren Rang als ${}\alpha$. Die Zugehörigkeit ${}\alpha \in \Gamma$ ist nach Lemma 14.6 (Einführung in die mathematische Logik (Osnabrück 2021))  (3) äquivalent zur gemeinsamen Zugehörigkeit ${}\beta _{1},\beta _{2}\in \Gamma$. Nach Induktionsvoraussetzung bedeutet dies ${}I\vDash \beta _{1}$ und ${}I\vDash \beta _{2}$. Dies bedeutet wiederum ${}I\vDash \beta _{1}\wedge \beta _{2}$ aufgrund der Modellbeziehung. Bei

${}\alpha =\exists x\beta \,$

besitzt wieder ${}\beta$ einen kleineren Rang. Die Zugehörigkeit ${}\alpha \in \Gamma$ ist aufgrund der Eigenschaft, Beispiele zu enthalten und aufgrund von Axiom 11.1 (Einführung in die mathematische Logik (Osnabrück 2021)) äquivalent zur Existenz eines Terms ${}t$ und der Zugehörigkeit ${}\beta {\frac {t}{x}}\in \Gamma$. Die Substitution von ${}\beta$ nach ${}\beta {\frac {t}{x}}$ verändert nach Aufgabe 14.17 (Einführung in die mathematische Logik (Osnabrück 2021)) nicht den Rang. Wir können also auf ${}\beta {\frac {t}{x}}$ die Induktionsvoraussetzung anwenden und erhalten die Äquivalenz zu ${}I\vDash \beta {\frac {t}{x}}$. Nach dem Substitutionslemma ist dies äquivalent zu ${}I{\frac {I(t)}{x}}\vDash \beta$ bzw. ${}I{\frac {[t]}{x}}\vDash \beta$ wegen Lemma 14.9 (Einführung in die mathematische Logik (Osnabrück 2021)). Dies ist äquivalent zu ${}I\vDash \exists x\beta$ aufgrund der Modellbeziehung und der Surjektivität der Termabbildung.

Aufgabe weiter

Es sei ${}S$ das Symbolalphabet, das neben Variablen aus dem einzigen zweistelligen Relationssymbol ${}G$ besteht. Wir betrachten die KO-Runden (also ab dem Achtelfinale) der Fußballweltmeisterschaften von 2014 und von 2018, ohne das Spiel um Platz ${}3$, als ${}S$-Modelle, wobei wir ${}G$ als die Gewinnrelation interpretieren, d.h. ${}xGy$ besagt, dass ${}x$ gegen ${}y$ (gespielt und) gewonnen hat.

1. Welche der folgenden Relationen sind für die WM 2014 wahr: Brasilien G Deutschland, Deutschland G Brasilien, Deutschland G Argentinien, Mexiko G Japan.
2. Ist ${}\forall yxGy$ eine Charakterisierung des Weltmeisters?
3. Charakterisiere durch einen ${}S$-Ausdruck in der einen freien Variablen ${}x$, dass eine Mannschaft mindestens das Halbfinale erreicht hat.
4. Charakterisiere durch einen ${}S$-Ausdruck in der einen freien Variablen ${}x$, dass eine Mannschaft das Halbfinale, aber nicht das Finale erreicht hat.
5. Betrachte Schweden bei der WM 2018. Man gebe einen ${}S$-Ausdruck in der einen freien Variablen ${}x$, der Schweden charakterisiert.
6. Welche(n) Mannschaft(en) der WM 2014 erfüllt (erfüllen) den ${}S$-Ausdruck, der Schweden bei der WM 2018 charakterisiert?
7. Definiere einen ${}S$- Isomorphismus zwischen der WM 2014 und der WM 2018.
8. Ist dies auch ein Isomorphismus, wenn man das Spiel um Platz ${}3$ mitberücksichtigt?

Lösung

1. Deutschland G Brasilien und Deutschland G Argentinien treffen zu, die beiden anderen nicht.
2. Nein, da der Weltmeister nicht gegen alle Mannschaften gewinnt, da er gar nicht gegen alle spielt.

3. $\exists y\exists z(y\neq z\wedge xGy\wedge xGz).$

4. $\exists y\exists z(y\neq z\wedge xGy\wedge xGz\wedge \forall w(xGw\rightarrow (w=y\vee w=z)).$

5. Schweden ist diejenige Mannschaft, die das Viertelfinale erreicht hat und gegen diejenige Mannschaft (England) ausgeschieden ist, die gegen diejenige Mannschaft (Kroatien) ausgeschieden ist, die im Finale unterlag. In einer Formel

   $\exists y\exists z\exists v\exists w(xGy\wedge zGx\wedge vGz\wedge wGv).$

6. Costa Rica.
7. Wir definieren induktiv, ausgehend vom Weltmeister, Finalist, Halbfinalisten, Viertelfinalisten einen Isomorphismus, wobei die Fortsetzung dadurch festgelegt wird, wer gegen wen in der Runde zuvor verloren hat. Dies liefert einen eindeutig bestimmten Isomorphismus. Es ergibt sich

   	${}Deutschland$	${}Frankreich$
   	${}Argentinien$	${}Kroatien$
   	${}Brasilien$	${}Belgien$
   	${}Niederlande$	${}England$
   	${}Frankreich$	${}Uruguay$
   	${}Belgien$	${}Russland$
   	${}Kolumbien$	${}Brasilien$
   	${}CostaRica$	${}Schweden$
   	${}Algerien$	${}Argentinien$
   	${}Schweiz$	${}{\text{Dänemark}}$
   	${}Chile$	${}Japan$
   	${}Mexiko$	${}Kolumbien$
   	${}Nigeria$	${}Portugal$
   	${}USA$	${}Spanien$
   	${}Uruguay$	${}Mexiko$
   	${}Griechenland$	${}Schweiz$

8. Im Jahr 2014 verlor der Halbfinalist, der gegen den Weltmeister verloren hat, das Spiel um Platz${}3$, 2018 gewann er es hingegen. Deshalb ist die Abbildung bei Berücksichtigung des Spiels um Platz ${}3$ kein Isomorphismus mehr.

Aufgabe (5 Punkte)

Schreibe einen Programmabschnitt ${}C(i,j,k)$ für eine Registermaschine, das zum Befehl ${}j$ wechselt, wenn im ${}i$-ten Register der Wert ${}k$ steht, und ansonsten weiterläuft. Man verwende nur die Grundbefehle.

Lösung

Wir arbeiten mit den ${}2k+1$ Programmzeilen (in relativer Nummerierung)

$1.\,\,\,\,\,\,\,\,\,\,\,\,C(i,2k+2)$

$2.\,\,\,\,\,\,\,\,\,\,\,\,i-$

$3.\,\,\,\,\,\,\,\,\,\,\,\,C(i,2k+2)$

$4.\,\,\,\,\,\,\,\,\,\,\,\,i-$

$\vdots$

$2k-3.\,\,\,\,\,\,\,\,\,\,\,\,C(i,2k+2)$

$2k-2.\,\,\,\,\,\,\,\,\,\,\,\,i-$

$2k-1.\,\,\,\,\,\,\,\,\,\,\,\,C(i,2k+2)$

$2k.\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,i-$

$2k+1.\,\,\,\,\,\,\,\,\,\,\,\,C(i,j)$

Das Programm reduziert also höchstens ${}k$-mal den Registerinhalt von ${}R_{i}$ um ${}1$. Wenn der Registerinhalt von ${}R_{i}$ am Anfang kleiner als ${}k$ ist, so wird dieser Registerinhalt in weniger als ${}k$ Schritten geleert und in diesem Fall landet man durch einen der bedingten Sprungbefehle ${}C(i,2k+2)$ unmittelbar hinter dem Programmabschnitt. Wenn der Registerinhalt von ${}R_{i}$ am Anfang gleich ${}k$ ist, so wird der Registerinhalt genau im Befehl ${}2k$ geleert und in diesem Fall wird man im letzten Befehl zum Befehl ${}j$ geleitet. Wenn der Registerinhalt von ${}R_{i}$ am Anfang größer als ${}k$ ist, so wird der Registerinhalt bis zum Befehl ${}2k$ nicht geleert und in diesem Fall wird man im letzten Befehl unmittelbar weitergeleitet. Das Programm leistet also das Gewünschte.

Aufgabe (3 Punkte)

Es seien ${}T_{1},T_{2}\subseteq L^{S}$ aufzählbar axiomatisierbare Theorien. Zeige, dass dann auch ${}(T_{1}\cup T_{2})^{\vdash }$ aufzählbar ist.

Lösung Aufzählbar axiomatisierbar/Vereinigung/Aufgabe/Lösung

Aufgabe (6 Punkte)

Es sei

${}T=\mathbb {N} 2\subseteq \mathbb {N} \,$

die Menge der geraden natürlichen Zahlen. Es sei ${}\Gamma$ die Ausdrucksmenge, die besagt, dass ${}+$ eine assoziative, kommutative Verknüpfung mit ${}0$ als neutralem Element ist. Es sei

${}\psi =\exists y(x=y+y)\,.$

Zeige, dass ${}T$ durch ${}\psi$ in ${}\Gamma$ schwach repräsentiert wird, aber nicht stark.

Lösung

Wir zeigen zuerst die schwache Repräsentierbarkeit, dass also für alle ${}n\in \mathbb {N}$ die Zugehörigkeit ${}n\in \mathbb {N} 2$ genau dann vorliegt, wenn die Ableitbarkeit ${}\Gamma \vdash \psi (n)$ gilt.

Wenn ${}n$ eine gerade natürliche Zahl ist, so ist

${}n=1+\cdots +1={\left(1+\cdots +1\right)}+{\left(1+\cdots +1\right)}={\frac {n}{2}}+{\frac {n}{2}}\,,$

wobei wir die ${}n$ Einsen in zwei gleichgroße Hälften aufgeteilt haben. Da in ${}\Gamma$ die Assoziativität und Kommutativität ableitbar ist (was auch der Grund dafür ist, dass wir in der Darstellung von ${}n$ als Summe von ${}1$ keine Klammerung festlegen müssen), ist auch

$\Gamma \vdash n={\frac {n}{2}}+{\frac {n}{2}},$

wobei ${}n$ und ${}{\frac {n}{2}}$ Abkürzungen für Einsersummen sind. Aufgrund der Existenzeinführung im Sukzedens ist

$\Gamma \vdash n={\frac {n}{2}}+{\frac {n}{2}}\rightarrow \exists y(n=y+y)$

und mit Modus ponens auch

$\Gamma \vdash \exists y(n=y+y),$

also

$\Gamma \vdash \psi (n).$

Wenn ${}n$ ungerade ist, so ist definitiv nicht

$\Gamma \vdash \psi (n),$

da wegen ${}\Gamma \subseteq {\rm {PA}}^{\vdash }$ dies auch in ${}\mathbb {N}$ gelten würde, was aber nicht der Fall ist.

Es liegt aber keine starke Repräsentierbarkeit vor. In diesem Fall würde nämlich für ${}n$ ungerade die Ableitbarkeit

$\Gamma \vdash \neg \psi (n)$

gelten. Dies würde dann in jedem Modell, das ${}\Gamma$ erfüllt, gelten. Da die Gültigkeit von ${}\Gamma$ nur bedeutet, dass ein kommutatives Monoid vorliegt, ist beispielsweise auch ${}(\mathbb {Q} ,0,+)$ ein Modell für ${}\Gamma$. Innerhalb der rationalen Zahlen besitzt aber jede Zahl eine Hälfte.

Aufgabe (2 Punkte)

Es sei ${}\Gamma$ eine arithmetische Ausdrucksmenge und ${}\alpha$ ein einstelliges Prädikat mit

$\Gamma \vdash \alpha (n)$

für alle ${}n\in \mathbb {N}$. Zeige, dass es einen Satz ${}q$ mit

$\Gamma \vdash \alpha (GN(q))\leftrightarrow q$

gibt.

Lösung

Es sei ${}q$ eine in der arithmetischen Sprache formulierbare prädikatenlogische Tautologie ohne freie Variable, beispielsweise ${}0=0$. Dann ist insbesondere ${}\Gamma \vdash q$ und nach Voraussetzung ist auch ${}\Gamma \vdash \alpha (GN(q))$. Also ist auch ${}\Gamma \vdash \alpha (GN(q))\leftrightarrow q$.

Aufgabe (4 Punkte)

Beweise das Unvollständigkeitslemma.

Lösung

Aus der Repräsentierbarkeit von ${}\Gamma ^{\vdash }$ folgt, dass es einen arithmetischen Ausdruck in einer freien Variablen gibt, sagen wir ${}a(x)$, mit der Eigenschaft, dass

$\Gamma \vdash s$

genau dann gilt, wenn

$\Gamma \vdash a(GN(s))$

gilt. Wir betrachten die Negation ${}\beta =\neg a$. Nach Satz 22.8 (Einführung in die mathematische Logik (Osnabrück 2021)) gibt es für ${}\beta$ einen Fixpunkt, also einen Satz ${}q$ mit

$\Gamma \vdash q\longleftrightarrow \beta (GN(q))$

bzw.

$\Gamma \vdash q\longleftrightarrow \neg a(GN(q)).$

Sowohl aus ${}\Gamma \vdash q$ als auch aus ${}\Gamma \vdash \neg q$ ergibt sich dann direkt ein ableitbarer Widerspruch, was der Widerspruchsfreiheit des Systems widerspricht.