Sprache: Einführung

Eingangstest

Bevor man die Einheit durcharbeitet, lohnt es sich, den Ausgangspunkt zu bestimmen. Dieser Test ist eine Selbstüberprüfung: Er wird nicht benotet, und sein einziger Zweck ist es, das Lernen zu leiten. Seine elf Fragen behandeln der Reihe nach die vier Lektionen der Einheit: drei die erste, drei die zweite, zwei die dritte und drei die vierte. Wer nie Logik studiert hat, sollte nicht erwarten, alle richtig zu beantworten, und das macht nichts: Jede Antwort, ob richtig oder falsch, erklärt den Punkt und nennt die Lektion, die ihn behandelt. Dieselben Fertigkeiten werden am Ende, in der Lektion der Zusammenfassung, erneut gemessen; da dies die erste Einheit eines Kurses ohne Zugangsvoraussetzungen ist, gibt es keine Fragen zu früheren Einheiten.

Die Inhalte der Einheit

Diese Einheit dient vor allem dem ersten der Ziele des Kurses, die Objektsprache von der Metasprache zu unterscheiden und mit den Bildungsregeln zu entscheiden, ob eine Zeichenkette eine Formel ist; sie dient auch dem zweiten, Aussagen und Argumente der natürlichen Sprache zu formalisieren, und sie bereitet das vierte vor, Metatheoreme durch Induktion zu beweisen, das den Kurs bis zu seiner letzten Einheit begleiten wird. Ihr Ziel ist, dass wer sie abschließt, weiß, was die Logik untersucht, über eine mit aller Strenge aufgebaute formale Sprache verfügt, Eigenschaften aller ihrer Formeln beweisen kann und deutsche Aussagen und Argumente in sie übersetzen kann, im Wissen darum, was die Übersetzung bewahrt und was sie verliert. Ihre vier Lektionen bilden eine Kette, in der jede sich auf die vorigen stützt.

1. Was ist mathematische Logik. Sie grenzt den Gegenstand der Disziplin ab: nicht die Wahrheit der einzelnen Aussagen, sondern die Gültigkeit, die Beziehung zwischen Prämissen und Konklusion, die garantiert, dass die Wahrheit jener auf diese übergeht. Sie unterscheidet die Gültigkeit von der Wahrheit, zeigt, warum die natürliche Sprache, mehrdeutig und fähig, über sich selbst zu sprechen, nicht genügt, um sie zu untersuchen, und führt die Unterscheidung zwischen Objektsprache und Metasprache ein. Sie analysiert mit ausdrücklich gemachten Annahmen die Paradoxien des Lügners, von Berry, des Barbiers und von Russell und endet mit der Karte des Kurses.
2. Die Sprache der Aussagenlogik. Sie lehrt das Unentbehrliche über Mengen und Zeichenketten, zählt die Zeichenketten, die sich mit zwei Zeichen schreiben lassen, und baut die Grundsprache auf: unendlich viele Variablen, mit Kreisen und Scheiben geschrieben, eine einzige Bildungsregel und eine Abschlussklausel, aus der sich ein Prinzip zum Beweis von Eigenschaften aller Formeln ergibt. Sie gibt ein Verfahren an, um zu entscheiden, ob eine Zeichenkette eine Formel ist, und baut auf der Grundsprache die Metasprache auf, mit der von nun an gearbeitet wird: Metavariablen, den mit Klammern geschriebenen Peirce-Pfeil und die offiziellen Abkürzungen der übrigen Junktoren.
3. Die Induktion über die natürlichen Zahlen und über Formeln. Sie lehrt die vollständige Induktion über die natürlichen Zahlen, die einfache und die starke, und überträgt sie auf die Formeln. Mit ihr beweist sie das Gewichtslemma und daraus den Satz von der eindeutigen Lesbarkeit, den die vorige Lektion formuliert hatte: Jede zusammengesetzte Formel zerfällt auf nur eine Weise. Die eindeutige Lesbarkeit rechtfertigt schließlich die rekursiven Definitionen über Formeln (Länge, Teilformeln, Tiefe) und die Substitution einer Teilformel durch eine andere.
4. Die Formalisierung der natürlichen Sprache. Sie schlägt die Brücke zwischen dem Deutschen und der formalen Sprache: das Wörterbuch einer Formalisierung, die Lesart jedes Junktors, abgeleitet aus der des primitiven Junktors, die Feinheiten von „aber“, „nur dann, wenn“ und „es sei denn“, der Wirkungsbereich der Junktoren, die materiale Implikation und das, was die Aussagenlogik nicht ausdrücken kann. Sie endet damit, vollständige Argumente als eine Prämissenmenge und eine Konklusion zu formalisieren, die die folgenden Einheiten der Deduktion und der Semantik unterwerfen werden.

