Die Philosophie der Mathematik

Die Geburt der modernen Logik

Induktion

Wie soll die elementare Zahlentheorie axiomatisiert werden? Trotz wiederholter Würdigung von Euklids Axiomatisierung der Geometrie scheint niemand vor dem neunzehnten Jahrhundert auf die Idee gekommen zu sein, die Arithmetik zu axiomatisieren. Grundlegend dafür ist das Prinzip der Induktion, genauer gesagt der endlichen Induktion, das erstmals im siebzehnten Jahrhundert bedeutend wurde. Das Induktionsprinzip ist eine Methode, um zu beweisen, dass eine Aussage für jede natürliche Zahl gilt. Es besteht zunächst darin zu zeigen, dass die Aussage für Null gilt, die sogenannte Induktionsbasis, und dann zu zeigen, dass, wenn sie für eine beliebige Zahl k gilt, sie auch für k plus eins gilt, den Induktionsschritt. Da sie für Null gilt, muss sie für Eins gelten; folglich gilt sie auch für Zwei und durch Wiederholung des Arguments für jede natürliche Zahl. Dies lässt sich illustrieren, indem man die bekannte Formel 0 + 1 + ... + n = n(n + 1)/2 mittels Induktion beweist. Wenn n gleich Null gesetzt wird, reduziert sich dies auf 0 = (0 mal 1)/2, was offensichtlich ist; die Induktionsbasis ist also einfach. Angenommen, für eine gegebene Zahl k gilt die Formel, sodass 0 + 1 + ... + k = k(k + 1)/2 (die Induktionsannahme). Wir wollen zeigen, dass unter dieser Annahme die Formel auch für n = k + 1 gilt. Dann ergibt sich 0 + 1 + ... + (k + 1) = k(k + 1)/2 + (k + 1) = (k + 1)(k/2 + 1) - (k + 1)(k/2) und der Induktionsschritt ist vollzogen, wodurch die Formel für alle natürlichen Zahlen bewiesen ist.

Das Induktionsprinzip ist nicht nur wichtig, um Aussagen über alle natürlichen Zahlen zu beweisen; es dient auch dazu, zu definieren, was die natürlichen Zahlen sind. Die natürlichen Zahlen bilden eine unendliche Folge, das Prototyp der einfachsten Art unendlicher Folge. Sie lassen sich daher am leichtesten als die Glieder einer solchen Folge charakterisieren, die bei Null beginnt und von jedem Glied ausgehend zu seinem Nachfolger, der um eins größeren Zahl, fortschreitet. Wie lässt sich diese Charakterisierung in einer Definition fassen? Eine Möglichkeit ist eine Definition mit mehreren Klauseln: Null ist eine natürliche Zahl. Der Nachfolger jeder natürlichen Zahl ist eine natürliche Zahl. Es könnte eingewendet werden, dass diese beiden Klauseln zwar zeigen, dass jede natürliche Zahl eine natürliche Zahl ist, jedoch nicht aussagen, dass es keine weiteren natürlichen Zahlen gibt, oder zeigen, dass etwas, das keine natürliche Zahl ist, tatsächlich keine ist. Eine direkte Methode, diesen Mangel zu beheben, besteht darin, eine dritte Klausel hinzuzufügen: Nichts anderes ist eine natürliche Zahl. Oder: Nichts ist eine natürliche Zahl, es sei denn, es folgt aus den Klauseln Eins und Zwei, dass es eine ist. Dies ist, was man als induktive Definition bezeichnet. Eine solche Definition erlaubt es nicht wirklich, das definierte Term zu eliminieren, indem man es durch den Ausdruck ersetzt, durch den es definiert wurde. Eine der großen Entdeckungen Frege's bestand darin, zu zeigen, wie dieses Problem überwunden werden kann.

