Der Erste Unvollständigkeitssatz von Kurt Gödel

Inhaltsverzeichnis

1 Die Grundlagenkrise der Mathematik
1.1 Cantors Mengentheorie
1.2 Die Paradoxa
1.2.1 Cantors Paradoxon (1899)
1.2.2 Russells Paradoxon (1902)
1.2.3 Das Paradoxon des Epimenides (auch: Lügnerparadoxon, um 600 v. Chr.)
1.2.4 Das Paradoxon des Proklos (um 450 n. Chr.)
1.2.5 Das Paradoxon von Grelling (1908)
1.2.6 Das Paradoxon von Berry (1906)
1.3 Wege aus dem Dilemma der Paradoxa
1.3.1 Die Einschränkung des Mengenbegriffes
1.3.2 Vermeidung von Selbstbezüglichkeit
1.3.3 Der Logizismus
1.3.4 Der Konstruktivismus
1.3.5 Der Formalismus (Metamathematik)

2 Grundlagen
2.1 Cantors Diagonalmethode
2.1.1 Die Überabzählbarkeit von R und P (N)
2.1.2 Die Überabzählbarkeit von P (M) für unendliche Mengen
2.1.3 Die Beweisidee der Diagonalmethode
2.2 Formale Systeme
2.2.1 Das MIU-System
2.2.2 Das pg-System
2.3 Formales Axiomensystem der Arithmetik (nach Peano)
2.3.1 Formale Sprache des PA-Systems
2.3.2 Axiome des PA-Systems
2.3.3 Schlussregeln
2.3.4 Beispiele für Beweise im PA-System
2.3.5 Ausdrückbar und repräsentierbar
2.3.6 ω -Unvollständigkeit und ω -Widersprüchlichkeit

3 Der Beweis
3.1 Beweisidee
3.2 Schritt 1: Gödelisierung
3.2.1 Ebene 1: Motivation
3.2.2 Ebene 2: Einfache Gödelisierungen
3.2.3 Ebene 3: Vollständige Gödelisierung des PA-Systems
3.3 Schritt 2: Aussagekraft des PA-Systems
3.3.1 Ebene 1: Motivation
3.3.2 Ebene 2: Programme mit begrenzten Schleifen
3.3.3 Ebene 3: Primitiv-rekursive Funktionen
3.4 Schritt 3: Im PA-System repräsentierte Funktionen
3.4.1 Ebene 1: Motivation
3.4.2 Ebene 2: Uninteressante“ Unvollständigkeit
3.4.3 Ebene 3: ” Beweisidee für die Repräsentierbarkeit der primitiv-rekursiven Prädikate
3.5 Schritt 4: Diagonalmethode und Konstruktion von G
3.5.1 Ebene 1: Motivation
3.5.2 Ebene 2: Die Selbstbezüglichkeit im PA-System
3.5.3 Ebene 3: Das Diagonallemma

4 Folgerungen und Folgen
4.1 Folgerungen aus dem ersten Unvollständigkeitssatz
4.2 Folgen für die Mathematik

A Anhang
A.1 Formales System der Peano-Arithmetik (PA-System):
A.2 Einfache Gödelnummerierung des PA-Systems
A.3 Vollständige Gödelnummerierung des PA-Systems
A.4 Beweis für die Existenz nicht-primitiv-rekursiver Funktionen
A.5 Beweis für Lemma I aus 3.3.3

Kapitel 1

1. Die Grundlagenkrise der Mathematik

1.1 Cantors Mengentheorie

In der zweiten Hälfte des 19. Jahrhundert gelang es Georg Cantor (1845– 1918), die verschiedenen Teilgebiete der Mathematik auf eine einheitliche Grundlage zu stellen: die Mengentheorie. Damit konnte man die natürlichen

Zahlen definieren (als

Äquivalenzklassen verschiedener Begriffsumfänge –

Grundlage der Zahlentheorie), die ganzen und die rationalen Zahlen (als geordnete Paare ganzer Zahlen) und die reellen Zahlen (z. B. durch unendliche Dezimalbrüche oder mittels Dedekindscher Schnitte – Grundlage der Analysis). Die Geometrie ließ sich schon seit Ren´e Descartes (1596–1650) analytisch, d. h. mittels reeller Zahlen betreiben. Alles konnte zurückgeführt werden auf den Begriff der Menge, den Cantor folgendermaßen definierte:

Unter einer ” Mannigfaltigkeit“ oder ” Menge“ verstehe ich nämlich allgemein jedes Viele, welches sich als Eines denken lässt, d. h. jeden Inbegriffb estimmter Elemente, welcher durch ein Gesetz zu einem Ganzen verbunden werden kann,[. . . ] [2]

Eine Menge ist also eine Zusammenfassung von bestimmten, wohlunterschiedenen Objekten unserer Anschauung oder unseres Denkens zu einem Ganzen. Die Objekte heißen Elemente der Menge. Zwei Mengen sollen als gleichmächtig gelten, wenn es zwischen ihnen eine umkehrbar eindeutige (bijektive) Abbildung gibt, d. h. wenn man jedem Element der einen Menge genau ein Element der anderen Menge zuordnen kann. So lässt sich sehr leicht feststellen, ob die Anzahl der Studenten in einem Hörsaal (Menge A) gleich groß ist der Anzahl der Stühle im Hörsaal (Menge B), indem man die Studenten bittet, sich zu setzen. Bleibt kein Platz frei und muss kein Student mehr stehen, besteht eine umkehrbar eindeutige Abbildung zwischen der Menge A der Studenten und der Menge B der Stühle. Daher sind A und B gleichmächtig.

Es ist also nicht notwendig, Mengen abzählen zu können, um den Begriff der Mächtigkeit zu definieren. Daher können die natürlichen Zahlen auch auf Basis des Mengenbegriffes definiert werden (nach Gottlob Frege, 1848–1925):

Zu jeder Eigenschaft gibt es die Menge aller Dinge, die diese Eigenschaft besitzen (Fre ges ches Komprehensionsaxiom). So hat jeder Begriff einen Umfang, d. i. die Menge der Objekte, auf die der Begriff zutrifft. Zwei Begriffe heißen gleichmächtig, wenn die Mengen, die sie umfassen, gleichmächtig sind. Zwischen gleichmächtigen Begriffen A und B besteht also eine Äquivalenzrelation (A ~ B), d. h. es gilt:

A ~ A, B ~ B

Wenn A ~ B, dann B ~ A.

Wenn A ~ B und B ~ C, dann A ~ C.

Zu jedem Begriff A existiert somit die Äquivalenzklasse aller mit A gleichmächtigen Begriffe. Die Menge der natürlichen Zahlen N definiert man nun folgendermaßen: Die Zahl Null sei die Äquivalenzklasse des Begriffs ” von sich selbst verschieden“ (oder irgend ein anderer Begriff, der auf nichts zutrifft). Die Zahl Eins sei die Äquivalenzklasse des Begriffs ” Planet Erde“. Die Zahl

Zwei sei die Äquivalenzklasse des Begriffs ” Geschlecht“ usw. Dadurch erhält auch jede Äquivalenzklasse eine Kardinalzahl (Schreibweise: card (A)). Für endliche Mengen entspricht die Kardinalzahl der Anzahl der Elemente der Menge. Die Kardinalzahl von N heißt [Abbildung in dieser Leseprobe nicht enthalten] (aleph null). Alle Mengen, die gleichmächtig der Menge der natürlichen Zahlen sind (d. h. die Kardinalzahl

ℵ 0 besitzen), heißen abzählbar unendlich. Insbesondere sind auch echte Teilmengen der natürlichen Zahlen (z. B. die ungeraden Zahlen, die Quadratzahlen, die Primzahlen etc.) gleichmächtig wie die gesamte Menge der natürlichen Zahlen (ein Umstand, den Galileo Galilei (1564–1642) schon im 17. Jahrhundert bemerkte und den er als p ar adox empfand):

1 , 2 , 3 , 4 , . . . , n, . . .

↕ ↕ ↕ ↕ ↕

1 , 4 , 9 , 16 , . . . , n 2 , . . .

Diese Eigenschaft ist aber keineswegs paradox, sondern vielmehr typisch für unendliche Mengen. Sie wird daher auch verwendet, um unendliche Mengen elegant zu definieren. vielmehr mittels ” Durch geschicktes Anordnen der Elemente lässt sich zeigen, dass sowohl die Menge der ganzen Zahlen Z als auch die Menge der rationalen Zahlen Q abzählbar sind. Bei den reellen Zahlen R gelingt das nicht mehr, Cantor konnte seiner“ Diagonalmethode (siehe 2.1) zeigen, dass R eine größere Mächtigkeit besitzt als N . Weiters bewies er, dass die Potenzmenge

