Lindenbaum-Tarski algebra


Lindenbaum-Tarski algebra of a propositional langauge

Let L be a classical propositional languagePlanetmathPlanetmath. We define the equivalence relationMathworldPlanetmath over formulasMathworldPlanetmathPlanetmath of L by φψ if and only if φψ. Let B=L/ be the set of equivalence classesMathworldPlanetmath. We define the operationsMathworldPlanetmath join , meet , and complementation, denoted [φ] on B by :

[φ][ψ] :=[φψ]
[ψ] :=[φψ]
:=[¬φ]

We let 0=[φ¬φ] and 1=[φ¬φ]. Then the structureMathworldPlanetmath (B,,,,0,1) is a Boolean algebraMathworldPlanetmath, called the Lindenbaum-Tarski algebra of the propositional language L.

Intuitively, this algebraMathworldPlanetmath 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 Pi and the connectivesMathworldPlanetmath ,,¬ and that denotes tautologiesMathworldPlanetmath. Then our algebra consists of statements formed from these connectives with tautologously equivalentMathworldPlanetmathPlanetmathPlanetmath satements reckoned as the same element of the algebra. For instance, “¬(P1P2)” is considered the same as “¬P1¬P2”. Furthermore, since any statement of propositional calculusMathworldPlanetmath may be recast in disjunctive normal formMathworldPlanetmath, we may view this particular Lindenbaum-Tarski algebra as a Boolean analogue of polynomialsMathworldPlanetmath in the Pi’s and their negationsMathworldPlanetmath.

It can be shown that the Lindenbaum-Tarski algebra of the propositional language L is a free Boolean algebra freely generated by the set of all elements [p], where each p is a propositional variable of L

Lindenbaum-Tarski algebra of a first order langauge

Now, let L be a first order language. As before, we define the equivalence relation over formulas of L by φψ if and only if φψ. Let B=L/ be the set of equivalence classes. The operations and and complementation on B are defined exactly the same way as previously. The resulting algebra is the Lindenbaum-Tarski algebra of the first order language L. It may be shown that

tT[φ(t)] :=[xφ(x)]
tT[φ(t)] :=[xφ(x)]

where T is the set of all terms in the language L. Basically, these results say that the statement xφ(x) is equivalent to taking the supremumMathworldPlanetmathPlanetmath of all statements φ(x) where x ranges over the entire set V of variables. In other words, if one of these statements is true (with truth value 1, as opposed to 0), then xφ(x) is true. The statement xφ(x) 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 predicateMathworldPlanetmath 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