Lindenbaum's lemma

The set of Lindenbaum (also Lemma Lindenbaum, after Adolf Lindenbaum ) is a result of mathematical logic. He states that every consistent set of formulas of first-order predicate logic can be extended to a consistent and complete theory. Such a theory, it is also referred to as a maximum consistent since all their real supersets are inconsistent. The set plays an important role in the proof of Gödel's completeness theorem.

Idea of ​​proof

The proof of any amount can be made ​​with the axiom of choice or an equivalent statement like Zorn's Lemma: If a (with respect to set inclusion ) is ascending chain of consistent sets of formulas, then also consistent. After Zorn's Lemma, there is thus a maximum consistent theory.

Certain generalizations of the theorem are even equivalent to the axiom of choice. For consistent sets of formulas over countable languages ​​can also show without the axiom of choice set. For sufficiently strong recursively enumerable sets of formulas consistent although there after Gödel's incompleteness theorem recursively enumerable no full extension, but every recursively enumerable consistent set of formulas has a full extension in the class of the arithmetic hierarchy.