Die Einheit endet mit der Lektion Zusammenfassung und Herausforderungen, die das Erreichte in einer deduktiven Kette zusammenführt, in ihrem Abschlusstest die Fertigkeiten des Eingangstests wiederholt und Herausforderungen stellt, die mehrere Lektionen verbinden.

Der Ort der Einheit im Kurs

Der Kurs durchläuft für die einfachste Sprache der Logik den vollständigen Weg einer logischen Theorie, und zwar in vier Teilen, die seine vier inhaltlichen Einheiten sind. Die erste, diese, legt die Sprache fest. Die zweite, die Deduktion, definiert, was es heißt, dass eine Formel $\varphi$ aus einer Formelmenge $\Gamma$ mittels Axiomen und Schlussregeln gewonnen wird, was man $\Gamma \vdash \varphi$ schreiben wird; sie ist die syntaktische Seite der Gültigkeit, auf der Zeichen bearbeitet werden, ohne auf ihre Bedeutung zu achten. Die dritte, die Semantik, ordnet jeder Formel unter jeder Belegung einen Wahrheitswert zu und definiert, was es heißt, dass $\varphi$ aus $\Gamma$ folgt, was man $\Gamma \models \varphi$ schreiben wird; sie ist die semantische Seite der Gültigkeit. Die vierte, die Metatheorie, beweist, dass beide Seiten übereinstimmen: Die Korrektheit besagt, dass alles Ableitbare folgt, und die Vollständigkeit, dass jede Folgerung ableitbar ist.

Wenn dem so ist, ist die Syntax keine Vorrede, die sich abkürzen ließe, sondern die Bedingung der anderen drei Teile. Eine Ableitung ist eine Folge von Formeln, und um zu entscheiden, ob eine Folge eine solche ist, muss man ohne Zögern wissen, welche Zeichenketten Formeln sind und wie sie zerfallen; eine Belegung wird von den Variablen durch Rekursion auf alle Formeln fortgesetzt, und die Rekursion gibt jeder Formel nur dann einen einzigen Wert, wenn jede Formel sich nur auf eine Weise lesen lässt; die Sätze der Metatheorie werden durch Induktion bewiesen, über die Komplexität der Formeln oder über die Länge der Ableitungen. Daraus folgt die Ordnung der Einheit: zuerst, was man untersuchen will und warum eine formale Sprache nötig ist; dann die Sprache; danach das Werkzeug, um etwas über alle ihre Formeln zu beweisen, mit dem die eindeutige Lesbarkeit bewiesen wird; und schließlich die Brücke zu den Argumenten des Deutschen, die der Grund für alles Vorangehende sind.

Warum eine Sprache der Kreise und Scheiben

Die Sprache des Kurses hat ein Alphabet aus nur zwei Zeichen, dem Kreis $\sigO$ und der Scheibe $\sigI$, und eine einzige Bildungsregel: Wenn $\varphi$ und $\psi$ Formeln sind, so ist es auch $\sigI\varphi\psi$. Die $n$-te Variable ist die Zeichenkette aus $n$ Kreisen, gefolgt von einer Scheibe, $v_{n} = \sigO^{n}\sigI$. Auf den ersten Blick ist die Wahl seltsam, denn so geschriebene Formeln sind schwer zu lesen. Sie hat jedoch vier genaue Gründe.

