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

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

Aufgabe * (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe. Bei 3.-7. bedeutet ${}S$ ein Symbolalphabet einer prädikatenlogischen Sprache erster Stufe.

1. Ein Primzahlzwilling.
2. Die Bestandteile einer Grundtermmenge.
3. Eine ${}S$-Struktur zu einem Symbolalphabet ${}S$ einer Sprache erster Stufe.
4. Ein allgemeingültiger prädikatenlogischer Ausdruck ${}\alpha \in L^{S}$.
5. Ein ${}S$-Homomorphismus

   $\varphi \colon M\longrightarrow N$

   zwischen zwei ${}S$- Strukturen ${}M$ und ${}N$.

6. Eine arithmetisch repräsentierbare Relation ${}R\subseteq \mathbb {N} ^{r}$.

Lösung

1. Ein Primzahlzwilling ist ein Paar bestehend aus ${}p$ und ${}p+2$, wobei diese beiden Zahlen Primzahlen sind.
2. Die Bestandteile einer Grundtermmenge besteht aus den folgenden (untereinander disjunkten) Mengen.
   1. eine Variablenmenge ${}V$,
   2. eine Konstantenmenge ${}K$,
   3. zu jedem ${}n\in \mathbb {N} _{+}$ eine Menge ${}F_{n}$ von Funktionssymbolen.
3. Unter einer ${}S$-Struktur versteht man eine nichtleere Menge ${}M$ mit den folgenden Festlegungen.
   1. Für jede Konstante ${}c\in K$ ist ein Element ${}c^{M}\in M$ festgelegt.
   2. Zu jedem ${}n$-stelligen Funktionssymbol ${}f$ (aus ${}S$) ist eine ${}n$-stellige Funktion

      $f^{M}\colon M^{n}\longrightarrow M$

      festgelegt.

   3. Zu jedem ${}n$-stelligen Relationssymbol ${}R$ (aus ${}S$) ist eine ${}n$-stellige Relation

      $R^{M}\subseteq M^{n}$

      festgelegt.

4. Man nennt ${}\alpha$ allgemeingültig, wenn er in jeder ${}S$- Interpretation ${}I$ gilt.
5. Die Abbildung

   $\varphi \colon M\longrightarrow N$

   heißt ${}S$-Homomorphismus, wenn folgende Eigenschaften gelten.

   1. Für jede Konstante ${}c\in S$ ist

      ${}\varphi (c^{M})=c^{N}\,.$

   2. Für jedes ${}n$-stellige Funktionssymbol ${}f\in S$ ist

      ${}\varphi (f^{M}(m_{1},\ldots ,m_{n}))=f^{N}(\varphi (m_{1}),\ldots ,\varphi (m_{n}))\,$

      für alle ${}m_{1},\ldots ,m_{n}\in M$.

   3. Für jedes ${}n$-stellige Relationsymbol ${}R\in S$ impliziert die Gültigkeit von

      $R^{M}(m_{1},\ldots ,m_{n})$

      die Gültigkeit von

      $R^{N}(\varphi (m_{1}),\ldots ,\varphi (m_{n})).$

6. Die Relation ${}R\subseteq \mathbb {N} ^{r}$ heißt arithmetisch repräsentierbar, wenn es einen ${}L^{\rm {Ar}}$-Ausdruck ${}\psi$ in ${}r$ freien Variablen derart gibt, dass für alle ${}r$-Tupel ${}(n_{1},\ldots ,n_{r})\in \mathbb {N} ^{r}$ die Äquivalenz ${}(n_{1},\ldots ,n_{r})\in R$ genau dann, wenn ${}\mathbb {N} \vDash \psi (n_{1},\ldots ,n_{r})$ gilt.

 

Aufgabe * (3 Punkte)

Formuliere die folgenden Sätze.

1. Der Isomorphiesatz für (zweitstufige) Dedekind-Peano-Modelle.
2. Der Vollständigkeitssatz der Prädikatenlogik.
3. Der erste Gödelsche Unvollständigkeitssatz.

Lösung

1. Es seien ${}N_{1}$ und ${}N_{2}$ Dedekind-Peano-Modelle für die natürlichen Zahlen. Dann gibt es eine eindeutig bestimmte bijektive Abbildung

   $\varphi \colon N_{1}\longrightarrow N_{2}$

   mit ${}\varphi (0_{1})=0_{2}$ und

   ${}\varphi (n')=(\varphi (n))'\,$

   für alle ${}n\in N_{1}$.
2. Es sei ${}S$ ein Symbolalphabet, ${}\Gamma$ eine Menge an ${}S$- Ausdrücken und ${}\alpha$ ein weiterer ${}S$-Ausdruck. Dann gilt ${}\Gamma \vDash \alpha$ genau dann, wenn ${}\Gamma \vdash \alpha$ gilt.
3. Es sei ${}\Gamma \subseteq L^{\rm {Ar}}$ eine arithmetische Ausdrucksmenge, die widerspruchsfrei und aufzählbar sei und Repräsentierungen erlaube. Dann ist ${}\Gamma ^{\vdash }$ unvollständig.

 

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 * (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 * (4 Punkte)

Es sei ${}V$ eine Menge an Aussagenvariablen und ${}\Gamma \subseteq L^{V}$ eine maximal widerspruchsfreie Teilmenge der zugehörigen Sprache der Aussagenlogik. Zeige, dass für jedes ${}\alpha \in L^{V}$ entweder ${}\alpha \in \Gamma$ oder ${}\neg \alpha \in \Gamma$ gilt.

Lösung

Wegen der Widerspruchsfreiheit können nicht sowohl ${}\alpha$ als auch ${}\neg \alpha$ zu ${}\Gamma$ gehören. Wenn weder ${}\alpha$ noch ${}\neg \alpha$ zu ${}\Gamma$ gehören, so ist entweder ${}\Gamma \cup \{\alpha \}$ oder ${}\Gamma \cup \{\neg \alpha \}$ widerspruchsfrei. Wären nämlich beide widersprüchlich, so würde für einen beliebigen Ausdruck ${}\beta$ sowohl

$\Gamma \cup \{\alpha \}\vdash \beta$

als auch

$\Gamma \cup \{\neg \alpha \}\vdash \beta$

gelten. Dies bedeutet nach Aufgabe 4.9 (Einführung in die mathematische Logik (Osnabrück 2021))

$\Gamma \vdash \alpha \rightarrow \beta$

und

$\Gamma \vdash \neg \alpha \rightarrow \beta ,$

woraus aufgrund der Fallunterscheidungsregel

$\Gamma \vdash \beta$

folgt. Dies bedeutet aber, dass ${}\Gamma$ widersprüchlich ist.

 

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 * (1 Punkt)

Erstelle einen prädikatenlogischen Ausdruck ${}\alpha$, der in einer Struktur genau dann gilt, wenn die Grundmenge der Struktur genau ${}4$ Elemente besitzt.

Lösung

$\exists x\exists y\exists z\exists u{\left(x\neq y\wedge x\neq z\wedge x\neq u\wedge y\neq z\wedge y\neq u\wedge z\neq u\wedge \forall v{\left(v=x\vee v=y\vee v=z\vee v=u\right)}\right)}.$

 

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 * (12 (1+1+4+2+4) Punkte)

Es sei ${}G$ ein dreistelliges Relationssymbol und ${}L$ die zugehörige prädikatenlogische Sprache. Es sei ${}I$ die Interpretation, bei der die Grundmenge die euklidische Ebene ist und ${}G$ durch die dreistellige Relation interpretiert wird, bei der ${}G(A,B,C)$ zutrifft, wenn die Punkte ${}A,B,C$ auf einer Geraden liegen.

1. Zeige ${}I\vDash Gxyz\leftrightarrow Gyxz$.
2. Zeige, dass im Allgemeinen nicht ${}I\vDash \forall x\forall y\forall z{\left(Gxyz\rightarrow Gxyu\right)}$ gelten muss.
3. Es sei ${}\Gamma =\{\forall x\forall y\forall z{\left(Gxyz\leftrightarrow Gyxz\right)},\,\forall x\forall y\forall z{\left(Gxyz\leftrightarrow Gxzy\right)}\}$. Erstelle eine Ableitung für ${}\Gamma \vdash Gxyz\leftrightarrow Gyzx$.
4. Zeige, dass der Ausdruck ${}Gxyz\wedge Gxyu$ bei der gegebenen Interpretation nicht bedeutet, dass die die freien Variablen ${}x,y,z,u$ belegenden Punkte auf einer Geraden liegen.
5. Formuliere einen Ausdruck aus ${}L$ in vier freien Variablen, der bei der gegebenen Interpretation besagt, dass die die freien Variablen belegenden Punkte auf einer Geraden liegen.

Lösung

1. Die Eigenschaft, ob drei Punkte auf einer Geraden liegen, hängt nicht von der Reihenfolge der Punkte ab.
2. Es seien ${}A,B$ verschiedene Punkte der Ebene, ${}C$ ein beliebiger Punkt auf der durch ${}A,B$ definierten Geraden und ${}D$ ein Punkt, der nicht auf dieser Geraden liegt. Dann ist der Vordersatz erfüllt, aber nicht der Nachsatz, und daher gilt die Implikation bei dieser Interpretation nicht.
3. Aufgrund der Alleinführung im Antezedens gilt für beliebige Variablen ${}u,v,w$ die Ableitbarkeit

   $\vdash \forall x\forall y\forall z{\left(Gxyz\leftrightarrow Gyxz\right)}\rightarrow {\left(Guvw\leftrightarrow Gvuw\right)}.$

   Daher gilt mit Modus ponens

   $\Gamma \vdash Guvw\leftrightarrow Gvuw$

   für beliebige Variablen. Insbesondere gilt

   $\Gamma \vdash Gxyz\leftrightarrow Gyxz.$

   Ebenso kann man auf

   $\Gamma \vdash Gyxz\leftrightarrow Gyzx$

   schließen. Die Transitivität der Äquivalenz liefert

   $\Gamma \vdash Gxyz\leftrightarrow Gyzx$

4. Wenn ${}x$ und ${}y$ durch den gleichen Punkt ${}A$ interpretiert werden und ${}z$ durch einen Punkt ${}C$ und ${}u$ durch einen Punkt ${}D$, derart, dass diese Punkte nicht auf einer Geraden liegen, so liegen dennoch ${}A,C$ und ${}A,D$ auf einer Geraden. Bei einer solchen Belegung sind ${}Gxyz$ und ${}Gxyu$ wahr, ohne dass alle Punkte auf einer Geraden liegen.
5. Man nimmt ${}\alpha =Gxyz\wedge Gxyu\wedge Gyzu$. Die Variablen seien durch die Punkte ${}A,B,C,D$ belegt. Wenn diese Punkte auf einer gemeinsamen Geraden liegen, so liegen insbesondere je drei von ihnen auf einer (nämlich dieser) Geraden und daher gilt ${}\alpha$ bei dieser Belegung. Zum Beweis der Umkehrung sei ${}I\vDash \alpha$. Dies bedeutet, dass sowohl ${}A,B,C$ als auch ${}A,B,D$ als auch ${}B,C,D$ jeweils auf einer Geraden liegen. Wenn unter den Punkten ${}A,B,C,D$ nur zwei verschiedene Punkte vorkommen, so liegen alle Punkte auf einer Geraden. Wir können uns also auf den Fall beschränken, wo maximal zwei Punkte identisch sind. Wenn ${}A\neq B$ ist, so definiert dies eine eindeutige Gerade, und auf dieser Geraden müssen wegen der Gültigkeit von ${}Gxyz$ bzw. ${}Gxyu$ sowohl ${}C$ als auch ${}D$ liegen. In diesem Fall liegen alle Punkte auf einer Geraden. Es sei nun ${}A=B$. Wegen ${}Gyzu$ liegen ${}B=A,C,D$ auf einer Geraden.

 

Aufgabe (3 Punkte)

Erläutere den Begriff Sortenprädikat an einem mathematischen Beispiel.

Lösung

Sortenprädikat/Mathematisches Beispiel/Erläutere/Aufgabe/Lösung

 

Aufgabe * (2 Punkte)

Man gebe ein Beispiel für einen kommutativen Halbring, der kein Peano-Halbring ist.

Lösung

Die ganzen Zahlen ${}\mathbb {Z}$ sind ein kommutativer Ring und insbesondere ein kommutativer Halbring. Sie bilden aber keinen Peano-Halbring, da das erste Axiom ${}\forall x(\neg (x+1=0))$, also dass die ${}0$ keinen Vorgänger hat, in ${}\mathbb {Z}$ nicht gilt.

 

Aufgabe (6 (3+3) Punkte)

1. Entwerfe ein Programm für eine Registermaschine, das die Potenz ${}r_{j}^{r_{k}}$ berechnet, wobei ${}r_{j}$ und ${}r_{k}$ die Inhalte im ${}j$-ten bzw. ${}k$-ten Register sind.
2. Entwerfe ein Programm für eine Registermaschine, das entscheidet, ob der Registerinhalt ${}r_{i}$ des Registers ${}R_{i}$ die echte Potenz einer natürlichen Zahl ist.

Lösung

Registermaschine/Potenzen und Potenztest/Programm/Aufgabe/Lösung

 

Aufgabe * (5 Punkte)

Es sei ${}T\subseteq \mathbb {N}$ eine Teilmenge von natürlichen Zahlen. Zeige, dass ${}T$ genau dann ${}R$- entscheidbar ist, wenn sowohl ${}T$ als auch das Komplement ${}\mathbb {N} \setminus T$ ${}R$- aufzählbar ist.

Lösung

Wenn ${}P$ ein Programm ist, das ${}T$ entscheidet, so kann man einfach ein ${}T$ aufzählendes Programm konstruieren. Man lässt der Reihe nach jede natürliche Zahl mittels ${}P$ auf ihre Zugehörigkeit zu ${}T$ überprüfen und druckt sie aus, falls sie dazu gehört (dazu muss man den Haltebefehl von ${}P$ zu einer Druckausgabe modifizieren). Entsprechend konstruiert man ein Aufzählungsprogramm für das Komplement.

Es seien nun ${}T$ als auch ${}\mathbb {N} \setminus T$ aufzählbar, und es seien ${}P$ und ${}Q$ Programme, die dies leisten. Dann liefert die folgende Kombination der beiden Programme ein Entscheidungsverfahren: Man schreibt die Programme ${}P$ und ${}Q$ hintereinander (wobei man natürlich die adressierten Register und Programmzeilen umnummerieren muss) und lässt sie abwechselnd bis zu einer Druckausgabe laufen. Sobald eine Druckausgabe eines Programmteils mit der zu überprüfenden Zahl ${}n$ übereinstimmt, weiß man, ob ${}n$ zu ${}T$ gehört oder nicht. Da ${}n$ entweder zu ${}T$ oder zum Komplement gehört, muss einer dieser Fälle eintreten.

 

Aufgabe * (6 Punkte)

Man gebe für die Abbildung

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

mit

${}F(n)={\begin{cases}{\sqrt {n}}\,,{\text{ falls }}{\sqrt {n}}\in \mathbb {N} \,,\\0{\text{ sonst}}\,,\end{cases}}\,$

einen Ausdruck an, der ${}F$ arithmetisch repräsentiert.

Lösung

Wir setzen

${}\alpha :={\left(x=y\cdot y\right)}\vee {\left(\forall z{\left(x\neq z\cdot z\right)}\wedge y=0\right)}\,$

und müssen zeigen, dass ${}F(n)=m$ genau dann gilt, wenn ${}\mathbb {N} \vDash \alpha {\frac {n}{x}}{\frac {m}{y}}$ gilt. Diese Äquivalenz beweisen wir durch eine doppelte Fallunterscheidung.

1.1. ${}n$ ist eine Quadratzahl und ${}m$ ist die Quadratwurzel aus ${}n$. Dann ist einerseits ${}F(n)=m$. Andererseits ist ${}\mathbb {N} \vDash {\left(x=y\cdot y\right)}{\frac {n}{x}}{\frac {m}{y}}$. Daher gilt auch ${}\alpha$ bei dieser Belegung.

1.2. ${}n$ ist eine Quadratzahl und ${}m$ ist nicht die Quadratwurzel aus ${}n$. Dann ist einerseits ${}F(n)\neq m$. Andererseits ist ${}\mathbb {N} \vDash {\left(\neg {\left(x=y\cdot y\right)}\right)}{\frac {n}{x}}{\frac {m}{y}}$. Da ${}n$ eine Quadratzahl ist, gilt die Aussage ${}\forall z{\left(x\neq z\cdot z\right)}{\frac {n}{x}}$ in ${}\mathbb {N}$ nicht. Daher gelten beide durch ${}\vee$ verbundenen Teilaussagen von ${}\alpha$ nicht und somit gilt ${}\alpha {\frac {n}{x}}{\frac {m}{y}}$ nicht.

2.1. ${}n$ ist keine Quadratzahl und ${}m$ ist ${}0$. Dann ist einerseits ${}F(n)=m$. Andererseits gelten die Aussagen ${}\forall z{\left(x\neq z\cdot z\right)}{\frac {n}{x}}$ und ${}{\left(y=0\right)}{\frac {0}{y}}$ und somit gilt ${}\alpha {\frac {n}{x}}{\frac {m}{y}}$ in ${}\mathbb {N}$.

2.2. ${}n$ ist keine Quadratzahl und ${}m$ ist nicht ${}0$. Dann ist einerseits ${}F(n)\neq m$. Andererseits gilt in ${}\mathbb {N}$ die Aussage ${}{\left(x=y\cdot y\right)}{\frac {n}{x}}{\frac {m}{y}}$ und die Aussage ${}{\left(y=0\right)}{\frac {m}{y}}$ nicht. Somit gilt auch ihre ${}\vee$-Verknüpfung nicht und daher ${}\mathbb {N} \not \vDash \alpha {\frac {n}{x}}{\frac {m}{y}}$.

 

Aufgabe * (7 Punkte)

Es sei ${}\Gamma \subseteq L^{\rm {Ar}}$ eine arithmetische Ausdrucksmenge ohne freie Variablen und ${}R\subseteq \mathbb {N}$ eine Relation. Es seien ${}\alpha ,\beta \in L^{\rm {Ar}}$ Ausdrücke in einer freien Variablen ${}x$. Zeige, dass aus

$\Gamma \vdash \alpha \leftrightarrow \beta$

folgt, dass ${}\alpha$ in ${}\Gamma$ die Relation ${}R$ genau dann repräsentiert, wenn ${}\beta$ in ${}\Gamma$ die Relation ${}R$ repräsentiert.

Lösung

Es sei ${}\Gamma \vdash \alpha \leftrightarrow \beta$ und es sei vorausgesetzt, dass ${}\alpha$ die Relation ${}R$ repräsentiert. Wir müssen zeigen, dass auch ${}\beta$ die Relation repräsentiert. Es sei zunächst ${}n\in R$. Dann ist

$\Gamma \vdash \alpha {\frac {n}{x}}$

wegen der Repräsentierbarkeit von ${}R$ durch ${}\alpha$. Nach Voraussetzung ist

$\Gamma \vdash \alpha \rightarrow \beta .$

Aus der Alleinführung im Sukzedens (die anwendbar ist, da in ${}\Gamma$ nur gebundene Variablen vorkommen) folgt

$\Gamma \vdash \forall x{\left(\alpha \rightarrow \beta \right)}.$

Das Einsetzungsaxiom sichert

$\vdash \forall x{\left(\alpha \rightarrow \beta \right)}\rightarrow {\left(\alpha \rightarrow \beta \right)}{\frac {n}{x}},$

was

$\vdash \forall x{\left(\alpha \rightarrow \beta \right)}\rightarrow {\left(\alpha {\frac {n}{x}}\rightarrow \beta {\frac {n}{x}}\right)}$

bedeutet. Also gilt

$\Gamma \vdash \alpha {\frac {n}{x}}\rightarrow \beta {\frac {n}{x}}$

und somit

$\Gamma \vdash \beta {\frac {n}{x}}.$

Bei ${}n\not \in R$ gilt

$\Gamma \vdash \neg \alpha {\frac {n}{x}}$

und

$\Gamma \vdash \neg \alpha \rightarrow \neg \beta .$

Mit dem gleichen Schluss wie oben ergibt sich

$\Gamma \vdash \neg \alpha {\frac {n}{x}}\rightarrow \neg \beta {\frac {n}{x}}$

und somit

$\Gamma \vdash \neg \beta {\frac {n}{x}}.$