Über die Unmöglichkeit der Mechanisierung der Mathematik. Gödels Unvollständigkeitssatz und philosophische Implikationen

Inhaltsverzeichnis

1. Einleitung

2. Der Gödelsche Unvollständigkeitssatz

2.1. Darstellung des Kerns des Beweises

2.2. Bedeutung, Einordnung und kurze Bewertung des Theorems für die Mathematik

3. Die Unmöglichkeit einer mechanisierten Mathematik

3.1. „Die Eliminierung des Geistes und abstrakter Entitäten“

3.2. „Mechanisierung“

3.3. Zusammenführung, Gesamtbild und Implikation

4. Abschließende Bemerkungen und Ausblick

5. Literatur

1. Einleitung

Philosophers should have the audacity to generalize things without any inhibition: go on along the direction on the lower level, and generalize along different directions in a uniquely determined manner.

Gödel, 13 September 1972 (nach Wang 1996, S. 1)

Das 20. Jahrhundert war Zeuge der Setzung eines Marksteins in der Geschichte der Logik und Mathematik durch eine Arbeit, über deren Autor mancher gar sagt, er sei der größte Logiker seit Aristoteles.^[1] Im Jahre 1931 veröffentlicht der junge Mathematiker Kurt Gödel überraschend diese relativ kurze Abhandlung mit dem Titel „Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme“. Auch wenn die wissenschaftliche Gemeinschaft nicht sofort den gesamten Gehalt von Gödels Werk erkannte, so werden doch die von ihm ge-zogenen Schlüsse heutzutage weitgehend als revolutionierend und von grundlegender philoso-phischer Bedeutung angesehen (Nagel/Newman 2007, S. 9). Es ist das Ziel der vorliegenden Arbeit, durch eine Briefbemerkung Gödels angedeutete philosophische Implikationen seiner in jenem Fachartikel erbrachten (mathematischen) Hauptergebnisse, die sich in dem soge-nannten Unvollständigkeitssatz manifestieren, aufzuzeigen und zu erläutern (Kap. 3).

Dafür soll jedoch zunächst das Wesentliche respektive der allgemeine Charakter von Gödels Beweisführung herausgestellt werden (Kap. 2.1), damit nachvollzogen werden kann, auf welche geniale Weise er seine Erkenntnisse gewann,^[2] um darauf aufbauend zu einer Einschätzung und Würdigung seiner Arbeit zu gelangen (Kap. 2.2), die ein Kernproblem der Grundlagen der Mathematik in Angriff nimmt. In diesem Sinne wird knapp umrissen, inwieweit Gödels Argumentation und die daraus folgenden Unvollständigkeitssätze bahnbrechend für die Mathematik waren.

GT [i.e. Gödel’s theorem, C.H.] Mathematics [or arithmetic, C.H.] is inexhaustible.

GT1 Any consistent formal theory of mathematics must contain undecidable propositions.

GT2 No theorem-proving computer can prove all and only the true propositions of mathematics.

GT3 No formal system of mathematics can be both consistent and complete.

GT4 Mathematics is mechanically (or algorithmically) inexhaustible (or incompletable).

(ebd. S. 3)

Mathematisch genau genommen müsste zwischen Unvollständigkeits sätzen differenziert werden,^[3] jedoch genügt es für die Zwecke dieser Arbeit, vereinfacht bei dem gebräuchlicheren Ausdruck im Singular zu bleiben. In ersten gleichwertigen Annäherungen kann Gödels Unvollständigkeitssatz – entsprechend Wang (1996) – wie folgt aufgefasst werden, wobei im weiteren Verlauf besonders die fünfte Formulierung Aufmerksamkeit erfährt:

2. Der Gödelsche Unvollständigkeitssatz

2.1. Darstellung des Kerns des Beweises

