Was ist mathematische Logik

Zusammenfassung

Diese Lektion grenzt den Gegenstand der mathematischen Logik ab: nicht die Wahrheit der einzelnen Aussagen, die jeder Wissenschaft zukommt, sondern die Form der Schlussfolgerungen und die Gültigkeit, das heißt die Beziehung zwischen Prämissen und Konklusion, die garantiert, dass die Wahrheit jener auf diese übergeht. Sie definiert Aussage, Argument, Prämisse, Konklusion, Form und Gegenbeispiel; sie unterscheidet die Gültigkeit von der Wahrheit anhand gültiger Argumente mit falscher Konklusion und ungültiger Argumente mit wahrer Konklusion; sie zeigt, warum die natürliche Sprache, mehrdeutig und fähig, über sich selbst zu sprechen, nicht ausreicht, um die Gültigkeit streng zu untersuchen, und sie führt die Unterscheidung zwischen Objektsprache und Metasprache ein, die den ganzen Kurs bestimmt. Danach stellt sie mit ihren ausdrücklichen Annahmen und ihren Beweisen das Lügner-Paradoxon, das Berry-Paradoxon und das Barbier-Paradoxon dar, dazu die Russellsche Antinomie, die der Barbier vorwegnimmt, und erklärt, wie eine formale Sprache sie vermeidet oder in Sätze verwandelt. Sie schließt mit den vier Säulen der mathematischen Logik und mit der Karte des Kurses.

Lernziele

Die Gültigkeit eines Arguments von der Wahrheit seiner Prämissen und seiner Konklusion unterscheiden und eine ungültige Form durch die Konstruktion eines Gegenbeispiels widerlegen.
Mehrdeutigkeiten der natürlichen Sprache erkennen und jede Lesart einer mehrdeutigen Aussage präzisieren.
Die Objektsprache von der Metasprache und den Gebrauch eines Ausdrucks von seiner Erwähnung unterscheiden.
Ein Paradoxon analysieren: seine Annahmen isolieren, den Widerspruch herleiten und entscheiden, welche Annahme aufzugeben ist.

Was die Logik untersucht

Jedes Wissen, das nicht durch unmittelbare Beobachtung gewonnen wird, wird durch Schließen gewonnen: Von gewissen Behauptungen, die man annimmt, geht man zu einer anderen über, die aus ihnen folgt. In der Geometrie schließt, wer weiß, dass die Winkel eines Dreiecks zusammen zwei rechte ergeben, dass kein Dreieck zwei stumpfe Winkel hat; in der Medizin schließt, wer weiß, dass eine bestimmte Krankheit Fieber hervorruft und dass die untersuchte Person keines hat, diese Krankheit aus. Die Logik ist die Disziplin, die untersucht, wann dieser Übergang berechtigt ist, und die mathematische Logik ist diejenige, die ihn mit den Methoden der Mathematik untersucht: indem sie ihre Gegenstände, nämlich Sprachen, Formeln und Ableitungen, exakt definiert und Sätze über sie beweist.

Um genau zu sagen, was sie untersucht, legt man zuerst das Vokabular fest. Eine Aussage ist ein Aussagesatz, von dem es sinnvoll ist zu sagen, er sei wahr oder er sei falsch: „ $7$ ist eine Primzahl“ ist eine wahre Aussage; „jede gerade Zahl ist größer als $5$ “, eine falsche Aussage. Keine Aussagen sind dagegen Fragen („wie spät ist es?“), Befehle („schließ die Tür“) und Ausdrücke mit freien Variablen wie „ $x$ ist gerade“, deren Wert davon abhängt, was $x$ bezeichnet.

Ein Argument ist eine Liste von Aussagen, den Prämissen, zusammen mit einer weiteren Aussage, der Konklusion, die als Folge aus ihnen dargestellt wird. Die Prämissen können beliebige Aussagen sein: wahre, falsche, bekannte oder bloße Annahmen; das Einzige, was sie auszeichnet, ist der Platz, den sie im Argument einnehmen. Wir schreiben Argumente mit den Prämissen in aufeinanderfolgenden Zeilen und der Konklusion nach einem „also“:

BeispielEin Argument

Wenn eine Zahl ein Vielfaches von $4$ ist, ist sie gerade. Die Zahl $28$ ist ein Vielfaches von $4$ . Also ist $28$ gerade.

Seine Prämissen sind „wenn eine Zahl ein Vielfaches von $4$ ist, ist sie gerade“ und „ $28$ ist ein Vielfaches von $4$ “; seine Konklusion, „ $28$ ist gerade“.

Die Logik ist keine Theorie der Wahrheit

Wenn dem so ist, hat die Logik nicht die Aufgabe, herauszufinden, ob die Prämissen eines Arguments wahr sind. Ob $28$ ein Vielfaches von $4$ ist, entscheidet die Arithmetik; ob eine Person Fieber hat, das Thermometer; ob eine Schlacht in einem bestimmten Jahr stattfand, die Geschichtswissenschaft. Ebenso wenig kommt es ihr zu, zu definieren, was Wahrheit ist, eine Frage, die der Philosophie angehört. Die Logik setzt voraus, dass die Aussagen einen Wahrheitswert haben, welcher es auch sei, und untersucht, wie diese Werte zueinander in Beziehung stehen: insbesondere, wann die Wahrheit gewisser Aussagen die Wahrheit einer anderen erzwingt. Anders gesagt: Die Logik ist keine Theorie der Wahrheit, sondern eine Theorie der Übertragung der Wahrheit.

Nun hängt das, was die Wahrheit überträgt, nicht vom Thema des Arguments ab, sondern von seiner Struktur. Man vergleiche das vorige Argument mit diesem: „wenn ein Tier ein Säugetier ist, atmet es Luft; der Wal ist ein Säugetier; also atmet der Wal Luft“. Beide haben dieselbe Form: „wenn etwas $A$ ist, ist es $B$ ; $c$ ist $A$ ; also ist $c$ $B$ “. Die Form eines Arguments ist das, was übrig bleibt, wenn man seine nichtlogischen Ausdrücke (Zahlen, Tiere, Eigenschaften) durch Buchstaben ersetzt und die logischen Wörter beibehält: „nicht“, „und“, „oder“, „wenn… dann“, „alle“, „einige“. Jedes Argument, das man aus einer Form erhält, indem man ihren Buchstaben einen Inhalt gibt, ist eine Instanz dieser Form.

Eine Form ist gültig, wenn keine ihrer Instanzen lauter wahre Prämissen und eine falsche Konklusion hat; ein Argument ist gültig, wenn seine Form es ist. Eine Instanz mit wahren Prämissen und falscher Konklusion heißt Gegenbeispiel zur Form: Woraus folgt, dass eine Form genau dann ungültig ist, wenn sie ein Gegenbeispiel hat.

In den Beweisen dieser Lektion verwenden wir eine Kurzschrift des Deutschen: $V(A)$ kürzt „ $A$ ist wahr“ ab und $F(A)$ , „ $A$ ist falsch“; $\neg$ kürzt „nicht“ ab, $\wedge$ kürzt „und“ ab, $\vee$ kürzt „oder“ ab, $\Rightarrow$ kürzt „wenn… dann“ ab und $\Leftrightarrow$ kürzt „genau dann, wenn“ ab; $\forall$ wird „für alle“ gelesen und $\exists$ , „es gibt“. Diese Zeichen sind hier bloße Abkürzungen von Wörtern der Metasprache, und die Doppelpfeile sind im ganzen Kurs diesem Gebrauch vorbehalten. In der nächsten Lektion erscheinen die Zeichen mit einfachem Strich, $\rightarrow$ und $\leftrightarrow$ , zusammen mit $\neg$ , $\wedge$ und $\vee$ , als Abkürzungen einer formalen Sprache, mit einer Bedeutung, die der Kurs genau festlegen wird; der Unterschied im Strich der Pfeile wird daran erinnern, auf welcher Ebene man spricht.

