5/13/2018 Diagonalsierung-Gödel-Stegmüller-ChristensenEDS - slidepdf.com

http://slidepdf.com/reader/full/diagonalsierung-goedel-stegmueller-christenseneds 1/49

 

Gödel-Stegmüller 

– Strukturalismus– Systemtheorie (z.B. Nach Mario Bunge)– Die Sinnlosigkeit des Wittgensteinschen Axiomensystem.– Die Paradoxer deutscher Rechtstheorien in der IT ("Abstrahlsicherheit").– Das Meta im Rechtsstaat besteht in der Beschreibung der Objekte, in ihrer 

subjektiven Wahrnehmung. Warum sollen Menschen determiniert werden? Warumdeterminieren wir nicht die Maschinen rechtskonform?

– Es folgt die Frage, wie mache ich mich den RichterInnen als Informatiker und nichtals Submillimeteringenieur verständlich? Ganz einfach: Lassen Sie diesemenschenverachtende Technik zerstören. Die passt nicht zum Rechtsstaat,ansonsten sehe ich folgende "Blauri" - Delirium vor mir.

– Auch Mario Diekmann @ Hausjurist im BVA versuchte sich schon am

Täterstrafrecht gegen Leibnitz. Leibnitz ist eine gemeinsame Wertschätzung zumwulffen.

Warum? Eine Theorie zur politischen Teilhabe im Spähangriff 

Unvollständigkeit und Unentscheidbarkeit. Die metamathematischen Resultate von Gödel,Church, Kleene, Rosser und ihre erkenntnistheoretische Bedeutung. - 1. Auflage 1959. 3. Auflage. - Springer-Verlag, Wien, New York, 1973. ISBN 3-211-81208-3. 116 S. 

Lesen Sie doch meine Diagonalisierung in den Stellungnahmen. Frau nach Jürgen

Habermas, vieldemensionale Menschen diagonalisieren auf verschiedenenWirklichkeitsebenen und dazu gehört die Internet Community.

http://de.wikipedia.org/wiki/Wolfgang_Stegm%C3%BCller  

Wolfgang Stegmüller 

Wolfgang Stegmüller (* 3. Juni 1923 in Natters, Tirol; † 1. Juni 1991 in München) war eindeutsch-österreichischer Philosoph mit bedeutenden Beiträgenzur Erkenntnistheorie, Wissenschaftstheorieund zur Analytischen Philosophie. Mit seinemWerk Hauptströmungen der Gegenwartsphilosophie hat Stegmüller einer deutschsprachigen Leserschaft den Zugang zur Analytischen Philosophie geöffnet.

5/13/2018 Diagonalsierung-Gödel-Stegmüller-ChristensenEDS - slidepdf.com

http://slidepdf.com/reader/full/diagonalsierung-goedel-stegmueller-christenseneds 2/49

 

Inhaltsverzeichnis[Verbergen] 

• 1 Leben• 2 Wissenschaftliche Arbeitsfelder • 3 Werk (Auswahl)• 4 Literatur • 5 Weblinks• 6 Einzelnachweise

Leben [Bearbeiten]

Wolfgang Stegmüller studierte an der Universität Innsbruck Wirtschaftswissenschaften undPhilosophie. 1944 erlangte er einen Abschluss als Diplom-Volkswirt, ein Jahr später erreichte er das wirtschaftswissenschaftliche Doktorat. Ebenfalls an der UniversitätInnsbruck promovierte er 1947 zum Doktor der Philosophie und habilitierte sich 1949 mitdem Thema Sein, Wahrheit und Wert in der heutigen Philosophie.

Nach einem einjährigen Aufenthalt an der Universität Oxford kehrte Stegmüller 1954 andie Universität Innsbruck zurück, wo er 1956 zum Titular-Professor für Philosophie ernanntwurde. Nach Zwischenaufenthalten als Gastprofessor an denUniversitäten Kiel und Bonn erhielt er einen Ruf an die LMU München, wo er 1958 zumOrdinarius für Philosophie, Logik und Wissenschaftstheorie und zum Vorstand desSeminars II wurde. Unterbrochen wurde sein Wirken in München durch zweiGastprofessuren in den Jahren 1962/63 und 1964 an der University of Pennsylvania. Von1977 bis 1979 war er auch Dekan der Fakultät für Philosophie, Wissenschaftstheorie undStatistik.

Stegmüller war von 1966 an korrespondierendes Mitglied der Österreichischen Akademieder Wissenschaften und seit 1967 Mitglied der Bayerischen Akademie der Wissenschaften. Von 1972 an war er Mitglied am Institut International de Philosophie inParis.

1989 wurde Stegmüller zum Ehrendoktor der Universität Innsbruck ernannt. 1990 wurde er an der LMU emeritiert und im selben Jahr zum Ehrenpräsidenten der Gesellschaft für Analytische Philosophiegewählt. Sein Grab liegt auf dem Friedhof von Gräfelfing.[1]

Die Gesellschaft für Analytische Philosophie vergibt seit 1994 den nach ihmbenannten Wolfgang-Stegmüller-Preis zur Förderung des wissenschaftlichenNachwuchses.

Stegmüller hat achtzehn seiner Schüler habilitiert und damit eine beträchtliche Wirkung

entfaltet, wenngleich es keine Stegmüller-Schule gibt. Gemeinsam ist allen seinenSchülern jedoch die Orientierung an der analytischen Philosophie und die Insistenz auf formalen Verfahren. Zu den Schülern zählen: Wolfgang Balzer , Ulrich Blau, KlausButzenberger , Max Drömmer , Wilhelm Essler ,Peter Hinst, Norbert Hoerster , AndreasKamlah, Godehard Link, Georg Meggle, Carlos Ulises Moulines, Felix Mühlhölzer , MihaiNadin, Wolfgang Röd, Julian Nida-Rümelin, Matthias Varga von Kibed,Franz vonKutschera, Eike von Savigny, Reinhard Werth und Wolfgang Spohn.

Wissenschaftliche Arbeitsfelder [Bearbeiten]

Stegmüller wurde am Anfang seiner Laufbahn im Jahr 1948 von Karl Popper auf den Logischen Positivismus aufmerksam gemacht, dessen philosophische Position nach

dem Zweiten Weltkrieg in Deutschland nahezu unbekannt war. In der Folge orientierte er sich dann insbesondere an Rudolf Carnap, ohne jedoch die politischen und anti-metaphysischen Auffassungen des Wiener Kreises aufzunehmen. Nach eigener Auskunft

5/13/2018 Diagonalsierung-Gödel-Stegmüller-ChristensenEDS - slidepdf.com

http://slidepdf.com/reader/full/diagonalsierung-goedel-stegmueller-christenseneds 3/49

 

ergab sich für ihn der Anschluss an Carnap daraus, dass von den in Frage kommendenPositionen einerseits Wittgenstein eine streng wissenschaftliche Philosophe für unmöglichhielt und Popper andererseits der Sprachphilosophie keine besondere Bedeutung zumaß.Mit seinen Publikationen trug Stegmüller maßgeblich zur Kenntnisnahme und Verbreitungder Analytischen Philosophie und der Wissenschaftstheorie im deutschsprachigen Raumbei. Bereits in seiner Antrittsvorlesung erwähnte Stegmüller die vier Probleme der 

Erkenntnistheorie, welche später zentrale Punkte in seinen Arbeiten werden sollten:• Induktionsproblem• Basisproblem der Erfahrung• Problem der theoretischen Begriffe• Problem der wissenschaftlichen Erklärung

Die philosophischen Arbeitsgebiete Stegmüllers überspannen einen weiten Bereich.Neben umfangreichen Arbeiten zur Gegenwartsphilosophie publizierte er ausführlich zuden Grundlagen der Logik, der Erkenntnistheorie und der Wissenschaftstheorie.

Logik

W. Stegmüller trug durch seine Bücher Das Wahrheitsproblem und die Idee der Semantik (1957) und Unvollständigkeit und Unentscheidbarkeit (1959) dazu bei, dass dieIdeen von Alfred Tarski undRudolf Carnap auf dem Gebiet der Semantik und der Logik,sowie Kurt Gödels Beiträge zur Mathematischen Logik einem deutschsprachigen Publikumzugänglich wurden. Weitere wichtige Beiträge auf diesem Gebiet sind sein Artikel Die Antinomien und ihre Behandlung (1955) und das von ihm mitverfasste Buch Strukturtypender Logik (1961).

Erkenntnistheorie

Eines der einflussreichsten Werke Stegmüllers ist sein erstmals 1954 veröffentlichtes Buch"Metaphysik, Skepsis, Wissenschaft", in dem er die erkenntnistheoretischen Grundlagen

der drei Gebiete darstellt. Er zeigt hier, dass die Suche nach diesenerkenntnistheoretischen Grundlagen unweigerlich zum Problem der Evidenz führt, welcheser für nicht lösbar hält. Auch die Möglichkeit einer Lösung durch den Nachweis der Selbstwidersprüchlichkeit der universellen Erkenntnisskepsis schließt er aus, selbst wenndiese Selbstwidersprüchlichkeit wirklich gegeben wäre. Vielmehr kommt er zu demSchluss, dass ein universeller Erkenntnisskeptizismus widerspruchsfrei vertreten werdenkann, sofern man auf eine Begründung dieser Position verzichtet. Trotz der Unlösbarkeitdes Problems der Evidenz seien Evidenzvoraussetzungen sowohl für Metaphysik, alsauch für Wissenschaft unentbehrlich; beide können nach Stegmüller also letztlich nichtbegründet werden, sondern setzen bereits eine Entscheidung voraus.

Ein weiterer Arbeitsschwerpunkt Stegmüllers lag in der Auseinandersetzung mitdem Phänomenalismus. In einer Publikation "Der Phänomenalismus und seineSchwierigkeiten" im Jahre 1958 beschreibt er die extremen Schwierigkeiten, welche einer konsequenten Durchführung des phänomenalistischen Programms entgegenstehen.

Wissenschaftstheorie

Stegmüller gilt als einer der bedeutendsten Wissenschaftstheoretiker in der zweiten Hälftedes 20. Jahrhunderts. Es ist besonders sein Verdienst, dass die Probleme und Resultateder Wissenschaftstheorie und der Analytischen Philosophie im deutschsprachigen Raumeinem weiten Publikum bekannt wurden.

Prägend für Stegmüllers Arbeiten in der Wissenschaftstheorie sollte dabei die

Veröffentlichung der Bücher The Structure of Scientific Revolutions von Thomas S.Kuhn im Jahre 1962 und The Logical Structure of Mathematical Physics von Joseph D.Sneed im Jahre 1971 werden. Während Kuhns Publikation ihn nach eigenen Angaben in

5/13/2018 Diagonalsierung-Gödel-Stegmüller-ChristensenEDS - slidepdf.com

http://slidepdf.com/reader/full/diagonalsierung-goedel-stegmueller-christenseneds 4/49

 

eine tiefe geistige Krise verstrickte, sah er in den Ideen Sneeds sowohl einen Ausweg ausder Rationalitätskrise der Wissenschaften - welche oft aus Kuhns Publikationherausgedeutet wurde - als auch eine angemessene Antwort auf das Problemder theoretischen Begriffe. Die Ausarbeitung der Sneedschen Ideen durch ihn und seinenUmkreis ist heute als wissenschaftstheoretischer Strukturalismus eine bedeutendeRichtung innerhalb der Wissenschaftstheorie.

Werk (Auswahl) [Bearbeiten]

• Hauptströmungen der Gegenwartsphilosophie. 1. Auflage Humboldt-Verlag, Wien,Stuttgart 1952. Zweite neubearbeitete und erweiterte Auflage 1960 bei Kröner,Stuttgart mit weiteren, teilw. wesentlich erweiterten Auflagen bis zur vierbändigenAusgabe 1989 ISBN 3-520-30807-X

• Metaphysik - Skepsis - Wissenschaft . Humboldt-Verlag, Frankfurt/Main 1954.• Sprache und Logik . In: Studium Generale, Band 9, 1956.• Das Universalienproblem, einst und jetzt . 2 Teile. In: Archiv für Philosophie,

Stuttgart, Band 6, 1956; Band 7, 1957.• Das Wahrheitsproblem und die Idee der Semantik . Springer, Wien 1957.• Unvollständigkeit und Unentscheidbarkeit. Die metamathematischen Resultate von

Gödel, Church, Kleene, Rosser und ihre erkenntnistheoretische Bedeutung. - 1. Auflage 1959. 3. Auflage. - Springer-Verlag, Wien, New York, 1973. ISBN 3-211-81208-3. 116 S.

• Glauben, Wissen und Erkennen. Wissenschaftliche Buchgesellschaft, Darmstadt1965

• Einheit und Problematik der wissenschaftlichen Welterkenntnis. Hueber, München1967

• Der Phänomenalismus und seine Schwierigkeiten. WissenschaftlicheBuchgesellschaft, Darmstadt 1969

•  Aufsätze zur Wissenschaftstheorie. Wissenschaftliche Buchgesellschaft, Darmstadt1970.

•  Aufsätze zu Kant und Wittgenstein. Wissenschaftliche Buchgesellschaft, Darmstadt1970.

• Probleme und Resultate der Wissenschaftstheorie und Analytischen Philosophie• Band I, Erklärung-Begründung-Kausalität , 1983• Band II, Theorie und Erfahrung , 1974

• 1. Teilband: Theorie und Erfahrung , 1974• 2. Teilband: Theorienstrukturen und Theoriendynamik , 1985• 3. Teilband: Die Entwicklung des neuen Strukturalismus seit 1973,

1986• Band III, Strukturtypen der Logik ,1984• Band IV, Personelle und statistische Wahrscheinlichkeit , 1973

• 1. Halbband: Personelle Wahrscheinlichkeit und rationaleEntscheidung , 1973

• 2. Halbband: Statistisches Schließen - Statistische Begründung -Statistische Analyse, 1973

• Das Problem der Induktion. Humes Herausforderung und moderne Antworten.Wissenschaftliche Buchgesellschaft, Darmstadt 1975.

• The Structure and Dynamics of Theories. Springer, Berlin 1976.•

Rationale Rekonstruktion von Wissenschaft und ihrem Wandel . Reclam, Stuttgart1979• Neue Wege der Wissenschaftsphilosophie. Springer, Berlin 1979.

5/13/2018 Diagonalsierung-Gödel-Stegmüller-ChristensenEDS - slidepdf.com

http://slidepdf.com/reader/full/diagonalsierung-goedel-stegmueller-christenseneds 5/49

 

• The Structuralists View of Theories. Springer, Berlin 1979• Philosophy of Economics. Springer, Berlin 1982• Kripkes Deutung der Spätphilosophie Wittgensteins. Kommentarversuch über einen

versuchten Kommentar. Kröner, Stuttgart 1986.Literatur [Bearbeiten]

•

C.G. Hempel, H. Putnam, W.K. Essler: Methodology, Epistemology, and Philosophy of Science: Essays in Honour of Wolfgang Stegmüller on the Occasion of his 60thBirthday, June 3rd, 1983. Reprinted ... Journal Erkenntnis, Vol. 19, Nos. 1,2 and 3. Springer Verlag (1983) ISBN 90-277-1646-3

• R. Kleinknecht: Nachruf auf Wolfgang Stegmüller , Journal for General Philosophy of Science, Vol. 24, 1-16, (1993)

• Wolfgang Stegmüllers Erbe(n). Ein Gespräch zwischen Franz von Kutschera,Carlos Ulises Moulines, Wolfgang Spohn und Hans Rott. Information Philosophie, 2,110-115, (2004). [1]

Weblinks [Bearbeiten]

•

Literatur von und über Wolfgang Stegmüller im Katalog der DeutschenNationalbibliothek• Nachlass im Brenner-Archiv der Universität Innsbruck

Einzelnachweise [Bearbeiten]

1. ↑ Gerd Otto-Rieke: Gräber in Bayern. München 2000. S.26.

http://de.wikipedia.org/wiki/G%C3%B6del,_Escher,_Bach 

Gödel, Escher, Bach

Gödel, Escher, Bach – ein Endloses Geflochtenes[1] Band, kurz GEB, ist ein Buch

von Douglas R. Hofstadter aus dem Jahr 1979. Der Originaltitel lautet: Gödel, Escher,Bach – An Eternal Golden Braid .

5/13/2018 Diagonalsierung-Gödel-Stegmüller-ChristensenEDS - slidepdf.com

http://slidepdf.com/reader/full/diagonalsierung-goedel-stegmueller-christenseneds 6/49

 

Inhaltsverzeichnis[Verbergen]

• 1 Hintergrund• 2 Anhang

• 2.1 Werksausgaben• 2.2 Quellen• 2.3 Weblinks

Hintergrund [Bearbeiten]

Die deutsche Übersetzung erschien 1985. Hofstadter sieht in bestimmtenselbstbezüglichen Mustern, den von ihm so genannten Seltsamen Schleifen, denSchlüssel zum Verständnis vonPhänomenen wie Sein oder Bewusstsein. Er stellt dieseMuster in seinem Buch vor.

Seine Systematik verbindet das mathematische Werk Kurt Gödels mit den kunstvollenIllustrationen M. C. Eschers und der Musik Johann Sebastian Bachs. Diese

schöpferischen Werke setzt er in Beziehung zur Informatik, wie selbstbezüglichenComputerprogrammen, den so genannten Quines, und den Strukturen der DNA, mithinder Molekularbiologie.

Jedem Kapitel geht ein kurzer Dialog mit den Hauptfiguren Achilles und TheoSchildkröte voran, in dem das Thema des Kapitels spielerisch veranschaulicht wird. Diesgeschieht durch die geschilderten Ereignisse, aber teilweise auch durch literarischeStilmittel.

Das Buch wurde in Deutschland ein Bestseller und stand für fünf Monate auf Platz 1. 1980wurde es mit dem Pulitzer-Preis in der Kategorie General Non-Fiction und dem AmericanBook Award in der Kategorie Science Hardback ausgezeichnet.

Anhang [Bearbeiten]

Werksausgaben [Bearbeiten]

• Douglas R. Hofstadter: Gödel, Escher, Bach: An Eternal Golden Braid . BasicBooks, 1979, ISBN 978-0-4650-2685-2.

• Douglas R. Hofstadter: Gödel, Escher, Bach: An Eternal Golden Braid (Jubiläumsausgabe mit neuem Vorwort des Autors). Vintage Books, 1989, ISBN978-0-3947-5682-0.

• Douglas R. Hofstadter: Gödel, Escher, Bach. ein Endloses Geflochtenes Band .18. Auflage. Klett-Cotta, 2008 (Originaltitel: Gödel, Escher, Bach: An Eternal Golden

Braid ), ISBN 978-3-6089-4442-6.Quellen [Bearbeiten]

1. ↑ Diese Großschreibung entspricht dem Titel der deutschen ErstausgabeWeblinks [Bearbeiten]

• en:File:GEBcover.jpg – Bild des Bucheinbandes in der englischsprachigenWikipedia

Diagonalisierungsverfahren

5/13/2018 Diagonalsierung-Gödel-Stegmüller-ChristensenEDS - slidepdf.com

http://slidepdf.com/reader/full/diagonalsierung-goedel-stegmueller-christenseneds 7/49

 

- http://www.mathematik.uni-ulm.de/stochastik/lehre/ws05_06/statistik2old/skript/node7.html 

Nächste Seite: Symmetrie und Definitheit; Faktorisierung Aufwärts: Einige Grundbegriffeund Ergebnisse Vorherige Seite: Eigenwerte und Eigenvektoren  Inhalt 

Diagonalisierungsverfahren

