直観主義論理: 可能世界意味論(命題論理)

公開日: 2022/09/08

最終更新: 2023/05/07

この記事では、直観主義論理に対する意味論のうち、可能世界意味論(possible world semantics) ないし クリプキ意味論(Kripke semantics) と呼ばれるものを紹介する。

なお以下では、命題変数の加算無限集合$\PV$が与えられているものとし、(命題)論理式の集合$\Fml$を以下のように帰納的に定める。

  • $\top,\bot\in\Fml$
  • $\Forall p\in\PV. p\in\Fml$
  • $\vphi,\psi\in\Fml\implies \vphi\land\psi, \vphi\lor\psi, \vphi\to\psi\in\Fml$

また、$\lnot \vphi \defeq \vphi\to\bot$とする。

非形式的な説明

直観主義論理(intuitionistic logic) の1つの特徴は、排中律($\vphi\lor\lnot\vphi$)が一般には成立しないことである。一方で、これは「真でも偽でもない命題が存在する」「真・偽に加えて第3の真理値を導入する」ということではない。実際、直観主義論理は3値論理としては特徴づけられない1。

このような一見奇妙な振る舞いは、「真である」という概念の捉え方に起因する。直観主義は「私たちの認識から独立した真理」という見方を批判し、「$\vphi$が真である」と言うためには、$\vphi$が真であることの証明が実際に構成できなければならないと主張する。

この観点からすると排中律が成り立たないのは自然なことである。なぜなら、数学の未解決問題のように、まだ肯定的な証明も否定的な証明も得られていない命題が存在するからである。やや紛らわしいかもしれないが、「偽である(真とはいえない)」と「否定が真である」は等価ではないということになる。

以上のような立場のもとでは、論理結合子の意味は古典論理とは異なった形で解釈されることになる。非形式的な説明としてしばしば引き合いに出されるのは、以下の BHK解釈(BHK interpretation) である。これは、各論理結合子の「証明が得られる」とはどういうことかを説明している。

定義. BHK解釈
  • $\bot$の証明は存在しない
  • $\vphi_1\land\vphi_2$の証明は、$\vphi_1$の証明と$\vphi_2$の証明の組である
  • $\vphi_1\lor\vphi_2$の証明は、$i\in\qty{1,2}$と$\vphi_i$の証明の組である
  • $\vphi_1\to\vphi_2$の証明は、$\vphi_1$の任意の証明を$\vphi_2$の証明へと変換する(実効的な)手続きである

そしてこのBHK解釈を反映しているのが、本ページで説明する 可能世界意味論 である。このモデルにおいては、命題の真偽は絶対的に決まるのではなく、1つ1つの「状態」において決まる。 そして、状態と状態の間の遷移関係を「時間の経過」のように捉え、遷移とともに真である(証明が得られた)命題が増えていくようにする。ちょうどこれは、数学者が時間の経過の中で証明を行い、だんだんと数学的知識を増やしていくような様子をモデル化しているといえる。

定義

まず、状態とその間の関係をフレームとして定義する。

定義. フレーム

直観主義命題論理の フレーム(frame) を、以下から成る組$\tuple{W, \leq}$のこととする。

  • $W$: 非空な集合
  • $\leq$: $W$上の擬順序

$W$の元のことを 状態(state) ないし 可能世界(possible world) という。$\leq$のことを 到達可能性関係(accessibility relation) という。

次に、古典命題論理と同様に、各命題変数の真偽を付値によって与える。ただし、付値は各状態に対して定義される。

定義. モデル

直観主義命題論理の モデル(model) を、フレームに以下を加えた組$\tuple{W,\leq,(v_w)_{w\in W}}$のこととする2。

  • $v_w:\PV\to\qty{0,1}$であって、以下の条件を満たすもの
