Sprache: Zusammenfassung und Herausforderungen

Zusammenfassung

Diese Lektion schließt die Einheit über die Sprache der Aussagenlogik ab. Sie rekonstruiert die deduktive Kette, die von der Unterscheidung zwischen Gültigkeit und Wahrheit und von der Analyse der Paradoxien bis zur eindeutigen Lesbarkeit der Formeln und zur Formalisierung von Aussagen und Argumenten führt, und gibt bei jedem Glied an, welches Prinzip verwendet wird und in welcher Lektion es bewiesen wird; sie ordnet das Erreichte in den Plan des Kurses ein und erklärt, warum die bereits aufgebaute Sprache die Frage der nächsten Einheit aufwirft, die der Deduktion gewidmet ist. Ihr Abschlusstest wiederholt die Fertigkeiten des Eingangstests, und am Ende stehen sechs Herausforderungen, schwieriger als die Aufgaben der Lektionen, die verlangen, die Werkzeuge mehrerer von ihnen zu verbinden.

Lernziele

Die logische Ordnung der Ergebnisse der Einheit rekonstruieren und dabei für jedes das Prinzip angeben, auf dem es beruht, und die Lektion, in der es bewiesen wird.
Erklären, wie Abschlussprinzip, Zerlegung in Wörter, Gewichtslemma und eindeutige Lesbarkeit ineinandergreifen und warum die rekursiven Definitionen und der Vergleich von Formalisierungen von der letzten abhängen.
Unterscheiden, was die Einheit bewiesen hat, von dem, was sie als Annahme zugelassen hat (die Zweiwertigkeit, das Wahrheitsschema, das Induktionsprinzip und die Lesart des Peirce-Pfeils), und von dem, was sie den folgenden Einheiten überlassen hat.
Aufgaben lösen, die das Diagonallemma, das Zählen von Zeichenketten, die Induktion über Formeln, das Gewichtsargument und das Auflösen von Abkürzungen verbinden.

Was die Einheit erreicht hat

Die Einheit hatte sich vorgenommen, aus einem Alphabet von zwei Zeichen eine Sprache aufzubauen, in der jede Formel auf nur eine Weise gelesen wird, die Eigenschaften dieser Sprache streng zu beweisen und eine Brücke zwischen ihr und der Sprache zu schlagen, in der wir argumentieren. Das Vorhaben ist mit wenigen Vorbehalten erfüllt, deren jeder an seiner Stelle offengelegt wurde: die Zweiwertigkeit und das Wahrheitsschema, die die erste Lektion nicht als Wahrheiten, sondern als ausdrückliche Annahmen zuließ, um zu prüfen, was geschieht, wenn man sie zugleich aufrechterhält; das Prinzip der Induktion über die natürlichen Zahlen, das als fünftes Peano-Axiom angenommen wird; die informelle Lesart des Peirce-Pfeils, die festgesetzt wird und die die Einheit über die Semantik zu einer Definition machen wird; und das Unentbehrliche der Mengenlehre (Elementbeziehung, Inklusion und Vereinigung), das dort gelehrt wurde, wo es nötig war. Mit diesen Vorbehalten lässt sich der zurückgelegte Weg als eine einzige deduktive Kette in vier Abschnitten lesen.

Argumentieren und über die Sprache sprechen

