## You are here

HomeLindenbaum-Tarski algebra

## Primary tabs

# 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.

## Mathematics Subject Classification

03G05*no label found*03B05

*no label found*03B10

*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections

## Corrections

Typo by kompik ✓

classification by CWoo ✓

capitalization by Mathprof ✓

propositional vs predicate calculus by CWoo ✓