Zum Inhalt springen
Topos Uranos
Deutsch

Induktion über die natürlichen Zahlen und über Formeln

Zusammenfassung

Es gibt unendlich viele Formeln der Aussagenlogik, und jede Behauptung über sie alle verlangt eine Methode, die nicht darin besteht, sie einzeln zu prüfen. Diese Lektion baut sie in zwei Stufen auf. Die erste ist die vollständige Induktion über die natürlichen Zahlen, in ihrer einfachen und in ihrer starken Form, die aus der einfachen hergeleitet wird; die zweite ist die Induktion über die Komplexität der Formeln, auch strukturelle Induktion genannt, die durch starke Induktion über die Länge begründet wird. Mit ihr wird das Gewichtslemma der Sprache der Kreise und Scheiben bewiesen (jede Formel wiegt +1+1 und jedes echte, nichtleere Wortpräfix wiegt höchstens 00), und aus ihm folgt, dass keine Formel echtes Präfix einer anderen ist, und daraus die eindeutige Lesbarkeit: Jede zusammengesetzte Formel zerfällt auf nur eine Weise in ihre Anfangsscheibe und ihre zwei Komponenten. Die eindeutige Lesbarkeit rechtfertigt schließlich die rekursiven Definitionen über Formeln (Länge, Anzahl der Variablen und der Junktorscheiben, Teilformeln, Tiefe) und die Substitution einer Teilformel durch eine andere.

Lernziele

  1. Eigenschaften der natürlichen Zahlen durch einfache und durch starke Induktion beweisen, dabei den Induktionsanfang prüfen und den Fehler einer falschen Induktion lokalisieren.
  2. Durch Induktion über die Komplexität beweisen, dass alle Formeln eine Eigenschaft haben, wobei die Variablen und die einzige Bildungsregel als die einzigen Fälle behandelt werden.
  3. Das Gewichtslemma beweisen und daraus folgern, dass keine Formel echtes Präfix einer anderen ist und dass jede zusammengesetzte Formel eindeutig lesbar ist.
  4. Funktionen über Formeln rekursiv definieren (Länge, Tiefe, Teilformeln, Substitution) und Beziehungen zwischen ihnen durch Induktion beweisen.

Behauptungen über alle Formeln

In der Lektion über die Sprache der Aussagenlogik wurden die Formeln aus zwei Zeichen, ∘\sigO und ∙\sigI, die wir Kreis und Scheibe nennen, und aus einer einzigen Bildungsregel aufgebaut. Es gibt unendlich viele Formeln, und viele der Behauptungen, auf die es ankommt, beziehen sich auf alle: dass jede Formel mit einer Scheibe endet, dass keine Formel sich auf zwei Weisen lesen lässt, dass in jeder Formel eine Variable mehr vorkommt als Junktorscheiben. Solche Behauptungen sind keine Formeln der Sprache, die wir untersuchen, sondern Aussagen über sie, formuliert in der Metasprache (dem Deutschen, unterstützt durch die mathematische Notation); ihr Beweis ist daher keine Ableitung innerhalb eines formalen Systems, sondern ein gewöhnliches mathematisches Argument, dessen Gegenstand das formale System ist. Deshalb nennt man sie metatheoretische oder externe Beweise.

Nun beweist keine noch so große Zahl geprüfter Beispiele eine Behauptung über unendlich viele Gegenstände. Daraus folgt, dass ein Prinzip nötig ist, das erlaubt, aus endlich vielen Prüfungen zu schließen, dass eine Eigenschaft in unendlich vielen Fällen gilt. Dieses Prinzip ist die Induktion. Sie wird zuerst für die natürlichen Zahlen vorgestellt, wo sie vertrauter ist, und dann für die Formeln, wo sie sich auf die vorige stützt. Dasselbe Werkzeug wird in der Einheit über Metatheorie die Korrektheit und die Vollständigkeit des Deduktionssystems beweisen.