Studium, Ausbildung und Beruf

web uni-protokolle.de
 powered by
NachrichtenLexikonProtokolleBücherForenMittwoch, 26. Februar 2020 

Gödelscher Unvollständigkeitssatz


Dieser Artikel von Wikipedia ist u.U. veraltet. Die neue Version gibt es hier.
Der Gödelsche Unvollständigkeitssatz beschäftigt sich mit der Beweisbarkeit von in formalen Theorien . Aussagen für die man einen Beweis gelten als wahr. Unter Umständen kann man nachweisen dass ein Beweis existiert ohne diesen zu kennen. Solche Aussagen bezeichnet man als Aussagen deren Gegenteil beweisbar ist heißen widerlegbar. Mathematiker Kurt Gödel wies im Jahre 1930 nach dass man in Systemen wie Arithmetik nicht alle Aussagen beweisen oder widerlegen Sein Satz besagt:

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

Gödels Argumentation läuft auf eine Abzählung Sätze innerhalb des formalen Systems hinaus jeder erhält eine eigene Nummer. Er konstruiert dann Aussage der Form: " Der Satz mit der Nummer x ist beweisbar " und setzt für x die Nummer dieser Aussage ein. Insgesamt er einen Satz der Form " Ich bin nicht beweisbar ". Es gibt nun zwei Möglichkeiten: Entweder " Satz x " ist wahr dann ist er nicht (was ja der Inhalt des Satzes ist). er ist falsch dann muss ja das gelten also muss der Satz beweisbar und wahr sein. Das ist ein Widerspruch also dieser Satz nur falsch sein wenn das System widersprüchlich ist.

Damit dieser Ansatz funktioniert muss das formale System also mindestens Zählungen erlauben. Für Systeme gilt der Unvollständigkeitssatz daher nicht. Die von Zählungen ist aber die einzige wesentliche einer formalen Theorie für die der Satz Dies ist für relativ viele mathematische Theorien

Normalerweise könnte man sich dadurch behelfen man für alle Sätze die weder bewiesen widerlegt werden können einfach definiert ob sie wahr oder falsch gelten und die Definition formalen System hinzufügt. Im neuen erweiterten System dann für diese Sätze ein Beweis nämlich die hinzugefügte Definition. Gödel zeigte jedoch dass unmöglich ist da stets unbeweisbare Sätze übrigbleiben. das erweiterte System bleibt unvollständig.

Inhaltsverzeichnis

Beispiel an einem Verschlüsselungsverfahren

Jemand hat sich folgendes Verschlüsselungsverfahren ausgedacht. und verschlüsselter Text enthalten beide nur die Buchstabe A-Z des Alphabets denen fortlaufend der von 1-26 zugeordnet ist. A kann anfangs Wert von 1-26 haben es muß nur den Partnern festgelegt sein. Wenn einem Buchstaben Buchstabe mit geringerem Wert folgt dann rotieren Buchstaben um eine Position weiter (Beispiel: ti tj)

 Beispiel: tomate -> tpodwi  

Das Problem: Wenn zwei gleiche Buchstaben Ein Buchstabe und sein Vorgängerbuchstabe aufeinander folgen erzeugen sie die gleiche Buchstabenfolge (Beispiel: mm mm und ml -> mm)

 Beispiel: hammer -> hbnngt und gonaden goocfgp  

In beiden Beispielen ist eine Doppelbuchstaben-Folge Die Frage die sich beim rückentschlüsseln stellt entstand die Doppelbuchstaben-Folge durch Verschiebung oder war schon vorher da? Man kann das Problem versuchen zu umgehen indem man ein 27. einführt das eine Doppelfolge von der Verschiebung (Beispiel: mm -> m@ und ml -> )

 Beispiel: hammer -> hbn@gt und gonaden goocfgp  

Das Entschlüsseln sollte vordergründig kein problem machen. Aber wenn man das @ als Zeichen einführt müßte es als 27. Zeichen werden. Es müßte damit auch rotieren.

 Beispiel: umzug -> un@wj  

