Satz von Lindenbaum

Der Satz von Lindenbaum (auch Lemma von Lindenbaum, nach Adolf Lindenbaum) ist ein Ergebnis der mathematischen Logik. Er besagt, dass jede konsistente Formelmenge der Prädikatenlogik erster Stufe zu einer konsistenten und vollständigen Theorie erweitert werden kann. Eine solche Theorie wird auch als maximalkonsistent bezeichnet, da alle ihre echten Obermengen inkonsistent sind. Der Satz spielt eine wichtige Rolle beim Beweis des Gödelschen Vollständigkeitssatzes.

Beweisidee

Der Beweis für beliebige Mengen kann mit dem Auswahlaxiom oder einer äquivalenten Aussage wie dem Zornschen Lemma geführt werden: Wenn $\{\Gamma _{i}|i\in I\}$ eine (bezüglich Mengeninklusion) aufsteigende Kette von konsistenten Formelmengen ist, dann ist auch ${\textstyle \bigcup _{i\in I}\Gamma _{i}}$ konsistent. Nach dem Zornschen Lemma gibt es damit eine maximale konsistente Theorie.[1]

Gewisse Generalisierungen des Satzes sind sogar äquivalent zum Auswahlaxiom.[2] Für konsistente Formelmengen über abzählbaren Sprachen lässt sich der Satz auch ohne Auswahlaxiom zeigen. Für ausreichend starke rekursiv aufzählbare konsistente Formelmengen gibt es zwar nach dem Gödelschen Unvollständigkeitssatz keine rekursiv aufzählbare vollständige Erweiterung, aber jede rekursiv aufzählbare konsistente Formelmenge hat eine vollständige Erweiterung in der $\Delta _{2}$ -Klasse der arithmetischen Hierarchie.

Literatur

Hans Dieter Ebbinghaus, Jörg Flum, Wolfgang Thomas: Einführung in die mathematische Logik. Spektrum Akademischer Verlag, Heidelberg 2007, ISBN 3-8274-1691-4.
Wolfgang Rautenberg: Einführung in die Mathematische Logik. 3. Auflage. Vieweg+Teubner, Wiesbaden 2008, ISBN 978-3-8348-0578-2.

Einzelnachweise

Wolfgang Rautenberg: Einführung in die Mathematische Logik. 3. Auflage. Vieweg+Teubner, Wiesbaden 2008, ISBN 978-3-8348-0578-2, S. 22.
W. Dzik: The Existence of Lindenbaum’s Extensions is Equivalent to the Axiom of Choice. In: Reports on Mathematical Logic. Band 12, 1981, S. 29–31. D.W. Miller: Some Restricted Lindenbaum Theorems Equivalent to the Axiom of Choice. In: Logica Universalis. Band 1, Nr. 1, 2007, ISSN 1661-8297, S. 183–199 (warwick.ac.uk [PDF]).

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.

[1] Wolfgang Rautenberg: Einführung in die Mathematische Logik. 3. Auflage. Vieweg+Teubner, Wiesbaden 2008, ISBN 978-3-8348-0578-2, S. 22.

[2] W. Dzik: The Existence of Lindenbaum’s Extensions is Equivalent to the Axiom of Choice. In: Reports on Mathematical Logic. Band 12, 1981, S. 29–31. D.W. Miller: Some Restricted Lindenbaum Theorems Equivalent to the Axiom of Choice. In: Logica Universalis. Band 1, Nr. 1, 2007, ISSN 1661-8297, S. 183–199 (warwick.ac.uk [PDF]).