Kurs:Einführung in die mathematische Logik (Osnabrück 2011-2012)/Vorlesung 6/kontrolle

Peano-Axiome

Giuseppe Peano (1858 -1932)

Wir besprechen nun, inwiefern man die natürlichen Zahlen ${}\mathbb {N}$ axiomatisieren kann, und was davon erststufig durchführbar ist. Dazu diskutieren wir die Peano-Axiome, wobei wir mit der zweitstufigen Version beginnen.

Axiom

Eine Menge ${}N$ mit einem ausgezeichneten Element ${}0\in N$ (die Null) und einer (Nachfolger)-Abbildung

$'\colon N\longrightarrow N,\,n\longmapsto n',$

heißt natürliche Zahlen (oder Dedekind-Peano-Modell für die natürlichen Zahlen), wenn die folgenden Dedekind-Peano-Axiome erfüllt sind.

1. Das Element ${}0$ ist kein Nachfolger (die Null liegt also nicht im Bild der Nachfolgerabbildung).
2. Jedes ${}n\in N$ ist Nachfolger höchstens eines Elementes (d.h. die Nachfolgerabbildung ist injektiv).
3. Für jede Teilmenge ${}T\subseteq N$ gilt: Wenn die beiden Eigenschaften
   • ${}0\in T$,
   • mit jedem Element
   ${}n\in T$ ist auch ${}n'\in T$,

gelten, so ist ${}T=N$.

Mit zweitstufig ist gemeint, dass nicht nur über die Elemente der Menge ${}\mathbb {N}$, die man axiomatisch charakterisieren will, quantifiziert wird, sondern auch über beliebige Teilmengen dieser Menge. Mit dieser Axiomatik lassen sich ausgehend von der Nachfolgerfunktion die Addition und die Multiplikation rekursiv einführen, und es lässt sich zeigen, dass je zwei Modelle für diese zweistufigen Peano-Axiome „isomorph“ sind, dass es also zwischen ihnen eine strukturerhaltende Bijektion gibt. Das im Wesentlichen eindeutig bestimmte Modell für diese Arithmetik bezeichnen wir mit ${}\mathbb {N}$.

Wir betrachten zwei erststufige Varianten. Dabei wird die Nachfolgerfunktion beibehalten und das Induktionsaxiom, das oben für beliebige Teilmengen formuliert war, wird durch ein Induktionsaxiom für die in der Sprache formulierbaren Ausdrücke ersetzt. Das Induktionsaxiom gilt somit lediglich für Teilmengen, die in der gegebenen Sprache charakterisierbar sind.

Axiom

Die Peano-Axiome für die Nachfolgerfunktion in der ersten Stufe werden (in der Sprache ${}L$ zur Symbolmenge mit einer Konstanten ${}0$ und einem einstelligen Funktionssymbol ${}N$) folgendermaßen definiert.

1. ${}\forall x(\neg (Nx=0))$.
2. ${}\forall x\forall y((Nx=Ny)\rightarrow (x=y))$.
3. Für jeden Ausdruck ${}\alpha$ von ${}L$ mit einer freien Variablen ${}x$ gilt

   $\alpha {\frac {0}{x}}\wedge \forall x{\left(\alpha \rightarrow \alpha {\frac {Nx}{x}}\right)}\rightarrow \forall x\alpha .$

Aus der obigen zweitstufigen Formulierung der Axiomatik, die nur die Nachfolgerabbildung verwendet, kann man in jedem Modell in eindeutiger Weise eine Addition und eine Multiplikation definieren. Dafür ist das obige erststufige Axiomensystem zu schwach. Stattdessen werden wir unter der Peano-Arithmetik das folgende Axiomensystem verstehen, das mit zwei Konstanten ${}0$ und ${}1$ und zwei zweistelligen Operationen ${}+$ und ${}\cdot$ auskommt. Die Nachfolgerfunktion ist dann durch ${}Nx=x+1$ definiert und es braucht dafür kein eigenes Funktionssymbol.

Axiom

Die Peano-Axiome für Addition und Multiplikation in der ersten Stufe werden (in der Sprache ${}L^{\rm {Ar}}$ zur Symbolmenge mit den beiden Konstanten ${}0$ und ${}1$ und zwei zweistelligen Funktionssymbolen ${}+$ und ${}\cdot$) folgendermaßen definiert.

