World Library  
Flag as Inappropriate
Email this Article

Lindenbaum's lemma

Article Id: WHEBN0006625296
Reproduction Date:

Title: Lindenbaum's lemma  
Author: World Heritage Encyclopedia
Language: English
Subject: Mathematical Logic, Adolf Lindenbaum, Theory (mathematical logic), Lemmas, Logic Gates & Human Logic
Collection: Lemmas, Mathematical Logic
Publisher: World Heritage Encyclopedia
Publication
Date:
 

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.

Contents

  • Uses 1
  • Extensions 2
  • History 3
  • Notes 4
  • References 5
  • External links 6

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

  • Crossley, J.N.; Ash, C.J.; Brickhill, C.J.; Stillwell, J.C.; Williams, N.H. (1972). What is mathematical logic?. London-Oxford-New York:  

External links

  • University of Texas, A Causal Theory of Modal Knowledge (Including Logical and Mathematical Knowledge
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 


Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.