P (M) (d. i. die Menge aller Teilmengen) einer Menge M ebenfalls eine größere Mächtigkeit besitzt als die Menge selbst. Somit hat auch die Potenzmenge der natürlichen Zahlen P (N) eine größere Mächtigkeit als [Abbildung in dieser Leseprobe nicht enthalten] (nämlich wie [Abbildung in dieser Leseprobe nicht enthalten]).

Da man die Potenzmengenbildung beliebig oft fortsetzen kann, ergibt sich eine unendliche Vielfalt unendlicher Mächtigkeiten.

1.2 Die Paradoxa

Kaum hatte sich Cantors Mengentheorie durchgesetzt, als auch schon erste Zweifel an der Gültigkeit der gesamten Konstruktion auftraten. Es ließen sich einige Paradoxa herleiten, die die Mengentheorie (und damit das gesamte auf ihrem scheinbar sicheren Grund errichtete Gebäude der Mathematik) ins Wanken brachten.

1.2.1 Cantors Paradoxon (1899)

Dieses Paradoxon wurde von Cantor selbst im Jahre 1899 entdeckt:

Wir betrachten die Menge aller Mengen (die laut dem Cantorschen Mengenbegriff existiert) und nennen sie M. Wir bilden die Potenzmenge von M, P (M). Da die Potenzmenge eine Menge ist, muss sie natürlich in der Menge aller Mengen enthalten sein, d. h. P (M) ⊆ M.

Die Kardinalzahl einer Teilmenge kann aber höchstens gleich groß sein wie die Kardinalzahl der Menge, in der sie enthalten ist, also gilt:

card (P (M)) ≤ card (M) . (1)

Andererseits hatte Cantor gezeigt, dass die Kardinalzahl der Potenzmenge immer größer ist als die Kardinalzahl der Menge selbst, daher:

card (P (M)) > card (M) im Widerspruch zu Gleichung 1. Q

1.2.2 Russells Paradoxon (1902)

Dieses Paradoxon wurde 1902 unabhängig voneinander von Bertrand Russell

(1872–1970) und Ernst Zermelo (1871–1953) entdeckt:

Wir betrachten die Eigenschaft von Mengen, nicht Element ihrer selbst zu sein (was sicher eine vernünftige Eigenschaft ist und daher im Sinne des Fregeschen Komprehensionsaxioms auch eine Menge definiert). Da es also solche Mengen gibt, macht es auch Sinn, die Menge aller dieser Mengen zu betrachten, also die Menge aller Mengen, die nicht in sich selbst enthalten sind. Wir nennen sie R.

R = { X: X ƒ∈ X }

Offenbar ist dann eine beliebige Menge M genau dann in R enthalten, wenn M nicht in sich selbst enthalten ist:

M ∈ R ⇔ M ƒ∈ M an:

Was ist aber mit R selbst? Wenn wir für M (das ja eine beliebige Menge war) R einsetzen, dann erhalten wir:

R ∈ R ⇔ R ƒ∈ R also einen Widerspruch. Q

Für dieses Paradoxon gab Russell selbst eine schöne Veranschaulichung

In einem Dorf lebte ein Barbier. Er rasierte alle Bewohner des Dorfes, die sich nicht selbst rasierten, sonst keinen. (Das entspricht der Menge R.) Die Frage ist: Rasierte sich der Barbier selbst? (Der Barbier gehört genau dann zu R, wenn er nicht zu R gehört, und umgekehrt.)

Die beiden genannten Paradoxa gehören zu den sogenannten syntaktischen Antinomien. Sie entstehen durch rein logisches Schlussfolgern auf Grund der Verwendung an sich schon widersprüchlicher Begriffe (Menge aller Mengen,

Mengen, die sich selbst enthalten, Russells Barbier). Darüber hinaus gibt es noch eine Vielzahl von semantischen Antinomien, die in der Umgangssprache auftreten, wenn verschiedene Sprachebenen vermischt werden, die sich aber in der naiven Mengenlehre“ Cantors nachbilden lassen. Einige von ihnen sind

Abbildung in dieser Leseprobe nicht enthalten

1.2.3 Das Paradoxon des Epimenides (auch: Lügnerparadoxon, um 600 v. Chr.)

Dieses Paradoxon wird den Philosophen Epimenides von Kreta (um 600 v. Chr.) zugeschrieben:

Der Kreter Epimenides sagt: Alle Kreter sind Lügner.”

” oder strenger:

Epimenides sagt: Was ich jetzt sage, ist eine Lüge“

”

Während man in der ersten Form noch die Voraussetzung braucht, dass ein Lügner jemand ist, der immer lügt, entgeht man dem Paradoxon in seiner strengen Form nicht mehr:

Wenn Epimenides die Wahrheit sagt, dann ist seine Aussage wahr, d. h. er lügt gerade. Lügt Epimenides aber, dann ist seine Aussage eine Lüge, und somit spricht er die Wahrheit.

1.2.4 Das Paradoxon des Proklos (um 450 n. Chr.)

Dieses Paradoxon geht auf Proklos (412–485) zurück ([13], S. 28):

” Protagoras lehrt einen Schül er die Rechte und trifft mit ihm die Verabredung, daß der Schül er die Studienkosten erst zu entrichten hat,

nachdem er seinen ersten Prozeß gewonnen hat. Da er nach Abschluß seiner Studien keine Prozesse üb ernimmt, verklagt ihn P. schließlich auf Zahlung der Kosten. Er argumentiert: Gewinne ich den Prozeß, so erhalte ich mein Geld aufgrund des Urteilsspruches, verliere ich, so erhalte ich es aufgrund der früheren Verabredung. Der Schül er argumentiert umgekehrt, daß er die Studienkosten in keinem Fall zu zahlen braucht , entweder wegen der getroffenen Verabredung oder aufgrund des ri chterlichen Urteil sspru ches.“

1.2.5 Das Paradoxon von Grelling (1908)

Dieses Paradoxon stammt von Grelling ([13], S. 28)

” Man teile alle deutschen Adjektive (Eigenschaftswörter) in folgende zwei Klassen ein:

a) heterologische A djekti ve, die nicht das sind, was sie bedeuten, z. B.

das kurze Adjektiv ”lang“, das dreisilbige Adjektiv ”zweisilbig“, das deutsche Adjektiv ” französisch“.

b) autologische A djekt ive, die das sind, was sie bedeuten, z. B. das kur-

ze Adjektiv ”kurz“, das dreisilbige Adjektiv ”dreisilbig“, das deutsche A djektiv ”deutsch“.

Die Frage, in welcher Klasse das Adjektiv ” heterologisch“ liegt, führt zu einem Widerspruch. Die Annahme, es liege in a), führt zu dem Schluß,

daß es in b) liegt, und umgekehrt.“

1.2.6 Das Paradoxon von Berry (1906)

Dieses von Berry veröffentlichte Beispiel ist vor allem deswegen interessant, weil dabei das Paradoxon durch die Beschreibung einer natürlichen Zahl und dem Wechsel zwischen Syntax und Semantik dieser Beschreibung entsteht (eine Methode, die in dieser Arbeit noch eine große Rolle spielen wird):

Abbildung in dieser Leseprobe nicht enthalten

Betrachten wir den Ausdruck eine natürliche Zahl, die nicht mit weniger als sechsundzwanzig Sil ” genannt werden kann“. Dieser Ausdruck benennt mit 25 Silben eine Zahl, die nicht mit weniger als 26 Silben benannt werden kann!

1.3 Wege aus dem Dilemma der Paradoxa

Nachdem das Auftauchen von Paradoxa in der naiven Mengenlehre Cantors diese Grundlegung der Mathematik in Frage gestellt hatte, wurden mehrere

Anläufe gemacht, einen sauberen und widerspruchsfreien Weg zu finden, die Mathematik auf ein sicheres Fundament zu stellen.

1.3.1 Die Einschränkung des Mengenbegriffes

Da alle Antinomien auftreten, wenn der Cantorsche bzw. Fregesche Mengenbegriff zu sehr ausgereizt wird (Menge aller Mengen etc. [Abbildung in dieser Leseprobe nicht enthalten] syntaktische

Antinomien), oder verschiedene Bedeutungsebenen vermischt werden (Aussagen und Aussagen

über Aussagen, Eigenschaften und Eigenschaften von

Eigenschaften etc. [Abbildung in dieser Leseprobe nicht enthalten] semantische Antinomien), lag der Gedanke nahe, den

