1. Grundlagen

1.1 Mathematische Logik

1.2 Die axiomatische Methode

1.3 Mengenlehre

1.4 Das Axiomensystem von Zermelo und Fraenkel

1.1 Mathematische Logik

1.1.1 Aussagen und Aussageformen

Mathematik ist das Aufstellen und Analysieren von Aussagen, wie zum Beispiel:

• Die Zahl \( 3 \) ist eine Primzahl.
• Die Zahl \( 4 \) ist eine Primzahl.
• Es gibt unendlich viele Primzahlzwillinge.

Die erste Aussage ist richtig, die zweite falsch. Über den Wahrheitsgehalt der dritten Aussage köonnen wir nicht abschließend entscheiden, sind aber überzeugt, dass sie entweder wahr oder falsch ist.

Definition: Eine Aussage ist ein umgangssprachlicher Satz, der entweder wahr oder falsch ist.

Diese Definition beinhaltet die Zweiwertigkeit der Aussagenlogik. Außer wahr und falsch gibt keine weitere, dritte Möglichkeit.

Es gibt auch sprachliche Formulierungen, die keine Aussagen sind, da wir ihnen auf sinnvolle Weise keinen Wahrheitswert zuordnen können, wie Glückwünsche, Fragen oder Aufforderungen der folgenden Art:

• Herzlichen Glückwunsch!
• Wollen wir wetten?
• Komm jetzt endlich!

Mathematische Ausdrücke, wie

• \( x+7=28 \)
• \( {\mathcal R}(0,3,1) \)

bezeichnen wir als Aussageformen. Sie werden zu Aussagen, nachdem wir einmal den „Platzhalter“ \( x \) durch eine Zahl substituieren und so \( x+7=28 \) zu einer wahren oder einer falschen Aussage machen, oder \( {\mathcal R}(x,y,z) \) beispielsweise als die Relation \( x\lt y\lt z \) interpretieren, was die Aussage \( {\mathcal R}(x,y,z) \) in unserem Beispiel falsch macht.

Aufgaben

Aufgabe 1.1.1: (Beispiele für Aussagen)

Welche der folgenden Sätze sind Aussagen, welche sind keine Aussagen?

Aufgabe 1.1.2: (Eigene Beispiele für Aussagen)

Formulieren Sie wenigstens

Aufgabe 1.1.3: (Aussageformen)

Geben Sie jeweils ein Beispiel einer mathematischen Aussageform \( {\mathcal R}(x) \) mit einer, \( {\mathcal S}(x,y) \) mit zwei und \( {\mathcal T}(x,y,z) \) mit drei freien Variablen, so dass

Aufgabe 1.1.4: (Ungelöste Probleme der Mathematik)

Formulieren Sie als Aussagen je zwei

Aufgabe 1.1.5: (Primzahlen und Primzahlzwillinge)

Erstellen Sie eine Liste aller Primzahlen kleiner oder gleich \( 300. \) Kennzeichnen Sie insbesondere alle in Ihrer Liste enthaltenen Primzahlzwillinge.

Aufgabe 1.1.6: (Primzahldrillinge)

Zeigen Sie: Es ist \( (3,5,7) \) das einzig mögliche Beispiel eines Primzahldrillings, so dass also \( p, \) \( p+2 \) und \( p+4 \) mit \( p\ge 3 \) drei aufeinander folgende Primzahlen sind. Gehen Sie dabei wie folgt vor:

Warum führt diese Argumentation im Fall \( p=3 \) nicht zum Widerspruch?

1.1.2 Logische Paradoxien

Ein umgangssprachlicher Satz kann grammatikalisch korrekt sein, inhaltlich aber eine logische Paradoxie darstellen. So kennt jeder das Beispiel

Dieser Satz ist falsch.

Ist nämlich dieser Satz wahr, so ist er nach seiner eigenen Behauptung falsch. Ist er aber falsch, so muss er mit derselben Begründung doch wahr sein.

Was stimmt aber nun?

Offenbar werden verschiedene Sprachebenen vermischt: Der Ausdruck dieser Satz

Um Paradoxien dieser Art zu vermeiden, wird die Aussagenlogik zunächst auf

d.h. rein formal, aufbauend auf endlich vielen Axiomen und Schlussregeln und ohne jede inhaltliche Interpretation formuliert. Aussagen werden dann allein vermittels der Axiome und Schlussregeln nach strengen Beweisregeln in neue Aussagen überführt.

Erst im zweiten Schritt wird dieser syntaktischen Form der Logik eine