PropositionWas die Gültigkeit garantiert

Ist ein Argument gültig und sind alle seine Prämissen wahr, so ist seine Konklusion wahr. Folglich ist, wenn ein gültiges Argument eine falsche Konklusion hat, mindestens eine seiner Prämissen falsch.

Beweis

$\dato{p}{V(A_1) \wedge \cdots \wedge V(A_n)}$
Sei ein gültiges Argument mit den Prämissen $A_1, \ldots, A_n$ und der Konklusion $C$ gegeben, und nehmen wir an, dass alle Prämissen wahr sind.
$\resaltar{A_1, \ldots, A_n, C}$
Jedes Argument ist eine Instanz seiner eigenen Form: Es genügt, den Buchstaben der Form den Inhalt zu geben, den sie im Argument hatten.
$\dato{v}{\neg\left( V(A_1) \wedge \cdots \wedge V(A_n) \wedge \resaltar{\neg V(C)} \right)}$
Nach der Definition der Gültigkeit hat keine Instanz dieser Form wahre Prämissen und eine falsche Konklusion; insbesondere hat das Argument selbst sie nicht.
$\resaltar{V(C)}$
Da die Prämissen wahr sind, kann in der verneinten Konjunktion nur die Falschheit der Konklusion versagen: Die Konklusion ist wahr.
$\neg V(C) \Rightarrow \neg\left( V(A_1) \wedge \cdots \wedge V(A_n) \right)$
Ist dagegen die Konklusion falsch, so können nicht alle Prämissen wahr sein, weil sonst die Konklusion wahr wäre.

Die Proposition sagt, was die Gültigkeit garantiert; ebenso klar sollte man sehen, was sie nicht garantiert. Von den acht möglichen Kombinationen aus der Gültigkeit des Arguments, der Wahrheit aller seiner Prämissen und der Wahrheit seiner Konklusion ist nur eine ausgeschlossen, die des gültigen Arguments mit wahren Prämissen und falscher Konklusion; alle übrigen kommen vor.

BeispielGültig, mit falscher Konklusion

Jede Primzahl ist ungerade. Die Zahl $2$ ist eine Primzahl. Also ist $2$ ungerade.

Die Form ist dieselbe wie die des ersten Arguments der Lektion, sodass das Argument gültig ist; dennoch ist seine Konklusion falsch. Die vorige Proposition zeigt, wo der Fehler liegt: Eine Prämisse ist falsch, und zwar die erste, denn $2$ ist eine Primzahl und gerade. Ein gültiges Argument bringt keine Wahrheiten hervor; es bewahrt nur die, die es empfängt.

BeispielUngültig, mit wahrer Konklusion

Wenn eine Zahl ein Vielfaches von $4$ ist, ist sie gerade. Die Zahl $8$ ist gerade. Also ist $8$ ein Vielfaches von $4$ .

Prämissen und Konklusion sind wahr, und dennoch ist das Argument ungültig. Seine Form, „wenn etwas $A$ ist, ist es $B$ ; $c$ ist $B$ ; also ist $c$ $A$ “, hat ein Gegenbeispiel: Mit der Zahl $6$ anstelle der $8$ bleiben die Prämissen wahr („wenn eine Zahl ein Vielfaches von $4$ ist, ist sie gerade“; „ $6$ ist gerade“), und die Konklusion, „ $6$ ist ein Vielfaches von $4$ “, ist falsch. Die Wahrheit der ursprünglichen Konklusion stammt nicht aus den Prämissen, sondern aus der Arithmetik: $8 = 4 \cdot 2$ . Diese ungültige Form, häufig im alltäglichen Schließen, heißt Bejahung des Konsequens.

Daraus folgt die praktische Regel, die die Lektion einüben wird: Um zu zeigen, dass ein Argument ungültig ist, genügt es nicht, darauf hinzuweisen, dass eine Prämisse oder die Konklusion falsch ist, und um zu zeigen, dass es gültig ist, genügt es nicht, dass alles in ihm wahr ist; das Erste verlangt, ein Gegenbeispiel zu seiner Form vorzuweisen, das Zweite, eine Überlegung, die für alle Instanzen gilt.

Natürliche und formale Sprache

Die Definition der Gültigkeit beruht auf zwei Operationen: die Form eines Arguments zu erkennen und zu entscheiden, ob eine Aussage wahr oder falsch ist. Beide setzen voraus, dass jeder Satz nur eine Lesart hat. Die natürliche Sprache, das Deutsche, das Chinesische oder das Arabische, die die Menschen ohne formale Unterweisung erlernen und zur Verständigung gebrauchen, erfüllt diese Bedingung nicht: Ihre Biegsamkeit, die sie für die Dichtung, das Gespräch und die Nuance tauglich macht, macht sie auch mehrdeutig.

Lexikalische Mehrdeutigkeit: Ein Wort hat mehrere Bedeutungen. „Wir treffen uns an der Bank“ kann eine Sitzbank oder ein Geldinstitut meinen.
Syntaktische Mehrdeutigkeit: Ein Satz lässt mehrere Strukturen zu. „Das Doppelte von drei plus vier“ kann $2 \cdot 3 + 4 = 10$ oder $2 \cdot (3 + 4) = 14$ sein.
Mehrdeutigkeit des Wirkungsbereichs: Man weiß nicht, auf welchen Teil des Satzes sich ein logisches Wort bezieht. „Alle Schüler haben nicht bestanden“ kann bedeuten, dass keiner bestanden hat oder dass nicht alle bestanden haben.
Ungenaue Junktoren: Das „oder“ lässt manchmal zu, dass beide Alternativen zutreffen („verlangt wird ein Abschluss oder Berufserfahrung“), und schließt es manchmal aus („Kaffee oder Tee“); das „wenn… dann“ drückt manchmal eine Ursache aus, manchmal eine Regel, manchmal eine bloße Abfolge.

Zur Mehrdeutigkeit kommt ein tieferer Zug hinzu: Die natürliche Sprache kann über sich selbst sprechen. Sie enthält die Wörter „Satz“, „wahr“ und „definieren“, und mit ihnen kann sie Sätze bilden, die sich auf sich selbst beziehen, wie „dieser Satz hat fünf Wörter“. Diese Selbstbezüglichkeit ist im Allgemeinen harmlos; aber, wie man sehen wird, verbunden mit dem Begriff der Wahrheit bringt sie Sätze hervor, die weder wahr noch falsch sein können.

Eine formale Sprache wird so angelegt, dass beide Quellen der Schwierigkeit beseitigt sind. Man legt ein Alphabet fest, eine Sammlung von Zeichen, und Bildungsregeln, die ohne Raum für Deutung sagen, welche Zeichenfolgen wohlgeformte Ausdrücke sind; die Bedeutung jedes Ausdrucks wird danach durch ebenso genaue Definitionen festgelegt. So ist die Frage, ob eine Zeichenfolge zur Sprache gehört, eine Frage, die mechanisch entschieden wird, durch das Prüfen von Regeln, und jeder Ausdruck wird auf nur eine Weise gelesen. Die Sprache dieses Kurses, die die Lektion über die Sprache der Aussagenlogik aufbaut, hat ein Alphabet aus nur zwei Zeichen, dem Kreis $\sigO$ und der Scheibe $\sigI$ , und eine einzige Bildungsregel.