Mengenbegriff einzugrenzen und somit ein Entstehen der Paradoxa zu verhindern.

Ähnlich der Begriffe ” nkt“ und ” e“ in Euklids Geometrie,

Pu Gerad wurde der Begriff der Menge axiomatisch eingefuhrt, also unter Angabe einer Anzahl von Bedingungen (Axiome), die zu gelten hätten, wenn von einer Menge die Rede sein sollte. Eines der ersten Systeme einer Axiomatischen Mengenlehre ist das von Zermelo 1908 angegebene und von Abraham Fraenkel (1891–1965) verfeinerte der Zermelo-Fraenkelschen Mengenlehre.

John von Neumann (1903–1957) gab eine Möglichkeit an, die natürlichen Zahlen darin zu definieren, indem man für jede Zahl eine bestimmte Menge als Repräsentanten auswählt (und nicht wie Frege antinomieverdächtige Äquivalenzklassen): Null sei die leere Menge (die einer widersprüchlichen Eigenschaft entspricht), Eins die Menge, die der Eigenschaft entspricht, gleich

Null zu sein, Zwei die Menge, die der Eigenschaft entspricht, gleich Null oder Eins zu sein usw.:

Abbildung in dieser Leseprobe nicht enthalten

Die gesamte Arithmetik lässt sich auf diesen Repräsentanten und auf den mengentheoretischen Funktionen Vereinigung, Durchschnitt, Elementsein usw. aufbauen.

Tatsächlich ließen sich die bekannten Antinomien in der axiomatischen Mengenlehre nicht mehr herleiten. Allerdings hieß das noch lange nicht, dass nicht irgendwann wieder Antinomien auftreten würden. ” Eine durch keinen widerle gen den Widerspruch zu hemmende unrichtige Theorie ist darum nicht

wen i ger unrichtig, so wie eine durch kein reprimierendes Gericht zu hemmende verbrecherische Politik darum nicht weniger verbrecherisch ist“, meinte Luitzen Egbertus Jan Brouwer (1871–1953) [1]. Außerdem blieb die auf der axiomatischen Mengenlehre aufgebaute Analysis nicht frei von Selbstbezüglichkeiten, die wieder potentiell antinomieverdächtig“ sind. ”

1.3.2 Vermeidung von Selbstbezüglichkeit

Wenn eine Menge M und ein Objekt m so definiert werden, dass einerseits m Element von M ist, andererseits aber die Definition von m von M abhängig ist, so nennt man diese Definition (von m oder M) selbstbezüglich. Gleiches gilt für ein Objekt m, dass die Eigenschaft E hat und dessen Definition auf der Eigenschaft E beruht. (Hier ist M einfach die Menge der Objekte mit der Eigenschaft E.).

Alle angeführten Antinomien beruhen auf einer selbstbezüglichen Definition. In Cantors Paradoxon (1.2.1) enthält die Menge aller Mengen M die Menge P (M), die durch M definiert ist. In Russells Antinomie (1.2.2) wird die Menge aller Mengen M in zwei Teile geteilt: die Mengen, die sich selbst enthalten, und die Mengen, auf die das nicht zutrifft (R). Dann stellen wir uns die Frage, in welchen Teil von M die Menge R (die ja als Teil von M definiert ist), liegt. Im Lügnerparadoxon (1.2.3) wird die Gesamtheit aller Aussagen in wahre und falsche aufgeteilt. Eine Aussage, die auf diese Zweiteilung Bezug nimmt (indem sie von sich selbst behauptet, zu den falschen Aussagen zu gehören), wird wieder Element dieser Gesamtheit, wenn man sich die Frage stellt, zu welchem Teil sie gehört. Genauso wird bei Grelling (1.2.5) die Gesamtheit der deutschen Adjektive in zwei Gruppen geteilt, und ein Ele- Abbildung in dieser Leseprobe nicht enthalten ment dieser Gesamtheit (nämlich das Adjektiv heterologisch“), das auf Grund dieser Zweiteilung definiert ist, führt bei der ” tellung, Element welchen

Teiles der Zweiteilung es ist, zum Widerspruch. Ebenso lässt sich Berrys Paradoxon (1.2.6) erklären (Aufteilung aller natürlichen Zahlen in solche, die mit weniger als 26 Silben beschrieben werden können, und solche, die mehr

Silben benötigen - zu welchem Teil gehört die beschriebene Zahl?) und auch das des Proklos (1.2.4) (Teilung aller Urteile in solche, die Protagoras und solche, die seinem Schüler Recht geben - in welchen Teil fällt die richterliche

Entscheidung?).

Russell (1906, 1908) formulierte dieses Problem der Selbstbezüglichkeit in seinem Zirkel-Prinzip (circulus vitiosus)“(zitiert nach [12]): ”

” No total ity can contain m emb ers defi nabl e only in terms of this totality, or members involving or presupposing this totality.“

In der Mengenlehre lassen sich solche Selbstbezüglichkeiten vermeiden, indem man etwa die Elementbeziehungen strenger regelt: Man unterscheidet zwischen den Elementen einer Grundmenge, Mengen von Elementen der Grundmenge, Mengen solcher Mengen usw. Variablen der Elemente der verschiedenen Stufen werden ebenfalls unterschiedlich gekennzeichnet. Damit ist eine Ausdruck x ∈ y nur definiert, wenn y einer Stufe angehört, die um 1 höher ist als die Stufe von x. Die oben angeführten syntaktischen Antinomien können somit nicht mehr auftreten, da Ausdrücke der Form x ∈ x und x ƒ∈ x nicht mehr zulässig sind. Die semantischen Antinomien, die auf einer Vermischung der Bedeutungsebenen beruhen, können ebenfalls nicht mehr entstehen, da die Variablen verschiedener Ebenen strikt getrennt werden. Auf diesen

Überlegungen beruht die Russellsche T y p entheorie.

Es schien, als hätte sich ein brauchbarer Weg gefunden, Antinomien in Zukunft zu vermeiden. Allerdings blieb ein großes Problem noch ungelöst:

Die Analysis fußte selbst auf einigen selbstbezüglichen Definitionen (z. B. die Definition der kleinsten oberen Schranke“). Aus dieser Problematik resultier- Abbildung in dieser Leseprobe nicht enthalten ten drei Haup” ömungen in der mathematischen Grundlagenforschung: der

Logizismus, der Konstruktivismus und der Formalismus.

1.3.3 Der Logizismus

Die These der Logizisten lautete, dass die Mathematik ein Teilgebiet der Logik sei. Aufbauend auf Russells Typentheorie sollte die gesamte Mathematik mittels logischer Schlüsse und Symbolik aufgebaut werden. Die natürlichen Zahlen wurden z. B. über die Kardinalzahlen definiert. (Eine natürliche Zahl ist eine endliche Kardinalzahl, für die das Prinzip der vollständigen Induktion gilt). Um das Problem der selbstbezüglichen Definitionen der Analysis zu lösen, war es jedoch nötig, ein eigenes Axiom einzuführen (das R e duzibilitätsaxiom), das sicherstellte, dass es zu jeder selbstbezüglichen Definition eine äquivalente, nicht-selbstbezügliche gab. Die Entwicklung gipfelte im dreibändigen Werk Principia Mathematica“ von Russell und Alfred North ”

Whitehead (1861–1947). Der Zugang der Logizisten war ein intuitiver: Die

Axiome mussten einfach als wahr akzeptiert werden, oder zumindest als plausible Hypothesen

über die Welt der Zahlen. Der Schönheitsfehler war das

Principia Mathematica“ in der

Reduzibilitätsaxiom. Wie die Autoren der ” zweiten Auflage [14] selbst feststellten:

” This Axiom has a purely pragmatic justification: it leads to the desired res ults, and to no others. But clearly it is not the sort of axiom with

which we can rest content.“

Claus Weyl (1885–1955) meinte 1946, dass im System der Principia Ma- Abbildung in dieser Leseprobe nicht enthalten

” thematica“ die Mathematik nicht mehr länger auf Logik, son vielmehr auf einer Art Paradies der Logiker“ gründe und, wenn man an diese ” transzen- ” dente Welt“ glauben wolle, man genauso gut an die axiomatische Zermelo- Fraenkelsche Mengenlehre glauben könne, die zudem den Vorteil hätte, einfacher im Aufbau zu sein.

1.3.4 Der Konstruktivismus