•Sei nun eine invertierbare symmetrische Matrix.

•In Lemma 1.4 haben wir gezeigt, dass dann sämtliche Eigenwerte

von reelle Zahlen sind (wobei in dieser Folge gegebenenfalls einunddieselbeZahl mehrfach auftreten kann).•Wegen ist keine Lösung von (3), d.h., sämtliche

Eigenwerte von sind von Null verschieden.•Außerdem kann man zeigen, dass es orthonormale (Basis-)Vektoren gibt, d.h.

mit (6)

so dass ein zu gehörender Eigenvektor ist; .

•

Wenn sämtliche Eigenwerte voneinander verschieden sind, dann folgtdies unmittelbar aus Teilaussage 2 von Lemma 1.4.•Hieraus resultiert das folgende Diagonalisierungsverfahren für invertierbaresymmetrische Matrizen.

Lemma 1.5 

• Sei eine invertierbare symmetrische Matrix, und sei

die Matrix, die aus den orthonormalen Eigenvektoren besteht.

• Dann gilt

(7)

wobei die Diagonalmatrix bezeichnet, die aus den

Eigenwerten gebildet wird.

Beweis 

•

Aus der Defintionsgleichung (2) von Eigenwerten bzw. -vektoren ergibt sich,dass für jedes .

5/13/2018 Diagonalsierung-Gödel-Stegmüller-ChristensenEDS - slidepdf.com

http://slidepdf.com/reader/full/diagonalsierung-goedel-stegmueller-christenseneds 8/49

 

• Hieraus folgt, dass

bzw. , wobei sich die letzte Gleichheit aus

(6) ergibt.

Cantor-Diagonalisierung

Als Cantor-Diagonalisierung werden zwei von Georg Cantor entwickelteDiagonalisierungsbeweisverfahren bezeichnet:

• Cantors erstes Diagonalargument ist ein mathematisches Beweisverfahren, mitdem man zeigen kann, dass eine Menge abzählbar ist.

• Cantors zweites Diagonalargument ist ein mathematischer  Beweis dafür, dass dieMenge der reellen Zahlen überabzählbar ist. Dieser Beweis ist auch unter demNamen Diagonalisierung bekannt. Der Mathematiker Georg Cantor fand ihn imJahr 1877.

Verwandte Themen [Bearbeiten]

• Cantorsche Paarungsfunktion• Cauchy-Produktformel

Cantors erstes Diagonalargument

Cantors erstes Diagonalargument ist ein mathematisches Beweisverfahren, mit demman ggf. zeigen kann, dass zwei unendliche Mengen gleichmächtig sind.

Entwickelt wurde dieses Verfahren von Georg Cantor .

Zum Verständnis der Problematik und des Beweises ist es notwendig, dieunspezifizierte Größe einer Menge durch die in der Mengenlehre formaldefinierte Mächtigkeit zu ersetzen:

Zwei Mengen sind genau dann gleichmächtig, wenn jedem Element der einen

Menge genau ein Element der anderen Menge zugeordnet werden kann, und umgekehrt ebenso, wenn also eineBijektion zwischen den Mengen existiert.

Während dies bei Mengen mit endlich vielen Elementen klar ist ({1,2,3} und {6,8,10} sindgleichmächtig), wird bei Mengen mit unendlich vielen Elementen die Problematikoffensichtlich.

Beispielsweise sind die Menge der natürlichen Zahlen und die Menge der positivengeraden Zahlen gleichmächtig, denn man kann umkehrbar eindeutig jeder natürlichenZahl i ihr Doppeltes 2·i zuordnen, obwohl die positiven geraden Zahlen echt in dennatürlichen Zahlen enthalten sind.

5/13/2018 Diagonalsierung-Gödel-Stegmüller-ChristensenEDS - slidepdf.com

http://slidepdf.com/reader/full/diagonalsierung-goedel-stegmueller-christenseneds 9/49

 

Inhaltsverzeichnis

[Verbergen]• 1 Vorgehen

bei Cantorserstem

Diagonalargument

• 2 Mächtigkeitder reellenZahlen

• 3 Verallgemeinerung deserstenCantorschenDiagonalargumentes

• 4 VerwandteThemen

Vorgehen bei Cantors erstem Diagonalargument [Bearbeiten]

Cantors Verfahren wird am besten mit der einfachsten unendlich großen Menge, der Menge der natürlichen Zahlen, und der Menge der positiven Brüche veranschaulicht. Die

Aussage ist, dass die Menge der natürlichen Zahlen und die Mengeder positiven rationalen Zahlen gleichmächtig sind.

Dies lässt sich zeigen, indem man die Brüche folgendermaßen in einemzweidimensionalen Schema anordnet:

Dieses Schema zählt man dann diagonal ab, wobei man nicht vollständig gekürzte Brücheüberspringt:

Man erhält auf diese Weise eine Abzählung der positiven rationalen Zahlen:

Durch das Überspringen kürzbarer Brüche liegt für jede positive rationale Zahl genau einRepräsentant (der nicht mehr kürzbare Bruch) in dieser Abzählung, wodurch diegewünschte Bijektion hergestellt ist.

Um die Gleichmächtigkeit aller rationalen Zahlen und der natürlichen Zahlen zu zeigen,erweitert man diese Abzählung. Vor die Eins fügt man eine Null ein und hinter jeder Zahl

deren Negatives:

5/13/2018 Diagonalsierung-Gödel-Stegmüller-ChristensenEDS - slidepdf.com

http://slidepdf.com/reader/full/diagonalsierung-goedel-stegmueller-christenseneds 10/49

 

Man erhält damit eine Bijektion zwischen der Menge der natürlichen Zahlen und der Menge der rationalen Zahlen, was bedeutet, dass diese beiden Mengen gleichmächtigsind. Diese Aussage zählt zu den wichtigsten mathematischen Theoremen.

Mengen, welche gleichmächtig zur Menge der natürlichen Zahlen sind,heißen abzählbar (oder abzählbar unendlich). Mengen, welche gleichmächtig zuirgendeiner Teilmenge der natürlichen Zahlen sind, heißen höchstens abzählbar (manchebezeichnen das auch als abzählbar ). Mengen, welche gleichmächtig zu einer beschränkten Teilmenge der natürlichen Zahlen sind, sind endlich. Die Menge der rationalen Zahlen ist also abzählbar.

Unendliche Mengen widersprechen oft der Intuition. Das wird beispielsweisedurch Hilberts Hotel veranschaulicht.

Mächtigkeit der reellen Zahlen [Bearbeiten]

Die Menge der reellen Zahlen ist zur Menge der natürlichen Zahlen nicht

gleichmächtig, deshalb ist die Menge überabzählbar . Man sagt auch, diereellen Zahlen haben die Mächtigkeit desKontinuums.

Der Beweis der Überabzählbarkeit von ist Inhalt des zweiten CantorschenDiagonalbeweises.

Verallgemeinerung des ersten Cantorschen Diagonalargumentes [Bearbeiten]

Das erste Cantorsche Diagonalargument kann man verallgemeinern, um vergleichbareAussagen über Mengen von Tupeln reeller Zahlen zu machen.

Die folgende Darstellung ist nicht das traditionelle 'erste Cantor Diagonalargument',sondern eher eine Vorschrift zum Erstellen eines 'fraktalen' Objektes.

Georg Cantor hat gezeigt, dass es Kurven (1-dimensionale Objekte) gibt, die Flächen (2-dimensionale Objekte) füllen können, und zwar so:

Man nehme eine quadratische Fläche, die durch die Eckpunkte (0,0) und (3,3)aufgespannt ist. Man ziehe eine Strecke von (0,0) nach (3,3).

Visualisierung der Cantor-DiagonalisierungIm Bild rechts ist der Kurvenverlauf durch Abstand in den Berührungspunkten verdeutlicht,wie in ausreichender Vergrößerung sichtbar wird

Diese Kurve innerhalb des Quadrates ändere man nun so ab: Man teile die quadratischeFläche in ein Raster 9 gleichgroßer Quadrate. Man ändere den Kurvenverlauf nun so ab,dass folgende Punkte die Endpunkte von Teilstrecken bilden:

(0,0) - (1,1) - (0,2) - (1,3) - (2,2) - (1,1) - (2,0) - (3,1) - (2,2) - (3,3)

Die abgeänderte Kurve hat die Eigenschaft, dass sie ebenfalls das Quadrat durchziehtund denselben Anfangs- und denselben Endpunkt hat.

5/13/2018 Diagonalsierung-Gödel-Stegmüller-ChristensenEDS - slidepdf.com

http://slidepdf.com/reader/full/diagonalsierung-goedel-stegmueller-christenseneds 11/49

 

Dieses Verfahren wiederhole man nun für jedes der kleinen Teil-Quadrate, und die darausentstandenen Teil-Quadrate und so weiter. Der Grenzwert dieses Verfahrens ist eineKurve, die das gesamte Quadrat ausfüllt.

Diese (unendlich lange) Grenzkurve ist Bild einer stetigen Abbildung φ des Intervalls [0, 1].Dazu setzt man zunächst die Endpunkte φ(0) = (0,0), φ(1) = (3,3). Im zweiten Schritt setztman die Eckpunkte der ersten Verfeinerung:

0 -> (0,0)1/9 -> (1,1)2/9 -> (0,2)3/9 -> (1,3)4/9 -> (2,2)5/9 -> (1,1)6/9 -> (2,0)7/9 -> (3,1)8/9 -> (2,2)

 

1 -> (3,3)

Dann setzt man in jedem Schritt die hinzukommenden Eckpunkte auf Werte zwischen denbisherigen Zahlen. Die Grenzkurve ist dann genau das Bild der so definierten Abbildung φ.Beachte, dass dies keine Bijektion von [0, 1] auf [0,3]×[0,3] ist, da die Abbildungzwar surjektiv, aber nicht injektiv ist; z.B. ist φ(1/9) = φ(5/9).

Während die Zahl eindimensional ist, sind die zugehörigen Koordinaten zweidimensional.Folglich kann man eindimensionale Zahlen in mehrdimensionale Zahlen überführen undumgekehrt. Mengen mehrdimensionaler Elemente sind somit nicht mächtiger als Mengeneindimensionaler Elemente.

Verwandte Themen [Bearbeiten]

• Cantorsche Paarungsfunktion

Cantors zweites Diagonalargument

Cantors zweites Diagonalargument ist ein mathematischer  Beweis dafür, dass dieMenge der reellen Zahlen überabzählbar ist, und allgemeiner, dass die Abbildungen einer Menge nach {0,1} sowie die Potenzmenge einer Menge mächtiger als diese Menge sind.Der Mathematiker Georg Cantor  fand diesen Beweis im Jahr 1877 und gab die beidenVerallgemeinerungen 1891 und 1899 an.[1]

Mit seinem ersten Diagonalargument zeigte Cantor, dass die Menge der rationalenZahlen abzählbar ist, er gab eine umkehrbar eindeutige Abbildung (eine Bijektion)zwischen der Menge der natürlichen Zahlen und der Menge der rationalen Zahlen an.Diese Abbildung erlaubt es anschaulich, alle rationalen Zahlen in einer abzählbar unendlichen Folge anzuordnen.

Durch Widerspruch zeigte er, dass es für die reellen Zahlen keine solche Folge gibt, d. h.keine Bijektion zu den natürlichen Zahlen.

5/13/2018 Diagonalsierung-Gödel-Stegmüller-ChristensenEDS - slidepdf.com

http://slidepdf.com/reader/full/diagonalsierung-goedel-stegmueller-christenseneds 12/49

 

Dieser Beweis ist nicht Cantors erster Beweis der Überabzählbarkeit der reellenZahlen. Cantors erster Überabzählbarkeitsbeweis wurde 1874, drei Jahre vor seinemDiagonalargument, veröffentlicht. Der erste Beweis arbeitet mit anderen Eigenschaften der reellen Zahlen und kommt ganz ohne ein Zahlensystem aus.

Inhaltsverzeichnis

[Verbergen]• 1 Beweis der 

Überabzählbarkeit der reellenZahlen

• 2 Verallgemeinerung:Mächtigkeit

der Potenzmengeeiner Menge

• 3 Standpunktder Konstruktivisten

• 4 Einzelnachweise

• 5 Weblinks

Beweis der Überabzählbarkeit der reellen Zahlen [Bearbeiten]

Sei (zi ) irgendeine unendliche Folge reeller Zahlen im offenen Intervall (0,1). Wir werdenzeigen, dass es mindestens eine reelle Zahl in diesem Intervall gibt, die nicht in der Folge (zi ) vorkommt. Da diese Argumentation für jede beliebige Folge (zi ) gilt, kann eskeine Folge geben, die alle reellen Zahlen im Intervall (0,1) enthält.

Die Zahlen in dieser als gegeben vorausgesetzten Folge sehen in ihrer Dezimalbruch-Entwicklung so aus:

Hier sind die zi  reelle Zahlen und die aij  Dezimalstellen dieser reellen Zahlen. Die

Diagonalelemente sind hervorgehoben, aus diesen konstruieren wir eine neue Zahl

5/13/2018 Diagonalsierung-Gödel-Stegmüller-ChristensenEDS - slidepdf.com

http://slidepdf.com/reader/full/diagonalsierung-goedel-stegmueller-christenseneds 13/49

 

Jede Zahl zi der Folge definiert auf folgende Weise eine Dezimalstelle xi von x .

Wenn a11 = 5 ist, setzen wir  x 1 = 4, sonst x 1 = 5. Mit dieser Definition istsichergestellt, dass x eine andere Zahl ist als z 1.

Wenn a22 = 5 ist, setzen wir  x 2 = 4, sonst x 2 = 5. Damit gilt .

Allgemein legen wir für jede natürliche Zahl i fest:

Wenn aii = 5 ist, setzen wir  xi = 4, sonst xi = 5. Damit gilt .

So gehen wir durch die ganze Folge und erhalten eine Zahl x , die sich von allen Zahlen inder Folge unterscheidet und die größer als 0 und kleiner als 1 ist. Diese Zahl nennt mandie Diagonalzahl , die der Folge (zi ) zugeordnet wird.

Die Folge (zi ) enthält also nicht alle reellen Zahlen zwischen 0 und 1. Wählt man eineandere Folge, erhält man möglicherweise eine andere Diagonalzahl, aber wir habenbewiesen: Für jede Folge von Zahlen zwischen 0 und 1 gibt es eine Zahl zwischen 0 und

1, die nicht in dieser Folge enthalten ist. Deshalb enthält keine Folge alle reellen Zahlen

zwischen 0 und 1. Mit Folgen als Abbildungen aufgefasst, gibt es also

keine surjektive Abbildung . Das Intervall (0,1) ist deshalb weder gleichmächtig

zu , noch endlich, mithin überabzählbar .

Da das betrachtete Intervall (0,1) eine Teilmenge der Menge aller reellen

Zahlen ist, ist erst recht überabzählbar: Aus jeder surjektiven

Abbildung ließe sich sofort eine surjektive Abbildung gewinnen.

Tatsächlich ist sogar gleichmächtig zu (0,1), wie man anhand einer geeigneten

Bijektion, beispielsweise , erkennt.

Verallgemeinerung: Mächtigkeit der Potenzmenge einer Menge [Bearbeiten]

Mit einer allgemeineren Form des obigen Beweises zeigte Cantor, dassdie Potenzmenge einer beliebigen Menge mächtiger als diese Menge ist. Genauer zeigte

er: Es gibt keine surjektive Abbildung von A auf . Diese Aussage wird auch Satzvon Cantor genannt.

Im älteren Beweis von 1891 zeigte Cantor die größere Mächtigkeit der Abbildungenvon A nach {0,1}, die bijektiv auf die Teilmengen von A, also auf die Potenzmenge,

abgebildet werden können. Den Zusammenhang zum Beweis von kann man –

ungefähr – erkennen, wenn man Teilmengen als Folge von 0en und 1en

schreibt (für bzw. ) und diese als Ziffernentwicklung interpretiert.

5/13/2018 Diagonalsierung-Gödel-Stegmüller-ChristensenEDS - slidepdf.com

http://slidepdf.com/reader/full/diagonalsierung-goedel-stegmueller-christenseneds 14/49

 

Standpunkt der Konstruktivisten [Bearbeiten]

Auf Kritik gestoßen ist Cantors Beweis der Überabzählbarkeit der reellen Zahlen durch daszweite Diagonalverfahren bei Leopold Kronecker , Hermann Weyl , L.E.J. Brouwer , HenriPoincaré und Ludwig Wittgenstein. Konstruktivisten deuten das CantorscheDiagonalverfahren anders als Cantor. Es wird selbst als Zahlenkonstruktionsverfahrenverstanden, in dem nicht irgendeine Ordnung gewählt wird, sondern eine konkreteOrdnung (eine bestimmte Folge) der abzählbaren Ausgangsmenge vorausgesetzt wird.Die durch das Diagonalverfahren entdeckte Eigenschaft wird von konstruktivenMathematikern als Offenheit oder als Indefinitheit (Paul Lorenzen, Christian Thiel) der Mengen reeller Zahlen angesehen und nicht als die Überabzählbarkeit einer Menge. Sowie man etwa die Menge der ganzen Zahlen zur Menge der rationalen Zahlen erweiternkann, so könne man auch die algebraischen Zahlen durch algebraische Hüllen über neueDiagonalzahlen oder transzendente Zahlen erweitern und erhält so immer größereabzählbare Mengen reeller Zahlen.

Einzelnachweise [Bearbeiten]

1. ↑ Herbert Meschkowski: Georg Cantor, Leben, Werk und Wirkung , Mannheim,Wien, Zürich, 1983, S. 85f. Cantor: Über eine elementare Frage der Mannigfaltigkeitslehre, 1891

Weblinks [Bearbeiten]

• Über eine elementare Frage der Mannigfaltigkeitslehre - (Jahresbericht der Deutschen Mathematiker-Vereinigung, Band I ab Seite 75 (Navigationsleiste 83:75))

Diagonalmatrix

Als Diagonalmatrix bezeichnet man im mathematischen Teilgebiet der linearenAlgebra eine quadratische Matrix, bei der alle Elemente außerhalbder Hauptdiagonale Null sind. Diagonalmatrizen sind deshalb allein durch die Angabe ihrer Hauptdiagonale bestimmt und man schreibt häufig

.

Stimmen dabei sämtliche Zahlen auf der Hauptdiagonalen überein, spricht manauch von Skalarmatrizen.[1]

5/13/2018 Diagonalsierung-Gödel-Stegmüller-ChristensenEDS - slidepdf.com

http://slidepdf.com/reader/full/diagonalsierung-goedel-stegmueller-christenseneds 15/49

 

Inhaltsverzeichnis

[Verbergen]• 1 Rechenoper 

ationen• 1.1 Mat

rixaddition,Skalar multiplikationundMatrixmultiplikation,Transposition

• 1.2 Ber echnung der Inversen

• 2 Eigenschaften vonDiagonalmatrizen

• 3 Diagonalisie

rbarkeit• 3.1 Eig

enschafteneiner diagonalisierbarenMatrix

• 3.2 Diagonalisierung

• 3.3 SimultaneDiagonalisierung

• 4 Beispiel• 5 Spezielle

Diagonalmatri

zen• 6 Siehe auch• 7 Einzelnach

weise

5/13/2018 Diagonalsierung-Gödel-Stegmüller-ChristensenEDS - slidepdf.com

http://slidepdf.com/reader/full/diagonalsierung-goedel-stegmueller-christenseneds 16/49

 

Rechenoperationen [Bearbeiten]

Matrixaddition, Skalarmultiplikation und Matrixmultiplikation,Transposition [Bearbeiten]