Der Preis ist die Biegsamkeit: Eine formale Sprache taugt nicht zum Gespräch, und jede formale Sprache drückt nur aus, was ihre Regeln zulassen. Es stimmt jedoch nicht, dass die ganze Ausdruckskraft geopfert wird: Die formalen Sprachen der Logik erster Stufe reichen aus, um fast die gesamte Mathematik zu schreiben. Geopfert werden die Mehrdeutigkeit und die unkontrollierte Selbstbezüglichkeit; gewonnen wird die Möglichkeit, Sätze über die Sprache selbst zu beweisen.

Objektsprache und Metasprache

Um eine Sprache zu untersuchen, muss man über sie sprechen, und um über sie zu sprechen, braucht man eine andere Sprache. Die Objektsprache ist die Sprache, die untersucht wird; die Metasprache ist die Sprache, in der sie untersucht wird. In einer lateinischen Grammatik, die auf Deutsch geschrieben ist, ist das Lateinische die Objektsprache und das Deutsche die Metasprache. In diesem Kurs wird die Objektsprache die formale Sprache der Kreise und Scheiben sein, und die Metasprache wird das Deutsche sein, angereichert mit mathematischen Zeichen und mit griechischen Buchstaben, $\varphi$ , $\psi$ , die beliebige Formeln der Objektsprache bezeichnen, ohne ihr anzugehören.

Die Unterscheidung ist aus einem genauen Grund zentral: Die Behauptungen, die der Kurs über die formale Sprache beweisen wird (dass jede Formel auf nur eine Weise gelesen wird, dass alles Ableitbare wahr ist), sind keine Formeln der formalen Sprache, sondern Sätze der Metasprache. Deshalb heißen sie Metatheoreme, zur Unterscheidung von den Theoremen, die das Deduktionssystem innerhalb der Objektsprache hervorbringt.

Eine elementare Gestalt der Unterscheidung ist die, die den Gebrauch eines Ausdrucks von seiner Erwähnung trennt. In „Rom ist eine Stadt“ wird das Wort gebraucht, um über die Stadt zu sprechen; in „‚Rom‘ hat drei Buchstaben“ wird das Wort erwähnt, und die Anführungszeichen zeigen es an: Der Satz spricht über das Wort, nicht über die Stadt. Beides zu verwechseln erzeugt unsinnige Aussagen wie „Rom hat drei Buchstaben“ oder Fehlschlüsse wie „Rom ist eine Stadt; ‚Rom‘ ist ein Wort mit drei Buchstaben; also ist eine Stadt ein Wort mit drei Buchstaben“.

BeispielDrei Ebenen

Nehmen wir das Lateinische als Objektsprache. Der Satz „Roma aeterna est“ gehört zur Objektsprache. Der Satz „‚Roma aeterna est‘ hat drei Wörter“ gehört zur Metasprache, dem Deutschen, und ist wahr. Der Satz „der vorige Satz ist auf Deutsch geschrieben“ spricht über einen Satz der Metasprache: Er gehört einer dritten Ebene an, der Metasprache der Metasprache, obwohl er in derselben Sprache geschrieben ist. Nichts hindert eine und dieselbe Sprache daran, auf mehreren Ebenen zu dienen; worauf es ankommt, ist, nicht aus dem Blick zu verlieren, worüber man spricht.

Die Paradoxien der Sprache

Ein Widerspruch ist eine Behauptung zusammen mit ihrer Verneinung, wie $V(A) \wedge \neg V(A)$ . Ein Paradoxon ist eine Überlegung, die, von annehmbar scheinenden Annahmen ausgehend und in gültig scheinenden Schritten fortschreitend, zu einem Widerspruch gelangt. Nach der Proposition über das, was die Gültigkeit garantiert, ist, wenn die Schritte wirklich gültig sind, eine Annahme falsch: Ein Paradoxon auflösen heißt herausfinden, welche. Man sollte das Paradoxon weder mit der Mehrdeutigkeit verwechseln, die bloß die Vielheit der Lesarten ist, noch mit dem bloß Überraschenden.

Der Lügner

Das älteste Paradoxon dieser Art wird Eubulides von Milet zugeschrieben, im 4. Jahrhundert vor unserer Zeitrechnung. In seiner genauen Fassung spricht es nicht vom Lügen, das die Absicht zu täuschen voraussetzt, sondern von Falschheit: Sei $m$ der Satz „der Satz $m$ ist falsch“. Um den Widerspruch zu erhalten, genügen zwei Annahmen, die man ausdrücklich hinschreiben sollte.

Zweiwertigkeit (B): Jede Aussage ist wahr oder falsch, und nicht beides; falsch zu sein ist gleichbedeutend damit, nicht wahr zu sein.
Wahrheitsschema (T): Ein Satz ist genau dann wahr, wenn das, was er sagt, der Fall ist. Zum Beispiel ist „Schnee ist weiß“ genau dann wahr, wenn Schnee weiß ist.

SatzDas Lügner-Paradoxon

Die Annahmen der Zweiwertigkeit und des Wahrheitsschemas führen, auf den Satz $m$ angewandt, zu einem Widerspruch: Es gibt keine Möglichkeit, $m$ einen Wahrheitswert zuzuordnen, der sie respektiert. In der Abbildung zeigt der Satz $m$ auf sich selbst, und die Pfeile durchlaufen die beiden Möglichkeiten.

Beweis

$\dato{B}{F(m) \Leftrightarrow \neg V(m)}$
Nach der Zweiwertigkeit ist $m$ wahr oder falsch, und nicht beides: Falsch sein heißt nicht wahr sein.
$\dato{T}{V(m) \Leftrightarrow \resaltar{F(m)}}$
Was $m$ sagt, ist, dass $m$ falsch ist. Nach dem Wahrheitsschema ist $m$ genau dann wahr, wenn das, was er sagt, der Fall ist.
$V(m) \Leftrightarrow \resaltar{\neg V(m)}$
Verkettet man beide Äquivalenzen, so ist die Wahrheit von $m$ äquivalent zu ihrer eigenen Verneinung.
$V(m) \Rightarrow \neg V(m), \quad \resaltar{\neg V(m)}$
Wäre $m$ wahr, so wäre er nach der von links nach rechts gelesenen Äquivalenz nicht wahr: Die Annahme widerlegt sich selbst, und $m$ ist nicht wahr.
$\resaltar{V(m) \wedge \neg V(m)}$
Dann aber ist $m$ nach der von rechts nach links gelesenen Äquivalenz wahr: Man hat zugleich eine Behauptung und ihre Verneinung.

Das Ergebnis besagt nicht, dass die Logik widersprüchlich ist, sondern dass die beiden Annahmen für eine Sprache, die den Satz $m$ enthält, nicht zugleich aufrechterhalten werden können. Es gibt also drei Auswege: die Zweiwertigkeit aufgeben und Sätze ohne Wahrheitswert zulassen; das Wahrheitsschema einschränken; oder verhindern, dass die Sprache den Satz $m$ bildet. Der dritte ist der von Alfred Tarski, 1933: Das Prädikat „ist wahr“ einer Sprache gehört nicht zu dieser Sprache, sondern zu ihrer Metasprache. In einer solchen Sprache ist $m$ kein wohlgeformter Satz, und das Paradoxon lässt sich nicht formulieren.

