Curry–Howard対応

同義語:Curry–Howard correspondenceCurry-Howard対応Curry–Howard同型Curry–Howard isomorphism命題は型propositions as types

概要

Curry–Howard対応(Curry–Howard correspondence)とは、直観主義命題論理の論理式を型と読むと、自然演繹の仮定にラベルをつけた導出と、直積型・直和型・空型を加えた単純型付き λ 計算の項が 1 対 1 に対応し、導出の遠回りの除去が項の簡約に対応する、という対応である。連言は直積、選言は直和、含意は関数型、矛盾は空型にあたる。型のつく項はすべて正規形をもち、閉じた正規項が導入の形であることから、無矛盾性と選言特性が従う。

$$\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}} $$

前提知識: 自然演繹, 直観主義論理, λ計算

Curry–Howard対応(Curry–Howard correspondence)は、直観主義命題論理の論理式を型と読むと、自然演繹 の仮定にラベルをつけた導出と、直積型・直和型・空型を加えた単純型付き λ 計算の項が 1 対 1 に対応し、導出の遠回りの除去が項の簡約に対応する、という対応である。
直観主義論理 の BHK 解釈では、$A\to B$ の証明は $A$ の証明を $B$ の証明に変える手続きであり、$A\land B$ の証明は $A$ の証明と $B$ の証明の対である。この読み方を形式化すると、論理式は型、証明は項、証明の簡単化は計算になる。
型理論 では含意だけの断片で、証明可能性と項の存在の同値を示した。この記事では $\land,\lor,\to,\bot$ をすべて含む体系で、導出そのものと項の全単射を与え、変換と簡約の対応を証明する。さらに、この対応を使って正規形の存在を完全に証明し、選言特性、部分論理式性、Peirce の法則が証明できないことを、項の形の計算から導く。

定義

論理式 を、命題変数 $p,q,\dots$ と $\bot$ から $\land,\lor,\to$ で帰納的に作る。$\lnot A$ は $A\to\bot$ の略とする。自然演繹 の $\lnot\mathrm I,\lnot\mathrm E$ は、この略記のもとで $\to\mathrm I,\to\mathrm E$ の特別な場合である。背理法 $\bot_{\mathrm C}$ は使わない。
文脈 $\Gamma$ は、相異なる変数 $x_1,\dots,x_n$ に論理式を割り当てた有限の宣言 $x_1{:}A_1,\dots,x_n{:}A_n$ である。

項と型付け

項 を次で帰納的に定める。
$$ M::=x\mid\langle M,M\rangle\mid\pi_1M\mid\pi_2M\mid\mathrm{inl}_BM\mid\mathrm{inr}_AM\mid\mathrm{case}(M;x.M;y.M)\mid\lambda x{:}A.\,M\mid MM\mid\mathrm{abort}_AM $$
$\mathrm{case}(M;x.P;y.Q)$ で $x$ は $P$ の中で、$y$ は $Q$ の中で束縛される。束縛変数の名前だけが違う項は同じものとみなす。$M[N/x]$ は、変数の捕獲を避けて自由な $x$ を $N$ に置き換えた項である。
型判断 $\Gamma\vdash M:A$ を次の規則で導かれるものとする($i=1,2$)。
$$ \dfrac{x{:}A\in\Gamma}{\Gamma\vdash x:A}\ {\scriptstyle\mathrm{hyp}}\qquad \dfrac{\Gamma\vdash M:A\quad\Gamma\vdash N:B}{\Gamma\vdash\langle M,N\rangle:A\land B}\ {\scriptstyle\land\mathrm I}\qquad \dfrac{\Gamma\vdash M:A_1\land A_2}{\Gamma\vdash\pi_iM:A_i}\ {\scriptstyle\land\mathrm E_i} $$
$$ \dfrac{\Gamma\vdash M:A}{\Gamma\vdash\mathrm{inl}_BM:A\lor B}\ {\scriptstyle\lor\mathrm I_1}\qquad \dfrac{\Gamma\vdash M:B}{\Gamma\vdash\mathrm{inr}_AM:A\lor B}\ {\scriptstyle\lor\mathrm I_2}\qquad \dfrac{\Gamma\vdash M:A\lor B\quad\Gamma,x{:}A\vdash P:C\quad\Gamma,y{:}B\vdash Q:C}{\Gamma\vdash\mathrm{case}(M;x.P;y.Q):C}\ {\scriptstyle\lor\mathrm E} $$
$$ \dfrac{\Gamma,x{:}A\vdash M:B}{\Gamma\vdash\lambda x{:}A.\,M:A\to B}\ {\scriptstyle\to\mathrm I}\qquad \dfrac{\Gamma\vdash M:A\to B\quad\Gamma\vdash N:A}{\Gamma\vdash MN:B}\ {\scriptstyle\to\mathrm E}\qquad \dfrac{\Gamma\vdash M:\bot}{\Gamma\vdash\mathrm{abort}_AM:A}\ {\scriptstyle\bot\mathrm E} $$
$\Gamma,x{:}A$ の $x$ は $\Gamma$ に現れないとする(束縛変数の名前を変えておく)。

