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 $⊢\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 $⊢$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)$” isconsidered 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 $⊢\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

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

${\displaystyle \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.