Das Berry-Paradoxon

Dieses Paradoxon, 1906 von Bertrand Russell veröffentlicht, der es George Berry zuschrieb, einem Bibliothekar in Oxford, verwendet nicht das Wort „wahr“, sondern das Wort „definieren“. Man sagt, ein deutscher Ausdruck definiere eine natürliche Zahl, wenn er sie so beschreibt, dass man sie ohne Mehrdeutigkeit identifizieren kann: „die kleinste Primzahl größer als zehn“ definiert die $11$ . Betrachten wir den Ausdruck „die kleinste natürliche Zahl, die nicht mit weniger als zwanzig Wörtern definierbar ist“, der genau so zu lesen ist, wie er geschrieben steht, und nennen wir $b$ die Zahl, die er zu definieren vorgibt. Die natürlichen Zahlen sind in diesem Kurs $1, 2, 3, \ldots$

SatzDas Berry-Paradoxon

Ist der Wortschatz des Deutschen endlich und ist die Beziehung „der Ausdruck definiert die Zahl“ wohlbestimmt, so gelangt man zu einem Widerspruch: Die Zahl $b$ existiert und kann zugleich mit weniger als zwanzig Wörtern definiert werden und nicht definiert werden. In der Abbildung werden die kurzen Ausdrücke auf die Zahlen geschickt, die sie definieren, und das sind wenige; die erste Zahl, die frei bleibt, ist $b$ .

Beweis

$\dato{N}{N \leq k + k^2 + \cdots + k^{19}}$
Sei $k$ die Anzahl der Wörter des Wörterbuchs. Ausdrücke aus einem Wort gibt es höchstens $k$ ; aus zweien höchstens $k^2$ ; und so weiter bis zu denen aus neunzehn. Die Ausdrücke aus weniger als zwanzig Wörtern bilden also eine endliche Anzahl $N$ .
$\dato{D}{D = \{ d_1, \ldots, d_r \}, \quad r \leq N}$
Jeder Ausdruck definiert höchstens eine Zahl. Sei $D$ die Menge der natürlichen Zahlen, die irgendein Ausdruck aus weniger als zwanzig Wörtern definiert: Sie hat höchstens $N$ Elemente.
$(\exists n \leq N + 1)\,(n \notin D), \quad \resaltar{b \notin D}$
Unter den $N + 1$ Zahlen $1, 2, \ldots, N + 1$ gibt es eine, die nicht in $D$ liegt. Durchläuft man sie der Reihe nach, so ist die erste, die nicht in $D$ liegt, die kleinste natürliche Zahl, die sich nicht mit weniger als zwanzig Wörtern definieren lässt: Alle vorhergehenden liegen in $D$ .
$13 < 20, \quad \resaltar{b \in D}$
Aber der Ausdruck „die kleinste natürliche Zahl, die nicht mit weniger als zwanzig Wörtern definierbar ist“ hat dreizehn Wörter und definiert gerade $b$ .
$\resaltar{b \in D \wedge b \notin D}$
Man hat zugleich eine Behauptung und ihre Verneinung.

Die übliche Darstellung, die sich auf die Bemerkung beschränkt, der Ausdruck habe weniger als zwanzig Wörter, lässt die Hälfte des Arguments aus: dass die Zahl $b$ existiert, was die Endlichkeit des Wortschatzes und die Wahl der ersten fehlenden Zahl erfordert. Die Annahme, die versagt, ist die zweite: „Definieren“ ist keine genaue Beziehung des Deutschen, denn der Ausdruck, der $b$ definiert, verwendet selbst das Wort „definieren“, und sein Sinn hängt davon ab, welche Ausdrücke als Definitionen zählen. In einer formalen Sprache $L$ lässt sich präzisieren, was „definierbar in $L$ “ bedeutet, aber dieser Begriff ist nur in der Metasprache ausdrückbar; der Ausdruck, der $b$ definiert, gehört nicht zu $L$ , und der Widerspruch verschwindet: $b$ ist in $L$ nicht mit wenigen Zeichen definierbar, wohl aber in der Metasprache.

Der Barbier und die Russellsche Menge

Das Barbier-Paradoxon wird gewöhnlich so erzählt: In einem Dorf gibt es einen Barbier, einen Mann aus dem Dorf, der alle Männer des Dorfes rasiert, die sich nicht selbst rasieren, und nur diese. Rasiert der Barbier sich selbst? Die Wörter „und nur diese“ sind wesentlich: Ein Barbier, der alle rasierte, die sich nicht selbst rasieren, ohne die Einschränkung, könnte sich auch selbst rasieren, ohne jeden Widerspruch. Das Paradoxon ist ein Sonderfall eines allgemeinen Lemmas von diagonaler Form, das man ein für alle Mal beweisen sollte.

LemmaDas Diagonallemma

Sei $D$ eine Gesamtheit von Gegenständen und $R$ eine Beziehung zwischen ihnen, sodass für jedes Paar $x$ , $y$ von Gegenständen aus $D$ die Behauptung $R(x, y)$ wahr oder falsch ist. Dann gibt es keinen Gegenstand $b$ aus $D$ , sodass für jedes $x$ aus $D$ die Behauptung $R(b, x)$ genau dann gilt, wenn $R(x, x)$ nicht gilt. In der Abbildung ist jede Zeile ein Gegenstand $x$ und jede Spalte ein Gegenstand $y$ , und ein Feld ist ausgefüllt, wenn $R(x, y)$ gilt; die Zeile, die wir für $b$ suchen, müsste die Diagonale umkehren und unterscheidet sich deshalb von jeder Zeile in deren Diagonalfeld.

Beweis

$\dato{b}{(\forall x \in D)\,\left( R(b, x) \Leftrightarrow \neg R(x, x) \right)}$
Nehmen wir an, es gebe ein solches $b$ in $D$ .
$R(b, \resaltar{b}) \Leftrightarrow \neg R(\resaltar{b}, \resaltar{b})$
Die Bedingung gilt für jedes $x$ aus $D$ , und $b$ ist eines davon: Wir können $x = b$ setzen.
$R(b, b) \Rightarrow \resaltar{\neg R(b, b)}$
Gilt $R(b, b)$ , so gilt es nach der Äquivalenz nicht: Widerspruch.
$\neg R(b, b) \Rightarrow \resaltar{R(b, b)}$
Gilt $R(b, b)$ nicht, so gilt es nach der Äquivalenz: ebenfalls Widerspruch.
$\neg (\exists b \in D)\,(\forall x \in D)\,\left( R(b, x) \Leftrightarrow \neg R(x, x) \right)$
Da einer der beiden Fälle eintreten muss, ist die Annahme unhaltbar: Ein solches $b$ gibt es nicht.

KorollarDen Barbier gibt es nicht

In keinem Dorf gibt es einen Mann aus dem Dorf, der alle Männer des Dorfes rasiert, die sich nicht selbst rasieren, und nur diese.

Beweis