ラベルつきの導出

$\Gamma\vdash A$ の導出 とは、def-ch-terms の規則から項を消した規則でできる、$\Gamma\vdash A$ を根とする木である。葉の規則 $\mathrm{hyp}$ には使う変数 $x$(ラベル)を記録し、$\to\mathrm I$ と $\lor\mathrm E$ には外すラベルを記録する。外されたラベルの名前だけが違う導出は同じものとみなす。

ラベルは 自然演繹 の $[A]^n$ の番号にあたり、同じラベルの葉が同じ仮定の束である(GLT89 §3.5、p. 19 の parcel)。$\Gamma\vdash A$ の導出があることと、$A$ が $\Gamma$ の論理式から直観主義論理で導出できることは同値である。
導出 $D$ に項 $t(D)$ を、次の表の対応で根から帰納的に定める。

論理型導入の項除去の項
仮定 $x$変数$x$
$A\land B$直積$\langle M,N\rangle$$\pi_1M,\ \pi_2M$
$A\lor B$直和$\mathrm{inl}_BM,\ \mathrm{inr}_AM$$\mathrm{case}(M;x.P;y.Q)$
$A\to B$関数型$\lambda x{:}A.\,M$$MN$
$\bot$空型なし$\mathrm{abort}_AM$
Curry–Howard対応

文脈 $\Gamma$ と論理式 $A$ を固定する。$D\mapsto t(D)$ は、$\Gamma\vdash A$ の導出全体から $\Gamma\vdash M:A$ となる項 $M$ の全体への全単射である。とくに、$A$ が $\Gamma$ の論理式から導出できることと、$\Gamma\vdash M:A$ となる項 $M$ があることは同値である。

項は導出を記録している

$\Gamma\vdash t(D):A$ は $D$ の帰納法で明らかである。各規則の型判断から項を消すと導出の規則になるからである。
逆を作る。まず 型の一意性 を項 $M$ の帰納法で示す:$\Gamma\vdash M:A$ かつ $\Gamma\vdash M:A'$ なら $A=A'$ で、$\Gamma\vdash M:A$ の型付けの導出はただ $1$ つである。項の形ごとに規則は $1$ つなので、最後の規則は $M$ で決まる。$M=x$ なら $\Gamma$ で決まる。$\langle M_1,M_2\rangle,\pi_iM_1$ なら帰納法の仮定による。$\mathrm{inl}_BM_1$ なら $M_1$ の型と添字 $B$ で決まり、$\mathrm{inr}_AM_1$ も同じである。$\lambda x{:}A_1.\,M_1$ なら注釈 $A_1$ と文脈 $\Gamma,x{:}A_1$ での $M_1$ の型で決まる。$M_1M_2$ なら $M_1$ の型 $C\to B$ が帰納法の仮定で決まり、前提の型も決まる。$\mathrm{case}(M_1;x.P;y.Q)$ なら $M_1$ の型 $C\lor C'$ が決まるので、枝の文脈と型が決まる。$\mathrm{abort}_AM_1$ なら添字で決まり、前提の型は $\bot$ である。
$\Gamma\vdash M:A$ の唯一の型付けの導出から項を消した導出を $d(M)$ とする。$t(d(M))=M$ は、導出の各規則に当てる項の構成が $M$ の構成そのものであることから分かる。$d(t(D))=D$ は、$D$ の項つきの版が $\Gamma\vdash t(D):A$ の型付けの導出であり、それが一意であることから分かる。導出が記録する情報(ラベル、$\land\mathrm E_i$ の $i$、$\lor\mathrm I$ の結論)は、項の変数、$\pi_i$、$\mathrm{inl}$ と添字にそのまま現れる。$\square$