Schwere Kritik am Logik-fundierten Zugang der Logizisten kam von Seite der Konstruktivisten (auch Intuitionisten). So bestritt Brouwer, dass die Gesetze der Logik, die schließlich auf Aristoteles (384 – 322 v. Chr.) zurückgingen und für endliche Mengen und Teilmengen entwickelt worden war, auch ohne Abstriche für unendliche Mengen gelten sollten. Denn es gibt ja auch andere Prinzipien, die für endliche Mengen Gültigkeit haben, sich aber nicht auf unendliche Mengen übertragen lassen: z. B. das Prinzip, dass das Ganze immer größer ist als ein echter Teil des Ganzen (gilt nicht für bijektive Abbildungen zwischen unendlichen Mengen, s. 1.1), oder dass eine beliebige Menge natürlicher Zahlen immer ein größtes Element enthält.

Ein Prinzip der klassischen Logik, dass Brouwer im Bereich unendlicher

Abbildung in dieser Leseprobe nicht enthalten¹

Eigenschaft E nicht“. Wenn M eine endliche Menge ist, dann gibt es am Gesetz vom Ausgeschlossenem Dritten“ nichts auszusetzen, ist es doch m¨ ” h, jedes Element von M zu betrachten und auf die Eigenschaft E zu untersuchen. Natürlich könnten praktischen Schwierigkeiten auftreten, z. B. wenn M sehr groß ist oder es sehr aufwendig ist festzustellen, ob ein Element von M die

Eigenschaft E besitzt, aber prinzipiell ist diese Untersuchung möglich und es daher gerechtfertigt, zu behaupten, dass entweder A oder ¬ A gelten muss.

Ganz anders sieht es für unendliche Mengen aus. Es ist hier auch prinzipiell unmöglich, alle Elemente zu untersuchen. Für Brouwer ist es daher nur gerechtfertigt, sich eine Meinung über den Wahrheitsgehalt von A zu bilden, wenn es gelingt, ein konkretes Beispiel für ein Element zu finden, das die Eigenschaft E hat, oder durch mathematische Überlegungen zu zeigen, dass jedes Element von M die Eigenschaft nicht- E besitzt (z. B. indem man aus der Annahme, ein beliebiges Element von M hätte die Eigenschaft E, einen Widerspruch herleitet). Es besteht aber kein Grund, zu behaupten, dass eine der beiden Möglichkeiten in jedem Fall durchführbar sein wird. Daher ist es sinnlos, von wahren und falschen Aussagen zu sprechen, sondern vielmehr von beweisbaren und widerlegbaren.

Wieso sollte es auch keine Aussagen in der Mathematik geben, für die (oder auch deren Gegenteil) man niemals einen Beweis würde finden können. Schließlich kannte z. B. die Zahlentheorie einige ungelöste Rätsel, an deren Beweis Generationen von Mathematiker gescheitert waren, wie die Gol db achsche

V ermutung² oder den Gr oßen F ermat³. David Hilbert (1862–1943) meinte zu Brouwer nur abschätzig: ” Da ist das Problem, suche die Lösung. Du kanns t sie du rch reines Denken finden; denn in der Mathematik gibt es kein Ignorabimus⁴ ! “ [9]

Abbildung in dieser Leseprobe nicht enthalten

Die Ablehnung des Gesetz vom Ausgeschlossenem Dritten“ nimmt den Mathematiker ein wicht ” s Werkzeug aus der Hand – die indirekte Beweismethode. (Hilbert formulierte das so: ” Dieses Tertium non datur dem Mathematiker zu nehmen, wäre etwa, wie wenn man dem Astronomen das Fernrohr

o der dem Boxer den Gebrauch der Fäuste untersagen wollte.“ [8]). Ebenso werden Existenzbeweise abgelehnt, die kein Beispiel für ein Objekt, dessen Existenz bewiesen werden soll, liefern oder nicht zumindest eine Methode zur Konstruktion eines solchen. Ein typisches Beispiel wäre der klassische Beweis für die Existenz transzendenter Zahlen:

Es gibt überabzählbar viele reelle Zahlen, die algebraischen Zahlen (das sind die Nullstellen aller Polygone über Q), eine Teilmenge der reellen Zahlen, sind aber abzählbar. Daher muss es noch andere reelle Zahlen geben, eben die transzendenten Zahlen. Q

Da der Beweis keine einzige transzendente Zahl als Beispiel angibt oder eine Konstruktionsmethode, ist er für einen Konstruktivisten wie Brouwer nicht akzeptabel. Dennoch akzeptiert dieser aber die Existenz von transzendenten Zahlen, wie sie ja für konkrete Beispiele (wie π und e) nachweisbar ist.

Der konstruktivistische Zugang Brouwers führte zur Entwicklung einer vollkommen neuen Mathematik, in der sich Konzepte finden lassen, die der klassischen Mathematik fremd sind, und obwohl sie sich als weniger stark und auch schwieriger zu entwickeln erwies, war sie dennoch sehr attraktiv. Als Beispiel sei das Problem des Kontinuums der reellen Zahlen genannt: Es ist in der konstruktivistischen Mathematik nicht möglich, ohne weiteres die Gleichheit oder Ungleichheit zweier reeller Zahlen festzustellen. a ƒ = b meint, dass a = b zu einem Widerspruch führt, während a =// b die wesentlich stärkere Bedingung meint, dass sich ein Beispiel für eine rationale Zahl finden lässt, die zwischen a und b liegt. Es ist klar, dass dadurch der klassische Kontinuumsbegriff durch einen etwas weniger verständlichen und eingängigen ersetzt wird. wir werden es nicht wissen“. ”

Aufgrund der doch einschneidenden Eingriffe Brouwers und seiner Schule in die Begriffswelt der klassischen Mathematik kam es zu Beginn des 20. Jahrhunderts zu einem Expertenstreit, der oft wissenschaftliche Unvoreingenommenheit und Objektivität vermissen ließ und teilweise mit eher unfeinen

Methoden ausgetragen wurde. Hilbert meinte über Brouwers Zugang zur

Mathematik:

” Ich staune unter diesen Umständen darüb er, daß ein Mathematiker an der strengen Gül tigkeit der Schlußweise des Tertium non datur zwei-

felt. Ich staune noch mehr darüb er, daß, wie es scheint, eine ganze Gemeinde von Mathematikern sich heute zusammengefunden hat, die das gleiche tut. Ich staune am meisten über die Tatsache, daß überhaupt auch im Kreise der Mathematiker die Suggestivkraft eines einzelnen temperamentvollen und geistreichen Mannes die unwahrscheinlichsten und exzentrischten Wirkungen auszuüben vermag.“ [8]

” Br ouwer ist nicht, wie Weyl meint, die Revolution, sondern nur die Wie derholung eines Putschversuches mit alten Mitteln, der seinerzeit,

viel schneidiger unternommen, doch gänzlich mißlang und jetzt zumal, wo die Staatsmacht durch Frege, Dedekind und Cantor so wohl gerüstet und befestigt ist, von vornherein zur Erfolglosigkeit verurteilt ist.“ [10]

1.3.5 Der Formalismus (Metamathematik)

Hilbert behagte der radikale Weg der Konstruktivisten um Brouwer ganz und gar nicht. Er meinte: ” A u s dem Paradies, das Cantor uns geschaffen,

soll uns niemand vertreiben können.“ [7]. Er wählte einen anderen Weg, um der Widersprüchlichkeit der klassischen Mathematik zu entgehen, den der formalen Axiomatik. Es sollte ein Axiomensystem angegeben werden, das die gesamte klassische Mathematik umfasste, und zwar in einer formalen Sprache, um den Mehrdeutigkeiten der realen Sprachen, die in der Mathematik immer wieder zur Anwendung kamen, zu entgehen. Danach sollte bewiesen werden, dass diese formalen Axiomatik konsistent, d. h. widerspruchsfrei sei, und zwar unter ausschließlicher Verwendung finiter Methoden, die auch in den Augen der Konstruktivisten unangreifbar sein würden (Hilberts Programm). Um also die Widerspruchsfreiheit einer Theorie zu zeigen, sollte eine Aussage uber die Theorie selbst, d. h. uber alle möglichen Beweise und Herleitungen in dieser Theorie, bewiesen werden. Die Theorie würde selbst zum Objekt einer mathematischen Betrachtung, Hilbert nannte das Metamathematik oder Beweistheorie.

Grundlage sind also nicht irgendwelche Vorstellungen über die Beschaffenheit der Zahlen, ihre unendliche Ausdehnung und ähnliche unzulängliche Begriffe und Objekte, sondern zunächst nur die Zeichen der formalen Sprache ohne weitere Bedeutung. (

[. . . ] am Anfang [. . . ] ist das Zeichen.“ [10])

