In mathematical logic, the Lindenbaum–Tarski algebra (or Lindenbaum algebra) of a logical theory T consists of the equivalence classes of sentences of the theory, under the equivalence relation ~ defined such that p ~ q exactly when p and q are provably equivalent in T. That is, two sentences are equivalent if the theory T proves that each implies the other. The algebra is named for logicians Adolf Lindenbaum and Alfred Tarski.
Contents |
Operations
The operations in a Lindenbaum–Tarski algebra A are inherited from those in the underlying theory T. These typically include conjunction and disjunction, which are well-defined on the equivalence classes. When negation is also present in T, then A is a Boolean algebra, provided the logic is classical. Conversely, for every countable Boolean algebra A, there is a theory T of (classical) sentential logic such that the Lindenbaum-Tarski algebra of T is isomorphic to A. (We may drop the restriction to countable Boolean algebras if we allow theories in uncountable languages.) In other words, every Boolean algebra is (up to isomorphism) a Lindenbaum-Tarski algebra.
Related algebras
Heyting algebras and interior algebras are the Lindenbaum-Tarski algebras for intuitionistic logic and the modal logic S4, respectively.
See also
References
- Hinman, P. (2005). Fundamentals of Mathematical Logic. A K Peters. ISBN 1-568-81262-0.
 |
This mathematical logic-related article is a stub. You can help Wikipedia by expanding it. |
This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)