この全単射が導出の木の情報を失わないのは、def-ch-derivation でラベルを記録し、$\mathrm{inl}_B$ などに添字をつけたからである(節「反例:条件を外すと成り立たないこと」)。

証明と項

$A,B,C$ を論理式とする。次の項は閉じた項で、右の論理式の証明である。

論理式項
$A\land B\to B\land A$$\lambda p{:}A\land B.\,\langle\pi_2p,\pi_1p\rangle$
$A\lor B\to B\lor A$$\lambda z{:}A\lor B.\,\mathrm{case}(z;x.\mathrm{inr}_Bx;y.\mathrm{inl}_Ay)$
$A\to\lnot\lnot A$$\lambda x{:}A.\,\lambda k{:}\lnot A.\,kx$
$\lnot(A\lor B)\to\lnot A\land\lnot B$$\lambda n{:}\lnot(A\lor B).\,\langle\lambda x{:}A.\,n(\mathrm{inl}_Bx),\ \lambda y{:}B.\,n(\mathrm{inr}_Ay)\rangle$
$\lnot\lnot\lnot A\to\lnot A$$\lambda f{:}\lnot\lnot\lnot A.\,\lambda x{:}A.\,f(\lambda k{:}\lnot A.\,kx)$

命題変数 $p$ について $\lnot\lnot p\to p$ の閉じた項はない。$\lnot\lnot p\to p$ が直観主義論理で証明できない(直観主義論理)ことと thm-ch-main による。

遠回りの除去と簡約

簡約

除去の枠 とは、穴 $\square$ を $1$ つもつ次の形の式である。
$$ E::=\square\,N\mid\pi_i\square\mid\mathrm{case}(\square;u.R;v.S)\mid\mathrm{abort}_D\square $$
簡約 $M\to M'$ を、項の中の $1$ か所を次の左辺から右辺に置き換える操作とする。左の列は、同じ置き換えを導出の上で述べたものである。$\to^*$ は $0$ 回以上の簡約である。

導出の遠回り項の簡約
$\to\mathrm I$ の直後の $\to\mathrm E$$(\lambda x{:}A.\,M)N\to M[N/x]$
$\land\mathrm I$ の直後の $\land\mathrm E_i$$\pi_i\langle M_1,M_2\rangle\to M_i$
$\lor\mathrm I_1$ の直後の $\lor\mathrm E$$\mathrm{case}(\mathrm{inl}_BN;x.P;y.Q)\to P[N/x]$
$\lor\mathrm I_2$ の直後の $\lor\mathrm E$$\mathrm{case}(\mathrm{inr}_AN;x.P;y.Q)\to Q[N/y]$
$\lor\mathrm E$ の結論が除去の主前提$E[\mathrm{case}(M;x.P;y.Q)]\to\mathrm{case}(M;x.E[P];y.E[Q])$
$\bot\mathrm E$ の結論が除去の主前提$E[\mathrm{abort}_CM]\to\mathrm{abort}_DM$

最後の $2$ 行を 交換変換 という(GLT89 §10.4、pp. 76–78、§10.6、pp. 79–80)。$x,y$ は $E$ に自由に現れないようにとり、最後の行の $D$ は $E[\mathrm{abort}_CM]$ の型である。簡約できない項を 正規形 という。

導出の側の置き換えは、次のとおりに読む。$D_1$ が文脈 $\Gamma,x{:}A$ の導出、$D_2$ が $\Gamma\vdash A$ の導出のとき、$D_1[D_2/x]$ は $D_1$ のラベル $x$ の葉をすべて $D_2$ に置き換えた $\Gamma$ の導出である。$\to\mathrm I$ の直後の $\to\mathrm E$ は、$D_1$ と $D_2$ から $D_1[D_2/x]$ への置き換えになる。これは 正規化定理(自然演繹) の定義「変換」に、ラベルを保って交換変換を足したものである。

代入と差し込み

$D_1$ が $\Gamma,x{:}A\vdash B$ の導出、$D_2$ が $\Gamma\vdash A$ の導出なら、$t(D_1[D_2/x])=t(D_1)[t(D_2)/x]$ である。とくに $\Gamma,x{:}A\vdash M:B$、$\Gamma\vdash N:A$ なら $\Gamma\vdash M[N/x]:B$ である。