Es wird gezeigt, dass ein formales System, welches die Arithmetik beschreibt, nicht gleichzeitig vollständig (mit der Bedeutung, dass alle wahren Aussagen mit den Mitteln des Systems abge-leitet werden können, also dass alle wahren Aussagen und die Negationen aller falschen Aus-sagen beweisbar sind) und widerspruchsfrei (mit der Bedeutung, dass es nicht möglich ist, aus den Axiomen sowohl eine Aussage P als auch ihre Negation ¬P abzuleiten) sein kann.

Im Folgenden wird die Idee des Beweises – in Anlehnung an Nagel/Newman (2007) und Hofstadter (1979) – aufgrund des begrenzten Raumes nur verkürzt wiedergegeben. Gödels Argument beruht auf zwei wesentlichen Überlegungen (Hofstadter 1979, S. 470): zum einen auf der Einsicht, dass es möglich ist, Aussagen über die Arithmetik (Sätze über Zahlen) in der Arithmetik selbst (als Zahlen) zu repräsentieren.^[4] Zum anderen ist die Widerspiegelung der selbstbezüglichen Aussage „Dieser Satz ist kein Satz der Arithmetik“ zu nennen (ebd. S. 480).

Um mathematische Aussagen eindeutig auf natürliche Zahlen abzubilden, definiert man zu-nächst genau die in den Sätzen verwendeten konstanten Elementarzeichen (z.B. „¬“, „ x“ oder „=“) und ihre Bedeutung und weist ihnen eine eindeutige Zahl („Gödelnummer“) zu, welche als eine Art unterscheidendes Etikett dient. Sodann werden den Zahlenvariablen, den Satzvariablen und Prädikatvariablen die erste, zweite und dritte Potenz von Primzahlen entsprechend der Reihenfolge ihres Auftretens zugeordnet. Ein mathematischer Satz lässt sich dann auf eine natürliche Zahl abbilden, indem man für das erste Zeichen der Formel die erste Primzahl zur Potenz der Gödelnummer dieses Zeichens erhebt, für das zweite Zeichen die zweite Primzahl und allgemein für das n -te Zeichen die n -te Primzahl und aus diesen so potenzierten Primzahlen das Produkt bildet. Aufgrund dieser Primfaktorisierung ist die Darstellung eines mathematischen Satzes als Zahl eindeutig. Da auch Folgen von Formeln ähnlich auf natürliche Zahlen abge-bildet werden können, ist es möglich, formale Beweise für metamathematische Sätze in dem Kalkül selbst darzustellen. Dies geschieht mittels eines Prädikats Dem (x, z), welches zum Ausdruck bringt: „Die Formelfolge mit der Gödelnummer x ist ein Beweis oder eine Demons-tration für die Formel mit der Gödelnummer z “ (Nagel/Newman 2007, S. 79).^[5]

Der zweite Schritt auf dem Weg des Beweises besteht darin, eine selbstbezügliche Aussage über die Arithmetik zu finden und diese darüber hinaus in der Arithmetik selbst darzustellen. Das angewandte Verfahren beruht auf der von Cantor erfundenen Diagonalisierung und zwar insofern, dass eine Zahl auf zwei verschiedene Arten verwendet wird, um eine selbstbe-zügliche Aussage herzuleiten, die widersprüchlich ist (Hofstadter 1979, S. 478).

Ausgehend von diesen Präliminarien wird die zu Dem (x, z) kontradiktorische Formel ¬ Dem (x, z) eingeführt, die innerhalb der formalisierten Arithmetik den metamathematischen Satz vertritt: „Die Formelfolge mit der Gödelnummer x ist kein Beweis für die Formel mit der Nummer z “.

Durch Ergänzung eines Allquantors ergibt sich: x: ¬ Dem (x, z), was die eindeutige Abbildung des metamathematischen Satzes ist: „Die Aussage mit der Nummer z ist nicht beweisbar“ (Nagel/Newman 2007, S. 86). Die Variable z wird nun zur Herstellung der Selbstbezüglichkeit genutzt. Die Funktion sub (x, y, z) besagt, dass in der Aussage mit der Gödelnummer x jedes Vorkommen derjenigen Variablen, deren Gödelnummer y ist, durch das Zahlzeichen für z er-setzt wird (ebd. S. 81f.). Das Ergebnis dieser Funktion ist wiederum die Gödelnummer einer be-stimmten Formel. Sei 17 die Gödelnummer der Variablen y. Nun generiert man einen Spezial-fall, indem zunächst z in dem Ausdruck x: ¬ Dem (x, z) durch sub (y, 17 , y) substituiert wird. Daraus resultiert:

x: ¬ Dem (x, sub (y, 17 , y)). (1)

(1) ist eine Aussagenform, die zum arithmetischen Kalkül gehört, die einen metamathematischen Satz widerspiegelt^[6] und in der sowohl y als auch die Gödelnummer von y vorkommen. Die (1) konstituierenden Elemente müssten wiederum durch Gödelnummern repräsentiert werden, errechnete man die Gödelnummer von (1). Angenommen diese Zahl sei n. Wir substituieren nun in der Formel (1) für die Variable mit der Gödelnummer 17 das Zahlzeichen für n. Damit erhalten wir eine neue (nach Gödel benannte) Formel G, die jenem angekündigten Spezialfall entspricht, den wir oben zu konstruieren versprachen (Nagel/Newman 2007, S. 86-88).

x: ¬ Dem (x, sub (n, 17 , n)) (G)

G ist also eine Aussage mit der Bedeutung: „Die Aussage, die man erhält, wenn man in der Formel mit der Gödelnummer n, d.h. (1), jedes Auftreten der Variablen mit der Gödelnummer 17, d.h. y, durch das Zahlzeichen für n ersetzt, ist nicht beweisbar". Daraus ergibt sich, dass G etwas über sich selbst aussagt: „G ist nicht beweisbar“ (ebd. S. 88). Dies ist eine Aussage, die prinzipiell wahr oder falsch sein kann. Gödel zeigte dann, dass G formal beweisbar ist, gdw. auch ihr Gegenteil ¬ G formal bewiesen werden kann, wenn also die Arithmetik widersprüchlich ist. Das heißt, dass im Falle der Widerspruchsfreiheit der Axiome eines formalisierten Systems der Arithmetik weder die Formel G noch ihre Negation ¬ G formal beweisbar sind, dass also G unentscheidbar und die Arithmetik unvollständig ist (ebd. S. 90f).

Wenngleich G in diesem Fall formal (also durch Deduktion aus den Axiomen) nicht entscheidbar ist, so kann dennoch eingesehen werden, dass G wahr sein muss: Wäre G ein formal beweisbarer Satz, so stünde dies im Widerspruch mit seiner Bedeutung „ G ist nicht beweisbar“. Also ist G kein formal beweisbarer Satz. Nichts anderes sagt jedoch G von sich aus – ergo ist G wahr (Hofstadter 1979, S. 480). Daraus folgt ein zweifaches Hauptergebnis:

Gödelscher Unvollständigkeitssatz:^[7]

Erstens demonstrierte Gödel, dass es unmöglich ist, einen metamathematischen Beweis für die Widerspruchsfreiheit oder die Konsistenz eines formalen Systems innerhalb des gleichen Systems zu erbringen, welches umfassend genug ist, die gesamte Arithmetik zu enthalten.

Er zeigte zweitens, dass die Principia Mathematica oder jedes andere System, in dem die Arithmetik entwickelt werden kann, wesentlich oder notwendigerweise unvollständig ist; mit anderen Worten: „[…] in any consistent system which is strong enough to produce simple arithmetic there are formulae which cannot be proved-in-the-system, but which we can see to be true“ (Lucas 1963, S. 255).

Dies ist ein entscheidender Punkt, der eingehendere Ausführung verdient.

2.2. Bedeutung, Einordnung und kurze Bewertung des Theorems für die Mathematik

Gerade Gödels zweite Erkenntnis kann vermutlich als noch weitreichender und revolutionierender angesehen werden, denn sie beweist eine grundsätzliche Beschränkung für die Anwendbarkeit der axiomatischen Methode (Nagel/Newman 2007, S. 60).^[8]

