Satz von Lindenbaum

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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[Bearbeiten]

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 \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[Bearbeiten]

Einzelnachweise[Bearbeiten]

  1. Rautenberg (2008), S. 22.
  2.  W. Dzik: The Existence of Lindenbaum’s Extensions is Equivalent to the Axiom of Choice. In: Reports on Mathematical Logic. 12, 1981, S. 29-31.;  D.W. Miller: Some Restricted Lindenbaum Theorems Equivalent to the Axiom of Choice. In: Logica Universalis. 1, Nr. 1, 2007, ISSN 1661-8297, S. 183--199 (http://www2.warwick.ac.uk/fac/soc/philosophy/people/associates/miller/lindenbaum.pdf).