Die Matrixaddition, Skalarmultiplikation und Matrixmultiplikation gestalten sich beiDiagonalmatrizen sehr einfach:

Multiplikation einer Matrix A von links mit einer Diagonalmatrix entspricht der Multiplikationder Zeilen von A mit den Diagonaleinträgen. Die entsprechende Multiplikation von Rechtsentspricht der Multiplikation der Spalten von A mit den Diagonaleinträgen.

Für jede Diagonalmatrix A gilt, dass sie symmetrisch ist, folglich gilt: A=AT.[2]

Berechnung der Inversen [Bearbeiten]

Eine Diagonalmatrix ist genau dann invertierbar, wenn keiner der Einträge auf der Hauptdiagonale 0 ist. Die inverse Matrix berechnet sich dann wie folgt:

Eigenschaften von Diagonalmatrizen [Bearbeiten]

• Die jeweiligen Diagonalmatrizen bilden einen

kommutativen Unterring des Rings der quadratischen -Matrizen.• Die Eigenwerte einer Diagonalmatrix sind die Einträge auf der Hauptdiagonale mit

den kanonischen Einheitsvektoren als Eigenvektoren.

• Die Determinante einer Diagonalmatrix ist das Produkt der Einträge auf der Hauptdiagonalen:

Diagonalisierbarkeit [Bearbeiten]

Eine quadratische n-dimensionale Matrix A heißt diagonalisierbar , wenn es eineDiagonalmatrix DA gibt, zu der sie ähnlich ist, das heißt es existiert eine invertierbareMatrix S, so dass gilt DA = S − 1 AS, bzw. SDA = AS.

Für eine lineare Abbildung  (Vektorraum-Endomorphismus) bedeutet dies, dass

eine Basis B existiert, bei der die Darstellungsmatrix eine Diagonalmatrix ist.

Seien S und DA mit den gewünschten Eigenschaften gefunden, so gilt dass dieDiagonaleinträge von DA, nämlich λi , Eigenwerte von DA zu den Einheitsvektoren ei sind.Weiterhin ist ASei = SDAei = Sλiei = λiSei . Die Sei sind also auch Eigenvektoren von A,und zwar jeweils zum Eigenwert λi .

Da S umkehrbar sein soll, ist zudem linear unabhängig.

Zusammenfassend ergibt sich daraus die notwendige Bedingung, dass dieMatrix A n linear unabhängige Eigenvektoren hat, der Raum, auf dem sie operiert, alsoeine Basis aus Eigenvektoren von Abesitzt. Diese Bedingung ist aber auch hinreichend,

5/13/2018 Diagonalsierung-Gödel-Stegmüller-ChristensenEDS - slidepdf.com

http://slidepdf.com/reader/full/diagonalsierung-goedel-stegmueller-christenseneds 17/49

 

denn aus n gefundenen Eigenvektoren von A mit den dazugehörigen Eigenwerten lassensich geeignete DA und S ganz direkt konstruieren.

Das Problem reduziert sich damit auf das Auffinden von ausreichend vielen linear unabhängigen Eigenvektoren von A.

Eigenschaften einer diagonalisierbaren Matrix [Bearbeiten]

Ist eine Matrix diagonalisierbar, so ist die geometrischeVielfachheit ihrer Eigenwerte gleich der jeweiligen algebraischen Vielfachheit. Dasbedeutet, die Dimension der einzelnen Eigenräume stimmt jeweils mit der algebraischenVielfachheit der entsprechenden Eigenwerte im charakteristischen Polynom der Matrixüberein.

Diagonalisierung [Bearbeiten]

Ist eine Matrix A diagonalisierbar, existiert eine Diagonalmatrix DA, für die dieÄhnlichkeitsbedingung erfüllt ist:

DA = S − 1 AS

Zur Diagonalisierung dieser Matrix berechnet man die Diagonalmatrix DA und einezugehörige Basis aus Eigenvektoren. Dies geschieht in drei Schritten:

1. Es werden die Eigenwerte λi der Matrix A bestimmt.

2. Es werden die Eigenräume  zu allen Eigenwerten λi berechnet, alsofolgendes Gleichungssystem gelöst:

3. Nun ist die Diagonalform DA der Matrix A bezüglich der Basis B:

S = {E (λ1),...,E (λn)}Simultane Diagonalisierung [Bearbeiten]

Gelegentlich will man auch zwei unterschiedliche Matrizen A,B mit derselbenTransformation S diagonalisieren. Falls das gelingt, gilt S − 1 AS = D1 und S −1BS = D2 und da D1 und D2 Diagonalmatrizen sind,

.

Also müssen die Endomorphismen miteinander kommutieren. In der Tat gilt auch dieUmkehrung: kommutieren zwei diagonalisierbare Endomorphismen, so können siesimultan diagonalisiert werden. In der Quantenmechanik gibt es für zwei solcheOperatoren dann eine Basis aus gemeinsamen Eigenzuständen.

Beispiel [Bearbeiten]

Die darstellende Diagonalmatrix

eines Endomorphismus besitzt die Eigenwerte

5/13/2018 Diagonalsierung-Gödel-Stegmüller-ChristensenEDS - slidepdf.com

http://slidepdf.com/reader/full/diagonalsierung-goedel-stegmueller-christenseneds 18/49

 

mit zugehörigen Eigenräumen / Eigenvektoren

.

Spezielle Diagonalmatrizen [Bearbeiten]

• Die Einheitsmatrix ist ein Spezialfall einer Diagonalmatrix, bei der alle Elemente der Hauptdiagonale den Wert 1 haben.

• Die quadratische Nullmatrix ist ein Spezialfall einer Diagonalmatrix, bei der alleElemente der Hauptdiagonale den Wert 0 haben.

Siehe auch [Bearbeiten]

• TrigonalisierungEinzelnachweise [Bearbeiten]

1. ↑ Uwe Storch, Hartmut Wiebe: Lehrbuch der Mathematik, Band II: Lineare Algebra.BI-Wissenschafts-Verlag, 1990, ISBN 3-411-14101-8

2. ↑ http://books.google.de/books?id=CnfrIB6IDFQC&pg=PA363&lpg=PA363&dq=diagonalmatrix+transponierte&source=bl&ots=39hjhMN5dT&sig=z4nFG4mqVhlcWJAOrUpgzeZaHYk&hl=de&ei=-d9LTYPvAse3hQe7vZHUDg&sa=X&oi=book_result&ct=result&resnum=2&ved=0CCEQ6AEwAQ#v=onepage&q=diagonalmatrix%20transponierte&f=false

Gödelnummer 

Eine Gödelnummer ist eine natürliche Zahl, die einem Wort einer formalen Sprache nacheinem „durchschaubaren“ Verfahren – Gödelisierung – zugeordnet wird und diesesWort eindeutig kennzeichnet. Alle über die Kodierung von Programmen in einer Programmiersprache definierten Aufzählungen sind Gödelnummerierungen. DieBezeichnungen beziehen sich auf Kurt Gödel, der erstmals ein solches Verfahren angab,um seinen Unvollständigkeitssatz zu beweisen.

5/13/2018 Diagonalsierung-Gödel-Stegmüller-ChristensenEDS - slidepdf.com

http://slidepdf.com/reader/full/diagonalsierung-goedel-stegmueller-christenseneds 19/49

 

Inhaltsverzeichnis

[Verbergen]• 1 Formale

Definition• 2 Beispiel• 3 Gödelisieru

ng vonzahlentheoretischenAussagen

• 4 Gödelisierung vonTuringmaschinen

• 4.1 Bei

spiel• 5 Siehe auch• 6 Einzelnach

weis

Formale Definition [Bearbeiten]

Sei M die (abzählbare) Menge der Wörter einer formalen Sprache. Eine Funktion

wird Gödelisierung genannt, wenn[1]

• g  injektiv und berechenbar ,• die Bildmenge g (M ) entscheidbar sowie• die auf g (M ) definierte Umkehrfunktion von g  berechenbar ist.

g (m) nennt man dann die Gödelnummer von m.

Beispiel [Bearbeiten]

Angenommen, beliebige Wörter der formalen Sprache L, die auf dem Alphabet Σ basieren,sollen gödelisiert werden. Hier sei Σ = {a,b,c }.

Eine Möglichkeit der Kodierung wäre, den Buchstaben zunächst einfach fortlaufendeNummern zuzuweisen. Ein „a“ entspräche der 1, ein „b“ der 2 und ein „c“ der 3. Nun kannman gödelisieren, indem man die dem Buchstaben entsprechenden Potenzen der 

fortlaufenden Primzahlen miteinander multipliziert:

Das Wort „abccba“

• Das „a“ an erster Stelle hat den Wert 21 = 2• Das „b“ an zweiter Stelle hat den Wert 32 = 9• Das „c“ an dritter Stelle hat den Wert 53 = 125• Das „c“ an vierter Stelle hat den Wert 73 = 343• Das „b“ an fünfter Stelle hat den Wert 112 = 121• Das „a“ an sechster Stelle hat den Wert 131 = 13

Die Gödelnummer für „abccba“ in dieser Kodierung lautet also

5/13/2018 Diagonalsierung-Gödel-Stegmüller-ChristensenEDS - slidepdf.com

http://slidepdf.com/reader/full/diagonalsierung-goedel-stegmueller-christenseneds 20/49

 

Da es unendlich viele Primzahlen gibt, kann man auf diese Weise tatsächlich beliebiglange Wörter kodieren und aufgrund der Eindeutigkeit der Primfaktorzerlegung lässt sichetwa aus der Zahl 1213962750 wieder das Wort „abccba“ rekonstruieren. Es gibt zwar 

Zahlen, die keinem Wort der Sprache entsprechen, beispielsweise (kein erster Buchstabe) oder 16 = 24 (Alphabet Σhat kein viertes Element). Aber zumindest lassen sich

diese ungültigen Werte auf berechenbare Weise von den gültigen unterscheiden.Neben der hier gezeigten gibt es natürlich noch andere Methoden, eine Gödelisierungdurchzuführen.

Eine im Buch Gödel, Escher, Bach beschriebene Methode verwendet beispielsweiseein Stellenwertsystem mit der Basis 1000, was zwar sehr anschaulich ist, aber formalschwieriger zu handhaben ist als eine Methode, die wie die obige auf Primzahlpotenzenberuht.

Gödelisierung von zahlentheoretischen Aussagen [Bearbeiten]

Aussagen der Zahlentheorie (oder auch anderer mathematischer Theorien) lassen sich mit

Hilfe eines endlichen Alphabets formulieren, dessen „Buchstaben“ neben Zeichen für 

Variablen auch gewisse mathematische und logische Symbole (etwa + ,

, = , , , ) umfasst. (Die abzählbar unendlich vielenVariablen können als besonders gekennzeichnete Wörter des endlichen Alphabetsdargestellt werden.)

Auf diese Weise lassen sich also zahlentheoretische Aussagen (und sogar Beweise) inZahlen übersetzen. Als Folge hiervon kann die Zahlentheorie, die ja Aussagen über Zahlen behandeln soll, auch Aussagen über zahlentheoretische Aussagen und Beweisebehandeln. Diese Tatsache ist der Punkt, an dem Gödels Unvollständigkeitssatz ansetzt.

Gödelisierung von Turingmaschinen [Bearbeiten]

Eine bekannte Anwendung der Gödelnummer ist die Codierungeiner Turingmaschine durch ein Binärwort w . Auf diese Weise wird jeder Turingmaschineeine Zahl zugeordnet (d. h. die Menge aller Turingmaschinen ist abzählbar). DieseTatsache wird unter Anderem im Halteproblem ausgenutzt.

Beispiel [Bearbeiten]

Natürlich lassen sich verschiedenste Konventionen für die Nummerierung vereinbaren. ImFolgenden soll der Vorgang an einem einfachen Beispiel gezeigt werden. Sei

eine Turingmaschine. Seien o. B. d. A. die Zustandsmenge Q, sowie dasBandalphabet Γ durchnummeriert.

Wir codieren nun vorerst jeden Übergang δ(qm,an) = (qm',an',{L,N ,R }) mit einem Wort

über dem Alphabet . Zustände bzw. Terminalsymbole werden durch die

5/13/2018 Diagonalsierung-Gödel-Stegmüller-ChristensenEDS - slidepdf.com

http://slidepdf.com/reader/full/diagonalsierung-goedel-stegmueller-christenseneds 21/49

 

Binärdarstellung ihrer Indizes dargestellt, die einzelnen Elemente werden mitgetrennt.

wobei b die Kopfbewegung darstellt (L = 0,N = 1,R = 2). Um uns auf das zweistellige

Alphabet {0,1} beschränken zu können, führen wir eine Abbildung der Mengeauf {0,1} ein:

.

Die Turingmaschine mit der einzigen Produktion wird sozu 10100010001000100010012 = 265639310.

Eine Alternative, die auf das Trennzeichen verzichtet, nutzt die Eindeutigkeitder Primfaktorzerlegung aus, um Tupel in einer Zahl codieren zu können.

Siehe auch [Bearbeiten]

• Church-Turing-These• Gödelscher Unvollständigkeitssatz• Turingmaschine• Halteproblem

Halteproblem

Das Halteproblem ist ein Problem aus der Theoretischen Informatik. Es besteht darin, zuentscheiden, ob die Ausführung einer bestimmten Berechnungsvorschrift(eines Algorithmus oder Programms) zu einem Ende gelangt. Alan Turing bewies, dass

dieses Problem in dem von ihm eingeführten Kalkül der Turingmaschine nichtalgorithmisch entscheidbar ist. Auch wenn für viele Algorithmen die Frage, ob sieirgendwann terminieren, leicht beantwortet werden kann, gibt es also keinen Algorithmus,der diese Frage für alle möglichen Algorithmen und beliebigen Eingaben beantwortet.Turings Resultat spielt eine grundlegende Rolle in der Theorie der Berechenbarkeit.

5/13/2018 Diagonalsierung-Gödel-Stegmüller-ChristensenEDS - slidepdf.com

http://slidepdf.com/reader/full/diagonalsierung-goedel-stegmueller-christenseneds 22/49

 

Inhaltsverzeichnis

[Verbergen]• 1 Problemstel

lung• 2 Beweisskizz

e• 3 Konsequen

zen• 4 Politik• 5 Literatur • 6 Einzelnach

weise

Problemstellung [Bearbeiten]

Das Halteproblem stellt die Frage, ob es eine Turingmaschine H gibt, die für jedeTuringmaschine T mit jeder Eingabe w entscheidet, ob T irgendwann anhält oder endlosweiterläuft. Die Eingabe für H besteht dabei jeweils aus einer codiertenBeschreibung b(T ) der Maschine T und deren Eingabe w .

Alan Turing bewies 1936, dass eine solche Maschine H nicht existiert.

Beweisskizze [Bearbeiten]

Der Nachweis, dass das Halteproblem nicht entscheidbar ist, geschieht durcheinen Widerspruchsbeweis. Man nimmt an, dass die oben beschriebeneMaschine H existiert, und zeigt, dass dies zu einem logischen Widerspruch führt. Diesgelingt mit der folgenden Konstruktion von Marvin Minsky:[1]

Angenommen, H existiert. Man darf ohne Beschränkung der Allgemeinheit annehmen,dass die Eingabe für H die Form b(T ) * w hat. Dabei ist * eine Zeichenkette, die weder inder Beschreibung b(T )der Turingmaschine T noch in deren Eingabe w vorkommt.

Es ist möglich, um H herum eine Maschine G zu konstruieren, die sich bis auf einenUnterschied so verhält wie H :

• Wenn H , angesetzt auf die Beschreibung b(T ) einer Maschine T mit der Eingabe w ,das Ergebnis liefert, dass T auf w nicht hält, dann liefert auch G dieses Ergebnis.

• Wenn hingegen H unter derselben Eingabe das Ergebnis liefert, dass T hält, dannlässt man G in eine Endlosschleife laufen.

Dann gilt in tabellarischer Darstellung:Maschine

T  Eingabe w 

Maschine H Eingabe b(T ) * w 

Maschine G Eingabe b(T ) * w 

hält nichthält

Ergebnisanzeige0

hältErgebnisanzeige

0

hälthält

Ergebnisanzeige1

hält nicht

Um G herum kann eine Turingmaschine F mit der folgenden einfachen Erweiterungkonstruiert werden: F ersetzt eine beliebige Eingabe x durch x * x . Anschließend ruft F dasProgramm von G auf.

5/13/2018 Diagonalsierung-Gödel-Stegmüller-ChristensenEDS - slidepdf.com

http://slidepdf.com/reader/full/diagonalsierung-goedel-stegmueller-christenseneds 23/49

 

Wenn man F mit ihrer eigenen Beschreibung b(F ) als Eingabe in Betrieb setzt, dannpassiert Folgendes:

1. F ersetzt die Eingabe b(F ) durch b(F ) * b(F ).2. F ruft G mit der Eingabe b(F ) * b(F ) auf.3. G ruft H mit der Eingabe b(F ) * b(F ) auf.

Angenommen, H hält mit dem Ergebnis 1, d.h. F mit der Eingabe b(F ) hält. Danngeht es folgendermaßen weiter:

4. G setzt ihr Programm fort, geht in eine Endlosschleife, und hält nicht.5. Die G umfassende Maschine F  hält nicht.

Angenommen H hält mit dem Ergebnis 0, d.h. F mit der Eingabe b(F ), hält nicht.Dann geht es folgendermaßen weiter:

4. G hält mit dem Ergebnis 0.5. F  hält.

F mit der Eingabe b(F ) hält genau dann, wenn F nicht hält. Die Annahme, dass H existiert,hat zu diesem Widerspruch geführt – also ist diese Annahme falsch. H existiert nicht, das

Halteproblem ist nicht entscheidbar.

Grafische Darstellung der BeweiskonstruktionKonsequenzen [Bearbeiten]

Bereits durch den gödelschen Unvollständigkeitssatz wurde gezeigt, dass es unmöglichwar, die Mathematik durch eine strikte Axiomatisierung vollständig und widerspruchsfrei zuformulieren. Er erbrachte den Beweis, dass Hilberts Programm zum Scheitern verurteiltwar. Auch nach den Erkenntnissen von Turing ist so etwas grundsätzlich nicht möglich: in jedem System, das einer Turingmaschine gleichmächtig ist, lassen sich Aussagenformulieren, die weder bewiesen noch widerlegt werden können.[2] Des Weiteren folgt ausder Unlösbarkeit des Halteproblems, dass esFunktionen gibt, die zwar wohldefiniert sind,deren Werte sich jedoch nicht für jeden Parameter berechnen lassen. Ein bekanntes

Beispiel für eine solche Funktion ist die Radó-Funktion.Setzt man nun die churchsche These als wahr voraus, so kann das Halteproblemgrundsätzlich nicht gelöst werden. Das führt zu der philosophisch weitreichendenAussage, dass nicht jedes Problem lösbar ist, selbst dann nicht, wenn man eigentlich allerelevanten Informationen kennt und sich streng an einen mächtigen Formalismus hält.

Für die Softwareentwicklung folgt aus der Nichtentscheidbarkeit des Halteproblems, dassim Allgemeinen eine automatisierte Verifikation einer Programmlogik nicht möglich ist.Insbesondere ist es im generellen Fall nicht möglich, automatisiert festzustellen, welcheProgramme jemals zu einem Ende finden. Die gängigen Programmiersprachen sindnämlich Turing-vollständig, das heißt, einer Turingmaschine gleichmächtig. Mit ihnen

lassen sich alle Funktionen berechnen, die auch eine Turingmaschine berechnen kann,und umgekehrt.

