mathematical logic Mathematical logic is the study of logic, 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 for ...

, 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 In classical deductive logic, a consistent theory is one that does not lead to a logical contradiction. The lack of contradiction can be defined in either semantic or syntactic terms. The semantic definition states that a theory is consistent ...

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 Complete may refer to: Logic * Completeness (logic) * Completeness of a theory, the property of a theory that every formula in the theory's language or its negation is provable Mathematics * The completeness of the real numbers, which implies t ...

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

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

s, applied to the

Lindenbaum algebra Lindenbaum is a surname, meaning '' Tilia'' in German; the nearest British tree name is Lime tree. It may refer to: * Belda Lindenbaum, Jewish philanthropist and feminist *Adolf Lindenbaum, Polish mathematician **Lindenbaum's lemma ** Lindenbaum ...

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

, 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 nearly u ...

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