Peirceの法則(Peirce's law)とは、論理式 $((\varphi\to\psi)\to\varphi)\to\varphi$ の形の主張であり、含意だけで書かれた古典論理の恒真式である。直観主義論理では一般には証明できず、2 点の Kripke モデルや 3 元の Heyting 代数が反例を与える。直観主義論理にすべての実例を公理として加えると排中律や二重否定除去と同じ力をもち、含意だけの公理 $\alpha\to(\beta\to\alpha)$ と $(\alpha\to(\beta\to\gamma))\to((\alpha\to\beta)\to(\alpha\to\gamma))$ に加えると、含意だけの恒真式がすべて導出できる。
Peirce の法則(Peirce's law)は、論理式
$$
((\varphi\to\psi)\to\varphi)\to\varphi
$$
の形の主張である。否定も矛盾の記号も使わず、含意 $\to$ だけで書かれているのに、古典論理 では成り立ち、直観主義論理 では証明できない。古典論理と直観主義論理を分ける式としては 排中律 $\varphi\lor\lnot\varphi$ や二重否定除去 $\lnot\lnot\varphi\to\varphi$ が有名だが、これらは否定なしには書けない。Peirce の法則は、その差を含意だけで表す式である。
この記事では、Peirce の法則が恒真式であること、直観主義論理で証明できないこと、直観主義論理に加えると排中律と同じ力をもつことを示す。さらに、含意だけの公理系に加えると、含意だけで書かれた恒真式がすべて導出できるようになること(thm-peirce-implicational)を証明する。
論理式 $\varphi,\psi$ について、論理式
$$
((\varphi\to\psi)\to\varphi)\to\varphi
$$
を Peirce の法則 という。$\varphi,\psi$ に任意の論理式を入れた形全体を公理図式とみるときは、Peirce の法則の図式といい、個々の論理式をその実例という。
命題論理の論理式と体系は 直観主義論理 の記事のものを使う。命題変数と $\bot$ から $\land,\lor,\to$ で論理式を作り、$\lnot\varphi:=(\varphi\to\bot)$ とする。$\Gamma\vdash_{\mathrm I}\varphi$ は、同じ記事の定義「直観主義命題論理の公理系」の公理 1〜7 と前件肯定(MP)による導出があることを表す。公理 7 は $\bot\to\varphi$ である。
含意だけを扱うために、次の体系も使う。
命題変数から $\to$ だけで作った論理式を含意論理式という。公理図式
$$
\text{(K)}\ \ \alpha\to(\beta\to\alpha),\qquad\text{(S)}\ \ (\alpha\to(\beta\to\gamma))\to((\alpha\to\beta)\to(\alpha\to\gamma))
$$
($\alpha,\beta,\gamma$ は含意論理式)と MP からなる体系を $\mathbf P$ とする。$\mathbf P$ に Peirce の法則の図式($\varphi,\psi$ は含意論理式)を公理として加えた体系を $\mathbf P^{+}$ とする。導出可能性を $\vdash_{\mathbf P}$、$\vdash_{\mathbf P^{+}}$ と書く。
(K)・(S) は直観主義論理の公理 1・2 と同じ形なので、$\mathbf P$ の導出はそのまま $\vdash_{\mathrm I}$ の導出である。$\mathbf P$ と $\mathbf P^{+}$ は MP だけを規則にもち (K)・(S) をもつので、演繹定理 の定理「演繹定理」が成り立つ。すなわち $\Gamma\cup\{\alpha\}\vdash\beta\iff\Gamma\vdash\alpha\to\beta$ である。以下の導出は、これを使って「$\alpha$ を仮定して $\beta$ を導く」形で書く。
古典論理で $\varphi$ が偽なら、$\varphi\to\psi$ は $\psi$ によらず真である。したがって「$\varphi\to\psi$ から $\varphi$ が出る」という前件は、$\varphi$ が偽のときは「真から偽が出る」となって成り立たない。Peirce の法則はこの観察を述べている。「$\varphi$ が偽なら何でも言える」という仮定から $\varphi$ が出るなら、$\varphi$ は真だった、という背理法の形である。$\psi$ はどんな主張でもよい目印で、$\bot$ の代わりをしている。
$\mathrm{T},\mathrm{F}$ で真偽を書く。
| $p$ | $q$ | $p\to q$ | $(p\to q)\to p$ | $((p\to q)\to p)\to p$ |
|---|---|---|---|---|
| T | T | T | T | T |
| T | F | F | T | T |
| F | T | T | F | T |
| F | F | T | F | T |
よって Peirce の法則は恒真式である。一般の $\varphi,\psi$ についても、値が $p,q$ の値に置き換わるだけなので同じである。一方、前件だけの $(p\to q)\to p$ は恒真式でない(3・4 行目)。
世界 $w_0\le w_1$ の 2 点からなる Kripke意味論 のモデルで、$V(p)=\{w_1\}$、$V(q)=\emptyset$ とする。$w_1$ では $p$ が強制され $q$ が強制されないので、$w_0$ でも $w_1$ でも $p\to q$ は強制されない。よって $(p\to q)\to p$ は両方の世界で強制される(確かめるべき場合がない)。しかし $w_0$ は $p$ を強制しないので、$w_0\not\Vdash((p\to q)\to p)\to p$ である。
Kripke 意味論の健全性(Kripke意味論 の記事の定理「Kripke 意味論の健全性」)により、$((p\to q)\to p)\to p$ は $\vdash_{\mathrm I}$ で証明できない。この反例により、含意「恒真式ならば直観主義論理で証明できる」は成り立たない。
Heyting代数 $H=\{0<\tfrac12<1\}$ では、$a\Rightarrow b$ は $a\le b$ なら $1$、そうでなければ $b$ である。$p$ に $\tfrac12$、$q$ に $0$ を割り当てると、$\tfrac12\Rightarrow0=0$、$0\Rightarrow\tfrac12=1$、$1\Rightarrow\tfrac12=\tfrac12\ne1$ となる。Heyting 代数に関する健全性(直観主義論理 の記事の定理)から、ex-peirce-kripke と同じ結論が得られる。
Peirce の法則の図式が直観主義論理で証明できないといっても、すべての実例が証明できないわけではない。
| 論理式 | 恒真式か | $\vdash_{\mathrm I}$ で証明できるか |
|---|---|---|
| $((p\to q)\to p)\to p$ | はい | いいえ |
| $(\lnot p\to p)\to p$($\psi=\bot$ の場合) | はい | いいえ |
| $((p\to p)\to p)\to p$($\psi=\varphi$ の場合) | はい | はい |
| $((\lnot r\to q)\to\lnot r)\to\lnot r$($\varphi=\lnot r$ の場合) | はい | はい |
| $\lnot\lnot(((p\to q)\to p)\to p)$ | はい | はい |
| $(p\to q)\to p$ | いいえ | いいえ |
2 行目が証明できないことは、ex-peirce-kripke のモデルで $q$ を $\bot$ に替えた同じ計算で分かる。最後の行は恒真式でないので、健全性により証明できない。
公理 1〜7 に次のどれか 1 つの図式(すべての論理式 $\varphi,\psi$ について)を加えた体系は、どれも同じ論理式を証明する。
各図式の実例が、前の図式を加えた体系で導けることを示す。
1 ⇒ 2:$h:=(\varphi\to\psi)\to\varphi$ を仮定する。$\varphi\vdash_{\mathrm I}\varphi$ である。また $\lnot\varphi$ を仮定すると、$\varphi$ から $\bot$、公理 7 で $\psi$ が出るので $\lnot\varphi\vdash_{\mathrm I}\varphi\to\psi$ であり、$h$ と MP で $\varphi$ が出る。公理 6 $(\varphi\to\varphi)\to((\lnot\varphi\to\varphi)\to((\varphi\lor\lnot\varphi)\to\varphi))$ と排中律で、$h$ から $\varphi$ が出る。
2 ⇒ 3:2 で $\psi:=\bot$ とする。
3 ⇒ 4:$\lnot\lnot\varphi$ と $\lnot\varphi$ を仮定すると $\bot$、公理 7 で $\varphi$ が出るので、$\lnot\lnot\varphi\vdash_{\mathrm I}\lnot\varphi\to\varphi$ である。3 と MP で $\lnot\lnot\varphi$ から $\varphi$ が出る。
4 ⇒ 1:$\theta:=\varphi\lor\lnot\varphi$ とおく。$\lnot\theta$ と $\varphi$ を仮定すると、公理 5 で $\theta$ が出て $\bot$ となるので、$\lnot\theta\vdash_{\mathrm I}\lnot\varphi$ である。公理 5 で $\lnot\varphi$ から $\theta$ が出るので $\lnot\theta\vdash_{\mathrm I}\bot$、すなわち $\vdash_{\mathrm I}\lnot\lnot\theta$ である。4 で $\theta$ が出る。
最後の主張は、公理 1〜7 に 1 を加えた体系が古典論理であること(直観主義論理 の記事)による。$\square$
3 は Peirce の法則の $\psi$ を $\bot$ に固定したものだが、それでも図式としては全体と同じ力をもつ。一方、「図式として」は外せない。
実数直線の開集合の Heyting代数 で、$p$ に $U=(-\infty,0)$ を割り当てる。$\lnot U=(0,\infty)$ であり、$\lnot U\Rightarrow U=\operatorname{int}((-\infty,0]\cup U)=U$ なので、$(\lnot p\to p)\to p$ の値は $U\Rightarrow U=\mathbb R$ である。一方、$p\lor\lnot p$ の値は $\mathbb R\setminus\{0\}$ である。$(\lnot p\to p)\to p\vdash_{\mathrm I}p\lor\lnot p$ なら、直観主義論理 の記事の命題「演繹定理」により $((\lnot p\to p)\to p)\to(p\lor\lnot p)$ が証明でき、値は $\mathbb R$ のはずだが、実際の値は $\mathbb R\setminus\{0\}$ である。1 つの実例は、同じ $p$ についての排中律さえ導かない。
すべての $\varphi,\psi$ について、$P:=((\varphi\to\psi)\to\varphi)\to\varphi$ とおくと $\vdash_{\mathrm I}\lnot\lnot P$ である。
$\lnot P$ を仮定して $\bot$ を導く。$\varphi$ を仮定すると、公理 1 で $P$ が出て $\bot$ となるので、$\lnot\varphi$ が導ける。すると $\varphi$ の仮定から $\bot$、公理 7 で $\psi$ が出るので、$\varphi\to\psi$ が導ける。ここで $h:=(\varphi\to\psi)\to\varphi$ を仮定すると、MP で $\varphi$ が出る。よって $h\to\varphi$ すなわち $P$ が導け、$\lnot P$ と合わせて $\bot$ となる。$\square$
これは Glivenkoの定理 の特別な場合である。
$\bot$ のない体系 $\mathbf P$ では、排中律も二重否定除去も書けない。それでも Peirce の法則は書けて、古典論理の含意の部分を過不足なく与える(thm-peirce-implicational)。
$\lnot$ がないので、証明では 1 つの論理式を $\bot$ の代わりに使う。論理式 $c$ を固定し、$A^{\ast}:=(A\to c)\to c$ と書く。これは「$c$ を偽の代わりにした」二重否定である。
$p_1,\dots,p_n$ を命題変数、$c$ を含意論理式、$v$ を $p_1,\dots,p_n$ の付値とし、$\Gamma_v$ を、$v(p_i)=\mathrm T$ の $i$ について $p_i$、$v(p_i)=\mathrm F$ の $i$ について $p_i\to c$ を集めた集合とする。$p_1,\dots,p_n$ から作った含意論理式 $A$ について、
$A=p_i$ のとき:$v(p_i)=\mathrm T$ なら、$p_i$ と $p_i\to c$ から $c$ が出るので $p_i\vdash p_i^{\ast}$ である。$v(p_i)=\mathrm F$ なら $p_i\to c\in\Gamma_v$ である。
$A=B\to C$ のとき:次の 3 つの場合のどれかになる。
$v(C)=\mathrm T$ の場合($v(A)=\mathrm T$)。帰納法の仮定で $\Gamma_v\vdash(C\to c)\to c$ である。$(B\to C)\to c$ を仮定する。$C$ を仮定すると (K) で $B\to C$ が出て $c$ が出るので、$C\to c$ が導ける。よって $c$ が出る。したがって $\Gamma_v\vdash A^{\ast}$ である。
$v(B)=\mathrm T$、$v(C)=\mathrm F$ の場合($v(A)=\mathrm F$)。帰納法の仮定で $\Gamma_v\vdash(B\to c)\to c$、$\Gamma_v\vdash C\to c$ である。$B\to C$ を仮定すると、$C\to c$ と合わせて $B\to c$ が導ける。よって $c$ が出る。したがって $\Gamma_v\vdash A\to c$ である。
$v(B)=\mathrm F$ の場合($v(A)=\mathrm T$)。帰納法の仮定で $\Gamma_v\vdash B\to c$ である。$h:=(B\to C)\to c$ を仮定する。さらに $c\to C$ を仮定すると、$B\to c$ と合わせて $B\to C$ が導け、$h$ から $c$ が出る。よって $\Gamma_v,h\vdash(c\to C)\to c$ である。Peirce の法則の実例 $((c\to C)\to c)\to c$ と MP で $c$ が出る。したがって $\Gamma_v\vdash A^{\ast}$ である。$\square$
Peirce の法則を使うのは最後の場合だけである。そこでは $B$ が偽なので本来は $B\to C$ を導きたいが、$B$ から得られるのは $c$ までで、$c$ から $C$ へ進む手段がない。Peirce の法則は、この不足を「$c\to C$ を仮定してよい」という形で補う。
含意論理式 $\varphi$ について、$\varphi$ が恒真式であることと $\vdash_{\mathbf P^{+}}\varphi$ は同値である。一方、$\mathbf P$ だけではそうならない。Peirce の法則の実例 $((p\to q)\to p)\to p$ は恒真式だが、$\vdash_{\mathbf P}$ で導出できない。
(K)・(S)・Peirce の法則はすべて恒真式で、MP は恒真式を保つから、$\vdash_{\mathbf P^{+}}\varphi$ なら $\varphi$ は恒真式である。最後の主張は、$\mathbf P$ の導出が $\vdash_{\mathrm I}$ の導出であることと ex-peirce-kripke から従う。
逆を示す。$\varphi$ を恒真式とし、現れる命題変数を $p_1,\dots,p_n$、$c:=\varphi$ とする。どの付値 $v$ でも $v(\varphi)=\mathrm T$ なので、lem-peirce-valuation により $\Gamma_v\vdash(\varphi\to\varphi)\to\varphi$ であり、$\vdash\varphi\to\varphi$ と MP で $\Gamma_v\vdash\varphi$ である。
次に仮定を 1 つずつ除く。$\Sigma$ を $p_1,\dots,p_k$ についての $\Gamma_v$ の形の集合とする($k< n$)。$\Sigma\cup\{p_{k+1}\}\vdash\varphi$ かつ $\Sigma\cup\{p_{k+1}\to\varphi\}\vdash\varphi$ なら、演繹定理により $\Sigma\vdash p_{k+1}\to\varphi$ かつ $\Sigma\vdash(p_{k+1}\to\varphi)\to\varphi$ なので、MP で $\Sigma\vdash\varphi$ である。$k=n-1$ から $k=0$ まで繰り返すと $\vdash_{\mathbf P^{+}}\varphi$ を得る。$\square$
Heyting 代数 $H$ について、次は同値である。
1 ⇒ 2:$c:=(a\Rightarrow b)\Rightarrow a$ とおき、$c\le a$ を示す。$a\land\lnot a=0\le b$ なので $\lnot a\le a\Rightarrow b$ である。よって $c\land\lnot a\le c\land(a\Rightarrow b)\le a$ であり、$c\land\lnot a\le a\land\lnot a=0$ となる。分配律と 1 から $c=c\land(a\lor\lnot a)=(c\land a)\lor(c\land\lnot a)=c\land a\le a$ である。
2 ⇒ 1:$x\in H$ について $a:=x\lor\lnot x$ とおく。$\lnot a=\lnot x\land\lnot\lnot x=0$ なので $\lnot a\Rightarrow a=1$ である。2 で $b=0$ とすると $(\lnot a\Rightarrow a)\Rightarrow a=1$、すなわち $1\Rightarrow a=a=1$ である。$\square$
Kripke フレーム $(W,\le)$ について、$W$ 上のすべての Kripke モデルで $((p\to q)\to p)\to p$ が妥当であることと、$\le$ が等号だけ($w\le w'$ なら $w=w'$)であることは同値である。
Kripke意味論 の記事の命題「上集合の Heyting 代数」により、強制は上に閉じた部分集合の Heyting 代数 $\operatorname{Up}(W)$ での値で読める。$p,q$ には任意の上に閉じた集合を割り当てられるので、妥当であることは $\operatorname{Up}(W)$ が thm-peirce-boolean の 2 を満たすこと、すなわち 1 を満たすことと同値である。
$\le$ が等号だけなら、すべての部分集合が上に閉じていて、$\lnot U=W\setminus U$ なので 1 が成り立つ。$w\le w'$、$w\ne w'$ なら、$U:=\{z\mid w'\le z\}$ について、半順序なので $w\notin U$ であり、$w$ の先に $w'\in U$ があるので $w\notin\lnot U$ である。よって 1 が成り立たない。$\square$
命題論理 の記事の定義「シーケント計算」の体系では、次のように導出できる(同記事の完全性の節でも同じ導出を文で述べている)。シーケント計算 の記事の $\mathbf{LK}$ では、弱化と縮約を補えば同じ流れになる。
$$
\begin{prooftree}
\AxiomC{$p\Rightarrow p,q$}
\UnaryInfC{$\Rightarrow p,\ p\to q$}
\AxiomC{$p\Rightarrow p$}
\BinaryInfC{$(p\to q)\to p\Rightarrow p$}
\UnaryInfC{$\Rightarrow((p\to q)\to p)\to p$}
\end{prooftree}
$$
左上の 2 行では、右辺に論理式が 2 つ並んでいる。結論の $p$ を残したまま $p\to q$ の導入に進むところに、この導出の要がある。
GLT89 第 3 章の対応では、$\to$ だけの型は含意の式、閉じた項はその証明にあたる。型 $((A\to B)\to A)\to A$ をもつ閉じた項は、単純型付き λ 計算にない。実際、型を 3 元の鎖 $H$ で解釈すると、項 $t$(自由変数 $x_i$ の型を $U_i$、$t$ の型を $T$ とする)について $\bigwedge_i[U_i]\le[T]$ が項の組み立てに沿って確かめられる。閉じた項の型の値は $1$ だが、この型の値は ex-peirce-chain の割り当てで $\tfrac12$ である。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| thm-peirce-equivalents の「図式として加える」 | 1 つの実例 $(\lnot p\to p)\to p$ | $p\lor\lnot p$ の導出(ex-peirce-one-instance) |
| thm-peirce-implicational の「Peirce の法則を加える」 | 体系 $\mathbf P$ と $((p\to q)\to p)\to p$ | 恒真式の導出 |
| thm-peirce-implicational の「含意論理式」 | $\bot$ を原子式として許した $\mathbf P^{+}$ と $\bot\to p$ | 恒真式の導出 |
| thm-peirce-boolean の「Boole 代数」 | 3 元の鎖 | Peirce の法則の値が $1$ |
3 行目を確かめる。$\bot$ を許した体系の導出で $\bot$ を新しい命題変数 $r$ に置き換えると、$\mathbf P^{+}$ の導出になる。$\bot\to p$ が導出できるなら $r\to p$ が導出でき、$r\to p$ は恒真式でないので thm-peirce-implicational に反する。$\bot$ を偽と読むときに必要な公理 7 が、$\mathbf P^{+}$ にはない。4 行目は ex-peirce-chain である。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する