5/13/2018 Diagonalsierung-Gödel-Stegmüller-ChristensenEDS - slidepdf.com

http://slidepdf.com/reader/full/diagonalsierung-goedel-stegmueller-christenseneds 24/49

 

Viele in der Praxis vorkommende Programme und Verfahren sind jedoch so strukturiert,dass dennoch ein automatisierter Terminierungsbeweis geführt werden kann.

Politik [Bearbeiten]

In der netzpolitischen Diskussion spielt das Halteproblem seit dem Bekanntwerdendes „Staatstrojaners“ eine Rolle. So behauptete Parl. Staatssekretär Dr. Ole Schröder in

der Aktuellen Stunde zur Quellen-TKÜ [3]:„Die Software wird für jeden Einzelfall entsprechend konzipiert und vorher überprüft, damit sie eben nicht mehr kann, als sie darf. “ – DR. OLE SCHRÖDER

Woraufhin Ulrich Kelber zweifelte, „dass das BKA ohne Kenntnis des Quellcodes mithilfeeines geeigneten Verfahrens vollständig und sicher geprüft hat, ob die Softwarenichterlaubte Funktionen enthält oder nicht“ .

In der Debatte zum Einsatz der Quellen-TKÜ im Berliner Abgeordnetenhaus erklärte Alexander Morlang den anwesenden Parlamentariern das

Halteproblem[4].Literatur [Bearbeiten]

• Alan Turing: On computable numbers, with an application to theEntscheidungsproblem, Proceedings of the London Mathematical Society, 2, 42(1936), S. 230–265. Online-Fassung

Einzelnachweise [Bearbeiten]

1. ↑ Vorlesungsskript der Old Dominion University, abgerufen am 13. Juli 20112. ↑ Eine gut verständliche Darstellung der Zusammenhänge und Konsequenzen aus

Gödels und Turings Arbeiten bietet beispielsweise Douglas R.

Hofstadter: Besprechung von Alan Turing: The Enigma, in Metamagicum, Klett-Cotta, Stuttgart 1988, ISBN 3-608-93089-2, S. 519–528.3. ↑ Stenografischer Bericht der 132. Sitzung. Fragestunde (Drucksachen 17/7311,

17/7333). In: bundestag.de.4. ↑ Redebeitrag Alexander Morlang "Einsatz von Quellen-TK in Berlin".

Auf: youtube.com

Gödelscher Unvollständigkeitssatz

Der Gödelsche Unvollständigkeitssatz ist einer der wichtigsten Sätze der modernenLogik. Er beschäftigt sich mit der Ableitbarkeit von Aussagen in Formalen Systemen. Der Satz zeigt die Grenzen der formalen Systeme ab einer bestimmten Mächtigkeit auf undweist nach, dass es in hinreichend mächtigen Systemen (wie der Arithmetik) Aussagengibt – und geben muss – die man weder formal beweisen, noch widerlegen kann. Der Satz

beweist damit die Unmöglichkeit des Hilbertprogramms, welches von David Hilbert unter anderem gegründet wurde, um die Widerspruchsfreiheit der Mathematik zu beweisen.

5/13/2018 Diagonalsierung-Gödel-Stegmüller-ChristensenEDS - slidepdf.com

http://slidepdf.com/reader/full/diagonalsierung-goedel-stegmueller-christenseneds 25/49

 

In der Wissenschaftstheorie und in anderen Gebieten der Philosophie zählt der Satz zuden meistrezipierten der Mathematik. Das Buch Gödel, Escher, Bach und die Werkevon John Randolph Lucas, der versuchte eine Theorie der Menschenrechte mit der Aussage zu zeigen, werden in dem Zusammenhang, zusammen mit ihren ebensozahlreichen Kritikern, gern exemplarisch herausgehoben. Der Satz wurde zuerst in der Arbeit von Kurt Gödel formuliert und bewiesen: Über formal unentscheidbare Sätze

der Principia Mathematica und verwandter Systeme I. in: Monatshefte für Mathematik und Physik 38 (1931), S. 173 ff.

Inhaltsverzeichnis

[Verbergen]• 1 Grundbegrif 

fe• 2 Gödels Satz

• 2.1 Sat

z• 2.2 Be

weisdes 1.Unvollständigkeitssatzes

• 3 BedeutungdesUnvollständigkeitssatzes

• 4 PhilosophischeInterpretationen

• 5 GenauereFormulierung

• 6 Sonstiges• 7 Siehe auch• 8 Literatur • 9 Weblinks

Grundbegriffe [Bearbeiten]

Aussagen sind Folgen von Zeichen, die ähnlich wieein Programm einer Programmiersprache einer gewissen Syntax genügen müssen. Für solche Aussagen definiert man auf naheliegende Weise das Konzept der Gültigkeit oder Wahrheit in Strukturen (siehe Modelltheorie). Dabei kann die Wahrheit einer Aussagedurchaus von der betrachteten Struktur abhängen: Eine Aussage mit der intendiertenBedeutung „Es gibt ein Element, das echt größer als 0 und echt kleiner als 1 ist“ gilt zum

Beispiel in der Struktur der reellen Zahlen, nicht jedoch in der 

Struktur der natürlichen Zahlen.

5/13/2018 Diagonalsierung-Gödel-Stegmüller-ChristensenEDS - slidepdf.com

http://slidepdf.com/reader/full/diagonalsierung-goedel-stegmueller-christenseneds 26/49

 

Der Begriff der Gültigkeit einer Aussage in einer Struktur führt auf natürliche Weise auf einen logischen Folgerungsbegriff, den sogenannten semantischen Folgerungsbegriff :Aussage A folgt aus einer Menge von Aussagen T (einer sogenannten Theorie) genaudann, wenn in jeder Struktur, in der alle Aussagen aus T gelten, auch A gilt.

Dem semantischen Folgerungsbegriff wird in der mathematischen Logik ein zweiter,der syntaktische Folgerungsbegriff , gegenübergestellt. Man gibt einen aus gewissenlogischen Axiomen und Regeln bestehenden Kalkül an, der spezifiziert, wie man eineAussage mechanisch und rein syntaktisch aus anderen folgern kann; auf diese Weiseerhält man einen formalisierten Beweisbegriff.

Von einem geeignet gewählten Kalkül lässt sich dann zeigen, dass er korrekt undvollständig ist; das heißt, dass der von ihm festgelegte syntaktische Folgerungsbegriff mitdem oben beschriebenen semantischen zusammenfällt (sogenannter Gödelscher Vollständigkeitssatz). Dieses Resultat sichert, dass man die natürliche semantischeFolgerungsrelation durch Überlegungen zum durch den Kalkül vorgegebenensyntaktischen Beweisbegriff adäquat untersuchen kann. Solche Überlegungen spielen beider Herleitung der Unvollständigkeitssätze eine zentrale Rolle.

Im Umfeld der Gödelschen Unvollständigkeitssätze sind die Begriffeder Widerspruchsfreiheit und der Vollständigkeit von Bedeutung. Eine Theorie T heißtgenau dann widerspruchsfrei , wenn es keine Aussage A gibt, sodass aus T sowohl A alsauch die Verneinung oder Negation von A folgt. Diese Bedingung ist, wie man leicht zeigenkann, äquivalent dazu, dass nicht jede Aussage aus T folgt. Eine Theorie T heißt genaudann vollständig , wenn für alle Aussagen A aus T die Aussage A oder deren Negation folgt.

Gödels Satz [Bearbeiten]

Satz [Bearbeiten]

Der Mathematiker Kurt Gödel wies mit seinem im Jahre 1931 veröffentlichten

Unvollständigkeitssatz nach, dass man in (hier stets als rekursivaufzählbar vorausgesetzten) Systemen wie der Arithmetiknicht alle Aussagen formalbeweisen oder widerlegen kann. Sein Satz besagt:

Jedes hinreichend mächtige formale System ist entweder widersprüchlich oder unvollständig.

Eine einfache Formulierung des ersten Unvollständigkeitssatzes sowie des darausunmittelbar folgenden zweiten Gödelschen Unvollständigkeitssatzes lautet:

In jedem formalen System der Zahlen, das zumindest eine Theorie der Arithmetik 

der natürlichen Zahlen ( ) enthält, gibt es einen unentscheidbaren Satz,also einen Satz, der nicht beweisbar und dessen Negierung ebenso wenig beweisbar ist. (1. Gödelscher Unvollständigkeitssatz).

Daraus folgt unmittelbar, dass kein formales System der Zahlen, das zumindest eine

Theorie der natürlichen Zahlen ( ) samt Addition und Multiplikation enthält, sichinnerhalb seiner selbst als widerspruchsfrei beweisen lässt (2. Gödelscher Unvollständigkeitssatz).

Beweis des 1. Unvollständigkeitssatzes [Bearbeiten]

Gödels Argumentation läuft auf eine Abzählung aller Sätze innerhalb des formalenSystems hinaus, jeder Satz erhält eine eigene Nummer. Er konstruiert dann mit Hilfe

5/13/2018 Diagonalsierung-Gödel-Stegmüller-ChristensenEDS - slidepdf.com

http://slidepdf.com/reader/full/diagonalsierung-goedel-stegmueller-christenseneds 27/49

 

einer Diagonalisierung eine Aussage der Form: „Der Satz mit der Nummer x ist nicht ableitbar “ und zeigt, dass es eine Einsetzung für  x gibt, so dass x die Nummer dieser Aussage ist. Insgesamt erhält er einen Satz der Form „Ich bin nicht ableitbar “. Es gibt nunzwei Möglichkeiten: Entweder dieser „Satz x “ ist wahr, dann ist er nicht ableitbar (genaudas ist sein Inhalt: Ich bin nicht ableitbar!). Oder „Satz x “ ist falsch, dann muss der Satzableitbar sein. Ein formales System, aus dem ein falscher Satz abgeleitet werden kann, ist

aber widersprüchlich. Demnach kann dieser Satz nur wahr sein, wenn das formale Systemunvollständig ist, oder falsch, wenn das formale System widersprüchlich ist (siehe hierfür auch das klassische Problem des Lügner-Paradox).

Man beachte: Falls das formale System nicht widersprüchlich ist, ist der Satz mitNummer  x und der Bedeutung „Satz x ist nicht ableitbar “ damit gezeigt. Wir vertrauen auf diesen „Beweis“, obwohl es innerhalb des Systems keine Ableitung gibt, die zu diesemSatz führt.

Damit obiger Ansatz funktioniert, muss das zugrundegelegte formale System alsomindestens Zählungen und eine Multiplikation mit einer Konstanten größer als 1 (für Kodierungszwecke) erlauben. Für zu einfache Systeme gilt der Unvollständigkeitssatz

daher nicht. Die Möglichkeit von Addition und Multiplikation sind ganz wesentlicheEigenschaften in vielen Theorien, so dass hier dieser Satz gilt. Insbesondere muss aber eine Substitution wie im Beweis Gödels möglich sein. Es gibt sehr einfache Systeme, für die diese Bedingungen erfüllt sind.

Nun könnte man sich dadurch behelfen, dass man für alle Sätze, die weder bewiesennoch widerlegt werden können, einfach festlegt, ob sie als wahr oder falsch gelten. Dasformale System würde dann durch diese zusätzlichen Axiome erweitert. Lesen wir jedocherneut den Unvollständigkeitssatz, so sehen wir, dass auch hier die Voraussetzungenerfüllt sind und somit auch das erweiterte System unvollständig bleibt, da stetsunbeweisbare Sätze übrigbleiben.

Bedeutung des Unvollständigkeitssatzes [Bearbeiten]Gödel versetzte mit seinem Unvollständigkeitssatz einem Ansatz von David Hilbert zur vollständigen Begründung und Formalisierung der Mathematik einen schweren Schlag.Dieser Ansatz ist alsHilbertprogramm bekannt geworden und wurde von ihm im Jahre1921 veröffentlicht. Hilbert hatte vorgeschlagen, die Widerspruchsfreiheit von komplexerenSystemen durch diejenige einfacherer Systeme nachzuweisen. Hintergrund ist der, dasseinem Beweis zur Widerspruchsfreiheit eines Systems, der in diesem System selbstgegeben ist, nicht getraut werden kann. Der Grund ist, dass sich aus einem Widerspruchheraus alles beweisen lässt (Ex falso quodlibet), also ließe sich aus einem Widerspruch imSystem auch die Widerspruchsfreiheit des Systems beweisen. Daher sollte die

Widerspruchsfreiheit in einem einfacheren System bewiesen werden.Eine streng formalisierte Prädikatenlogik erster Stufe war eines von Hilberts Konzepten.Am Ende seines Programms sollte die gesamte Mathematik auf die einfache Arithmetikzurückgeführt und auf ein axiomatisches System gestellt werden, aus dem allemathematischen Sätze streng ableitbar sind.

Gödels Schaffen war durch Hilberts Programm motiviert. Er verwendete die von Hilbertvorgeschlagenen Methoden, um seinen Unvollständigkeitssatz zu zeigen. Gödel bewiesauch den folgenden Satz

Ein System kann nicht zum Beweis seiner eigenen Widerspruchsfreiheit verwendet werden.

Gödel hatte damit gewissermaßen Hilbert mit dessen Methoden gezeigt, dass der Vorschlag nicht funktioniert.

5/13/2018 Diagonalsierung-Gödel-Stegmüller-ChristensenEDS - slidepdf.com

http://slidepdf.com/reader/full/diagonalsierung-goedel-stegmueller-christenseneds 28/49

 

Die Folge daraus ist, dass man die Korrektheit von (gewissen) formalen Systemen alsgegeben annehmen muss, sie lässt sich nicht beweisen.

Ein anderer Ansatz, der unüberbrückbare Lücken in Hilberts Programm nachweist, stammtvon dem Mathematiker Alan Turing. Er erfand die Turingmaschine und formuliertederen Halteproblem.

Philosophische Interpretationen [Bearbeiten]Obwohl Gödel sich im Laufe seines Lebens wiederholt als Platoniker zu erkennen gab,wurde sein Unvollständigkeitssatz wiederholt in einem subjektivistischen Sinn interpretiert.Auch schien Gödels Teilnahme am Wiener Kreis eine Nähe des Unvollständigkeitssatzesmit dem logischen Positivismus nahezulegen, der dem Platonismus in vielerlei Hinsichtentgegengesetzt ist. Gödels zurückhaltende, konfliktscheue Art trug dazu bei, dieFehlinterpretationen am Leben zu erhalten.

Gödel selbst verstand seinen Satz jedoch insbesondere als einen Schlag gegen den vonHilbert propagierten Formalismus in der Mathematik, der in letzter Konsequenz diegesamte Mathematik zu einem rein formalen Gebilde ohne Bezug zur „realen Welt“

machen sollte. Für Gödel als Platoniker waren jedoch die mathematischen Objektedurchaus „real“. Sie waren zwar nicht durch Sinneswahrnehmungen zu bestätigen (wie esdie Positivisten einforderten), doch waren sie der Erkenntnis zugänglich. Der Unvollständigkeitssatz zeigte für Gödel, dass man dieser Realität nicht mit rein formalenMitteln beikommen konnte.

Obwohl Gödel sich in seiner Grundhaltung gegenüber dem damals bedeutsamenlogischen Positivismus nicht sehr von Ludwig Wittgenstein unterschied, der eine Realität jenseits der möglichen Bedeutung von Sätzen anerkannte (und sie sogar für wichtiger hieltals das Sagbare), hielten Wittgenstein und Gödel Zeit ihres Lebens nicht viel voneinander.In Wittgensteins Werk wird der Unvollständigkeitssatz eher abschätzig behandelt. Für 

Wittgenstein taugte der Satz lediglich für „logische Kunststücke“. Gödel hingegen wies inspäteren Interviews jeglichen Einfluss Wittgensteins auf sein eigenes Denken weit vonsich.

Genauere Formulierung [Bearbeiten]

Der Gödelsche Satz besagt genauer, dass jedes Beweissystem für die Menge der wahrenarithmetischen Formeln unvollständig ist (sofern man voraussetzt, dassdie Arithmetik widerspruchsfrei ist – was, wie Gödel auch zeigt, nicht mit Mitteln der untersuchten Theorie allein bewiesen werden kann). Das heißt:

In jeder formalen Theorie, welche mindestens so mächtig wie die Theorie der natürlichenZahlen (Peano-Arithmetik) ist, bleiben wahre (und falsche) arithmetische Formeln übrig,

die nicht innerhalb der Theorie beweisbar (widerlegbar) sind. Paul Cohen bewies 1963,dass sowohl das Auswahlaxiom als auch die Kontinuumshypothese auf Grundlageder Zermelo-Fraenkel-Mengenlehre formal unentscheidbar sind. Er fand damit die erstenBeispiele mathematisch bedeutsamer unentscheidbarer Sätze, deren Existenz Gödelbewiesen hatte.

Damit eine Theorie (in der  Prädikatenlogik erster Stufe, PL1) die Voraussetzungen für dieUnvollständigkeit erfüllt, muss gelten:

• Das Axiomensystem muss rekursiv aufzählbar sein• Zu jeder durch einen Ausdruck G(x) beschriebenen Menge ist

das Komplement beschreibbar.• Zu jeder durch einen Ausdruck G(x) beschriebenen Menge M ist die Menge M*={x|

d(x) M} beschreibbar; Dabei ist d(x) die∈  Diagonalisierung von x.

5/13/2018 Diagonalsierung-Gödel-Stegmüller-ChristensenEDS - slidepdf.com

http://slidepdf.com/reader/full/diagonalsierung-goedel-stegmueller-christenseneds 29/49

 

• Die Menge der beweisbaren Ausdrücke der Theorie ist durch einen Ausdruck der Form G(x) beschreibbar.

Nach dem Satz von Löwenheim-Skolem findet man zu jeder Theorie in PL1 ein Modell mitder Mächtigkeit der Signatur . Für normale Theorien existiert also ein abzählbares Modell,beispielsweise die natürlichen Zahlen (das heißt, es lässt sich für jede Theorie in PL1 auchein Modell finden, in dem die Objekte natürliche Zahlen sind). Die Idee von Gödel war,

Formeln der Theorie selbst zum Objekt derselben zu machen. Dazu wurdendie Formeln gödelisiert, das heißt eine (injektive) Abbildung von Formeln auf natürlicheZahlen gebildet. Das kann man zum Beispiel dadurch erreichen, dass man jedem Symbolder Signatur eine Zahl zuordnet und einer Symbolkette entsprechend eine Kette vonZahlen. Ordnet man der 0 die 1 und = die 2 zu, so ist die Gödelnummer der Formel (indem Spezialfall) 0=0 die 121. Die Zahlenkette wird dann durch Exponentieren in eineeinzelne Zahl übersetzt. Es lassen sich auch die syntaktisch wohlgeformten, undschließlich die beweisbaren Formeln durch arithmetische Ausdrücke(Addition, Multiplikation, Exponentiation) beschreiben.

Die Diagonalisierung in Gödels Beweis ist nun eine Anwendung eines Ausdrucks P(x) auf 

die eigene Gödelnummer. Ist die Gödelnummer des Ausdrucks (und damit der Zeichenreihe) P(x) zum Beispiel 12345, so ist die Diagonalisierung d der Zahl 12345 dieGödelnummer von P (12345) (selbstverständlich hat eine Zahl, hier 12345, auch eineGödelnummer, die entsteht, indem man alle vorkommendenZiffern gödelisiert).

