Jump to content

Lindenbaum's lemma

From Wikipedia, the free encyclopedia

In mathematical logic, Lindenbaum's lemma, named after Adolf Lindenbaum, states that any consistent theory of predicate logic can be extended to a complete consistent theory. The lemma is a special case of the ultrafilter lemma for Boolean algebras, applied to the Lindenbaum algebra of a theory.

Uses

[edit]

It is used in the proof of Gödel's completeness theorem, among other places.[citation needed]

Extensions

[edit]

The effective version of the lemma's statement, "every consistent computably enumerable theory can be extended to a complete consistent computably enumerable theory," fails (provided Peano arithmetic is consistent) by Gödel's incompleteness theorem.

History

[edit]

The lemma was not published by Adolf Lindenbaum; it is originally attributed to him by Alfred Tarski.[1]

Notes

[edit]
  1. ^ Tarski, A. On Fundamental Concepts of Metamathematics, 1930.

References

[edit]
  • Crossley, J.N.; Ash, C.J.; Brickhill, C.J.; Stillwell, J.C.; Williams, N.H. (1972). What is mathematical logic?. London-Oxford-New York: Oxford University Press. p. 16. ISBN 0-19-888087-1. Zbl 0251.02001.