Die Lektion darüber, was mathematische Logik ist, hat den Gegenstand des Kurses festgelegt: nicht die Wahrheit der Aussagen, die Sache jeder einzelnen Wissenschaft ist, sondern ihre Übertragung. Ein Argument ist gültig, wenn seine Form keine Instanz mit wahren Prämissen und falscher Konklusion zulässt, und aus dieser Definition wurde das Einzige hergeleitet, was die Gültigkeit garantiert: Sind die Prämissen wahr, so ist es auch die Konklusion; folglich hat ein gültiges Argument mit falscher Konklusion eine falsche Prämisse, und eine Form ist genau dann ungültig, wenn sie ein Gegenbeispiel hat. Dasselbe Ergebnis hat die Analyse der Paradoxien zu einem Verfahren gemacht: Sind die Schritte einer Überlegung, die in einem Widerspruch endet, gültig, so ist eine Annahme falsch, und das Paradoxon auflösen heißt herausfinden, welche. So wurde der Lügner behandelt, bei dem Zweiwertigkeit und Wahrheitsschema für einen Satz, der sich selbst für falsch erklärt, nicht zugleich aufrechterhalten werden können, und so wurden das Berry-Paradoxon und das Adjektiv „heterologisch“ behandelt. Aus dem Barbier wurde ein allgemeines Lemma gewonnen, das Diagonallemma, das beweist, dass es den Barbier nicht gibt und dass das uneingeschränkte Komprehensionsprinzip widersprüchlich ist. Zuletzt hat die Lektion die Unterscheidung zwischen Objektsprache und Metasprache sowie zwischen dem Gebrauch eines Ausdrucks und seiner Erwähnung eingeführt, die alles Weitere bestimmt: Die Ergebnisse der Einheit über Formeln sind keine Formeln, sondern Metatheoreme.

Die Sprache der Kreise und Scheiben

Die Lektion über die Sprache der Aussagenlogik hat Mengen und Zeichenketten eingeführt, die Zeichenketten jeder Länge gezählt (es gibt $2^{n}$ der Länge $n$ und $2^{N + 1} - 2$ der Längen $1$ bis $N$ ) und die Grundsprache aufgebaut: die Variablen $v_n = \sigO^{n}\sigI$ und eine einzige Regel, die aus zwei Formeln $\varphi$ und $\psi$ die Formel $\sigI\varphi\psi$ bildet. Die Klausel „nichts sonst ist eine Formel“ wurde präzisiert, indem die Formeln als die Zeichenketten definiert wurden, die zu allen abgeschlossenen Mengen gehören, und aus dieser Definition wurde das Abschlussprinzip hergeleitet, mit dem bewiesen wurde, dass jede Formel eine Variable ist oder $\sigI\varphi\psi$ ist, und nicht beides, dass jede Formel mit einer Scheibe endet und dass sie eine ungerade Anzahl von Scheiben enthält. Die Beobachtung, dass die Variablen und die einzelne Scheibe einen Präfixcode bilden, ergab die eindeutige Zerlegung in Wörter und mit ihr den Begriff des Gewichts. Die Lektion hat auch die Metasprache aufgebaut, mit der von da an gearbeitet wird: die Metavariablen, den als $(\varphi \downarrow \psi)$ geschriebenen Peirce-Pfeil und die sechs offiziellen Abkürzungen, jede nur einmal aus den vorigen definiert, sodass jeder abgekürzte Ausdruck eine einzige Zeichenkette bezeichnet.

Induktion und eindeutige Lesbarkeit

Die Lektion über die Induktion über die natürlichen Zahlen und über Formeln hat die Zählungen begründet, die die vorige Lektion mit „und so weiter“ abgeschlossen hatte, hat die starke Induktion aus der einfachen hergeleitet und, indem sie diese auf die Länge anwandte, die strukturelle Induktion gewonnen, die sich als dieselbe Induktion über die natürlichen Zahlen erweist, übertragen auf die Formeln. Mit diesem Werkzeug hat sie das Gewichtslemma bewiesen: Jede Formel wiegt $+1$ , und jedes echte, nichtleere Wortpräfix wiegt höchstens $0$ . Daraus folgt in dieser Reihenfolge, dass keine Formel echtes Präfix einer anderen ist und dass jede zusammengesetzte Formel auf eine einzige Weise gelesen wird. Die eindeutige Lesbarkeit ist das Glied, an dem der Rest der Einheit hängt: Sie rechtfertigt das Entscheidungsverfahren, das die Lektion über die Sprache als eine Schuld beschrieben hatte, die beglichen wird, und sie legitimiert die Definitionen durch Rekursion (die Länge, die Anzahl der Variablen und der Junktorscheiben, die Teilformeln, die Tiefe und die Substitution), die ohne sie einer Formel zwei verschiedene Werte zuordnen könnten.