gegenübergestellt. Hierunter versteht man beispielsweise eine Zuordnung von Aussagen und Aussagenverknüpfungen in die aus den beiden natürlichen Zahlen \( 0 \) und \( 1 \) bestehende Menge \( \{0,1\} \) oder in die Menge \( \{f,w\}, \) wobei \( 0 \) bzw. \( f \) für falsch und \( 1 \) bzw. \( w \) für wahr stehen.

Wahr und falsch sind also semantische Begriffe, denen innerhalb der Aussagenlogik die syntaktischen Begriffe beweisbar bzw. nicht beweisbar gegenüberstehen.

Im Folgenden diskutieren wir wichtige Aspekte der Semantik der Aussagenlogik, die für die mathematische Analysis wichtig sind. Daran anschließend geben wir einen ersten Einblick in die axiomatische Methode, da wir auch später mit verschiedenen Axiomensystemen zu arbeiten haben. Bei dieser Gelegenheit und nur aus historischem Interesse stellen wir verschiedene Axiomensysteme der Aussagenlogik dar.

Aufgaben

Aufgabe 1.1.7: (Ein einfaches Beispiel zur Selbstbezüglichkeit)

Aus ➝ Zoglauer (2008), Seite 16, entnehmen wir das folgende Beispiel:

Dieser Sats enthält drei Feler.

Welche drei Fehler sind gemeint?

Aufgabe 1.1.8: (Die Lügnerparadoxie)

In dem Brief des Paulus an Titus (Der notwendige Kampf gegen Irrlehren) lesen wir (Zitat nach Wikipedia, Die freie Enzyklopädie, Seite "Paradoxon des Epimenides"):

Es hat einer von ihnen gesagt, ihr eigener Prophet: Die Kreter sind immer Lügner, böse Tiere und faule Bäche.

Im Jahre 1908 greift ➝ Russell (1908) dieses Zitat wieder auf:

The oldest contradiction of the kind in question is the Epimenides. Epimenides the Cretan said that all Cretans were liars, and all other statements made by Cretans were certainly lies. Was this a lie?

Das ist die Quelle einer der bekanntesten logischen Paradoxien: Alle Kreter lügen (siehe ➝ Zoglauer (2008)). Diskutieren Sie diese Paradoxie.

Aufgabe 1.1.9: (Russells Barbier-Paradoxie)

In ➝ Russell (2010), Seite 101, finden wir folgende Paradoxie:

I once had a form suggested to me which was not valid, namely the question whether the barber shaves himself or not. You can define the barber as "one who shaves all those, and those only, who do not shave themselves." The question is, does the barber shave himself? In this form the contradiction is not very difficult to solve ...

Wie nämlich ist dieser Widerspruch auflösbar?

Aufgabe 1.1.10: (Zoglauers Kannibalen-Paradoxie)

Aus ➝ Zoglauer (2008), Abschnitt 1.2, entnehmen wir das folgende Beispiel einer Paradoxie:

Ein Reisender gerät unter Kannibalen, die ihn gefangen nehmen und anschließend zur Bereicherung ihres Speiseplanes essen wollen. Die Kannibalen sind sich nur noch nicht einig, wie sie ihn zubereiten sollen. Sie bieten ihm an, er könne irgendeine Aussage machen. Wenn die Aussage wahr ist, werde er gekocht, und wenn sie falsch ist, werde er geröstet ... Daher wird der Reisende entweder gekocht oder geröstet, aber dem unstillbaren Hunger der Kannibalen scheint er nicht entkommen zu können. Trotzdem fand der Reisende einen logischen Ausweg ... Seine Aussage lautet: „Das, was ich jetzt sage, ist falsch.“ Dieser Satz stürzte die Kannibalen in große Verwirrung ...

Was könnte die Kannibalen denn in Verwirrung gebracht haben?

1.1.3 Verknüpfungen von Aussagen

Mathematische Aussagen bezeichnen wir mit kleinen Buchstaben a, b, c usw. Wir ordnen ihnen genau einen der beiden Wahrheitswerte zu:

entweder   \( 1 \) (wahr)   oder   \( 0 \) (falsch)

Aussagen setzen wir durch folgende Junktoren miteinander in Beziehung \[ \neg\,,\quad \wedge\,,\quad \vee\,,\quad \to\,,\quad \leftrightarrow\,. \] In dieser Reihenfolge bedeuten sie: nicht, und, oder, folgt (impliziert), äquivalent.

Aussagenverknüpfungen stellen wieder gewöhnliche Aussagen dar. Die Bedeutungen dieser Verknüpfungen definieren wir anhand einer Wahrheitstabelle:

Beispiel: Es besitzen \( a\to b \) und \( \neg a\vee b \) dieselben Wahrheitstabellen:

