Lindenbaum's lemma

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

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

Extensions

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

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

Notes

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

References

External links

This article is issued from Wikipedia - version of the Tuesday, November 25, 2014. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.