$(\forall x \in D)\,\left( R(b, x) \Leftrightarrow \neg R(x, x) \right)$
Sei $D$ die Gesamtheit der Männer des Dorfes und $R(x, y)$ die Beziehung „ $x$ rasiert $y$ “. Der Barbier $b$ ist ein Mann aus dem Dorf, sodass er in $D$ liegt; dass er ein Barbier wie der beschriebene ist, bedeutet, dass er jeden Mann des Dorfes genau dann rasiert, wenn dieser Mann sich nicht selbst rasiert.
$\resaltar{\neg (\exists b \in D)}\,(\forall x \in D)\,\left( R(b, x) \Leftrightarrow \neg R(x, x) \right)$
Nach dem Diagonallemma erfüllt kein Mann des Dorfes diese Bedingung: Der beschriebene Barbier existiert nicht. Die Geschichte ist kein Paradoxon, sondern der Beweis, dass ihr Held unmöglich ist.

Die Folgerung aus dem Barbier ist harmlos: Niemand hatte behauptet, dass es einen solchen Barbier gebe. Anders steht es mit seiner Fassung in der Mengenlehre. 1902 schrieb Russell an Gottlob Frege, dass dessen System, das die Arithmetik auf die Logik gründen wollte, das folgende Komprehensionsprinzip zuließ: Zu jeder Eigenschaft gibt es eine Menge, deren Elemente genau die Gegenstände sind, die sie haben. Auf die Eigenschaft angewandt, sich nicht selbst als Element zu enthalten, behauptet das Prinzip, dass es die Menge gibt

Z = \{ x : x \notin x \}

KorollarDie Russellsche Antinomie

Das Komprehensionsprinzip ohne Einschränkungen ist widersprüchlich.

Beweis

$\dato{Z}{(\forall x \in D)\,\left( x \in Z \Leftrightarrow x \notin x \right)}$
Sei $D$ die Gesamtheit aller Mengen und $R(x, y)$ die Beziehung „ $y$ ist Element von $x$ “. Das Komprehensionsprinzip, auf die Eigenschaft $x \notin x$ angewandt, behauptet, dass es eine Menge $Z$ gibt, deren Elemente die Mengen sind, die sich nicht selbst als Element enthalten.
$(\forall x \in D)\,\left( \resaltar{R(Z, x)} \Leftrightarrow \resaltar{\neg R(x, x)} \right)$
Mit der gewählten Beziehung ist die Bedingung für $Z$ genau die des Diagonallemmas, mit $Z$ an der Stelle von $b$ : $x \in Z$ ist $R(Z, x)$ , und $x \notin x$ ist $\neg R(x, x)$ .
$\resaltar{Z \in Z \Leftrightarrow Z \notin Z}$
Die Menge $Z$ ist eine Menge, sodass sie in $D$ liegt; nach dem Diagonallemma gibt es ein solches $Z$ nicht, und mit $x = Z$ erhält man die unmögliche Äquivalenz. Das Prinzip behauptet aber, dass es existiert. Das Prinzip impliziert also einen Widerspruch.

Anders als beim Barbier war hier die Existenz von $Z$ keine Annahme einer Erzählung, sondern ein Prinzip der Theorie. Die Russellsche Antinomie löst man nicht, indem man erklärt, dass $Z$ nicht existiert, sondern indem man die Theorie umgestaltet: Die axiomatische Mengenlehre Zermelos von 1908 erlaubt, mit einer Eigenschaft nur Teilmengen einer schon gegebenen Menge zu bilden, und mit dieser Einschränkung lässt sich der Widerspruch nicht herleiten.

Was kein Paradoxon ist

Man hat bisweilen die Beobachtung „Paradoxon der leeren Menge“ genannt, dass die leere Menge existiert, obwohl sie keine Elemente hat, als müsste ein existierender Gegenstand aus existierenden Gegenständen bestehen. Darin liegt keinerlei Widerspruch: Eine Menge besteht nicht aus ihren Elementen wie eine Mauer aus ihren Ziegeln, sondern ist durch sie bestimmt, und die Gesamtheit der Elemente einer Menge kann keines enthalten, so wie eine leere Schachtel eine Schachtel bleibt. Dass eine Tatsache überrascht, macht sie nicht paradox; das Paradoxon verlangt, einen Widerspruch herzuleiten, und hier wird keiner hergeleitet.

Wie eine formale Sprache mit ihnen umgeht

Aus dem Vorigen folgt, dass eine formale Sprache die Paradoxien nicht durch Zauberei vermeidet, sondern auf zwei genaue Weisen. Die erste: Es können ihr die Mittel fehlen, die sie hervorbringen. Die Sprache der Aussagenlogik, die dieser Kurs aufbaut, hat weder Sätze, die sich auf sich selbst beziehen, noch ein Wahrheitsprädikat: In ihr lässt sich der Satz des Lügners nicht schreiben, und ihre Semantik ordnet jeder Formel bei jeder Zuordnung von Werten zu den Variablen einen einzigen Wahrheitswert zu. Die zweite: In reicheren Sprachen wird das Paradoxon zu einem Satz. Die Überlegung des Lügners, streng durchgeführt, beweist, dass die Wahrheit einer hinreichend ausdrucksstarken Sprache in eben dieser Sprache nicht definierbar ist (Tarski); die des Barbiers und Russells beweist, dass gewisse Gesamtheiten keine Mengen sind; und mit dem von Berry verwandte Argumente stehen im Zentrum der Unvollständigkeitssätze Kurt Gödels von 1931. So ist das, was in der natürlichen Sprache eine Verlegenheit ist, in einer formalen Sprache eine Information.

Die vier Säulen der mathematischen Logik

Die mathematische Logik entstand am Ende des 19. und zu Beginn des 20. Jahrhunderts, mit Frege, Peano, Russell und David Hilbert, als Antwort auf eine genaue Frage: auf welchen Grundlagen die Mathematik ruht und ob diese Grundlagen frei von Widerspruch sind. Heute teilt man sie in vier große Zweige ein, die sich ständig verflechten.

Beweistheorie: Sie untersucht formale Beweise als mathematische Gegenstände, das heißt als endliche Folgen von Formeln, die ausdrücklichen Regeln folgen; sie fragt, was sich in einem System beweisen lässt, ob ein System widerspruchsfrei ist und wie sich Beweise ineinander umformen lassen. Die Einheit zur Deduktion in diesem Kurs ist eine erste Berührung mit ihr.
Modelltheorie: Sie untersucht die Beziehung zwischen einer formalen Sprache und den Strukturen, die sie interpretieren, ihren Modellen; sie fragt, welche Strukturen eine Menge von Formeln erfüllen und welche Eigenschaften der Strukturen sich in einer gegebenen Sprache ausdrücken lassen. Die Einheit zur Semantik mit ihren Zuordnungen von Wahrheitswerten ist ihre elementarste Fassung.
Mengenlehre: Sie untersucht die Mengen mit genauen Axiomen, wie denen von Zermelo und Fraenkel, in denen sich fast die gesamte Mathematik schreiben lässt; sie entstand zu einem guten Teil aus der Notwendigkeit, die Russellsche Antinomie zu vermeiden.
Berechenbarkeitstheorie: Sie untersucht, welche Probleme sich durch ein mechanisches Verfahren lösen lassen und welche nicht. Die Aussagenlogik ist entscheidbar, wie der Kurs zeigen wird: Es gibt ein Verfahren, das in endlich vielen Schritten entscheidet, ob eine Formel allgemeingültig ist; die Prädikatenlogik dagegen ist es nicht.