Besagt der Ausdruck Bew(x) also, dass x ableitbar ist, so sagt B(x)=¬Bew(d(x)), dass dieFormel mit der Gödelnummer d(x) nicht ableitbar ist. Ist nun zum Beispiel 12345 dieGödelnummer von B(x), so ist B(12345) eine nicht ableitbare Aussage. Diese Aussagebesagt dann nämlich: Die Formel mit der Gödelnummer d(12345) ist nicht ableitbar. 12345ist aber die Gödelnummer von B(x), alsod(12345) die Gödelnummer von B(12345). Alsosagt B(12345): Ich bin nicht ableitbar. Wenn PA korrekt ist, so ist dieser Satz wahr (in PA),aber nicht ableitbar.

Gödels ursprünglicher Beweis ging noch weiter. Er wollte Rückgriffe auf die Semantik,insbesondere die Korrektheit, vermeiden. Deswegen bewies er seinenUnvollständigkeitssatz unter der Voraussetzung der ω-Konsistenz: Eine Theorie ist ω-inkonsistent, wenn ein Ausdruck mit einer einzigen freien Variable x existiert, für 

den ableitbar ist, zugleich aber für alle n < ω ableitbar ist.

Rosser erweiterte das gödelsche Resultat, indem er einen Unvollständigkeitsbeweislieferte, für den nicht die Menge der Ausdrücke, deren Diagonalisierung beweisbar ist,beschrieben wird, sondern eine zu dieser Menge disjunkte Obermenge der Ausdrücke,

deren Diagonalisierung widerlegbar ist. Dadurch ist auch der Bezug auf die ω-Konsistenzüberflüssig.

Gödels zweiter Unvollständigkeitssatz ist eine leicht zu sehende Konsequenz aus demersten. Da Gödel beweisbare Aussagen innerhalb der Prädikatenlogik formalisierte(beispielsweise durch das Prädikat Bew ( x )), lässt sich auch folgende Aussage

bilden: , wobei die Gödelnummer von einer beliebigen Kontradiktion,

zum Beispiel , ist. Die Aussage behauptet die Nichtbeweisbarkeiteiner Kontradiktion, und damit die Widerspruchsfreiheit der gesamten Theorie (der Peano-

Arithmetik). W ist in PA nicht beweisbar. Um die Nicht-Beweisbarkeit zu zeigen, wird eineFixpunktkonstruktion verwendet. Sei g ( x ) die Gödelisierungsfunktion, A eine

5/13/2018 Diagonalsierung-Gödel-Stegmüller-ChristensenEDS - slidepdf.com

http://slidepdf.com/reader/full/diagonalsierung-goedel-stegmueller-christenseneds 30/49

 

Aussage, B( x ) ein Prädikat. A heißt Fixpunkt für B( x ), wenn beweisbar ist. Über einfache aussagenlogische Konstruktionen lässt sich beweisen, dass beweisbar 

ist, wenn A Fixpunkt von ist. Außerdem kann leicht gezeigt werden, dass,

wenn A Fixpunkt von ist, A nicht beweisbar ist, falls PA konsistent ist. Daraus

folgt dann, dass W nicht beweisbar ist.Durch diese erstaunlichen Sätze ist der Mathematik eine prinzipielle Grenze gesetzt: Nicht jeder wahre mathematische Satz kann aus den wie auch immer gewählten Axiomen einesmathematischen Teilgebietes (zum Beispiel Arithmetik, Geometrie, Algebra etcetera)formal abgeleitet werden.

Viel Verwirrung entsteht aus dem Zusammenhang der GödelschenUnvollständigkeitssätze mit dem Gödelschen Vollständigkeitssatz. Hier ist zu beachten,dass der Begriff der Vollständigkeit in zwei verschiedenen Bedeutungen gebraucht wird.Der Vollständigkeitssatz beweist die semantische Vollständigkeit der Prädikatenlogik der ersten Stufe, behandelt also eine Eigenschaft von formalen Systemen. Der 

Unvollständigkeitssatz hingegen beweist, dass gewisse Mengen von Ausdrücken nichtvollständig im klassischen Sinne sind.

Ein häufiger Fehlschluss aus dem Unvollständigkeitssatz ist, dass gewisse mathematischeObjekte, wie z. B. die natürlichen Zahlen nicht mit einer vollständigen Menge vonAusdrücken formalisierbar seien. Man erkennt aber sofort, dass die Menge aller Ausdrücke (in einer geeigneten formalen Sprache), die in der Menge der natürlichenZahlen gelten, sowohl vollständig ist als auch die natürlichen Zahlen formalisiert. EineKonsequenz aus dem Unvollständigkeitssatz ist aber, dass eine solche Mengenicht entscheidbar sein kann, womit sie eine in vielen Bereichen der Logik notwendigeEigenschaft nicht erfüllt.

Ein weiterer Fehlschluss ist, dass die meisten in der Mathematik benutzten Theorienunvollständig seien. Es gibt aber einige wichtige vollständige Theorien, wie z. B. dieTheorie der algebraisch abgeschlossenen Körper von Charakteristik p, die Theorie der dichten linearen Ordnungen ohne größtes und kleinstes Elementoder Tarskis Axiomatisierung der euklidischen Geometrie.

Sonstiges [Bearbeiten]

Gödel nannte seinen Aufsatz Über formal unentscheidbare Sätze der PrincipiaMathematica und verwandter Systeme I , weil er plante, einen zweiten Aufsatz zuverfassen, in dem er den Beweis genauer erläutern wollte. Der erste Aufsatz fand jedochbereits so große Anerkennung, dass der Bedarf für einen zweiten entfiel, der daher auch

nie geschrieben wurde.

Konkret bezog sich Gödels Aufsatz auf die Principia Mathematica, ein großes formalesSystem, das Bertrand Russell und Alfred North Whitehead zwischen 1910 und 1913veröffentlichten. Gödel zeigte jedoch auf, dass jedes System mit der gleichen Mächtigkeitwie die Principia Mathematica ebenso anfällig ist.

Weiterhin konnte Gerhard Gentzen zeigen, dass eine konstruktive Mathematik und Logikdurchaus widerspruchsfrei ist. Hier zeigt sich ein Grundlagenstreit der Mathematik. Der Philosoph Paul Lorenzen hat eine widerspruchsfreie Logik und Mathematik erarbeitet(Methodischer Konstruktivismus), und sein Buch Metamathematik (1962) eigensgeschrieben, um zu zeigen, dass der gödelsche Unvollständigkeitssatz keinen Einwandgegen einen widerspruchsfreien Aufbau der Mathematik darstellt.

5/13/2018 Diagonalsierung-Gödel-Stegmüller-ChristensenEDS - slidepdf.com

http://slidepdf.com/reader/full/diagonalsierung-goedel-stegmueller-christenseneds 31/49

 

Siehe auch [Bearbeiten]

• Metamathematik• Goodstein-Folgen haben eine innerhalb der Peano-Arithmetik formulierbare, aber 

nicht beweisbare Eigenschaft.• Referenzproblem

Literatur [Bearbeiten]• Kurt Gödel: Über formal unentscheidbare Sätze der Principia Mathematica und 

verwandter Systeme I . Monatshefte für Mathematik und Physik 38, 1931, S. 173–198, doi:10.1007/BF01700692.Zentralblatt MATH.

• Kurt Gödel: Diskussion zur Grundlegung der Mathematik: Erkenntnis 2 .Monatshefte für Math. und Physik, 1931–32, S. 147–148.

• Ernest Nagel u. James R. Newman: Der Gödelsche Beweis. 8. Auflage 2007. ISBN978-3-486-45218-1.

• Douglas R. Hofstadter : Gödel, Escher, Bach, ein Endloses Geflochtenes Band .München 1991 ISBN 3-423-30017-5 (Eine interessante und relativ leicht

verständliche Erklärung von Gödels Satz und seinen Implikationen).• Paul Lorenzen: Metamathematik . Mannheim 1962. ISBN 3-86025-870-2.• Wolfgang Franz: Über mathematische Aussagen, die samt ihrer Negation

nachweislich unbeweisbar sind. Der Unvollständigkeitssatz von Gödel. FranzSteiner Verlag, Wiesbaden, 1977, 27 S.,ISBN 3-515-02612-6. (verständlicher Vortrag mit wissenschaftsgeschichtlichen Bezügen).

• Torkel Franzen: Gödel’s Theorem. An incomplete guide to its use and abuse.Wellesley, Massachusetts 2005. ISBN 1-56881-238-8 (Eine leicht verständlicheErläuterung von Gödels Unvollständigkeitssätzen, ihren Implikationen und ihrenFehlinterpretationen).

• Max Woitschach: Gödel, Götzen und Computer: eine Kritik der unreinen Vernunft .

Stuttgart 1986. ISBN 3-87959-294-2.• Paul Lorenzen: Lehrbuch der konstruktiven Wissenschaftstheorie. Stuttgart

2000. ISBN 3-476-01784-2.• Wolfgang Stegmüller : Unvollständigkeit und Unentscheidbarkeit. Die

metamathematischen Resultate von Gödel, Church, Kleene, Rosser und ihreerkenntnistheoretische Bedeutung. 3. Auflage, Springer-Verlag, Wien, New York,1973. ISBN 3-211-81208-3. 116 S.

• Sybille Krämer: Symbolische Maschinen: die Idee der Formalisierung ingeschichtlichem Abriß. Darmstadt 1988. ISBN 3-534-03207-1.

• Ludwig Fischer: Die Grundlagen der Philosophie und der Mathematik . Leipzig 1933.•

