Curry–Howard対応(Curry–Howard correspondence)とは、直観主義命題論理の論理式を型と読むと、自然演繹の仮定にラベルをつけた導出と、直積型・直和型・空型を加えた単純型付き λ 計算の項が 1 対 1 に対応し、導出の遠回りの除去が項の簡約に対応する、という対応である。連言は直積、選言は直和、含意は関数型、矛盾は空型にあたる。型のつく項はすべて正規形をもち、閉じた正規項が導入の形であることから、無矛盾性と選言特性が従う。
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$ |
文脈 $\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$
要点:簡約の場所についての帰納法で、根で起きる $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)$ の証明. $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$
型のつく閉じた項(自由変数のない項)で正規形のものは、導入の項である。したがって次が成り立つ。
幹の先頭は自由変数なので、閉じた正規項は $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\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 |
| 自然演繹の木 | シークエント計算の導出 | 全単射 |
対応は命題論理の外へ延びる。二階の全称量化は 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アソシエイト)の紹介料で運営されています。 支援について / 寄付する