Lindenbaum–Tarski algebra

From Wikipedia, the free encyclopedia

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 1 Operations 2 Related algebras 3 See also 4 References

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

[edit] Related algebras

Heyting algebras and interior algebras are the Lindenbaum-Tarski algebras for intuitionistic logic and the modal logic S4, respectively.

[edit] See also

• Abstract algebraic logic
• Algebraic logic
• List of Boolean algebra topics

[edit] References

• Hinman, P. (2005). Fundamentals of Mathematical Logic. A K Peters. ISBN 1-568-81262-0.