Theorem of Lindenbaum

The set of lime (also Lemma Lindenbaum , by Adolf Lindenbaum ) is a result of the mathematical logic. It says that any consistent set of formulas in first-order predicate logic can be expanded to a consistent and complete theory . Such a theory is also called maximally consistent , since all of its real supersets are inconsistent. The theorem plays an important role in proving Gödel's completeness theorem .

Proof idea

The proof for arbitrary sets can be done with the axiom of choice or an equivalent statement like Zorn's lemma : If an ascending chain (with respect to set inclusion) is of consistent formula sets, then is also consistent. According to Zorn's lemma, there is thus a maximally consistent theory. ${\displaystyle \{\Gamma _{i}|i\in I\}}$ ${\displaystyle \bigcup _{i\in I}\Gamma _{i}}$

Certain generalizations of the theorem are even equivalent to the axiom of choice. For consistent sets of formulas across countable languages, the sentence can also be shown without the axiom of choice. For sufficiently strong recursively enumerable consistent formula sets there is no recursively enumerable complete extension according to Gödel's incompleteness theorem , but every recursively enumerable consistent formula set has a complete extension in the class of the arithmetic hierarchy . ${\displaystyle \Delta _{2}}$

literature

• Hans Dieter Ebbinghaus, Jörg Flum, Wolfgang Thomas: Introduction to mathematical logic . Spektrum Akademischer Verlag, Heidelberg 2007, ISBN 3-8274-1691-4 .
• Wolfgang Rautenberg : Introduction to Mathematical Logic . 3. Edition. Vieweg + Teubner, Wiesbaden 2008, ISBN 978-3-8348-0578-2 .

Individual evidence

1. ↑ Wolfgang Rautenberg : Introduction to Mathematical Logic . 3. Edition. Vieweg + Teubner, Wiesbaden 2008, ISBN 978-3-8348-0578-2 , pp. 22 .
2. ^ W. Dzik: The Existence of Lindenbaum's Extensions is Equivalent to the Axiom of Choice . In: Reports on Mathematical Logic . tape 12 , 1981, p. 29-31 . DW Miller: Some Restricted Lindenbaum Theorems Equivalent to the Axiom of Choice . In: Logica Universalis . tape 1 , no. 1 , 2007, ISSN  1661-8297 , p. 183-199 ( warwick.ac.uk [PDF]).