Peirceの法則

同義語:パースの法則Peirce's law

概要

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))$ に加えると、含意だけの恒真式がすべて導出できる。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 命題論理, 直観主義論理, Kripke意味論

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)を証明する。

定義

Peirce の法則

論理式 $\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$
TTTTT
TFFTT
FTTFT
FFTFT

よって Peirce の法則は恒真式である。一般の $\varphi,\psi$ についても、値が $p,q$ の値に置き換わるだけなので同じである。一方、前件だけの $(p\to q)\to p$ は恒真式でない(3・4 行目)。

反例:2 点の Kripke モデル

世界 $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}$ で証明できない。この反例により、含意「恒真式ならば直観主義論理で証明できる」は成り立たない。

反例:3 元の鎖

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 の法則の図式が直観主義論理で証明できないといっても、すべての実例が証明できないわけではない。

直観主義論理で証明できる実例
  1. $\psi=\varphi$ のとき、$\vdash_{\mathrm I}((\varphi\to\varphi)\to\varphi)\to\varphi$ である。$\vdash_{\mathrm I}\varphi\to\varphi$ と前件から MP で $\varphi$ が出る。$\varphi$ が含意論理式なら、この導出は $\mathbf P$ の導出である。
  2. $\varphi=\lnot\chi$ のとき、$\vdash_{\mathrm I}((\lnot\chi\to\psi)\to\lnot\chi)\to\lnot\chi$ である。$h:=(\lnot\chi\to\psi)\to\lnot\chi$ と $\chi$ を仮定する。$\lnot\chi$ を仮定すると $\chi$ と合わせて $\bot$、公理 7 で $\psi$ が出るので、$\lnot\chi\to\psi$ が導ける。$h$ から $\lnot\chi$ が出て、$\chi$ と合わせて $\bot$ となる。よって $h\vdash_{\mathrm I}\chi\to\bot$ である。
  3. どの実例も、全体を $\lnot\lnot$ で包めば証明できる(prop-peirce-double-negation)。
論理式恒真式か$\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. $\varphi\lor\lnot\varphi$
  2. $((\varphi\to\psi)\to\varphi)\to\varphi$
  3. $(\lnot\varphi\to\varphi)\to\varphi$
  4. $\lnot\lnot\varphi\to\varphi$
    したがって、これらの体系はどれも古典論理である。
1 から順にまわす

各図式の実例が、前の図式を加えた体系で導けることを示す。
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$ に固定したものだが、それでも図式としては全体と同じ力をもつ。一方、「図式として」は外せない。

反例:1 つの実例だけでは足りない

実数直線の開集合の 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$ である。

否定の仮定から $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$ について、

  • $v(A)=\mathrm T$ ならば $\Gamma_v\vdash_{\mathbf P^{+}}A^{\ast}$、
  • $v(A)=\mathrm F$ ならば $\Gamma_v\vdash_{\mathbf P^{+}}A\to c$
    である。
$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 代数と Kripke フレーム

Boole 代数の特徴づけ

Heyting 代数 $H$ について、次は同値である。

  1. すべての $a\in H$ について $a\lor\lnot a=1$ である($H$ は Boole 代数である)。
  2. すべての $a,b\in H$ について $((a\Rightarrow b)\Rightarrow a)\Rightarrow a=1$ である。
分配律と $b=0$ の場合

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$

Peirce の法則が妥当なフレーム

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 である。

補足

  • 名前は Charles Sanders Peirce にちなむ。MBTZ25 §14.1 は真理値表で恒真式であることを確かめ、この名を挙げている。読みは「パース」である。
  • thm-peirce-implicational の $\mathbf P^{+}$ は、含意だけの Hilbert 流の体系(Hilbert流の証明体系)の 1 つである。完全性定理(命題論理) の例「Peirce の法則」は、$\lnot$ をもつ体系 $\mathbf H_0$ で同じ式が導出できることを述べている。上の定理は、$\lnot$ も $\bot$ も通らない導出があることを述べている。
  • lem-peirce-valuation は、完全性定理(命題論理) の記事の定理「恒真式の導出の構成」の型の議論を、$\lnot$ の代わりに $A\to c$ を使って行ったものである。

関連項目

参考文献

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する