Im späten 19. Jahrhundert setzte sich in der Mathematik eine immer größere Abstraktion von den zuvor verwendeten anschaulichen Begriffen und damit verbunden eine Formalisierung durch. Man erkannte, dass der Kern der Mathematik darin besteht, aus gegebenen Axiomen korrekte Schlussfolgerungen zu ziehen (ebd. S. 17). Mit dieser Einsicht verbreitete sich auch die Überzeugung, dass in allen Zweigen der Mathematik ein geeignetes Axiomensystem ausreichen würde, um alle wahren Sätze formal beweisen zu können (ebd. S. 11).

Aus dem Unvollständigkeitssatz geht indessen hervor, dass Wahrheit und Beweisbarkeit nicht identisch sind,^[9] was die eben erwähnten Bemühungen, nämlich die Mathematik komplett zu formalisieren, zunichtemachte. Ihre bekannteste Ausprägung fand dieses Bestreben wohl im Hilbertschen Programm, das auf das zweite Problem^[10] einer von Hilbert erstellten Liste von 23 mathematischen Problemen zurückgeht und das darauf abzielte, mit„finiten“ Methodendie Widerspruchsfreiheit der formalen Systeme für die klassische Mathematik nachzuweisen.^[11]

Gödels Arbeit zwingt also im Allgemeinen zur Aufgabe der Annahme, dass sich für jedes Teilgebiet der Mathematik ein Axiomensystem aufstellen lässt, aus dem man die unbegrenzte Gesamtheit der wahren Sätze des infrage stehenden Teilgebietes systematisch ableiten kann. Im Besonderen und im Lichte dieser Erkenntnisse erwies sich das Hilbertprogramm in seinem ursprünglichen Anspruch als wahrscheinlich undurchführbar.^[12] Stattdessen machte Gödel die Mathematiker mit der verblüffenden, vielleicht melancholisch stimmenden Schlussfolgerung bekannt, dass „eine axiomatische Behandlung z.B. der Zahlentheorie den Bereich der arithmetischen Wahrheiten nicht voll ausschöpfen kann“ und dass „dasjenige, was wir unter einem bestimmten mathematischen Beweisverfahren verstehen, nicht mit der Durchführung einer formalisierten axiomatischen Methode zusammenfällt“ (Nagel/Newman 2007, S. 96f.).

Gleichwohl und trotz dieser negativen Folgen stellte sich der Unvollständigkeitssatz als sehr fruchtbar für die Grundlagenforschung heraus. Gödels Arbeit führte in sie ein neues Untersuchungsverfahren ein,

das seinem Wesen und seiner Fruchtbarkeit nach mit der von René Descartes in die Geometrie eingeführten algebraischen Methode vergleichbar ist. Dieses Verfahren brachte die logische und mathematische Forschung auf neue Probleme und führte zu einer noch nicht abgeschlossenen Neubewertung weitverbreiteter Philosophien der Mathematik und der Erkenntnis im allgemeinen. (ebd. S. 12)

In der Tat ist Gödels Unvollständigkeitssatz von allgemeinem Interesse und großer philosophischer Bedeutung. Aufschlussreiche Implikationen für die Philosophie des Geistes, die Philosophie der Mathematik finden im folgenden Kapitel Eingang in die Untersuchung.

[...]

^[1] So äußerte sich z.B. Robert Oppenheimer oder John Wheeler, letzterer stellt ihn sogar über Aristoteles. Vgl. Bernstein (1991), S. 141.

^[2] Nagel/Newman (2007) greifen diesen Punkt mit der Hommage auf: „Gödels grandiose intellektuelle Sinfonie“.

^[3] Vgl. z.B. Wang (1996), S. 72f., insbesondere die Punkte (2) und (3). Der zweite Gödelsche Unvollständigkeits-satz folgt allerdings unmittelbar aus dem ersten, es bedarf keiner aufwendigen zusätzlichen Beweisschritte.

^[4] Nagel/Newman (2007) sprechen in diesem Zusammenhang korrekterweise von der Arithmetisierung der Metamathematik. Vgl. ebd. S. 77ff.

