canonical model

Recall that a logic is a set of wff’s containing all tautologies and closed under modus ponens. Given a logic $\mathrm{\Lambda }$, a set $\mathrm{\Delta }$ of wff’s is $\mathrm{\Lambda }$-consistent if $⟂$ can not be deduced from $\mathrm{\Delta }$ given $\mathrm{\Lambda }$. $\mathrm{\Lambda }$ itself is said to be $\mathrm{\Lambda }$-consistent if $⟂$ can not be deduced from the empty set. Let $\mathrm{\Lambda }$ be a consistent normal modal logic. The canonical frame for $\mathrm{\Lambda }$ is the Kripke frame ${ℱ}_{\mathrm{\Lambda }}:=(W_{\mathrm{\Lambda }},R_{\mathrm{\Lambda }})$, where

1. $W_{\mathrm{\Lambda }}$ is the set of all maximally consistent sets, and

2. $w{R}_{\mathrm{\Lambda }}u$ iff $\mathrm{\square }A\in w$ implies $A\in u$ for any wff $A$.

If we define ${\mathrm{\Delta }}_w:=\{B\mid \mathrm{\square }B\in w\}$, then the second condition above reads $w{R}_{\mathrm{\Lambda }}u$ iff ${\mathrm{\Delta }}_w\subseteq u$.

The canonical model of $\mathrm{\Lambda }$ based on ${ℱ}_{\mathrm{\Lambda }}$ is the pair $M_{\mathrm{\Lambda }}:=({ℱ}_{\mathrm{\Lambda }},V_{\mathrm{\Lambda }})$, where

• $V(p):=\{w\in W_{\mathrm{\Lambda }}\mid p\in w\}$.

The main result regarding the canonical model of $\mathrm{\Lambda }$ is:

Theorem 1.

$M_{\mathrm{\Lambda }}\vDash A$ iff $\mathrm{\Lambda }\mathrm{⊢}A$, where $A$ is any wff.

