Lindenbaum's lemma
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
It is used in the proof of Gödel's completeness theorem, among other places.{{cn|reason=Is it used in Gödel's own proof or just Henkin's?|date=February 2021}}
Extensions
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
The lemma was not published by Adolf Lindenbaum; it is originally attributed to him by Alfred Tarski.Tarski, A. On Fundamental Concepts of Metamathematics, 1930.
Notes
References
- {{cite book | last1=Crossley | first1=J.N. | last2=Ash | first2=C.J. | last3=Brickhill | first3=C.J. | last4=Stillwell | first4=J.C. | last5=Williams | first5=N.H. | title=What is mathematical logic? | zbl=0251.02001 | location=London-Oxford-New York | publisher=Oxford University Press | year=1972 | isbn=0-19-888087-1 | page=16 }}
{{logic-stub}}