1. ${}\forall x(\neg (x+1=0))$.
2. ${}\forall x\forall y((x+1=y+1)\rightarrow (x=y))$.
3. ${}\forall x(x+0=x)$.
4. ${}\forall x\forall y(x+(y+1)=(x+y)+1))$.
5. ${}\forall x(x\cdot 0=0)$.
6. ${}\forall x\forall y(x\cdot (y+1)=(x\cdot y)+x)$.
7. Für jeden Ausdruck ${}\alpha$ von ${}L^{Ar}$ mit einer freien Variablen ${}x$ gilt

   $\alpha {\frac {0}{x}}\wedge \forall x{\left(\alpha \rightarrow \alpha {\frac {x+1}{x}}\right)}\rightarrow \forall x\alpha .$

Die Axiome ${}(1),(2)$ und ${}(7)$ entsprechen dabei direkt den Nachfolgeraxiomen von oben. Die Axiome ${}(3)$ und ${}(4)$ spiegeln die Grundregeln in der zweistufigen Peano-Arithmetik für die rekursive Definition der Addition wider, und die Axiome ${}(5)$ und ${}(6)$ entsprechen den Grundregeln für die rekursive Definition der Multiplikation. Bekanntlich gelten diese Axiome für die natürlichen Zahlen. Anders als bei der obigen zweitstufigen Axiomatik gibt es aber von ${}\mathbb {N}$ verschiedene Modelle (nicht Standard-Arithmetiken), die die erststufige Peano-Arithmetik erfüllen. Dies ist aber kein „zufälliges“ Defizit der gewählten Axiomatik, sondern dahinter verbirgt sich eine grundsätzliche Schwäche der Sprache erster Stufe, die durch die Gödelschen Unvollständigkeitssätze präzisiert werden wird.

Kalkül der Prädikatenlogik

Gegeben sei ein Symbolalphabet einer Sprache erster Stufe und damit die zugehörige Termmenge und die zugehörige Ausdrucksmenge. Wir möchten die logisch wahren Aussagen einer solchen Sprache syntaktisch charakterisieren. Mathematische Aussagen sind im Allgemeinen „wenn-dann“-Aussagen, d.h. sie behaupten, dass, wenn gewisse Voraussetzungen erfüllt sind, dann auch eine gewisse Folgerung erfüllt ist.

Wenn man einen Beweis eines Satzes der Gruppentheorie oder der elementaren Arithmetik entwirft, so sind dabei die Axiome der Gruppentheorie bzw. die Peano-Axiome stets präsent. Wenn ${}p_{1},p_{2},p_{3}$ die Gruppenaxiome bezeichnen und ${}p$ die Aussage, dass das neutrale Element eindeutig bestimmt ist, bezeichnet, so folgt ${}p$ aus ${}p_{1},p_{2},p_{3}$. Mit der Folgerungsbeziehung kann man dies als

$\{p_{1},p_{2},p_{3}\}\vDash p$

formulieren. Dies kann man auch so ausdrücken, dass

$p_{1}\wedge p_{2}\wedge p_{3}\rightarrow p$

allgemeingültig ist, also dass

$\vDash p_{1}\wedge p_{2}\wedge p_{3}\rightarrow p$

gilt. So kann man jede Folgerung ${}\Gamma \vDash p$ aus einer endlichen Ausdrucksmenge ${}\Gamma$ „internalisieren“, also durch einen allgemeingültigen Ausdruck der Form

$\vDash p_{1}\wedge \ldots \wedge p_{n}\rightarrow p$

wiedergegeben, wobei vorne die Ausdrücke aus ${}\Gamma$ konjugiert werden. Die Folgerungsbeziehung (zumindest aus endlichen Ausdrucksmengen) kann also vollständig durch allgemeingültige Ausdrücke verstanden werden.