Freges Aufgabe war es, eine rein logische Charakterisierung einer Folge zu geben. Kant betrachtete das Konzept einer Folge als im Wesentlichen zeitlich: Beginnend beim Anfangsglied, bei Null im Fall der natürlichen Zahlen, nehmen wir aufeinanderfolgende Schritte von jedem Glied zum nächsten, was Kant zufolge nur als zeitlicher Prozess gedacht werden könne. Frege hingegen nutzte das Prinzip der Induktion und verallgemeinerte es. Angenommen, wir wollen zunächst ausdrücken, dass n von m durch eine endliche Anzahl von Schritten erreicht werden kann, wobei jeder Schritt von einer Zahl zu ihrem Nachfolger führt, also dass n zur Nachfolgerfolge beginnend mit m gehört. Zuerst benötigen wir den Begriff einer vererbbaren Eigenschaft in der Nachfolgerfolge. Eine Eigenschaft F erfüllt dies, wenn der Nachfolger von allem, was F besitzt, ebenfalls F besitzt. Wir können dann die betreffende Tatsache ausdrücken, indem wir sagen, dass n jede Eigenschaft besitzt, die m besitzt und in der Nachfolgerfolge vererbbar ist. Durch Spezialisierung lässt sich definieren: n ist eine natürliche Zahl bedeutet, dass n zur Nachfolgerfolge beginnend bei Null gehört, also jede Eigenschaft besitzt, die Null besitzt und in der Nachfolgerfolge vererbbar ist. Umgekehrt kann man von der Nachfolgerrelation zu jeder anderen Relation R verallgemeinern: Eine Eigenschaft F gilt als vererbbar in der R-Folge, wenn jedes Objekt F besitzen muss, wenn ein Objekt mit F in der Relation R zu ihm steht. Dann drückt y jede Eigenschaft aus, die x besitzt und in der R-Folge vererbbar ist, was bedeutet, dass y ein Glied jeder Folge ist, deren Anfangsglied x ist und in der jedes Glied von einem folgt, zu dem es in der Relation R steht. Frege war auf diese Definition sehr stolz, da sie eine Quantifizierung über Eigenschaften beinhaltete und somit eine zweite Ordnung darstellte. Sie erfasste das Konzept einer Folge rein logisch, ohne zeitliche oder räumliche Intuition, und bot eine Grundlage für den Beweis allgemeiner Aussagen über Folgen, ebenfalls ohne Intuition. Gleichzeitig ermöglichte sie eine Definition der natürlichen Zahl unter Einbeziehung des Induktionsprinzips und widerlegte die weit verbreitete Meinung, dass Induktion ein für die Zahlentheorie einzigartiges Argumentationsmittel sei.

Die bekannteste Menge von Axiomen für die elementare Zahlentheorie sind die sogenannten Peano-Axiome, erstmals von Giuseppe Peano veröffentlicht, ursprünglich jedoch von Dedekind formuliert. Diese verwenden als primitive Bestandteile das Prädikat nat(x), was bedeutet, dass x eine natürliche Zahl ist, den Term Null und das Funktionssymbol s(x), den Nachfolger von x. Sie lauten: Null ist eine natürliche Zahl. Wenn x eine natürliche Zahl ist, dann ist auch ihr Nachfolger s(x) eine natürliche Zahl. Für jedes x gilt: s(x) ist nicht gleich Null. Für alle x und y gilt: Wenn s(x) = s(y), dann ist x = y. Für jede Eigenschaft F gilt: Wenn F für Null zutrifft und für jedes x, falls F für x zutrifft, auch für s(x) zutrifft, dann gilt F für jede natürliche Zahl x. Axiom fünf verkörpert selbstverständlich das Induktionsprinzip. Die Axiome eins und zwei sagen aus, dass die natürlichen Zahlen alle Objekte in der Folge von Null ausgehend zu ihren Nachfolgern umfassen. Axiom fünf besagt, dass jede natürliche Zahl zu dieser Folge gehört. Axiom drei stellt sicher, dass die Folge nicht zu Null zurückkehrt, und Axiom vier, dass sie nicht zu einem Glied nach Null zurückkehrt. Diese Axiome sind kategorisch: Sie haben bis auf Isomorphie nur ein Modell.

Aufgrund von Axiom fünf sind die Axiome auch zweiter Ordnung. Will man eine formale Theorie erster Ordnung für die Arithmetik, muss das einzelne Axiom fünf durch ein Axiomenschema mit unendlich vielen Instanzen ersetzt werden. Ein solches Schema lautet: Wenn A für Null gilt und für jedes x, falls A für x gilt, auch für s(x) gilt, dann gilt A für alle x. Dabei steht A stellvertretend für jede Formel der Sprache mit einer freien Variablen. Beispielsweise könnte A ausdrücken, dass eins ein Teiler von x ist; die entsprechende Instanz würde lauten: Wenn eins Null teilt und für jedes x, falls eins x teilt, auch eins s(x) teilt, dann teilt eins jede Zahl x. Die Instanzen des Schemas sind nicht so stark wie das zweite Axiom fünfter Ordnung. Letzteres besagt, dass Induktion für jede Eigenschaft natürlicher Zahlen gilt; das Schema besagt nur, dass sie für die im System ausdrückbaren Eigenschaften gilt.