Since the logic $\mathrm{\Lambda }$ is the intersection of all maximally consistent sets (see here (http://planetmath.org/LindenbaumsLemma)), the theorem is the result of the following:

Proposition 1.

$M_{\mathrm{\Lambda }}{\vDash }_{w}A$ iff $A\mathrm{\in }w$.

which is the result of the following:

Lemma 1.

For any world $w$ in $M_{\mathrm{\Lambda }}$, $\mathrm{\square }\mathit{}A\mathrm{\in }w$ iff $A\mathrm{\in }u$ for all worlds $u$ such that $w\mathit{}{R}_{\mathrm{\Lambda }}\mathit{}u$.

Proof.

Suppose $\mathrm{\square }A\in w$ and $w{R}_{\mathrm{\Lambda }}u$. Then $A\in u$ by the definition of $R_{\mathrm{\Lambda }}$. Conversely, suppose $A\in u$ for all $u$ such that $w{R}_{\mathrm{\Lambda }}u$. In other words, $A\in u$ for all $u$ such that ${\mathrm{\Delta }}_w\subseteq u$, or $A\in \bigcap \{u\mid {\mathrm{\Delta }}_w\subseteq u\}$. But $\bigcap \{u\mid {\mathrm{\Delta }}_w\subseteq u\}=\text{Ded}({\mathrm{\Delta }}_w)$, the deductive closure of ${\mathrm{\Delta }}_w$, so ${\mathrm{\Delta }}_w⊢A$, and therefore $\mathrm{\square }{\mathrm{\Delta }}_w⊢\mathrm{\square }A$ (see here (http://planetmath.org/SyntacticPropertiesOfANormalModalLogic)), or $w⊢\mathrm{\square }A$ (since ${\mathrm{\Delta }}_w\subseteq w$), or $\mathrm{\square }A\in w$ (since $w$ is maximally consistent). ∎

Proof of Proposition 1. We do induction on the number $n$ of logical connectives in $A$. If $n=0$, then $A$ is either a propositional variable or $⟂$. The former is just the definition of $V_{\mathrm{\Lambda }}$. The later case is just the definition of $\mathrm{\Lambda }$-consistency. Next, if $A$ is $B\to C$, then $M_{\mathrm{\Lambda }}{\vDash }_{w}A$ iff either $M_{\mathrm{\Lambda }}{\vDash ̸}_{w}B$ or $M_{\mathrm{\Lambda }}{\vDash }_{w}C$ iff $B\notin w$ or $C\in w$ iff $\mathrm{\neg }B\in w$ or $C\in w$ iff $\mathrm{\neg }B\vee C\in w$ iff $A\in w$. Finally, if $A$ is $\mathrm{\square }B$, then $M_{\mathrm{\Lambda }}{\vDash }_w\mathrm{\square }B$ iff $\mathrm{\square }B\in w$ iff $B\in u$ for all $u$ such that $w{R}_{\mathrm{\Lambda }}u$ iff $M_{\mathrm{\Lambda }}{\vDash }_{u}B$ for all $u$ such that $w{R}_{\mathrm{\Lambda }}u$.

Recall that a logic is complete in a frame if it is complete in every model based on the frame. As a corollary to Theorem 1, we have

Corollary 1.

$\mathrm{\Lambda }$ is complete in its canonical frame ${\mathrm{F}}_{\mathrm{\Lambda }}$.

Proof.

Any wff valid in every model based on ${ℱ}_{\mathrm{\Lambda }}$ is valid in $M_{\mathrm{\Lambda }}$ in particular, and therefore a theorem of $\mathrm{\Lambda }$ by Theorem 1. ∎

The converse is not true. There are in fact normal modal logics that are sound in no frames at all.

Canonical models are useful in proving the completeness theorems for many common normal modal logics. To prove that a logic is complete in a class of frames, by the corollary above, it is enough to show that the canonical frame is in the class. Here are two examples:

1. Let $\mathrm{\Lambda }$ be the smallest normal logic containing the schema $\mathrm{\square }A$. Then $\mathrm{\Lambda }$ is complete in the class of null frames.

   Proof.

   By the discussion above, it is enough to show that ${ℱ}_{\mathrm{\Lambda }}$ is a null frame: the assumption $\exists w\exists u(w{R}_{\mathrm{\Lambda }}u)$ leads to a contradiction. Suppose $w{R}_{\mathrm{\Lambda }}u$. Then ${\mathrm{\Delta }}_w\subseteq u$. This means that if $\mathrm{\square }A\in w$, then $A\in u$. But $\mathrm{\square }A$ is a theorem (in $\mathrm{\Lambda }$), $\mathrm{\square }A\in w$ for any wff $A$. This means that $A\in u$ for any wff $A$, or that $u$ is inconsistent, a contradiction. ∎

2. Let $\mathrm{\Lambda }$ be the smallest normal logic containing the schema $A\to \mathrm{\square }A$. Then $\mathrm{\Lambda }$ is complete in the class of weak identity frames (a binary relation $R$ is weak identity it is satisfies the condition $\forall x\forall y(xRy\to x=y)$).

   Proof.

   Again, we show that $R_{\mathrm{\Lambda }}$ is weak identity. Suppose $w{R}_{\mathrm{\Lambda }}u$. Then for any $A$, $\mathrm{\square }A\in w$ implies that $A\in u$. Now, if $A\in w$, then applying modus ponens to $A\to \mathrm{\square }A$, we get that $\mathrm{\square }A\in w$ since $w$ is closed under modus ponens. But this means that $A\in u$. So $w\subseteq u$. But since both $w$ and $u$ are maximal, they are the same. ∎

Title	canonical model
Canonical name	CanonicalModel
Date of creation	2013-03-22 19:35:01
Last modified on	2013-03-22 19:35:01
Owner	CWoo (3771)
Last modified by	CWoo (3771)
Numerical id	15
Author	CWoo (3771)
Entry type	Definition
Classification	msc 03B45
Defines	canonical frame