www.wikidata.de-de.nina.az

Gödelscher Vollständigkeitssatz Der Gödelsche Vollständigkeitssatz benannt nach Kurt Gödel ist der Hauptsatz der mathema

Gödelscher Vollständigkeitssatz

Der Gödelsche Vollständigkeitssatz (benannt nach Kurt Gödel) ist der Hauptsatz der mathematischen Logik. Er zeigt für den Hilbert-Kalkül (ein formales System der Prädikatenlogik erster Stufe) die Korrektheit und Vollständigkeit: Jeder Satz, der semantisch aus einer Formelmenge folgt, lässt sich mit den Schlussregeln des Systems aus der Formelmenge herleiten, und umgekehrt. Für die Logik erster Stufe sind also syntaktische und semantische Folgerung gleichbedeutend.

Grundbegriffe Bearbeiten

Formeln: Zunächst muss eine Menge von Konstanten-, Funktions- und Relationssymbolen festgelegt werden. Neben diesen Symbolen stehen dann aussagenlogische Junktoren, die Quantoren, das Gleichheitszeichen sowie Variablen zum Formelaufbau zur Verfügung.

Semantik: Eine Struktur ist eine nichtleere Menge, in der die Konstanten-, Funktions- und Relationssymbole durch Elemente, Funktionen und Relationen interpretiert werden. Zu einer Interpretation gehört außerdem eine Belegung der Variablen mit Werten aus der Struktur. Eine Formel ist allgemeingültig, wenn sie in jeder Interpretation wahr ist. Eine Interpretation, die jede Formel aus einer Formelmenge wahr macht, nennt man ein Modell von . Eine Formel ist eine semantische Folgerung aus (in Zeichen ), wenn in jedem Modell von wahr ist.

Herleitungen: Ein Hilbert-Kalkül ist durch Axiome und Schlussregeln gegeben. Die wichtigste Schlussregel ist dabei der modus ponens: Von den Formeln und darf man zu übergehen. Eine Formel ist aus einer Formelmenge herleitbar (in Zeichen ), wenn es eine endliche, mit endende Folge von Formeln gibt, wobei für jedes Glied der Folge gilt: Es ist ein Axiom oder ein Element von oder es wird mit einer Schlussregel aus früheren Gliedern der Folge gebildet.

Der Satz Bearbeiten

Kurt Gödel bewies 1929 den Vollständigkeitssatz im Wesentlichen in der folgenden Form:

Verwendet man als Zeichen für die semantische Folgerung und für die Herleitbarkeit im Kalkül, ergibt sich die kurze Formulierung:

Der Schluss von rechts nach links bedeutet die Korrektheit des Kalküls: Alles, was sich mit dem Kalkül aus vorgegebenen Annahmen herleiten lässt, folgt auch wirklich logisch aus diesen Annahmen. Jeder sinnvolle Logikkalkül muss diese Forderung erfüllen.

Der Schluss von links nach rechts ist die eigentliche Vollständigkeit: Es wird behauptet, dass zu jedem Satz, der aus einer Menge von vorgegebenen Annahmen logisch folgt, tatsächlich ein Beweis aus diesen Annahmen im Kalkül existiert.

Eine abgeschwächte Fassung des Vollständigkeitssatzes wird oft so formuliert:

In Zeichen lautet diese Fassung kurz:

Sie ist ein Spezialfall der obigen Aussage, wobei die Formelmenge leer ist.

Es ist wichtig, sich zu vergegenwärtigen, dass Vollständigkeit eine Eigenschaft eines Kalküls ist. Das Symbol für die Herleitbarkeit ist also eigentlich eine Abkürzung für , wobei den Kalkül bezeichnet. Zum Beweis des Satzes muss ein konkreter Kalkül angegeben werden. Gödel hat dies mit einem Hilbert-Kalkül, bestehend aus Axiomen und Schlussregeln, getan. Ebenfalls vollständig ist zum Beispiel der von Gerhard Gentzen eingeführte Sequenzenkalkül.

Beweisidee Bearbeiten

Gödel bewies den Satz ursprünglich, indem er das Problem auf die Vollständigkeit für eine eingeschränkte Klasse von Formeln reduzierte, für die die Vollständigkeit dann auf die Vollständigkeit der Aussagenlogik zurückgeführt werden kann. Heute wird meist ein von Leon Henkin 1949 veröffentlichter Beweis benutzt. Dazu wird zunächst folgender Satz bewiesen:

Konsistenz ist dabei ein syntaktischer Begriff und bedeutet für eine Formelmenge , dass aus ihr kein Widerspruch im Kalkül hergeleitet werden kann (formal: Es gibt keine Formel mit und ).

