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
It is used in the proof of Gödel's completeness theorem, among other places.[citation needed]
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.[1]
Notes
References
Wikiwand - on
Seamless Wikipedia browsing. On steroids.