Ausserdem kommt es möglicherweise auch als Zeichen vor: auto@mobil. Dann hätte man wieder gleche Problem: Steht das @ als @? steht das @ als Wiederholungszeichen. Durch beliebiges ist das Problem nicht zu lösen.

Hilberts Programm

Gödel versetzte mit seinem Unvollständigkeitssatz einem von David Hilbert zur vollständigen Begründung und Formalisierung der einen schweren Schlag. Dieser Ansatz ist als Programm bekannt geworden und wurde von ihm Jahre 1921 veröffentlicht. Hilbert schlug vor die Widerspruchsfreiheit komplexeren Systemen durch einfachere Systeme nachzuweisen. Eine formalisierte Prädikatenlogik erster Stufe war eines von Hilberts Am Ende seines Programms sollte die gesamte auf die einfache Arithmetik zurückgeführt und auf axiomatisches System gestellt werden aus dem alle Sätze streng ableitbar sind.

Gödels Arbeit war durch Hilberts Programm Er verwendete die von Hilbert vorgeschlagenen Methoden seinen Unvollständigkeitssatz zu zeigen. Gödel bewies auch folgenden Satz

Ein System kann nicht zum Beweis seiner Widerspruchsfreiheit verwendet werden.

Gödel hatte damit gewissermaßen Hilbert mit eigenen Methoden geschlagen.

Ein anderer Ansatz der unüberbrückbare Lücken Hilberts Programm nachweist stammt von dem Mathematiker Turing. Er erfand die Turingmaschine und formulierte deren Halteproblem .

Genauere Formulierung

Der Gödelsche Satz besagt genauer dass Beweissystem für die Menge der wahren arithmetischen Formeln unvollständig ist man voraussetzt dass die Arithmetik widerspruchsfrei ist - was wie Gödel auch zeigt nicht mit Mitteln der Theorie alleine bewiesen werden kann). Das heißt:

In jeder formalen Theorie welche mindestens so mächtig wie die der natürlichen Zahlen ( Peano-Arithmetik ) ist bleiben wahre (und falsche) arithmetische übrig die nicht innerhalb der Theorie beweisbar sind.

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

  • Zu jeder durch einen Ausdruck G(x) Menge ist das Komplement beschreibbar.
  • Zu jeder durch einen Ausdruck G(x) Menge M ist die Menge M*={n|d(x)∈M} beschreibbar; ist d(x) die Diagonalisierung von x.
  • Die Menge der beweisbaren Ausdrücke der ist durch einen Ausdruck der Form G(x)

Nach dem Satz von Löwenheim-Skolem findet zu jeder Theorie in PL1 ein Modell mit der Mächtigkeit der Signatur . Für "normale" Theorien existiert also ein Modell z.B. die natürlichen Zahlen . Die Idee von Gödel war Formeln Theorie selbst zum Objekt derselben zu machen. wurden die Formeln gödelisiert d.h. eine (umkehrbar eindeutige) Abbildung Formeln auf natürliche Zahlen gebildet. Das kann z.B. dadurch erreichen dass jedem Symbol der eine Zahl zugeordnet wird die dann verkettet Ordnet man der 0 die 1 und = die 2 zu so ist die Gödelnummer der (in dem Spezialfall) 0=0 die 121 . Die Verkettungsoperation ist einfach durch Exponentieren zu realisieren. Es lassen sich auch syntaktisch wohlgeformten und schließlich die beweisbaren Formeln arithmetische Ausdrücke ( Addition Multiplikation Exponentiation ) beschreiben.

Die Diagonalisierung in Gödels Beweis ist nun eine Anwendung eines Ausdrucks auf die eigene Gödelnummer. Ist die Gödelnummer Ausdrucks (und damit der Zeichenreihe) P(x) zum 12345 so ist die Diagonalisierung der Zahl 12345 die Gödelnummer von P(12345) (selbstverständlich hat eine Zahl hier 12345 auch eine Gödelnummer die entsteht indem alle vorkommenden Ziffern gödelisiert).

