Lindenbaum–Tarski algebra

From Wikipedia, the free encyclopedia

In mathematical logic, the Lindenbaum-Tarski algebra A of a logical theory T consists of the equivalence classes of sentences p of the theory, under the equivalence relation ~ defined by

p ~ q when p and q are logically equivalent in T.

That is, in T the sentence q can be deduced from p, and p from q.

Operations in A are inherited from those available in T, typically conjunction and disjunction, where they are well-defined on the classes. When negation is also present in T, then A is a Boolean algebra, provided the logic is classical. Conversely, for every Boolean algebra A, there is a theory T of (classical) sentential logic such that the Lindenbaum-Tarski algebra of T is isomorphic to A. In other words, every Boolean algebra is (up to isomorphism) a Lindenbaum-Tarski algebra.

In the case of intuitionistic logic, the Lindenbaum-Tarski algebras are the Heyting algebras.

Sometimes called simply Lindenbaum algebra, this construction is named for logicians Adolf Lindenbaum and Alfred Tarski.

[edit] See also

• List of Boolean algebra topics

[edit] References

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