mathematical logic Mathematical logic is the study of Logic#Formal logic, formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory (also known as computability theory). Research in mathematical logic com ...

, 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. Life He was born and brought up in Warsaw. He earned a Ph.D. in 1928 un ...

, states that any consistent theory of

predicate logic First-order logic, also called predicate logic, predicate calculus, or quantificational logic, is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantified variables ove ...

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 on a set X is a ''maximal filter'' on the set X. In other words, it is a collection of subsets of X that satisfies the definition of a filter on X and that is maximal with respect to incl ...

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 variable (mathematics), variables are the truth values ''true'' and ''false'', usually denot ...

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 semantics, semantic truth and syntactic Provability logic, provability in first-order logic. The completeness theorem applies ...

, 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 In mathematical logic, the Peano axioms (, ), also known as the Dedekind–Peano axioms or the Peano postulates, are axioms for the natural numbers presented by the 19th-century Italian mathematician Giuseppe Peano. These axioms have been used nea ...

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 ...

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

Notes

References

* Mathematical logic Lemmas {{logic-stub