Lindenbaum-Tarski algebra
Lindenbaum-Tarski algebra of a propositional langauge
Let be a classical propositional language. We define the equivalence relation over formulas of by if and only if . Let be the set of equivalence classes. We define the operations join , meet , and complementation, denoted on by :
We let and . Then the structure is a Boolean algebra, called the Lindenbaum-Tarski algebra of the propositional language .
Intuitively, this algebra is an algebra of logical statements in which logically equivalent formulations of the same statement are not distinguished. One can develop intuition for this algrebra by considering a simple case. Suppose our language consists of a number of statement symbols and the connectives and that denotes tautologies. Then our algebra consists of statements formed from these connectives with tautologously equivalent satements reckoned as the same element of the algebra. For instance, “” is considered the same as “”. Furthermore, since any statement of propositional calculus may be recast in disjunctive normal form, we may view this particular Lindenbaum-Tarski algebra as a Boolean analogue of polynomials in the ’s and their negations.
It can be shown that the Lindenbaum-Tarski algebra of the propositional language is a free Boolean algebra freely generated by the set of all elements , where each is a propositional variable of
Lindenbaum-Tarski algebra of a first order langauge
Now, let be a first order language. As before, we define the equivalence relation over formulas of by if and only if . Let be the set of equivalence classes. The operations and and complementation on are defined exactly the same way as previously. The resulting algebra is the Lindenbaum-Tarski algebra of the first order language . It may be shown that
where is the set of all terms in the language . Basically, these results say that the statement is equivalent to taking the supremum of all statements where ranges over the entire set of variables. In other words, if one of these statements is true (with truth value , as opposed to ), then is true. The statement can be similarly analyzed.
Remark. It may possible to define the Lindenbaum-Tarski algebra on logical languages other than the classical ones mentioned above, as long as there is a notion of formal proof that can allow the definition of the equivalence relation. For example, one may form the Lindenbaum-Tarski algebra of an intuitionistic propositional language (or predicate language) or a normal modal propositional language. The resulting algebra is a Heyting algebra (or a complete Heyting algebra) for intuitionistic propositional language (or predicate language), or a Boolean algebras with an operator for normal modal propositional languages.
Title | Lindenbaum-Tarski algebra |
---|---|
Canonical name | LindenbaumTarskiAlgebra |
Date of creation | 2013-03-22 12:42:40 |
Last modified on | 2013-03-22 12:42:40 |
Owner | CWoo (3771) |
Last modified by | CWoo (3771) |
Numerical id | 31 |
Author | CWoo (3771) |
Entry type | Definition |
Classification | msc 03G05 |
Classification | msc 03B05 |
Classification | msc 03B10 |
Synonym | Lindenbaum algebra |