Der Grund, warum in der Schlussfolgerung des Schemas die Einschränkung auf jede natürliche Zahl fehlt, liegt darin, dass die Variablen der formalen Theorie nur über die natürlichen Zahlen reichen. Ebenso wird das Symbol für die Nachfolgerfunktion als Funktion von natürlichen Zahlen zu natürlichen Zahlen verstanden. Dadurch kann das primitive Prädikat nat(x) zusammen mit den Peano-Axiomen eins und zwei entfallen. Da Addition und Multiplikation jedoch nicht aus Null und der Nachfolgeroperation definiert werden können, müssen die Symbole + und · als zusätzliche Primitive eingeführt werden. Sie unterliegen den Rekursionsgleichungen nach Dedekind: x + 0 = x, x + s(y) = s(x + y), x · 0 = 0, x · s(y) = x · y + x. Das resultierende formale System, das die Peano-Axiome drei und vier, die Instanzen des Axiomenschemas, sowie die Rekursionsgleichungen umfasst, wird als Peano-Arithmetik bezeichnet.

Gödels berühmter Satz von 1931 besagt, dass jede konsistente formale Theorie der Arithmetik unvollständig ist. In jeder solchen Theorie lässt sich ein Satz konstruieren, der nicht beweisbar ist, wenn die Theorie konsistent ist; eine kleine Modifikation durch Rosser zeigt, dass es ausreicht, die Konsistenz der Theorie anzunehmen, um zu beweisen, dass er auch nicht widerlegbar ist. Die Vollständigkeit einer Theorie erster Ordnung entspricht nach dem Vollständigkeitssatz der Logik erster Ordnung ihrer Kategorizität. Kein konsistentes formales System erster Ordnung kann kategorisch sein; es wird stets nicht-standardisierte Modelle zulassen, in denen der von Gödel als unentscheidbar nachgewiesene Satz falsch ist, da die Hinzufügung seiner Negation zu den Axiomen konsistent bleibt und somit ein Modell besitzt. Gödels Satz gilt ebenso für Theorien zweiter Ordnung; auch sie sind, sofern konsistent, unvollständig. Da eine solche Theorie kategorisch ist, folgt daraus, dass die Logik zweiter Ordnung unvollständig ist und nicht vollständig gemacht werden kann.

Ist ein formales System erster Ordnung für Arithmetik nicht nur konsistent, sondern auch korrekt – seine Axiome und Theoreme sind unter der intendierten Standardinterpretation wahr – wird der unentscheidbare Satz unter dieser Interpretation offensichtlich wahr sein: Er lautet Für jedes x gilt B(x), wobei B für jede Zahl v im System beweisbar und daher wahr ist. Dies veranlasste John Lucas und Roger Penrose zu argumentieren, dass Gödels Satz zeigt, dass der menschliche Geist mächtiger ist als jedes Computerprogramm oder zumindest, dass seine Fähigkeit, arithmetische Wahrheiten zu erkennen, von keinem Computerprogramm repräsentiert werden kann. Ein Programm zur Erzeugung arithmetischer Wahrheiten kann durch ein formales System dargestellt werden, das konsistent ist, falls das Programm konsistent ist; ein Mensch, der versteht, was vor sich geht, kann jedoch die Wahrheit des unentscheidbaren Satzes erkennen, die das Programm niemals erzeugen wird.

Man sollte dieses Argument sorgfältig bedenken. Dabei ist die Relevanz folgendes Faktums zu berücksichtigen: Gödel bewies einen zweiten Unvollständigkeitssatz, der besagt, dass ein konsistentes formales System der Arithmetik seine eigene Konsistenz nicht beweisen kann, im Sinne einer arithmetischen Aussage, die wahr ist, wenn und nur wenn das System konsistent ist. Dazu zeigte er, wie der gesamte Beweis des ersten Unvollständigkeitssatzes innerhalb des Systems nachgebildet werden kann. Das Ergebnis ist ein beweisbarer Satz der Form: Wenn Con(S), dann U, wobei Con(S) die Aussage über die Konsistenz des Systems ist und U der unentscheidbare Satz für S.