Keine Säule lässt sich gründlich untersuchen, ohne die anderen zu berühren: Die Vollständigkeit, ein zentrales Ergebnis dieses Kurses, ist zugleich ein Satz der Beweistheorie und der Modelltheorie, und die Entscheidbarkeit, die man aus ihr gewinnt, gehört zur Berechenbarkeit.

Die Karte des Kurses

Der Kurs durchläuft für die einfachste Sprache der Logik, die aussagenlogische, den vollständigen Weg einer logischen Theorie, in vier Einheiten.

Sprache: die Syntax. Man baut die Objektsprache mit ihrem Alphabet aus zwei Zeichen und ihrer Bildungsregel auf, beweist, dass jede Formel auf nur eine Weise gelesen wird, lernt, durch Induktion zu beweisen, und übersetzt Aussagen und Argumente der natürlichen Sprache in die formale Sprache, wobei man festhält, was die Übersetzung bewahrt und was sie verliert.
Deduktion: Man legt ein System von Axiomen und Schlussregeln fest und definiert, was es bedeutet, dass eine Formel $\varphi$ aus einer Menge von Formeln $\Gamma$ ableitbar ist, was man $\Gamma \vdash \varphi$ schreibt. Das ist die syntaktische Seite der Gültigkeit: Zeichen nach Regeln umformen, ohne auf ihre Bedeutung zu achten.
Semantik: Man ordnet jeder Formel bei jeder Zuordnung einen Wahrheitswert zu und definiert, was es bedeutet, dass $\varphi$ aus $\Gamma$ folgt, was man $\Gamma \models \varphi$ schreibt: Jede Zuordnung, die die Formeln von $\Gamma$ wahr macht, macht $\varphi$ wahr. Das ist die semantische Seite der Gültigkeit, die Definition dieser Lektion, präzise gemacht.
Metatheorie: Man beweist, dass beide Seiten übereinstimmen. Die Korrektheit besagt, dass alles Ableitbare eine Folgerung ist, und die Vollständigkeit, dass jede Folgerung ableitbar ist. Danach untersucht man die Kompaktheit und ein mechanisches Verfahren, die Resolution, um zu entscheiden, ob eine Menge von Formeln erfüllbar ist.

Wenn dem so ist, ist der Kurs das erste vollständige Beispiel einer mathematischen Theorie, deren Gegenstand das Schließen selbst ist; und alle seine Behauptungen über die formale Sprache werden, wie man in dieser Lektion gesehen hat, Sätze der Metasprache sein, die mit der Strenge der Mathematik bewiesen sind.

Gelöste Aufgaben

Die folgenden Aufgaben üben mit steigender Schwierigkeit die Unterscheidungen der Lektion ein: ein Argument widerlegen, dessen Sätze alle wahr sind, die Lesarten einer mehrdeutigen Aussage trennen, Ausdrücke der Objektsprache und der Metasprache einordnen und zwei Überlegungen von paradoxem Anschein analysieren, um zu entscheiden, ob sie Paradoxien sind.

Gelöste Aufgabe 1Alles wahr und dennoch ungültig

Man zeige, dass das folgende Argument ungültig ist, obwohl seine Prämissen und seine Konklusion wahr sind: „jedes Vielfache von $6$ ist gerade; die Zahl $12$ ist gerade; also ist $12$ ein Vielfaches von $6$ “.

Lösung

$(\forall x)\,(S(x) \Rightarrow P(x)), \quad P(12), \quad S(12)$
Wir kürzen „ $x$ ist ein Vielfaches von $6$ “ durch $S(x)$ ab und „ $x$ ist gerade“ durch $P(x)$ . Die Prämissen und die Konklusion sind wahr, denn $12 = 6 \cdot 2$ .
$(\forall x)\,(S(x) \Rightarrow P(x)), \quad P(\resaltar{c}), \quad S(\resaltar{c})$
Die Form erhält man, indem man den Namen $12$ durch einen Buchstaben $c$ ersetzt: zwei Prämissen und eine Konklusion.
$(\forall x)\,(S(x) \Rightarrow P(x)), \quad P(\resaltar{4})$
Wir suchen eine Instanz mit wahren Prämissen: Die erste hängt nicht von $c$ ab, und die zweite verlangt eine gerade Zahl. Wir nehmen $c = 4$ .
$\neg S(\resaltar{4})$
Die Konklusion dieser Instanz ist falsch, denn $4$ ist kein Vielfaches von $6$ .
$\resaltar{12 = 6 \cdot 2}$
Die Form hat ein Gegenbeispiel: Sie ist ungültig, und das Argument ebenso. Die Wahrheit seiner Konklusion stammt aus der Arithmetik, nicht aus den Prämissen.

Gelöste Aufgabe 2Eine Mehrdeutigkeit des Wirkungsbereichs

Sei $L$ die Liste der Zahlen $4$ , $6$ , $7$ . Man zeige, dass der Satz „alle Zahlen von $L$ sind nicht prim“ zwei Lesarten hat und dass bei dieser Liste die eine wahr und die andere falsch ist.

Lösung

$\dato{a}{\neg Q(4) \wedge \neg Q(6) \wedge \neg Q(7)}$
Wir kürzen „ $x$ ist prim“ durch $Q(x)$ ab. Erste Lesart: Die Verneinung bezieht sich auf jede Zahl, und der Satz sagt, dass keine prim ist.
$\dato{n}{\neg\left( Q(4) \wedge Q(6) \wedge Q(7) \right)}$
Zweite Lesart: Die Verneinung bezieht sich auf die ganze Behauptung, und der Satz sagt, dass nicht alle prim sind.
$Q(7), \quad \neg\left( \neg Q(4) \wedge \neg Q(6) \wedge \resaltar{\neg Q(7)} \right)$
Da $7$ prim ist, ist das letzte Glied der ersten Lesart falsch und mit ihm die ganze Konjunktion: Die erste Lesart ist falsch.
$\neg Q(4), \quad \neg\left( \resaltar{Q(4)} \wedge Q(6) \wedge Q(7) \right)$
Da $4$ nicht prim ist, ist die Konjunktion der zweiten Lesart falsch und ihre Verneinung wahr: Die zweite Lesart ist wahr.
$\resaltar{\neg Q(4) \wedge \neg Q(6) \wedge \neg Q(7)} \Rightarrow \neg\left( Q(4) \wedge Q(6) \wedge Q(7) \right)$
Die beiden Lesarten sind nicht äquivalent: Die erste impliziert die zweite, aber nicht umgekehrt, und diese Liste zeigt es. In der Mathematik schreibt man die zweite „nicht alle Zahlen von $L$ sind prim“ und die erste „keine Zahl von $L$ ist prim“.

Gelöste Aufgabe 3Objektsprache und Metasprache

Nehmen wir als Objektsprache die Folgen der Zeichen $\sigO$ und $\sigI$ und als Metasprache das Deutsche, mit griechischen Buchstaben, die beliebige Folgen bezeichnen. Man ordne jeden der folgenden Ausdrücke ein und entscheide, wo es angebracht ist, ob er wahr ist: (a) $\sigO\sigO\sigI$ ; (b) „ $\sigO\sigO\sigI$ hat drei Zeichen“; (c) „für jede Folge $\varphi$ beginnt die Folge $\sigI\varphi$ mit einer Scheibe“; (d) „ $\sigO\sigO\sigI$ ist wahr“.

Lösung