Der erste ist, dass zwei Zeichen genügen, um unendlich viele Variablen zu schreiben, ohne ein endliches Alphabet zu verlassen, sodass jede Formel buchstäblich eine endliche Zeichenkette über einer zweielementigen Menge ist und die Fragen über die Sprache Fragen über Zeichenketten sind, die man zählen und vergleichen kann. Der zweite ist, dass eine einzige Regel in jedem Induktionsbeweis einen einzigen Fall lässt: Was für die Variablen und für $\sigI\varphi\psi$ bewiesen ist, ist für alle Formeln bewiesen, ohne einen Fall je Junktor. Der dritte ist, dass die Regel den Junktor vor seine beiden Argumente stellt, wie in der Notation, die Jan Łukasiewicz in den 1920er Jahren vorschlug, und deshalb keine Klammern braucht: Die eindeutige Lesbarkeit wird mit einem Argument von einer Seite bewiesen, das jeder Variablen das Gewicht $+1$ und jeder Junktorscheibe das Gewicht $-1$ zuweist. Der vierte ist, dass der einzige Junktor, der Peirce-Pfeil, „weder $\varphi$ noch $\psi$“, genügt, um alle anderen auszudrücken, wie Charles Sanders Peirce um 1880 bemerkte und Henry Sheffer 1913 veröffentlichte und wie die Einheit über die Semantik beweisen wird; die Sparsamkeit der Sprache opfert also nichts von dem, was die Aussagenlogik sagen kann.

Nun ist der Preis dieser Sparsamkeit die Lesbarkeit, und die Einheit bezahlt ihn in der Metasprache: Niemand wird im Alltag Ketten aus Kreisen und Scheiben schreiben, sondern ihre Namen, $(\varphi \downarrow \psi)$, $\neg\varphi$, $(\varphi \rightarrow \psi)$, die nur einmal definiert sind und sich jederzeit bis zu der Zeichenkette auflösen lassen, die sie bezeichnen. Daher arbeitet der Kurs auf zwei Ebenen zugleich: mit einer minimalen Grundsprache, über die bewiesen wird, und mit einer bequemen Notation, in der geschrieben wird; und die Unterscheidung zwischen Objektsprache und Metasprache, die die erste Lektion einführt, ist es, die erlaubt, beide nicht zu verwechseln.

Was vorausgesetzt wird

Die Einheit geht von fast nichts aus. Sie setzt nicht voraus, dass man Logik studiert hat, die Mengenlehre kennt oder je einen Satz bewiesen hat: Was sie von den Mengen verwendet, lehrt die zweite Lektion, und was sie von der Induktion verwendet, die dritte. Sie setzt nur zwei Dinge voraus. Erstens aufmerksames Lesen: In einer formalen Sprache verändert ein hinzugefügtes oder weggelassenes Zeichen die Zeichenkette, und die Reihenfolge der Wörter einer Definition zählt ebenso viel wie die Wörter selbst. Zweitens die elementare Arithmetik der natürlichen Zahlen, die in diesem Kurs $1, 2, 3, \ldots$ sind: addieren und multiplizieren, Potenzen von $2$ berechnen, gerade von ungeraden Zahlen unterscheiden und eine Primzahl erkennen.

Wer eine zusätzliche Stütze für die Induktion wünscht, kann die Lektionen über die Peano-Axiome und über Summen und Induktion aus dem Kurs Algebra und Geometrie I heranziehen; nötig ist es nicht, denn die dritte Lektion dieser Einheit lehrt die Induktion von ihrer Formulierung an.

Das Problem, das die Einheit löst

Die Logik untersucht die Gültigkeit, und die Gültigkeit hängt von der Form der Argumente ab. Um aber streng über die Form zu sprechen, muss jeder Ausdruck eine einzige Form haben, und die natürliche Sprache garantiert das nicht: „das Doppelte von drei plus vier“ kann $10$ oder $14$ sein, je nachdem, wie man gruppiert. Das stellt zwei Probleme, die die der Einheit sind. Das erste ist, eine Sprache aufzubauen, in der sich jeder Ausdruck nur auf eine Weise lesen lässt. Das zweite ist, dies zu beweisen: Die Formeln sind unendlich viele, und keine Prüfung Fall für Fall, wie lang sie auch sei, stellt fest, dass sich alle nur auf eine Weise lesen lassen. Das folgende Beispiel zeigt beide Probleme an einem einzigen Ausdruck.

