Das Gödel`sche Unvollständigkeitsaxiom im historischen Kontext

Inhaltsverzeichnis

1.  Einleitung  3

2.  Die Geschichte der Logik  

2.1  Die Aristotelische Logik  4

2.2  Logik im 19 Jahrhundert  

2.2.1  Boole sche Algebra  5

2.2.2  Peano-Arithmetik  6

2.3  Das Hilbert-Programm  8

2.4  Die Principia Mathematica  8

2.5  Die Metamathematik  9

3.  Gödels Werk  

3.1  Einführung der Gödelzahl  10

3.2  Arithmetisierung der Arithmetik  14

3.3  Das Kernstück des Gödelschen Beweises  

3.3.1  Der erste Unvollständigkeitssatz  16

3.3.2  Der zweite Unvollständigkeitssatz  19

4.  Schlussfolgerung  20

  Hommage à Kurt Gödel  22

  Literaturverzeichnis  23

  Bestätigung  24

  Anhang  

  2  

Einleitung

„Jetzt war Hügelbart von seiner Unbesiegbarkeit überzeugt und wollte diese auch beweisen. In die Zeit heftiger Dispute zwischen seinen Anhängern und Skeptikern fiel die Veröffentlichung von Knödels 'Unmöglichkeitssatz', der streng bewies, dass beim Spiel, dessen ungeschlagener Meister Hügelbart war, Unbesiegbarkeit eines Spielers unmöglich ist.

Die Skeptiker frohlockten. Die Fachwelt aber war erstaunt, hatte doch Knödel erst vor kurzem einen 'Möglichkeitssatz' verfasst, der Hügelbarts Überzeugung stärkte. Der 'Möglichkeitssatz' beanspruchte Gültigkeit für eine Klasse von Spielen und wurde meist so interpretiert, dass Unbesiegbarkeit eines Spielers möglich ist.

Die Fortschritte junger Spieler sprachen mehr und mehr gegen Hügelbarts Überzeugung. Das Vertrauen in die Richtigkeit des 'Unmöglichkeitssatzes' nahm stetig zu. Nach Hügelbarts erster Niederlage wurde der Beweis als eine der größten Leistungen menschlichen Denkens gefeiert.

Nach und nach kristallisierte sich aus den unzähligen Definitionen, Theoremen und Schlüssen das Beweisprinzip heraus:

Der 'Möglichkeitssatz' hingegen gilt, wenn es neben Sieg oder Niederlage auch Unentschieden geben kann. Obwohl es nicht darum gegangen war, dass Hügelbart eine Niederlage bei einem Spiel gegen sich selbst nicht vermeiden kann, stieg der 'Unmöglichkeitssatz' in den Rang einer heiligen Schrift auf.“ 1

Der ‚Unmöglichkeitssatz’ stellt eine triviale Analogie zu Kurt Gödels 1931 veröffentlichtem Unvollständigkeitssatz dar, wobei sich Gödel anstatt mit Spielern eines Spiels mit Sätzen eines Systems beschäftigt hatte, und es dabei nicht um die Unmöglichkeit der Unbesiegbarkeit, sondern um die Unbeweisbarkeit der Widerspruchsfreiheit der Axiome, die die Grundlage des Systems bilden, geht.

1 Quelle 1: Wolfgang Gasser: Der Unmöglichkeitssatz

3

Diese Arbeit ist ein Versuch, den Gödelschen Beweis, trotz seiner Komplexität, zu veranschaulichen und ihn in die Historie der Logik und der Mathematik einzubetten, was uns seine globale Bedeutung erst bewusst werden lässt.

Die Geschichte der Logik

Die Aristotelische Logik

Um die Entwicklung der Logik bis zu Gödels Unvollständigkeitsaxiomen nachvollziehen zu können, fangen wir vor über 2000 Jahren bei einem Philosophen namens Aristoteles an. Dieser lebte von 384-322 v. Chr. und gilt damals wie auch heute als einer der Begründer der Logik.

Aristoteles beschäftigte sich hauptsächlich mit Argumenten und deren Aussagen und Schlussfolgerungen. Ein Argument definierte er als eine Anordnung von Aussagen, wobei sich die eine Aussage, die Schlussfolgerung, aus den anderen Aussagen, den Grundgedanken, ergibt. Aussagen definiert Aristoteles als Sätze, die entweder eine Wahrheit oder eine Unwahrheit ausdrücken. Er unterteilt die Aussagen in verschiedene Klassen, nämlich in ‚universelle’ Aussagen, die etwas strikt dementieren oder bestätigen, und in ‚partikuläre’ Aussagen die dies nur bis zu einem gewissen Grad tun. Aristoteles zog somit vier Arten von Aussagen in Betracht: Die universelle Bestätigung, die universellen Dementis, die partikuläre Bestätigung und die partikulären Dementis. Diesen Aussagen ordnete man später die Buchstaben A,E,I,O, in Anlehnung an die lateinischen Wörter affirmo (ich bestätige) und nego (ich dementiere), zu, die wir aus reiner Bequemlichkeit im folgenden Beispiel auch verwenden werden:

Jeder Mensch ist weiß: A Gegensätze E : Kein Mensch ist weiß

Einige Menschen

sind nicht weiß

Anhand dieses Diagramms lassen sich nun leicht Aussagen über den Wahrheitsgehalt der einzelnen Aussagen treffen, wobei eine Aussage stets als ´wahr` oder ´falsch` vorgegeben sein muss. W ist die Abkürzung für ´wahr`, F für ´falsch`.

4

Annahme: A ist W. Dann ist A gleich W (vorgegeben), E ist F (da A und E Gegensätze sind),

I ist W (da A I impliziert), und O ist F (da A und O Widersprüche sind).

Nicht allen Aussagen können W oder F zugeordnet werden. In einem solchen Fall benützen wir U für ´unentscheidbar`, z.B.:

Annahme: A ist F. Dann ist A gleich F (vorgegeben), E ist U, da wenn ´jeder Mensch ist weiß` falsch ist, dann kann ´kein Mensch ist weiß` sowohl wahr als auch falsch sein, weil auch nur ´einige Menschen sind weiß` wahr sein könnte. Für I ergibt sich ebenfalls U und für

O W. 2

Aristoteles war der Erste, der Symbole in der Logik benutze, auch wenn diese Symbole nur Buchstaben waren, die aus Bequemlichkeitsgründen Aussagen oder Wörter abkürzen sollten. Die Symbolik, wie auch die Unentscheidbarkeit, die schon Aristoteles beschäftigte, werden wir gut 2000 Jahre später im Gödelschen Unvollständigkeitssatz wieder finden, nachdem weitere Grundsteine für Gödels Werk in der Geschichte der Logik und der Mathematik gelegt wurden.

Logik im 19. Jahrhundert

Die Boole’sche Algebra

Nach Aristoteles kam die Weiterentwicklung der Logik fast zu einem Stillstand, da man sich mit den Ergebnissen, die er erbracht hatte, zufrieden gab und alle Wahrheiten ergründet zu sein schienen. Immanuel Kant erklärte 1787, dass die formale Logik seit Aristoteles „auch bis jetzt keinen Schritt vorwärts hat tun können und also allem Ansehen nach geschlossen und vollendet zu sein scheint.“ 3 Erst 1847, mit der Veröffentlichung von George Booles (1815-1864) The Mathematical Analysis of Logic, „setzte eine Wiederbelebung der logischen Untersuchungen in der Neuzeit ein.“ 4 Boole konstruierte eine Klassenalgebra mit der es möglich war, logische Beziehungen der Aussagenlogik darzustellen. Diese Klassenalgebra beruhte auf Symbolen und Variablen, deren konsequenter Gebrauch es in Aussagesätzen ermöglichte, logische Ausdrücke von umgangssprachlichen Zweideutigkeiten zu befreien und somit die Logik in einer vollständig formalisierten Sprache darzustellen. Die Anwendung der Klassenalgebra soll folgendes Beispiel verdeutlichen:

2 vgl.: Howard Delong: A Profile of Mathematical Logic. United States of America 1970. S. 14ff. 3 Ernest Nagel / James R. Newman: Der Gödelsche Beweis. Wien / München 1964. S. 43. 4 Ernest Nagel / James R. Newman: Der Gödelsche Beweis. Wien / München 1964. S. 44.

5

Die ursprünglichen Aussagen lauten: Alle Gentlemen sind höflich

Kein Gentleman ist Bankier

Mit Hilfe der Klassenalgebra werden diese Aussagen durch Variablen und Symbole wiedergegeben. Dafür werden die Subjekte wie folgt definiert:

- Gentleman/Gentlemen: g (Klasse aller Gentlemen)

- Bankier: b (Klasse aller Bankiers)

- höflich: h (Klasse aller höflichen Menschen)

- nicht höflich: h` (Klasse aller unhöflichen Menschen)

Daraus ergibt sich eine neue Darstellungsweise, nämlich:

g ⊂ h

Das Symbol ´⊂` bedeutet ´ist enthalten in`, so das ´g ⊂ h` aussagt, dass die Klasse (gleichbedeutend mit Menge) aller Gentlemen in der Klasse aller höflichen Menschen enthalten ist. 5 Die Anwendung von Symbolen und Variablen vervollständigte und verbesserte der deutsche Mathematiker und Philosoph Friedrich Ludwig Gottlob Frege (1848-1925) in seinem 1878 erschienenen Hauptwerk Begriffsschrift, in dem die Logik erstmals als eine vollständig formalisierte Sprache dargestellt wurde. Frege gilt als der Begründer der modernen Logik.

Die Peano-Arithmetik

Der nächste größere Schritt in Richtung des Gödelschen Unvollständigkeitsaxioms ist die Axiomatisierung der Arithmetik. Der Begründer dieser Bewegung war der deutsche Mathematiker Julius Wilhelm Richard Dedekind (1831-1916), der einen rein logischen Aufbau der Arithmetik anstrebte, aber keine großen Errungenschaften in dieser Hinsicht für sich verbuchen konnte. Erst der Italiener Giuseppe Peano stellte 1889 in seinem Werk Arithmetices Principia nova methoda exposita ein Axiomensystem für die natürlichen Zahlen auf. In diesem Axiomensystem umgeht Peano umgangssprachliche Uneindeutigkeiten, indem 5 Ernest Nagel / James R. Newman: Der Gödelsche Beweis. Wien / München 1964. S. 44.

6

er eine Symbolsprache der Logik einführt, die nach bestehenden Regeln festgelegt ist. So werden strukturelle Merkmale der natürlichen Zahlen innerhalb der Axiome in logischer Symbolik wiedergegeben, welche nach Peano PA (Peano-Arithmetik) genannt wird. Die „Sprache“ PA bezieht sich nur auf Prädikate über Individuen aus dem Bereich der Sprache, nicht aber auf Aussagen über Aussagen, und ist somit „Sprache“ PA der ersten Stufe mit Identität. Identität bedeutet, als Symbol wiedergegeben, ´=` und hat folgende Eigenschaften:

1. Reflexivität: a = a (Gleichheit ist eine reflexive, transitive und symmetrische

2. Substitutivität: a 1 = a 2

Die sechs Peano-Axiome lauten wie folgt:

(1) 0 є N Null ist Element der natürlichen Zahlen

(2) ∀x(~s(x)=0) für alle x gilt: Null ist nicht der Nachfolger einer natürlichen Zahl; Null hat keinen Vorgänger (3) ∀x∀y(s(x)=s(y) → x=y) Wenn zwei natürliche Zahlen den gleichen Nachfolger haben, sind sie gleich;

verschiedene natürliche Zahlen haben verschiedene Nachfolger

(4) α(0) ∩ x[α(x) → α(s(x))] → xα(x)

(5) ∀x∀y(x+0=x) ∩ x+s(y)=s(x+y)

(6) ∀x∀y(x×0=0) ∩ x×s(y)=s(x×y)+x

Das Hilbert-Programm

6 Gianbruno Guerrerio: Kurt Gödel - logische Paradoxien und mathematische Wahrheit. Spektrum der

Wissenschaft. Biographie 1/2002. S. 48f.

7

David Hilbert (1862-1943), dessen wohl begabtester Schüler Kurt Gödel war, versuchte diejenigen mathematischen Gebiete, in denen es Grundlegungsbedarf gab, auf eine Grundlage von eindeutig formulierten Axiomen zu stellen. Diese Axiome mussten nur den folgenden drei Bedingungen genügen:

(1) die Axiome des Systems sollte unabhängig sein, d.h. es sollte keines der Axiome aus den anderen abgeleitet werden können (2) die Axiome sollten vollständig sein, d.h. alle Sätze des zu axiomatisierenden Gebietes sollte aus den Axiomen abgeleitet sein (3) die Axiome sollte einander nicht widersprechen, d.h. das System sollte widerspruchsfrei sein und es sollten auch keine widersprüchigen Sätze aus den Axiomen abgeleitet werden können Diese letzte Bedingung, die Hilbert an die Axiome eines Systems stellte, beinhaltete die Forderung nach einem Widerspruchsfreiheitsbeweises für axiomatische Systeme. 7 Im Jahr 1900, auf dem zweiten Mathematiker-Kongress in Paris, präsentierte Hilbert den übrigen Teilnehmern eine Liste, bestehend aus 23 ungelösten mathematischen Problemen, deren Lösung er als Agenda für die Mathematik, und somit für die Mathematiker und Logiker des 20. Jahrhunderts betitelte. An zweiter Stelle stand auf dieser Problemliste der ausstehende Widerspruchsfreiheitsbeweis für die Axiome der Arithmetik, dessen sich Jahre später der junge Gödel annahm.

Principia Mathematica

1910 erschien das monumentale, aus drei Bänden bestehende, Werk von Bertrand Russel (1872-1970) und Alfred North Whitehead (1861-1947) Principia Mathematica. Der Wunsch Russels und Whiteheads war es, die Mathematik auf eine sichere logische Basis zu stellen. Die Mathematik, besonders aber die Arithmetik, wird in den Principia als reines Teilgebiet der formalen Logik behandelt. Russel versuchte, wie es vor ihm schon Frege getan hatte, zu zeigen, dass sich alle arithmetischen Begriffe mit logischen Mitteln definieren lassen können und dass sie gänzlich aus logischen Axiomen ableitbar sein sollten. Russel und Whitehead reduzierten den Beweis der Widerspruchsfreiheit mathematischer Systeme, den das Hilbert- Programm forderte, auf die Widerspruchsfreiheit der formalen Logik. Sie verglichen die

7 vgl.: Quelle 2: Volker Peckhaus: Kurt Gödel – Die Entdeckung der Unvollständigkeit – Leben und Lehre des Begründers der Modernen Logik.

8

Widerspruchsfreiheit der Axiome der Arithmetik, die sie als „einfache Umschreibungen logischer Theoreme“ 8 definierten, mit der Widerspruchsfreiheit der „fundamentalen logischen Axiome“ 9 . Diese Methode lieferte deswegen keine endgültige Antwort auf die Frage nach der Widerspruchsfreiheit. Trotzdem zählen die Principia Mathematica zu den bedeutendsten Schriften zur Untersuchung der Widerspruchsfreiheit, da sie zwei wichtige Aspekte in sich vereinen, nämlich beinhalten sie zum einen ein sehr umfassendes Zeichensystem, mit dem es möglich war, alle Sätze der Arithmetik gesetzmäßiger Weise zu kodieren. Zum anderen listeten sie die meisten in mathematischen Beweisen verwendeten Ableitungsregeln auf und wurde so zum Hauptwerk was die Problemlösung der Widerspruchsfreiheit angeht.

Die Metamathematik

Die zunehmende Arbeit an Beweistheorien, z.B. am Widerspruchfreiheitsbeweis, den Hilbert forderte, zwang die Mathematiker die beiden Ebenen der Mathematik strikt zu trennen. Die eine der beiden sprachlichen Ebenen ist die Ebene einer Theorie selbst, die andere ist diejenige, in der über eine gegebene Theorie Untersuchungen angestellt werden. Das bedeutet, dass alle Diskussionen über die Mathematik in der Metamathematik statt finden, in der Sprache in der man über die Mathematik spricht. Ein einfaches Beispiel soll dies noch verdeutlichen:

2 + 3 = 5

Dieser Ausdruck ist gänzlich aus elementaren arithmetischen Zeichen aufgebaut und gehört zur Mathematik (Arithmetik). Hingegen stellt der Satz ´2 + 3 = 5` ist eine arithmetische Formel eine Behauptung über den genannten Ausdruck dar. Er drückt keine arithmetische Tatsache aus und gehört nicht zur formalen Sprache der Arithmetik, sondern zur Metamathematik, da er eine Kette arithmetischer Zeichen als Formel bezeichnet.

Die Metamathematik ist von solch großer Bedeutung für die Beweistheorien, dass auch Gödel seinen Beweis darauf aufbaut.

Gödels Werk

Die Einführung der Gödelzahl

8 Ernest Nagel / James R. Newman: Der Gödelsche Beweis. Wien / München 1964. S .46.

9 Ernest Nagel / James R. Newman: Der Gödelsche Beweis. Wien / München 1964. S .46.

9

1931 veröffentlichte Kurt Gödel im Alter von gerade mal 24 Jahren seine Abhandlung „Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I“ im Monatsheft für Mathematik und Physik 38, in dem er seine beiden Unvollständigkeitssätze erstmals der Öffentlichkeit präsentierte und somit für heftige Diskussionen bezüglich deren Richtigkeit sorgte.

Immerhin stellte Gödels Arbeit die Theorie seines Lehrers David Hilbert über die Widerspruchsfreiheit eines formalen Kalküls, einem System von Zeichen, auf den Kopf. Gödel behauptete bewiesen zu haben, dass ein System S unvollständig sei, da es einen Satz G enthalte, der innerhalb von S nicht bewiesen werden könne. Ferner erweiterte er seinen Beweis bezüglich der Widerspruchsfreiheit einer Theorie und stellte fest, dass die meisten formalisierten Systeme der Mathematik nicht in der Lage wären ihre eigene Widerspruchsfreiheit zu beweisen und dass ein solches System S somit unvollständig sei, da es eines erweiterten Systems S’ bedürfe, um diesen Beweis durchzuführen. Wobei wiederum auch das erweiterte System S’ unvollständig sei und deren Widerspruchsfreiheit nur mit einem System S’’ bewiesen werde könne, was zu einer endlosen Folge von Systemen führen würde. Der zweite Teil dieser Abhandlung erschien nie.

Da es sich dabei um ein sehr komplexes Werk handelt, ist einige Vorarbeit zu leisten, um Kurt Gödels Beweisführung folgen zu können.

Das arithmetische System in dem Gödel seinen Beweis durchführt, ist auf Axiomen, Regeln, aufgebaut, die er von Guiseppe Peano übernommen hat:

(1) 0 є N

Null ist Element der natürlichen Zahlen

(2) ∀x(~s(x)=0) für alle x gilt: Null ist nicht der Nachfolger einer natürlichen Zahl; Null hat keinen Vorgänger (3) ∀x∀y(s(x)=s(y) → x=y) Wenn zwei natürliche Zahlen den gleichen Nachfolger haben, sind sie gleich;

verschiedene natürliche Zahlen haben verschiedene Nachfolger

(4) α(0) ∩ x[α(x) → α(s(x))] → xα(x)

Prinzip, der vollständigen Induktion:

wenn eine Eigenschaft α für Null gilt und der Schluss „Wenn α für eine Zahl x gilt,

10

dann auch für deren Nachfolger s(x)“ zutrifft, dann gilt für alle natürlichen Zahlen die Eigenschaft α 10

Da Gödel mit seinen Beweisen Aussagen über die Mathematik trifft, bedient er sich der so genannten Metamathematik, die, um in den Beweisen verwendet werden zu können, formalisiert, d.h. mit arithmetischen Mitteln dargestellt werden muss. Dies führt dazu, dass man metamathematische Aussagen im arithmetischen System abbilden kann. Es gibt dabei zwei Arten von Objekten, die man in der Arithmetik darstellen will, nämlich die gängigen Elementarzeichen und Variablen, deren Zuordnung wie folgt geschieht: Zuerst führte er die so genannte Gödelzahl ein, mit der es möglich ist den zehn konstanten Elementarzeichen eines Theorems, einer aus den Axiomen abgeleiteten Aussage, in einem formalisierten Kalkül eine eindeutige Zahl zuweisen. Ein Kalkül ist ein aus den Axiomen abgeleitetes System, das nur aus konstanten Zeichen und Variablen besteht, wobei die Axiome angeben, nach welchen Regeln diese Zeichen kombiniert werden können. Die Bedeutung dieser Elementarzeichen und die denen zugewiesene Gödelzahl zeigt die folgende Tabelle 11 :

10 Gianbruno Guerrerio: Spektrum der Wissenschaft. Kurt Gödel - logische Paradoxien und mathematische

Wahrheit. Biographie 1/2002. S. 48f.

11 vgl.: Ernest Nagel / James R. Newman: Der Gödelsche Beweis. München 1964. S. 71.

11

Gödel selbst benutze ein etwas anderes Kodierungssystem. Er baute seine Beweisführung auf nur sieben Elementarzeichen auf, und verwendete als Gödelzahlen für diese Elementarzeichen nicht die natürlichen Zahlen 1 – 10, sonder die ersten sieben Primzahlen. Dieser Unterschied ist für uns jedoch völlig unerheblich, solange wir unser System mit den zehn Elementarzeichen und den natürlichen Zahlen 1 – 10 konsequent durchziehen. Neben den Elementarzeichen existieren noch drei Arten von Variablen. Die erste Art ist die der Zahlenvariablen x, y, z…, die für Zahlzeichen eingesetzt werden (z.B. 0, s0, y,…); die zweite sind Satzvariablen p, q, r…, die Theoreme oder Axiome darstellen (z.B. 0=0; (∃x)(x = sy);…). Die letzte Variablenart ist die der Prädikatvariablen P, Q, R…, die Prädikate wie zum Beispiel ‚Primzahl’, ‚größer als’, ‚zusammengesetzt’,… ausdrücken. Diesen Variablen werden wiederum Gödelzahlen zugeordnet, was nach den folgenden Regeln geschieht:

(i) Zahlenvariablen werden Primzahlen größer als 10 (11, 13, 17,…) zugeordnet (ii) Satzvariablen werden die Quadrate von Primzahlen größer als 10 (11², 13², 17²,…) zugeordnet (iii) Prädikatvariablen werden die dritte Potenz von Primzahlen größer als 10 (11³, 13³, 17³,…) zugewiesen

Nun können wir ein beliebiges Theorem, das aus den Axiomen des formalen Kalküls abgeleitet wurde, und sich uns in Form von Elementarzeichen präsentiert, durch die zugewiesenen Gödelzahlen ersetzten. Die Gödelzahl dieses Theorems ist das Produkt der ersten Primzahlen (2, 3, 5, 7, …), der Reihe nach, potenziert mit jener Gödelzahl g die dem entsprechenden Elementarzeichen zugewiesen wurde. Dies geschieht nach folgender Vorschrift:

2 g1 x 3 g2 x 5 g3 x … x p k

gk

; wobei p k die k-te Primzahl ist 12

Auf diese Weise erhalten wir für jedes einzelne Theorem eine eindeutige Zahl. 12 vgl.: Gianbruno Guerrerio: Kurt Gödel - logische Paradoxien und mathematische Wahrheit. Spektrum der

Wissenschaft. Biographie 1/2002. S. 49.

12

Für die Formel (∃x)(x = sy) funktioniert das wie folgt:

( ∃ x ) ( x = s y )

Formel:

Gödelzahlen der Elementarzeichen: 8 4 11 9 8 11 5 7 13 9

Die Gödelzahl dieser Formel lautet dann:

2 8 x 3 4 x 5 11 x 7 9 x 11 8 x 13 11 x 17 5 x 19 7 x 23 13 x 29 9

welche wir als m bezeichnen wollen.

Betrachtet man sich nun unsere Formel (∃x)(x = sy), die ausgesprochen besagt: es gibt ein x, und dieses x ist der unmittelbare Nachfolger von y, und ersetzt das y, welches ja eine Zahlenvariable darstellt, durch ein Zahlzeichen, z.B. 0, so erhält man eine zweite Formel, die aus der ersten abgeleitet wurde.

(∃x)(x=sy) [=m]

Subst.: y=0

sprich, es gibt ein x und dieses x ist der unmittelbare Nachfolger von Null. Folglich ergibt sich, dass jede Zahl einen unmittelbaren Nachfolger hat. Diese zweite Formel nennen wir n. Beide Formeln zusammen, stellen eine endliche Folge von Formeln dar. Wieder wird eine Gödelzahl gesucht, um diese endliche Folge von Formeln zu kennzeichnen. Analog zur Gödelzahl einer Formel können wir die Gödelzahl einer Folge von Formeln bestimmen, indem wir wiederum das Produkt der ersten Primzahlen bilden, wobei die Primzahlen mit der 1., 2., 3., … Gödelzahl G, die diesen Formeln zugewiesen wurden, potenziert werden, nach der Vorschrift:

2 G1 x 3 G2 x 5 G3 x 7 G4 x … x p k Gk , wobei p k wiederum die k-te Primzahl ist 13

In unserem Beispiel lautet die neue Gödelzahl, die Gödelzahl des Beweises, wir wollen sie k nennen, wie folgt:

k = 2 m x 3 n

13 vgl.: Gianbruno Guerrerio: Kurt Gödel - logische Paradoxien und mathematische Wahrheit. Spektrum der

Wissenschaft. Biographie 1/2002. S. 49.

13

Mit dieser so genannten Gödelisierung haben wir das formale Kalkül vollständig arithmetisiert und die erste Hürde zum Gödelschen Beweis genommen

Die Arithmetisierung der Metamathematik

Diese Methode kann man nun auf Aussagen über Beziehungen, Zusammenhänge und Struktureigenschaften des Kalküls erweitern, die mit Hilfe einer arithmetisierten Sprache im Kalkül selbst ausgedrückt werden können. Um solche Aussagen in der Mathematik treffen zu können bedarf es einer eigenen logischen Sprache, der Metamathematik. Um diese in der Beweisführung verwenden zu können, muss auch sie, wie schon das formale Kalkül, arithmetisiert werden, d.h. mit einfachen arithmetischen Mitteln dargestellt werden. Ein ‚weltliches’ Beispiel für eine solche Aussage über Beziehungen ist die Situation in einem Arbeitsamt: Jeder der dort in einem persönlichen Gespräch Rat sucht, muss bei Betreten des Amtes eine Nummer ziehen. Diese Nummern sind natürliche Zahlen (1,2,3,…) und werden der Reihe nach aufgerufen, um die entsprechenden Personen zu einem solchen Gespräch zu bitten. Somit wird auch die Beziehung zwischen diesen Nummern klar, denn je kleiner die Nummer, die man gezogen hat, desto früher ist man an der Reihe. Mit Hilfe dieser Nummern kann man leicht feststellen, wie viele Personen schon beraten wurden, und wie viele noch warten. So kann ein jeder feststellen, wie lange er noch warten muss, oder um wie viel früher ein anderer an der Reihe ist, der eine kleinere Nummer gezogen hat, also das Amt früher betreten hat. Wie im Arbeitsamt jeder Arbeitssuchende durch eine eindeutige Nummer zu identifizieren ist, so wird jeder metamathematische Satz durch eine eindeutige Formel und somit durch eine eindeutig zuweisbare Gödelzahl repräsentiert. 14 Man kann verschiedene metamathematische Aussagen bezüglich eines Satzes, einer Formel, eines Kalküls treffen, z.B. über die Beziehung zweier Formeln zueinander, oder über den Zusammenhang zweier Sätze in einer Formel. Dies sollen die folgenden Beispiele verdeutlichen:

(a) Zusammenhang zwischen Formel und einem Satz dieser Formel

14 vgl.: Ernest Nagel / James R. Newman: Der Gödelsche Beweis. Wien/München 1964. S.77.

14

Betrachten wir uns nun das formale Axiom ‚(p v p) ⊃ p’, mit der Satzvariablen p, das ausgesprochen heißt: wenn p oder p, dann p. Die Gödelzahl dieses Axioms lässt sich leicht zuweisen:

Formel:

( p v p ) ⊃ p

Gödelzahlen der Elementarzeichen : 8 11² 2 11² 9 3 11²

Die Gödelzahl des Axioms lautet folglich:

2 8 x 3 11² x 5 2 x 7 11² x 11 9 x 13 3 x 17 11²

diese bezeichnen wir kurz mit ‚a’.

Nun nehmen wir uns einen Teil dieser Formel, nämlich ‚(p v p)’, deren Gödelzahl 2 8 x 3 11² x

5 2 x 7 11² x 11 9 ist, und bezeichnen sie mit ‚b’. Wir machen nun die Aussage, dass es sich bei

dieser Formel um ein Teilglied des Axioms ‚(p v p) ⊃ p’ handelt. Dies ist aber nur dann der Fall, wenn die kleinere Gödelzahl ‚b’ ein Faktor von ‚a’ ist. Stellt sich diese Aussage als wahr heraus, dann ergibt sich daraus, dass ‚(p v p)’ wirklich ein Teilglied von ‚(p v p) ⊃ p’ ist.

(b) Beziehung zwischen Formel und einem Teilglied

Beziehen wir nun unser neues Wissen auf unser vorheriges Beispiel mit der Gödelzahl des

Beweises k = 2 m x 3 n , wobei n die Gödelzahl eines Teilglieds ist. Um die Beziehung

zwischen k und n ausdrücken zu können, schreiben wir die Formel ‚Dem(x,z)’- ‚Dem’ steht für Demonstration, sprich, Beweis - wobei das x unser k, und das z unser n repräsentiert. In Wortsprache lautet die Formel ‚Dem(x,z)’: „Die Formelfolge mit der Gödelzahl x ist ein Beweis für die Formel mit der Gödelzahl z.“

Um uns dem Kernstück des Gödelschen Beweises nähern zu können, müssen wir einen weiteren Schritt tun, und zu unserer neu eingeführten Symbolik etwas ergänzen. Gehen wir von unserer schon bekannten Formel (∃x)(x = sy) aus, die die Gödelzahl m hat. Nun substituieren wir die Variable y, die eigentlich eine Zahlenvariable ist und durch eine Primzahl größer als Zehn dargestellt werden müsste, z.B. 13, durch die Gödelzahl m. Die daraus entstehende Formel nennen wir r:

( ∃ x ) ( x = s y ) [=m] ;( y= 13)

15

( ∃ x ) ( x = ssss…ss 0 )

Gödelzahlen der Elementarzeichen :

r = 2 8 x 3 4 x 5 11 x 7 9 x 11 8 x 13 11 x 17 5 x 19 7 x 23 7 x…x p 9

r bezeichnet dabei eine ganz bestimmt arithmetische Funktion von m und 13, in der innerhalb der Funktion die Funktion selbst abgebildet werden kann, da wir m in sich selbst, anstelle einer Variablen, substituiert haben. Dies Bezeichnen wir als ‚sub(m,13,m)’; sprich: „die Gödelzahl der Formel, die man aus der Formel mit der Gödelzahl m erhält, wenn für die Variable mit der Gödelzahl 13 das Zahlzeichen m substituiert wird.“ Diese Bezeichnung kann man natürlich auch für Zahlzeichen anwenden, z.B. ‚sub(y,13,y)’, sprich: „die Gödelzahl jener Formel, die man aus der Formel mit der Gödelzahl y erhält, wenn man für die Variable mit der Gödelzahl 13 das Zahlzeichen y substituiert“. Da es sich bei y jedoch um eine Zahlenvariable selbst handelt, erhält man nach der Substitution eine bestimmte ganze Zahl, die keinerlei Behauptungen aufstellt, und somit nicht wahr oder falsch seien kann. Die Arithmetisierung der Metamathematik war der letzte große Schritt auf dem Weg zum Kernstück des Gödelschen Beweises, welchem wir nun unsere gesamte Konzentration widmen müssen, um der Beweisführung folgen zu können.

Das Kernstück des Gödelschen Beweises

Gödels erster Unvollständigkeitssatz

Der Hauptteil von Gödels Arbeit besteht nun darin, einen arithmetischen Satz zu finden, der von sich selbst behauptetet, nicht beweisbar zu sein. Der erste Schritt zu diesem Ziel ist es, eine Grundkonstruktion für diese Behauptung zu finden. Der für uns wohl passendste Anfang ist die Beweis-Formel Dem(x,z), da wir mit ihrer Hilfe einen Beweis konstruieren können. Ausgehend von der Formel Dem(x,z) können wir nun deren Negation bilden, nämlich ,die besagt, dass die Formelfolge mit der Gödelzahl x kein Beweis

~Dem(x,z) sei für die Formel mit der Gödelzahl z . Fügen wir zu dieser Formel nun ein (x) hinzu, welches die Bedeutung von‚ für jedes x gilt’ hat. Die neue Formel lautet nun

16

,und drückt aus, dass für jedes x gilt, dass die Formelfolge mit der

(x)~Dem(x,z) Gödelzahl x kein Beweis ist für die Formel mit der Gödelzahl z. Kurz gesagt, die Formel mit der Gödelzahl z ist nicht beweisbar, bzw. es kann für sie kein Beweis erbracht werden. Anstelle dieses z müssen wir nun die Gödelzahl einer Formel finden, die von sich selbst aussagt, nicht beweisbar zu sein. Es versteht sich fast von selbst, dass man dazu diese Formel in sich selbst durch Substitution abbilden muss, um eine solche Aussage zu erreichen. Dazu wenden wir das bereits eingeführte Substitutionsverfahren (sub(y,13,y))an: Ersetzt man das z nun durch die Gödelzahl einer Formel, z.B. ‚sub(y,13,y)’, so erhält man die folgende Formel:

(1)

wir wollen diese n nennen.

Substituieren wir das y in der obigen Formel durch n selbst, um die Formel in sich selbst abzubilden, erhält man

(G)

(x)~Dem(x, sub(n,13,n))

deren Gödelzahl sub(n,13,n) ist, da sub(n,13,n) per Definition die Gödelzahl derjenigen Formel ist, die man erhält, wenn man in die Formel mit der Gödelzahl n (1) für die Zahlenvariable y n einsetzt. Und genau so wurde G gebildet. G sagt also aus, dass die Formel mit der Gödelzahl sub(n,13,n) nicht beweisbar sei, wobei die Formel mit der Gödelzahl sub(n,13,n) G selbst ist. Diese arithmetische Formel vertritt im Kalkül den metamathematischen Satz: „die Formel (x)~Dem(x, sub(n,13,n)) [=G] ist nicht beweisbar“ und wird nach Gödel G genannt.

G sagt von sich selbst aus, nicht beweisbar zu sein

Um diese Aussage zu überprüfen, gehen wir von der Annahme aus, dass G beweisbar ist, d.h., dass es innerhalb der Arithmetik eine Folge von Formeln geben muss, die den Beweis für G bildet (-> Dem(x,z)), diese Formelfolge nennen wir k. Daraus erhalten wir die wahre arithmetische Formel ‚Dem(k, sub(n,13,n))’, die die Relation zwischen k, der Gödelzahl des Beweises, und sub(n,13,n), der Gödelzahl von G, bezeichnet. Da es laut Annahme ein k gibt, das G beweist, kann man die Behauptung, dass es überhaupt eine Zahl gibt, die G beweist, leicht ableiten:

17

((x)Dem(x, sub(n,13,n))

Dieser Satz sagt nun aus, dass für alle x gilt: Die Formelfolge mit der Gödelzahl x ist ein Beweis für die Formel mit der Gödelzahl sub(n,13,n). Wenn man aufmerksam die Herleitung von G verfolgt hat, wird man bemerken, dass es sich bei diesem Satz um nicht anderes als die Verneinung von G handelt. G sagt ja aus, nicht beweisbar zu sein, wenn man dies aber verneint, behauptet der neue Satz genau das Gegenteil, nämlich beweisbar zu sein.

~G

Daraus lässt sich entnehmen, dass wenn G ableitbar ist, auch deren Negation ~G ableitbar sein muss, und die Arithmetik somit widersprüchig ist, da man aus den Axiomen nicht eine Aussage und gleichzeitig deren Negation, also deren gegenteilige Aussage ableiten dürfte. Ist die Arithmetik widerspruchsfrei, so ist G nicht beweisbar, da ~G nicht beweisbar ist. Die Formel G ist somit wahr, da sie ja gerade behauptet nicht beweisbar zu sein, und ist eine formal unentscheidbare Formel, was sich an folgendem Beispiel verdeutlichen lässt: Wir denken uns ein genügend reichhaltiges System, in Form eines Rechtecks, das den Satz G enthält, der ausdrückt, dass er nicht beweisbar sei:

(a) Angenommen, G ist wahr, dann entspricht das, was der Satz ausdrückt der Wahrheit und G ist nicht beweisbar.

(b) Angenommen G ist falsch, dann entspricht das, was der Satz ausdrückt nicht der Wahrheit und deswegen ist G beweisbar.

(a’) Angenommen G ist beweisbar (~ ‚wahr’), dann ist der Satz, da er ja ausdrückt, nicht beweisbar zu sein, falsch.

18

(b’) Angenommen G ist nicht beweisbar (~ ‚nicht wahr’), dann ist der Satz, da er besagt nicht beweisbar zu sein, wahr. 15

Daraus schließen wir, dass, wenn wir ein System haben, das reichhaltig genug ist um G auszudrücken, dieses System einen Satz (nämlich G selbst) enthält, der dann und nur dann wahr ist, wenn er nicht beweisbar ist.

Die Axiome eines Systems sind dann vollständig, wenn alle wahren Aussagen formal aus ihnen ableitbar sind. Wie jedoch gerade gezeigt, ist G zwar eine wahre Aussage, aber nicht aus den Axiomen ableitbar, da alle aus den Axiomen abgeleiteten Aussagen beweisbar sind, was G allerdings nicht ist. Somit sind die Axiome unvollständig, auch wenn man G als neues Axiom zu dem System hinzufügen würde, da man dann ein neuen Satz G’ bilden könnte, der wiederum wahr, aber nicht beweisbar ist.

Gödels zweiter Unvollständigkeitssatz

„Wir kommen zum letzten Satz von Gödels grandioser intellektueller Sinfonie“ 16 , nämlich dass, wenn die Arithmetik widerspruchsfrei ist, sie unvollständig ist.

Auf Grund der Tatsache, dass die Axiome des Systems, wie oben gezeigt, unvollständig sind, kann man die Behauptung aufstellen, dass die Arithmetik an sich unvollständig ist. Analog zu

G wird nun eine Formel A konstruiert, die aussagt: „die Arithmetik ist widerspruchsfrei“ (vgl.

„G ist beweisbar“), das wäre dann der Fall, wenn es mindestens eine Formel y gäbe, die nicht beweisbar ist. Was in Worten bedeuten würde: „Es gibt mindestens eine Zahl y, dass für alle x gilt: x steht in keiner Relation Dem zu y.“

(A)

Dieser Satz stellt ein Teilglied des Satzes „wenn die Arithmetik widerspruchsfrei ist, ist sie unvollständig“ dar. Der zweite Teil dieses Satzes, nämlich „die Arithmetik ist unvollständig“, lautet in anderen Worten ausgedrückt: „Es gibt mindestens einen wahren arithmetischen Satz, der innerhalb der Arithmetik nicht formal beweisbar ist.“ Diesen Satz, nämlich G, haben wir gerade erst konstruiert und können somit beide metamathematischen Sätze zu einem

15 vgl.: Howard Delong: A Profile of Mathematical Logic. United States of America 1970. S. 160f. 16 Ernest Nagel / James R. Newman: Der Gödelsche Beweis. Wien/München 1964. S. 93.

19

zusammenfügen, der lautet: „wenn die Arithmetik widerspruchsfrei ist (A), dann ist sie unvollständig(G).“ Dieser wird durch die folgende arithmetische Formel dargestellt:

„Die Arithmetik ist wiederspruchsfrei“ ⊃ „Die Arithmetik ist unvollständig“

A ⊃ G

A ist also innerhalb der Arithmetik nicht beweisbar, sonst wäre das auch G, und dies haben

wir, wie oben gezeigt, ausgeschlossen. David Hilberts Forderung nach der Widerspruchsfreiheit der Arithmetik kann damit nicht durch einen metamathematischen ) 17

Beweis, der auf die Arithmetik abgebildet wird, erbracht werden.

Bertrand Russel sagte einst: „Die reine Mathematik ist jene Disziplin, bei der man weder weiß, worüber man spricht, noch ob das, was man sagt, wahr ist.“ 18 Dieser bezeichnende Ausspruch hat auch heute noch Gültigkeit und man kann David Hilbert seine Fehlbarkeit in Bezug auf den Widerspruchfreiheitsbeweis nicht verübeln.

Schlussfolgerung

Die Globale Bedeutung der Gödelschen Unvollständigkeitssätze, speziell aber die des ersten, kann man dann erkennen, wenn man den Satz „die Arithmetik ist unvollständig“ auf die ganze Mathematik ausweitet: Die Mathematik ist unvollständig, beziehungsweise unerschöpflich, oder kann einfach mit den Möglichkeiten des menschlichen Verstandes nicht erfasst werden. Man kann die Ablehnung, auf die Gödel nach Veröffentlichung seiner Abhandlung gestoßen ist fast verstehen, da sie das Weltbild der damaligen Zeit auf den Kopf stellte, unter anderem indem sie den Beweis für das Vorhandensein von unentscheidbaren Aussagen in formalen Theorien der Mathematik lieferte. 19 Ein meiner Meinung nach passendes Beispiel hierfür liefert die Astronomie: „Gibt es außer uns Menschen noch andere ‚intelligente’ Lebensformen im Universum?“ Eine Antwort auf diese Frage kann in unserer Zeit nicht erbracht werden, ist also unentscheidbar. Es gibt noch

17 Ernest Nagel / James R. Newman: Der Gödelsche Beweis. Wien/München 1964.

18 Ernest Nagel / James R. Newman: Der Gödelsche Beweis. Wien/München 1964. S. 18f.

19 Gianbruno Guerrerio: Spektrum der Wissenschaft. Kurt Gödel - logische Paradoxien und mathematische

Wahrheit. Biographie 1/2002. S. 52.

20

viele andere Aspekte des menschlichen Lebens, die unergründlich sind und die Menschheit

den Rest ihres Daseins beschäftigen werden. Ob der menschliche Geist jedoch jemals in der

Lage sein wird, solche Dinge wie die Unendlichkeit des Universums zu begreifen, ist fraglich.

21

Hommage à Gödel - Hans Magnus Enzensberger

Usw.

Um sich zu rechtfertigen

In jedem genügend reichhaltigen System

22

Literaturverzeichnis

Delong, Howard: A Profile of Mathematical Logic. Addison-Wesley Publishing

Company, Inc..United States of America 1970.

Kleene, Stephen Cole: Interduction to Metamathematics. American Elsevier

Publishing Company, Inc.. New York 1971.

Kleene, Stephen Cole: Mathematical Logic. John Wiley & Sons, Inc.. New York

1967.

Lorenzen, Paul: Metamathematik. Bibliographisches Institut AG. Mannheim

1962.

Nagel, Ernest / Newman, James R.: Der Gödelsche Beweis (aus dem Engl.). R.

Oldenbourg. Wien / München 1964.

Quellen aus dem Internet

Gasser, Wolfgang Gottfried: Der Unmöglichkeitssatz

http://members.lol.li/twostone/satire3.html

Peckhaus, Volker: Kurt Gödel – Die Entdeckung der Unvollständigkeit –

Leben und Lehre des Begründers der Modernen Logik.

23