$\resaltar{\sigO\sigO\sigI}$
Der Ausdruck (a) gehört zur Objektsprache: Er ist eine Folge von Zeichen, kein Satz des Deutschen, und weder wahr noch falsch; man spricht über ihn, aber er behauptet nichts.
$\sigO \; \sigO \; \sigI \quad (3)$
Der Ausdruck (b) ist ein Satz der Metasprache, der die Folge (a) erwähnt und ihre Zeichen zählt: Er ist wahr.
$\resaltar{\sigI}\varphi$
Der Ausdruck (c) ist ein Satz der Metasprache. Der Buchstabe $\varphi$ ist kein Zeichen der Objektsprache, sondern eine Variable der Metasprache, die ihre Folgen durchläuft; der Satz ist wahr, denn $\sigI\varphi$ beginnt nach Konstruktion mit der Scheibe.
$v_2 = \sigO\sigO\sigI$
Der Ausdruck (d) gehört zur Metasprache, hat aber noch keinen Wahrheitswert: Die Folge $\sigO\sigO\sigI$ wird eine Variable der Sprache des Kurses sein, und eine Variable ist nicht an sich wahr oder falsch, sondern erst, wenn eine Zuordnung ihr in der Einheit zur Semantik einen Wert gibt. In der nächsten Lektion wird sie $v_2$ heißen.

Gelöste Aufgabe 4Epimenides ist nicht der Lügner

Auf einer Tafel steht der Satz $e$ , vielleicht neben anderen: „jeder Satz, der auf dieser Tafel steht, ist falsch“. Man beweise unter Annahme der Zweiwertigkeit und des Wahrheitsschemas, dass $e$ falsch ist und dass auf der Tafel irgendein anderer wahrer Satz steht; und man folgere, dass es genau dann ein Paradoxon gibt, wenn kein anderer Satz auf der Tafel wahr ist, wie es der Fall ist, wenn $e$ der einzige ist.

Lösung

$\dato{T}{V(e) \Leftrightarrow (\forall x \in O)\,F(x)}$
Sei $O$ die Menge der Sätze auf der Tafel; $e$ ist einer von ihnen. Nach dem Wahrheitsschema ist $e$ genau dann wahr, wenn alle Sätze von $O$ falsch sind.
$V(e) \Rightarrow \resaltar{F(e)} \Rightarrow \neg V(e)$
Wäre $e$ wahr, so wären alle Sätze von $O$ falsch, und $e$ liegt in $O$ : $e$ wäre falsch und nach der Zweiwertigkeit nicht wahr. Die Annahme widerlegt sich selbst.
$\resaltar{F(e)}$
Also ist $e$ nicht wahr; nach der Zweiwertigkeit ist er falsch.
$(\exists x \in O)\,\left( x \neq e \wedge V(x) \right)$
Nach dem Wahrheitsschema bedeutet, dass $e$ falsch ist, dass nicht alle Sätze von $O$ falsch sind: Einer ist wahr, und er ist nicht $e$ , der falsch ist.
$\neg (\exists x \in O)\,\left( x \neq e \wedge V(x) \right) \Rightarrow \resaltar{V(e) \wedge \neg V(e)}$
Steht auf der Tafel ein anderer wahrer Satz, so ist alles stimmig: $e$ ist einfach falsch. Ist dagegen kein anderer wahr, so gibt es kein $x$ , das von $e$ verschieden ist, in $O$ liegt und wahr ist, und man erhält einen Widerspruch, wie beim Lügner; so ist es insbesondere, wenn $e$ der einzige Satz auf der Tafel ist. Ob das Paradoxon auftritt, hängt also von einer empirischen Tatsache ab: von dem, was auf der Tafel steht.

Gelöste Aufgabe 5Das Heterologische

Ein Adjektiv ist autologisch, wenn es auf sich selbst zutrifft („mehrsilbig“ ist mehrsilbig; „deutsch“ ist ein deutsches Wort), und heterologisch, wenn nicht („einsilbig“ ist nicht einsilbig; „englisch“ ist kein englisches Wort). Man beweise, dass man zu einem Widerspruch gelangt, wenn „heterologisch“ ein Adjektiv ist und die Beziehung „trifft zu auf“ für alle Adjektive wohlbestimmt ist; und man entscheide, welche Annahme aufzugeben ist.

Lösung

$\dato{R}{R(x, x)}$
Sei $D$ die Gesamtheit der Adjektive des Deutschen und $R(x, y)$ die Beziehung „das Adjektiv $x$ trifft auf das Wort $y$ zu“. Ein Adjektiv $x$ ist autologisch, wenn $R(x, x)$ , und heterologisch, wenn $\neg R(x, x)$ .
$\dato{h}{(\forall x \in D)\,\left( R(h, x) \Leftrightarrow \neg R(x, x) \right)}$
Sei $h$ das Adjektiv „heterologisch“. Nach seiner Definition trifft es auf ein Adjektiv genau dann zu, wenn dieses Adjektiv nicht auf sich selbst zutrifft.
$R(\resaltar{h}, \resaltar{h}) \Leftrightarrow \neg R(\resaltar{h}, \resaltar{h})$
Ist $h$ ein Adjektiv, so liegt es in $D$ , und seine Bedingung ist die des Diagonallemmas. Mit $x = h$ erhält man die unmögliche Äquivalenz.
$h \in D \Rightarrow \resaltar{h \notin D}$
Nach dem Diagonallemma erfüllt kein Gegenstand aus $D$ die Bedingung von $h$ . Liegt $h$ in $D$ , so gibt es einen Widerspruch.
$\resaltar{h \notin D}$
Die Annahme, die versagt, ist die zweite: „trifft zu auf“ ist keine genaue Beziehung für Adjektive, die, wie „heterologisch“, ihrerseits durch eben diese Beziehung definiert sind. In einer formalen Sprache würde die Beziehung $R$ in der Metasprache definiert, und das Adjektiv $h$ gehörte nicht zur Objektsprache, sodass die Bedingung $h \in D$ falsch wäre und es keinen Widerspruch gäbe.

Übungsaufgaben

Die ersten beiden Aufgaben üben die Gültigkeit und die Mehrdeutigkeit ein; die dritte den Gebrauch und die Erwähnung; die beiden letzten verlangen, ein neues Paradoxon zu analysieren und das Diagonallemma außerhalb der Sprachwissenschaft anzuwenden. Jede hat einen Hinweis, den man erst öffnen sollte, nachdem man sie versucht hat.

Übungsaufgabe 1Zwei ähnliche Formen

Man betrachte die beiden folgenden Formen: (a) „wenn $p$ , dann $q$ ; nicht $q$ ; also nicht $p$ “; (b) „wenn $p$ , dann $q$ ; nicht $p$ ; also nicht $q$ “. Man entscheide, welche gültig ist und welche nicht; für die ungültige konstruiere man ein Gegenbeispiel mit Aussagen über Zahlen, und für die gültige erkläre man, warum keine Instanz ein Gegenbeispiel sein kann.

Hinweis

Suche für die Form (b) eine wahre Implikation zwischen Eigenschaften von Zahlen, etwa „wenn $n$ ein Vielfaches von $4$ ist, ist es gerade“, und eine Zahl, die die erste Eigenschaft nicht hat, wohl aber die zweite. Für die Form (a) nimm an, dass die Prämissen wahr sind, und frage dich, was geschähe, wenn $p$ wahr wäre.

Lösung