Abbildung in dieser Leseprobe nicht enthalten

Als Interpretation dieser Ze ” hen soll alles erlaubt sein, was den Axiomen des formalen Systems genügt (d. h. diese in wahre Aussagen über die Objekte der Interpretation übergehen lässt). Wenn das Axiomensystem stark genug ist, um (unter geeigneter Interpretation der Zeichen der formalen Sprache) die Sprache und Begriffswelt der Mathematik abzubilden, dann soll bewiesen werden, dass es nicht möglich ist, mittels der Schlussregeln des formalen Systems (das sind die Regeln, die aus den Axiomen neue Sätze bilden) einen Satz abzuleiten, der (wieder unter der gewählten Interpretation) eine widersprüchliche mathematische Aussage darstellt. Die zur Führung dieses Beweises verwendeten Methoden sollen streng finit sein, d. h. keine unendliche Klasse soll als abgeschlossenen Ganzes betrachtet werden und Existenzbeweise sollen, zumindest im Rahmen einer Konstruktionsvorschrift, ein Beispiel des bewiesenen Objekts angeben.

Anfänglich machte Hilberts Programm gute Fortschritte (so konnte Wilhelm Ackermann (1896–1962) zeigen, dass Guiseppe Peanos (1858–1939) Axiomensystem der Arithmetik (siehe 2.3) eingeschränkt auf die Addition widerspruchsfrei ist). Einen Rückschlag erhielt es aber durch Kurt Gödels

Abbildung in dieser Leseprobe nicht enthalten

(1906–1978) Arbeit ”er formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I“ [5]. Gödel zeigte darin, dass nicht nur die Principia Mathematica, sondern alle widerspruchsfreien formalen Axiomensysteme unvollständig sind, sofern sie mächtig genug sind, die Arithmetik der natürlichen Zahlen darzustellen. Eine ausführliche und (so hoffe ich) verständliche Darstellung des Beweises für den sogenannten Ersten Unvollständigkeitssatz ist Ziel dieser Arbeit.

Kapitel 2

Gr undlagen

Bevor wir zu Gödels Beweis der Unvollständigkeitssätze kommen, sollen einige grundlegende Konzepte erörtert werden, die zum besseren Verständnis des Beweises hilfreich sind. Im ersten Abschnitt werden wir uns mit Cantors Diagonalmethode vertraut machen, die in Gödels Beweis zur Anwendung kommt. Danach beschäftigen wir uns mit formalen Sprachen und Peanos (formalen) Axiomensystem der Arithmetik.

2.1 Cantors Diagonalmethode

Die im folgenden beschriebene Beweismethode geht auf Cantor zurück, der sie verwendete, um die

Überabzählbarkeit der reellen Zahlen zu beweisen.

Diese Methode findet in vielen Beweisen ihre Anwendung, unter anderem im Beweis des Ersten Gödelschen Unvollständigkeitssatzes. Daher soll an Hand von Beispielen versucht werden, die Grundidee dieser Beweismethode herauszuarbeiten.

2.1.1 Die Überabzählbarkeit von R und P(N)

Abbildung in dieser Leseprobe nicht enthalten