Vom Deutschen zu den Formeln

Die Lektion über die Formalisierung der natürlichen Sprache hat die Brücke zur Sprache geschlagen. Sie hat die Konvention festgelegt, die Buchstaben $p$ , $q$ , $r$ , $s$ und $t$ als Namen von fünf bestimmten Variablen zu verwenden, hat verlangt, dass jede Formalisierung ihr Wörterbuch angibt, und allein aus der festgesetzten Lesart des Peirce-Pfeils die Lesart jeder Abkürzung hergeleitet. Mit der eindeutigen Lesbarkeit hat sie bewiesen, dass zwei verschiedene Klammerungen derselben Junktoren verschiedene Formeln sind, und mit der rekursiven Definition der Länge hat sie berechnet, wie lang die aufgelösten Abkürzungen sind, was ein schnelles Kriterium liefert, um Formalisierungen zu unterscheiden. Sie hat gezeigt, dass die materiale Implikation nur dann falsch ist, wenn das Antezedens wahr und das Konsequens falsch ist, und dass dies die einzige Lesart ist, die nur von der Wahrheit der Teile abhängt und die bedingten Sätze der Mathematik wahr macht; sie hat angegeben, was die Formalisierung verliert (Quantoren, Zeit, Kausalität, Modalität), und zum Schluss vollständige Argumente als eine Prämissenmenge $\Gamma$ und eine Konklusion formalisiert.

Die folgende Abbildung fasst die vier Abschnitte zu einer einzigen Kette zusammen. Jeder Knoten der Säule ist eine Definition oder ein Ergebnis, nummeriert nach der logischen Ordnung und durch einen Bogen mit den früheren Gliedern verbunden, die sein Beweis verwendet; ringsum schweben die Stützen, also die Prinzipien, auf die die Kette immer wieder zurückgreift, jede durch einen durchgezogenen Strich mit den Gliedern verbunden, die sich auf sie stützen, und durch einen gepunkteten mit dem Glied, in dem sie begründet wird, außer denen, die ohne Beweis angenommen werden und als Ringe gezeichnet sind. Ein Klick auf eine Stütze hebt alle Glieder hervor, die sie verwenden, und jedes Glied verweist auf die Lektion, in der es bewiesen wird. Man beachte, dass das Entscheidungsverfahren, obwohl es in der Lektion über die Sprache dargestellt wird, seinen logischen Platz nach der eindeutigen Lesbarkeit hat, auf die es sich stützt.

Stützen der Kette

AZweiwertigkeit. Jede Aussage ist wahr oder falsch, und nicht beides; falsch zu sein ist gleichbedeutend damit, nicht wahr zu sein. Sie wird bei der Analyse der Paradoxien als ausdrückliche Annahme zugelassen. In dieser Einheit ohne Beweis angenommen.
BWahrheitsschema. Ein Satz ist genau dann wahr, wenn das, was er sagt, der Fall ist. Es wird als ausdrückliche Annahme zugelassen; Tarskis Lösung behält es bei, aber nur für die Sätze einer Sprache, die ihr eigenes Wahrheitsprädikat nicht enthält. In dieser Einheit ohne Beweis angenommen.
CInduktionsprinzip. Gilt eine Eigenschaft für $1$ und, jedes Mal wenn sie für eine natürliche Zahl $k$ gilt, auch für $k + 1$ , so gilt sie für alle natürlichen Zahlen. Es ist das fünfte Peano-Axiom und wird angenommen. In dieser Einheit ohne Beweis angenommen.
DDiagonallemma. Kein Objekt $b$ einer Gesamtheit erfüllt $R(b, x) \Leftrightarrow \neg R(x, x)$ für jedes $x$ der Gesamtheit. Begründet in: 3. Diagonallemma.
EAbschlussprinzip. Eine Eigenschaft, die alle Variablen haben und die von $\varphi$ und $\psi$ auf $\sigI\varphi\psi$ übergeht, haben alle Formeln. Begründet in: 5. Abschlussprinzip.
FStrukturelle Induktion. Die Induktion über die Komplexität der Formeln, hergeleitet aus der starken Induktion über die Länge: Ihr Induktionsanfang sind die Variablen, ihr Induktionsschritt ist die einzige Bildungsregel. Begründet in: 9. Strukturelle Induktion.
GEindeutige Lesbarkeit. Ist $\sigI\varphi\psi = \sigI\varphi'\psi'$ , wobei die vier Zeichenketten Formeln sind, so gilt $\varphi = \varphi'$ und $\psi = \psi'$ . Begründet in: 11. Eindeutige Lesbarkeit.
HLesart des Peirce-Pfeils. Die Formel $(\varphi \downarrow \psi)$ ist genau dann wahr, wenn $\varphi$ und $\psi$ beide falsch sind. Es ist die einzige Lesart, die festgesetzt wird; die übrigen werden aus ihr hergeleitet, und die Einheit über die Semantik wird sie präzisieren. In dieser Einheit ohne Beweis angenommen.