Wir besprechen nun die syntaktische Variante der allgemeingültigen Ausdrücke, nämlich die syntaktischen prädikatenlogischen Tautologien. Über den soeben besprochenen Zusammenhang ergibt sich daraus auch ein Ableitungskalkül, der das syntaktische Analogon zur Folgerungsbeziehung ist. Da wir Ausdrücke der Form ${}p_{1}\wedge \ldots \wedge p_{n}\rightarrow p$ als Grundtyp für eine mathematische Aussage ansehen, arbeiten wir allein mit den Junktoren ${}\neg ,\wedge ,\rightarrow$ und lesen ${}\vee$ und ${}\leftrightarrow$ als Abkürzungen. Man könnte auch noch ${}\wedge$ bzw. ${}\rightarrow$ eliminieren und durch die verbleibenden beiden Junktoren ausdrücken, doch würde dies zu recht unleserlichen Formulierungen führen.

Der prädikatenlogische Kalkül, den wir vorstellen wollen, soll es erlauben, „alle“ prädikatenlogischen allgemeingültigen Ausdrücke formal abzuleiten. Der Aufbau dieses Kalküls geschieht wiederum rekursiv (und für beliebige Symbolalphabete gleichzeitig). D.h. man hat eine Reihe von Anfangstautologien (oder Grundtautologien) und gewisse Schlussregeln, um aus schon nachgewiesenen Tautologien neue zu produzieren. Sowohl die Anfangstautologien als auch die Schlussregeln sind aus der mathematischen Beweispraxis vertraut.

Zur Formulierung dieses Kalküls verwenden wir die Schreibweise

$\vdash p.$

Sie bedeutet, dass der Ausdruck ${}p$ in der Prädikatenlogik (erster Stufe zu einem gegebenen Alphabet) ableitbar ist, also eine Tautologie (im syntaktischen Sinne) ist.

Aussagenlogische Tautologien

In den folgenden aussagenlogischen Tautologien sind ${}p$ und ${}q$ beliebige Ausdrücke. Um Klammern zu sparen verwenden wir die Konvention, dass die Negation sich auf das folgende Zeichen bezieht und dass die Konjunktion stärker bindet als die Implikation.

Axiom

Für eine Aussagenvariablenmenge ${}V$ und beliebige Ausdrücke ${}\alpha ,\beta ,\gamma$ legt man folgende (syntaktische) Tautologien axiomatisch fest.

1. $\vdash \alpha \rightarrow (\beta \rightarrow \alpha ).$

2. $\vdash (\alpha \rightarrow \beta )\wedge (\beta \rightarrow \gamma )\rightarrow (\alpha \rightarrow \gamma ).$

3. $\vdash (\alpha \rightarrow \beta )\wedge (\alpha \rightarrow \gamma )\rightarrow (\alpha \rightarrow \beta \wedge \gamma ).$

4. $\vdash (\alpha \wedge \beta \rightarrow \gamma )\rightarrow (\alpha \rightarrow (\beta \rightarrow \gamma ))$

   und

   $\vdash (\alpha \rightarrow (\beta \rightarrow \gamma ))\rightarrow (\alpha \wedge \beta \rightarrow \gamma ).$

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

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

Diese Tautologien sind also die Startglieder. Dabei stehen ${}p,q,r$ für beliebige Ausdrücke der Prädikatenlogik erster Stufe (in der Aussagenlogik werden diese Tautologien einfach mit Aussagenvariablen formuliert). Das Axiom (3) besagt die Transitivität der Implikation, Axiom (5) heißt Widerspruchsaxiom und Axiom (6) heißt Fallunterscheidungsaxiom.

Um überhaupt aus diesen Axiomen weitere Tautologien generieren zu können, braucht man Ableitungsregeln. Davon gibt es lediglich eine.

Modus ponens

Aus ${}\vdash p$ und ${}\vdash p\rightarrow q$ folgt ${}\vdash q$.

Wir wollen uns nicht lange an aussagenlogischen Tautologien aufhalten. Eine Durchsicht der angeführten Tautologien zeigt, dass es sich auch um semantische Tautologien, also allgemeingültige Ausdrücke, handelt.

Bemerkung   Referenznummer erstellen

Die aussagenlogischen Axiome der Form ${}\vdash \alpha \rightarrow \beta$ führen zu entsprechenden Schlussregeln, d.h. Vorschriften, wie man aus (schon etablierten) syntaktischen Tautologien neue Tautologien erhält. Wir gehen unter diesem Gesichtspunkt die Axiome durch.

