Prove $\models_{S_5}\square(\square P\to\square Q)\lor\square(\square Q\to \square P)$ with natural deduction

117 Views Asked by At

Some defs. in general:

Let $\mathscr{M}(=\left<\mathscr{W,R,I~}\right>)$ be some MPL-model,

Where $\mathscr{W}$ is a non-empty set of objects ("possible worlds")

$\mathscr{R}$ is a binary relation over $\mathscr{W}$ ("accessiblity relation")

$\mathscr{I}$ is a two-place function ("interpretation function")

that assigns $0$ or $1$ to each $\underline{\text{sentence}}$ $\alpha$ relative to each world $\omega\in\mathscr{W}$

$V_\mathscr{M}$ is a two-place function ("valuation function")

that assigns $0$ or $1$ to each $\underline{\text{wffs}}$ $\phi$ relative to each world $\omega\in\mathscr{W}$

Let $V_\mathscr{M}$ be the valuation for $\mathscr{M}$, $\alpha$ be some sentence letter and $\omega\in\mathscr{W}$, then we have

$$V_\mathscr{M}(\alpha,\omega)=\mathscr{I(\alpha,\omega)}\tag*{(1)}$$

$$V_\mathscr{M}(\neg\phi,\omega)=1\text{ iff }V_\mathscr{M}(\phi,\omega)=0\tag*{(2)}$$

$$V_\mathscr{M}(\phi\to\varphi,\omega)=1\text{ iff }V_\mathscr{M}(\phi,\omega)=0\lor V_{\mathscr{M}}(\varphi,v)=1\tag*{(3)}$$

$$V_\mathscr{M}(\square\phi,\omega)=1\text{ iff }~\forall v\in\mathscr{W},\mathscr{R}wv\to V_{\mathscr{M}}(\phi,v)=1\tag*{(4)}$$

$$\text{etc.}$$

Prove the following statement

$$\models_{S_5}\square(\square P\to\square Q)\lor\square(\square Q\to \square P)$$

The question is asking to prove the statement in $S_5$, and i'm not familiar with natural deduction in MPL, but here my thoughts:

$1.$ Apply $(4)$ $$V_\mathscr{M}(\square(\square P\to\square Q)\lor\square(\square Q\to \square P),\omega)=1$$ $$\text{ iff }~\forall v_1\in\mathscr{W},\mathscr{R}wv_1\to \color{blue}{V_{\mathscr{M}}(\square P\to\square Q,v_1)=1}\lor \color{red}{V_{\mathscr{M}}(\square Q\to\square P,v_1)=1}\tag*{(0)}$$ $2.1.$ Apply $(3)$ $$\color{blue}{V_{\mathscr{M}}(\square P\to\square Q,v_1)=1}$$ $$\text{ iff }~\forall v_2\in\mathscr{W},(\mathscr{R}v_1v_2\to V_{\mathscr{M}}(P,v_2)=0\lor V_{\mathscr{M}}(Q,v_2)=1)$$ $2.2.$ Apply $(3)$ $$\color{red}{V_{\mathscr{M}}(\square Q\to\square P,v_1)=1}$$ $$\text{ iff }~\forall v_2\in\mathscr{W},(\mathscr{R}v_1v_2\to V_{\mathscr{M}}(Q,v_2)=0\lor V_{\mathscr{M}}(P,v_2)=1)$$ $3.$ put $2.1$ and $2.2$ together $$\color{blue}{V_{\mathscr{M}}(\square P\to\square Q,v_1)=1}\lor \color{red}{V_{\mathscr{M}}(\square Q\to\square P,v_1)=1}$$ $$\text{ iff }~\forall v_2\in\mathscr{W},(\mathscr{R}v_1v_2$$ $$\to \underbrace{V_{\mathscr{M}}(P,v_2)=0\lor V_{\mathscr{M}}(Q,v_2)=1\lor V_{\mathscr{M}}(Q,v_2)=0\lor V_{\mathscr{M}}(P,v_2)=1)}_{\text{tautology}}$$

$4.$ Substitute this tautology back to $(0)$ we get:

$$\forall v_1\in\mathscr{W}\big(\mathscr{R}wv_1\to(\forall v_2\in\mathscr{W},(\mathscr{R}v_1v_2\to\top))\big)$$

Which is also a tautology, hence proved.


Is this analysis correct $?$

Please tell me if there is any mistakes.

And how do I prove this with natural deduction $?$

Any help would be appreciated.