Die Existenz des Modells wird bewiesen, indem mithilfe des Satzes von Lindenbaum eine gegebene konsistente Formelmenge zu einer sogenannten maximalkonsistenten Menge erweitert wird, die keine konsistente echte Obermenge hat. Dann wird die Sprache durch sogenannte Henkinkonstanten erweitert und die Formelmenge so erweitert, dass für jede Formel der Form auch (c eine Henkinkonstante) enthalten ist. Dann gibt es nach dem Satz von Henkin eine Terminterpretation, deren Grundmenge aus den Termen der Sprache besteht und die alle Elemente der entstehenden Formelmenge erfüllt, und damit auch die ursprüngliche konsistente Formelmenge .

Dann lässt sich die Vollständigkeit leicht zeigen: Angenommen, es gilt zwar , aber nicht . Der Kalkül hat die Eigenschaft, dass man die Negation einer aus einer konsistenten Formelmenge nicht herleitbaren Formel zu der Formelmenge hinzunehmen kann und die Konsistenz dabei erhalten bleibt. Im vorliegenden Fall ist also konsistent und hat nach dem Satz von Henkin ein Modell. In diesem Modell ist aber nun falsch, im Widerspruch zur Voraussetzung, dass in allen Modellen von wahr ist.

Bedeutung Bearbeiten

Dass sich das inhaltliche logische Folgern durch Ableitungen in einem rekursiven Kalkül vollständig abbilden lässt, ist eine herausragende Eigenschaft der Prädikatenlogik erster Stufe. Diese Vollständigkeit gilt für viele andere Logiken nicht, zum Beispiel nicht für die Prädikatenlogik höherer Stufe.

Der Kompaktheitssatz, ein zentraler Satz der Modelltheorie, ergibt sich als Korollar aus dem Vollständigkeitssatz.

Im Rahmen des Hilbertprogramms (zur Schaffung eines widerspruchsfreien und vollständigen Kalküls für die Mathematik) schien der Satz zunächst ein Schritt zum Ziel zu sein. Das Programm scheiterte allerdings, weil Gödel mit seinem Unvollständigkeitssatz zeigen konnte, dass eine genügend ausdrucksstarke Theorie nicht jeden wahren Satz beweisen kann. (Man beachte, dass sich der Unvollständigkeitssatz auf eine andere Art von Vollständigkeit bezieht als der hier vorgestellte Vollständigkeitssatz.)

Stellung in der Mengenlehre Bearbeiten

Für abzählbare (oder allgemeiner: wohlgeordnete) Mengen von Symbolen lässt sich der Vollständigkeitssatz aus den Axiomen der Zermelo-Fraenkel-Mengenlehre ohne Auswahlaxiom beweisen. Der Beweis für beliebige Symbolmengen lässt sich mit dem Auswahlaxiom führen, der Satz ist allerdings nicht äquivalent zum Auswahlaxiom, sondern (relativ zu den Axiomen der Mengenlehre ohne Auswahlaxiom) u. a. zu:

Literatur Bearbeiten

  • Heinz-Dieter Ebbinghaus, Jörg Flum, Wolfgang Thomas: Einführung in die mathematische Logik. Spektrum Akademischer Verlag, Heidelberg 2007, ISBN 3-8274-1691-4.
  • K Gödel: Über die Vollständigkeit des Logikkalküls. In: Dissertation. University Of Vienna., 1929.
  • K Gödel: Die Vollständigkeit der Axiome des logischen Funktionenkalküls. In: Monatshefte für Mathematik. 37. Jahrgang, Nr. 1, 1930, S. 349–360, doi:10.1007/BF01696781.
  • Leon Henkin: The Completeness of the First-Order Functional Calculus. In: Journal of Symbolic Logic, 14, 1949, S. 159–166
  • Wolfgang Rautenberg: Einführung in die Mathematische Logik. 3. Auflage. Vieweg+Teubner, Wiesbaden 2008, ISBN 978-3-8348-0578-2.
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Der Godelsche Vollstandigkeitssatz benannt nach Kurt Godel ist der Hauptsatz der mathematischen Logik Er zeigt fur den Hilbert Kalkul ein formales System der Pradikatenlogik erster Stufe die Korrektheit und Vollstandigkeit Jeder Satz der semantisch aus einer Formelmenge folgt lasst sich mit den Schlussregeln des Systems aus der Formelmenge herleiten und umgekehrt Fur die Logik erster Stufe sind also syntaktische und semantische Folgerung gleichbedeutend Inhaltsverzeichnis 1 Grundbegriffe 2 Der Satz 3 Beweisidee 4 Bedeutung 5 Stellung in der Mengenlehre 6 LiteraturGrundbegriffe BearbeitenFormeln Zunachst muss eine Menge von Konstanten Funktions und Relationssymbolen festgelegt werden Neben diesen Symbolen stehen dann aussagenlogische Junktoren die Quantoren das Gleichheitszeichen sowie Variablen zum Formelaufbau zur Verfugung Semantik Eine Struktur ist eine nichtleere Menge in der die Konstanten Funktions und Relationssymbole durch Elemente Funktionen und Relationen interpretiert werden Zu einer Interpretation gehort ausserdem eine Belegung der Variablen mit Werten aus der Struktur Eine Formel ist allgemeingultig wenn sie in jeder Interpretation wahr ist Eine Interpretation die jede Formel aus einer Formelmenge G displaystyle Gamma nbsp wahr macht nennt man ein Modell von G displaystyle Gamma nbsp Eine Formel f displaystyle varphi nbsp ist eine semantische Folgerung aus G displaystyle Gamma nbsp in Zeichen G f displaystyle Gamma vDash varphi nbsp wenn f displaystyle varphi nbsp in jedem Modell von G displaystyle Gamma nbsp wahr ist Herleitungen Ein Hilbert Kalkul ist durch Axiome und Schlussregeln gegeben Die wichtigste Schlussregel ist dabei der modus ponens Von den Formeln f displaystyle varphi nbsp und f ps displaystyle varphi rightarrow psi nbsp darf man zu ps displaystyle psi nbsp ubergehen Eine Formel f displaystyle varphi nbsp ist aus einer Formelmenge G displaystyle Gamma nbsp herleitbar in Zeichen G f displaystyle Gamma vdash varphi nbsp wenn es eine endliche mit f displaystyle varphi nbsp endende Folge von Formeln gibt wobei fur jedes Glied der Folge gilt Es ist ein Axiom oder ein Element von G displaystyle Gamma nbsp oder es wird mit einer Schlussregel aus fruheren Gliedern der Folge gebildet Der Satz BearbeitenKurt Godel bewies 1929 den Vollstandigkeitssatz im Wesentlichen in der folgenden Form Es gibt einen Kalkul der Pradikatenlogik erster Stufe derart dass fur jede Formelmenge G displaystyle Gamma nbsp und fur jede Formel f displaystyle varphi nbsp gilt f displaystyle varphi nbsp folgt genau dann aus G displaystyle Gamma nbsp wenn f displaystyle varphi nbsp im Kalkul aus G displaystyle Gamma nbsp hergeleitet werden kann Verwendet man displaystyle vDash nbsp als Zeichen fur die semantische Folgerung und displaystyle vdash nbsp fur die Herleitbarkeit im Kalkul ergibt sich die kurze Formulierung G f G f displaystyle Gamma vDash varphi Longleftrightarrow Gamma vdash varphi nbsp Der Schluss von rechts nach links bedeutet die Korrektheit des Kalkuls Alles was sich mit dem Kalkul aus vorgegebenen Annahmen herleiten lasst folgt auch wirklich logisch aus diesen Annahmen Jeder sinnvolle Logikkalkul muss diese Forderung erfullen Der Schluss von links nach rechts ist die eigentliche Vollstandigkeit Es wird behauptet dass zu jedem Satz der aus einer Menge von vorgegebenen Annahmen logisch folgt tatsachlich ein Beweis aus diesen Annahmen im Kalkul existiert Eine abgeschwachte Fassung des Vollstandigkeitssatzes wird oft so formuliert Es gibt einen Kalkul der Pradikatenlogik erster Stufe derart dass fur jede Formel f displaystyle varphi nbsp gilt f displaystyle varphi nbsp ist genau dann allgemeingultig wenn f displaystyle varphi nbsp im Kalkul bewiesen werden kann In Zeichen lautet diese Fassung kurz f f displaystyle vDash varphi Longleftrightarrow vdash varphi nbsp Sie ist ein Spezialfall der obigen Aussage wobei die Formelmenge G displaystyle Gamma nbsp leer ist Es ist wichtig sich zu vergegenwartigen dass Vollstandigkeit eine Eigenschaft eines Kalkuls ist Das Symbol displaystyle vdash nbsp fur die Herleitbarkeit ist also eigentlich eine Abkurzung fur K displaystyle vdash K nbsp wobei K displaystyle K nbsp den Kalkul bezeichnet Zum Beweis des Satzes muss ein konkreter Kalkul angegeben werden Godel hat dies mit einem Hilbert Kalkul bestehend aus Axiomen und Schlussregeln getan Ebenfalls vollstandig ist zum Beispiel der von Gerhard Gentzen eingefuhrte Sequenzenkalkul Beweisidee BearbeitenGodel bewies den Satz ursprunglich indem er das Problem auf die Vollstandigkeit fur eine eingeschrankte Klasse von Formeln reduzierte fur die die Vollstandigkeit dann auf die Vollstandigkeit der Aussagenlogik zuruckgefuhrt werden kann Heute wird meist ein von Leon Henkin 1949 veroffentlichter Beweis benutzt Dazu wird zunachst folgender Satz bewiesen Jede konsistente Formelmenge hat ein Modell Konsistenz ist dabei ein syntaktischer Begriff und bedeutet fur eine Formelmenge G displaystyle Gamma nbsp dass aus ihr kein Widerspruch im Kalkul hergeleitet werden kann formal Es gibt keine Formel f displaystyle varphi nbsp mit G f displaystyle Gamma vdash varphi nbsp und G f displaystyle Gamma vdash neg varphi nbsp Die Existenz des Modells wird bewiesen indem mithilfe des Satzes von Lindenbaum eine gegebene konsistente Formelmenge G displaystyle Gamma nbsp zu einer sogenannten maximalkonsistenten Menge erweitert wird die keine konsistente echte Obermenge hat Dann wird die Sprache durch sogenannte Henkinkonstanten erweitert und die Formelmenge so erweitert dass fur jede Formel der Form x f x displaystyle exists x varphi x nbsp auch f c displaystyle varphi c nbsp c eine Henkinkonstante enthalten ist Dann gibt es nach dem Satz von Henkin eine Terminterpretation deren Grundmenge aus den Termen der Sprache besteht und die alle Elemente der entstehenden Formelmenge erfullt und damit auch die ursprungliche konsistente Formelmenge G displaystyle Gamma nbsp Dann lasst sich die Vollstandigkeit leicht zeigen Angenommen es gilt zwar G f displaystyle Gamma vDash varphi nbsp aber nicht G f displaystyle Gamma vdash varphi nbsp Der Kalkul hat die Eigenschaft dass man die Negation einer aus einer konsistenten Formelmenge nicht herleitbaren Formel zu der Formelmenge hinzunehmen kann und die Konsistenz dabei erhalten bleibt Im vorliegenden Fall ist also G f displaystyle Gamma cup neg varphi nbsp konsistent und hat nach dem Satz von Henkin ein Modell In diesem Modell ist aber nun f displaystyle varphi nbsp falsch im Widerspruch zur Voraussetzung dass f displaystyle varphi nbsp in allen Modellen von G displaystyle Gamma nbsp wahr ist Bedeutung BearbeitenDass sich das inhaltliche logische Folgern durch Ableitungen in einem rekursiven Kalkul vollstandig abbilden lasst ist eine herausragende Eigenschaft der Pradikatenlogik erster Stufe Diese Vollstandigkeit gilt fur viele andere Logiken nicht zum Beispiel nicht fur die Pradikatenlogik hoherer Stufe Der Kompaktheitssatz ein zentraler Satz der Modelltheorie ergibt sich als Korollar aus dem Vollstandigkeitssatz Im Rahmen des Hilbertprogramms zur Schaffung eines widerspruchsfreien und vollstandigen Kalkuls fur die Mathematik schien der Satz zunachst ein Schritt zum Ziel zu sein Das Programm scheiterte allerdings weil Godel mit seinem Unvollstandigkeitssatz zeigen konnte dass eine genugend ausdrucksstarke Theorie nicht jeden wahren Satz beweisen kann Man beachte dass sich der Unvollstandigkeitssatz auf eine andere Art von Vollstandigkeit bezieht als der hier vorgestellte Vollstandigkeitssatz Stellung in der Mengenlehre BearbeitenFur abzahlbare oder allgemeiner wohlgeordnete Mengen von Symbolen lasst sich der Vollstandigkeitssatz aus den Axiomen der Zermelo Fraenkel Mengenlehre ohne Auswahlaxiom beweisen Der Beweis fur beliebige Symbolmengen lasst sich mit dem Auswahlaxiom fuhren der Satz ist allerdings nicht aquivalent zum Auswahlaxiom sondern relativ zu den Axiomen der Mengenlehre ohne Auswahlaxiom u a zu Ultrafilterlemma Kompaktheitssatz Satz von Lindenbaum Darstellungssatz fur Boolesche AlgebrenLiteratur BearbeitenHeinz Dieter Ebbinghaus Jorg Flum Wolfgang Thomas Einfuhrung in die mathematische Logik Spektrum Akademischer Verlag Heidelberg 2007 ISBN 3 8274 1691 4 K Godel Uber die Vollstandigkeit des Logikkalkuls In Dissertation University Of Vienna 1929 K Godel Die Vollstandigkeit der Axiome des logischen Funktionenkalkuls In Monatshefte fur Mathematik 37 Jahrgang Nr 1 1930 S 349 360 doi 10 1007 BF01696781 Leon Henkin The Completeness of the First Order Functional Calculus In Journal of Symbolic Logic 14 1949 S 159 166 Wolfgang Rautenberg Einfuhrung in die Mathematische Logik 3 Auflage Vieweg Teubner Wiesbaden 2008 ISBN 978 3 8348 0578 2 Abgerufen von https de wikipedia org w index php title Godelscher Vollstandigkeitssatz amp oldid 238904551