Aus ${}\vdash \alpha$ folgt ${}\vdash \beta \rightarrow \alpha$.

Dies ergibt sich aus der Voraussetzung ${}\vdash \alpha$ aus ${}\vdash \alpha \rightarrow (\beta \rightarrow \alpha )$ und dem Modus ponens.

Aus ${}\vdash \alpha \wedge \beta$ folgt ${}\vdash \alpha$ (und ebenso $\vdash \beta$).

Dies ergibt sich aus ${}\vdash \alpha \wedge \beta \rightarrow \alpha$ nach Fakt ***** und der Voraussetzung ${}\vdash \alpha \wedge \beta$ mittels Modus ponens. Umgekehrt gilt die sogenannte Konjunktionsregel, d.h. aus ${}\vdash \alpha$ und ${}\vdash \beta$ folgt auch ${}\vdash \alpha \wedge \beta$. Dies ergibt sich aus

$\vdash \alpha \rightarrow (\beta \rightarrow \alpha \wedge \beta )$

(was aus den Axiomen folgt, siehe Aufgabe 6.5) aus den Voraussetzungen durch eine zweifache Anwendung des Modus ponens.

Aus ${}\vdash \alpha \rightarrow \beta$ und ${}\vdash \beta \rightarrow \gamma$ ergibt sich ${}\vdash \alpha \rightarrow \gamma$. Diese Regel heißt Kettenschlussregel. Nach der obigen abgeleiteten Konjunktionsregel folgt aus den Voraussetzungen direkt ${}\vdash (\alpha \rightarrow \beta )\wedge (\beta \rightarrow \gamma )$ und daraus und dem Kettenschlussaxiom mit dem Modus ponens ${}\vdash \alpha \rightarrow \gamma$.

Lemma Referenznummer erstellen

Es ist

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

Beweis

Nach Axiom 6.4  (3) ist

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

Die beiden Bestandteile des Vordersatzes gelten nach Fakt *****, sodass auch ihre Konjunktion ableitbar ist. Daher ist auch der Nachsatz ableitbar.

$\Box$

Lemma Lemma 6.7 ändern

1. $\vdash (\alpha \rightarrow \beta )\rightarrow (\alpha \wedge \gamma \rightarrow \beta ).$

2. $\vdash (\alpha \rightarrow \beta )\wedge (\gamma \rightarrow \delta )\rightarrow (\alpha \wedge \gamma \rightarrow \beta \wedge \delta ).$

Beweis

1. Nach Axiom 6.4  (2) ist

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

   und daher mit Axiom 6.4  (4) auch

   $\vdash (\alpha \wedge \gamma \rightarrow \alpha )\rightarrow ((\alpha \rightarrow \beta )\rightarrow (\alpha \wedge \gamma \rightarrow \beta )).$

   Der Vordersatz ist nach Fakt ***** ableitbar, also auch der Nachsatz.
   

2. Nach Teil (1) ist

   $\vdash (\alpha \rightarrow \beta )\rightarrow (\alpha \wedge \gamma \rightarrow \beta )$

   und (unter Verwendung von Fakt ***** und Aufgabe ***** {{:Kurs:Kurs:Einführung in die mathematische Logik (Osnabrück 2011-2012)/Aussagenlogik/Implikationen/Schlussregel/1/Aufgabe/Aufgabereferenznummer/Aussagenlogik/Implikationen/Schlussregel/1/Aufgabe/Aufgabereferenznummer}})

   $\vdash (\gamma \rightarrow \delta )\rightarrow (\alpha \wedge \gamma \rightarrow \delta ).$

   Daher gilt auch (nach der Regelversion zu Teil (1))

   $\vdash (\alpha \rightarrow \beta )\wedge (\gamma \rightarrow \delta )\rightarrow (\alpha \wedge \gamma \rightarrow \beta )$

   und

   $\vdash (\alpha \rightarrow \beta )\wedge (\gamma \rightarrow \delta )\rightarrow (\alpha \wedge \gamma \rightarrow \delta )$

   bzw. unter Verwendung von Axiom 6.4  (4) und der Assoziativität der Konjunktion

   $\vdash (\alpha \rightarrow \beta )\wedge (\gamma \rightarrow \delta )\wedge \alpha \wedge \gamma \rightarrow \beta$

   und

   $\vdash (\alpha \rightarrow \beta )\wedge (\gamma \rightarrow \delta )\wedge \alpha \wedge \gamma \rightarrow \delta .$

   Nach Axiom 6.4  (3) ist mit der Abkürzung ${}\varphi =(\alpha \rightarrow \beta )\wedge (\gamma \rightarrow \delta )\wedge \alpha \wedge \gamma$

   $\vdash (\varphi \rightarrow \beta )\wedge (\varphi \rightarrow \delta )\rightarrow (\varphi \rightarrow \beta \wedge \delta ).$

   Da die beiden Teilaussagen im Vordersatz ableitbar sind, ist auch der Nachsatz ableitbar, was unter Verwendung von Axiom 6.4  (4) zur Behauptung umformulierbar ist.
   