Wolfgang Rautenberg: Einführung in die MathematischeLogik . Vieweg+Teubner , Wiesbaden 2008, ISBN 978-3-8348-0578-2 (http://www.springerlink.com/content/u46007/).

• Peter Smith: An Introduction to Gödel’s Theorems. Cambridge Introductions toPhilosophy. Cambridge 2007. ISBN 978-0-521-85784-0.

• S. G. Shanker (Hg.): Gödel’s Theorem in focus. London/New York 1988. ISBN 0-415-04575-4.

• Raymond Smullyan: Dame oder Tiger – Logische Denkspiele und einemathematische Novelle über Gödels große Entdeckung . Fischer-Verlag Frankfurtam Main 1983. Das amerikanische Original erschien bei Alfred A. Knopf, New York1982.

• Raymond Smullyan: To Mock a Mockingbird . 1985.• Raymond Smullyan: Forever undecided: a puzzle guide to Gödel . 1987.

5/13/2018 Diagonalsierung-Gödel-Stegmüller-ChristensenEDS - slidepdf.com

http://slidepdf.com/reader/full/diagonalsierung-goedel-stegmueller-christenseneds 32/49

 

• Raymond Smullyan: Gödel’s Incompleteness Theorems. Oxford Logic Guides.Oxford University Press, 1992.

• Max Urchs, Klassische Logik: eine Einführung, Berlin (1993). – ISBN 3-05-002228-0. (dort im Kapitel: Theorien erster Ordnung, S. 137–149).

• Palle Yourgrau: Gödel, Einstein und die Folgen. Vermächtnis einer ungewöhnlichenFreundschaft. Beck, München 2005. ISBN 3-406-52914-3. (Original: A World 

Without Time: The Forgotten Legacy of Gödel and Einstein. Basic Books,Cambridge, Massuchusetts 2005).

• Norbert Domeisen: Logik der Antinomien. Bern 1990. ISBN 3-261-04214-1, Zentralblatt MATH.

http://www.joergresag.privat.t-online.de/mybk3htm/start3.htm 

Die Grenzen der Berechenbarkeit

Unvollständigkeit und Zufall in der Mathematik

Jörg Resag

2008

5/13/2018 Diagonalsierung-Gödel-Stegmüller-ChristensenEDS - slidepdf.com

http://slidepdf.com/reader/full/diagonalsierung-goedel-stegmueller-christenseneds 33/49

 

Inhaltsverzeichnis

1 Vorwort

2 Die Unvollständigkeit formaler Systeme  2.1 Axiome und formale Systeme

2.2 Widerspruchsfreiheit, Vollständigkeit und Entscheidungsverfahren

2.3 Berechenbarkeit und Turings Halteproblem2.4 Gödels Satz über die Unvollständigkeit der Arithmetik2.5 Wie Gödel die Unvollständigkeit der Arithmetik bewies2.6 Ist Widerspruchsfreiheit beweisbar?

3 Im Umfeld von Gödels Theorem  3.1 Interpretationen der Gödel-Aussage G und übernatürliche Zahlen

3.2 Was bedeutet Gödels Theorem?3.3 Über die Komplexität und Zufälligkeit von Zahlen3.4 Chaitins Zufallszahl der Weisheit3.5 Über die Lösbarkeit diophantischer Gleichungen

4 Die Fundamente der Mathematik  4.1 Mengenlehre und Widersprüche

4.2 Die Axiome der Mengenlehre4.3 Die Kontinuumshypothese4.4 Logik, Interpretation und Skolems Paradoxon4.5 Infinitesimale und unendliche Größen (Nichtstandard-Analysis)4.6 Goodsteinfolgen, Ordinalzahlen und transfinite Induktion

5 Ungelöste Rätsel und weitere Themen  5.1 Die Komplexität von Problemen (ist P = NP ?)

5.2 Die Riemannsche Vermutung

5.3 Die 3-Sphäre und die Poincaré-Vermutung5.4 Quantenfeldtheorie und Eichfelder 

  5.4.1 Einleitung5.4.2 Die Grundpfeiler: spezielle Relativitätstheorie und Quantentheorie5.4.3 Die Quantisierung der klassischen Mechanik5.4.4 Die kanonische Quantisierung des freien elektromagnetischen Feldes5.4.5 Pfadintegral-Quantisierung des freien elektromagnetischen Feldes5.4.6 Eichtheorien5.4.7 Die Frage nach der Existenz einer Quanten-Eichtheorie

5.5 Ein kleiner mathematischer Rundgang

5.6 Mathematische Unendlichkeiten5.7 Unentscheidbarkeit und Wahrheit5.8 Quantencomputer 5.9 Kryptographie -- die Kunst der Verschlüsselung5.10 Die wundersame Welt der endlichen Gruppen (in Arbeit)

Dieses Buch wird immer wieder durch neue Kapitel erweitert, wenn ich ein Themabesonders interessant finde. Also gelegentlich mal vorbeischauen, ob es etwas Neuesgibt!

5/13/2018 Diagonalsierung-Gödel-Stegmüller-ChristensenEDS - slidepdf.com

http://slidepdf.com/reader/full/diagonalsierung-goedel-stegmueller-christenseneds 34/49

 

Ralf Josephy Kommen wir zu der mathematischen Seite des Verfahrens und damit sindwieder die Richter gefragt.

Kapitel 5Ungelöste Rätsel

7 Unentscheidbarkeit und Wahrheit

In diesem Kapitel möchte ich einer Frage nachgehen, die mich immer wieder beschäftigthat und die ich zunächst recht verwirrend finde:

Vermutung:

• Betrachten wir eine Aussage, die behauptet, dass es keinObjekt mit einer bestimmten Eigenschaft P gibt. Viele Fragen imRahmen der Zahlentheorie sind solche Aussagen,beispielsweise die Goldbachsche Vermutung. Was geschieht,wenn sich diese Aussage nun als unentscheidbar herausstellt?Nun, dann kann man jedenfalls kein Gegenbeispiel finden, denndann wäre die Aussage ja entscheidbar. Also muss dieAussage wahr sein.

Andererseits folgt aus der Unentscheidbarkeit aber, dass es neben Modellen, in denen die

Aussage wahr ist, auch Modelle geben muss, in denen die Aussage falsch ist. Genau sobeweist man ja typischerweise die Unentscheidbarkeit einer Aussage. Wäre die Aussagein allen Modellen wahr, so müsste sie nach Gödels Vollständigkeitssatz auch beweisbar sein (siehe Kapitel 4.4 ).

In einem Modell, in dem die Aussage falsch ist, muss es ein Gegenbeispiel geben. Aber oben hatten wir doch gerade behauptet, dass es kein Gegenbeispiel geben könne, denndamit wäre die Aussage ja entscheidbar. Wie passt das zusammen? Wie kann man obenbehaupten, dass die Aussage wahr ist?

Ein Lösungsansatz wäre: Ja, es gibt in bestimmten Modellen Gegenbeispiele, aber dasformale System, das wir hier modellieren, weiß davon nichts. Anders gesagt: DasGegenbeispiel ist zwar da, kann aber mit den Mitteln des formalen Systems nichtkonstruiert oder bewiesen werden. Das Gegenbeispiel existiert im speziellen Modell, seineExistenz kann aber nicht aus den Axiomen des formalen Systems abgeleitet werden. Esbefindet sich damit außerhalb der deduktiven Reichweite des formalen Systems.

Etwas Ähnliches ist uns bereits bei Skolems Paradoxon in Kapitel 4.4 begegnet. Dorthatten wir gelernt, dass es abzählbare Modelle der Mengenlehre gibt, dass aber dieMengenlehre zugleich beweisen kann, dass sie überabzählbare Mengen umfasst. ImModell gibt es nur abzählbare Mengen, aber diese Erkenntnis entzieht sich dem formalenSystem, das darin modelliert wird. Es gibt im Modell keine bijektive Modellfunktionzwischen der Modellmenge für die natürlichen und der für die reellen Zahlen. Im Prinzip

gibt es schon eine solche Funktion, aber diese ist keine Interpretation (Modell) einer Funktion aus dem formalen System, das hier modelliert wird.

5/13/2018 Diagonalsierung-Gödel-Stegmüller-ChristensenEDS - slidepdf.com

http://slidepdf.com/reader/full/diagonalsierung-goedel-stegmueller-christenseneds 35/49

 

Unsere Lösungsidee könnte also in die richtige Richtung führen. Dieser Verdacht verstärktsich, wenn wir uns an Kapitel 3.1 erinnern, in dem es um Gödels unentscheidbareAussage G und um übernatürliche Zahlen ging. Dort hatten wir die Situation, dass in der Peano-Arithmetik für jede natürliche Zahl g die Aussage NICHT B(m,g) beweisbar war,dass wir aber dennoch die dort unentscheidbare Aussage ES_GIBT y: B(m,y) zur Peano-Arithmetik hinzufügen konnten (das ist die Aussage NICHT G ). In den

natürlichen Zahlen ist also dieses y nicht zu finden -- es liegt außerhalb der Reichweite der natürlichen Zahlen. Wir sprachen daher vonübernatürlichen Zahlen.

Ok -- irgendwie haben wir also eine grobe Idee, was hier los sein könnte. Versuchen wir,diese Idee zu präzisieren:

Unentscheidbarkeit und Wahrheit in der Zahlentheorie:

Kehren wir zurück zu unserem Ausgangspunkt, also zu der Aussage, dass es kein Objektmit einer bestimmten Eigenschaft P gibt. Als formales System setzen wir die Peano-

Arithmetik voraus, also das formale System, das versucht, die natürlichen Zahlen zubeschreiben (siehe Kapitel 2.1 ). Unsere Aussage A lautet dann:

•A: NICHT ES_GIBT x : P(x)

oder vollkommen gleichwertig dazu:

•A: FÜR_ALLE x : NICHT P(x)

Es gibt also kein x mit der Eigenschaft P(x). Dabei soll P(x) in der Peano-Arithmetik entscheidbar sein, d.h. bei jedem gegebenem x kann man in endlich vielenSchritten in der Peano-Arithmetik ableiten, ob P(x) gilt oder nicht. Ein Beispiel für P(x)wäre die folgende Eigenschaft, die der berühmten Goldbachschen

Vermutung aus Kapitel 5.5 entspricht:•Goldbach: P(x) : x ist gerade und kann nicht als Summe zweier Primzahlengeschrieben werden

Die Goldbachsche Aussage A sagt also, dass es kein x gibt, dass gerade ist und nicht alsSumme zweier Primzahlen geschrieben werden kann. Für die zweite Version der AussageA ist auch NICHT P(x) interessant:

•Goldbach: NICHT P(x) : x ist ungerade oder kann als Summe zweier Primzahlen geschrieben werden

Die zweite Version der Goldbachschen Aussage A sagt also, dass alle x entweder 

ungerade sind oder als Summe zweier Primzahlen geschrieben werden können.Nehmen wir an, wir könnten für jede einzelne natürliche Zahl n (also für jeden n-fachenNachfolger der Null) in der Peano-Arithmetik einzeln zeigen, dass n nicht die EigenschaftP(n) hat. Für jedes n wäre also NICHT P(n) beweisbar (ganz analog zu NICHT B(m,g)

von oben). Können wir daraus in der Peano-Arithmetik die Aussage A: FÜR_ALLE x :NICHT P(x) ableiten? Von der Diskussion zu Gödels B(m,g) von oben wissen wir, dassdas nicht geht, denn es könnte ja eine übernatürliche Zahl x geben, die die EigenschaftP(x) aufweist.

Für die Goldbachsche Vermutung bedeutet das: Selbst wenn wir für jede einzelne geradenatürliche Zahl n in der Peano-Arithmetik beweisen könnten, dass sie als Summe zweier 

Primzahlen geschrieben werden kann, so können wir in der Peano-Arithmetik daraus nichtfolgern, dass das für alle geraden Zahlen x gilt (wegen der Möglichkeit übernatürlicher 

5/13/2018 Diagonalsierung-Gödel-Stegmüller-ChristensenEDS - slidepdf.com

http://slidepdf.com/reader/full/diagonalsierung-goedel-stegmueller-christenseneds 36/49

 

Zahlen). Wenn also die Goldbachsche Vermutung für alle natürlichen Zahlen wahr ist, sokönnen wir das in der Peano-Arithmetik nicht unbedingt allgemein beweisen.

Nehmen wir umgekehrt an, es gäbe eine natürliche Zahl n, die die Eigenschaft P(n)aufweist. Für die Goldbachsche Vermutung hieße das, dass wir eine natürliche Zahl nhätten, die gerade ist und nicht als Summe zweier Primzahlen geschrieben werden kann.Das wäre dann ein Gegenbeispiel zur Goldbachschen Vermutung. In der Peano-Arithmetik wäre dann die Formel P(n) für dieses n ableitbar, und ebenfalls ableitbar wäreder Ausdruck NICHT A: ES_GIBT x : P(x) . Das ist der entscheidende Punkt!

Fassen wir zusammen (siehe auch K.Podnieks: Incompleteness Theorems. RelatedResults ):

•Wenn sich für jede natürliche Zahl n einzeln in der Peano-Arithmetik zeigen lässt,dass es die entscheidbare Eigenschaft P(n) nicht hat, so kann man in der Peano-Arithmetik trotzdem nicht zeigen, dass alle x die Eigenschaft P(x) nicht haben. AusNICHT P(n) für jede natürliche Zahl n folgt in der Peano-Arithmetik nicht, dass dieAussage A: FÜR_ALLE x : NICHT P(x) gilt (es könnte ja eine übernatürliche

Zahl x geben, die formal die Eigenschaft P(x) hat).•Wenn es dagegen unter den natürlichen Zahlen ein Gegenbeispiel zur AussageA: FÜR_ALLE x : NICHT P(x) gibt, d.h. es gibt eine natürliche Zahl n mit der Eigenschaft P(n), so kann man in der Peano-Arithmetik die Aussage NICHT A:ES_GIBT x : P(x) ableiten.

Man kann es auch so ausdrücken:

 

• Wenn es unter den natürlichen Zahlen ein Gegenbeispiel zur Aussage A gibt, dann bekommt die Peano-Arithmetik das auchmit, d.h. sie kann die Aussage NICHT A beweisen. Wenn also

die Goldbachsche Vermutung falsch ist, dann gibt es in der Peano-Arithmetik auch einen Beweis dazu.

Was geschieht nun, wenn die Aussage A in der Peano-Arithmetik unentscheidbar ist?Dann kann es kein Gegenbeispiel zu A in den natürlichen Zahlen geben, denn sonstkönnte die Peano-Arithmetik beweisen, dass A falsch ist, und A wäre damit entscheidbar.Also muss A für natürliche Zahlen wahr sein, d.h. mögliche Gegenbeispiele gibt es formalnur außerhalb der natürlichen Zahlen.

Dieses Ergebnis bestätigt unsere Ausgangsvermutung und zugleich auch unserenLösungsansatz, beides bezogen auf die Zahlentheorie. Dabei wird die

Ausgangsvermutung entsprechend präzisiert:Unentscheidbarkeit und Wahrheit in der Zahlentheorie:

• Betrachten wir eine Aussage A der Peano-Arithmetik, diebehauptet, dass es keine Zahl mit einer bestimmten entscheidbaren Eigenschaft P gibt:

A: NICHT ES_GIBT x : P(x)

Wenn diese Aussage A unentscheidbar in der Peano-

Arithmetik ist, dann gibt es kein Gegenbeispiel in dennatürlichen Zahlen, denn ein solches Gegenbeispiel führt dazu,dass man NICHT A in der Peano-Arithmetik beweisen kann

5/13/2018 Diagonalsierung-Gödel-Stegmüller-ChristensenEDS - slidepdf.com

http://slidepdf.com/reader/full/diagonalsierung-goedel-stegmueller-christenseneds 37/49

 

und A damit entscheidbar wäre. Also muss die Aussage A für dienatürlichen Zahlen wahr sein.

Wenn A unentscheidbar ist, so gibt es Modelle der Peano-Arithmetik, in denen A falsch ist.Aber auch in diesen Modellen ist A für alle natürlichen Zahlen (also für allen n-fachen

Nachfolger der Null) wahr, d.h. alle n-fachen Nachfolger der Null haben nicht dieEigenschaft P(n). Das war genau unser Lösungsansatz von oben: Ja, es gibt in diesenModellen Gegenbeispiele, aber die Peano-Arithmetik weiß davon nichts, denn dieGegenbeispiele kann man mit den Mitteln der Peano-Arithmetik nicht konstruieren -- siesind keine n-fachen Nachfolger der Null, also keine natürlichen Zahlen.

Woher kann man wissen, ob A in der Peano-Arithmetik unentscheidbar ist? Innerhalb der Peano-Arithmetik kann man das jedenfalls nicht beweisen, denn sonst hätte die Peano-Arithmetik ja bewiesen, dass es keine Gegenbeispiele in den natürlichen Zahlen gibt. Manbraucht eine umfassendere Metatheorie -- nehmen wir wie immer die ZFC-Mengenlehre.Die Aussage A wird dazu aus der Sprache der Peano-Arithmetik in die Sprache der Mengenlehre übersetzt. In der Mengenlehre kann dann ein solcher Beweis der Unabhängigkeit der Aussage A von der Peano-Arithmetik ggf. geführt werden,beispielsweise durch Konstruktion entsprechender Modelle (siehe Kapitel 4.4 und Kapitel5.6 ). Damit hätte die Mengenlehre allerdings zugleich die Aussage A in etwas modifizierter Form bewiesen:

A': NICHT ES_GIBT x in N : P(x)

wobei N die Menge der natürlichen Zahlen ist. Konkret: Wenn man in der Mengenlehrebeweisen kann, dass die Goldbachsche Vermutung unabhängig von der Peano-Arithmetikist, dann hat man zugleich bewiesen, dass sie in den natürlichen Zahlen gilt.

Hier sehen wir wieder einmal sehr schön, dass die ZFC-Mengenlehre sehr viel mächtiger 

als die Peano-Arithmetik ist. Wenn es der Peano-Arithmetik nicht gelingt, eine Aussage Azu beweisen, so gelingt das vielleicht der ZFC-Mengenlehre, wobei die Aussage sokonkretisiert wird, dass die Variablen wirklich nur natürliche Zahlen sein können (diePeano-Arithmetik kann das nicht). Die Goodsteinfolgen aus Kapitel 4.6 waren einBeispiel für eine solche Aussage.

Und was wäre, wenn man in der ZFC-Mengenlehre nicht nur beweisen könnte, dass Aunabhängig von der Peano-Arithmetik ist, sondern sogar unabhängig von der ZFC-Mengenlehre selbst ist? So etwas ist ja im Prinzip möglich -- man denke an dieKontinuumshypothese. Im Grunde ändert das aber nichts, denn damit ist A auchunabhängig von der Peano-Arithmetik (die ZFC-Axiome umfassen ja die Peano-

Arithmetik). In den natürlichen Zahlen N ist A damit wahr, oder anders gesagt: die AussageA': NICHT ES_GIBT x in N : P(x) ist in der ZFC-Mengenlehre universell wahr. Nunwissen wir aber aus Kapitel 4.4, dass die universell wahren Aussagen genau diebeweisbaren Aussagen sind (Gödels Vollständigkeitssatz). Wenn also A unentscheidbar ist, so ist A' universell wahr und damit beweisbar. Kann auch A' unentscheidbar in ZFCsein? Wenn wir diese Unentscheidbarkeit in ZFC beweisen könnten, dann wäre A'universell wahr und damit beweisbar -- ein Widerspruch! Also können wir in ZFC nichtbeweisen, dass A' unentscheidbar in ZFC ist! Man sagt auch, A' ist (wennüberhaupt) bösartig unentscheidbar (siehe Jan Thor: Mersenne.pdf ).

Die Goldbachsche Vermutung in der Form A' ist also entweder falsch -- dann kann mandas im Prinzip auch beweisen, oder sie ist beweisbar wahr, oder sie ist in ZFCunentscheidbar und damit ebenfalls wahr, wobei wir diese Unentscheidbarkeit aber nie inZFC beweisen können. Damit wird verständlich, warum man in der Zahlentheorie imNormalfall nicht auf einfache unentscheidbare Aussagen trifft: Die meisten dieser 

5/13/2018 Diagonalsierung-Gödel-Stegmüller-ChristensenEDS - slidepdf.com

http://slidepdf.com/reader/full/diagonalsierung-goedel-stegmueller-christenseneds 38/49

 

Aussagen müssen bösartig unentscheidbar in ZFC sein, falls sie wirklich unentscheidbar in ZFC sind. Daher wissen wir auch normalerweise nicht, ob sie unentscheidbar in ZFCsind. Es sieht allerdings heute so aus, als sei die ZFC-Mengenlehre stark genug, umalle natürlicherweise in der Zahlentheorie auftretenden Aussagen über natürliche Zahlenentscheiden zu können. ZFC scheint bezüglich natürlicher arithmetischer Aussagenvollständig zu sein. Mit natürlich meint man Aussagen, die man nicht extra als unabhängig

von der ZFC-Mengenlehre konstruiert hat, sondern die man ohne Rücksicht auf dieMengenlehre in der üblichen Zahlentheorie untersucht.

Falls eine Aussage A' wie die Goldbachsche Vermutung in ZFC unentscheidbar und damitbösartig unentscheidbar wäre, so könnte es in einer Erweiterung von ZFC dennochgelingen, genau das zu beweisen. Damit wäre zugleich bewiesen, dass A' universell wahr ist, d.h. es muss einen Beweis für A' geben. Dieser Beweis kann dann allerdings nicht inZFC geführt werden, denn dort ist A' ja unentscheidbar. Man benötigt die Erweiterung vonZFC für den Beweis. Eine solche Erweiterung kann beispielsweise darin bestehen, dassman die Existenz von sehr mächtigen Mengen fordert -- mächtiger als alle Mengen, die mitZFC-Mitteln erreichbar sind. Vielleicht braucht man solche Mengen zur Erfassung

komplizierter divergierender Baumstrukturen im Beweis?! Mehr dazu siehe Kapitel 5.6.

Zusammenhang mit diophantischen Gleichungen:

Das Standardbeispiel für Unentscheidbarkeit im Reich der natürlichen Zahlen sinddie diophantischen Gleichungen, die wir in Kapitel 3.5 kennengelernt haben. Zunächsteine kurze Wiederholung:

Ein Beispiel für eine diophantische Gleichung ist die Gleichung

4x2 − 2xy + 3y2 + 2y − 7x + 81 = 0

Hier gibt es zwei Variablen x und y, und links steht ein Polynom vom Grad 2 in diesenbeiden Variablen mit ganzzahligen Koeffizienten. Gesucht sind natürliche Zahlen für x undy, so dass die Gleichung stimmt.

Allgemeiner kann eine diophantische Gleichung auch mehr Variablen umfassen und auchhöhere Potenzen. In Kapitel 3.5 hatten wir eine allgemeine diophantische Gleichung sogeschrieben:

P(x, n, y1, ..., ym) = 0

Dabei ist P ein Polynom mit ganzzahligen Koeffizienten, n ist eine vorgegebenenatürliche Zahl, die die Gestalt des Polynoms mitbestimmt, und x sowie y1, ..., ym 

sind die Variablen, für die bei gegebenem n Lösungen in den natürliche Zahlen gesuchtwerden. In der Schreibweise haben wir die Variable x gesondert bezeichnet, da wir dieLösungswerte für diese Variable separat in einer Menge Dn sammeln wollen, d.h. Dn 

ist die Menge aller Werte für x , für die es Werte der Variablen y1, ..., ym gibt, so dass

die Gleichung P(..) = 0 stimmt.

Ein entscheidendes Ergebnis war:

•Es gibt ein universelles Polynom P , so dass man durch Variieren desParameters n jede beliebige rekursiv aufzählbare (d.h. per Computer auflistbare)Menge natürlicher Zahlen als Lösungsmenge D

n

erzeugen kann.

Man kann also jeden Algorithmus zur Erzeugung von Zahlenlisten in eine diophantischeGleichung umwandeln, die als Lösungsmenge für x dieselbe Zahlenmenge ergibt. Diese

5/13/2018 Diagonalsierung-Gödel-Stegmüller-ChristensenEDS - slidepdf.com

http://slidepdf.com/reader/full/diagonalsierung-goedel-stegmueller-christenseneds 39/49

 

diophantische Gleichung kann man jeweils ganz konkret konstruieren, wobei allerdingssehr komplexe Gleichungen entstehen können. So hatten wir in Kapitel 3.5 eine Gleichunggesehen, die die Menge der Primzahlen als Lösungsmenge hat.

Übrigens: Jede ES_GIBT -Aussage der Peano-Arithmetik definiert eine rekursivaufzählbare Menge und ist damit äquivalent zur Lösbarkeit einer passendendiophantischen Gleichung. Die dazu negative NICHT ES_GIBT -Aussage (oder gleichwertig dazu die passende FÜR_ALLE -Aussage) ist dann äquivalent zur Nicht-Lösbarkeit der passenden diophantischen Gleichung. Siehe auch SolomonFefermann: The Impact of the Incompleteness Theorems on Mathematics, Notices of theAMS Vol. 53 No. 4, S. 434, im Internet.

Der externe Parameter n nummeriert alle rekursiv aufzählbaren Mengen komplett durch,d.h. die Liste aller Dn ist die Liste aller rekursiv aufzählbaren Mengen. Auf diese Liste lässt

sich nun Cantors Diagonalmethodeanwenden: Wir stellen für alle Werte von n dieFrage, ob dieses n selbst in der zugehörigen Lösungsmenge Dn auftaucht. Falls nicht,

nehmen wir es in eine Menge V auf, d.h. die Menge V ist definiert als

V := { n aus N , n gehört nicht zu Dn }

Diese Menge V unterscheidet sich von jeder Menge Dn , denn wenn Dn die Zahl n

enthält, so enthält V sie nicht und umgekehrt. Damit ist V nicht in der Liste aller Dn enthalten, ist also auch keine rekursiv aufzählbare Menge (denn die stehen alle in der 

Liste drin). Es gibt also kein Computerprogramm, das die Elemente der Menge V auflistenkann. Entsprechend kann kein Computerprogramm für alle natürlichen Zahlen n dieFrage beantworten, ob dieses n wirklich nicht in der zugehörigen LösungsmengeDn auftaucht, denn sonst könnte dieses Programm ja die Menge V auflisten. Da hilft dann

auch die Auflistung der Elemente von Dn nichts, denn man kann die Liste bei unendlich

vielen Elementen ja nie komplett durchsuchen.

Nun war Dn die Lösungsmenge aller x, für die die Gleichung P(x, n, y1, ..., ym) = 0 bei

geeigneten Werten für die Hilfsvariablen y1, ..., ym erfüllt ist. Wenn man nun nicht

allgemein entscheiden kann, ob ein n zu Dn gehört, so kann man auch nicht

allgemein entscheiden, ob die Gleichung P(n, n, y1, ..., ym) = 0 (also mit x = n ) für 

geeignete Werte der Hilfsvariablen y1, ..., ym erfüllt ist, d.h. ob es Lösungen für y1, ...,

ym gibt. Damit gibt es kein allgemeines Entscheidungsverfahren für die Lösbarkeit

diophantischer Gleichungen.

Das alles kannten wir schon aus Kapitel 3.5. Wie hängt das nun mit dem Thema desaktuellen Kapitels zusammen? Dazu habe ich in Martin Davis: The IncompletenessTheorem, Notices of the AMS, Vol 53, No. 4, S.414 (im Internet) das Folgende gefunden:

Nach unserem Ergebnis muss es für jedes Entscheidungsverfahren mindestens ein n0 

geben, das nicht zu Dn0 gehört und bei dem wir das mit dem Entscheidungsverfahren

nicht nachweisen können. Entsprechend können wir auch nicht nachweisen, dass diezugehörige diophantische Gleichung P(n0, n0, y1, ..., ym) = 0 für dieses

n0  keine Lösungen in y1, ..., ym hat. Die Aussage

• FÜR_ALLE y1, ..., y

m: NICHT P(n

0, n

0, y

1, ..., y

m) = 0

ist für das gegebene Entscheidungsverfahren für dieses n0 nicht entscheidbar. Das siehtgenauso aus wie unsere Aussage A von ganz oben, nur mit mehreren Variablen statt

5/13/2018 Diagonalsierung-Gödel-Stegmüller-ChristensenEDS - slidepdf.com

http://slidepdf.com/reader/full/diagonalsierung-goedel-stegmueller-christenseneds 40/49

 

nur mit einer, was aber keine große Rolle spielt. Insofern gilt alles, was wir oben über Abzw. A' gesagt haben, auch hier, d.h. die Aussage ist unentscheidbar und deswegen für natürliche Zahlen wahr.

Welche Werte für n0 in Frage kommen, hängt von dem Entscheidungsverfahren ab, das

wir anwenden. Egal welches Verfahren wir anwenden, es gibt immer mindestens ein n0 

, das diesem Verfahren entschlüpft, so dass der obige Satz unentscheidbar ist.Eine Möglichkeit für Entscheidungsverfahren sind Beweise in der Peano-Arithmetik (siehedas Representation Theorem in Kapitel 2.4 ). Eine andere mächtigere Möglichkeit sindBeweise in der ZFC-Mengenlehre. Da die ZFC-Mengenlehre sehr viel mächtiger als diePeano-Arithmetik ist, wird es Aussagen geben, die für die Peano-Arithmetikunentscheidbar sind, die aber in der ZFC-Mengenlehre entschieden werden können.Daher gilt (siehe Martin Davis: The Incompleteness Theorem, Notices of the AMS, Vol 53,No. 4, S.414 (im Internet) ):

•Es gibt eine natürliche Zahl n0 , so dass die obige Aussage

FÜR_ALLE y1, ..., y

m: NICHT P(n

0, n

0, y

1, ..., y

m) = 0

in der Peano-Arithmetik unentscheidbar ist, aber in der ZFC-Mengenlehre bewiesenwerden kann.

Bei manchen diophantischen Gleichungen kann also erst die ZFC-Mengenlehre beweisen,dass sie keine Lösungen haben, während die Peano-Arithmetik dafür zu schwach ist. Erstdie ZFC-Mengenlehre wird dann auch ein entsprechendes n0 ermitteln können, denn

die Peano-Arithmetik wird die Unentscheidbarkeit für dieses n0 nicht sehen können.

Aber auch für die ZFC-Mengenlehre muss es mindestens ein n0 geben, so dass die

obige Aussage unentscheidbar ist, wobei die ZFC-Mengenlehre ein solches n0 nicht

ermitteln kann (die Werte für n0 dürften ziemlich große natürliche Zahlen sein, dennn0 kodiert gewissermaßen die Beweiskraft des formalen Systems -- entsprechend

komplex sind dann die diophantischen Gleichungen). Es gibt also arithmetische Aussagen(also Aussagen über natürliche Zahlen), die in ZFC unentscheidbar sind. Allerdings wärebeispielsweise eine entsprechende diophantische Gleichung sehr kompliziert und sie wäreüber das Diagonalverfahren oben auch extra so konstruiert, dass sie in ZFCunentscheidbar ist (wobei man in einer geeigneten ZFC-Erweiterung noch das passenden0 ermitteln muss). Dagegen haben wir oben bereits gesagt, dass ZFC

bezüglich natürlicher arithmetischer Aussagen vollständig zu sein scheint. In diesem Sinnewäre die speziell konstruierte diophantische Gleichung als unnatürlich anzusehen -- eben

eine Spezialkonstruktion.

Unentscheidbarkeit und Wahrheit in der ZFC-Mengenlehre:

Halten wir noch einmal fest: Wenn eine Aussage der Form A': NICHT ES_GIBT x in N :P(x) wie beispielsweise die Goldbachsche Vermutung in der ZFC-Mengenlehreunentscheidbar ist, so ist sie bösartig unentscheidbar , d.h. wir können dieseUnentscheidbarkeit in ZFC nicht beweisen. Wie passt das mit ähnlichen Aussagenzusammen, von denen wir wissen, dass sie in ZFC unentscheidbar sind (Beispiel:Kontinuumshypothese)? Was unterscheidet die Kontinuumshypothese von der Goldbachschen Vermutung? Auch die Kontinuumshypothese ist ja von der Form

K: NICHT ES_GIBT x : Q(x)

5/13/2018 Diagonalsierung-Gödel-Stegmüller-ChristensenEDS - slidepdf.com

http://slidepdf.com/reader/full/diagonalsierung-goedel-stegmueller-christenseneds 41/49

 

Dabei ist allerdings x nicht aus N, sondern irgendeine Menge, und Q(x) sagt, dass dieMächtigkeit dieser Menge zwischen den natürlichen und den reellen Zahlen liegt. DieMenge x ist also überabzählbar, aber bei jeder Bijektion von x in die reellen Zahlen bleibenimmer reelle Zahlen übrig (siehe Kapitel 4.3 und Kapitel 5.6 ). Die Kontinuumshypothesesagt, dass es eine solche Menge zwischen den natürlichen und den reellen Zahlen nichtgibt.

Im Internet habe ich dazu den folgenden sehr interessanten Text gefunden: Jan Thor:Mersenne.pdf . An diesem Text orientiere ich mich im Folgenden.

In der Zahlentheorie hatten wir die Voraussetzung gemacht, dass die Eigenschaft P(x) inendlich vielen Schritten entscheidbar sein muss. So kann man bei jeder natürlichen Zahlper Computer immer nachprüfen, ob sie sich als Summe zweier Primzahlen schreibenlässt -- man muss nur alle kleineren Primzahlen durchprobieren. Bei der Eigenschaft Q(x)der Kontinuumshypothese ist das sehr viel weniger durchsichtig. Es hängt davon ab, wiekonkret die Menge x ist. Man kann aber nicht davon ausgehen, dass man für  jededenkbare Menge x mechanisch nachprüfen kann, ob ihre Mächtigkeit zwischen dennatürlichen und den reellen Zahlen liegt.

Nehmen wir analog zur Zahlentheorie an, es gäbe eine Menge x, die die Eigenschaft Q(x)aufweist. Das wäre dann ein Gegenbeispiel zur Kontinuumshypothese. Anders als in der Zahlentheorie ist aber unklar, ob ZFC das erkennt, d.h. ob ZFC für diese Menge x auchden Ausdruck Q(x) ableiten kann. Die Eigenschaft Q(x) ist eben nicht allgemeinentscheidbar.

Man kann die denkbaren Mengen allerdings einschränken, beispielsweise indemman Gödel-Konstruierbarkeit fodert. Damit werden die Mengen so konkret, dass Q(x)entscheidbar wird. Wenn man jetzt eine konstruierbare Menge x fände, die die EigenschaftQ(x) aufweist (also zwischen den natürlichen und reellen Zahlen liegt), dann kann ZFCauch die Aussage NICHT K: ES_GIBT x : Q(x) ableiten, d.h. die Kontinuumshypothese

wäre durch Gegenbeispiel widerlegt.Nun weiß man aber, dass die Kontinuumshypothese unentscheidbar in ZFC ist. Daher kann es auch kein konstruierbares Gegenbeispiel geben, denn sonst wäre dieKontinuumshypothese widerlegt und damit entscheidbar. Ein mögliches Gegenbeispielmuss also so wenig greifbar sein, dass ZFC das Gegenbeispiel nicht konkretisieren kann.ZFC kann für kein konkretes x die Eigenschaft Q(x) nachweisen, denn sonst hätte ZFC dieKontinuumshypothese widerlegt und damit entschieden.

Daher ist klar, dass es unter den konkreten Mengen kein Gegenbeispiel zur Kontinuumshypothese geben kann. Immer dann, wenn man sich auf konkrete Mengenbeschränkt, so gilt die Kontinuumshypothese für diese Mengen, d.h. sie wird wahr unddamit für diese Mengen entscheidbar. Trotzdem scheint es sinnvoll zu sein, dieKontinuumshypothese besser als falsch anzusehen, da man sich dadurch mehr Denkfreiheit offen lässt. Man lässt also im Prinzip Gegenbeispiele zur Kontinuumshypothese zu, wobei man weiß, dass man nicht mit dem Finger auf sie zeigenkann. Mögliche Gegenbeispiele bleiben immer sehr abstrakt -- mehr dazu siehe Kapitel5.6.

Literatur:

•

Jan Thor: Mersenne.pdf  •K.Podnieks: Incompleteness Theorems. Related Results

5/13/2018 Diagonalsierung-Gödel-Stegmüller-ChristensenEDS - slidepdf.com

http://slidepdf.com/reader/full/diagonalsierung-goedel-stegmueller-christenseneds 42/49

 

•Martin Davis: The Incompleteness Theorem, Notices of the AMS, Vol 53, No. 4,S.414 (im Internet)

•Solomon Fefermann: The Impact of the Incompleteness Theorems onMathematics, Notices of the AMS Vol. 53 No. 4, S. 434, im Internet

•Bjorn Poonen: Undecidability in number theory , im Internet

Austausch der EPOS 2.0 QS, wichtigster Beitrag MBP (EDS), damals WestLB Systems.

Lesen Sie ein gutes Buch diagonal: Am besten Schwejk als Kryptoexperte, besser  jedenfalls als die Enigma Konstrukteure.

Diagonalisierung von Stakeholderentscheidungen (Semantische QS von Fachentwürfenbezogen auf ein Spiralmodell).

Kapitel 5

Ungelöste Rätsel

7 Unentscheidbarkeit und Wahrheit

In diesem Kapitel möchte ich einer Frage nachgehen, die mich immer wieder beschäftigt hat unddie ich zunächst recht verwirrend finde:

Vermutung:

• Betrachten wir eine Aussage, die behauptet, dass es kein Objekt miteiner bestimmten Eigenschaft P gibt. Viele Fragen im Rahmen der Zahlentheorie sind solche Aussagen, beispielsweise die GoldbachscheVermutung. Was geschieht, wenn sich diese Aussage nunals unentscheidbar herausstellt? Nun, dann kann man jedenfalls keinGegenbeispiel finden, denn dann wäre die Aussage ja entscheidbar.Also muss die Aussage wahr sein.

Andererseits folgt aus der Unentscheidbarkeit aber, dass es neben Modellen, in denen die Aussagewahr ist, auch Modelle geben muss, in denen die Aussage falsch ist. Genau so beweist man ja

typischerweise die Unentscheidbarkeit einer Aussage. Wäre die Aussage in allen Modellen wahr, somüsste sie nach Gödels Vollständigkeitssatz auch beweisbar sein (siehe Kapitel 4.4 ).

In einem Modell, in dem die Aussage falsch ist, muss es ein Gegenbeispiel geben. Aber oben hattenwir doch gerade behauptet, dass es kein Gegenbeispiel geben könne, denn damit wäre die Aussage

 ja entscheidbar. Wie passt das zusammen? Wie kann man oben behaupten, dass die Aussage wahr ist?

Ein Lösungsansatz wäre: Ja, es gibt in bestimmten Modellen Gegenbeispiele, aber das formaleSystem, das wir hier modellieren, weiß davon nichts. Anders gesagt: Das Gegenbeispiel ist zwar da,kann aber mit den Mitteln des formalen Systems nicht konstruiert oder bewiesen werden. DasGegenbeispiel existiert im speziellen Modell, seine Existenz kann aber nicht aus den Axiomen des

formalen Systems abgeleitet werden. Es befindet sich damit außerhalb der deduktiven Reichweitedes formalen Systems.

5/13/2018 Diagonalsierung-Gödel-Stegmüller-ChristensenEDS - slidepdf.com

http://slidepdf.com/reader/full/diagonalsierung-goedel-stegmueller-christenseneds 43/49

 

Etwas Ähnliches ist uns bereits bei Skolems Paradoxon in Kapitel 4.4 begegnet. Dort hatten wir gelernt, dass es abzählbare Modelle der Mengenlehre gibt, dass aber die Mengenlehre zugleich

 beweisen kann, dass sie überabzählbare Mengen umfasst. Im Modell gibt es nur abzählbareMengen, aber diese Erkenntnis entzieht sich dem formalen System, das darin modelliert wird. Esgibt im Modell keine bijektive Modellfunktion zwischen der Modellmenge für die natürlichen undder für die reellen Zahlen. Im Prinzip gibt es schon eine solche Funktion, aber diese ist keine

Interpretation (Modell) einer Funktion aus dem formalen System, das hier modelliert wird.Unsere Lösungsidee könnte also in die richtige Richtung führen. Dieser Verdacht verstärkt sich,wenn wir uns an Kapitel 3.1 erinnern, in dem es um Gödels unentscheidbare Aussage G und umübernatürliche Zahlen ging. Dort hatten wir die Situation, dass in der Peano-Arithmetik für jedenatürliche Zahl g die Aussage NICHT B(m,g) beweisbar war, dass wir aber dennoch die dortunentscheidbare Aussage ES_GIBT y: B(m,y) zur Peano-Arithmetik hinzufügen konnten (das istdie Aussage NICHT G ). In den natürlichen Zahlen ist also dieses y nicht zu finden -- es liegtaußerhalb der Reichweite der natürlichen Zahlen. Wir sprachen daher vonübernatürlichen Zahlen.

Ok -- irgendwie haben wir also eine grobe Idee, was hier los sein könnte. Versuchen wir, diese Ideezu präzisieren:

Unentscheidbarkeit und Wahrheit in der Zahlentheorie:

Kehren wir zurück zu unserem Ausgangspunkt, also zu der Aussage, dass es kein Objekt mit einer  bestimmten Eigenschaft P gibt. Als formales System setzen wir die Peano-Arithmetik voraus, alsodas formale System, das versucht, die natürlichen Zahlen zu beschreiben (siehe Kapitel 2.1 ).Unsere Aussage A lautet dann:

•A: NICHT ES_GIBT x : P(x)

oder vollkommen gleichwertig dazu:

•A: FÜR_ALLE x : NICHT P(x)

Es gibt also kein x mit der Eigenschaft P(x). Dabei soll P(x) in der Peano-Arithmetik entscheidbar sein, d.h. bei jedem gegebenem x kann man in endlich vielen Schritten inder Peano-Arithmetik ableiten, ob P(x) gilt oder nicht. Ein Beispiel für P(x) wäre die folgendeEigenschaft, die der berühmten Goldbachschen Vermutung aus Kapitel 5.5 entspricht:

•Goldbach: P(x) : x ist gerade und kann nicht als Summe zweier Primzahlen geschriebenwerden

Die Goldbachsche Aussage A sagt also, dass es kein x gibt, dass gerade ist und nicht als Summezweier Primzahlen geschrieben werden kann. Für die zweite Version der Aussage A ist auch

  NICHT P(x) interessant:•Goldbach: NICHT P(x) : x ist ungerade oder kann als Summe zweier Primzahlengeschrieben werden

Die zweite Version der Goldbachschen Aussage A sagt also, dass alle x entweder ungerade sind oder als Summe zweier Primzahlen geschrieben werden können.

 Nehmen wir an, wir könnten für jede einzelne natürliche Zahl n (also für jeden n-fachen Nachfolger der Null) in der Peano-Arithmetik einzeln zeigen, dass n nicht die Eigenschaft P(n) hat. Für jedes nwäre also NICHT P(n) beweisbar (ganz analog zu NICHT B(m,g) von oben). Können wir daraus in der Peano-Arithmetik die Aussage A: FÜR_ALLE x : NICHT P(x) ableiten? Von der 

Diskussion zu Gödels B(m,g) von oben wissen wir, dass das nicht geht, denn es könnte ja eineübernatürliche Zahl x geben, die die Eigenschaft P(x) aufweist.

5/13/2018 Diagonalsierung-Gödel-Stegmüller-ChristensenEDS - slidepdf.com

http://slidepdf.com/reader/full/diagonalsierung-goedel-stegmueller-christenseneds 44/49

 

Für die Goldbachsche Vermutung bedeutet das: Selbst wenn wir für jede einzelne gerade natürlicheZahl n in der Peano-Arithmetik beweisen könnten, dass sie als Summe zweier Primzahlengeschrieben werden kann, so können wir in der Peano-Arithmetik daraus nicht folgern, dass dasfür alle geraden Zahlen x gilt (wegen der Möglichkeit übernatürlicher Zahlen). Wenn also dieGoldbachsche Vermutung für alle natürlichen Zahlen wahr ist, so können wir das in der Peano-Arithmetik nicht unbedingt allgemein beweisen.

 Nehmen wir umgekehrt an, es gäbe eine natürliche Zahl n, die die Eigenschaft P(n) aufweist. Für die Goldbachsche Vermutung hieße das, dass wir eine natürliche Zahl n hätten, die gerade ist undnicht als Summe zweier Primzahlen geschrieben werden kann. Das wäre dannein Gegenbeispiel zur Goldbachschen Vermutung. In der Peano-Arithmetik wäre dann die FormelP(n) für dieses n ableitbar, und ebenfalls ableitbar wäre der Ausdruck NICHT A: ES_GIBT x :P(x) . Das ist der entscheidende Punkt!

Fassen wir zusammen (siehe auch K.Podnieks: Incompleteness Theorems. Related Results ):

•Wenn sich für jede natürliche Zahl n einzeln in der Peano-Arithmetik zeigen lässt, dass esdie entscheidbare Eigenschaft P(n) nicht hat, so kann man in der Peano-Arithmetik trotzdem

nicht zeigen, dass alle x die Eigenschaft P(x) nicht haben. Aus NICHT P(n) für jedenatürliche Zahl n folgt in der Peano-Arithmetik nicht, dass die Aussage A: FÜR_ALLEx : NICHT P(x) gilt (es könnte ja eine übernatürliche Zahl x geben, die formal dieEigenschaft P(x) hat).

•Wenn es dagegen unter den natürlichen Zahlen ein Gegenbeispiel zur Aussage A:FÜR_ALLE x : NICHT P(x) gibt, d.h. es gibt eine natürliche Zahl n mit der EigenschaftP(n), so kann man in der Peano-Arithmetik die Aussage NICHT A: ES_GIBT x : P(x)ableiten.

Man kann es auch so ausdrücken:

 

•

Wenn es unter den natürlichen Zahlen ein Gegenbeispiel zur AussageA gibt, dann bekommt die Peano-Arithmetik das auch mit, d.h. siekann die Aussage NICHT A beweisen. Wenn also die GoldbachscheVermutung falsch ist, dann gibt es in der Peano-Arithmetik auch einenBeweis dazu.

Was geschieht nun, wenn die Aussage A in der Peano-Arithmetik unentscheidbar ist? Dann kannes kein Gegenbeispiel zu A in den natürlichen Zahlen geben, denn sonst könnte die Peano-Arithmetik beweisen, dass A falsch ist, und A wäre damit entscheidbar. Also muss A für natürlicheZahlen wahr sein, d.h. mögliche Gegenbeispiele gibt es formal nur außerhalb der natürlichenZahlen.

Dieses Ergebnis bestätigt unsere Ausgangsvermutung und zugleich auch unseren Lösungsansatz, beides bezogen auf die Zahlentheorie. Dabei wird die Ausgangsvermutung entsprechend präzisiert:

Unentscheidbarkeit und Wahrheit in der Zahlentheorie:

• Betrachten wir eine Aussage A der Peano-Arithmetik, die behauptet,dass es keine Zahl mit einer bestimmten entscheidbaren Eigenschaft Pgibt:

A: NICHT ES_GIBT x : P(x)

Wenn diese Aussage A unentscheidbar in der Peano-Arithmetik ist,dann gibt es kein Gegenbeispiel in den natürlichen Zahlen, denn ein

5/13/2018 Diagonalsierung-Gödel-Stegmüller-ChristensenEDS - slidepdf.com

http://slidepdf.com/reader/full/diagonalsierung-goedel-stegmueller-christenseneds 45/49

 

solches Gegenbeispiel führt dazu, dass man NICHT A in der Peano-Arithmetik beweisen kann und A damit entscheidbar wäre. Also mussdie Aussage A für die natürlichen Zahlen wahr sein.

Wenn A unentscheidbar ist, so gibt es Modelle der Peano-Arithmetik, in denen A falsch ist. Aber 

auch in diesen Modellen ist A für alle natürlichen Zahlen (also für allen n-fachen Nachfolger der  Null) wahr, d.h. alle n-fachen Nachfolger der Null haben nicht die Eigenschaft P(n). Das war genauunser Lösungsansatz von oben: Ja, es gibt in diesen Modellen Gegenbeispiele, aber die Peano-Arithmetik weiß davon nichts, denn die Gegenbeispiele kann man mit den Mitteln der Peano-Arithmetik nicht konstruieren -- sie sind keine n-fachen Nachfolger der Null, also keine natürlichenZahlen.

Woher kann man wissen, ob A in der Peano-Arithmetik unentscheidbar ist? Innerhalb der Peano-Arithmetik kann man das jedenfalls nicht beweisen, denn sonst hätte die Peano-Arithmetik ja

 bewiesen, dass es keine Gegenbeispiele in den natürlichen Zahlen gibt. Man braucht eineumfassendere Metatheorie -- nehmen wir wie immer die ZFC-Mengenlehre. Die Aussage A wirddazu aus der Sprache der Peano-Arithmetik in die Sprache der Mengenlehre übersetzt. In der Mengenlehre kann dann ein solcher Beweis der Unabhängigkeit der Aussage A von der Peano-Arithmetik ggf. geführt werden, beispielsweise durch Konstruktion entsprechender Modelle(siehe Kapitel 4.4 und Kapitel 5.6 ). Damit hätte die Mengenlehre allerdings zugleich die Aussage Ain etwas modifizierter Form bewiesen:

A': NICHT ES_GIBT x in N : P(x)

wobei N die Menge der natürlichen Zahlen ist. Konkret: Wenn man in der Mengenlehre beweisenkann, dass die Goldbachsche Vermutung unabhängig von der Peano-Arithmetik ist, dann hat manzugleich bewiesen, dass sie in den natürlichen Zahlen gilt.

Hier sehen wir wieder einmal sehr schön, dass die ZFC-Mengenlehre sehr viel mächtiger als die

Peano-Arithmetik ist. Wenn es der Peano-Arithmetik nicht gelingt, eine Aussage A zu beweisen, sogelingt das vielleicht der ZFC-Mengenlehre, wobei die Aussage so konkretisiert wird, dass dieVariablen wirklich nur natürliche Zahlen sein können (die Peano-Arithmetik kann das nicht).Die Goodsteinfolgen aus Kapitel 4.6 waren ein Beispiel für eine solche Aussage.

Und was wäre, wenn man in der ZFC-Mengenlehre nicht nur beweisen könnte, dass A unabhängigvon der Peano-Arithmetik ist, sondern sogar unabhängig von der ZFC-Mengenlehre selbst ist? Soetwas ist ja im Prinzip möglich -- man denke an die Kontinuumshypothese. Im Grunde ändert dasaber nichts, denn damit ist A auch unabhängig von der Peano-Arithmetik (die ZFC-Axiomeumfassen ja die Peano-Arithmetik). In den natürlichen Zahlen N ist A damit wahr, oder andersgesagt: die Aussage A': NICHT ES_GIBT x in N : P(x) ist in der ZFC-Mengenlehre universell

wahr. Nun wissen wir aber aus Kapitel 4.4, dass die universell wahren Aussagen genau die beweisbaren Aussagen sind (Gödels Vollständigkeitssatz). Wenn also A unentscheidbar ist, so ist A'universell wahr und damit beweisbar. Kann auch A' unentscheidbar in ZFC sein? Wenn wir dieseUnentscheidbarkeit in ZFC beweisen könnten, dann wäre A' universell wahr und damit beweisbar --ein Widerspruch! Also können wir in ZFC nicht beweisen, dass A' unentscheidbar in ZFC ist! Mansagt auch, A' ist (wenn überhaupt) bösartig unentscheidbar (siehe Jan Thor: Mersenne.pdf ).

Die Goldbachsche Vermutung in der Form A' ist also entweder falsch -- dann kann man das imPrinzip auch beweisen, oder sie ist beweisbar wahr, oder sie ist in ZFC unentscheidbar und damitebenfalls wahr, wobei wir diese Unentscheidbarkeit aber nie in ZFC beweisen können. Damit wirdverständlich, warum man in der Zahlentheorie im Normalfall nicht auf einfache unentscheidbareAussagen trifft: Die meisten dieser Aussagen müssen bösartig unentscheidbar in ZFC sein, falls sie

wirklich unentscheidbar in ZFC sind. Daher wissen wir auch normalerweise nicht, ob sieunentscheidbar in ZFC sind. Es sieht allerdings heute so aus, als sei die ZFC-Mengenlehre stark genug, um alle natürlicherweise in der Zahlentheorie auftretenden Aussagen über natürliche Zahlen

5/13/2018 Diagonalsierung-Gödel-Stegmüller-ChristensenEDS - slidepdf.com

http://slidepdf.com/reader/full/diagonalsierung-goedel-stegmueller-christenseneds 46/49

 

entscheiden zu können. ZFC scheint bezüglich natürlicher arithmetischer Aussagen vollständig zusein. Mit natürlich meint man Aussagen, die man nicht extra als unabhängig von der ZFC-Mengenlehre konstruiert hat, sondern die man ohne Rücksicht auf die Mengenlehre in der üblichenZahlentheorie untersucht.

Falls eine Aussage A' wie die Goldbachsche Vermutung in ZFC unentscheidbar und damit bösartigunentscheidbar wäre, so könnte es in einer Erweiterung von ZFC dennoch gelingen, genau das zu

 beweisen. Damit wäre zugleich bewiesen, dass A' universell wahr ist, d.h. es muss einen Beweis für A' geben. Dieser Beweis kann dann allerdings nicht in ZFC geführt werden, denn dort ist A' jaunentscheidbar. Man benötigt die Erweiterung von ZFC für den Beweis. Eine solche Erweiterungkann beispielsweise darin bestehen, dass man die Existenz von sehr mächtigen Mengen fordert --mächtiger als alle Mengen, die mit ZFC-Mitteln erreichbar sind. Vielleicht braucht man solcheMengen zur Erfassung komplizierter divergierender Baumstrukturen im Beweis?! Mehr dazusiehe Kapitel 5.6.

Zusammenhang mit diophantischen Gleichungen:

Das Standardbeispiel für Unentscheidbarkeit im Reich der natürlichen Zahlen sinddie diophantischen Gleichungen, die wir in Kapitel 3.5 kennengelernt haben. Zunächst eine kurzeWiederholung:

Ein Beispiel für eine diophantische Gleichung ist die Gleichung

4x2 − 2xy + 3y2 + 2y − 7x + 81 = 0

Hier gibt es zwei Variablen x und y, und links steht ein Polynom vom Grad 2 in diesen beidenVariablen mit ganzzahligen Koeffizienten. Gesucht sind natürliche Zahlen für x und y, so dass dieGleichung stimmt.

Allgemeiner kann eine diophantische Gleichung auch mehr Variablen umfassen und auch höhere

Potenzen. In Kapitel 3.5 hatten wir eine allgemeine diophantische Gleichung so geschrieben:

P(x, n, y1, ..., ym) = 0

Dabei ist P ein Polynom mit ganzzahligen Koeffizienten, n ist eine vorgegebene natürlicheZahl, die die Gestalt des Polynoms mitbestimmt, und x sowie y1, ..., ym sind die Variablen, für 

die bei gegebenem n Lösungen in den natürliche Zahlen gesucht werden. In der Schreibweisehaben wir die Variable x gesondert bezeichnet, da wir die Lösungswerte für diese Variable separatin einer Menge Dn sammeln wollen, d.h. Dn ist die Menge aller Werte für x , für die es Werte

der Variablen y1, ..., ym gibt, so dass die Gleichung P(..) = 0 stimmt.

Ein entscheidendes Ergebnis war:

•Es gibt ein universelles Polynom P , so dass man durch Variieren des Parameters n jede beliebige rekursiv aufzählbare (d.h. per Computer auflistbare) Menge natürlicher Zahlen alsLösungsmenge Dn erzeugen kann.

Man kann also jeden Algorithmus zur Erzeugung von Zahlenlisten in eine diophantische Gleichungumwandeln, die als Lösungsmenge für x dieselbe Zahlenmenge ergibt. Diese diophantischeGleichung kann man jeweils ganz konkret konstruieren, wobei allerdings sehr komplexeGleichungen entstehen können. So hatten wir in Kapitel 3.5 eine Gleichung gesehen, die die Mengeder Primzahlen als Lösungsmenge hat.

Übrigens: Jede ES_GIBT -Aussage der Peano-Arithmetik definiert eine rekursiv aufzählbareMenge und ist damit äquivalent zur Lösbarkeit einer passenden diophantischen Gleichung. Die dazunegative NICHT ES_GIBT -Aussage (oder gleichwertig dazu die passende FÜR_ALLE

5/13/2018 Diagonalsierung-Gödel-Stegmüller-ChristensenEDS - slidepdf.com

http://slidepdf.com/reader/full/diagonalsierung-goedel-stegmueller-christenseneds 47/49

 

-Aussage) ist dann äquivalent zur Nicht-Lösbarkeit der passenden diophantischen Gleichung. Sieheauch Solomon Fefermann: The Impact of the Incompleteness Theorems on Mathematics, Notices of the AMS Vol. 53 No. 4, S. 434, im Internet.

Der externe Parameter n nummeriert alle rekursiv aufzählbaren Mengen komplett durch, d.h. dieListe aller Dn ist die Liste aller rekursiv aufzählbaren Mengen. Auf diese Liste lässt sich

nun Cantors Diagonalmethodeanwenden: Wir stellen für alle Werte von n die Frage, ob diesesn selbst in der zugehörigen Lösungsmenge Dn auftaucht. Falls nicht, nehmen wir es in eine Menge

V auf, d.h. die Menge V ist definiert als

V := { n aus N , n gehört nicht zu Dn }

Diese Menge V unterscheidet sich von jeder Menge Dn , denn wenn Dn die Zahl n enthält, so

enthält V sie nicht und umgekehrt. Damit ist V nicht in der Liste aller Dn enthalten, ist also auch

keine rekursiv aufzählbare Menge (denn die stehen alle in der Liste drin). Es gibt also keinComputerprogramm, das die Elemente der Menge V auflisten kann. Entsprechend kann keinComputerprogramm für alle natürlichen Zahlen n die Frage beantworten, ob dieses n wirklich

nicht in der zugehörigen Lösungsmenge Dn auftaucht, denn sonst könnte dieses Programm ja dieMenge V auflisten. Da hilft dann auch die Auflistung der Elemente von Dn nichts, denn man kann

die Liste bei unendlich vielen Elementen ja nie komplett durchsuchen.

 Nun war Dn die Lösungsmenge aller x, für die die Gleichung P(x, n, y1, ..., ym) = 0 bei

geeigneten Werten für die Hilfsvariablen y1, ..., ym erfüllt ist. Wenn man nun nicht allgemein

entscheiden kann, ob ein n zu Dn gehört, so kann man auch nicht allgemein entscheiden, ob die

Gleichung P(n, n, y1, ..., ym) = 0 (also mit x = n ) für geeignete Werte der Hilfsvariablen y1,

..., ym erfüllt ist, d.h. ob es Lösungen für y1, ..., ym gibt. Damit gibt es kein allgemeines

Entscheidungsverfahren für die Lösbarkeit diophantischer Gleichungen.Das alles kannten wir schon aus Kapitel 3.5. Wie hängt das nun mit dem Thema des aktuellenKapitels zusammen? Dazu habe ich in Martin Davis: The Incompleteness Theorem, Notices of theAMS, Vol 53, No. 4, S.414 (im Internet) das Folgende gefunden:

 Nach unserem Ergebnis muss es für jedes Entscheidungsverfahren mindestens ein n0 geben, das

nicht zu Dn0 gehört und bei dem wir das mit dem Entscheidungsverfahren nicht nachweisen

können. Entsprechend können wir auch nicht nachweisen, dass die zugehörige diophantischeGleichung P(n0, n0, y1, ..., ym) = 0 für dieses n0  keine Lösungen in y1, ..., ym hat. Die

Aussage

• FÜR_ALLE y1, ..., ym : NICHT P(n0, n0, y1, ..., ym) = 0

ist für das gegebene Entscheidungsverfahren für dieses n0 nicht entscheidbar. Das sieht genauso auswie unsere Aussage A von ganz oben, nur mit mehreren Variablen statt nur mit einer, was aber keine große Rolle spielt. Insofern gilt alles, was wir oben über A bzw. A' gesagt haben, auch hier,d.h. die Aussage ist unentscheidbar und deswegen für natürliche Zahlen wahr.

Welche Werte für n0 in Frage kommen, hängt von dem Entscheidungsverfahren ab, das wir 

anwenden. Egal welches Verfahren wir anwenden, es gibt immer mindestens ein n0 , das diesem

Verfahren entschlüpft, so dass der obige Satz unentscheidbar ist.

Eine Möglichkeit für Entscheidungsverfahren sind Beweise in der Peano-Arithmetik (siehedas Representation Theorem in Kapitel 2.4 ). Eine andere mächtigere Möglichkeit sind Beweise inder ZFC-Mengenlehre. Da die ZFC-Mengenlehre sehr viel mächtiger als die Peano-Arithmetik ist,wird es Aussagen geben, die für die Peano-Arithmetik unentscheidbar sind, die aber in der ZFC-

5/13/2018 Diagonalsierung-Gödel-Stegmüller-ChristensenEDS - slidepdf.com

http://slidepdf.com/reader/full/diagonalsierung-goedel-stegmueller-christenseneds 48/49

 

Mengenlehre entschieden werden können. Daher gilt (siehe Martin Davis: The IncompletenessTheorem, Notices of the AMS, Vol 53, No. 4, S.414 (im Internet) ):

•Es gibt eine natürliche Zahl n0 , so dass die obige Aussage

FÜR_ALLE y1, ..., ym : NICHT P(n0, n0, y1, ..., ym) = 0

in der Peano-Arithmetik unentscheidbar ist, aber in der ZFC-Mengenlehre bewiesen werden

kann.Bei manchen diophantischen Gleichungen kann also erst die ZFC-Mengenlehre beweisen, dass siekeine Lösungen haben, während die Peano-Arithmetik dafür zu schwach ist. Erst die ZFC-Mengenlehre wird dann auch ein entsprechendes n0 ermitteln können, denn die Peano-Arithmetik 

wird die Unentscheidbarkeit für dieses n0 nicht sehen können.

Aber auch für die ZFC-Mengenlehre muss es mindestens ein n0 geben, so dass die obige Aussage

unentscheidbar ist, wobei die ZFC-Mengenlehre ein solches n0 nicht ermitteln kann (die Werte

für n0 dürften ziemlich große natürliche Zahlen sein, denn n0 kodiert gewissermaßen die

Beweiskraft des formalen Systems -- entsprechend komplex sind dann die diophantischenGleichungen). Es gibt also arithmetische Aussagen (also Aussagen über natürliche Zahlen), die inZFC unentscheidbar sind. Allerdings wäre beispielsweise eine entsprechende diophantischeGleichung sehr kompliziert und sie wäre über das Diagonalverfahren oben auch extra so konstruiert,dass sie in ZFC unentscheidbar ist (wobei man in einer geeigneten ZFC-Erweiterung noch das

  passende n0 ermitteln muss). Dagegen haben wir oben bereits gesagt, dass ZFC

 bezüglich natürlicher arithmetischer Aussagen vollständig zu sein scheint. In diesem Sinne wäre diespeziell konstruierte diophantische Gleichung als unnatürlich anzusehen -- eben eineSpezialkonstruktion.

Unentscheidbarkeit und Wahrheit in der ZFC-Mengenlehre:

Halten wir noch einmal fest: Wenn eine Aussage der Form A': NICHT ES_GIBT x in N : P(x)wie beispielsweise die Goldbachsche Vermutung in der ZFC-Mengenlehre unentscheidbar ist, so istsie bösartig unentscheidbar, d.h. wir können diese Unentscheidbarkeit in ZFC nicht beweisen.Wie passt das mit ähnlichen Aussagen zusammen, von denen wir wissen, dass sie in ZFCunentscheidbar sind (Beispiel: Kontinuumshypothese)? Was unterscheidet dieKontinuumshypothese von der Goldbachschen Vermutung? Auch die Kontinuumshypothese ist javon der Form

K: NICHT ES_GIBT x : Q(x)

Dabei ist allerdings x nicht aus N, sondern irgendeine Menge, und Q(x) sagt, dass die Mächtigkeitdieser Menge zwischen den natürlichen und den reellen Zahlen liegt. Die Menge x ist alsoüberabzählbar, aber bei jeder Bijektion von x in die reellen Zahlen bleiben immer reelle Zahlenübrig (siehe Kapitel 4.3 und Kapitel 5.6 ). Die Kontinuumshypothese sagt, dass es eine solcheMenge zwischen den natürlichen und den reellen Zahlen nicht gibt.

Im Internet habe ich dazu den folgenden sehr interessanten Text gefunden: Jan Thor: Mersenne.pdf .An diesem Text orientiere ich mich im Folgenden.

In der Zahlentheorie hatten wir die Voraussetzung gemacht, dass die Eigenschaft P(x) in endlichvielen Schritten entscheidbar sein muss. So kann man bei jeder natürlichen Zahl per Computer immer nachprüfen, ob sie sich als Summe zweier Primzahlen schreiben lässt -- man muss nur alle

kleineren Primzahlen durchprobieren. Bei der Eigenschaft Q(x) der Kontinuumshypothese ist dassehr viel weniger durchsichtig. Es hängt davon ab, wie konkret die Menge x ist. Man kann aber 

5/13/2018 Diagonalsierung-Gödel-Stegmüller-ChristensenEDS - slidepdf.com

http://slidepdf.com/reader/full/diagonalsierung-goedel-stegmueller-christenseneds 49/49

 

nicht davon ausgehen, dass man für  jede denkbare Menge x mechanisch nachprüfen kann, ob ihreMächtigkeit zwischen den natürlichen und den reellen Zahlen liegt.

 Nehmen wir analog zur Zahlentheorie an, es gäbe eine Menge x, die die Eigenschaft Q(x) aufweist.Das wäre dann ein Gegenbeispiel zur Kontinuumshypothese. Anders als in der Zahlentheorie istaber unklar, ob ZFC das erkennt, d.h. ob ZFC für diese Menge x auch den Ausdruck Q(x) ableitenkann. Die Eigenschaft Q(x) ist eben nicht allgemein entscheidbar.

Man kann die denkbaren Mengen allerdings einschränken, beispielsweise indem man Gödel-

Konstruierbarkeit fodert. Damit werden die Mengen so konkret, dass Q(x) entscheidbar wird.Wenn man jetzt eine konstruierbare Menge x fände, die die Eigenschaft Q(x) aufweist (alsozwischen den natürlichen und reellen Zahlen liegt), dann kann ZFC auch die Aussage NICHT K:ES_GIBT x : Q(x) ableiten, d.h. die Kontinuumshypothese wäre durch Gegenbeispiel widerlegt.

 Nun weiß man aber, dass die Kontinuumshypothese unentscheidbar in ZFC ist. Daher kann es auchkein konstruierbares Gegenbeispiel geben, denn sonst wäre die Kontinuumshypothese widerlegtund damit entscheidbar. Ein mögliches Gegenbeispiel muss also so wenig greifbar sein, dass ZFCdas Gegenbeispiel nicht konkretisieren kann. ZFC kann für kein konkretes x die Eigenschaft Q(x)nachweisen, denn sonst hätte ZFC die Kontinuumshypothese widerlegt und damit entschieden.

Daher ist klar, dass es unter den konkreten Mengen kein Gegenbeispiel zur Kontinuumshypothesegeben kann. Immer dann, wenn man sich auf konkrete Mengen beschränkt, so gilt dieKontinuumshypothese für diese Mengen, d.h. sie wird wahr und damit für diese Mengenentscheidbar. Trotzdem scheint es sinnvoll zu sein, die Kontinuumshypothese besser als falschanzusehen, da man sich dadurch mehr Denkfreiheit offen lässt. Man lässt also im PrinzipGegenbeispiele zur Kontinuumshypothese zu, wobei man weiß, dass man nicht mit dem Finger auf sie zeigen kann. Mögliche Gegenbeispiele bleiben immer sehr abstrakt -- mehr dazu siehe Kapitel5.6.

Literatur:

•Jan Thor: Mersenne.pdf 

•K.Podnieks: Incompleteness Theorems. Related Results

•Martin Davis: The Incompleteness Theorem, Notices of the AMS, Vol 53, No. 4, S.414 (imInternet)

•Solomon Fefermann: The Impact of the Incompleteness Theorems on Mathematics, Noticesof the AMS Vol. 53 No. 4, S. 434, im Internet

•Bjorn Poonen: Undecidability in number theory, im Internet