Die Antwort der Einheit auf diese beiden Probleme hat also zwei Teile. Für das erste eine Sprache, deren einzige Regel den Junktor voranstellt, sodass Klammern überflüssig sind, und eine Metasprache, deren Abkürzungen jeweils eine einzige Zeichenkette bezeichnen. Für das zweite ein Beweisprinzip, die Induktion über die Komplexität der Formeln, das von endlich vielen Prüfungen (den Variablen und der Regel) zu allen Formeln übergeht, so wie die Induktion über die natürlichen Zahlen von der $1$ und vom Schritt von $k$ zu $k + 1$ zu allen Zahlen übergeht. Mit beiden Teilen wird die Form eines Arguments zu einem genauen Gegenstand, und die Frage nach seiner Gültigkeit kann in den folgenden Einheiten streng gestellt werden.

Wie man die Einheit studiert

Es empfiehlt sich, mit diesem Eingangstest zu beginnen und die falsch beantworteten Fragen zu notieren, die die Lektionen anzeigen, bei denen man verweilen muss. Die vier Lektionen sind der Reihe nach zu studieren, denn jede verwendet, was die vorigen feststellen. In der zweiten und der dritten verlangt das Studium Papier und Bleistift: Ketten aus Kreisen und Scheiben lesen sich auf dem Bildschirm schlecht, und es empfiehlt sich, sie abzuschreiben, ihre Wörter zu trennen (jede Variable und jede einzelne Scheibe) und das Gewicht jedes Wortes zu notieren, bis die Zählung der eindeutigen Lesbarkeit zur Gewohnheit wird. Die Beweise werden als Schritt-für-Schritt-Abfolgen zum Abspielen veröffentlicht, und jeder Schritt sollte sich begründen lassen, bevor man weitergeht. In der ersten und der vierten ist die Arbeit aufmerksames Lesen: sich bei jedem deutschen Satz fragen, was er genau behauptet, welche Lesarten er zulässt und welche Formel ihn darstellt. Schließlich öffnet man den Hinweis und die Antwort jeder Übungsaufgabe erst, nachdem man sie ernsthaft versucht hat.

Wohin sie führt

Am Ende der Einheit wird die Sprache festgelegt sein, und die folgenden Einheiten werden auf ihr aufbauen, ohne sie erneut zu erörtern. Die Einheit über die Deduktion wird ein System von Axiomen und zwei Schlussregeln definieren, den Modus ponens und, sobald die doppelte Negation bewiesen ist, die Ersetzung der doppelten Negation, dessen Ableitungen Folgen von Formeln sind; seine Axiome werden mit den offiziellen Abkürzungen geschrieben, die diese Einheit definiert, und sein Deduktionstheorem wird durch Induktion über die Länge der Ableitungen bewiesen, mit dem Werkzeug, das man hier erlernt. Ihre erste Lektion ist die über formale Deduktionssysteme. Die Einheit über die Semantik wird den Variablen Wahrheitswerte zuordnen und sie durch Rekursion auf alle Formeln fortsetzen, was nur dank der eindeutigen Lesbarkeit möglich ist; sie wird mit Tafeln die informellen Lesarten der Junktoren begründen, die die vierte Lektion verwendet, und in der Lektion über die funktionale Vollständigkeit beweisen, dass der Peirce-Pfeil genügt, um jeden Junktor auszudrücken. Die Einheit über die Metatheorie schließlich wird durch Induktion die Korrektheit und die Vollständigkeit beweisen, und die Argumente, die diese Einheit zu formalisieren lehrt, werden sich endlich gleichermaßen durch die Deduktion oder durch die Semantik entscheiden lassen.

Außerhalb dieses Kurses ist die Syntax einer formalen Sprache die jeder Programmiersprache: Ein Compiler, wie ihn Programmieren in C++ I behandelt, entscheidet zuerst, ob ein Programm wohlgeformt ist, und zerlegt es auf eine einzige Weise. Die Unterscheidung zwischen Gültigkeit und Wahrheit ist auch der Ausgangspunkt der Aristotelischen Logik, die die Form der Syllogismen untersucht; und die Induktion der dritten Lektion ist dieselbe, die in Algebra und Geometrie I die Eigenschaften der Zahlen beweist. In allen diesen Bereichen, wie bei der Abfassung von Vorschriften und Verträgen, ist die Lehre dieselbe: Genau zu sagen, was man behauptet, verlangt eine Sprache, in der jeder Ausdruck eine einzige Lesart hat.