Sie heißen daher im aussagenlogischen Sinn äquivalent, i.Z. \[ (a\to b)\equiv(\neg a\vee b). \] Die runden Klammern geben dabei an, in welcher Reihenfolge die Verknüpfungen auszuführen sind. Wir vereinbaren: Von der höchsten zur niedrigsten Priorität sind der Reihe nach auszuführen \( \neg, \) \( \wedge, \) \( \vee, \) \( \to, \) \( \leftrightarrow. \)

Aussagenverknüpfungen stellen wieder gewöhnliche Aussagen dar.

Aufgaben

Aufgabe 1.1.11: (Doppelte Verneinung)

Beweisen Sie die folgende aussagenlogische Äquivalenz vermittels einer Wahrheitstabelle: \[ \neg\neg a\equiv a. \]

Aufgabe 1.1.12: (Idempotenzgesetze der Aussagenlogik)

Beweisen Sie die folgenden aussagenlogische Äquivalenz vermittels einer Wahrheitstabelle:

Aufgabe 1.1.13: (Äquivalenzen der Implikation)

Beweisen Sie die folgenden aussagenlogischen Äquivalenzen vermittels Wahrheitstabellen:

Aufgabe 1.1.14: (Kommutativität der Disjunktion und Konjunktion)

Beweisen Sie die folgenden aussagenlogischen Äquivalenzen vermittels Wahrheitstabellen:

Aufgabe 1.1.15: (Assoziativgesetze der Aussagenlogik)

Beweisen Sie die folgenden aussagenlogischen Äquivalenzen vermittels Wahrheitstabellen:

Aufgabe 1.1.16: (Distributivgesetze der Aussagenlogik)

Beweisen Sie die folgenden aussagenlogischen Äquivalenzen vermittels Wahrheitstabellen:

Aufgabe 1.1.17: (Verschmelzung von Disjunktion und Konjunktion)

Beweisen Sie die folgenden aussagenlogischen Äquivalenzen vermittels Wahrheitstabellen:

Aufgabe 1.1.18: (de Morgansche Regeln der Aussagenlogik)

Beweisen Sie die folgenden aussagenlogischen Äquivalenzen vermittels Wahrheitstabellen:

1.1.4 Aussagenlogische Beweisprinzipien

Definition: Unter einer Tautologie verstehen wir eine Aussage, die unabhängig von der Belegung ihrer Variablen durch die Wahrheitswerte \( 0 \) oder \( 1 \) stets wahr ist.

Beispiele solcher Tautologien, die auch gleichzeitig grundlegende mathematische Beweisprinzipien darstellen, beinhaltet der

Satz: Die folgenden Aussagen sind Tautologien:

Hievon möchten wir vier Beweisprinzipien in Worte wiedergeben:

Im Gegensatz zu Tautologien sind Kontradiktionen Aussagen, die unabhängig von der Belegung ihrer Variablen durch Wahrheitswerte stets falsch sind.

Aufgaben

Aufgabe 1.1.19: (Beispiele aussagenlogischer Tautologien I)

Beweisen Sie die folgenden aussagenlogischen Tautologien vermittels Wahrheitstabellen:

Die Aussage (ii) bezeichnet man auch als reductio ad absurdum (indirekter Beweis oder Beweis durch Widerspruch).

Aufgabe 1.1.20: (Beispiele aussagenlogischer Tautologien II)

Beweisen Sie die folgenden aussagenlogischen Tautologien vermittels Wahrheitstabellen:

Aufgabe 1.1.21: (Beispiele aussagenlogischer Tautologien III)

Beweisen Sie die folgenden aussagenlogischen Tautologien vermittels Wahrheitstabellen:

Aufgabe 1.1.22: (Weitere Beispiele aussagenlogischer Tautologien)

Beweisen Sie die folgenden aussagenlogischen Tautologien vermittels Wahrheitstabellen:

1.1.5 Quantoren

In der Mathematik haben wir es mit Variablen \( x,y,\ldots \) als Elemente von Individuenmengen \( X \) zu tun. Für ihre Beschreibung benötigen wir die beiden folgenden Quantoren.

Definition: Es sei \( p \) eine von einer Variablen \( x \) aus einer Individuenmenge \( X \) abhängige Aussageform. Der Allquantor \( \forall \) und der Existenzquantor \( \exists \) sind dann wie folgt definiert:

Im zweiten Punkt bedeutet „es existiert“ die Existenz wenigstens eines Elementes \( x \) aus \( X. \)

Beispiel: Bedeutet \( \mathbb N=\{1,2,3,\ldots\} \) die Menge der natürlichen Zahlen, so gelten \[ \exists n\in\mathbb N\,:\,n=2,\quad \forall n\in\mathbb N\,:\,n\ge 1. \] Hierin sind die Doppelpunkte zur besseren Lesbarkeit eingefügt.