Cantor glaubte selbst lange, dass die reellen Zahlen abzählbar sein müssten, ja dass es überhaupt nur eine unendliche Mächtigkeit gebe, nämlich die der natürlichen Zahlen, und sich daher jede unendliche Menge in eine umkehrbar eindeutige Beziehung zu den natürlichen Zahlen setzen lassen müsste. Für die rationalen Zahlen (die intuitiv ja auch ” war das ja auch gelungen:

Abbildung in dieser Leseprobe nicht enthalten

Wenn man die rationalen Zahlen wie oben anordnet und entlang den Pfeilen vorgeht, kann man sie in eine umkehrbar eindeutige Beziehung zu den natürlichen Zahlen setzen und abzählen. (Genaugenommen hat man sogar mehr als die rationalen Zahlen abgezählt, da z. B. 2 / 2 dieselbe Zahl ist wie 3 / 3.) Nachdem Cantors Versuche, eine ähnlich geschickte Anordnung zur

Abzählung der reellen Zahlen zu finden, gescheitert waren, kam ihm die Idee, den Beweis des Gegenteils zu versuchen. Die Methode, die er erfand (oder entdeckte?), war eine indirekte: Er nahm an, es gebe eine Anordnung der reellen Zahlen, die eine Abzählung erlauben würde, und zeigte, dass diese Annahme zu einem Widerspruch führt:

Wir betrachten zuerst nur die reellen Zahlen r im Intervall 0 < r ≤ 1. Jede dieser Zahlen wird durch eine eindeutige unendliche Dezimaldarstellung repräsentiert, also z. B. 0,18327. . . . Wenn eine Zahl eine endliche Dezimaldarstellungen besitzt, dann kann diese durch die entsprechende unendliche ersetzt werden (z. B. ist 0 , 5 = 0 , 49999 . . .). Wir nehmen nun an, die reellen Zahlen des Intervalls sind abzählbar viele, d. h. es ist (theoretisch) möglich, eine Liste mit einer eindeutigen Anordnung dieser Zahlen anzugeben, die keine auslässt:

Abbildung in dieser Leseprobe nicht enthalten

Wir betrachten uns jetzt die Ziffern in der Diagonale und konstruieren damit eine neue reelle Zahl R, indem wir diese Ziffern verändern:

Abbildung in dieser Leseprobe nicht enthalten

Eine mögliche Konstruktionsvorschrift wäre etwa: Wenn die erste Nachkommastelle der ersten Zahl r 1 der Aufzählung (d. i. z 1) nicht 9“ ist, so erhöhen wir sie um Eins, um die erste Nachkommastelle

” 9“, dann

Abbildung in dieser Leseprobe nicht enthalten unserer neuen Zahl R zu bekommen. Lautet die erste Ziffer ” andern wir sie in 0“. Genauso verfahren wir bei der zweiten Nachkommastelle der zwe ” Zahl r (nämlich z 2) und erhalten die zweite Stelle

Abbildung in dieser Leseprobe nicht enthalten von R usw. Allgemein ist also die n-te Nachkommastelle von R gleich (z n + 1 mod 10). Im vorigen Beispiel würde also R folgendermaßen beginnen:

R = 0,1202. . .

Wir überlegen uns, ob R auf unserer Liste schon vorkommt. (Zur Erinnerung: Wir haben angenommen, dass die Liste alle reellen Zahlen des Intervalls (0,1] enthält, und R gehört zu diesem Intervall.) Zweifellos unterscheidet sich R von r 1, denn als erste Nachkommastelle von

Abbildung in dieser Leseprobe nicht enthalten

R wurde eine andere Ziffer gewählt als z 1. R unterscheidet sich aber auch von r 2, und zwar an der zweiten Nachkommastelle. Aufgrund der Konstruktion von R können wir dieses Argument für jedes beliebige Element r n der Liste anführen: R unterscheidet sich von r n sicher an der n-ten Nachkommastelle. Das heißt aber nichts anderes, als das R nicht auf unserer Liste steht im Widerspruch zu der Annahme, alle reellen Zahlen des Intervalls (0,1] aufgezählt zu haben. Es hilft auch nichts, R zur Liste hinzuzufügen: mit der gleichen Methode konstruieren wir eine neue Zahl R t, die dann auch in der erweiterten Liste nicht vorkommt, usw.– die reellen Zahlen des Intervall (0,1] lassen sich nicht abzählen. Und wenn schon eine echte Teilmenge von R überabzählbar viele Elemente enthält, dann erst recht ganz R. Q

Die Frage, ob die Potenzmenge der Menge der natürlichen Zahlen P (N) (also die Menge aller Teilmengen von N) abzählbar ist, konnte Cantor ebenfalls mittels der Diagonalmethode beantworten. Eine schöne Veranschaulichung des Cantorschen Beweises bietet Raymond Smullyan in [15]:

Nehmen wir wieder an, P (N) sei abzählbar. Wir stellen uns nun ein Buch vor, in dem P (N) verzeichnet ist, und zwar folgendermaßen: Auf jeder Seite steht die Beschreibung genau einer Teilmenge von N, keine Menge kommt zweimal vor, es wird aber auch keine mögliche Teilmenge von N ausgelassen. (Da laut Annahme P (N) abzählbar ist, ist so ein Buch vorstellbar, wenn es auch mit seinen unendlich vielen Seiten sehr umfangreich sein würde . . . ) Z. B. könnten die ersten Seiten dieses Buches wie folgt aussehen:

Abbildung in dieser Leseprobe nicht enthalten

: Menge aller durch 7 teilbaren Zahlen

Nun konstruieren wir die Menge S nach folgender Methode: Jede natürliche Zahl n geben wir genau dann zu S dazu, wenn n nicht in der auf der n -ten Seite beschriebenen Menge (S n) enthalten ist. S ist also die Menge aller natürlichen Zahlen n, die nicht Element von S n sind (S = { n | n ∈ / S n }). Im obigen Beispiel sehen die ersten Elemente von

S n so aus: Wir beginnen mit der 1. Ist 1 ein Element der Menge auf

Seite 1 (S 1)? Nein, denn 1 ist keine gerade Zahl, daher kommt 1 zur Menge S. Weiter mit 2. Gehört 2 zu S 2? Ja, denn 2 ist eine natürliche Zahl, und somit nehmen wir 2 nicht in S auf, usw.:

Abbildung in dieser Leseprobe nicht enthalten

Gibt es in unserem Buch eine Seite, auf der die Menge S beschrieben ist? Laut unserer Annahme muss es so sein, denn schließlich verzeichnet das Buch jede Teilmenge der natürlichen Zahlen, und S besteht nur aus solchen Zahlen und ist somit eine Teilmenge von N. Nun, auf der ersten Seite kann S nicht beschrieben sein, denn wenn die 1 Element von S 1 ist, dann gehört sie nicht zu S, und umgekehrt (wie im Beispiel). S kann also unmöglich mit S 1 übereinstimmen. Vielleicht S 2? Nein, denn 2 ist genau dann in S, wenn 2 nicht in S 2 ist, usw. Das Diagonalargument (denn das ist es, wenn auch hier keine Diagonale mehr erkennbar ist) hält für alle natürlichen Zahlen:

Abbildung in dieser Leseprobe nicht enthalten

Die Menge S kann also auf keiner der abzählbar unendlich vielen Seiten des Buches beschrieben sein, obwohl sie eine Teilmenge von P (N) ist. Und wieder ist es sinnlos, S ins Buch aufzunehmen, denn das Diagonalargument lässt sich auch auf das erweiterte Buch anwenden! Unsere Annahme, dass die Menge aller natürlichen Zahlenmengen P (N) abzählbar ist, muss also falsch sein – card (P (N)) > card (N). Q

Man kann leicht zeigen, dass card (P (N)) = 2 ℵ 0 ist und darüberhinaus

card (P (N)) = card (R) (Beweise siehe etwa [12], S. 15f.).

Nachdem die Überabzählbarkeit der reellen Zahlen und der Potenzmenge von N bewiesen war, war es klar, dass es mehr als eine unendliche Mächtigkeit geben musste, nämlich zumindest die Mächtigkeiten der Mengen der natürlichen und der reellen Zahlen. Aber wieso sollten es nicht noch mehr sein als diese zwei? Die Lösung dieser Frage fand Cantor durch eine weitere Anwendung der Diagonalmethode.

2.1.2 Die Überabzählbarkeit von P(M) für unendliche Mengen

Cantor konnte beweisen, dass die Potenzmenge P (M) immer eine höhere Mächtigkeit besitzt als die Ausgangsmenge M, egal ob M endlich ist oder nicht (Cantors Theorem). Für unendliche Mengen verwendete er ebenfalls die Diagonalmethode. (Eigentlich ist der Beweis für die Überabzählbarkeit von P (N) nur ein Spezialfall des folgenden Beweises.) Wieder findet sich eine schöne Veranschaulichung bei Smullyan [15]:

In einem bestimmten Universum bildet jede Menge von Bewohnern einen Verein. Der höchste Verwaltungsbeamte des Universums möchte je den V erein nach einem Bewohner benennen, und zwar so, daß keine zwei Vereine den Namen desselben Bewohners tragen und daß jeder Bewohner ein Namensgeber für einen Verein ist. Es ist nicht unbedingt notwendig, daß die Person ein Mitglied des Vereins ist, der seinen Namen trägt. Nun, für ein Universum mit nur endlich vielen Menschen

ist dies eindeutig unmöglich, denn es existieren mehr Vereine als Bewohner (wenn n die Zahl der Bewohner ist, dann ist 2 n die Zahl der Vereine). Allerdings hat dieses bestimmte Universum unendlich viele Einwohner, und deswegen sieht der höchste Verwaltungsbeamte keinen

Grund, warum dies nicht möglich sein sollte. Jedoch hat bisher jedes Schema, das er ausprobierte, versagt – es blieben immer Vereine übrig. [. . . ]

A ngenommen, das Schema des Verwalters könnte durchgeführt werden. Dann erhalten wir einen Widerspruch wie folgt: Wir nennen einen Einwohner gesellig , wenn er dem nach ihm benannten Verein angehört, sonst nennen wir ihn ungesellig . Weil in diesem Universum je de Menge von Einwohnern einen Verein bildet, bildet auch die Gruppe der ungeselligen Einwohner einen Verein. Dieser Verein ist nach jemandem benannt – sagen wir John . Also is t jedes Mitglie d von Johns Verein ungesellig, und jeder ungesellige Einwohner gehört zu Johns Verein. Ist John gesellig oder nicht? In jedem Fall erhalten wir einen Widerspruch: Nehmen wir zunächst einmal an, John ist gesellig: Dies bedeutet, daß John zu Johns Verein gehört, jedoch gehören nur ungesellige Menschen zu Johns Verein, dies ist also ausgeschlossen. Nehmen wir also an, daß John ungesellig ist: Da jeder ungesellige Einwohner in Johns Verein ist, müßte auch John als ungeselliger Einwohner zu seinem Verein gehören, was ihn aber gesellig macht. Und so ist John weder gesellig noch ungesellig; wir erhalten einen Widerspruch. Deswegen kann das Schema des Verwalters nicht funktionieren.

In mathematischer Terminologie (in Klammern jeweils Smullyans Vergleich) sieht der Beweis folgendermaßen aus:

Sei M eine beliebige unendliche Menge (die Bewohner des gedachten

Universums) und P (M) die Potenzmenge von M (die Vereine im Universum). Wenn beide Mengen dieselbe Mächtigkeit besitzen, heißt das, dass es eine umkehrbar eindeutige Abbildung zwischen ihnen hergestellt werden kann (jeder Verein bekommt den Namen genau eines Bewohners, jeder Bewohner hat genau einen Verein, der nach ihm benannt ist). Nennen wir diese Abbildung f (Schema des Verwalters). Jedem Element V von P (M) wird durch f also genau ein Element e von M zugeordnet: f (V) ›→ e.

Da V als Element der Potenzmenge von M eine Teilmenge von M ist (jeder Verein besteht aus Bewohnern des Universums), kann es sein, dass f (V) = e in V liegt oder nicht (der Einwohner e ist gesellig oder ungesellig). Sei nun U die Menge aller f (V) mit f (V) nicht in V:

U = { f (V) : f (V) ∈ / V }

(der Verein der ungeselligen Einwohner)

U ist eine Teilmenge von M, also ist U auch aus P (M). Wir betrachten nun f (U) (John): nach der Definition von U gilt einerseits

f (U) ∈ U ⇒ f (U) ∈ / U,

(wenn John ungesellig ist, dann ist John gesellig) andererseits aber auch

f (U) ∈ / U ⇒ f (U) ∈ U.

(wenn John gesellig ist, dann ist John ungesellig)

Somit gilt:

f (U) ∈ U ⇔ f (U) ∈ / U , und das ist ein Widerspruch. Q

Wenn aber die Potenzmenge einer beliebigen Menge immer von größerer Mächtigkeit ist als die Menge selbst, dann ist nicht nur card (P (N)) > card (N), sondern auch card (P (P (N))) > card (P (N)) usw. Es ergibt sich eine unendliche Kaskade immer größerer unendlicher Mächtigkeiten: [Abbildung in dieser Leseprobe nicht enthalten]⁵

2.1.3 Die Beweisidee der Diagonalmethode

Wie schon in den letzten zwei Beweisen klar geworden ist, kommt es bei der Diagonalmethode nicht auf eine Diagonale im eigentlichen Sinn an. Wir haben immer mit der Annahme der Existenz einer bijektiven Abbildung mit den natürlichen Zahlen begonnen (eine Aufzählung der reellen Zahlen des Intervalls (0,1], ein Buch mit Beschreibungen aller Teilmengen der natürlichen Zahlen, das Schema des Verwalters). Dann konstruierten wir ein spezielles Objekt (R, S, John bzw. f (U)) unter Verwendung eben dieser bijektiven Abbildung. (Wir benutzten die n-te Ziffer, die Teilmenge auf der n-ten Seite, den Verein der Ungeselligen bzw. U.) Daraus erhielten wir einen Widerspruch, aus dem wir schlossen, das eine bijektive Abbildung wie die vorausgesetzte unmöglich ist. Allerdings ist dies nicht der einzige Schluss, den diese Beweismethode zulässt: Denn wenn die Existenz der Abbildung außer Frage steht, dann muss man daran zweifeln, ob das konstruierte Objekt existiert oder ob es vielleicht bestimmte Bedingungen nicht erfüllt. Diese Varianten werden uns beim Beweis des Ersten Unvollständigkeitssatzes begegnen (s. Kapitel 3).

2.2 Formale Systeme

Um die Prinzipien verstehen zu lernen, die bei der Bildung formaler Systeme zur Anwendung kommen, werden wir zuerst ein sehr einfaches formales System betrachten, das MIU-System (Abschnitt 2.2.1). Um die Schwierigkeiten, die bei der Interpretation von Sätzen formaler Sprachen auftauchen können, zu untersuchen, verwenden wir ein noch aussagekräftigeres formales System, das pg-System (Abschnitt 2.2.2), dass immerhin schon im Stande ist, einfache arithmetische Tatsachen zu formulieren. Diese beiden Systeme sind Douglas

R. Hofstadters Buch [11] entnommen. Im Anschluss daran wird dann eine

Möglichkeit beschrieben, die gesamte Arithmetik zu formalisieren (Peanos formales Axiomensystem der Arithmetik, siehe 2.3).

2.2.1 Das MIU-System

Das erste, was wir zur Bildung eines formalen Systems benötigen, ist eine formale Sprache, bestehend aus einem Vorrat von Zeichen (A lphabet). Durch Aneinanderreihung dieser Zeichen bilden wir Zeichenketten der formalen Sprache. Das erste formale System, dass wir betrachten werden, das MIU-System, begnügt sich mit einem Alphabet bestehend aus den drei Zeichen M, I und U⁶. Daraus lassen sich beispielsweise folgende Ketten der formalen Sprache bilden:

MU verwendet.

UM MUUMUU

IIUMIUUMUIUMMIIUMMIUM

Die Zeichenketten sind also willkürliche Aneinanderreihungen der Zeichen unseres Alphabets. Als Sätze unseres Systems sollen aber nur diejenigen Zeichenketten gelten, die bestimmte Auflagen erfüllen. (Auch in der deutschen Sprache unterscheiden die Regeln der Grammatik einen korrekten, wenn auch sinnlosen Satz wie z.B. Die Herde der blauen Bücher singt in der ersten Reihe“ ” von einer willkürlichen Wortund Zeichenkette wie Die rehcüB BLAU“.)

Abbildung in dieser Leseprobe nicht enthalten

Als nächstens brauchen wir eine Art Grammatik“ für unser System, bestehend aus einer Anzahl von Schlussregel” die die Erzeugung von neuen Sätzen aus schon vorhandenen erlauben. Für das MIU-System sind das die folgenden vier Regeln:

Regel I: Zu einem Satz, deren letzter Buchstabe ein I ist, kann am Ende ein

U hinzugefügt werden. Beispiel:

Aus dem Satz MI wird der Satz MIU.

Regel II: Angenommen, M x ist ein Satz. Dann ist auch M xx ein Satz. Beispiele:

Aus dem Satz MIU wird der Satz MIUIU. Wenn MUM ein Satz ist, dann auch MUMUM. Wenn MU ein Satz ist, dann auch MUU.

In dieser Regel steht der Buchstabe x als Variable für irgendeine Zeichenkette der formalen Sprache. Wenn man sich aber einmal dafür entschieden hat, für welche Kette x steht, muss man natürlich dabei bleiben. (x ist also nicht Teil der formalen Sprache, die ja das Zeichen x gar nicht enthält, son- Abbildung in dieser Leseprobe nicht enthalten dern gehort zu einer Metasprache“, also der Sprache, in der üb er die formale Sprache gesprochen ”ird und in der auch die Regeln abgefasst sind.)

Regel III: Wenn in einem Satz III vorkommt, dann kann man einen Satz bilden, der statt III ein U enthält.

Beispiele:

Wenn UMIIIMU ein Satz ist, dann auch UMUMU. Aus MIIII erhält man MIU (oder auch MUI).

Auf IIMII ist die Regel nicht anwendbar, da die drei I nicht aufeinander folgen.

Aus MU wird nicht MIII – die Regeln gelten nur in einer Richtung!

Regel IV: Wenn in einem Satz UU vorkommt, dann kann man es ersatzlos streichen.

Beispiele:

Wenn MUUU ein Satz ist, dann auch MU. Aus MUUIII wird MIII.

Abbildung in dieser Leseprobe nicht enthalten

Das ist die gesamte Grammatik“ unseres Systems. Wir wollen unser formales MIU-System im ” noch einmal zusammenfassen. Dabei verwenden wir eine etwas formalere“ Schreibweise für die Schlussregeln (der

Abbildung in dieser Leseprobe nicht enthalten

” Ausgangssatz steht üb em Querstrich und der abgeleitete Satz darunter) anstatt der umgangssprachlichen Beschreibung in der obigen Aufzählung. (x

Abbildung in dieser Leseprobe nicht enthalten und y sind wieder Variablen der Metasprache“, die für beliebige Zeichenketten der formalen Sprache des S ” ms stehen.)

MIU-System:

- Alphabet: M, I, U
- Axiome: MI
- Schlussregeln:

Abbildung in dieser Leseprobe nicht enthalten

Die Frage, die uns in weiterer Folge immer wieder interessieren wird, ist nun, ob eine gegebene Zeichenfolge ein Satz eines formalen Systems ist, was nichts anderes bedeutet, als dass die Zeichenkette nach den Regeln des formalen Systems erzeugt werden kann. Wenn es möglich ist, eine explizite schrittweise Aufzählung der Regeln anzugeben, die eine Zeichenfolge als Satz eines gegebenen Systems ausweist, nennen wir das eine A bl eitung des Satzes. (Im Zusammenhang mit aussagekräftigeren formalen Systemen verwenden wir

äquivalent dazu den Begriff Beweis.) Als Beispiel wollen wir den Satz MUIIU im MIU-System ableit en:

Abbildung in dieser Leseprobe nicht enthalten

Als nächstes stellen wir uns die Frage, ob wir die Kette MU erzeugen können, d.h. ob MU ein Satz des MIU-Systems ist (Hofstadters ” - MU

Rätsel“). Der Leser möge es ruhig einmal selbst probieren, um mit dem System ein wenig vertrauter zu werden.

Das MU-Rätsel

Beim Versuch, MU im MIU-System abzuleiten, werden die meisten von uns wohl zuerst ein wenig mit den Regeln des Systems herumspielen. Dabei wird früher oder später ein Muster auffallen, das bei bloßer Betrachtung der Schlussregeln vielleicht nicht gleich ins Auge springt, nämlich das jeder Satz des Systems mit M beginnen muss. Denn das einzige Axiom des Systems,

Abbildung in dieser Leseprobe nicht enthalten

MI, besitzt diese Eigenschaft, und jede Schlussregel vererbt“ sie an einen abgeleiteten Satz weiter. Wenn man das einmal erk ” nt hat, lässt sich ohne weiteres feststellen, das z.B. UM kein Satz sein kann. Auch wenn diese Erkenntnis dem Leser nicht sehr großartig erscheint, ist sie doch etwas, dass der menschlichen Intelligenz zu eigen ist und den Unterschied zu einer maschinellen Herangehensweise ausmacht. Anstatt ständig neue Sätze abzuleiten und zu überprüfen, ob den endlich UM darunter ist (wie es vielleicht ein

Abbildung in dieser Leseprobe nicht enthalten

Computer tun würde), wird ein Mensch früher oder später aus dem System herausspringen“, um einige grundsätzliche Überlegungen ” tellen. Solche

Überlegungen helfen uns auch bei der Lösung des MU-Rätsels:

Die Idee besteht darin, uns die Anzahl der I in einer Zeichenkette des MIU-Systems zu betrachten. Nennen wir diese Zahl den I-Gehalt des Satzes. Somit hat das Axiom MI einen I-Gehalt von 1.

Jetzt überlegen wir uns, was die Schlussregeln mit dem I-Gehalt anstellen. Die Regeln I und IV lassen ihn völlig unverändert. Regel II verdoppelt ihn, Regel III vermindert ihn genau um 3. Wenn wir mittels Regel III einen Satz herleiten wollen, dessen I-Gehalt ein Vielfaches von 3 ist, dann brauchen wir einen Ausgangssatz, dessen I-Gehalt ein Vielfaches von 3 ist. Das Selbe gilt für Regel II. Denn wenn der I-Gehalt des Ausgangssatzes irgendeine Zahl n ist, so verdoppelt Regel II ihn auf 2 n. Wenn aber 2 n ein Vielfaches von 3 sein soll, dann muss auch n ein Vielfaches von 3 sein, da ja 3 kein Teiler von 2 ist.

Da der I-Gehalt mit 1 beginnt (dem I-Gehalt des einzigen Axioms MI), was kein Vielfaches von 3 ist, sehen wir also, dass der I-Gehalt irgendeines Satzes niemals ein Vielfaches von 3 sein kann. Insbesondere ist daher auch ein I-Gehalt von 0 nicht möglich und somit MU kein Satz des MIU-Systems.

Besonders interessant ist, dass wir zur Lösung des MU-Rätsels, einer Fragestellung, die sich auf Zeichenketten eines formalen Systems bezieht, zahlentheoretische Überlegungen heranziehen konnten. Wie wir noch sehen werden

(Abschnitt 3.2), lässt sich jedes Problem in jedem formalen System in die Zahlentheorie einbetten.

Entscheidungsverfahren für formale Systeme

Wir haben nun zwei Möglichkeiten kennengelernt, von Zeichenketten des MIU- Systems festzustellen, ob sie Sätze sind oder nicht. Sie erlauben uns, alle Zeichenketten auszusieben, die nicht M als Anfangsbuchstaben besitzen oder deren I-Gehalt kein Vielfaches von 3 ist. Allerdings bleiben da noch unendlich viele Zeichenketten,

über die wir nichts wissen. Wie steht es z.B. mit

Satz- MUIUIIIUUUII. Ist das ein Satz oder doch nicht? Gibt es einen Test für ” heit“? Eine Möglichkeit wäre, einen Computer auf das Problem anzusetzen und systematisch alle möglichen Sätze zu erzeugen. Z. B. könnte er so vorgehen:

Schritt 1: Wende jede anwendbare Regel auf das Axiom MI an. Das ergibt zwei neue Sätze: MIU, MII.

Schritt 2: Wende jede anwendbare Regel auf die im Schritt 1 erzeugten Sätze an. Das ergibt drei neue Sätze: MIUIU, MIIU, MIIII.

Schritt 3: Wende jede anwendbare Regel auf die im Schritt 2 erzeugten Sätze an. Das ergibt sechs neue Sätze: MIUIUIUIU, MIIUIIU, MIIIIU, MIIIIIIII, MIU, MUI. usw.

Früher oder später erzeugt dieses Verfahren jeden einzelnen Satz, weil die Regeln in jeder möglichen Form angewandt werden. Allerdings ist nicht klar, wie lange man darauf warten muss, dass ein bestimmter Satz in der Liste erscheint, denn die Sätze werden gemäß der Kürze ihrer Ableitung erzeugt.

Unser Test für Satzheit“ würde also lauten:

”

Warte, bis die fragliche Kette erzeugt wurde; wenn das geschieht, ist die Kette ein Satz – und wenn es nie geschieht, dann ist sie kein Satz.

Wir sehen schon, dass dieser Test im Allgemeinen nicht sehr sinnvoll ist, denn er setzt voraus, dass wir im Zweifelsfalle unendlich lang auf ein Ergebnis warten können. Von entscheidender Wichtigkeit ist also eine Garantie, dass wir die Antwort in endlicher Zeit erhalten. Wenn es einen Test gibt, der innerhalb einer endlichen Zeitspanne entscheidet, ob eine Zeichenkette ein Satz ist, dann nennen wir ihn ein Entscheidungsverfahren für das vorliegende formale System.

2.2.2 Das pg-System

Das MIU-System erlaubte uns, einige grundlegende Begriffe im Zusammenhang mit formalen Systemen zu studieren. Andererseits war es doch ein wenig an den Haaren herbeigezogen und bedeutungsleer (eben sehr formal). Das im Folgenden beschriebene pg-System wird uns die Möglichkeit geben, eine

Vorstellung von der Leistungsfähigkeit formaler Systeme zu erhalten und zu verstehen, warum sie für die Mathematiker von Interesse sind.

Auch das pg-System besitzt ein Alphabet, das nur aus drei Symbolen besteht: p, g und –. Im Unterschied zum MIU-System besitzt es aber eine unendliche Anzahl von Axiomen. Da wir nicht alle niederschreiben können, brauchen wir eine Methode, um sie zu beschreiben; ja mehr noch, wir brauchen eine Methode, um in endlicher Zeit entscheiden zu können, ob eine Zeichenkette ein Axiom ist oder nicht, also ein Entscheidungsverfahren für Axiomheit“. Folgendes Axiomenschema liefert uns ein solches Verfahren: ”

Definition : x p – g x – ist ein Axiom, wenn x nur aus Bindestrichen besteht.

Beispiele:

Abbildung in dieser Leseprobe nicht enthalten

ist kein Axiom, dieser Ausdruck ist nicht einmal eine Kette des pg-Systems (das Axiomenschema gehört zur Metasprache“ des Systems) ”

Von jeder Zeichenkette kann jetzt ohne Schwierigkeiten festgestellt werden, ob sie ein Axiom ist: Als erstes muss eine Anzahl von Bindestrichen stehen (etwa n), dann die Zeichenfolge p – g und danach genau n +1 Bindestriche. Da nur endlich viele Bindestriche vorkommen, kann man sie zählen und die Anzahl vergleichen (auch wenn es vielleicht sehr lange dauert); daher kommt dieses Entscheidungsverfahren sicher in endlicher Zeit zu einem Ende.

Die Sätze des pg-Systems entstehen durch Anwendung einer einzigen Schlussregel:

Regel : Angenommen, x, y, und z stehen für Zeichenketten, die nur aus Bindestrichen bestehen, und man weiß, dass x p y g z ein Satz ist. Dann ist auch x p y – g z – ein Satz.

Beispiel:

Abbildung in dieser Leseprobe nicht enthalten

Wir werden uns jetzt ein Entscheidungsverfahren für Sätze des pg-Systems überlegen. Als erstes fällt auf, dass bestimmte Zeichenketten sicher kein Satz sein können, zum Beispiel solche, die mehr als ein p oder ein g enthalten. Eine Kette, die überhaupt in Frage kommt, ein Satz zu sein, muss also schon geformalen Ansprüchen“ genügen: Als erstes muss eine Bindestrichkette stehen,” kommt genau ein p, danach wieder eine Bindestrichkette, dann dann genau ein g und schließlich wieder eine Bindestrichkette.

[...]

---

¹ lat. etwa: ein Drittes gibt es nicht“. ”

² Die (auch heute noch) unbewiesene Vermutung Christian Goldbachs (1690–1764) besagt, dass jede gerade natürliche Zahl größer 2 Summe zweier Primzahlen ist.

³ Pierre de Fermat (1601–1665) hatte behauptet, dass die Gleichung x n + y n = z n für ganze Zahlen x, y, z und für n > 2 nicht lösbar ist. Dies notierte er an den Rand eines Buches mit der Bemerkung, er hätte einen wirklich wunderbaren Beweis für diesen Satz gefunden, doch sei der Rand leider zu schmal, ihn zu fassen. Aus heutiger Sicht muss man wohl vermuten, dass Fermat hier irrte, gelang es doch erst vor einigen Jahren, diesen Satz unter Benutzung aufwändiger und modernster mathematischer Methoden zu beweisen. Doch die Suche nach Fermats elementaren Beweis war dennoch äußerst fruchtbar für die Zahlentheorie.

⁴ lat.

⁵ Ob ℵ 1, die nächstgrößte unendliche Mächtigkeit nach ℵ 0, zwischen ℵ 0 und 2 ℵ 0 liegt oder ob ℵ 1 = 2 ℵ 0 ist, konnte Cantor nicht mehr beweisen. Er vermutete aber, dass der zweite Fall zutreffen würde. Diese Kontinuumshypothese beschäftigte viele große Mathematiker unseres Jahrhunderts (darunter auch Gödel) und wurde erst 1963 von Paul Cohen (∗ 1934) vollständig geklärt – allerdings anders, als viele Mathematiker vermutet hätten (s. 4.2).

⁶ In weiterer Folge wird für Zeichen einer formalen Sprache die Schriftart Formale Syntax