# 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 $\varphi\sim\psi$ if and only if $\vdash\varphi\Leftrightarrow\psi$. Let $B=L/\sim$ be the set of equivalence classes. We define the operations join $\vee$, meet $\wedge$, and complementation, denoted $[\varphi]^{\prime}$ on $B$ by :

 $\displaystyle[\varphi]\vee[\psi]$ $\displaystyle:=[\varphi\vee\psi]$ $\displaystyle\wedge[\psi]$ $\displaystyle:=[\varphi\wedge\psi]$ ${}^{\prime}$ $\displaystyle:=[\neg\varphi]$

We let $0=[\varphi\wedge\neg\varphi]$ and $1=[\varphi\vee\neg\varphi]$. 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 $\lor,\land,\neg$ and that $\vdash$ 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, “$\neg(P_{1}\land P_{2})$” is considered the same as “$\neg P_{1}\lor\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 $\varphi\sim\psi$ if and only if $\vdash\varphi\Leftrightarrow\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

 $\displaystyle\bigvee_{t\in T}[\varphi(t)]$ $\displaystyle:=[\exists x\varphi(x)]$ $\displaystyle\bigwedge_{t\in T}[\varphi(t)]$ $\displaystyle:=[\forall x\varphi(x)]$

where $T$ is the set of all terms in the language $L$. Basically, these results say that the statement $\exists x\varphi(x)$ is equivalent to taking the supremum of all statements $\varphi(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\varphi(x)$ is true. The statement $\forall x\varphi(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 LindenbaumTarskiAlgebra 2013-03-22 12:42:40 2013-03-22 12:42:40 CWoo (3771) CWoo (3771) 31 CWoo (3771) Definition msc 03G05 msc 03B05 msc 03B10 Lindenbaum algebra