Das Ende der Idylle
Lange galt Mathematik als die perfekte Wissenschaft: Ausgehend von ein paar Axiomen ließ sich ein vollständiges, widerspruchsfreies Gebäude aus Regeln errichten. Mit 25 Jahren fand Kurt Gödel einen Satz, der seine Kollegen aus dem Paradies vertrieb.
- Christian Kirsch
Zu jeder w-widerspruchsfreien rekursiven Klasse K von Formeln gibt es rekursive Klassenzeichen r, so daß weder vGen r noch Neg(vGen r) zu Flg(K) gehört (wobei v die freie Variable aus r ist).“ [1] Mit diesem Satz und seinem Beweis zerstörte der österreichisch-ungarische Mathematiker Kurt Gödel, der im April 100 Jahre alt geworden wäre, vor 75 Jahren eine Idylle.
1900 hatte David Hilbert auf dem Pariser Mathematikerkongress eine Liste mit 23 ungelösten Problemen der Mathematik vorgestellt. An zweiter Stelle stand für ihn der Beweis der Widerspruchsfreiheit der Arithmetik. Wider Erwarten ließ sich dieser jedoch nicht führen. Vielmehr zeigte Gödel mit seinem oben erwähnten Unvollständigkeitssatz, dass es in der Zahlentheorie nicht beweisbare Sätze geben kann: Man kann nicht entscheiden, ob sie oder ihr Gegenteil zutreffen.
Dieses Phänomen zieht sich seit Jahrhunderten durch die Logik. Eine seiner ältesten Varianten dürfte das wenig charmante „Alle Kreter lügen“ sein. Geäußert von einem Kreter, enthüllt sich das Paradoxon sofort. Ähnliches offenbarte Anfang des 20. Jahrhunderts Bertrand Russells Antinomie: Er erfand die Menge aller Mengen, die sich nicht selbst als Element enthalten. Russel versuchte zusammen mit Alfred North Whitehead in ihrer „Principia Mathematica“ diesen Widerspruch aufzulösen.
Kreter lügen im 20. Jahrhundert
Gödel konnte 1931 in seinem Aufsatz „Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme“ zeigen, dass sich in der Zahlentheorie ähnliche Paradoxien konstruieren lassen. Dazu bildete er sämtliche „Zeichen“ (Symbole, Klammern, Operatoren) auf natürliche Zahlen ab. Eine geeignete Abbildung wäre etwa, jeder Kombination aus Zeichen und Position die Potenz einer Primzahl zuzuordnen. So ließe sich die Aussage
(∃ x)(x=sy)
(es gibt ein x, das Nachfolger von y ist) so kodieren:
28 x 34 x 513 x 79 x 118 x 1313 x 175 x 197x 2316 x 299
Dabei stehen die Primzahlen für die Position des Zeichens und der Exponent für das Zeichen selbst, etwa 8 für die öffnende und 9 für die schließende Klammer. Zwischen Aussagen und natürlichen Zahlen besteht eine ein-eindeutige Zuordnung, denn jede Zahl lässt sich eindeutig in ihre Primfaktoren zerlegen, und jedem Primfaktor entspricht wiederum ein Zeichen an einer bestimmten Position. Dadurch konnte Gödel die Zahlentheorie selbst dazu benutzen, Aussagen über sie zu treffen. Mit diesem Verfahren gelang es ihm, einen „Satz“ (das heißt eine Zahlenfolge) zu konstruieren, der etwas über sich selbst aussagt (ähnlich wie der lügende Kreter). Weder dieser Satz noch sein Gegenteil sind mit den Mitteln dieses Systems beweisbar.
Diese Methode, ein System mit seinen eigenen Mitteln zu beschreiben, machten sich später in ähnlicher Form die ersten Computerbauer zunutze. Schon Alan Turing beschrieb [2] die Speicherung von Daten und den Verfahren zu ihrer Verarbeitung im selben Format auf einem „Datenträger“.
Literatur
[1] Douglas R. Hofstadter; Gödel, Escher, Bach - Ein Endloses Geflochtenes Band; Klett-Cotta; Stuttgart 1985; ISBN 3-608-93037-X
[2] Alan Turing; Intelligence Service; Schriften; Brinkmann & Bose Verlag, Berlin 1987; ISBN 3-922660-22-3
| Kurt Gödel | |
| 28.4.1906 | Geburt in Brünn (heute Brno) |
| 1932 | Habilitation mit „Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme“ |
| 1933-1938 | Arbeit an der Universität Wien |
| 1940 | Emigration in die USA |
| 1953-1978 | Arbeit am Institute for Advanced Studies in Princeton |
| 14.1.1978 | gestorben in Princeton |
(ck)
