p-morphism

Let ${ℱ}_1=(W_1,R_1)$ and ${ℱ}_2=(W_2,R_2)$ be Kripke frames. A p-morphism from ${ℱ}_1$ to ${ℱ}_2$ is a function $f:W_1\to W_2$ such that

• if $u{R}_{1}w$, then $f(u)R_{2}f(w)$,

• if $s{R}_{2}t$ and $s=f(u)$ for some $u\in W_1$, then $u{R}_{1}w$ and $t=f(w)$ for some $w\in W_1$,

We write $f:{ℱ}_1\to {ℱ}_2$ to denote that $f$ is a p-morphism from ${ℱ}_1$ to ${ℱ}_2$.

Let $M_1=({ℱ}_1,V_1)$ and $M_2=({ℱ}_2,V_2)$ be Kripke models of modal propositional logic PL${}_M$. A p-morphism from $M_1$ to $M_2$ is a p-morphism $f:{ℱ}_1\to {ℱ}_2$ such that

• $M_1{\vDash }_{w}p$ iff $M_2{\vDash }_{f(w)}p$ for any propositional variable $p$.

Proposition 1.

For any wff $A$, $M_{\mathrm{1}}{\mathrm{\vDash }}_{w}A$ iff $M_{\mathrm{2}}{\mathrm{\vDash }}_{f\mathit{}\mathrm{(}w\mathrm{)}}A$.

Proof.

Induct on the number $n$ of logical connectives in $A$. When $n=0$, $A$ is either $⟂$ or a propositional variable. The case when $A$ is $⟂$ is obvious, and the other case is definition. Next, suppose $A$ is $B\to C$, then $M_1{\vDash }_{w}A$ iff $M_1{\vDash ̸}_{w}B$ or $M_1{\vDash }_{w}C$ iff $M_2{\vDash ̸}_{f(w)}B$ or $M_2{\vDash }_{f(w)}C$ iff $M_2{\vDash }_{f(w)}A$. Finally, suppose $A$ is $\mathrm{\square }B$, and $M_1{\vDash }_{w}A$. To show $M_2{\vDash }_{f(w)}A$, let $t$ be such that $f(w)R_{2}t$. Then there is a $u$ such that $t=f(u)$ and $w{R}_{1}u$, so that $M_1{\vDash }_{u}B$. By induction, $M_2{\vDash }_{f(u)}B$, or $M_2{\vDash }_{t}B$. Hence $M_2{\vDash }_{f(w)}A$. Conversely, suppose $M_2{\vDash }_{f(w)}A$. To show $M_1{\vDash }_{w}A$, let $u$ be such that $w{R}_{1}u$. So $f(w)R_{2}f(u)$, and therefore $M_2{\vDash }_{f(u)}B$. By induction, $M_1{\vDash }_{u}B$, whence $M_1{\vDash }_{w}A$. ∎

Proposition 2.

If a p-morphism $f\mathrm{:}{\mathrm{F}}_{\mathrm{1}}\mathrm{\to }{\mathrm{F}}_{\mathrm{2}}$ is one-to-one, then ${\mathrm{F}}_{\mathrm{2}}\mathrm{\vDash }A$ implies ${\mathrm{F}}_{\mathrm{1}}\mathrm{\vDash }A$ for any wff $A$.

Proof.

Suppose ${ℱ}_2\vDash A$. Let $M=(W_1,R_1,V_1)$ be any model based on ${ℱ}_1$ and $w$ any world in $W_1$. We want to show that $M{\vDash }_{w}A$.

Define a Kripke model $M^{\prime }:=(W_2,R_2,V_2)$ as follows: for any propositional variable $p$, let $V_2(p):=\{s\in W_2\mid f^{-1}(s)\cap V_1(p)\ne \mathrm{\varnothing }\}$. Then $M{\vDash }_{w}p$ iff $w\in V_1(p)$ iff $f^{-1}(f(w))=\{w\}\subseteq V_1(p)$ (since $f$ is one-to-one) iff $f^{-1}(f(w))\cap V_1(p)\ne \mathrm{\varnothing }$ iff $f(w)\in V_2(p)$ iff $M^{\prime }{\vDash }_{f(w)}p$. This shows that $f$ is a p-morphism from $M$ to $M^{\prime }$.

Now, let $w\in W_1$. Then $M^{\prime }{\vDash }_{f(w)}A$ by assumption. By the last proposition, $M{\vDash }_{w}A$. ∎

Proposition 3.

