レーブの定理

スマリヤンの決定不能の論理パズル(白揚社 2008年)」という本にレーブの定理がわかりやすく紹介されていたので、それを紹介したいと思います。

レーブの定理

任意の命題\hspace{1}k\hspace{1},\hspace{1}C\hspace{1}について、もし4型の推論者が\hspace{1}BC\supset C\hspace{1}\hspace{1}k\equiv (Bk\supset C)\hspace{1}を信じるならば、\hspace{1}C\hspace{1}を信じる。

ここで、\hspace{1}Bk\hspace{1}というのは、「命題\hspace{1}k\hspace{1}を信じている」という意味で、4型の推論者とは以下の推論規則に従う人です。

(A1a)\hspace{5}(p\equiv 1)\supset Bp

(A1b)\hspace{5}Bp\wedge B(p\supset q)\supset Bq

(A2)\hspace{10}B(Bp\wedge B(p\supset q)\supset Bq)

(A3)\hspace{10}Bp\supset BBp

(A4)\hspace{10}B(Bp\supset BBp)

証明する前に補題を2つほど示します。

補題

B(p\supset(q\supset r))\supset B(Bp\supset(Bq\supset Br))

証明 (1)\hspace{5}B(B(p\supset q)\supset (Bp\supset Bq) ) ∵(A2)と同値
   (2)\hspace{5}BB(p\supset q)\supset B(Bp\supset Bq) ∵(1),(A1b)より
   (3)\hspace{5}BB(p\supset (q\supset r) )\supset B(Bp\supset B(q\supset r) )
      ∵(2)の\hspace{1}q\hspace{1}\hspace{1}q\supset r\hspace{1}に置き換え
   (4)\hspace{5}B( (B(q\supset r)\supset (Bq\supset Br) )
     \supset ( (Bp\supset B(q\supset r) )\supset (Bp\supset (Bq\supset Br) ) ) )
      ∵(Y\supset Z)\supset( (X\supset Y)\supset(X\supset Z) ) XBp,YB(q\supset r),
       Z(Bq\supset Br)に置き換え
   (5)\hspace{5}B( (Bp\supset B(q\supset r) )\supset (Bp\supset (Bq\supset Br) ) ) ∵(1),(4),(A1b)より
   (6)\hspace{5}B(Bp\supset B(q\supset r) )\supset B(Bp\supset (Bq\supset Br) ) ∵(5),(A1b)より
   (7)\hspace{5}BB(p\supset (q\supset r))\supset B(Bp\supset (Bq\supset Br) ) ∵(3),(6)より
   (8)\hspace{5}B(p\supset(q\supset r))\supset BB(p\supset(q\supset r)) ∵(A3)より
    ∴\hspace{5}B(p\supset(q\supset r))\supset B(Bp\supset(Bq\supset Br)) ∵(7),(8)より
補題2(本では、補題1)

B(p\supset (Bp\supset q) )\supset B(Bp\supset Bq)

証明 (1)\hspace{5}B(p\supset (Bp\supset q) )\supset B(Bp\supset (BBp\supset Bq) ) ∵補題1より
   (2)\hspace{5}B(Bp\supset BBp) ∵(4)より
   (3)\hspace{5}B( (Bp\supset BBp)\supset ( (Bp\supset (BBp\supset Bq) )\supset (Bp\supset Bq) ) )
      ∵(X\supset Y)\supset ( (X\supset (Y\supset Z) )\supset (X\supset Z) )XBp,YBBp,
       ZBqに置き換え
   (4)\hspace{5}B( (Bp\supset (BBp\supset Bq) )\supset (Bp\supset Bq) ) ∵(2),(3),(A1b)より
    ∴B(p\supset (Bp\supset q) )\supset B(Bp\supset Bq) ∵(1),(4),(A1b)より

ではレーブの定理を証明します。

レーブの定理

B(BC\supset C)\wedge B(k\equiv (Bk\supset C))\supset BC

証明 (1)\hspace{5}B(k\equiv (Bk\supset C))\supset B(Bk\supset BC) ∵補題2より
   (2)\hspace{5}B( (Bk\supset BC\wedge BC\supset C)\supset (Bk\supset C))
      ∵( (X\supset Y)\wedge (Y\supset Z))\supset (X\supset Z)XBk,YBC,
       ZCに置き換え
   (3)\hspace{5}B(BC\supset C)\wedge B(k\equiv (Bk\supset C))\supset B(Bk\supset C) ∵(1),(2),(A1b)より
   (4)B(Bk\supset C)\wedge B( (Bk\supset C)\equiv k)\supset Bk ∵(A1b)より
   (5)Bk\supset BBk ∵(A3)より
   (6)BBk\wedge B(Bk\supset C)\supset BC ∵(A1b)より
    ∴B(BC\supset C)\wedge B(k\equiv (Bk\supset C))\supset BC ∵(3),(4),(5),(6)より

これで、レーブの定理が示せました。

実は、本はまだ半分までしか読んでないので、これがレーブの定理の全てなのかは分かりません。(まだ読んでないとこにも出てきていたので)

実際にはもっと詳しく書いてあるので、興味があったらぜひ読んでみてください。