$$ \Forall w, w'\in W.~w\leq w'\implies (\Forall p\in\PV. v_w(p)=1\implies v_{w'}(p)=1) $$

各$v_w$のことを 付値(valuation) といい、この条件のことを 遺伝性(heredity) または単調性(monotonicity)という。

遺伝性の条件は、「ある状態で命題が真と分かれば(= 証明が得られれば)、その後の状態でも真であると分かっていることに変わりはない」ことを反映していると解釈できる。なお後述するが、この性質は一般の論理式に拡張できる。

次に、命題変数に対して定義された真理値を論理式全体に拡張し、「モデル$\M$の状態$w$で論理式$\vphi$が真である」という関係を定義する。含意$\to$に関する定義が特徴的である。

定義. 充足関係

モデル$\M=\tuple{W,\leq,v}$と状態$w\in W$に対して、論理式$\vphi$の充足関係$\M,w\vDash\vphi$を以下のように帰納的に定める3。

  • $p\in\PV$:$\M,w\vDash p\defiff v_w(p)=1$
  • $\M,w\vDash\top$
  • $\M,w\nvDash\bot$
  • $\M,w\vDash\vphi\land\psi \defiff \M,w\vDash\vphi \And \M,w\vDash\psi$
  • $\M,w\vDash\vphi\lor\psi \defiff \M,w\vDash\vphi \Or \M,w\vDash\psi$
  • $\M,w\vDash\vphi\to\psi \defiff \Forall w'\geq w.~\M,w'\vDash\vphi\implies\M,w'\vDash\psi$

このとき($\M$において)$w$で$\vphi$が真であるという。モデルが明らかな場合は$\M$を省略して$w\vDash\vphi$と書く。

また、論理式の集合$\Gamma\sube\Fml$に対して、

$$ w\vDash\Gamma\defiff\Forall \vphi\in\Gamma.w\vDash\vphi $$

なお、否定は$\vphi\to\bot$として定義されていたので、帰結関係は次のように定まる ($w\nvDash\vphi$との違いに注意)。

$$ w\vDash\lnot\vphi \iff \Forall w'\geq w.~w'\nvDash\vphi $$
$\to$に関する定義の「任意の$w'\geq w$となる状態$w'$で...」という全称量化は、冒頭の説明のBHK解釈を反映したものである。BHK解釈によれば、「$\vphi\to\psi$が真である」と言えるためには、「$\vphi$の証明が与えられたら、$\psi$の証明を構成するような手続き」が構成できていなければならない。そして$\vphi$の証明はどのタイミングで与えられても良いはずなので、「この先の任意の状態で...」という量化をすることになる。

以下では、フレームを下図のように有向グラフで表し、各状態で論理式が真なら$+$、偽なら$-$を付けて表す。関係$\leq$を表す辺のうち、対称性・推移性により必要となるものは適宜省略する。

$$ \begin{xy} (0,0) *+{w_1}*\frm{o}="w1", (0,10) *{-\vphi}, (30,0) *+{w_2}*\frm{o}="w2", (30,10) *{+\vphi}, (60,0) *+{w_3}*\frm{o}="w3", (60,10) *{+\vphi}, \ar^{\leq} "w1";"w2", \ar^{\leq} "w2";"w3" \end{xy} $$

最後に、推論の妥当性を、任意のモデルにおいて前提から結論に充足関係が保存されることとして定義する。

定義. 妥当性

$\Gamma\cup\qty{\vphi}\sube\Fml$とする。$\Gamma$から$\vphi$への推論が 妥当である(valid) ことを、任意のモデル$\M=\tuple{W,\leq,(v_w)_{w\in W}}$と状態$w\in W$に対して$w\vDash\Gamma$ならば$w\vDash\vphi$であることと定義する。これを$\Gamma\vDash\vphi$と書く。

なお、前提を真・結論を偽とするような状態が存在するモデルのことを 反例モデル(counter model) という。すなわち、$\Gamma$から$\vphi$への推論に対する反例モデル$\M=\tuple{W,\leq,(v_w)_{w\in W}}$は以下を満たす。

$$ \Exists w\in W.~ w\vDash\Gamma \And w\nvDash\vphi $$

性質

基本的な性質

遺伝性の拡張

モデルの定義では、遺伝性の条件は命題変数の場合に限定されていた。この性質は論理式全体に拡張できる。

命題.

任意のモデル$\M=\tuple{W,\leq,(v_w)_{w\in W}}$, $w\leq w'$となる状態$w,w'\in W$に対して、

$$ \Forall \vphi\in\Fml.~w\vDash\vphi \implies w'\vDash\vphi $$

論理式の構成に関する帰納法で示す。$\to$についてのみ示す。

$w\vDash\vphi\to\psi$を仮定する。$w'\vDash\vphi\to\psi$を示すために、$w''\geq w'$となる$w''\in W$を任意にとる。このとき、推移性より$w''\geq w$でもあるから、仮定より$w''\vDash\vphi\implies w''\vDash\psi$となる。これと充足関係の定義より$w'\vDash\vphi\to\psi$となる。

※$\to$の場合には帰納法の仮定を使う必要がない。

選言特性

古典論理にはない性質として、次の 選言特性(disjunction property) がある4。

命題.
$$ \Forall\vphi_1,\vphi_2\in\Fml.~\vDash\vphi_1\lor\vphi_2 \implies {}\vDash\vphi_1\Or{}\vDash\vphi_2 $$

なお、これが古典論理では成り立たないことは、例えば適当な命題変数$p\in\PV$に対して$p\lor\lnot p$が反例になることから分かる。

概略のみ示す。$\nvDash\vphi_1$と$\nvDash\vphi_2$を仮定し、対偶を示す。仮定より、各$i=1,2$に対してモデル$\M_i=\tuple{W_i,\leq_i,(v_{w})_{w\in W_i}}$と状態$w_i\in W_i$が存在して、$\M_i,w_i\nvDash\vphi_i$となる。

反例モデルのフレームとして、$W_1$と$W_2$のそれぞれ$w_1,w_2$より後の部分だけ取り出し、それらに新たな最小元$w_0$を付け加えたようなものを考える(下図参照)。付値については、状態$w_0$では全て$0$とし、$W_i$の元に対しては各$\M_i$での値を適用する。これにより構成されたモデルを$\overline{\M}$とする。

$$ \begin{xy} (0,0) *+{w_0}*\frm{o}="w0", (-8,-9) *+{\small-\vphi_1}="p1to", (8,-9) *+{\small-\vphi_2}="p2to", (0,-18) *+{\small \therefore~-\vphi_1\lor\vphi_2}, (-30,20) *+{w_1}*\frm{o}="w1", (-41,20) *+{\small -\vphi_1}="p1from", (-30,35) *++++++++++++++++{}*\frm{o}, (-30,32) *+{\vdots}, (-25,31) *+{\small\leq}, (-30,47) *+{W_1}, (30,20) *+{w_2}*\frm{o}="w2", (41,20) *+{\small -\vphi_2}="p2from", (30,35) *++++++++++++++++{}*\frm{o}, (30,32) *+{\vdots}, (35,31) *+{\small\leq}, (30,47) *+{W_2}, \ar^{\leq} "w0";"w1" \ar_{\leq} "w0";"w2" \ar@{-->}@/_1.5pc/_{遺伝性} "p1from";"p1to" \ar@{-->}@/^1.5pc/^{遺伝性} "p2from";"p2to" \end{xy} $$

このとき、$\overline{\M}$においても$w_1$で$\vphi_1$が偽になり$w_2$で$\vphi_2$が偽になることが示せる。これと遺伝性(の対偶)より$w_0$では$\vphi_1,\vphi_2$がともに偽になるため、$\overline{\M},w_0\nvDash\vphi_1\lor\vphi_2$となり、$\overline{\M}$が反例モデルになることが分かる。

有限モデル性

妥当ではない推論に対しては反例モデルが存在するが、直観主義論理では任意の反例モデルを状態数が有限のモデルへと変換できる。このような性質を 有限モデル性(finite model property) という。

命題.

$\Gamma\nvDash\vphi$のとき、状態数が有限の反例モデルが存在する。

反例モデルの状態集合$W$に対して適当に同値類をとることで有限のモデルを構成する。詳細は割愛5。
系.

直観主義(命題)論理は決定可能である。すなわち、(前提が有限個の)任意の推論に対して、それが妥当か非妥当かを計算する実行的な手続きが存在する。

適当な証明論を用意することで妥当な推論を枚挙できるので、妥当な推論の判定は実効的に行える。非妥当な推論については、有限モデル性より、有限なモデルを順に枚挙していくことにより反例モデルが発見できる。

推論に関する性質

まず、直観主義論理は古典論理に含まれている。

命題.

(直観主義論理で)$\Gamma\vDash\vphi$のとき、$\Gamma$から$\vphi$への推論は古典論理でも妥当である。

適当な証明体系を与えれば簡単に示せるが、今回はモデルによる証明を与える。

対偶を示す。(概略) 前提を全て真・結論を偽にする古典論理の付値$v:\PV\to\qty{0,1}$が存在することを仮定する。状態1つだけ($w_0$)のフレームで付値を$v$により与えるようなモデル$\M$を考えると、$v\vDash\vphi \iff \M,w_0\vDash\vphi$となることを論理式の構成に関する帰納法で示せる。

なお、この証明と同様に考えると、状態$w$が「$w'\geq w$となる状態が自分以外にない」ような状況のとき(下図参照)、$w$上では充足関係が古典論理のように振舞うことが示せる(例えば$\M,w\vDash\vphi\lor\lnot\vphi$)。
$$ \begin{xy} (0,0) *+{\cdots}="cdots", (20,0) *+{w}*\frm{o}="w", \ar^{\leq} "cdots";"w" \ar@(ur,dr)^{\leq} "w";"w" \end{xy} $$

一方で、古典論理では妥当な推論の一部が実際に非妥当になることが確認できる。

命題. 非妥当な推論
  • 排中律: $\nvDash \vphi\lor\lnot\vphi$
  • 二重否定除去: $\lnot\lnot\vphi\nvDash\vphi$
  • パースの法則: $(\vphi\to\psi)\to\vphi\nvDash\vphi$
  • ド・モルガン(の片方): $\lnot(\vphi\land\psi)\nvDash\lnot\vphi\lor\lnot\psi$
  • 対偶: $\lnot\vphi\to\lnot\psi\nvDash \psi\to\vphi$

排中律についてのみ証明を与える。命題変数$p\in\PV$を1つとって固定し、以下のようなモデル$\M=\tuple{W,\leq,v}$を考える。

  • $W=\qty{w_1,w_2}$
  • $\leq{}=\qty{\tuple{w_1,w_1},\tuple{w_2,w_2},\tuple{w_1,w_2}}$ (確かに擬順序)
  • $v_{w_1}(p)=0,~v_{w_2}(p)=1$ (その他の引数のとき値は$0$)

付値の定義より$w_2\vDash p$であるから、これと$w_2\geq w_1$より$w_1\nvDash\lnot p$であることが分かる。よって、$w_1$では$p$も$\lnot p$も真ではないので、$w_1\nvDash p\lor\lnot p$であり、$\M$が反例モデルになることが分かる。

$$ \begin{xy} (0,0) *+{w_1}*\frm{o}="w1", (-12.5, 4) *{-p}, (-12.5, -4) *{-~\lnot p}, (30,0) *+{w_2}*\frm{o}="w2", (42.5, 0) *{+p}, \ar^{\leq} "w1";"w2" \end{xy} $$

フレームに関する性質

直観主義論理のフレームにもう少し強い制限を加えても、妥当な推論に影響はないことが知られている。このことを形式的に述べるために、まずフレーム上に制限した妥当性を定義する。

定義. フレーム上の妥当性

フレーム$F=\tuple{W,\leq}$上で$\Gamma$から$\vphi$への推論が妥当であることを、$F$上の任意の付値$(v_w)_{w\in W}$に対して以下が成り立つことと定義する(ただし$\M=\tuple{F,\leq,(v_w)_{w\in W}}$)。

$$ \Forall w\in W.~w\vDash\Gamma \implies w\vDash\vphi $$

これを$\Gamma\vDash_F\vphi$と書く。

命題. フレームの制限

$\Gamma\cup\qty{\vphi}\sube\Fml$とする。以下の3条件は同値である。

  1. 任意のフレーム$F$に対して$\Gamma\vDash_F\vphi$
  2. 最小元を持つ任意のフレーム$F$に対して$\Gamma\vDash_F\vphi$
  3. $\leq$が半順序となる任意のフレーム$F$に対して$\Gamma\vDash_F\vphi$

$(1)\Rarr(2),(1)\Rarr(3)$の向きは自明であり、この逆を示せば十分である。どちらも対偶をとり、反例モデルを適当に変換することで証明できる。概略のみ示す。

まず$\Not(1)$を仮定すると、あるモデル$\M=\tuple{W,\leq,v}$と状態$w_0\in W$が存在して、$w_0\vDash\Gamma,~w_0\nvDash\vphi$となる。このとき、新たなモデル$\M'$を次のように構成する。

  • $\Not(1)\Rarr\Not(2)$: 状態の集合を$W'=\qty{w\in W\mid w_0\leq w}$とし、$\leq,v$をこの集合上に制限してモデルを構成すれば、$w_0$が最小限になる。このとき$W'$上の状態では充足関係に変化がないことを論理式の構成に関する帰納法で確認すればよい。
  • $\Not(1)\Rarr\Not(3)$: $x\leq y\And x\geq y$により$W$上の同値関係$\sim$を定義し、$W/{\sim}$を状態の集合とする。関係と付値は自然に定義できる。あとは$\M,w\vDash\vphi\iff \M',[w]\vDash\vphi$を論理式の構成に関する帰納法で確認すればよい。

参考文献

Footnotes

  1. 証明の大枠は以下の通り: 相異なる4つの命題変数$p_1,p_2,p_3,p_4$に対して$\displaystyle\vphi=\bigvee_{1\leq i,j\leq 4,~i\neq j}p_i\leftrightarrow p_j$とする。直観主義論理が適当な3値論理として特徴づけられるならば、どれか2つの命題変数が同じ真理値を持つので(部屋割り論法)、$\vDash\vphi$となる。すると後述の選言特性により、ある$i,j$に対して$\vDash p_i\leftrightarrow p_j$が成り立つことになるが、これに対しては反例モデルが与えられるので、矛盾する。 ↩
  2. 付値を関数$V:W\to \mathrm{Pow}(\PV)$として定義し、$v_w(p)=1$の代わりに$p\in V(w)$とする流儀もある(実質的には同じ)。 ↩
  3. 付値$v$をそのまま拡張して、各論理式に$0,1$を割り当てるような関数を定義する流儀もある(実質的には同じ)。また、この関係のことを強制関係(forcing relation)と呼ぶ文献もある。 ↩
  4. 多くの文献では、選言特性は証明論的妥当性$\vdash$に関する定理として紹介される。健全かつ完全な証明体系であれば結局のところ同値なので些末な点ではあるが、厳密にはここで紹介しているのは「選言特性のモデル論的な書き方」ということになる。 ↩
  5. この手法は 濾過法(filtration) と呼ばれており、様相論理に対しても一般化できる。これに関する記事を前にMathlogで書いたので気になる方はそちらを参照のこと。 ↩