If a p-morphism $f\mathrm{:}{\mathrm{F}}_{\mathrm{1}}\mathrm{\to }{\mathrm{F}}_{\mathrm{2}}$ is onto, then ${\mathrm{F}}_{\mathrm{1}}\mathrm{\vDash }A$ implies ${\mathrm{F}}_{\mathrm{2}}\mathrm{\vDash }A$ for any wff $A$.

Proof.

Suppose ${ℱ}_1\vDash A$. Let $M=(W_2,R_2,V_2)$ be any model based on ${ℱ}_2$ and $s$ any world in $W_2$. We want to show that $M{\vDash }_{s}A$.

Define a Kripke model $M^{\prime }:=(W_1,R_1,V_1)$ as follows: for any propositional variable $p$, let $V_1(p):=\{w\in W_1\mid f(w)\in V_2(p)\}$. Then $w\in V_1(p)$ iff $f(w)\in V_2(p)$, so $f$ is a p-morphism from $M^{\prime }$ to $M$, and by assumption $M^{\prime }\vDash A$ for any wff $A$.

Now, let $w\in W_1$ be a world such that $f(w)=s$. Since $M^{\prime }\vDash A$, $M^{\prime }{\vDash }_{w}A$ in particular, and therefore $M{\vDash }_{f(w)}A$ or $M{\vDash }_{s}A$ by the last proposition. ∎

Corollary 1.

If $f\mathrm{:}{\mathrm{F}}_{\mathrm{1}}\mathrm{\to }{\mathrm{F}}_{\mathrm{2}}$ is bijective, then ${\mathrm{F}}_{\mathrm{1}}\mathrm{\vDash }A$ iff ${\mathrm{F}}_{\mathrm{2}}\mathrm{\vDash }A$ for any wff $A$.

A frame ${ℱ}^{\prime }$ is said to be a p-morphic image of a frame $ℱ$ if there is an onto p-morphism $f:ℱ\to {ℱ}^{\prime }$. Let $𝒞$ be the class of all frames validating a wff. Then by the third proposition above, $𝒞$ is closed under p-morphic images: if a frame is in $𝒞$, so is any of its p-morphic images. Using this property, we can show the following: if $𝒞$ is the class of all frames validating a wff $A$, then $𝒞$ can not be

• the class of all irreflexive frames

• the class of all asymetric frames

• the class of all anti-symmetric frames

Proof.

Let and ${ℱ}_2=(\{0\},R)$, where $0R0$. Notice that ${ℱ}_1$ is in both the class of irreflexive frames and the class of asymetric frames, but ${ℱ}_2$ is in neither. Let $f:\mathbb{N}\to \{0\}$ be the obvious surjection. Clearly, implies $f(m)Rf(n)$. Also, if $f(m)R0$, then $f(m)Rf(m+1)$. So $f$ is a p-morphism. Suppose $𝒞$ is either the class of all irreflexive frames or the class of all asymetric frames. If $A$ is validated by $𝒞$, $A$ is validated by ${ℱ}_1$ in particular (since ${ℱ}_1$ is in $𝒞$), so that $A$ is validated by ${ℱ}_2$ as well, which means ${ℱ}_2$ is $𝒞$ too, a contradiction. Therefore, no such an $A$ exists.

Next, let ${ℱ}_3=(\mathbb{N},S)$, where $nS(n+1)$ for all $n\in \mathbb{N}$ and ${ℱ}_4=(\{0,1\},R)$, where $R=\{(0,1),(1,0)\}$. Let $𝒞$ be the class of all anti-symmetric frames. Then ${ℱ}_3$ is in $𝒞$ but ${ℱ}_4$ is not. Let $f:{ℱ}_3\to {ℱ}_4$ be given by $f(n)=0$ if $n$ is even and $f(n)=1$ if $n$ is odd. If $aSb$, then $f(a)$ and $f(b)$ differ by $1$, so $f(a)Rf(b)$. On the other hand, if $f(a)Rx$, then $x$ is either $0$ or $1$, depending on whether $a$ odd or even. Pick $b=a+1$, so $aSb$ and $f(b)=x$. This shows that $f$ is a p-morphism. By the same argument as in the last paragraph, no wff $A$ is validated by precisely the members of $𝒞$. ∎

Title	p-morphism
Canonical name	Pmorphism
Date of creation	2013-03-22 19:34:54
Last modified on	2013-03-22 19:34:54
Owner	CWoo (3771)
Last modified by	CWoo (3771)
Numerical id	12
Author	CWoo (3771)
Entry type	Definition
Classification	msc 03B45
Related topic	Bisimulation