mathematical logic Mathematical logic is the study of formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical properties of formal ...

, Lindenbaum's lemma, named after

Adolf Lindenbaum Adolf Lindenbaum (12 June 1904 – August 1941) was a Polish-Jewish logician and mathematician best known for Lindenbaum's lemma and Lindenbaum–Tarski algebras. He was born and brought up in Warsaw. He earned a Ph.D. in 1928 under Wac ...

, states that any consistent theory of

predicate logic First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantifie ...

can be extended to a complete consistent theory. The lemma is a special case of the

ultrafilter lemma In the mathematical field of set theory, an ultrafilter is a ''maximal proper filter'': it is a filter U on a given non-empty set X which is a certain type of non-empty family of subsets of X, that is not equal to the power set \wp(X) of X (suc ...

for

Boolean algebra In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variables are the truth values ''true'' and ''false'', usually denoted 1 and 0, whereas i ...

s, applied to the Lindenbaum algebra of a theory.

Uses

It is used in the proof of

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. The completeness theorem applies to any first-order theory: ...

, among other places.

Extensions

The effective version of the lemma's statement, "every consistent

computably enumerable In computability theory, a set ''S'' of natural numbers is called computably enumerable (c.e.), recursively enumerable (r.e.), semidecidable, partially decidable, listable, provable or Turing-recognizable if: *There is an algorithm such that the ...

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

; it is originally attributed to him by

Alfred Tarski Alfred Tarski (, born Alfred Teitelbaum;School of Mathematics and Statistics, University of St Andrews ''School of Mathematics and Statistics, University of St Andrews''. January 14, 1901 – October 26, 1983) was a Polish-American logician a ...

.Tarski, A. ''On Fundamental Concepts of Metamathematics'', 1930.

Notes

References

* Mathematical logic Lemmas {{logic-stub