Beispiel: Eine reellwertige Funktion \( f\colon\Omega\to\mathbb R \) heißt in einem Punkt \( x_0\in\Omega \) stetig, wenn gilt \[ \forall\varepsilon>0\,\exists\delta>0\,\forall x\in\Omega\,(\lvert x-x_0\rvert\lt\delta\to\lvert f(x)-f(x_0)\rvert\lt\varepsilon) \] bzw. ausführlicher: Für alle \( \varepsilon\gt 0 \) existiert ein \( \delta\ge 0, \) so dass gilt \[ |f(x)-f(x_0)|\lt\varepsilon\quad\mbox{für alle}\ x\in\Omega\ \mbox{mit}\ |x-x_0|\lt\delta. \]

Definition: Der Allquantor \( \forall \) und der Existenzquantor \( \exists \) werden wie folgt negiert \[ \neg\forall x\,p(x)\equiv\exists x\,\neg p(x),\quad \neg\exists x\,p(x)\equiv\forall x\,\neg p(x). \] Linksseitig wirkt der Negationsoperator jeweils auf die gesamten Ausdrücke \( \forall x\,p(x) \) bzw. \( \exists x\,p(x). \)

Beispiel: Wir ermitteln \[ \neg\forall x\,\exists y\,p(y)\equiv\exists x\,\neg\exists y\,p(y)\equiv\exists x\forall y\,\neg p(y). \]

Aufgaben

Aufgabe 1.1.23: (Mathematische Aussagen)

Es bezeichne \( \mathbb Z=\{\ldots,-3,-2,-1,0,1,2,3,\ldots\} \) die Menge der ganzen Zahlen. Schreiben sie die folgenden Aussagen als prädikatenlogische Formeln. Welche Aussage ist wahr, welche ist falsch?

Aufgabe 1.1.24: (Aus den Peanoschen Axiomen der natürlichen Zahlen)

Es bezeichne \( \mathbb N=\{1,2,3,\ldots\} \) die Menge der natürlichen Zahlen. Schreiben Sie die folgenden Aussagen als prädikatenlogische Formeln.

Aufgabe 1.1.25: (Größer oder kleiner)

Formulieren Sie die folgenden prädikatenlogischen Formeln in Worten. Welche Aussage ist wahr, welche ist falsch? Negieren Sie die Aussagen. Sind die Negationen wahr? Begründen Sie jeweils.

Aufgabe 1.1.26: (Negation der Stetigkeit)

Negieren Sie die prädikatenlogische Formel der Stetigkeit \[ \forall\varepsilon\gt 0\,\exists\delta\gt 0\,\forall x\in\Omega\,\big(|x-x_0|\lt\delta\to|f(x)-f(x_0)|\lt\varepsilon\big) \] mit dem Ergebnis \[ \exists\varepsilon>0\,\forall\delta\gt 0\,\exists x\in\Omega\,(\lvert x-x_0\rvert\lt\delta\wedge\lvert f(x)-f(x_0)\rvert\ge\varepsilon). \]

1.2 Die axiomatische Methode

1.2.1 Mathematische Beweise

Das Aufstellen und Beweisen von Aussagen steht im Zentrum aller Teilgebiete der Mathematik. Dies geschieht in einem formalen Rahmen:

Eine Sprache besteht aus einer endlichen oder unendlichen Liste von Aussagenvariablen \( a_1,a_2,a_3,\ldots, \) aus aussagenlogischen Verknüpfungen, wie \( \neg \) oder \( \vee, \) deren Bedeutungen an die jeweiligen semantischen Bedeutungen angelehnt sind, und aus Formeln, wie \( a\vee\neg b, \) deren Regeln zum Aufbau ebenfalls im Voraus vereinbart werden.

Ein Axiom ist eine Formel, die in ihrer semantischen Interpretation immer wahr, also tautologisch ist, wie beispielsweise \( \neg a\vee a. \) Unter einer Schlussregel verstehen wir eine Regel, die angibt, wie von einem endlichen System wahrer Voraussetzungen \( a_1,\ldots,a_n \) auf eine neue wahre Formel \( b \) geschlossen werden kann, in Zeichen \[ \genfrac{}{}{1pt}{}{a_1,\ a_2,\ \ldots,a_n}{b}\,. \]

Ein solches formales System, bestehend aus den Elementen der Sprache, aus Axiomen und aus Schlussregeln, bezeichnen wir mit dem Buchstaben \( {\mathcal S.} \)

Es bezeichne nun \( \Gamma \) eine Menge endlich vieler Formeln von \( {\mathcal S}. \) Ein Beweis innerhalb des Systems \( {\mathcal S} \) unter Verwendung der Formelmenge \( \Gamma \) ist dann eine Folge \( F_1,F_2,\ldots,F_n \) von endlich vielen Formeln, die wie folgt entstehen:

Das Symbol \[ \vdash_{\,\Gamma}F_n \] zeigt die Beweisbarkeit der Formel \( F_n \) unter Verwendung der Formelmenge \( \Gamma \) an. Geht aus dem Kontext klar hervor, welche Voraussetzungen in den Beweis eingehen, schreiben wir auch einfach \( \vdash F_n, \) wie bei den nachstehenden Ableitungen verschiedener Schlussregeln. Erst in den Paragraphen 1.2.5 und 1.2.6 studieren wir Beweise, die, bis auf ein Axiom, ohne Voraussetzungen geführt werden - in Zeichen ebenfalls \( \vdash F_n. \)

Wir wollen nun ein konkretes formales System kennenlernen.

1.2.2 Das System von Hodel-Shoenfield

In diesem Paragraphen gehen wir nach dem Lehrbuch ➝ Hodel (2013) vor, siehe auch ➝ Shoenfield (1967). Zunächst legen wir die Sprachelemente fest.

Symbole:

Formeln:

Das Axiomensystem von Hodel-Shoenfield umfasst ferner ein Axiom, vier Schlussregeln:

Axiom:

Schlussregeln:

Zur Vereinfachung der Schreibweise werden noch folgende Setzungen vereinbart:

Definitionen:

Als Anwendung wollen wir folgenden Satz beweisen (siehe ➝ Hodel (2013), Seiten 80-81):

Satz: (Schlussregel der doppelten Negierung)

Es gilt \( \quad\displaystyle\genfrac{}{}{1pt}{}{a}{\neg\neg a}\,. \)

Aufgaben

Aufgabe 1.2.1: (Kommutativität in der Expansionsregel)

Beweisen Sie folgende Version der Expansionsregel \( \quad\displaystyle\genfrac{}{}{1pt}{}{a}{a\vee b}\,. \)

Aufgabe 1.2.2: (Kommutativität in der Assoziativregel)

Beweisen Sie folgende Version der Assoziativregel \( \quad\displaystyle\genfrac{}{}{1pt}{}{(a\vee b)\vee c}{a\vee(b\vee c)}\,. \)

Aufgabe 1.2.3: (Eine weitere Schlussregel zur doppelten Negierung)

Beweisen Sie die folgend Schlussregel \( \quad\displaystyle\genfrac{}{}{1pt}{}{\neg\neg a}{a}\,. \)

Aufgabe 1.2.4: (Satz zum modus tollendo ponens)

Beweisen Sie die Schlussregel \( \quad\displaystyle\genfrac{}{}{1pt}{}{a\vee b,\ \neg a}{b}\,. \)

Aufgabe 1.2.5: (Satz zum modus barbara)

Beweisen Sie die Schlussregel \( \quad\displaystyle\genfrac{}{}{1pt}{}{a\to b,\ b\to c}{a\to c}\,. \)

Aufgabe 1.2.6: (Satz zum modus tollens)

Beweisen Sie die Schlussregel \( \quad\displaystyle\genfrac{}{}{1pt}{}{a\vee b,\ \neg b}{\neg b}\,. \)

Aufgabe 1.2.7: (Satz von der Kontraposition)

Beweisen Sie die Schlussregel \( \quad\displaystyle\genfrac{}{}{1pt}{}{a\to b}{\neg b\to\neg a}\,. \)

1.2.3 Beweis der de Morganschen Regeln

1.2.3 Historische Axiomensysteme

Das Axiomensystem von Frege 1879

Entnommen aus: ➝ Begriffsschrift (1879); siehe auch ➝ Begriffsschrift und andere Aufsätze (2014)

Axiome:

1. \( \quad a\to(b\to a) \)
2. \( \quad [c\to(b\to a)]\to[(c\to b)\to(c\to a)] \)
3. \( \quad [c\to(b\to a)]\to[b\to(c\to a)] \)
4. \( \quad (b\to a)\to(\neg a\to\neg b) \)
5. \( \quad \neg\neg a\to a \)
6. \( \quad a\to\neg\neg a \)

Das Axiomensystem von Russell und Whitehead 1910

Entnommen aus: ➝ Principia mathematica 1 (1910)

Axiome:

1. \( \quad a\vee a\to a \)
2. \( \quad b\to a\vee b \)
3. \( \quad a\vee b\to b\vee a \)
4. \( \quad a\vee(b\vee c)\to b\vee(a\vee c) \)
5. \( \quad (b\to c)\to(a\vee b\to a\vee c) \)

Das Axiomensystem von Hilbert 1922

