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

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

Aufgabe (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Ein Primzahlzwilling.
2. Eine Wahrheitsbelegung für eine Menge an Aussagenvariablen.
3. Eine maximal widerspruchsfreie Teilmenge ${}\Gamma \subseteq L^{V}$ zu einer Menge ${}V$ an Aussagenvariablen.
4. Die Interpretation der Terme zu einem Symbolalphabet ${}S$ in einer gegebenen ${}S$- Interpretation auf einer Grundmenge ${}M$.
5. Ein allgemeingültiger prädikatenlogischer Ausdruck ${}\alpha \in L^{S}$.
6. Die Addition in einem Dedekind-Peano-Modell ${}\mathbb {N}$.

Lösung

1. Ein Primzahlzwilling ist ein Paar bestehend aus ${}p$ und ${}p+2$, wobei diese beiden Zahlen Primzahlen sind.
2. Unter einer Wahrheitsbelegung versteht man eine Abbildung

   $\lambda \colon V\longrightarrow \{0,1\}.$

3. Die Teilmenge ${}\Gamma \subseteq L^{V}$ heißt maximal widerspruchsfrei, wenn ${}\Gamma$ widerspruchsfrei ist und jede echt größere Menge ${}\Gamma \subset \Gamma '$ widersprüchlich ist.
4. 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.
5. Man nennt ${}\alpha$ allgemeingültig, wenn er in jeder ${}S$- Interpretation ${}I$ gilt.
6. Die Addition ${}n+k$ wird über die Addition ${}\alpha _{n}$ mit festem ${}n$ definiert, wobei ${}\alpha _{n}$ die eindeutig bestimmte Abbildung

   $\alpha _{n}\colon \mathbb {N} \longrightarrow \mathbb {N} ,\,k\longmapsto \alpha _{n}(k),$

   ist, für die

   $\alpha _{n}(0)=n{\text{ und }}\alpha _{n}(k')=(\alpha _{n}(k))'{\text{ für alle }}k\in \mathbb {N}$

   gilt.

Aufgabe (3 Punkte)

Formuliere die folgenden Sätze.

1. Das Lemma von Zorn.
2. Der Vollständigkeitssatz der Aussagenlogik.
3. Der Satz über die induktive Definition einer Abbildung auf einem Peano-Dedekind-Modell ${}(N,0,\prime )$.

Lösung

1. Es sei ${}(I,\preccurlyeq )$ eine geordnete Menge mit der Eigenschaft, dass jede total geordnete Teilmenge ${}J\subseteq I$ eine obere Schranke in ${}I$ besitzt. Dann gibt es in ${}I$ maximale Elemente.
2. Es sei ${}V$ eine Menge an Aussagenvariablen und ${}\Gamma \subseteq L^{V}$ eine Teilmenge der zugehörigen Sprache der Aussagenlogik. Es sei ${}\alpha \in L^{V}$. Dann ist

   $\Gamma \vdash \alpha {\text{ genau dann, wenn }}\Gamma \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 (1 Punkt)

Gehört das leere Wort ${}\emptyset$ zur Sprache der Aussagenlogik ${}L^{V}$ zu einer Aussagenvariablenmenge ${}V$?

Lösung

Das leere Wort gehört nicht zur Sprache der Aussagenlogik, da nur die Aussagenvariablen als Startglieder in der rekursiven Definition der Sprache auftreten und in den Rekursionsschritten die Ausdrücke stets verlängert werden.

Aufgabe (2 Punkte)

Zeichne einen Abstammungsbaum für die Aussage

$(((\neg (\neg (p)))\rightarrow (\neg (q)))\vee (\neg (r)))\leftrightarrow ((\neg (r))\wedge (q)).$

Lösung Aussage/Abstammungsbaum/3/Aufgabe/Lösung

Aufgabe (1 Punkt)

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

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

Lösung

${}\neg q$.

Aufgabe (3 Punkte)

Zeige, dass der aussagenlogische Ausdruck

${\left(r\rightarrow {\left(p\wedge \neg q\right)}\right)}\rightarrow {\left(\neg p\rightarrow {\left(\neg r\vee q\right)}\right)}$

allgemeingültig ist

Lösung

Wir müssen zeigen, dass für jede Wahrheitsbelegung ${}\lambda$ der Variablen ${}r,p,q$ der Wahrheitswert der Gesamtaussage gleich ${}1$ ist. Bei ${}\lambda (p)=1$ ist ${}\lambda (\neg p)=0$ und damit ist der Nachsatz und die Gesamtaussage wahr. Es sei also im Folgenden ${}\lambda (p)=0$. Dann ist ${}\lambda (p\wedge \neg q)=0$. Bei ${}\lambda (r)=1$ ist der Vordersatz falsch und somit die Gesamtaussage wahr. Es sei also ${}\lambda (r)=0$. Dann ist der Vordersatz wahr und wir müssen zeigen, dass auch der Nachsatz wahr ist. Es ist dann ${}\lambda (\neg r)=1$ und ${}\lambda (\neg r\vee q)=1$, also ist auch in diesem Fall der Nachsatz und die Gesamtaussage wahr.

Aufgabe (2 Punkte)

Es seien ${}p,q$ verschiedene Aussagenvariablen. Begründe die (Un)Richtigkeit der beiden folgenden Aussagen.

1. ${}\vdash p$ genau dann, wenn ${}\vdash q$.
2. ${}\vdash p\leftrightarrow q$.

Lösung

1. Da ${}\vdash p$ ebensowenig wie ${}\vdash q$ gilt, ist die Äquivalenz der beiden Ableitungen gegeben.
2. Der Ausdruck ${}p\leftrightarrow q$ ist nicht ableitbar, da er keine semantische Tautologie ist, wie man sieht, wenn man ${}p$ mit ${}1$ und ${}q$ mit ${}0$ belegt.

Aufgabe (6 Punkte)

Man gebe ein Beispiel für eine mathematische Existenzaussage, die mit dem Lemma von Zorn bewiesen wird, und führe den Beweis durch.

Lösung

Beispielsweise wird der Existenzsatz für maximale Ideale in einem kommutativen Ring ${}\neq 0$ mit dem Lemma von Zorn bewiesen. Der Beweis geht so:

Wir betrachten die Menge

${}M:={\left\{I\subseteq R\mid 1\not \in I,\,{\text{Ideal in }}R\right\}}\,.$

Diese Menge enthält das Nullideal ${}0$ und ist somit nicht leer. Wir wollen das Lemma von Zorn auf ${}M$ (mit der Inklusion als Ordnungsrelation) anwenden. Dazu sei ${}N\subseteq M$ eine total geordnete Teilmenge. Wir setzen

${}I:=\bigcup _{J\in N}J\,.$

Man zeigt nun, dass ${}I$ ein Ideal ist, das nicht die ${}1$ enthält. Also gehört es zu ${}M$ und es bildet eine obere Schranke für ${}N$. Das Lemma von Zorn liefert dann maximale Elemente in ${}M$, und dies sind maximale Ideale.

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

Der Planet Trigeno wird von einer einzigen Tierart bevölkert, den Trigos. Diese Tierart besitzt drei Geschlechter: Antilopen (A), Büffel (B) und Cnus (C). Bei der Paarung treffen zwei Individuen zusammen und erzeugen ein neues Individuum. Wenn das Paar gleichgeschlechtlich ist, so ist das Ergebnis wieder dieses Geschlecht, wenn das Paar gemischtgeschlechtlich ist, so ist das Ergebnis das dritte unbeteiligte Geschlecht. Alle Tiere gehören einer eindeutigen Generation an.

1. Die ${}n$-te Generation bestehe nur aus einem einzigen Geschlecht. Zeige, dass jede weitere Generation auch nur aus diesem Geschlecht besteht.
2. Die ${}n$-te Generation bestehe nur aus zwei Individuen unterschiedlichen Geschlechts. Zeige, dass diese Geschlechter mit ihrer Generation aussterben.
3. Es gelte nun die zusätzliche Bedingung, dass jedes Paar nur einen Nachkommen erzeugen darf. Zeige, dass die Tierart genau dann aussterben muss, wenn es in einer Generation nur zwei oder weniger Individuen gibt.
4. Es gelte nun die zusätzliche Bedingung, dass jedes Paar nur einen Nachkommen erzeugen darf, und in jeder Generation gebe es genau drei Individuen. Beschreibe die möglichen Generationsabfolgen. Welche Periodenlängen treten auf?

Lösung

1. Wenn die Generation nur aus dem Geschlecht ${}X$ besteht, so sind nur Paarungen innerhalb dieses Geschlechts möglich und das Ergebnis gehört stets diesem Geschlecht an. Mit Induktion folgt, dass dies über alle folgenden Generationen so bleibt.
2. Die Generation bestehe aus einem Individuum des Geschlechts ${}X$ und aus einem Individuum des Geschlechts ${}Y\neq X$. Die Folgegeneration besteht dann ausschließlich aus dem dritten Geschlecht ${}Z$ und nach Teil (1) überträgt sich das auf alle folgenden Generationen.
3. Wenn es nur ein oder kein Individuum gibt, so ist keine Paarung möglich und die nächste Generation ist leer. Wenn es zwei Individuen gibt, so ist nur eine Paarung möglich und es gibt nur einen Nachkommen, der sich allein nicht fortpflanzen kann. Wenn es dagegen mindestens drei Individuen, egal welchen Geschlechts, gibt, so sind auch mindestens drei Paarungen möglich und die nächste Generation besitzt mindestens wieder drei Individuen.
4. Wenn drei gleichgeschlechtliche Individuen in einer Generation leben, so erzeugen die drei möglichen Paare stets wieder ebendieses Geschlecht. Die Möglichkeiten sind ${}A,A,A$ oder ${}B,B,B$ oder ${}C,C,C$ und die Periodenlänge ist ${}1$. Wenn drei unterschiedliche Geschlechter vertreten sind, so ist jedes Geschlecht durch genau ein Individuum vertreten, es liegt also ${}A,B,C$ vor. Die drei Paarungen führen dann wieder zu ${}A,B,C$ und die Periodenlänge ist ebenfalls ${}1$. Wenn ein Geschlecht durch zwei Individuen vertreten ist und ein zweites Geschlecht durch ein Individuum, sagen wir ${}X,X,Y$, so wird daraus ${}X,Z,Z$ und daraus ${}Y,Y,Z$ und daraus ${}X,X,Y$. Die Periodenlänge ist also ${}3$. Von diesem Typ gibt es zwei Generationsabfolgen, nämlich die mit ${}A,A,B$ (mit $A,C,C$ und $B,B,C$) und die mit ${}A,B,B$ (mit $B,C,C$ und $A,A,C$).

Aufgabe (2 Punkte)

Es seien ${}x,y,z,w$ Variablen und ${}V$ ein zweistelliges Funktionssymbol. Welche der folgenden Wörter sind Terme?

1. ${}VxyzVVw$,
2. ${}VVxyVzw$,
3. ${}VVxyzVw$,
4. ${}VxVyVzw$,
5. ${}xVyVzVw$,
6. ${}VVVxyzw$,
7. ${}VxyVVzw$,
8. ${}VVxVyzw$,
9. ${}VxyVzw$,
10. ${}VxVyzVw$,
11. ${}VxVVyzw$,
12. ${}VxyVzVw$.

Lösung

Terme sind ${}2,4,6,8,11$, die anderen sind keine Terme.

Aufgabe (1 Punkt)

Wir betrachten den Satz „Lucy Sonnenschein tanzt auf allen Hochzeiten“. Negiere diesen Satz durch eine Existenzaussage.

Lösung

Es gibt eine Hochzeit, auf der Lucy Sonnenschein nicht tanzt.

Aufgabe (4 Punkte)

Es sei das arithmetische Alphabet ${}\{0,1,+,\cdot \}$ zusammen mit der Variablenmenge ${}\{x,y\}$ gegeben. Interpretiere den Term

$((0+1)+x)\cdot (1+(y+1))$

unter den folgenden Interpretationen, wobei ${}M$ die Grundmenge der Interpretation bezeichne.

1. ${}M=\mathbb {N}$ mit der Standardinterpretation und der Variablenbelegung ${}I(x)=5$ und ${}I(y)=3$.
2. ${}M=\operatorname {Mat} _{2}(\mathbb {R} )$ mit der Standardinterpretation

   $I(0)={\begin{pmatrix}0&0\\0&0\end{pmatrix}},\,I(1)={\begin{pmatrix}1&0\\0&1\end{pmatrix}}$

   und der üblichen Matrizenaddition und Matrizenmultiplikation und der Variablenbelegung ${}I(x)={\begin{pmatrix}1&2\\3&4\end{pmatrix}}$ und ${}I(y)={\begin{pmatrix}3&-2\\0&5\end{pmatrix}}$.

3. ${}M=\mathbb {Z}$, mit

   $I(0)=5,\,I(1)=-1,\,I(x)=0,\,I(y)=0,$

   und wo sowohl ${}+$ als auch ${}\cdot$ als Subtraktion interpretiert werden.

4. ${}M=$ Potenzmenge von ${}\{1,2,3,4,5\}$ mit

   $I(0)=\emptyset ,\,I(1)=\{1,2,3,4,5\},\,I(x)=\emptyset ,\,I(y)=\{2,4\},$

   und wo ${}+$ als ${}\cup$ und ${}\cdot$ als ${}\cap$ interpretiert wird.

Lösung

1. Es ist

   ${}{\left({\left(0+1\right)}+5\right)}\cdot {\left(1+{\left(3+1\right)}\right)}=6\cdot 5=30\,.$

2. Es ist

   ${}{\begin{aligned}{\left({\begin{pmatrix}0&0\\0&0\end{pmatrix}}+{\left({\begin{pmatrix}1&0\\0&1\end{pmatrix}}+{\begin{pmatrix}1&2\\3&4\end{pmatrix}}\right)}\right)}\cdot {\left({\begin{pmatrix}1&0\\0&1\end{pmatrix}}+{\left({\begin{pmatrix}3&-2\\0&5\end{pmatrix}}+{\begin{pmatrix}1&0\\0&1\end{pmatrix}}\right)}\right)}&={\begin{pmatrix}2&2\\3&5\end{pmatrix}}\cdot {\begin{pmatrix}5&-2\\0&7\end{pmatrix}}\\&={\begin{pmatrix}10&10\\15&29\end{pmatrix}}.\end{aligned}}$

3. Es ist

   ${}{\left({\left(5-{\left(-1\right)}\right)}-0\right)}-{\left({\left(-1\right)}-{\left(0-{\left(-1\right)}\right)}\right)}=6-{\left(-2\right)}=8\,.$

4. Es ist

   ${}{\begin{aligned}{\left({\left(\emptyset \cup \{1,2,3,4,5\}\right)}\cup \emptyset \right)}\cap {\left(\{1,2,3,4,5\}\cup {\left(\{2,4\}\cup \{1,2,3,4,5\}\right)}\right)}&=\{1,2,3,4,5\}\cap \{1,2,3,4,5\}\\&=\{1,2,3,4,5\}.\end{aligned}}$

Aufgabe (7 (3+4) Punkte)

Es sei ${}V=\{x,y,z,u,v,w\}$ eine Variablenmenge, ${}0$ eine Konstante und ${}-,+,\cdot$ zweistellige Funktionssymbole, die wir zentral unter der Zuhilfenahme von Klammern schreiben. Wir betrachten den prädikatenlogischen Ausdruck ${}\alpha$, der durch

$\forall x\forall y\forall z\forall u\forall v\forall w{\left(\left[(z-x)(z-y)+(w-u)(w-v)=0\right]\longrightarrow \left[(x-y)(x-y)+(u-v)(u-v)=(x-z)(x-z)+(u-w)(u-w)+(y-z)(y-z)+(v-w)(v-w)\right]\right)}$

gegeben ist.

1. Zeige, dass ${}\alpha$ bei Interpretation in einem Körper ${}K$ wahr wird, wenn man ${}0$ als ${}0$ und ${}\{-,+,\cdot \}$ als Subtraktion, Addition und Multiplikation interpretiert.
2. Welcher wichtige mathematische Satz verbirgt sich dahinter?

Lösung

1. Es sei ein Körper ${}K$ mit Elementen ${}x,y,z,u,v,w$ gegeben und sei vorausgesetzt, dass

   ${}(z-x)(z-y)+(w-u)(w-v)=0\,$

   ist. Unter Verwendung des Distributivgesetzes (bzw. der zweiten binomischen Formel) bedeutet dies

   ${}z^{2}-xz-yz+xy+w^{2}-uw-vw+uv=0\,.$

   Entsprechend ist

   ${}{\begin{aligned}(x-z)(x-z)+(u-w)(u-w)+(y-z)(y-z)+(v-w)(v-w)&=x^{2}+z^{2}-2xz+u^{2}+w^{2}-2uw+y^{2}+z^{2}-2yz+v^{2}+w^{2}-2vw\\&=x^{2}-2xz+u^{2}-2uw+y^{2}-2yz+v^{2}-2vw+2z^{2}+2w^{2}.\end{aligned}}$

   Wenn wir davon zweimal ${}0$ abziehen, und zwar in der oben etablierten Form, so ändert sich der Wert nicht und dies ist gleich

   ${}{\begin{aligned}x^{2}-2xz+u^{2}-2uw+y^{2}-2yz+v^{2}-2vw+2z^{2}+2w^{2}-2{\left(z^{2}-xz-yz+xy+w^{2}-uw-vw+uv\right)}&=x^{2}+u^{2}+y^{2}+v^{2}-2xy-2uv\\&=(x-y)(x-y)+(u-v)(u-v),\end{aligned}}$

   was insgesamt die Behauptung ist.

2. Es handelt sich bei ${}K=\mathbb {R}$ um den Satz des Pythagoras. Die sechs Variablen definieren drei Punkte in der Ebene ${}\mathbb {R} ^{2}$, sagen wir

   $P={\begin{pmatrix}x\\u\end{pmatrix}},\,Q={\begin{pmatrix}y\\v\end{pmatrix}},\,R={\begin{pmatrix}z\\w\end{pmatrix}}.$

   Die Verbindungsvektoren sind dann

   ${}R-P={\begin{pmatrix}z\\w\end{pmatrix}}-{\begin{pmatrix}x\\u\end{pmatrix}}={\begin{pmatrix}z-x\\w-u\end{pmatrix}}\,$

   und

   ${}R-Q={\begin{pmatrix}z\\w\end{pmatrix}}-{\begin{pmatrix}y\\v\end{pmatrix}}={\begin{pmatrix}z-y\\w-v\end{pmatrix}}\,.$

   Das Skalarprodukt dieser beiden Vektoren ist

   ${}\left\langle {\begin{pmatrix}z-x\\w-u\end{pmatrix}},{\begin{pmatrix}z-y\\w-v\end{pmatrix}}\right\rangle =(z-x)(z-y)+(w-u)(w-v)\,.$

   Dass dies gleich ${}0$ ist, bedeutet, dass diese beiden Vektoren aufeinander senkrecht stehen, dass also ${}P,Q,R$ ein rechtwinkliges Dreieck mit dem rechten Winkel an ${}R$ bilden. Das Quadrat der Länge der Strecke von ${}P$ nach ${}Q$ ist

   ${}{\begin{aligned}d(P,Q)^{2}&=\Vert {{\begin{pmatrix}x\\u\end{pmatrix}}-{\begin{pmatrix}y\\v\end{pmatrix}}}\Vert ^{2}\\&=\Vert {\begin{pmatrix}x-y\\u-v\end{pmatrix}}\Vert ^{2}\\&=(x-y)(x-y)+(u-v)(u-v)\end{aligned}}$

   und entsprechend ist

   ${}d(P,R)^{2}=(x-z)(x-z)+(u-w)(u-w)\,$

   und

   ${}d(Q,R)^{2}=(y-z)(y-z)+(v-w)(v-w)\,.$

   Der Nachsatz drückt also die Längenbeziehung im rechtwinkligen Dreieck aus.

Aufgabe (3 Punkte)

Formuliere die Injektivität für eine Abbildung

$f\colon D\longrightarrow Z$

prädikatenlogisch mit Hilfe der Verwendung von Sorten.

Lösung

Die Symbolmenge ${}S$ bestehe aus einem einstelligen Funktionssymbol ${}f$ und zwei einstelligen Relationssymbolen ${}D$ und ${}Z$. Wir betrachten den Ausdruck

$\forall x(Dx\rightarrow Zfx)\wedge \forall x\forall y{\left(Dx\wedge Dy\wedge \neg {\left(x=y\right)}\rightarrow \neg {\left(fx=fy\right)}\right)}.$

Bei einer Interpretation in einer Gesamtmenge ${}M$ besagt der linke Ausdruck, dass wenn ein Element ${}m$ zu ${}D^{M}$ gehört, dass dann der Funktionswert ${}f^{M}(m)$ zu ${}Z^{M}$ gehört. Das bedeutet also, dass eine Abbildung

$f^{M}\colon D^{M}\longrightarrow Z^{M}$

vorliegt. Der rechte Ausdruck besagt somit, dass für verschiedene Elemente aus ${}D^{M}$ die Bilder verschieden sind, was die Injektivität dieser Abbildung bedeutet.

Aufgabe (8 (3+5) Punkte)

Es sei ${}S$ ein Symbolalphabet erster Stufe und ${}U\subseteq S$ eine Teilmenge. Es sei ${}t$ ein ${}U$- Term und ${}\alpha$ ein ${}U$- Ausdruck. Es seien zwei ${}S$- Interpretationen ${}I_{1}$ und ${}I_{2}$ in einer gemeinsamen Grundmenge ${}M$ gegeben, die auf ${}U$ identisch seien. Beweise die folgenden Aussagen.

1. Es ist ${}I_{1}(t)=I_{2}(t)$.
2. Es ist ${}I_{1}\vDash \alpha$ genau dann, wenn ${}I_{2}\vDash \alpha$ (dazu genügt bereits, dass die Interpretationen auf den Symbolen aus ${}U$ und auf den in ${}\alpha$ frei vorkommenden Variablen identisch sind).

Lösung

(1). Wir führen Induktion über den Aufbau der ${}U$-Terme. Für den Induktionsanfang müssen wir Variablen und Konstanten aus ${}U$ betrachten. Für eine Variable ${}x$ (oder eine Konstante) aus ${}U$ ist nach Voraussetzung ${}I_{1}(x)=I_{2}(x)$. Im Induktionsschritt können wir annehmen, dass ein ${}n$-stelliges Funktionssymbol ${}f$ aus ${}U$ gegeben ist sowie ${}U$-Terme ${}t_{1},\ldots ,t_{n}$, für die die Interpretationsgleichheit schon gezeigt wurde. Nach Voraussetzung wird ${}f$ in beiden Interpretationen durch die gleiche Funktion ${}f^{M}$ interpretiert. Daher ist

${}{\begin{aligned}I_{1}(ft_{1}\ldots t_{n})&=f^{M}(I_{1}(t_{1}),\ldots ,I_{1}(t_{n}))\\&=f^{M}(I_{2}(t_{1}),\ldots ,I_{2}(t_{n}))\\&=I_{2}(ft_{1}\ldots t_{n}).\end{aligned}}$

(2). Wir führen Induktion über den Aufbau der ${}U$-Ausdrücke, wobei die zu beweisende Aussage über je zwei Interpretationen zu verstehen ist. Für die Gleichheit und ein Relationssymbol ${}R$ aus ${}U$ folgt die Aussage unmittelbar aus (1), da ja ${}R$ in beiden Interpretationen als die gleiche Relation zu interpretieren ist. Der Induktionsschritt ist für Ausdrücke der Form ${}\neg \alpha ,\,\alpha \wedge \beta ,\,\alpha \rightarrow \beta$ aufgrund der Modellbeziehung unmittelbar klar. Es sei nun ein ${}U$-Ausdruck der Form ${}\exists x\alpha$ gegeben, und es gelte ${}I_{1}\vDash \exists x\alpha$. Dies bedeutet aufgrund der Modellbeziehung, dass es ein ${}m\in M$ derart gibt, dass ${}I_{1}{\frac {m}{x}}\vDash \alpha$ gilt. Die beiden umbelegten Interpretationen ${}I_{1}{\frac {m}{x}}$ und ${}I_{2}{\frac {m}{x}}$ stimmen auf den Symbolen aus ${}U$ und den in ${}\alpha$ frei vorkommenden Variablen überein: Die Variable ${}x$ wird so oder so als ${}m$ interpretiert und die anderen freien Variablen aus ${}\alpha$ sind auch in ${}\exists x\alpha$ frei. Nach Induktionsvoraussetzung gilt ${}I_{2}{\frac {m}{x}}\vDash \alpha$ und daher wiederum ${}I_{2}\vDash \exists x\alpha$.

Aufgabe (3 Punkte)

Es sei ${}(\mathbb {N} ,0,^{\prime })$ ein Dedekind-Peano-Modell der natürlichen Zahlen. Zeige, dass die Addition die Abziehregel erfüllt, also die Aussage, dass aus einer Gleichung ${}n+k=m+k$ die Gleichheit ${}n=m$ folgt (dabei dürfen grundlegendere Regeln wie die Assoziativität der Addition und ähnliches verwendet werden).

Lösung

Wir führen Induktion über ${}k$ (für die Aussage für beliebige ${}n,m$). Für

${}k=0\,$

folgt die Aussage daraus, dass ${}0$ das neutrale Element der Addition ist. Die Aussage gelte nun für ein bestimmtes ${}k$. Wir müssen zeigen, dass sie auch für den Nachfolger ${}k'$ gilt. Es sei also

${}n+k'=m+k'\,.$

Aufgrund von Lemma 12.6 (Einführung in die mathematische Logik (Osnabrück 2021))  (2) bedeutet dies

${}n'+k=m'+k\,,$

woraus nach Induktionsvoraussetzung

${}n'=m'\,$

folgt. Aufgrund der Injektivität der Nachfolgerabbildung ergibt sich

${}n=m\,.$

Aufgabe (2 Punkte)

Formalisiere in der arithmetischen Sprache die (wahre) Aussage, dass es unendlich viele Primzahlen gibt.

Lösung

Wir arbeiten mit ${}\geq$ und setzen

$\operatorname {Prim} (y)=y\geq 2\wedge \forall t\forall s{\left(ts=y\rightarrow {\left(t=1\vee s=1\right)}\right)},$

was die Primeigenschaft von ${}y$ bedeutet. Eine Formalisierung für die Unendlichkeit der Primzahlen ist

$\forall x\exists y{\left(y\geq x+1\wedge \operatorname {Prim} (y)\right)},$

da dieser Ausdruck besagt, dass es oberhalb jeder Zahl eine Primzahl gibt.

Aufgabe (6 (3+3) Punkte)

Es sei ${}(M,0,N)$ ein Modell für die Peano-Axiome für den Nachfolger.

1. Zeige, dass ${}N$ fixpunktfrei ist, d.h. dass

   ${}N(x)\neq x\,$

   für alle ${}x\in M$.

2. Zeige, dass ${}N$ periodenfrei ist. D.h. für jedes ${}\ell \in \mathbb {N} _{+}$ ist

   ${}N^{\ell }(x)\neq x\,,$

   wobei

   ${}N^{\ell }=N\circ \cdots \circ N\,$

   die ${}\ell$-fache Hintereinanderschaltung von ${}N$ bedeutet.

Lösung

1. Wir zeigen die Aussage

   ${}Nx\neq x\,$

   durch Induktion über ${}x$. Bei

   ${}x=0\,$

   ergibt sich ${}N0\neq 0$ unmittelbar aus dem Axiom, dass ${}0$ kein Nachfolger ist. Es sei die Aussage für ${}x$ richtig, also

   ${}Nx\neq x\,.$

   Die Gleichheit

   ${}NNx=Nx\,$

   wäre in Verbindung mit der Induktionsvoraussetzung ein direkter Widerspruch zur Injektivität der Nachfolgerabbildung. Also ist

   ${}NNx\neq Nx\,$

   und die Aussage ist bewiesen.

2. Es sei nun ${}\ell$ und

   ${}N^{\ell }=N\circ \cdots \circ N\,$

   fixiert. Wir zeigen

   ${}N^{\ell }(x)\neq x\,$

   durch Induktion über ${}x$. Bei ${}x=0$ ergibt sich

   ${}N^{\ell }(0)\neq 0\,,$

   da sonst ${}0$ der Nachfolger von ${}N^{\ell -1}(0)$ wäre. Es sei die Aussage nun für ${}x$ richtig, also

   ${}N^{\ell }(x)\neq x\,.$

   Nehmen wir an, dass die Gleichheit

   ${}N^{\ell }Nx=Nx\,$

   gilt. Wegen

   ${}N^{\ell }(N(x))=N(N^{\ell }(x))\,$

   folgt aus der Injektivität der Nachfolgerabbildung direkt

   ${}N^{\ell }x=x\,$

   im Widerspruch zur Induktionsvoraussetzung. Also ist

   ${}N^{\ell }Nx\neq Nx\,$

   und die Aussage ist bewiesen.