Der Mathematiker Kurt Gödel machte mit seinen Arbeiten Aussagen über die Grenzen der Beweisbarkeit. Damit lieferte er einen wichtigen Beitrag zur Agnostizismus-Diskussion in der Philosophie.
Gödels Unvollständigkeitssatz
Hausaufsatz Ethik von Martin Matthes
Gliederung:
0) Einführung
1) Informationen zur Person Kurt Gödel
2) Die Problemstellung
2.1)
Vergangenheit
2.2) Principia Mathematica
2.3) Ein anschauliches Beispiel von Unvollständigkeit
3) Gödels Leistung
3.1) Erste
Versuche - Richardsche Zahlen
3.2) Gödel-Codierung (Gödelisierung)
4) Bedeutung des Gödelschen Unvollständigkeitssatzes
4.1) Grenzen der Berechenbarkeit und des Wissens
0) Einführung
Kurt Gödel ist
einer der größten Mathematiker und Logiker dieses Jahrhunderts. Obwohl
allgemein nicht so sehr bekannt, änderte seine Entdeckung fast revolutionär
die Grundansichten der meisten Mathematiker seiner Zeit. Seiner Entdeckung
wird manchmal die gleiche Bedeutung wie der Relativitätstheorie Einsteins
zugeschrieben und sie gilt als die wichtigste mathematische Theorie.
Gödel befasste sich damit, Axiome zu bestimmen, die als Grundlage für die
gesamte Mathematik dienen können. Gödels Theoreme handeln davon, was oder was
nicht bewiesen werden kann. Er kommt zu der Erkenntnis, dass es nicht möglich
ist mit den Sätzen eines axiomatischen Systems, dieses vollständig zu
beweisen; es ist somit unvollständig. Anders ausgedrückt: Es gibt wahre
Aussagen über das System, für deren Beweis ihre Methoden zu schwach sind.1
Wegen der enormern Komplexität dieses Themas kann hier nur ein Anriss dessen
stattfinden. Ich gehe auch nicht weiter auf die Trennung zwischen Gödels
erstem und zweitem Theorem ein. Es sei hier nur erwähnt, dass Gödel in seiner
1931 veröffentlichten Arbeit zwei Theoreme aufstellte, wobei das erste Theorem
das bekannteste ist bzw. beide Theoreme zusammengefasst werden als ,,Gödels
Unvollständigkeitssatz".
1) Informationen zur Person Kurt
Gödel
Name: Kurt Gödel
Geboren: 28.
April, 1906 in Brünn, Österreich - Ungarn (jetzt Brno, Tschechische Republik)
Gestorben: 14. Januar, 1978 in Princeton, New Jersey, USA
Von 1933 bis 1938 war Gödel Dozent an der Universität in Wien. Nach seiner Flucht vor dem Nationalsozialismus emigrierte er in die USA, wo er von 1953 bis zu seinem Tod am Institute for Advanced Studies in Princeton arbeitete. Im Jahre 1974 erhielt er als Auszeichnung für seine Leistungen die National Medal of Science.
2) Die Problemstellung
2.1.)
Vergangenheit
Schon vor Jahrtausenden erkannten die Griechen das Problem der
Unentscheidbarkeit. In der Aussagenlogik kann es sehr leicht zu unentscheidbaren
Problemen kommen. Mittels der Sprache ist es möglich Sätze zu formulieren, die
rein grammatikalisch richtig sind, inhaltlich aber Widersprüche in sich bergen.
Wenn sich ein Satz auf sich selbst bezieht, kann es zu einer unentscheidbaren
Situation oder einer Paradoxie kommen. Folgender Satz kann als Mittelpunkt
dieser Ausarbeitung aufgefasst werden:
Der Kreter Epimenides sagt: ,,Alle Kreter sind Lügner."
Dieser Satz, die Lügner-Paradoxie, stammt etwa aus dem 6. Jahrhundert v.u.Z. und ist das bekannteste Beispiel einer sprachlichen Paradoxie. Die Sätze ,,Ich lüge." und ,,Diese Aussage ist falsch." stellen eine Verknappung des Sachverhaltes dar. Für manchen wird der Widerspruch auf den ersten Blick vielleicht nicht gleich deutlich, deswegen wird er im Folgenden erklärt.
Wenn man davon ausgeht, dass Epimenides die Wahrheit sagt (seine Aussage wahr
ist), dann lügen alle Kreter. Alle Kreter, also auch er. Das heißt seine
Aussage ,,Alle Kreter sind Lügner." wäre gelogen. Daraus folgt: Wenn Epimenides
die Wahrheit sagt, lügt er. Das Ergebnis ist ein Widerspruch, eine Antinomie.
Das Problem wird deutlich. Solange Epimenides, der ein Kreter ist, etwas über
die Kreter sagt, weiß man nicht, ob er lügt oder die Wahrheit sagt, es ist
,,nicht-entscheidbar". Wenn der Satz hieße: Ein Spanier sagt: ,,Alle Kreter sind
Lügner.", dann ist die Aussage klar und entscheidbar. Entweder es stimmt, oder
es stimmt nicht. Es lässt sich vereinfacht sagen: Jede Aussage, die ihre eigene
Falschheit besagt, kann nie falsch oder richtig sein. Sie ist unentscheidbar.
Mathematiker und Logiker waren schon von an Anfang bestrebt, Mathematik
durchschaubar und ergründbar zu machen. Sie waren der festen Überzeugung, dass
sich die gesamte Mathematik auf wenige Axiome reduzieren ließe (z.B. Addition
und Multiplikation und natürliche Zahlen), diese Pfeiler der Mathematik müssten
nur gefunden werden. In ihrer Annahme, Mathematik sei vollkommen beweisbar,
logisch erklärbar und widerspruchsfrei, war ihnen solch eine Ungereimtheit, wie
die Antinomie des Lügners natürlich ein Dorn im Auge. Heutzutage verwundert es
wahrscheinlich kaum jemanden, wenn man behauptet, die Mathematik sei nicht
,,perfekt" (vollständig aus sich selbst heraus begründbar), doch zu Gödels Zeit
kam es wie ein Schock, dass jemand offensichtlich und eindeutig bewies, das die
Mathematik (und andere Systeme) nicht vollständig sein können, weil dies eine
unabdingbare Eigenschaft eben dieser Systeme ist.
2.2) Principia
Mathematica
Seit der ersten Erkenntnis dieser Paradoxien, beschäftigten sich Mathematiker
und Philosophen nun damit, solche Selbstbezüglichkeiten zu umgehen und Regeln zu
schaffen, die es unmöglich machen sollten, dass widersprüchliche Aussagen
entstehen. Der wahrscheinlich bedeutendeste Versuch, die Mathematik an ein paar
allgemeingültigen Axiomen festzumachen, war die Schaffung der ,,Principia
Mathematica", durch Alfred North Whitehead und Bertrand Russell von 1910 bis
1913. Dies ist ein Schriftwerk über mathematische Logik und die Fundamente der
Mathematik, welches versuchte allgemeingültige Regeln über die Grundlagen der
Mathematik aufzustellen. Neben Aristoteles' ,,Organon" ist es das
einflussreichste Buch über mathematische Logik. Whitehead und Russell versuchten
fortzusetzen, was schon viele vor ihnen versucht hatten zu beginnen, nämlich die
Reduzierung der Mathematik auf wenige Axiome. Obwohl ihnen einige wesentliche
Fortschritte gelangen, war es ihnen nicht möglich ihr eigentliches Vorhaben
überzeugend zu realisieren.
Der deutsche Mathematiker und Philosoph David Hilbert war einer der bekanntesten
Verfechter des Formalismus, das heißt der finiten, formalistischen Begründung
der klassischen Mathematik. Er sah die Grundregeln eines Systems in der
Konsistenz (Widerspruchsfreiheit), der Vollständigkeit und der Entscheidbarkeit
aller seiner Elemente. Er war fest davon überzeugt, dass man die gesamte
Mathematik auf wenigen allgemein anerkannten Axiomen gründen könne, doch nach
dem Erscheinen von Gödels Arbeit erwiesen sich alle diese Vorstellungen von der
Konsistenz der gesamten Mathematik als illusorisch und unmöglich. Gödel bewies
zudem, dass die Principia Mathematica selbst widerspruchsvoll wäre, wenn sie
vollständig bewiesen werden könnte.
2.3) Ein anschauliches Beispiel von Unvollständigkeit
Meist ist es sehr schwer, dieses abstrakte Thema an ein paar anschaulichen
Beispielen zu erläutern. Deswegen scheint es für manchen unmöglich, zum
Verständnis des Unvollständigkeitstheorems zu gelangen. Alle Beispiele sind in
einem hohen Maße unexakt und können nur oberflächlich zur Anschauung dienen.
Dennoch will ich hier einen Versuch unternehmen.
Gödels Satz setzt ein axiomatisches System voraus, welches widerspruchsfrei und
abgeschlossen (endlich) ist. Axiome sind gewissermaßen die ,,Spielregeln" in
einem System. Axiome sind so einleuchtend, dass sie gelten, ohne bewiesen werden
zu müssen. Weiterhin sagt Gödels Satz, das innerhalb eines axiomatischen Systems
keine Aussage über dessen Vollständigkeit getroffen werden kann
(Unentscheidbarkeit).
Nehmen wir an, jemand müsste ein Buch schreiben mit der Aufgabe, darin dieses Buch komplett in allen Einzelheiten zu beschreiben. Das axiomatische System ist hier das Buch und die Axiome sind zum Beispiel, dass das Buch nur eine endliche Seitenanzahl haben kann, nur endliche Seitenmaße hat und widerspruchsfrei ist. Ein abgeschlossenes System eben. Dieser Jemand fängt jetzt an, das Buch zu beschreiben. Er beginnt mit der Farbe des Einbandes, der Seitenstärke, der Höhe und Breite der Seiten, vielleicht noch der Papierart und des Geruchs. Irgendwann muss er auch anfangen zu beschreiben, was in dem Buch steht. Es steht ja nur das darin, was er bis dahin geschrieben hat. Also schreibt er weiter: ,,Auf der ersten Seite steht die Beschreibung der Farbe des Einbandes...", und so weiter. Doch schon bald bemerkt er, dass er nie fertig werden kann, denn er müsste alles, was er schreibt irgendwann wieder beschreiben! Es würde unendlich lang dauern und das Buch würde unendlich dick werden, was aber dem Axiom des Systems widersprechen würde. Es wäre also weder widerspruchsfrei, noch endlich. Er könnte das Buch nur dann vollständig beschreiben, wenn er ein zweites Buch beginnen würde, also ein System außerhalb des ersten.
Kaum exakt, jedoch recht anschaulich entspricht die Vorstellung, sich selbst aus dem Sumpf zu ziehen (Baron v. Münchhausen) der Aussage des Unvollständigkeitstheorem. Das abgeschlossene, axiomatische System entspricht dem Sumpf und dem darin feststeckenden Baron. Es ist unmöglich, aus dem System auszubrechen, indem man sich selbst an den Haaren herauszieht. Nur etwas von außerhalb kann helfen. Ein System kann sich mit seinen eigenen Elementen nicht vollständig selbst beschreiben. Nur ein zweites, außerhalb stehendes System kann dies tun.
3) Gödels Leistung
3.1) Erste Versuche - Richardsche Zahlen
Um auch in der Mathematik mit metamathematischen Sätzen umgehen zu können und
für die Mathematik greifbar zu machen, versuchten einige Mathematiker und
Philosophen durch einfache Zuordnungen Sätze in die Zahlentheorie zu überführen.
Frühe Versuche der Übertragung scheiterten daran, dass keine Unterscheidung
zwischen objekt- und metasprachlichen Angaben gemacht wurde. So versuchte
beispielsweise der Mathematiker Richard 1905 alle bekannten Definitionen der
Arithmetik der Länge nach zu sortieren und zu nummerieren. Die erste Definition
in dieser Liste ist also die kürzeste. Das heißt, die 1 macht eine Aussage über
die Länge der Definition und nicht über deren Inhalt, sie ist also
metasprachlich. Jeder objektsprachlichen Formulierung (die Definition) ordnete
er also einer metasprachlichen Aussage (die Zeichenkettenlänge der Definition)
zu. Die Definition hätte genauso gut länger gewesen sein können und hätte somit
an einer anderen Position gestanden. Beide Angaben sind also eigentlich nicht
vereinbar. Aber beginnen wir von vorn, damit das Problem erkennbar wird. Richard
ordnete also in einer Liste alle arithmetischen Definitionen jeweils einer Zahl
in einer aufsteigenden Zahlenfolge zu. Nun gibt es in dieser Auflistung auch
Zahlen, die der ihnen zugeordneten Definition entsprechen, z.B. 9 --- ,,Eine
Quadratzahl ist das Produkt einer ganzen Zahl mit sich selbst.".
Die Zahl 9 ist eine Quadratzahl. Alle Zahlen dieser Liste, auf die die zugeordneten Definitionen nicht zutreffen, heißen ,,Richardsche Zahlen". Die Definition für ,,Richardsche Zahlen" ist also folgende:
,,Eine Richardsche Zahl ist jede Zahl, auf die die ihr zugeordnete Definition nicht zutrifft."
Die Vermengung der objektsprachlichen und metasprachlichen Aussagen offenbart jedoch eine Paradoxie, nämlich genau dann, wenn die Definition für ,,Richardsche Zahlen" einer Zahl zugeordnet wird.
123 --- ,,Eine Richardsche Zahl ist jede
Zahl, auf die die ihr zugeordnete Definition nicht zutrifft."
(Die Zahl 123 ist willkürlich gewählt)
Ist 123 eine Richardsche Zahl, oder nicht? Wenn sie es wäre, dann träfe die Definition nicht zu, und wenn die Definition nicht zu trifft, dann ist 123 keine Richardsche Zahl. In anderen Worten: ,,123 ist genau dann eine Richardsche Zahl, wenn sie keine ist!" Es ist eine unentscheidbare Situation.
3.2) Gödel-Codierung (Gödelisierung)
Gödel erkannte aber das Problem und begab sich daran es zu umgehen, indem er nur
die Elementarsymbole der Arithmetik verwandte und keine objektsprachlichen
Definitionen. Auch sein Ziel war eine Umwandlung von metamathematischen Sätzen
in zahlentheoretische Aussagen, zu deren Erklärung es keiner metamathematischen
Sprache bedarf. Somit findet alles in dem System der Arithmetik statt und es
gibt keine Vermengung von verschiedenen Metaebenen mehr. Das ist die Grundlage
für die Übersetzung der Lügner-Paradoxie. Gödels Leistung ist die
Mathematisierung von sprachlichen Aussagen, speziell von auf sich selbst
bezogene Aussagen.
Das Werkzeug, welches es Gödel ermöglichte seine Überlegungen auf die Zahlentheorie zu übertragen und zu beweisen, ist die Codierung von einer rein sprachlichen Paradoxie in eine zahlentheoretische Aussage. Er übersetzte praktisch die Lügner-Paradoxie in Zahlen. Er ordnete jedem Elementarzeichen der Arithmetik (sowie der Aussagenlogik und des Prädikatenkalküls) eine Zahl einer aufsteigenden Zahlenfolge zu. Diese Zahlen werden nach ihm Gödelzahlen genannt. Durch diese Maßnahme kann jedes Zeichen eineindeutig als Zahl identifiziert werden. Die Zuordnung einer Gödelzahl kann willkürlich geschehen:
Arithmetisches Zeichen | Gödelzahl | Bedeutung |
... | ... | ... |
= | 6 | Gleichheit |
0 | 7 | Null |
* | 8 | Multiplikation |
( | 9 | Linke Klammer |
... | ... | ... |
Um die Gödelzahl beispielsweise einer Gleichung zu bekommen, geht man nach Gödel wie folgend vor:
0 = 0 (Ausgangsgleichung)
_ _ _ die einzelnen Symbole werden laut Tabelle übersetzt
7 6 7
_ _ _ die gewonnenen Nummern werden zu Potenzen einer aufsteigenden Primzahlfolge gesetzt und multipliziert
27 · 36 · 57
_
G = 7.290.000.000 das ist die einmalige Gödelzahl für die Gleichung 0 = 0
Auf diese Weise ist es möglich Formeln, Gleichungen, Aussagen, Programme als eine individuelle Zahl darzustellen, genauso wie das Kennzeichen eines Autos dessen individuelle Bezeichnung ist. Die Zahlen können natürlich sehr große Komplexität erhalten, sie stellen aber eine individuelle Repräsentation der Ausgangsgleichung dar. Genauso kann man durch Umkehrung des Verfahrens aus einer Gödelzahl die ursprüngliche Formel extrahieren. Das Ergebnis dieser Umformungen sind rein zahlentheoretische Aussagen. Beweise, die mit Hilfe der Gödelumformung geschehen, stellen nichts anderes als eine arithmetische Beziehung dar. Gödel war bestrebt, die Lügner-Antinomie rein zahlentheoretisch auszudrücken, also eine Vermischung von Objekt- und Metasprache auszuschließen. Die folgende Formel drückt das gleiche aus, wie die Lügner-Antinomie, nur ist sie mit Zeichen der Arithmetik geschrieben:
(1) _ = ¬ bwb (_)
,,_ besagt, dass _ unbeweisbar ist."
,,Ein Kreter sagt, alle Kreter lügen."
Das Prädikat ,,beweisbar" ist so zu verstehen, dass ein Satz, der beweisbar ist, auch wahr ist:
(2) bwb p _ p
Demzufolge ist das Prädikat ,,widerlegbar" als falsch zu verstehen:
¬ bwb p _ ¬ p
Es folgt eine direkte Gegenüberstellung zur Entwicklung der Unentscheidbarkeit bei der Lügner-Antinomie und deren arithmetische Entsprechung:
,,Ein Kreter sagt, alle Kreter lügen." | _ = ¬ bwb _ |
a) Man nehme
an, der Kreter sagt die Wahrheit: |
a) Man nehme
an, _ sei beweisbar. |
a) Man nehme
an, der Kreter lügt. |
a) Man nehme
an, _ sei widerlegbar. |
Da der Satz _ weder beweisbar noch widerlegbar ist, ist er unentscheidbar. Gödel zeigte nun mit seiner Arbeit, dass sich das metasprachliche Prädikat ,,beweisbar" im formalen System der Zahlentheorie mit Hilfe seiner Codierung ausschließlich mit den formalen, objektsprachlichen Mitteln ausdrücken lässt.2 Somit ist die Übertragung der Lügnerparadoxie in die Zahlentheorie gelungen. Der (nun) rein zahlentheoretische Satz _ kann nicht bewiesen oder widerlegt werden. Das heißt, dass die Zahlentheorie unvollständig sein muss.
4) Bedeutung des Gödelschen Unvollständigkeitssatzes
4.1) Grenzen der Berechenbarkeit und des Wissens
Die Bedeutung des Gödelschen Unvollständigkeitssatzes liegt darin, dass er
geradezu gnadenlos die Grenzen formaler Systeme beweist und somit die Grundlagen
vieler Forscher der damaligen Zeit entriss. Das faszinierende an seinem Theorem
ist, dass es durchaus weit ausgelegt werden kann und sich auf viele andere
Bereiche übertragen lässt. Es macht vor keinem System halt, wenn dieses den
Anforderungen an ein axiomatisches System erfüllt. Somit offenbart das Theorem
von Gödel die Grenzen des Wissens im Rahmen von Mathematik und Logik. Es zeigt
unter anderem, dass es nur außerhalb eines nichttrivialen Universums möglich
ist, dieses vollständig zu beschreiben. Vollständiges Wissen ist nur von
außerhalb möglich. Man kann sich selbst, seinen Körper und seine Seele, nie
vollständig beschreiben, da man nicht aus sich heraus treten kann. Daraus
folgernd kann man sagen, dass es auch nie eine Maschine geben kann, die dies
kann. Es wird nie eine Maschine geben, die alle zahlentheoretischen Probleme
lösen kann. Es wird auch nie eine Maschine geben, die etwas berechnet, wozu der
Mensch nicht in der Lage gewesen wäre, da der Mensch die Maschine programmiert.
Sie kann nie mehr machen, als ihre Mittel erlauben: ,,Man kann kein Glashaus aus
Ziegelsteinen bauen."
[ ... ]
5) Vereinfachte Vorgehensweise zum Beweis des Unvollständigkeitssatzes
Die folgende Darstellung beschreibt vereinfacht die Vorgehensweise zum Beweis des Gödelschen Unvollständigkeitssatzes.
Aus: Rucker, "Infinity and the Mind". Übersetzt aus dem Englischen von Martin Matthes.
1. Jemand stellt Gödel die UWM vor, die Universale WahrheitsMaschine, welche angeblich alle Fragen richtig beantwortet, die ihr gegeben werden.
2. Gödel bittet darum, das Programm und den Schaltplan sehen zu dürfen. Das Programm mag zwar äußerst komplex sein, aber es ist endlich, es hört irgendwann auf. Nennen wir das Programm P(UWM): ,,Das Programm für die Universale Wahrheitsmaschine."
3. Mit einem Lächeln schreibt Gödel den folgenden Satz auf: "Die Maschine, die auf der Grundlage des Programms P(UWM) konstruiert wurde, wird niemals sagen, dass dieser Satz wahr ist." Nennen wir diesen Satz G für ,,Gödel". G heißt in anderen Worten also: ,,Die UWM wird niemals sagen, dass G wahr ist."
4. Überzeugt lachend fragt Gödel die UWM jetzt, ob G wahr ist oder nicht.
5. Wenn die UWM sagt, dass G wahr ist, dann ist ,,Die UWM wird niemals sagen, dass G wahr ist." falsch. Wenn ,,Die UWM wird niemals sagen, dass G wahr ist." falsch ist, dann ist auch G falsch (denn G = ,,Die UWM wird niemals sagen, dass G wahr ist."). Das heißt, wenn die UWM sagt, dass G wahr ist, dann ist G falsch, und die UWM macht damit eine falsche Aussage und das kann sie ja nicht (denn die UWM macht nur wahre Aussagen). Die UWM wird also niemals sagen, dass G wahr ist.
6. Wir wissen nun, dass die UWM niemals sagen wird, G sei wahr. Also ist ,,Die UWM wird niemals sagen, dass G wahr ist." wahr.
7. "Ich kenne eine Wahrheit, die die UWM nie sagen kann oder behaupten wird.", sagt Gödel. ,,Ich weiß, dass G wahr ist. Die UWM ist also gar nicht universal!".
6) Quellenangabe
Borkowski, Ludwik: Formale Logik.
Hrsg. v. Lothar Kreiser. Berlin 1976
Heller, Bruno (Hrsg.): Kybernetik und Computer. Textband. Stuttgart 1991
Heller, Bruno (Hrsg.): Kybernetik und Computer. Kommentarband. Stuttgart
1991
Hofstadter, R. Douglas: Gödel Escher Bach - ein Endlos Geflochtenes Band.
München 1991
Kondakow, N. I.: Wörterbuch der Logik. Hrsg. v. Erhard Albrecht und
Günter Asser. Leipzig 1983
Menne, Albert: Einführung in die Logik. Tübingen 1993
1 Vgl. Hofstadter: Ein Endlos Geflochtenes Band, S.21