Adam-Kraft-Gymnasium

Schwabach

Kollegstufe 2002/2004 Abiturjahrgang 2004

Facharbeit

Thema

Das Gödelsche Unvollständigkeitsaxiom im historischen

Kontext

Verfasserin: Laura Gycha

Leistungskurs: Mathematik

Bearbeitungszeitraum: Kurshalbjahre 12/2 und 13/1

Abgabetermin: 2. Februar 2004

Unterschrift des Kursleiters

---

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: <Allen denkbaren Spielern wird eine Zahl zugeordnet. Damit der

Spieler der Zahl n unbesiegbar ist, muss er die Spieler aller Zahlen besiegen. Da n zur Menge

aller Zahlen gehört, folgt auch eine Niederlage des Spielers der Zahl n, womit die

Unbesiegbarkeit widerlegt ist.>

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ß

impliziert Widersprüche impliziert

Einige Menschen

sind weiß:

I O

: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 Bankier ist 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

b h`

g b`

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

Relation)

2. Substitutivität: a1 = a2 (a1) = (a2) (wenn zwei Objekte identisch sind,

dann gilt: wenn das eine Objekt eine

bestimmte Eigenschaft hat, dann hat

sie auch das andere Objekt)

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) xy(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,

dann auch für deren Nachfolger s(x)"

zutrifft, dann gilt für alle natürlichen

Zahlen die Eigenschaft

(5) xy(x+0=x) x+s(y)=s(x+y) Induktive Definition von Addition und

(6) xy(x×0=0) x×s(y)=s(x×y)+x Multiplikation6

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) xy(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

Tabelle11:

Gödelzahl Elementarzeichen Bedeutung

1 ~ Nicht

2 v Oder

3

Wenn... dann...

4

Es gibt ein...

5 =

Ist gleich

6 0 Null

Gödelzahl Elementarzeichen Bedeutung

7 s

Unmittelbarer

Nachfolger von...

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

---

8 (

Interpunktionszeichen

9 )

Interpunktionszeichen

10 ,

Interpunktionszeichen

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:

2g1

gk

x 3g2 x 5g3 x ... x pk ; wobei pk die k-te Primzahl ist12

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:

Formel:

(

x ) ( x = s y )

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

Die Gödelzahl dieser Formel lautet dann:

28x 34 x 511 x 79 x 118 x 1311 x 175 x 197 x 2313 x 299

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

(

x)(x=s0) [=n]

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:

2G1 x 3G2 x 5G3 x 7G4 x ... x p Gk

k

, wobei pk wiederum die k-te Primzahl ist13

In unserem Beispiel lautet die neue Gödelzahl, die Gödelzahl des Beweises, wir wollen sie

k

nennen, wie folgt:

k = 2m x 3n

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:

28 x 311² x 52 x 711² x 119 x 133 x 1711²

diese bezeichnen wir kurz mit ,

a

′.

Nun nehmen wir uns einen Teil dieser Formel, nämlich ,

(p v p)

′, deren Gödelzahl 28 x 311² x

52 x 711² x 119 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)

Substitution: y = m

(

x ) ( x = s m ) [=r]

15

---

(

x ) ( x = ssss...ss 0 )

Gödelzahlen der (m+1)-mal

Elementarzeichen : 8 4 11 9 8 11 5 7777 ...77 6 9

r

= 28 x 34 x 511 x 79 x 118 x 1311 x 175 x 197 x 237 x...x p9m+10

(m+10)te Primzahl

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

~Dem(x,z)

,die besagt, dass die Formelfolge mit der Gödelzahl

x

kein Beweis

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

---

(x)~Dem(x,z)

,und drückt aus, dass für jedes

x

gilt, dass die Formelfolge mit der

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)

(x)~Dem(x, sub(y,13,y)) [=n]

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.

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

~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:

.

.

Dieser Satz ist nicht beweisbar.

.

.

(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)

(

y)(x) ~Dem(x,z)

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

(

y)(x)~Dem(x,y)

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

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

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

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

Münchhausens Theorem, Pferd, Sumpf und Schopf,

ist bezaubernd, aber vergiss nicht:

Münchhausen war ein Lügner.

Gödels Theorem wirkt auf den ersten Blick

Etwas unscheinbar, doch bedenk:

Gödel hat recht.

"In jedem genügend reichhaltigen System

lassen sich Sätze formulieren,

die innerhalb des Systems

weder beweis- noch widerlegbar sind,

es sei denn das System

wäre selber inkonsistent."

Du kannst deine eigene Sprache

in deiner eigenen Sprache beschreiben:

aber nicht ganz.

Du kannst dein eigenes Gehirn

mit deinem eigenen Gehirn erforschen:

aber nicht ganz

Usw.

Um sich zu rechtfertigen

muss jedes denkbare System

sich transzendieren,

d.h. zerstören.

"Genügend reichhaltig" oder nicht:

Widerspruchsfreiheit

ist eine Mangelerscheinung

oder ein Widerspruch.

(Gewissheit = Inkonsistenz)

Jeder denkbare Reiter,

also auch Münchhausen,

also auch du bist ein Subsystem

eines genügend reichhaltigen Sumpfes.

Und ein Subsystem dieses Subsystems

Ist der eigene Schopf,

dieses Hebezeug

für Reformisten und Lügner.

In jedem genügend reichhaltigen System

also auch in diesem Sumpf hier,

lassen sich Sätze formulieren,

die innerhalb des Systems

weder beweis- noch widerlegbar sind.

Diese Sätze nimm in die Hand

Und zieh!

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

Anhang: Quelle 1

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

Leben und Lehre des Begründers der Modernen Logik.

Dokumenten Nr. 13195.DOC. Brockhaus - Die

Infothek. Erlangen-Nürnberg 2001.

Anhang: Quelle 2

23

---