$\Box$

Die folgende Aussage gibt eine „interne Version“ des Modus Ponens, der ja nach Definition eine Schlussregel ist.

Lemma Lemma 6.7 ändern

Es ist

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

Beweis

Nach Axiom 6.4  (6) ist

$\vdash (\alpha \rightarrow \beta )\wedge (\neg \alpha \rightarrow \beta )\rightarrow \beta ,$

und Axiom 6.4  (5) kann man wegen Axiom 6.4  (4) zu

$\vdash \alpha \rightarrow (\neg \alpha \rightarrow \beta )$

umformulieren. Daraus und aus (Fakt *****)

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

ergibt sich mit der Regelversion zu Lemma 6.7  (2)

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

und daraus durch den Kettenschluss die Behauptung.

$\Box$

Lemma Lemma 6.8 ändern

1. Aus ${}\vdash \alpha \rightarrow (\beta \rightarrow \gamma )$ und ${}\vdash \gamma \rightarrow \delta$ folgt ${}\vdash \alpha \rightarrow (\beta \rightarrow \delta )$.
2. Aus ${}\vdash \alpha$ und ${}\vdash \alpha \wedge \beta \rightarrow \gamma$ ergibt sich ${}\vdash \beta \rightarrow \gamma$.

Beweis

1. Sei

   $\vdash \alpha \rightarrow (\beta \rightarrow \gamma )$

   und

   $\vdash \gamma \rightarrow \delta .$

   Nach Bemerkung ***** gilt auch

   $\vdash \alpha \rightarrow (\gamma \rightarrow \delta )$

   und daraus ergibt sich mit Axiom 6.4  (3), der Konjunktionsregel und dem Modus ponens

   $\vdash \alpha \rightarrow (\beta \rightarrow \gamma )\wedge (\gamma \rightarrow \delta ).$

   Mittels des Kettenschlusses ergibt sich daraus und aus Axiom 6.4  (2) die Behauptung.
   

2. Siehe Aufgabe 6.8.
   

$\Box$

Die folgenden Tautologien machen wichtige Aussagen über das Negationszeichen. Die Tautologie (2) ist eine wichtige Variante der Widerspruchstautologie und die Tautologie (5) heißt Kontraposition.

Lemma Referenznummer erstellen

1. $\vdash (\neg \alpha \rightarrow \alpha )\rightarrow \alpha .$

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

3. $\vdash \alpha \rightarrow \neg \neg \alpha .$

4. $\vdash \neg \neg \alpha \rightarrow \alpha .$

5. $\vdash (\alpha \rightarrow \beta )\rightarrow (\neg \beta \rightarrow \neg \alpha ).$

6. $\vdash (\neg \beta \rightarrow \neg \alpha )\rightarrow (\alpha \rightarrow \beta ).$

Beweis

1. Die Fallunterscheidungstautologie liefert

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

   Aus (Fakt *****)

   $\vdash \alpha \rightarrow \alpha$

   ergibt sich daraus die Behauptung.
   

2. Nach Axiom 6.4  (3) gilt

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

   und nach Axiom 6.4  (5) gilt

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

   Nach Lemma 6.8  (1) folgt

   $\vdash (\neg \beta \rightarrow \neg \alpha )\wedge (\neg \beta \rightarrow \alpha )\rightarrow (\neg \beta \rightarrow \beta ),$

   woraus nach Teil (1) die Behauptung mit der Kettenschlussregel folgt.
   