Abschnitt 1 Argumentieren und über die Sprache sprechen
- Gültigkeit von Wahrheit unterscheiden und eine ungültige Form durch ein Gegenbeispiel widerlegen.
- Die Mehrdeutigkeiten der natürlichen Sprache erkennen und die Lesarten einer Aussage trennen.
- Die Objektsprache von der Metasprache unterscheiden und den Gebrauch eines Ausdrucks von seiner Erwähnung.
- Ein Paradoxon analysieren, indem man seine Annahmen isoliert und entscheidet, welche aufzugeben ist.
1. Was die Gültigkeit garantiert. Ist ein Argument gültig und sind alle seine Prämissen wahr, so ist seine Konklusion wahr; folglich hat ein gültiges Argument mit falscher Konklusion eine falsche Prämisse, und eine Form ist genau dann ungültig, wenn sie ein Gegenbeispiel hat.
  Bewiesen in: Was ist mathematische Logik.
2. Das Lügner-Paradoxon. Auf den Satz $m$ , „der Satz $m$ ist falsch“, angewandt, ergeben Zweiwertigkeit und Wahrheitsschema $V(m) \Leftrightarrow \neg V(m)$ ; für eine Sprache, die $m$ enthält, muss eine der beiden Annahmen aufgegeben werden, und Tarskis Ausweg ist, dass keine Sprache ihr eigenes Wahrheitsprädikat enthält, sodass $m$ nicht gebildet werden kann.
  Verwendet: 1. Was die Gültigkeit garantiert. Stützt sich auf: A (Zweiwertigkeit), B (Wahrheitsschema). Bewiesen in: Was ist mathematische Logik.
3. Diagonallemma. Ist $R$ eine Beziehung zwischen den Objekten einer Gesamtheit $D$ , sodass jedes $R(x, y)$ wahr oder falsch ist, so erfüllt kein $b$ aus $D$ die Bedingung $R(b, x) \Leftrightarrow \neg R(x, x)$ für jedes $x$ aus $D$ .
  Stützt sich auf: A (Zweiwertigkeit). Bewiesen in: Was ist mathematische Logik.
4. Der Barbier und Russell. Es gibt keinen Mann des Dorfes, der genau die Männer des Dorfes rasiert, die sich nicht selbst rasieren; und das uneingeschränkte Komprehensionsprinzip ist widersprüchlich, weil es die Existenz der Menge $Z = \{ x : x \notin x \}$ behauptet.
  Stützt sich auf: D (Diagonallemma). Bewiesen in: Was ist mathematische Logik.
Abschnitt 2 Die Sprache der Kreise und Scheiben
- Mengen von Zeichenketten beschreiben und die Zeichenketten jeder Länge zählen.
- Die Formeln als die kleinste abgeschlossene Menge definieren und daraus das Abschlussprinzip herleiten.
- Eigenschaften aller Formeln beweisen und mit ihnen Zeichenketten ausschließen.
- Eine Zeichenkette in Wörter zerlegen und die Abkürzungen bis zur Grundsprache auflösen.
1. Abschlussprinzip. Die Menge $\mathcal{F}$ der Formeln ist die kleinste Menge von Zeichenketten, die die Variablen $v_n = \sigO^{n}\sigI$ enthält und die mit $\varphi$ und $\psi$ auch $\sigI\varphi\psi$ enthält; daher haben alle Formeln eine Eigenschaft, die die Variablen haben und die von $\varphi$ und $\psi$ auf $\sigI\varphi\psi$ übergeht.
  Bewiesen in: Die Sprache der Aussagenlogik.