"Besagt" der Ausdruck B(x) also dass x beweisbar ist und ist zum Beispiel 12345 die Gödelnummer von B(x) so ist ¬B(12345) eine unbeweisbare Aussage . Diese Aussage besagt dann nämlich: Die mit der Gödelnummer 12345 ist nicht beweisbar. 12345 ist aber die Gödelnummer von B(x). sagt ¬B(12345): Ich bin nicht beweisbar. Wenn korrekt ist so ist dieser Satz wahr nicht beweisbar.

Gödels ursprünglicher Beweis ging noch weiter. wollte Rückgriffe auf die Semantik insbesondere die Korrektheit vermeiden. Deswegen bewies seinen Unvollständigkeitssatz unter der Voraussetzung der ω- Konsistenz : Eine Theorie ist ω-inkonsistent wenn ein mit einer einzigen freien Variable x existiert den <math>\exists x P(x)</math> beweisbar ist zugleich für alle <math>n<\omega</math> <math>\neg P(n)</math> beweisbar ist.

Rosser erweiterte das Gödelsche Resultat indem einen Unvollständigkeitsbeweis lieferte für den nicht die der Ausdrücke deren Diagonalisierung beweisbar ist beschrieben sondern eine zu dieser Menge disjunkte Obermenge Ausdrücke deren Diagonalisierung widerlegbar ist. Dadurch ist der Bezug auf die ω-Konsistenz überflüssig.

Durch diesen erstaunlichen Satz ist der Mathematik eine prinzipielle Grenze gesetzt: Nicht jeder mathematische Satz kann aus den wie auch gewählten Axiomen eines mathematischen Teilgebietes (z. B. Geometrie Algebra etc.) formal abgeleitet werden.

Literatur

  • Kurt Gödel Über formal unentscheidbare Sätze der Principia Mathematica verwandter Systeme I Monatsheft für Math. und Physik 38 S.173-198.
  • Kurt Gödel Diskussion zur Grundlegung der Mathematik Erkenntnis 2 Monatsheft für Math. und Physik 1931-32
  • Ernest Nagel James R. Newmann Der Gödelsche Beweis Scientia Nova Oldenburg ( ISBN 3-486-45214-2 )
  • Douglas R. Hofstadter Gödel Escher Bach ein Endloses Geflochtenes Band Dt. Taschenbuch Verlag München 1991 ( ISBN 3-423-30017-5 )
  • Max Woitschach Gödel Götzen und Computer; Eine Kritik der Vernunft. Poller Stuttgart 1986 ( ISBN 3-87959-294-2 )
  • Wolfgang Stegmüller Unvollständigkeit und Unentscheidbarkeit; Die mathematischen Resultate von Church Kleene Rosser und ihre erkenntnistheoretische Bedeutung. Springer-Verlag Wien 1973 ( ISBN 3-211-81208-3 Springer Wien-New York; ISBN 0-387-81208-3 Springer New York-Wien; Library of Congress Card Number 73-14357)
  • Sybille Krämer Symbolische Maschinen; d. Idee d. Formalisierung in Abriß Wissenschaftliche Buchgesellschaft Darmstadt 1988 ( ISBN 3-534-03207-1 )
  • Ludwig Fischer Die Grundlagen der Philosophie und der Mathematik Felix Meiner Verlag Leipzig 1933.
  • Norbert Domeisen Logik der Antinomien. Bern Peter Lang. 142 S. 1990. ( ISBN 3-261-04214-1 ) Zentralblatt MATH

Siehe auch: Formales System (Logik)



Bücher zum Thema Gödelscher Unvollständigkeitssatz

Dieser Artikel von Wikipedia unterliegt der GNU FDL.

ImpressumLesezeichen setzenSeite versendenSeite drucken

HTML-Code zum Verweis auf diese Seite:
<a href="http://www.uni-protokolle.de/Lexikon/G%F6delscher_Unvollst%E4ndigkeitssatz.html">Gödelscher Unvollständigkeitssatz </a>