Die Form (a), modus tollens genannt, ist gültig: Sind die Prämissen wahr und wäre $p$ wahr, so wäre auch $q$ wahr, gegen die zweite Prämisse. Die Form (b), die Verneinung des Antezedens, ist ungültig: „wenn $6$ ein Vielfaches von $4$ ist, ist $6$ gerade; $6$ ist kein Vielfaches von $4$ ; also ist $6$ nicht gerade“ hat wahre Prämissen und eine falsche Konklusion.

Übungsaufgabe 2Reisepass, Ausweis und Visum

Ein Aushang besagt: „für die Einreise sind ein Reisepass oder ein Personalausweis und ein Visum erforderlich“. Man schreibe seine beiden Lesarten mit den Buchstaben $p$ (Reisepass), $d$ (Personalausweis) und $v$ (Visum) und beschreibe eine reisende Person, die die eine Lesart einreisen lässt und die andere nicht.

Hinweis

Die Frage ist, ob das Visum nur zum Personalausweis gehört oder zu jedem der beiden Dokumente. Versuche es mit einer reisenden Person, die nur ein einziges Dokument hat.

Lösung

Die Lesarten sind $p \vee (d \wedge v)$ und $(p \vee d) \wedge v$ . Eine reisende Person mit Reisepass und ohne Visum darf nach der ersten einreisen und nach der zweiten nicht.

Übungsaufgabe 3Anführungszeichen

Man entscheide, ob jeder Satz über die Stadt oder über das Wort spricht und ob er wahr oder falsch ist: (a) „Rom hat drei Buchstaben“; (b) „‚Rom‘ hat drei Buchstaben“; (c) „‚Rom‘ ist die Hauptstadt Italiens“; (d) „der Satz ‚Rom ist die Hauptstadt Italiens‘ enthält das Wort ‚Rom‘“.

Hinweis

Anführungszeichen machen aus einem Ausdruck den Namen dieses Ausdrucks. Frage dich in jedem Fall, welchen Gegenstand das Subjekt des Satzes bezeichnet: eine Stadt, ein Wort oder einen Satz.

Lösung

(a) Er spricht über die Stadt und ist falsch, denn eine Stadt hat keine Buchstaben. (b) Er spricht über das Wort und ist wahr. (c) Er spricht über das Wort und ist falsch, denn ein Wort ist keine Hauptstadt. (d) Er spricht über einen Satz und über ein Wort und ist wahr.

Übungsaufgabe 4Die beiden Seiten einer Karte

Auf der einen Seite einer Karte steht der Satz $A$ : „der Satz $B$ ist wahr“; auf der anderen Seite der Satz $B$ : „der Satz $A$ ist falsch“. Man beweise unter Annahme der Zweiwertigkeit und des Wahrheitsschemas, dass es keine Möglichkeit gibt, $A$ und $B$ Wahrheitswerte zuzuordnen. Was geschieht, wenn $B$ stattdessen sagt: „der Satz $A$ ist wahr“?

Hinweis

Schreibe das Wahrheitsschema für jeden Satz auf und verkette die Äquivalenzen, bis du eine erhältst, die $V(A)$ mit sich selbst verbindet. Mache in der Variante dasselbe und prüfe, welche Zuordnungen sie erfüllen.

Lösung

In der ersten Fassung erhält man $V(A) \Leftrightarrow \neg V(A)$ , wie beim Lügner, ohne dass ein Satz über sich selbst spricht. In der Variante lässt $V(A) \Leftrightarrow V(B)$ zwei Zuordnungen zu, beide wahr oder beide falsch: Es gibt keinen Widerspruch, aber nichts entscheidet zwischen ihnen.

Ausführliche Lösung

Lösung

$\dato{A}{V(A) \Leftrightarrow V(B)}$
Nach dem Wahrheitsschema ist $A$ genau dann wahr, wenn $B$ es ist.
$\dato{B}{V(B) \Leftrightarrow F(A) \Leftrightarrow \neg V(A)}$
Nach dem Wahrheitsschema ist $B$ genau dann wahr, wenn $A$ falsch ist; nach der Zweiwertigkeit heißt falsch sein nicht wahr sein.
$V(A) \Leftrightarrow \resaltar{\neg V(A)}$
Verkettet man beide Äquivalenzen, so ist die Wahrheit von $A$ äquivalent zu ihrer eigenen Verneinung, und man schließt wie beim Lügner: Ist $A$ wahr, so ist er es nicht, und ist er es nicht, so ist er es.
$V(A) \Leftrightarrow V(B) \Leftrightarrow V(A)$
In der Variante ergibt das Wahrheitsschema für $B$ die Äquivalenz $V(B) \Leftrightarrow V(A)$ , die zusammen mit der ersten nur verlangt, dass beide denselben Wert haben: Es gibt zwei stimmige Zuordnungen und keinen Widerspruch.

Übungsaufgabe 5Cantors Diagonale

Sei $s_1, s_2, s_3, \ldots$ eine beliebige Liste unendlicher Folgen aus Nullen und Einsen, und schreiben wir $s_x(y)$ für das $y$ -te Glied der Folge $s_x$ . Man beweise mit dem Diagonallemma, dass die Folge $d$ , definiert durch $d(y) = 1$ , wenn $s_y(y) = 0$ , und $d(y) = 0$ , wenn $s_y(y) = 1$ , nicht in der Liste vorkommt. Man folgere, dass keine nummerierte Liste alle Folgen aus Nullen und Einsen enthält.

Hinweis

Nimm als Gesamtheit $D$ die natürlichen Zahlen und als Beziehung $R(x, y)$ die Behauptung $s_x(y) = 1$ . Welche Bedingung erfüllte eine Zahl $b$ mit $s_b = d$ ?

Lösung

Wäre $d = s_b$ , so erfüllte die Zahl $b$ die Äquivalenz $R(b, y) \Leftrightarrow \neg R(y, y)$ für jedes $y$ , was das Diagonallemma verbietet. Also unterscheidet sich $d$ von jedem $s_b$ mindestens im $b$ -ten Glied, und keine Liste enthält alle Folgen.

Ausführliche Lösung

Lösung

$\dato{R}{R(x, y) \Leftrightarrow s_x(y) = 1}$
Sei $D$ die Menge der natürlichen Zahlen und $R(x, y)$ die Behauptung, dass das $y$ -te Glied von $s_x$ gleich $1$ ist.
$\dato{d}{d(y) = 1 \Leftrightarrow \neg\left( s_y(y) = 1 \right)}$
Nach ihrer Definition ist $d(y)$ genau dann gleich $1$ , wenn $s_y(y)$ nicht gleich $1$ ist.
$(\forall y \in D)\,\left( R(\resaltar{b}, y) \Leftrightarrow \neg R(y, y) \right)$
Nehmen wir an, $d$ komme in der Liste an der Stelle $b$ vor, das heißt $d = s_b$ . Dann ist für jedes $y$ die Behauptung $R(b, y)$ äquivalent zu $d(y) = 1$ , und dies ist äquivalent zu $\neg R(y, y)$ .
$d(b) \neq s_b(b)$
Nach dem Diagonallemma erfüllt kein $b$ diese Bedingung: Die Folge $d$ kommt in der Liste nicht vor. Genauer unterscheidet sie sich von $s_b$ im $b$ -ten Glied.
$(\forall b \in \mathbb{N})\,(d \neq s_b)$
Da die Liste beliebig war, enthält keine nummerierte Liste alle Folgen aus Nullen und Einsen: Jeder Liste fehlt mindestens ihre Diagonalfolge.