Informatik, TU Wien

Dieser Satz ist falsch

Der große Wiener Logiker Kurt Gödel untersuchte Sätze, die Aussagen über sich selbst treffen – und brachte damit unser Bild von der Mathematik gehörig ins Wanken.

TU Wien, Presseaussendung 63 / 2014, Florian Aigner

„Alle Kreter lügen“, sagte Epimenides, der Kreter. Dann muss allerdings auch dieser Satz eine Lüge sein. Das würde aber bedeuten, dass die Kreter eben nicht lügen, und der Satz richtig sein muss. Ist der Satz nun also wahr oder falsch?

Mit Sätzen, die Aussagen über sich selbst treffen, lassen sich unauflösliche Widersprüche konstruieren. Der Mathematiker und Logiker Kurt Gödel fand Methoden, solche Aussagen mit den Mitteln der formalen Logik zu untersuchen und wurde damit zu einem Begründer der Meta-Mathematik. Dieser Bereich der Mathematik versucht nicht, neue Beweise oder Rechenregeln herzuleiten, sondern sich gewissermaßen selbst zu untersuchen und mit mathematischen Mitteln zu ergründen, was sich mit mathematischen Mitteln alles ergründen lässt.

Eine vollständige und widerspruchsfreie Mathematik

Wenn man mathematische Objekte definiert, muss man sehr vorsichtig sein, um sich nicht in Widersprüche zu verstricken. Das musste auch Gottlob Frege erkennen, der die Mathematik mit Hilfe der Mengenlehre auf ein solides Fundament stellen wollte. Gerade als er 1902 sein großes Werk „Grundgesetze der Arithmetik“ fertig schrieb, erhielt er einen Brief von seinem jungen Mathematikerkollegen Bertrand Russell, der ihn auf ein ernstes Problem aufmerksam machte:
In der Mengenlehre kann man Mengen aus beliebigen Objekten bilden, etwa die Menge aller Zahlen zwischen drei und sieben oder die Menge aller gleichschenkeligen Dreiecke. Eine Menge kann auch sich selbst enthalten – etwa die Menge aller Mengen. Doch was ist mit der Menge aller Mengen, die sich nicht selbst enthalten? Sie muss sich genau dann enthalten, wenn sie sich nicht enthält – ein unauflösbarer Widerspruch. Frege war tief getroffen und gab seine Arbeit an der Mengenlehre schließlich auf.

In den Zwanzigerjahren wollte man solche Ärgerlichkeiten ein für alle Mal aus der Welt räumen: David Hilbert, der damals wohl einflussreichste Mathematiker der Welt, rief das „Hilbert-Programm“ aus: Die gesamte Mathematik, so forderte Hilbert, sollte sauber und klar auf eine kleine Anzahl von Grundaxiomen zurückgeführt werden. Aus diesen Axiomen – klaren, unmittelbar einleuchtenden Grundgesetzen wie „jede natürliche Zahl hat einen Nachfolger“ – sollen sich alle Sätze der Mathematik ableiten lassen.

Außerdem sollte bewiesen werden, dass tatsächlich jeder wahre Satz innerhalb des mathematischen Systems ableitbar ist, und dass mit mathematischen Methoden von jedem Satz eindeutig entschieden werden kann, ob er wahr oder falsch ist – die Mathematik soll frei von inneren Widersprüchen sein. Es war eine Zeit der Aufbruchsstimmung und der Visionen: „Wir müssen wissen – wir werden wissen!“ war Hilberts Parole, mit der er die Mathematik auf festes Fundament stellen wollte.

Gödel und die Unvollständigkeitssätze

Doch dieser Traum einer vollständigen, widerspruchsfreien Mathematik wurde 1931 von Kurt Gödel zerstört. Er konnte zeigen, dass sich in jedem mathematischen System, das zumindest mächtig genug ist, eine Theorie der natürlichen Zahlen zu beinhalten, mathematische Aussagen konstruieren lassen, die zwar wahr sind, aber sich nicht aus den Axiomen beweisen lassen. Das Hilbert-Programm war damit gescheitert.

Geboren wurde Kurt Gödel 1906 in Brünn, er studierte in Wien, wo er auch Kontakt zum Wiener Kreis pflegte. Ein einfacher Zeitgenosse war Gödel wohl nicht: Er litt an Hypochondrie und Verfolgungswahn. Doch auch wenn er sich im täglichen Leben manchmal recht irrational verhielt, in der Mathematik arbeitete er sauber und klar.

In der Logik hat man mit Aussagen über Zahlen zu tun – zum Beispiel: „Für alle beliebigen natürlichen Zahlen x und y ist x+y dasselbe wie y+x.“ Das lässt sich in der formalen Sprache der Logik in einer einfachen Formel aufschreiben. Gödels Einsicht war, dass man solche Aussagen über Zahlen auch selbst als Zahl codieren kann. Man muss nur den einzelnen Symbolen, die man in der Logik verwendet, geeignete Zahlen zuweisen.

Das ist aus heutiger Sicht nichts Besonderes - im digitalen Zeitalter sind wir daran gewohnt, dass sich beliebige Inhalte als Zahl codieren lassen: In gewissem Sinn sind unsere Urlaubsfotos auf der Festplatte genauso als Zahl gespeichert wie unsere Lieblingsmusik auf einer CD. Und auf ähnliche Weise lässt sich jeder mathematischen Aussage eine Zahl zuweisen – die sogenannte „Gödel-Nummer“, die von Gödel ein Jahrzehnt vor den ersten Computern erdacht wurde.

