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
- Tarski, A. On Fundamental Concepts of Metamathematics, 1930.
gollark: The outdoor rocks might be far away, or too wet or something, or not at the level of difficulty you want.
gollark: It does say to do warm-ups. Just that stretching isn't an effective one. I will have to investigate further or something.
gollark: I see.
gollark: I found the thing I read in my browser history (https://www.painscience.com/articles/stretching.php), and it says that stretching hasn't been found to reduce injury risk, and might just make the brain happier with using more range of motion without actually changing the muscles.
gollark: Does it actually do that?
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: Oxford University Press. p. 16. ISBN 0-19-888087-1. Zbl 0251.02001.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.