導出の帰納法

要点:葉 $x$ で両辺は $t(D_2)$ になり、ほかの規則では帰納法の仮定を組み立て直すだけである。

詳しい証明を開く

$D_1$ の帰納法による。$D_1$ が葉 $x$ なら、両辺は $t(D_2)$ である。ほかの葉 $y$ なら両辺は $y$ である。規則が $\to\mathrm I$ や $\lor\mathrm E$ で、ラベル $y$ を外すなら、$y$ は $\Gamma,x$ に現れないようにとる。$D_2$ の文脈に $y{:}C$ を足した導出は同じ項をもつので、帰納法の仮定が使える。ほかの規則では項の構成と代入が可換である。後半は thm-ch-main で項を導出に移せばよい。$\square$

簡約の対応
  1. (主部簡約)$\Gamma\vdash M:A$、$M\to M'$ なら $\Gamma\vdash M':A$ である。
  2. $\Gamma\vdash A$ の導出 $D,D'$ について、$D$ が def-ch-reduction の左の列の $1$ か所の置き換えで $D'$ になることと、$t(D)\to t(D')$ は同値である。とくに、導出に遠回りがないことと $t(D)$ が正規形であることは同値である。
根での場合分け

要点:簡約の場所についての帰納法で、根で起きる $6$ 種類を確かめる。

詳しい証明を開く

1:簡約が真部分項で起きるなら、規則を組み立て直す。根で起きるとする。$(\lambda x{:}C.\,P)N$ は最後の $2$ 規則が $\to\mathrm I,\to\mathrm E$ なので、$\Gamma,x{:}C\vdash P:A$、$\Gamma\vdash N:C$ で、lem-ch-subst による。$\pi_i\langle M_1,M_2\rangle$ は前提の型である。$\mathrm{case}(\mathrm{inl}_BN;x.P;y.Q)$ は $\Gamma\vdash N:C$、$\Gamma,x{:}C\vdash P:A$ で、lem-ch-subst による。$\mathrm{inr}$ も同じである。$E[\mathrm{case}(M;x.P;y.Q)]:A$ なら、$\mathrm{case}$ の項の型を $C$ とすると、$P,Q$ の型も $C$ で、$\Gamma,x{:}C_1\vdash E[P]:A$($E$ の部分項に $x$ の宣言を足す)である。$\lor\mathrm E$ でまとめると型 $A$ である。$E[\mathrm{abort}_CM]\to\mathrm{abort}_AM$ は $\Gamma\vdash M:\bot$ による。

2:$t$ は全単射で部分導出を部分項に移す。根の置き換えが表の右に移ることは、$t$ の定義と lem-ch-subst による。$\square$

遠回りの計算

$a{:}A,\ b{:}B$ の文脈で、$A\land B$ の証明 $\langle a,b\rangle$ に ex-ch-terms の $A\land B\to B\land A$ の証明を適用すると、
$$ (\lambda p{:}A\land B.\,\langle\pi_2p,\pi_1p\rangle)\langle a,b\rangle\to\langle\pi_2\langle a,b\rangle,\pi_1\langle a,b\rangle\rangle\to\langle b,\pi_1\langle a,b\rangle\rangle\to\langle b,a\rangle $$
である。$1$ 歩目で仮定 $p$ の $2$ か所に $A\land B$ の導出が複製され、残りの $2$ 歩で作ってすぐ分解する対が消える。証明の簡単化が計算の実行になっている。

正規形の形

型のつく項の正規形は文法で書ける。

幹と正規項

幹 $S$ と 正規項 $N$ を、次で同時に帰納的に定める。
$$ S::=x\mid SN\mid\pi_iS,\qquad N::=S\mid\langle N,N\rangle\mid\mathrm{inl}_BN\mid\mathrm{inr}_AN\mid\lambda x{:}A.\,N\mid\mathrm{case}(S;x.N;y.N)\mid\mathrm{abort}_AS $$
幹の左端の変数を 先頭 という。先頭は幹全体の自由変数である。

正規形の特徴づけ

型のつく項が正規形であることと、def-ch-normal の正規項であることは同値である。

主前提の形を見る

正規項に簡約できる箇所がないことは、簡約の左辺の主前提が導入の項、$\mathrm{case}$、$\mathrm{abort}$ のどれかで、文法では幹しか主前提にならないことから分かる。逆に $M$ を型のつく正規形とする。$M$ が変数か導入の項なら、部分項についての帰納法でよい。$M=E[M_0]$($M_0$ が主前提)なら、$M_0$ は型のつく正規形で、$\mathrm{case}$・$\mathrm{abort}$ ではない(交換変換が使える)。導入の項でもない。型が合う導入の項なら遠回りになるからである。よって帰納法の仮定から $M_0$ は幹である。$\square$

正規化定理

$\Gamma\vdash M:A$ なら、$M\to^*N$ となる正規形 $N$ がある。

論理式の結合子の個数を $|C|$ と書く。証明は $|C|$ についての帰納法である。

型の大きさの帰納法

型のつく項だけを考える。thm-ch-reduction の 1 により簡約で型は変わらない。次の $2$ つを $n=|C|$ についての帰納法で示す。

  • $(\mathrm A_C)$ 型 $C$ の正規項 $M$ と、部分項がすべて正規項である除去の枠 $E$ について、$E[M]$ は正規形をもつ。
  • $(\mathrm S_C)$ 型 $C$ の正規項 $Q$ と、$\Gamma,x{:}C\vdash P:B$ の正規項 $P$ について、$P[Q/x]$ は正規形をもつ。$P$ が先頭 $x$ でない幹なら、その正規形は幹である。
    $|C'| < n$ の $(\mathrm A_{C'})$・$(\mathrm S_{C'})$ を仮定する。

$(\mathrm A_C)$ の証明. $M$ の大きさの帰納法で示す。$M$ が幹なら $E[M]$ は正規項である。$M=\lambda y{:}A.\,M_1$、$E=\square N$ なら $E[M]\to M_1[N/y]$ で、$|A| < n$ なので $(\mathrm S_A)$ が使える。$M=\langle M_1,M_2\rangle$、$E=\pi_i\square$ なら $E[M]\to M_i$ である。$M=\mathrm{inl}_BM_1$、$E=\mathrm{case}(\square;u.R;v.T)$ なら $E[M]\to R[M_1/u]$ で、$M_1$ の型の大きさは $n$ より小さいので $(\mathrm S)$ が使える。$\mathrm{inr}$ も同じである。
$M=\mathrm{case}(S;x.P;y.Q)$ なら $E[M]\to\mathrm{case}(S;x.E[P];y.E[Q])$ である。$P,Q$ は $M$ より小さく型は $C$ なので、帰納法の仮定から $E[P],E[Q]$ は正規形 $P',Q'$ をもつ。$\mathrm{case}(S;x.P';y.Q')$ は正規項である。$M=\mathrm{abort}_CS$ なら $E[M]\to\mathrm{abort}_DS$ は正規項である。
$(\mathrm S_C)$ の証明. $(\mathrm A_{C'})$ は $|C'|\le n$ のすべてで使える。$P$ の大きさの帰納法で示す。$P=x$ なら $P[Q/x]=Q$ で、$P$ が別の変数なら $P$ である。$P$ が導入の項なら、直下の部分項に帰納法の仮定を当てて組み立て直す。
残りは $P=E[S_0]$($S_0$ は幹、$E$ の部分項は正規項)である。帰納法の仮定から、$S_0[Q/x]$ と $E$ の部分項の代入はそれぞれ正規形 $S_0'$ と $E'$ の部分項をもつ。$P[Q/x]\to^*E'[S_0']$ である。$S_0$ の先頭が $x$ でなければ、$S_0'$ は幹なので $E'[S_0']$ は正規項で、$P$ が幹のときは幹である。$S_0$ の先頭が $x$ なら、幹の型は先頭の型の部分論理式なので、$S_0$ の型 $C_0$ は $C$ の部分論理式である。$|C_0|\le n$ なので $(\mathrm A_{C_0})$ から $E'[S_0']$ は正規形をもつ。
結論. $M$ の大きさの帰納法で定理を示す。$M$ が変数か導入の項なら部分項の正規形で組み立てる。$M=E[M_0]$ なら、$M_0$ と $E$ の部分項を正規形に簡約し、lem-ch-normal と $(\mathrm A)$ を当てる。$\square$

正規形の一意性は Church–Rosser の性質から、すべての簡約列が止まることは強正規化から従う(GLT89 §10.5、pp. 78–79)。この記事では証明しない。含意だけの断片の強正規化は 強正規化定理 で扱う。

項の形から分かること

部分論理式性

$M$ が正規形で $\Gamma\vdash M:A$ なら、$M$ のどの部分項の型も、$\Gamma$ に現れる論理式の部分論理式か $A$ の部分論理式である。

文法の帰納法

$\mathrm{Sub}$ を部分論理式の全体を返す写像とする。lem-ch-normal により $M$ は正規項である。幹 $S$ の部分項の型が $\mathrm{Sub}(\Gamma)$ に属すること、一般の正規項の部分項の型が $\mathrm{Sub}(\Gamma)\cup\mathrm{Sub}(A)$ に属することを同時に帰納法で示す。
変数は明らかである。幹 $SN$ では $S$ の型 $C\to D$ が $\mathrm{Sub}(\Gamma)$ に属するので $C$ も属し、$N$ に帰納法の仮定を当てると部分項の型は $\mathrm{Sub}(\Gamma)\cup\mathrm{Sub}(C)=\mathrm{Sub}(\Gamma)$ に属する。$\pi_iS$ も同じである。導入の項は、直下の部分項の型が $A$ の部分論理式で、$\lambda x{:}A_1.\,N$ の文脈に足す $A_1$ も $A$ の部分論理式である。$\mathrm{case}(S;x.P;y.Q)$ では $S$ の型が $\mathrm{Sub}(\Gamma)$ に属するので、枝で足す文脈の型も属し、$P,Q$ の型は $A$ である。$\mathrm{abort}_AS$ も同じである。$\square$

閉じた正規項と選言特性

型のつく閉じた項(自由変数のない項)で正規形のものは、導入の項である。したがって次が成り立つ。

  1. (無矛盾性)$\vdash M:\bot$ となる項はなく、命題変数 $p$ についても $\vdash M:p$ となる項はない。
  2. (選言特性)$A\lor B$ が証明可能なら、$A$ か $B$ が証明可能である。
幹には自由変数がある

幹の先頭は自由変数なので、閉じた正規項は $S$、$\mathrm{case}(S;\dots)$、$\mathrm{abort}_AS$ の形ではない。lem-ch-normal により導入の項である。
1:$\vdash M:\bot$ なら thm-ch-normalization と thm-ch-reduction により閉じた正規項の型が $\bot$ になるが、$\bot$ と $p$ の導入の項はない。2:$A\lor B$ の閉じた正規項は $\mathrm{inl}_BN$ か $\mathrm{inr}_AN$ で、$N$ が $A$ か $B$ の閉じた項である。thm-ch-main で導出に戻す。$\square$

def-ch-normal から、証明の個数を数えることもできる。

証明の数え上げ

命題変数 $p$ について、$p\to p\to p$ の閉じた正規項はちょうど $\lambda x{:}p.\,\lambda y{:}p.\,x$ と $\lambda x{:}p.\,\lambda y{:}p.\,y$ の $2$ 個である。導入の項は $\lambda x{:}p.\,N$ の形で、$x{:}p$ のもとの型 $p\to p$ の正規項 $N$ は、型 $p\to p$ の幹がないので $\lambda y{:}p.\,N'$ で、$N'$ は型 $p$ の幹 $x$ か $y$ である。$\lor,\bot$ の型の幹がないので、$\mathrm{case}$ と $\mathrm{abort}$ は現れない。
$(p\to p)\to p\to p$ の閉じた正規項は、$\lambda f{:}p\to p.\,f$ と $\lambda f{:}p\to p.\,\lambda x{:}p.\,f^nx$($n\ge0$)である。型 $p$ の正規項は幹 $x$ か $fN$ だけだからである。後者は Church 数である(λ計算)。$1$ つの論理式の証明が無限個あり、それらは計算として異なる。

反例:証明できない論理式

$p,q$ を相異なる命題変数とする。

  • 排中律 $p\lor\lnot p$. 閉じた正規項は $\mathrm{inl}_{\lnot p}N$ か $\mathrm{inr}_pN$ である。前者なら $N$ は $p$ の閉じた項で、cor-ch-canonical に反する。後者なら $N=\lambda x{:}p.\,N'$ で、$x{:}p\vdash N':\bot$ である。$\bot$ の導入の項はなく、幹は $x$ だけで型は $p$ である。$\mathrm{case}$ も $\mathrm{abort}$ も幹を要するが、$\lor$ や $\bot$ の型の幹がない。
  • Peirce の法則 $((p\to q)\to p)\to p$. 閉じた正規項は $\lambda f.\,N$ で、$N$ は型 $p$ の正規項である。$f$ から作れる幹の型は $(p\to q)\to p$ と $p$ だけで、$\lor,\bot$ の型の幹はない。よって $N=fN_1$ で、$N_1:p\to q$ である。この型の幹はないので $N_1=\lambda x{:}p.\,N_2$ で、$N_2:q$ である。文脈 $f,x$ の幹の型は上と $p$ だけで $q$ の幹がなく、$q$ は命題変数なので導入の項もない。
    どちらも thm-ch-main により直観主義論理で証明できない。直観主義論理 では Heyting 代数のモデルで示すところを、ここでは正規形の探索で示している。

反例:条件を外すと成り立たないこと

外す条件反例成り立たなくなること
導出の仮定のラベル$p\to p\to p$ の $2$ つの項thm-ch-main の全射性
$\mathrm{inl}_B$ の添字 $B$添字のない $\mathrm{inl}\,x$型の一意性
交換変換下の $\pi_1\mathrm{case}(\dots)$thm-ch-subformula
型がつくこと型のない $\Omega$thm-ch-normalization
規則が直観主義論理のもの定数 $\mathrm{em}_A:A\lor\lnot A$ を足すcor-ch-canonical
自然演繹の木シークエント計算の導出全単射
反例の確かめ
  • ラベル. 自然演繹 の定義のように、仮定を外す規則が外せるものをすべて外すなら、$p\to p\to p$ の導出で内側の $\to\mathrm I$ が仮定 $p$ を全部外すので、$\lambda x{:}p.\,\lambda y{:}p.\,x$ にあたる導出は書けず、$2$ つの項のうち $\lambda x{:}p.\,\lambda y{:}p.\,y$ にあたる導出だけが残る。
  • 添字. 文脈 $x{:}A$ で $\mathrm{inl}\,x$ は任意の $B$ について型 $A\lor B$ をもつので、項から導出が決まらない。
  • 交換変換. 文脈 $z{:}p\lor p$ で $\pi_1\mathrm{case}(z;x.\langle x,x\rangle;y.\langle y,y\rangle)$ の型は $p$ である。交換変換がないと簡約できないが、部分項の型 $p\land p$ は $p\lor p$ の部分論理式でも $p$ の部分論理式でもない(GLT89 §10.3.2、p. 76)。交換変換を使うと $\mathrm{case}(z;x.x;y.y)$ になる。
  • 型. $\Omega=(\lambda x.\,xx)(\lambda x.\,xx)$ は $\Omega$ に簡約されるだけである(型理論)。
  • 排中律の定数. $\mathrm{em}_p$ は閉じた正規形で、$\mathrm{inl}$ でも $\mathrm{inr}$ でもない。
  • シークエント計算. $x{:}p\land q,\ y{:}r\land s\vdash p\land r$ で左の $\land$ の規則を当てる順序は $2$ 通りあるが、どちらも項は $\langle\pi_1x,\pi_1y\rangle$ である。同じ証明の書き方が多いので、そのままでは項と $1$ 対 $1$ にならない(GLT89 p. 28)。

量化記号と他の対応

対応は命題論理の外へ延びる。二階の全称量化は System F の型の抽象と適用に対応し、導入規則の変数の条件が型の抽象の条件に対応する(GLT89 §11.6、p. 93)。依存積型 $\Pi$ と依存和型 $\Sigma$ は一階の $\forall,\exists$ に対応し(UFP13 §1.11、pp. 41–46)、Martin-Löf型理論 はこの見方を基礎にしている。対応の意味は両者の違いにある。関数の側には計算という見方があり、証明の側には論理の対称性がある(GLT89 §3.6、pp. 20–21)。

文献

型と命題の対応は Howard による(GLT89 p. 14、文献 p. 162)。$\land,\to$ の対応は GLT89 第 3 章、$\lor,\bot$ の項と交換変換は同書第 10 章に従う。この記事の正規化定理の証明は、正規項への代入についての型の帰納法である。

関連項目

参考文献

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