Entnommen aus: ➝ Die logischen Grundlagen der Mathematik (1922)

Axiome:

1. \( \quad a\to(b\to a) \)
2. \( \quad [a\to(a\to b)]\to(a\to b) \)
3. \( \quad [a\to(b\to c)]\to[b\to(a\to c)] \)
4. \( \quad (b\to c)\to[(a\to b)\to(a\to c)] \)
5. \( \quad a\to(\neg a\to b) \)
6. \( \quad (a\to b)\to[(\neg a\to b)\to b] \)

Schlussregel:

1. Modus Ponens \(\quad\displaystyle \quad\genfrac{}{}{1pt}{}{a,\ a\to b}{a} \)

Das Axiomensystem von Ackermann und Hilbert 1928

Entnommen aus: ➝ Grundzüge der theoretischen Logik (1928)

Axiome:

1. \( \quad a\vee a\to a \)
2. \( \quad a\to a\vee b \)
3. \( \quad a\vee b\to b\vee a \)
4. \( \quad (a\to b)\to(c\vee a\to c\vee b) \)

Schlussregel:

1. Modus Ponens \(\quad\displaystyle \quad\genfrac{}{}{1pt}{}{a,\ a\to b}{a} \)

Das Axiomensystem von Lukasiewicz und Tarski 1930

Entnommen aus: ➝ Untersuchungen über den Aussagenkalkül (1930); siehe auch ➝ J. Lukasiewicz: Elements of mathematical logic (1963)

Axiome:

1. \( \quad (a\to b)\to[(b\to c)\to(a\to c)] \)
2. \( \quad (\neg a\to a)\to a \)
3. \( \quad a\to(\neg a\to b) \)

Das Axiomensystem von Bernays und Hilbert 1934

Entnommen aus: ➝ Grundlagen der Mathematik I (1934)

Axiome:

1. \( \quad a\to(b\to a) \)
2. \( \quad [a\to(a\to b)]\to(a\to b) \)
3. \( \quad (a\to b)\to[(b\to c)\to(a\to c)] \)
4. \( \quad a\wedge b\to a \)
5. \( \quad a\wedge b\to b \)
6. \( \quad (a\to b)\to[(a\to c)\to(a\to b\wedge c)] \)
7. \( \quad a\to a\vee b \)
8. \( \quad b\to a\vee b \)
9. \( \quad (a\to c)\to[(b\to c)\to(a\vee b\to c)] \)
10. \( \quad (a\leftrightarrow b)\to(a\to b) \)
11. \( \quad (a\leftrightarrow b)\to(b\to a) \)
12. \( \quad (a\to b)\to[(b\to a)\to(a\leftrightarrow b)] \)
13. \( \quad (a\to b)\to(\neg b\to\neg a) \)
14. \( \quad a\to\neg\neg a \)
15. \( \quad \neg\neg a\to a \)

Das Axiomensystem von Rosser 1953

Entnommen aus: ➝ Logic for mathematicians (1953)

Axiome:

1. \( \quad a\to(a\wedge a) \)
2. \( \quad (a\wedge b)\to a \)
3. \( \quad (a\to b)\to[\neg(b\wedge c)\to\neg(c\wedge a)] \)

Schlussregel:

1. Modus Ponens \(\quad\displaystyle \quad\genfrac{}{}{1pt}{}{a,\ a\to b}{a} \)

Das Axiomensystem von Ackermann und Hilbert 1959, erste Variation

Entnommen aus: ➝ Grundzüge der theoretischen Logik (1959)

Axiome:

1. alle Formeln
   • die aus einer Disjunktion \( a_1\vee\ldots\vee a_n \) bestehen, worin die \( a_i \) Aussagenvariablen oder negierte Aussagenvariablen sind
   • eine gewisse Aussagenvariable tritt einmal negiert und einmal unnegiert auf

Schlussregel:

1. \(\displaystyle \quad\genfrac{}{}{1pt}{}{a\vee b\vee c}{a\vee \neg\neg b\vee c} \)
2. \(\displaystyle \quad\genfrac{}{}{1pt}{}{a\vee\neg c\vee b,a\vee\neg d\vee b}{a\vee\neg(c\vee d)\vee b} \)

Das Axiomensystem von Lukasiewicz 1963

Entnommen aus: siehe auch ➝ J. Lukasiewicz: Elements of mathematical logic (1963)

Axiome:

1. \( \quad (a\to b)\wedge(b\to c)\to(a\to c) \)
2. \( \quad (\neg a\to a)\to a \)
3. \( \quad a\to(\neg a\to b) \)

Schlussregel:

1. Modus Ponens \(\quad\displaystyle \quad\genfrac{}{}{1pt}{}{a,\ a\to b}{a} \)

