様相論理: 可能世界意味論(命題論理)

モデル$\M=\tuple{W,R,v}$と状態$w\in W$を任意にとり、$w\vDash\Box(\vphi\to\psi)$と$w\vDash\Box\vphi$を仮定する。

$w\vDash\Box\psi$を示すために、$wRw'$となる$w'\in W$を任意にとる。仮定より$w'\vDash\vphi\to\psi$と$w'\vDash\vphi$であり、これらより$w'\vDash\psi$である。$w'$の任意性より、$w\vDash\Box\psi$が示された。

$\Box(\varphi\lor\psi)\nvDash\Box\vphi\lor\Box\psi$のみ示す。なお、$\Box$の方の妥当性・非妥当性が示せれば、$\Diamond$の方は定義から導出できる。

命題変数$p,q\in\PV$をとって固定し、以下のように反例モデル$\M=\tuple{W,R,(v_w)_{w\in W}}$を定義する。

• $W=\qty{w_0,w_1,w_2}$
• $R=\qty{\tuple{w_0,w_1},\tuple{w_0,w_2}}$
• $v_{w_1}(p)=1,~v_{w_2}(q)=1$ (それ以外の場合、値は$0$)

付値の定義より$w_1\vDash p\lor q,~w_2\vDash p\lor q$となるので、$R$の定義より$w_0\vDash\Box(p\lor q)$である。一方で、$w_1\nvDash q$より$w_0\nvDash\Box q$であり、同様に$w_2\nvDash p$より$w_0\nvDash\Box p$なので、$w_0\nvDash\Box p\lor\Box q$となる。よってこの$\M$が反例モデルを与える。

$\vDash\vphi$を仮定すると、任意のモデル$\M$の任意の状態$w$で$w\vDash\vphi$である。改めてモデル$\M$とその状態$w$を任意にとると、$wRw'$となる任意の$w'$において、仮定より$w'\vDash\vphi$なので、$w\vDash\Box\vphi$である。よって$\vDash\Box\vphi$が成り立つ。

1つ目についてのみ証明を与える。$(\Rarr)$を示すために、$\F~(=\tuple{W,R})$の継続性を仮定する。$\F$上の付値$(v_w)_{w\in W}$と$w\in W$を任意にとり、$w\vDash\Box\vphi$を仮定する。このとき、継続性よりある$w'\in W$が存在して$wRw'$であり、これと仮定より$w'\vDash\vphi$が成り立つ。このような状態$w'$の存在より、$w\vDash\Diamond\vphi$が成り立つ。

次に、$(\Larr)$を対偶をとることで示す。そのために、$\F$が継続的でない、すなわち、ある$w\in W$が存在して、任意の$w'\in W$に対して$wRw'$とはならないと仮定する。このとき、付値$(v_w)_{w\in W}$を1つ、命題変数$p$を1つとると(任意でよい)、仮定より$w\vDash\Box p$かつ$w\nvDash\Diamond p$となるので、$w\nvDash\Box p\to\Diamond p$である。

$\mathbf{KT}$が$\mathbf{KD}$より強いことのみ示す。まず、$\mathbf{KT}$が$\mathbf{KD}$よりも弱くないこと(i.e., $\mathbf{KT}\supe\mathbf{KD}$)を示す。$\vDash_\mathbf{KD}\varphi$を仮定すると、フレームと公理の対応関係より、任意の継続的なフレーム$\F$において$\vDash^\F\varphi$である。ここで、反射的なフレームは継続的でもあるから、任意の反射的なフレーム$\F$において$\vDash^\F\varphi$となる。再びフレームと公理の対応関係より、$\vDash_\mathbf{KT}\varphi$が言える。

次に、$\mathbf{KT}$に含まれるが$\mathbf{KD}$には含まれない論理式の存在を示す。ある$p\in\PV$について(任意でよい)、$\Box p\to p$がそのような論理式であることを示そう。$\vDash_\mathbf{KT}\Box p\to p$は自明。$\nvDash_\mathbf{KD}\Box p\to p$を示すために、以下で定義されるモデル$\M=\tuple{W,R,(v_w)_{w\in W}}$を考える。

• $W=\qty{w_0,w_1}$
• $R=\qty{\tuple{w_0,w_1},\tuple{w_1,w_1}}$
• $v_{w_0}(p)=0, w_{w_1}(p)=1$ (それ以外の引数の場合、値は任意でよい)

このとき、$w_0\vDash\Box p$だが$w_0\nvDash p$なので、$w_0\nvDash\Box p\to p$である。このとき$\tuple{W,R}$は継続的であり、このフレーム上で$\Box p\to p$は妥当ではないので、フレームと公理の対応関係より、$\nvDash_\mathbf{KD}\Box p\to p$となる。

(5)のみ示す。以下では、普遍的なフレームと対応する論理のことを、$\mathbf{KU}$と呼ぶこととしよう。まず、普遍的なフレームは反射的かつユークリッド的なので、$\mathbf{S5}\sube\mathbf{KU}$は明らかである。

