Lindenbaum's lemma
Encyclopedia
In mathematical logic
, Lindenbaum's lemma states that any consistent theory of predicate logic
can be extended to a complete
consistent theory. It is used in the proof of Gödel's completeness theorem
, among other places. The lemma is a special case of the ultrafilter lemma for Boolean algebras, applied to the Lindenbaum algebra of a theory.
The effective version of the lemma's statement, "every consistent computably enumerable theory can be extended to a complete consistent computably enumerable theory," fails by Gödel's incompleteness theorem.
The lemma was not published by Adolf Lindenbaum
; it is originally attributed to him by Alfred Tarski
.
Mathematical logic
Mathematical logic is a subfield of mathematics with close connections to foundations of mathematics, theoretical computer science and philosophical logic. The field includes both the mathematical study of logic and the applications of formal logic to other areas of mathematics...
, Lindenbaum's lemma states that any consistent theory of predicate logic
Predicate logic
In mathematical logic, predicate logic is the generic term for symbolic formal systems like first-order logic, second-order logic, many-sorted logic or infinitary logic. This formal system is distinguished from other systems in that its formulae contain variables which can be quantified...
can be extended to a complete
Complete theory
In mathematical logic, a theory is complete if it is a maximal consistent set of sentences, i.e., if it is consistent, and none of its proper extensions is consistent...
consistent theory. It is used in the proof of Gödel's completeness theorem
Gödel's completeness theorem
Gödel's completeness theorem is a fundamental theorem in mathematical logic that establishes a correspondence between semantic truth and syntactic provability in first-order logic. It was first proved by Kurt Gödel in 1929....
, among other places. The lemma is a special case of the ultrafilter lemma for Boolean algebras, applied to the Lindenbaum algebra of a theory.
The effective version of the lemma's statement, "every consistent computably enumerable theory can be extended to a complete consistent computably enumerable theory," fails by Gödel's incompleteness theorem.
The lemma was not published by Adolf Lindenbaum
Adolf Lindenbaum
Adolf Lindenbaum , was a Polish logician and mathematician.He was a student of Wacław Sierpiński, became a distinguished author of works on set theory and had served as an Assistant Professor at Warsaw University...
; it is originally attributed to him by Alfred Tarski
Alfred Tarski
Alfred Tarski was a Polish logician and mathematician. Educated at the University of Warsaw and a member of the Lwow-Warsaw School of Logic and the Warsaw School of Mathematics and philosophy, he emigrated to the USA in 1939, and taught and carried out research in mathematics at the University of...
.