Lindenbaum's lemma

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In mathematical logic, Lindenbaum's lemma 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[edit]

It is used in the proof of Gödel's completeness theorem, among other places.

Extensions[edit]

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[edit]

The lemma was not published by Adolf Lindenbaum; it is originally attributed to him by Alfred Tarski.[1]

Notes[edit]

  1. ^ Tarski, A. On Fundamental Concepts of Metamathematics, 1930.

References[edit]

External links[edit]