Das Axiomensystem von Lukasiewicz 1963, erste Variation

Entnommen aus: siehe auch ➝ J. Lukasiewicz: Elements of mathematical logic (1963)

Axiome:

1. \( \quad (a\to b)\to[(b\to c)\to(a\to c)] \)
2. \( \quad (\neg a\to b)\to[(b\to a)\to a] \)
3. \( \quad a\to(\neg a\to b) \)

Schlussregel:

1. Modus Ponens \(\quad\displaystyle \quad\genfrac{}{}{1pt}{}{a,\ a\to b}{a} \)

Das Axiomensystem von Lukasiewicz 1963, zweite Variation

Entnommen aus: siehe auch ➝ J. Lukasiewicz: Elements of mathematical logic (1963)

Axiome:

1. \( \quad [(a\to b)\to c]\to(b\to c) \)
2. \( \quad [(a\to b)\to c]\to(\neg a\to a) \)
3. \( \quad (\neg a\to c)\to\{(b\to c)\to[(a\to b)\to c]\} \)

Schlussregel:

1. Modus Ponens \(\quad\displaystyle \quad\genfrac{}{}{1pt}{}{a,\ a\to b}{a} \)

Das Axiomensystem von Kleene 1967

Entnommen aus: ➝ Mathematical logic (1967); siehe auch ➝ Mathematical logic (2013);

Axiome:

1. \( \quad a\to(b\to a) \)
2. \( \quad (a\to b)\to\{[a\to(b\to c)]\to(a\to c)\} \)
3. \( \quad a\to(b\to a\wedge b) \)
4. \( \quad a\wedge b\to a \)
5. \( \quad a\wedge b\to b \)
6. \( \quad a\to a\vee b \)
7. \( \quad b\to a\vee b \)
8. \( \quad (a\to c)\to[(b\to c)\to(a\vee b\to c)] \)
9. \( \quad (a\to b)\to[(a\to\neg b)\to\neg a] \)
10. \( \quad \neg\neg a\to a \)
11. \( \quad (a\to b)\to[(b\to a)\to(a\leftrightarrow b)] \)
12. \( \quad (a\leftrightarrow b)\to(a\to b) \)
13. \( \quad (a\leftrightarrow b)\to(b\to a) \)

Schlussregel:

1. Modus Ponens \(\quad\displaystyle \quad\genfrac{}{}{1pt}{}{a,\ a\to b}{a} \)

Das Axiomensystem von Tanaka 1967

Entnommen aus: ➝ On axiom systems of propositional logic XXV (1967)

Axiome:

1. \( \quad (a\to b)\to[(b\to c)\to(a\to c)] \)
2. \( \quad [(a\to b)\to a]\to a \)
3. \( \quad a\to[(a\to b)\to b] \)

Das Axiomensystem von Mendelson 1997

Entnommen aus: ➝ Introduction to mathematical logic (4. Auflage, 1997)

Axiome:

1. \( \quad a\to(b\to a) \)
2. \( \quad a\to(b\to c)\to[(a\to b)\to(a\to c)] \)
3. \( \quad (\neg b\to\neg a)\to[(\neg b\to a)\to b] \)

Schlussregel:

1. Modus Ponens \(\quad\displaystyle \quad\genfrac{}{}{1pt}{}{a,\ a\to b}{a} \)

Die Ersetzungsregel besagt: Sind \( \varphi \) und \( \psi \) äquivalent, so auch \( \chi(\varphi) \) und \( \chi(\psi/\varphi) \) mit einer beliebigen Formel \( \chi, \) wobei \( \chi[\psi/\varphi] \) nach Ersetzen von \( \varphi \) durch \( \psi \) an einigen oder auch an allen Stellen, wo \( \varphi \) in \( \chi \) auftaucht, entsteht.

Die Ersetzungsregel besagt: Sind \( \varphi \) und \( \psi \) äquivalent, so auch \( \chi(\varphi) \) und \( \chi(\psi/\varphi) \) mit einer beliebigen Formel \( \chi, \) wobei \( \chi[\psi/\varphi] \) nach Ersetzen von \( \varphi \) durch \( \psi \) an einigen oder auch an allen Stellen, wo \( \varphi \) in \( \chi \) auftaucht, entsteht.

Aufgaben

Aufgabe 1.2.8: (Weitere Axiomensysteme)

Ergänzen Sie diesen Paragraphen durch weitere Axiomensysteme der Aussagenlogik.

1.2.5 Deduktionslemma, Ersetzungregel und Einsetzregel