3. Nach Axiom 6.4  (1) ist

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

   Nach Axiom 6.4  (5) ist

   $\vdash \neg \alpha \wedge \alpha \rightarrow \neg \neg \alpha ,$

   was wir mit Axiom 6.4  (4) zu

   $\vdash \neg \alpha \rightarrow (\alpha \rightarrow \neg \neg \alpha ),$

   umformulieren können. Daraus ergibt sich

   $\vdash \alpha \rightarrow \neg \neg \alpha$

   mit der Fallunterscheidungsregel.
   

4. Nach Axiom 6.4  (1) ist

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

   Nach Axiom 6.4  (5) ist

   $\vdash \neg \alpha \wedge \neg \neg \alpha \rightarrow \alpha ,$

   was wir zu

   $\vdash \neg \alpha \rightarrow (\neg \neg \alpha \rightarrow \alpha ),$

   umformulieren können. Daraus ergibt sich

   $\vdash \neg \neg \alpha \rightarrow \alpha$

   mit der Fallunterscheidungsregel.
   

5. Es ist nach Axiom 6.4  (1)

   $\vdash \neg \alpha \rightarrow (\neg \beta \rightarrow \neg \alpha )$

   und damit auch

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

   Ferner ist nach einer Variante von Axiom 6.4  (5)

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

   Nach Lemma 6.7 ist

   $\vdash \alpha \rightarrow ((\alpha \rightarrow \beta )\rightarrow \beta ),$

   woraus sich

   $\vdash \alpha \rightarrow ((\alpha \rightarrow \beta )\rightarrow (\neg \beta \rightarrow \neg \alpha ))$

   ergibt. Mit der Fallunterscheidungsregel folgt die Behauptung.
   

6. Dies folgt aus (3), (4) und (5).
   

$\Box$

Gleichheitstautologien

Es gelten die beiden folgenden Tautologien für die Gleichheit.

Axiom

Es sei ${}S$ ein Symbolalphabet, ${}s,t$ seien ${}S$- Terme und ${}\alpha$ sei ein ${}S$- Ausdruck. Dann sind die beiden folgenden Ausdrücke syntaktische Tautologien.

1. $\vdash t=t.$

2. $\vdash s=t\wedge \alpha {\frac {s}{x}}\rightarrow \alpha {\frac {t}{x}}.$

Diese beiden Axiome heißen Gleichheitsaxiom und Substitutionsaxiom.

In der folgenden Aussage wird ein wichtiger Begriff für eine syntaktische Tautologie, eine Ableitungsregel oder einen ganzen formalen Kalkül verwendet, den der Korrektheit. Er besagt, dass die Tautologie auch (im semantischen Sinn) allgemeingültig ist bzw. dass der Kalkül nur wahre Aussagen liefert. Die weiter oben axiomatisch formulierten aussagenlogischen Tautologien sind korrekt, d.h. sie (und auch jede weitere daraus mittels Modus Ponens ableitbare Tautologie) sind allgemeingültig, wie eine direkte Durchsicht zeigt. Die folgende Aussage zeigt, dass auch die eben postulierten Gleichheitsaxiome allgemeingültig sind und dass der Kalkül daher korrekt ist.

Lemma Referenznummer erstellen

Die Gleichheitsaxiome

sind korrekt.

Beweis

Es sei ${}I$ eine beliebige ${}S$- Interpretation. (1). Aufgrund der Bedeutung des Gleichheitszeichens unter jeder Interpretation gilt ${}I(t)=I(t)$, also

$I\vDash t=t.$

(2). Es gelte

$I\vDash s=t\wedge \alpha {\frac {s}{x}},$

also ${}I\vDash s=t$ und ${}I\vDash \alpha {\frac {s}{x}}$. Das bedeutet einerseits ${}I(s)=I(t)$. Andererseits gilt nach dem Substitutionslemma

$I{\frac {I(s)}{x}}\vDash \alpha .$

Wegen der Termgleichheit gilt somit auch

$I{\frac {I(t)}{x}}\vDash \alpha$

und daher, wiederum aufgrund des Substitutionslemmas, auch

$I\vDash \alpha {\frac {t}{x}}.$

$\Box$

Korollar Referenznummer erstellen

