Die Philosophie der Mathematik

Intuitionismus

Wahlsequenzen

Bisher haben wir die intuitionistische Mathematik nur insoweit betrachtet, als sie eine Version der konstruktiven Mathematik darstellt. 1967 veröffentlichte der bekannte amerikanische Mathematiker Errett Bishop ein Buch mit dem Titel Foundations of Constructive Analysis. Darin kündigte er seine Hinwendung zum Konstruktivismus an und entwickelte die Mathematik auf konstruktivistischen Prinzipien weiter, als es Brouwer und seine Anhänger getan hatten. Obwohl Bishop nicht an der Formalisierung der Logik interessiert war, akzeptierte er die zuvor beschriebene intuitionistische Logik, abgesehen davon, dass er jede explizite Verwendung der Negation ablehnte. Tatsächlich stimmte er allen bisher dargelegten intuitionistischen Ideen zu. Da alle intuitionistischen Gesetze der Prädikatenlogik erster Ordnung klassisch gültig sind, ergibt sich eine Theorie, die mit der klassischen Mathematik vereinbar ist. Sie lehnt bestimmte von klassischen Mathematikern akzeptierte Beweismethoden ab und unterscheidet Aussagen, die nach klassischem Maßstab äquivalent sind, führt aber keine Prinzipien ein, die ein klassischer Mathematiker als falsch ansehen würde.

Dies trifft nicht auf den von Brouwer entwickelten Intuitionismus zu. Er war nicht zufrieden damit, unendliche Sequenzen mit solchen zu identifizieren, die durch eine berechenbare Funktion der natürlichen Zahlen erzeugt werden. Vielmehr gestattete er, dass einige oder alle ihrer Terme durch willkürliche, ungebundene Entscheidungen oder unter effektiven Einschränkungen dessen, was gewählt werden darf, bestimmt werden. Dies sind die berühmten Wahlsequenzen. Sie mögen auf den ersten Blick höchst nicht-konstruktive Objekte sein, da sie im Allgemeinen von unendlich vielen willkürlichen Entscheidungen abhängen. Sie müssen jedoch konstruktiv gedacht werden, was bedeutet, dass sie keine abgeschlossenen Unendlichkeiten darstellen. Alles, was zu einem gegebenen Zeitpunkt über sie bekannt sein kann, ist ein endlicher Anfangsabschnitt ihrer Terme sowie jedes Gesetz, das die Wahl dieser Terme einschränkt oder in besonderen Fällen bestimmt; alles, was über eine Wahlsequenz ausgesagt werden kann, muss auf diesem Wissen basieren.

Wahlsequenzen natürlicher Zahlen sind als Elemente eines Streus zu betrachten. Ein Streu entspricht dem, was klassisch als Baum bezeichnet wird, dessen Knoten endliche Sequenzen natürlicher Zahlen sind; die sogenannten Elemente des Streus sind die Pfade im Baum, die alle unendlich lang sind, und diese Pfade sind die Wahlsequenzen. Die leere Sequenz bildet den Scheitelpunkt; die Knoten direkt unterhalb eines gegebenen Knotens oder einer endlichen Sequenz p sind unmittelbare Erweiterungen oder Nachkommen von p, gebildet durch das Anhängen einer einzigen natürlichen Zahl an das Ende von p. Jeder Streu wird von einem Streugesetz geregelt, das eine entscheidbare Eigenschaft endlicher Sequenzen natürlicher Zahlen darstellt. Es legt fest, ob eine solche endliche Sequenz in diesem Streu zulässig ist, das heißt, ob sie als Knoten des Baums erscheint und damit als Anfangsabschnitt einer Wahlsequenz gilt. Das Streugesetz muss die leere Sequenz als zulässig erkennen; für jede zulässige endliche Sequenz q jede endliche Sequenz, die eine Erweiterung von q ist, ebenfalls als zulässig anerkennen; und für jede zulässige endliche Sequenz p mindestens einen unmittelbaren Nachkommen von p als zulässig anerkennen. Das Streugesetz repräsentiert somit effektive Beschränkungen, die im Voraus für die Wahl eines Terms einer Wahlsequenz festgelegt sind, die ein Element des Streus sein soll.

Wir müssen oft unendliche Sequenzen betrachten, deren Terme nicht natürliche Zahlen sind, sondern etwa rationale Zahlen. Diese sind Elemente sogenannter bekleideter Streus. Ein gegebener nackter Streu kann durch ein effektives Korrelationsgesetz bekleidet werden, das endliche Sequenzen natürlicher Zahlen, die im Streu zulässig sind, mit mathematischen Objekten des erforderlichen Typs verknüpft.

Die Einführung von Wahlsequenzen in die intuitionistische Mathematik geht einher mit der Annahme von Prinzipien, die sie regeln und die von Konstruktivisten der Bishopschen Schule nicht anerkannt werden. Diese sind zweierlei Art: solche, die klassisch wahr sind, und solche, die klassisch falsch sind. Zur ersten Art gehört das Prinzip der Bar-Induktion. Angenommen, wir haben eine entscheidbare Menge R endlicher Sequenzen natürlicher Zahlen, die in einem gegebenen Streu zulässig sind. Angenommen ferner, A ist eine Eigenschaft endlicher Sequenzen, die jede Sequenz in R besitzt und erblich im folgenden Sinn ist: Wenn jeder zulässige unmittelbare Nachkomme einer zulässigen endlichen Sequenz p die Eigenschaft A besitzt, dann besitzt p selbst die Eigenschaft A. Wir sagen nun, dass die Menge R eine zulässige endliche Sequenz p sperrt, wenn jede Wahlsequenz, deren Anfangsabschnitt p ist, einen Anfangsabschnitt in R hat. Nach diesen Annahmen besagt die Bar-Induktion, dass, wenn jedes Element des Streus einen Anfangsabschnitt in R hat, also wenn R den Scheitelpunkt sperrt, die leere Sequenz die Eigenschaft A besitzt. Die Induktionsbasis ist die Tatsache, dass jede endliche Sequenz in R die Eigenschaft A hat; der Induktionsschritt besteht darin, dass A erblich ist.