2. Form der Formeln. Jede Formel ist eine Variable oder ist $\sigI\varphi\psi$ mit Formeln $\varphi$ und $\psi$ , und nicht beides: Jede Variable beginnt mit $\sigO$ , und jede zusammengesetzte Formel mit $\sigI$ .
  Stützt sich auf: E (Abschlussprinzip). Bewiesen in: Die Sprache der Aussagenlogik.
3. Letztes Zeichen und Anzahl der Scheiben. Jede Formel endet mit einer Scheibe und enthält eine ungerade Anzahl von Scheiben; folglich sind weder die Verkettung zweier Formeln noch die Zeichenkette $\sigI\varphi$ Formeln.
  Stützt sich auf: E (Abschlussprinzip). Bewiesen in: Die Sprache der Aussagenlogik.
4. Zerlegung in Wörter. Jede Zeichenkette, die mit einer Scheibe endet, zerfällt auf eine einzige Weise in Wörter, das heißt in Variablen $\sigO^{n}\sigI$ und einzelne Scheiben, weil jedes Wort mit seiner einzigen Scheibe endet und keines echtes Präfix eines anderen ist.
  Bewiesen in: Die Sprache der Aussagenlogik.
Abschnitt 3 Induktion und eindeutige Lesbarkeit
- Durch einfache und starke Induktion beweisen und aus ihnen die Induktion über die Komplexität der Formeln herleiten.
- Das Gewichtslemma beweisen und die eindeutige Lesbarkeit herleiten.
- Entscheiden, ob eine Zeichenkette eine Formel ist, und ihre Bildung rekonstruieren.
- Funktionen auf den Formeln durch Rekursion definieren und Beziehungen zwischen ihnen beweisen.
1. Strukturelle Induktion. Die starke Induktion folgt aus der einfachen; auf die Länge angewandt, ergibt sie das Prinzip der Induktion über die Komplexität: Haben die Variablen eine Eigenschaft und geht diese von $\varphi$ und $\psi$ auf $\sigI\varphi\psi$ über, so haben sie alle Formeln.
  Verwendet: 6. Form der Formeln. Stützt sich auf: C (Induktionsprinzip). Bewiesen in: Induktion über die natürlichen Zahlen und über Formeln.
2. Gewichtslemma. Wiegt jedes Vorkommen einer Variablen $+1$ und jede Junktorscheibe $-1$ , so wiegt jede Formel $+1$ , und jedes echte, nichtleere Wortpräfix einer Formel wiegt höchstens $0$ ; insbesondere hat jede Formel ein Vorkommen von Variablen mehr als Junktorscheiben.
  Verwendet: 8. Zerlegung in Wörter. Stützt sich auf: F (Strukturelle Induktion). Bewiesen in: Induktion über die natürlichen Zahlen und über Formeln.
3. Eindeutige Lesbarkeit. Keine Formel ist echtes Präfix einer anderen; folglich gilt, wenn $\sigI\varphi\psi = \sigI\varphi'\psi'$ ist und die vier Zeichenketten Formeln sind, $\varphi = \varphi'$ und $\psi = \psi'$ .
  Verwendet: 7. Letztes Zeichen und Anzahl der Scheiben, 8. Zerlegung in Wörter, 10. Gewichtslemma. Bewiesen in: Induktion über die natürlichen Zahlen und über Formeln.