次に、$\mathbf{KU}\sube\mathbf{S5}$、すなわち、「任意の普遍的なフレーム$\F$で$\vDash^\F\varphi$ならば、$\vDash_\mathbf{S5}\varphi$」となることを示そう。ここでは対偶を示す。そのために、まず$\nvDash_\mathbf{S5}\varphi$を仮定する。(3)の結果を利用すると、$\nvDash_\mathbf{KT4B}\varphi$を得る。すなわち、あるモデル$\M=\tuple{W,R,(v_w)_{w\in W}}$と状態$w_0\in W$が存在して、以下が成り立つ。

• $\tuple{W,R}$は反射的・推移的・対称的 (i.e., $R$は$W$上の同値関係)
• $w_0\nvDash\varphi$

証明を続ける前に、直観的な説明をする。目下の目標は、$\M$を基に普遍的なフレームから成る反例モデルを構成することである。そのために、ここではモデル$\M$全体を$w_0$と($R$に関して)同値な元に制限する。すると、論理式の真偽を保存したまま、普遍的なフレームを得ることができる(下図参照)。

以下のようにモデル$\M'=\tuple{W',R',(v'_w)_{w\in W'}}$を定義する。ただし、$[w]$で$w$を代表元とする同値類を表す。

• $W'=[w_0]$
• $R'=W'\times W'$ (よって$\tuple{W',R'}$は普遍的なフレームである)
• 各$w\in W'(\sube W)$に対して、$v'_w(p) = v_w(p)$

次に、以下の主張が成り立つことを示す。

証明は論理式の構造に関する帰納法による。

• $\psi\equiv p\in\PV$の場合: 付値の定義より自明。
• $\psi\equiv\lnot\theta$の場合 ($\to$についても同様)
  $$ \begin{align*} \M,w\vDash\lnot\theta &\iff \M,w\nvDash\theta\\[5pt] &\iff \M',w\nvDash\theta\quad(\because\text{帰納法の仮定})\\[5pt] &\iff \M',w\vDash\lnot\theta \end{align*} $$
• $\psi\equiv\Box\theta$の場合
  $$ \begin{align*} \M,w\vDash\Box\theta &\iff \Forall w'\in W. wRw'\implies \M,w'\vDash\theta\\[5pt] &\iff \Forall w'\in[w_0].\M,w'\vDash\theta\quad(\because~w\in[w_0])\\[5pt] &\iff \Forall w'\in W'.\M',w'\vDash\theta\quad(\because\text{帰納法の仮定})\\[5pt] &\iff \Forall w'\in W'.wR'w'\implies \M,w'\vDash\theta\quad(\because\text{$\tuple{W',R'}$は普遍的})\\[5pt] &\iff \M',w\vDash\Box\theta \end{align*} $$

以上と$\M,w_0\nvDash\varphi$より、$\M',w_0\nvDash\varphi$となり、所期の結果を得た。

$(\Larr)$の向きについてのみ示す。対偶を示すために$\Gamma\nvDash_\Int\vphi$と仮定すると、以下を満たす(直観主義論理の)反例モデル$\M=\tuple{W,\leq,(v_w)_{w\in W}}$とその状態$w_0\in W$が存在する。

• $\Forall\psi\in\Gamma.w_0\vDash_\Int\psi$
• $w_0\nvDash_\Int\vphi$

このとき、$\leq$が擬順序(i.e., 反射的かつ推移的)であるから、$\M$は$\Sfour$のモデルでもある。このことに注意して、以下の主張の成立を示そう。

証明は論理式の構造に関する帰納法による。

• $\psi\equiv p\in\PV$の場合
  $$ \begin{align*} w\vDash_\Int p &\iff v_w(p)=1\\[5pt] &\iff w\vDash_\Sfour p\\[5pt] &\iff w\vDash_\Sfour\Box p \quad(\because~(\ast)) \end{align*} $$
  • $(\ast)$の部分について、$(\Rarr)$の向きは$v_w$の遺伝性より、$(\Larr)$の向きは公理(T)より成立することが分かる。
• $\psi\equiv\lnot\theta$の場合 (他の論理結合子の場合も同様なので割愛)
  $$ \begin{align*} w\vDash_\Int\lnot\theta &\iff \Forall w'\geq w.w'\nvDash_\Int\theta\\[5pt] &\iff \Forall w'\geq w.w'\nvDash_\Sfour\tau(\theta)\quad(\because~\text{帰納法の仮定})\\[5pt] &\iff \Forall w'\geq w.w'\vDash_\Sfour\lnot\tau(\theta)\\[5pt] &\iff w\vDash_\Sfour\Box\lnot\tau(\theta) \end{align*} $$

この主張より、$\M$が$\tau(\Gamma)$から$\tau(\vphi)$への(様相論理の)反例モデルになっていることが示された。