# Lindenbaum-Tarski algebra

## Lindenbaum-Tarski algebra of a propositional langauge

Let $L$ be a classical propositional language^{}. We define the equivalence relation^{} $\sim $ over formulas^{} of $L$ by $\phi \sim \psi $ if and only if $\u22a2\phi \iff \psi $. Let $B=L/\sim $ be the set of equivalence classes^{}. We define the operations^{} join $\vee $, meet $\wedge $, and complementation, denoted ${[\phi ]}^{\prime}$ on $B$ by :

$[\phi ]\vee [\psi ]$ | $:=[\phi \vee \psi ]$ | ||

$\wedge [\psi ]$ | $:=[\phi \wedge \psi ]$ | ||

${}^{\prime}$ | $:=[\mathrm{\neg}\phi ]$ |

We let $0=[\phi \wedge \mathrm{\neg}\phi ]$ and $1=[\phi \vee \mathrm{\neg}\phi ]$. Then the structure^{} $(B,\vee ,\wedge {,}^{\prime},0,1)$ is a Boolean algebra^{}, called the *Lindenbaum-Tarski algebra* of the propositional language $L$.

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 ${P}_{i}$ and the connectives^{} $\vee ,\wedge ,\mathrm{\neg}$ and that $\u22a2$
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, “$\mathrm{\neg}({P}_{1}\wedge {P}_{2})$” is
considered the same as “$\mathrm{\neg}{P}_{1}\vee \mathrm{\neg}{P}_{2}$”. 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 ${P}_{i}$’s and their negations^{}.

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 $\sim $ over formulas of $L$ by $\phi \sim \psi $ if and only if $\u22a2\phi \iff \psi $. Let $B=L/\sim $ be the set of equivalence classes. The operations $\vee $ and $\wedge $ 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

$\underset{t\in T}{\bigvee}}[\phi (t)]$ | $:=[\exists x\phi (x)]$ | ||

$\underset{t\in T}{\bigwedge}}[\phi (t)]$ | $:=[\forall x\phi (x)]$ |

where $T$ is the set of all terms in the language $L$. Basically, these results say that the statement $\exists x\phi (x)$ is equivalent to taking the supremum^{} of all statements $\phi (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 $\exists x\phi (x)$ is true. The statement $\forall x\phi (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 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 |