4. Entscheidungsverfahren. Eine Zeichenkette, die mit $\sigO$ endet, ist keine Formel; endet sie mit $\sigI$ , so zerlegt man sie in Wörter. Ist das erste Wort eine Variable, so ist die Zeichenkette genau dann eine Formel, wenn diese Variable ihr einziges Wort ist. Ist es eine Scheibe, so führt man danach die Schuld: Wird sie nie null, so ist die Zeichenkette keine Formel; wird sie null, so liegt der Schnitt zwischen $\varphi$ und $\psi$ dort, wo sie zum ersten Mal null wird, und jedes Stück wird auf dieselbe Weise geprüft, wobei die leere Zeichenkette keine Formel ist.
  Verwendet: 6. Form der Formeln, 7. Letztes Zeichen und Anzahl der Scheiben, 8. Zerlegung in Wörter. Stützt sich auf: G (Eindeutige Lesbarkeit). Bewiesen in: Die Sprache der Aussagenlogik.
5. Definition durch Rekursion. Sind ein Wert für jede Variable und eine Regel gegeben, die den Wert von $\sigI\varphi\psi$ aus $\varphi$ , aus $\psi$ und aus deren Werten berechnet, so gibt es genau eine Funktion auf den Formeln, die sie einhält; so werden die Länge, die Teilformeln, die Tiefe und die Substitution definiert, die stets Formeln erzeugt.
  Verwendet: 6. Form der Formeln. Stützt sich auf: C (Induktionsprinzip), F (Strukturelle Induktion), G (Eindeutige Lesbarkeit). Bewiesen in: Induktion über die natürlichen Zahlen und über Formeln.
Abschnitt 4 Vom Deutschen zu den Formeln
- Aussagen mit einem ausdrücklichen Wörterbuch formalisieren und dabei den Wirkungsbereich jedes Junktors festlegen.
- Abkürzungen auflösen, um zu entscheiden, ob zwei Formalisierungen dieselbe Formel sind.
- Die materiale Implikation vom „wenn … dann“ der Alltagssprache unterscheiden und angeben, was die Formalisierung verliert.
- Vollständige Argumente als eine Prämissenmenge und eine Konklusion formalisieren.
1. Länge der Abkürzungen. Ist $L(\varphi) = a$ und $L(\psi) = b$ , so haben die Zeichenketten von $\neg\varphi$ , $(\varphi \vee \psi)$ , $(\varphi \rightarrow \psi)$ und $(\varphi \wedge \psi)$ die Längen $2a + 1$ , $2a + 2b + 3$ , $4a + 2b + 5$ und $8a + 8b + 15$ ; zwei Formalisierungen verschiedener Länge sind verschiedene Formeln.
  Verwendet: 13. Definition durch Rekursion. Bewiesen in: Formalisierung der natürlichen Sprache.
2. Wirkungsbereich und verschiedene Formeln. Die Klammerungen $((p \wedge q) \vee r)$ und $(p \wedge (q \vee r))$ sind verschiedene Zeichenketten: Fielen sie zusammen, so zwänge die zweimal angewandte eindeutige Lesbarkeit die Variable $r$ , mit der zusammengesetzten Formel $(p \wedge q)$ übereinzustimmen.
  Verwendet: 6. Form der Formeln. Stützt sich auf: G (Eindeutige Lesbarkeit). Bewiesen in: Formalisierung der natürlichen Sprache.
3. Materiale Implikation. Die Implikation $(\varphi \rightarrow \psi)$ , die $(\neg\varphi \vee \psi)$ abkürzt, ist nur dann falsch, wenn $\varphi$ wahr und $\psi$ falsch ist; sie ist die einzige Lesart, die nur von der Wahrheit der Teile abhängt und die bedingten Sätze der Mathematik wahr macht.
  Stützt sich auf: H (Lesart des Peirce-Pfeils). Bewiesen in: Formalisierung der natürlichen Sprache.

Auf dem Weg zur Deduktion. Die Kette hält dort an, wo die Sprache aufgebaut ist und die Argumente als eine Prämissenmenge und eine Konklusion formalisiert sind. Zu entscheiden bleibt, wann eine Formel aus anderen folgt: zuerst, indem man Zeichen mit Regeln umformt, in der nächsten Einheit, und danach, indem man auf ihre Wahrheit achtet.