^[5] Dieses Prädikat lässt sich primitiv-rekursiv überprüfen, vgl. dazu Hofstadter (1979), S. 472.

^[6] Und zwar klarerweise den folgenden: „Die Formel mit der Gödelnummer sub (y, 17 , y) ist nicht beweisbar“, respektive ausführlicher formuliert: „Die Formel, die man erhält, wenn man in der Formel mit der Gödelnummer y jedes Vorkommen von y durch das Zahlzeichen für y ersetzt, ist nicht beweisbar“.

^[7] Selbstverständlich könnte man nun den ersten (zweiten) Teil als ersten (zweiten) Unvollständigkeitssatz bezeichnen. Da aber die Präsentation der Ergebnisse nicht der Reihenfolge des tatsächlichen Gödelschen Beweis-ganges entspricht, wird davon abgesehen. Vgl. im Folgenden auch Nagel/Newman (2007), S. 60.

^[8] Die Vorstellung, dass eine Aussage als Schlusssatz aus einem expliziten logischen Beweis folgen könne, geht auf die Griechen zurück (man denke z.B. an die systematische Entwicklung der Euklidischen Geometrie), die die sogenannte „axiomatische Methode“ erfanden. Die axiomatische Methode besteht darin, dass bestimmte Sätze ohne Beweis als Axiome oder Postulate angenommen werden (z.B. Euklids viertes Postulat, nach welchem alle rechten Winkel einander gleich sind), aus denen dann alle anderen Sätze des Systems als Theoreme deduziert werden: „Die Axiome stellen die »Grundlage« des Systems dar; die Theoreme sind der »Überbau« und werden aus den Axiomen ausschließlich mit Hilfe logischer Grundsätze erhalten“ (Nagel/Newman 2007, S. 10).

^[9] Vgl. weiterführend auch Boolos/Burgess (2002), S. 225.

^[10] Dieses betrifft die Frage nach der Widerspruchsfreiheit der arithmetischen Axiome.

^[11] Die Liste von 23 mathematischen Problemen wurde 1900 von dem deutschen Mathematiker David Hilbert auf dem Internationalen Mathematikerkongress vorgestellt. Mit dieser Präsentation sollten die damals aktuellen, wich-tigen Probleme bzw. Problemkreise der Mathematik zusammengefasst, zu einer intensiven Auseinandersetzung mit ihnen und zur Konzipierung von Lösungen angeregt werden, um die Wissenschaft so voranzubringen. Im Übrigen steht nicht nur das zweite der gelisteten Probleme in Verbindung mit Gödels Unvollständigkeitssatz. Ein weiteres spezifisches Problem Hilberts (das zehnte) war es nämlich, einen Algorithmus zu finden, der feststellt, ob eine beliebige diophantische Gleichung der Form p (x 1 , x 2 , . . . , xn) = 0 eine ganzzahlige Lösung hat. Fast vierzig Jahre nachdem Kurt Gödel seine Arbeit veröffentlicht hatte, konnte Matijassewitsch auf ihr aufbauend beweisen, dass für dieses Problem keine Lösung existiert. Vgl. dazu Schöning (2008), S. 141f.

^[12] „[The incompleteness theorems, C.H.] seem to show that the hope of finding an absolute proof of consistency for any deductive system in which the whole of arithmetic is expressible cannot be realized, if such a proof must satisfy the finitistic requirements of Hilbert’s original program” (Nagel/Newman 1956, S.1694). Man beachte allerdings, dass die Möglichkeit für die Konstruktion eines finitistischen absoluten Beweises der Widerspruchsfreiheit der Arithmetik durch Gödels Ergebnisse nicht logisch ausgeschlossen wird. Gödel zeigte bloß, dass kein solcher Beweis möglich ist, der innerhalb der Arithmetik wiedergegeben werden kann. Seine Beweisführung schließt die Möglichkeit streng finitistischer Beweise, welche sich nicht innerhalb der Arithmetik darstellen lassen, nicht aus. Vgl. Nagel/Newman (2007), S. 96.