You are here
Homecanonical model
Primary tabs
canonical model
Recall that a logic is a set of wff’s containing all tautologies and closed under modus ponens. Given a logic $\Lambda$, a set $\Delta$ of wff’s is $\Lambda$consistent if $\perp$ can not be deduced from $\Delta$ given $\Lambda$. $\Lambda$ itself is said to be $\Lambda$consistent if $\perp$ can not be deduced from the empty set. Let $\Lambda$ be a consistent normal modal logic. The canonical frame for $\Lambda$ is the Kripke frame $\mathcal{F}_{{\Lambda}}:=(W_{{\Lambda}},R_{{\Lambda}})$, where
1. $W_{{\Lambda}}$ is the set of all maximally consistent sets, and
2.
If we define $\Delta_{w}:=\{B\mid\square B\in w\}$, then the second condition above reads $wR_{{\Lambda}}u$ iff $\Delta_{w}\subseteq u$.
The canonical model of $\Lambda$ based on $\mathcal{F}_{{\Lambda}}$ is the pair $M_{{\Lambda}}:=(\mathcal{F}_{{\Lambda}},V_{{\Lambda}})$, where

$V(p):=\{w\in W_{{\Lambda}}\mid p\in w\}$.
The main result regarding the canonical model of $\Lambda$ is:
Theorem 1.
$M_{{\Lambda}}\models A$ iff $\Lambda\vdash A$, where $A$ is any wff.
Since the logic $\Lambda$ is the intersection of all maximally consistent sets (see here), the theorem is the result of the following:
Proposition 1.
$M_{{\Lambda}}\models_{w}A$ iff $A\in w$.
which is the result of the following:
Lemma 1.
For any world $w$ in $M_{{\Lambda}}$, $\square A\in w$ iff $A\in u$ for all worlds $u$ such that $wR_{{\Lambda}}u$.
Proof.
Suppose $\square A\in w$ and $wR_{{\Lambda}}u$. Then $A\in u$ by the definition of $R_{{\Lambda}}$. Conversely, suppose $A\in u$ for all $u$ such that $wR_{{\Lambda}}u$. In other words, $A\in u$ for all $u$ such that $\Delta_{w}\subseteq u$, or $A\in\bigcap\{u\mid\Delta_{w}\subseteq u\}$. But $\bigcap\{u\mid\Delta_{w}\subseteq u\}=\mbox{Ded}(\Delta_{w})$, the deductive closure of $\Delta_{w}$, so $\Delta_{w}\vdash A$, and therefore $\square\Delta_{w}\vdash\square A$ (see here), or $w\vdash\square A$ (since $\Delta_{w}\subseteq w$), or $\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 $\perp$. The former is just the definition of $V_{{\Lambda}}$. The later case is just the definition of $\Lambda$consistency. Next, if $A$ is $B\to C$, then $M_{{\Lambda}}\models_{w}A$ iff either $M_{{\Lambda}}\not\models_{w}B$ or $M_{{\Lambda}}\models_{w}C$ iff $B\notin w$ or $C\in w$ iff $\neg B\in w$ or $C\in w$ iff $\neg B\lor C\in w$ iff $A\in w$. Finally, if $A$ is $\square B$, then $M_{{\Lambda}}\models_{w}\square B$ iff $\square B\in w$ iff $B\in u$ for all $u$ such that $wR_{{\Lambda}}u$ iff $M_{{\Lambda}}\models_{u}B$ for all $u$ such that $wR_{{\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.
$\Lambda$ is complete in its canonical frame $\mathcal{F}_{{\Lambda}}$.
Proof.
Any wff valid in every model based on $\mathcal{F}_{{\Lambda}}$ is valid in $M_{{\Lambda}}$ in particular, and therefore a theorem of $\Lambda$ by Theorem 1. ∎
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 $\Lambda$ be the smallest normal logic containing the schema $\square A$. Then $\Lambda$ is complete in the class of null frames.
Proof.
By the discussion above, it is enough to show that $\mathcal{F}_{{\Lambda}}$ is a null frame: the assumption $\exists w\exists u(wR_{{\Lambda}}u)$ leads to a contradiction. Suppose $wR_{{\Lambda}}u$. Then $\Delta_{w}\subseteq u$. This means that if $\square A\in w$, then $A\in u$. But $\square A$ is a theorem (in $\Lambda$), $\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 $\Lambda$ be the smallest normal logic containing the schema $A\to\square A$. Then $\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_{{\Lambda}}$ is weak identity. Suppose $wR_{{\Lambda}}u$. Then for any $A$, $\square A\in w$ implies that $A\in u$. Now, if $A\in w$, then applying modus ponens to $A\to\square A$, we get that $\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. ∎
Mathematics Subject Classification
03B45 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