Man kann, wenn man eine passende Codierung festgelegt hat, also bestimmte Zahlen als mathematische Aussage oder als mathematischen Beweis lesen. Damit lassen sich nun allerdings mathematische Sätze konstruieren, die nicht nur Aussagen über Zahlen, sondern auch Aussagen über mathematische Sätze treffen – etwa „n ist nicht die Gödel-Nummer eines Beweises des Satzes F“ – und auch solche Aussagen haben ihrerseits wieder eine Gödel-Nummer.

Auf diese Weise gelang es Gödel, eine Aussage zu konstruieren, die besagt: „Es gibt keine Zahl, die die Gödel-Nummer eines Beweises dieser Aussage ist“ – oder simpler formuliert: eine Aussage, die behauptet: „Ich bin nicht beweisbar“.

Wenn diese Aussage nun wahr ist, dann gibt es innerhalb des verwendeten mathematischen Systems eine wahre Aussage, die niemals bewiesen werden kann. Dann ist das System also unvollständig. Wenn die Aussage hingegen falsch ist, der Satz mit der Aussage „ich bin nicht beweisbar“ also bewiesen werden kann, dann ist das ein innerer Widerspruch.

Damit lautet Gödels erster Unvollständigkeitssatz (in einer etwas umgangssprachlichen Formulierung): „Jedes logische System (das zumindest mächtig genug ist, eine Theorie der natürlichen Zahlen zu enthalten) ist entweder widersprüchlich oder unvollständig.“ Daraus lässt sich auch der noch allgemeinere zweite Gödelsche Unvollständigkeitssatz ableiten: „Jedes hinreichend mächtige konsistente System kann die eigene Konsistenz nicht beweisen.“

Die Geburt einer neuen Wissenschaft

Der Hilbertsche Traum von der in sich geschlossenen, vollständigen, widerspruchsfreien Mathematik, deren Gültigkeit aus sich selbst folgt, war damit ausgeträumt. Doch in gewisser Hinsicht wurde dadurch die Logik noch viel spannender als vorher – nicht zuletzt dadurch, dass zur selben Zeit ein ganz neuer Wissenschaftszweig entstand: Die Informatik. John von Neumann war einer der ersten, die die volle Tragweite von Gödels Unvollständigkeitssätzen erkannte, er wandte sich von der mathematischen Forschung ab und wurde zu einem der Väter der Computerwissenschaften.

Alan Turing, ebenfalls eine der wichtigsten Persönlichkeiten in der Geschichte der Informatik, wandte ganz ähnliche Überlegungen wie Gödel auf die Frage an, welche Berechnungen von Computern überhaupt durchgeführt werden können. Turings berühmtes „Halteproblem“ ist eng mit Gödels Unvollständigkeitssätzen verwandt: Es gibt Computerprogramme, die irgendwann zu rechnen aufhören und ein Ergebnis liefern, andere Computerprogramme verfangen sich in unendlichen Berechnungen und enden nie. Turing stellte sich die Frage, ob es Computerprogramme gibt, mit denen man feststellen kann, ob ein gegebenes Computerprogramm jemals zu einem Ende seiner Berechnung kommen wird. So ähnlich wie Gödel Sätze konstruierte, die Aussagen über sich selbst treffen, untersuchte Turing Computercodes, die sich selbst untersuchen. Sein Ergebnis: Ein solches Computerprogramm ist logisch nicht möglich.

Von Wien nach Princeton

1940 verließ Gödel Wien gemeinsam mit seiner Frau Adele, über Russland gelangte er in die USA, wo er an der Universität Princeton zum Kollegen und Freund von Albert Einstein wurde. Zeitweise beschäftigte sich Gödel auch selbst mit der Relativitätstheorie – so konnte er zeigen, dass nach Einsteins Formeln ein rotierendes Universum möglich ist, in dem man in seine eigene Vergangenheit reisen kann.

Seine psychischen Probleme begleiteten Kurt Gödel bis an sein Lebensende: Besessen von der Angst, vergiftet zu werden, aß er nur, was seine Frau für ihn vorgekostet hatte. Als sie selbst für längere Zeit ins Krankenhaus musste, weigerte sich Gödel zu essen und starb schließlich 1978, völlig abgemagert und entkräftet.

Seine Ideen allerdings sind heute lebendiger als je zuvor: Zweifellos gehört Gödel zu den Wissenschaftlern des 20. Jahrhunderts, die unser Verständnis der Wissenschaft am tiefgreifendsten verändert haben. In der Mathematik, in der Informatik und auch in der Philosophie kommt man heute an dem Namen Kurt Gödel mit Sicherheit nicht vorbei.

 

Die Kurt Gödel Society organisiert den "Vienna Summer of Logic", der vom 9. bis 24. Juli an der TU Wien stattfindet. Er ist in drei Themenblöcke geglieder: Informatik, künstliche Intelligenz und mathematische Logik. Insgesamt werden 2.000 TeilnehmerInnen erwartet.

 

Aussender:
Dr. Florian Aigner
Büro für Öffentlichkeitsarbeit
Technische Universität Wien
Operngasse 11, 1040 Wien
T: +43-1-58801-41027
florian.aigner@tuwien.ac.at