nLab
Lindenbaum-Tarski algebra

The Lindenbaum–Tarski algebra of a normal modal logic

Associated to any normal modal logic, $\Lambda$ in ${ℒ}_{\omega }(n)$ (and more generally) is an algebra ${𝔄}_{\omega }^{\Lambda }$,which is a BAO of type $n$, i.e. $n$ (modal) operators, $m_i$. This is called the Lindenbaum–Tarski algebra of $\Lambda$, and is a quotient of the term algebra? of ${ℒ}_{\omega }(n)$, i.e. of the free universal algebra of type $n$ formed by the ${ℒ}_{\omega }(n)$-formulae using the connectives $\vee$, $\wedge$, $\neg$, $\perp$, $\top$, and the ${\diamond }_i$. The Lindenbaum–Tarski algebra is formed from this free algebra by using the congruence ${\simeq }_{\Lambda }$, where

$$\varphi {\simeq }_{\Lambda }\psi \mathrm{if}\mathrm{and}\mathrm{only}\mathrm{if}{⊢}_{\Lambda }\varphi \leftrightarrow \psi .$$\phi \simeq_\Lambda\psi if and only if {\vdash}_\Lambda \phi\leftrightarrow \psi.

(Recall the usual rules of notation: $\varphi \to \psi$ is $\neg \varphi \vee \psi$; $\varphi \leftrightarrow \psi$ is $(\varphi \to \psi )\wedge (\psi \to \varphi )$; and ${⊢}_{\Lambda }\varphi$ means $\varphi \in \Lambda$.)

The elements of ${𝔄}_{\omega }^{\Lambda }$ are the equivalence classes:

$$\parallel \varphi \parallel =\{\psi \mid {⊢}_{\Lambda }\varphi \leftrightarrow \psi \},$${\left\|\phi\right\|} = \{\psi \mid \vdash_\Lambda \phi\leftrightarrow \psi\},

with the operations

• $\parallel \varphi \parallel +\parallel \psi \parallel =\parallel \varphi \vee \psi \parallel$;

• $\parallel \varphi \parallel \cdot \parallel \psi \parallel =\parallel \varphi \wedge \psi \parallel \mid \mid \mid \mid$;

• $\mid \mid \varphi \mid {\mid }^{-}=\mid \mid \neg \varphi \mid \mid$;

• $0=\mid \mid \perp \mid \mid$;

• $1=\mid \mid \top \mid \mid$;

and

• $m_i\mid \mid \varphi \mid \mid =\mid \mid {\diamond }_i\varphi \mid \mid .$$

As we assumed that $\Lambda$ was normal, the normality schemata:

$(K)$: $\diamond (\psi \vee \chi )\to \diamond \psi \vee \diamond \chi$;

$(N)$, in the form, $\neg {\diamond }_i(\perp )$

and monotonicity :

if $\psi \to \chi \in \Lambda$ then ${\diamond }_i\psi \to {\diamond }_i\chi \in \Lambda$.

imply

Lemma

$m_i$ is a normal operator.

Proof

We first note that ${⊢}_{\Lambda }\diamond (\psi \vee \varphi )\leftrightarrow {\diamond }_i\psi \vee {\diamond }_i\varphi$, then the result follows by simply writing down what is required and staring at it for a moment!

Canonical models

The Lindenbaum–Tarski algebra for a modal logic, $\Lambda$, gives rise a canonical Kripke model. This has the set of $\Lambda$-maximal consistent formulae as its set of states.