Aus den Gleichheitsaxiomen lassen sich folgende Gleichheitstautologien ableiten (dabei sind ${}r,s,t,s_{1},\ldots ,s_{n},t_{1},\ldots ,t_{n}$ Terme, ${}f$ ein ${}n$-stelliges Funktionssymbol und ${}R$ ein ${}n$-stelliges Relationssymbol).

1. $\vdash s=t\rightarrow t=s.$

2. $\vdash r=s\wedge s=t\rightarrow r=t.$

3. $\vdash s_{1}=t_{1}\wedge \ldots \wedge s_{n}=t_{n}\rightarrow fs_{1}\ldots s_{n}=ft_{1}\ldots t_{n}.$

4. $\vdash s_{1}=t_{1}\wedge \ldots \wedge s_{n}=t_{n}\wedge Rs_{1}\ldots s_{n}\rightarrow Rt_{1}\ldots t_{n}.$

Beweis

(1). Aufgrund der Gleichheitsaxiome haben wir

$\vdash s=s$

und

$\vdash s=t\wedge (x=s){\frac {s}{x}}\rightarrow (x=s){\frac {t}{x}},$

wobei ${}x$ eine Variable sei, die weder in ${}s$ noch in ${}t$ vorkomme. Daher sind die beiden substituierten Ausdrücke gleich ${}s=s$ bzw. ${}t=s$. Eine aussagenlogische Umstellung der zweiten Zeile ist

$\vdash s=s\rightarrow (s=t\rightarrow t=s),$

sodass sich aus der ersten Zeile mittels Modus ponens

$\vdash s=t\rightarrow t=s$

ergibt.
(2). Es sei wieder ${}x$ eine Variable, die weder in ${}r$ noch in ${}s$ noch in ${}t$ vorkomme. Eine Anwendung des Substitutionsaxioms liefert

$\vdash s=t\wedge (r=x){\frac {s}{x}}\rightarrow (r=x){\frac {t}{x}}.$

Nach Einsetzen und einer aussagenlogischen Umstellung ist dies die Behauptung.
Für (3) siehe Aufgabe *****. {{:Kurs:Kurs:Einführung in die mathematische Logik (Osnabrück 2011-2012)/Prädikatenlogik/Gleichheitstautologien/Folgerungen/Funktion/Aufgabe/Aufgabereferenznummer/Prädikatenlogik/Gleichheitstautologien/Folgerungen/Funktion/Aufgabe/Aufgabereferenznummer}}
(4). Es sei ${}u$ eine Variable, die weder in einem der ${}s_{i}$ noch in einem der ${}t_{i}$ vorkommt. Für jedes ${}i=1,\ldots ,n$ gilt nach Axiom *****  (2) (mit ${}\alpha =\alpha _{i}=Rt_{1}\ldots t_{i-1}us_{i+1}\ldots s_{n}$) dann

$\vdash s_{i}=t_{i}\rightarrow {\left(Rt_{1}\ldots t_{i-1}us_{i+1}\ldots s_{n}{\frac {s_{i}}{u}}\rightarrow Rt_{1}\ldots t_{i-1}us_{i+1}\ldots s_{n}{\frac {t_{i}}{u}}\right)},$

also

$\vdash s_{i}=t_{i}\rightarrow {\left(Rt_{1}\ldots t_{i-1}s_{i}s_{i+1}\ldots s_{n}\rightarrow Rt_{1}\ldots t_{i-1}t_{i}s_{i+1}\ldots s_{n}\right)}.$

Diese Ableitbarkeiten gelten auch, wenn man die Vordersätze durch ihre Konjunktion

$(s_{1}=t_{1})\wedge \ldots \wedge (s_{n}=t_{n})$

ersetzt. Durch die Transitivität der Implikation ergibt sich daher

$\vdash (s_{1}=t_{1})\wedge \ldots \wedge (s_{n}=t_{n})\rightarrow {\left(Rs_{1}\ldots s_{n}\rightarrow Rt_{1}\ldots t_{n}\right)}.$

$\Box$

<< | Kurs:Einführung in die mathematische Logik (Osnabrück 2011-2012) | >> PDF-Version dieser Vorlesung Arbeitsblatt zur Vorlesung (PDF)