Das formale Beweisen kann in der Praxis erleichtert werden durch das Verwenden verschiedener Metaregeln, von denen wir hier, indem wir nach ➝ Hodel (2013), Abschnitt 3.3 vorgehen, das Deduktionslemma, die Ersetzungsregel und die Einsetzregel vorstellen. Diese Regeln gehören überhaupt zum Standardwerkzeug des mathematischen Alltags.

Das Deduktionslemma

Das Deduktionslemma \[ \vdash_{\{a\}}b,\quad\mbox{dann auch}\quad\vdash(a\to b) \] besagt: Gibt es einen Beweis der Formel \( b \) unter Verwendung der Hypothese \( a, \) so gibt es auch einen Beweis der Formel \( a\to b. \) Das Deduktionslemma gilt auch in der Form \[ \vdash_{\Gamma\cup\{a\}}b\,,\quad\mbox{dann auch}\quad\vdash_{\Gamma}(a\to b) \] mit einer Formelmenge \( \Gamma, \) die die Formel \( a \) nicht enthält, aber zu der \( a \) hinzugefügt wird mit dem Resultat einer um \( a \) vergrößerten Formelmenge \( \Gamma\cup\{a\}. \)

Beispielsweise haben wir ➝ hier gezeigt \[ \genfrac{}{}{1pt}{}{a}{\neg\neg a}\quad\mbox{und}\quad\genfrac{}{}{1pt}{}{\neg\neg a}{a}\,, \] und damit folgt nach dem Deduktionslemma \[ \vdash(a\to\neg\neg a)\quad\mbox{und}\quad\vdash(\neg\neg a\to a). \] Es gilt also \( a\leftrightarrow\neg\neg a. \)

Die Ersetzungsregel

Die Ersetzungsregel \[ \genfrac{}{}{1pt}{}{a\leftrightarrow b}{\varphi(a)\leftrightarrow\varphi[b/a]} \] besagt: Sind \( a \) und \( b \) äquivalent, so auch \( \varphi(a) \) und \( \varphi[b/a] \) mit einer beliebigen Formel \( \varphi, \) wobei \( \varphi[b/a] \) nach Ersetzen von \( a \) durch \( b \) an einigen oder auch an allen Stellen, wo \( a \) in \( \varphi \) auftaucht, entsteht.

Beispielsweise gilt wegen \( a\leftrightarrow\neg\neg a \) mit \( \varphi(a,b)=a\vee b \) \[ \genfrac{}{}{1pt}{}{a\vee b}{\neg\neg a\vee b}\,. \]

Die Einsetzregel

Die Einsetzregel \[ \genfrac{}{}{1pt}{}{\varphi(a)}{\varphi[\psi/a]} \] besagt: Ist \( \varphi(a) \) allgemeingültig, so auch \( \varphi[\psi/a], \) wobei \( \varphi[\psi/a] \) nach Einsetzen der Formel \( \psi \) an allen Stellen von \( a \) in \( \varphi(a) \) entsteht.

Beispielsweise gilt mit \( \varphi(a)=\neg a\vee a \) und \( \psi(a,b)=a\vee b \) \[ \genfrac{}{}{1pt}{}{\neg a\vee a}{\neg(a\vee b)\vee(a\vee b)}\,. \]

1.2.6 Herleitung des Systems von Frege

Als Anwendung der vorigen Metaregeln wollen wir vier Axiome des Fregeschen Axiomensystems

1. \( \quad a\to(b\to a) \)
2. \( \quad [c\to(b\to a)]\to[(c\to b)\to(c\to a)] \)
3. \( \quad [c\to(b\to a)]\to[b\to(c\to a)] \)
4. \( \quad (b\to a)\to(\neg a\to\neg b) \)
5. \( \quad \neg\neg a\to a \)
6. \( \quad a\to\neg\neg a \)

aus ➝ diesem Paragraphen aus dem System von Hodel-Shoenfield herleiten. Die Axiome 5 und 6 haben wir bereits ➝ hier als Anwendung des Deduktionslemmas bewiesen. Axiom 4 folgt ebenfalls aus dem Deduktionslemma mit einer als Aufgabe bewiesenen Schlussregel aus ➝ diesem Paragraphen. Zum Beweis von Axiom 1 zeigen wir zunächst \[ \genfrac{}{}{1pt}{}{a\vee b}{a\vee(c\vee b)}\qquad\mbox{(REG)} \] und gehen dazu wie folgt vor:

Damit schließen wir auf

Damit ist Axiom 1 gezeigt.\( \qquad\Box \)

Aufgaben

Aufgabe 1.2.9: (Herleitung der Fregeschen Axiome I)

Beweisen Sie Axiom 2 des Axiomensystems von Frege.

Aufgabe 1.2.10: (Herleitung der Fregeschen Axiome II)

Beweisen Sie Axiom 3 des Axiomensystems von Frege.