Die bekannteste Anwendung der Bar-Induktion ist das Fan-Theorem. Ein Fan ist ein endlicher Streu, bei dem jede zulässige endliche Sequenz nur endlich viele zulässige unmittelbare Erweiterungen hat. Angenommen, wir haben einen Fan und eine entscheidbare Menge R zulässiger endlicher Sequenzen, sodass jedes Element des Fans einen Anfangsabschnitt in R besitzt. Dann besagt das Fan-Theorem, dass es eine Grenze m gibt, sodass jedes Element des Fans einen Anfangsabschnitt in R mit einer Länge von höchstens m besitzt.

Sowohl Bar-Induktion als auch das Fan-Theorem sind klassisch wahr. Ihre klassischen Beweise sind jedoch intuitionistisch nicht gültig. In Formalisierungen der intuitionistischen Mathematik wird Bar-Induktion üblicherweise als Axiom angenommen; das Fan-Theorem kann dann daraus bewiesen werden.

Prinzipien, die weit davon entfernt sind, klassisch wahr zu sein, sind die Kontinuitätsprinzipien, von denen wir hier nur den grundlegenden Fall beschreiben. Angenommen, wir haben eine extensional zugeordnete Relation zwischen Wahlsequenzen und natürlichen Zahlen: das heißt, wenn die Relation für gegebene Sequenzen a und Zahl n gilt, dann gilt sie für jede Sequenz, die mit a Terme für Term übereinstimmt. Angenommen ferner, dass wir für jede Sequenz a eine Zahl n finden können, sodass die Relation gilt. Dann besagt das Kontinuitätsprinzip, dass wir eine berechenbare Funktion endlicher Sequenzen natürlicher Zahlen finden können, die für jede Sequenz einen Wert n + 1 liefert, sodass die Relation erfüllt ist, und für jeden kürzeren Anfangsabschnitt der Sequenz den Wert null hat. Die zugrunde liegende Annahme ist, dass, wenn wir wissen, dass für jede Sequenz a ein n existiert, das die Relation erfüllt, und die Relation extensional ist, wir n aus einem endlichen Anfangsabschnitt von a bestimmen können.

Das Kontinuitätsprinzip erlaubt es, die Anforderung, dass R entscheidbar sein muss, im Fan-Theorem fallen zu lassen. Es ermöglicht auch, im Ausdruck der Bar-Induktion die Bedingung der Entscheidbarkeit durch die Bedingung der Monotonie zu ersetzen. Es hebt jedoch nicht alle Beschränkungen von R auf, da dies intuitionistisch nachweislich falsch wäre. Außerdem erlaubt das Kontinuitätsprinzip den Beweis vieler Aussagen, die mit der klassischen Mathematik in Konflikt stehen, insbesondere durch Anwendung des Fan-Theorems. Seine Kraft zeigt sich in einem berühmten Ergebnis Brouwers: Aus dem Fan-Theorem lässt sich folgern, dass, wenn für jedes Element a eines gegebenen Fans eine Zahl n gefunden werden kann, die eine extensional definierte Relation erfüllt, es eine Zahl m gibt, sodass für jedes Element a des Fans eine Zahl n gefunden werden kann, die die Relation für alle Elemente des Fans erfüllt, die mit a in den ersten m Termen übereinstimmen.

Eine reelle Funktion auf den reellen Zahlen ist eine Abbildung, die jeden Generator reeller Zahlen auf einen Generator reeller Zahlen abbildet und äquivalente Generatoren auf äquivalente Generatoren abbildet. Eine solche Funktion ist in einem Intervall gleichmäßig stetig, wenn für jedes k eine Zahl gefunden werden kann, sodass für alle x und y im Intervall gilt: wenn die absolute Differenz zwischen x und y kleiner als ein bestimmter Wert ist, dann ist die absolute Differenz der Funktionswerte ebenfalls kleiner als dieser Wert. Mit dem vorgenannten Korollar des Fan-Theorems lässt sich das Ergebnis beweisen, überraschend für klassische Mathematiker, dass, wenn eine Funktion auf jeder reellen Zahl eines Intervalls definiert ist, sie in diesem Intervall gleichmäßig stetig ist.

Frege strebte an, die klassische Mathematik direkt aus der reinen Logik zu rechtfertigen. Hilbert verfolgte einen indirekten Ansatz. Brouwer hingegen wollte sie durch eine von Grund auf reformierte Version der Mathematik ersetzen, die er für begrifflich unproblematisch hielt, während er die klassische Mathematik als konzeptuell unhaltbar ansah. Obwohl er einige bemerkenswerte Anhänger gewann, gelang es ihm nicht, eine dauerhafte Schule zu etablieren; der Intuitionismus hat in den letzten Jahrzehnten viel Aufmerksamkeit von Logikern erhalten, aber nur wenige überzeugte Anhänger. Bishops Version des Konstruktivismus war erfolgreicher; heute gibt es in den USA und Großbritannien eine respektable Zahl konstruktivistischer Mathematiker seiner Art, obwohl es höchst unwahrscheinlich erscheint, dass sie klassische Mathematiker von ihrer dominanten Position verdrängen werden.