組合せ論理

同義語:組み合わせ論理combinatory logic

概要

組合せ論理(combinatory logic)とは、定数 $\mathsf S$・$\mathsf K$ と変数を適用だけで組み立てた項を、$\mathsf SPQR\to PR(QR)$ と $\mathsf KPQ\to P$ で書き換える体系で、Schönfinkel が導入した。束縛変数をもたないが、括弧抽象により変数を含む任意の式を変数の関数として表す項が作れ(関数完全性)、λ計算の β 簡約を真似できる。弱簡約は Church–Rosser の性質をもち、正規形はあればただ 1 つである。一方で ξ 規則や外延性は成り立たず、型をつけると Hilbert 流の含意の命題論理の導出と対応する。

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

前提知識: λ計算, Hilbert流の証明体系, 演繹定理

組合せ論理(combinatory logic)は、2 つの定数 $\mathsf S$・$\mathsf K$ と変数を、適用だけで組み立てた項と、
$$ \mathsf S PQR\ \to\ PR(QR),\qquad \mathsf K PQ\ \to\ P $$
という 2 つの書き換えからなる体系である。λ計算 と違って変数を束縛する操作(抽象 $\lambda x.$)をもたないので、束縛変数の名前の付け替えや代入のときの変数の捕獲を気にする必要がない。それでも、変数を含む任意の式を「変数の関数」として表す項が作れる(関数完全性)。M. Schönfinkel が 1920 年の講演で、論理の基本概念から変数を消すために導入した(Sch24 §1–§4、pp. 305–312)。
この記事では、項と弱簡約を定義し、次を証明する。括弧抽象による関数完全性(thm-cl-completeness)、弱簡約の Church–Rosser の定理(thm-cl-church-rosser)、λ計算との対応とずれ(prop-cl-to-lambda、prop-cl-from-lambda、反例の表)、型つきの組合せ論理と Hilbert 流の命題論理の対応(thm-cl-curry-howard)。

定義

変数の可算無限集合を固定し、$x,y,z,f$ などで表す。

組合せ論理の項

CL 項 を次の規則で帰納的に定める。

  1. 変数は CL 項である。定数 $\mathsf S$ と $\mathsf K$ は CL 項である(変数と定数を 原子 という)。
  2. $P,Q$ が CL 項なら、$(PQ)$ は CL 項である(適用)。
    適用は左に結合するとして括弧を省く($PQR$ は $((PQ)R)$)。$P$ に現れる変数の集合を $\mathrm{FV}(P)$ と書く。変数を含まない CL 項を 閉じた 項という。$P$ の中の変数 $x$ をすべて $N$ に置き換えた項を $P[N/x]$ と書く。
弱簡約

$\mathsf KPQ$ と $\mathsf SPQR$ の形の項を 基(redex)といい、それぞれ $P$ と $PR(QR)$ をその 縮約 という。弱簡約の一歩 $M\to_wM'$ を、次で生成される最小の関係とする。

  1. $\mathsf KPQ\to_wP$、$\mathsf SPQR\to_wPR(QR)$。
  2. $M\to_wM'$ なら $MN\to_wM'N$ かつ $NM\to_wNM'$。
    $\to_w$ を $0$ 回以上続けることを $\to_w^*$、$\to_w$ を含む最小の同値関係を $=_w$(弱同値)と書く。基を含まない項を 正規形 といい、$M\to_w^*N$ となる正規形 $N$ を $M$ の正規形という。

$\mathsf K$ は 2 つ目の引数を捨て、$\mathsf S$ は 3 つ目の引数を 2 つに複製してそれぞれに配る。Schönfinkel は $\mathsf K$ を 定数関数(Konstanzfunktion)$C$、$\mathsf S$ を 融合関数(Verschmelzungsfunktion)と呼んだ(Sch24 §3、pp. 309–311)。$\mathsf K$ や $\mathsf SP$・$\mathsf SPQ$ のように引数が足りない項は基ではない。

例

恒等と合成

$\mathsf I:=\mathsf{SKK}$ とおくと、任意の $P$ について
$$ \mathsf IP=\mathsf{SKK}P\ \to_w\ \mathsf KP(\mathsf KP)\ \to_w\ P $$
である(Sch24 p. 312 は同じ式 $I=SCC$ を挙げる)。$\mathsf B:=\mathsf S(\mathsf{KS})\mathsf K$ とおくと
$$ \mathsf BPQR=\mathsf S(\mathsf{KS})\mathsf KPQR\to_w\mathsf{KS}P(\mathsf KP)QR\to_w\mathsf S(\mathsf KP)QR\to_w\mathsf KPR(QR)\to_wP(QR) $$
であり、$\mathsf B$ は関数の合成を表す(Schönfinkel の合成関数 $Z$ と同じ項である。Sch24 p. 312)。

数の表し方

$f^0x:=x$、$f^{n+1}x:=f(f^nx)$ とする。$\overline0:=\mathsf{KI}$、$\overline{n+1}:=\mathsf{SB}\,\overline n$ とおくと、すべての $n$ と項 $F,X$ について $\overline nFX\to_w^*F^nX$ である。これは λ計算 の Church 数にあたる。

確かめを開く

$\mathsf{KI}FX\to_w\mathsf IX\to_w^*X$ であり、$\mathsf{SB}\,\overline nFX\to_w\mathsf BF(\overline nF)X\to_w^*F(\overline nFX)\to_w^*F(F^nX)$(最後は $n$ についての帰納法の仮定)である。

終わらない簡約

$\mathsf D:=\mathsf{SII}$ とおくと $\mathsf DP\to_w\mathsf IP(\mathsf IP)\to_w^*PP$ である。とくに $\mathsf{DD}$ は 1 歩以上の簡約で $\mathsf{DD}$ に戻るので、これを繰り返すと $\mathsf{DD}$ から始まる無限の簡約の列ができる。

主定理:関数完全性

λ計算の抽象 $\lambda x.\,M$ の代わりに、CL 項から変数 $x$ を消す操作を定める。

括弧抽象

CL 項 $M$ と変数 $x$ に対し、CL 項 $[x].M$ を $M$ についての再帰で次のように定める。

  1. $x\notin\mathrm{FV}(M)$ なら $[x].M:=\mathsf KM$。
  2. $[x].x:=\mathsf I\ (=\mathsf{SKK})$。
  3. $x\in\mathrm{FV}(PQ)$ なら $[x].(PQ):=\mathsf S([x].P)([x].Q)$。

3 つの場合は重ならず、すべての $M$ を尽くす($x\in\mathrm{FV}(M)$ の原子は $x$ だけである)。

関数完全性

任意の CL 項 $M,N$ と変数 $x$ について、次が成り立つ。

  1. $\mathrm{FV}([x].M)=\mathrm{FV}(M)\setminus\{x\}$。
  2. $([x].M)N\to_w^*M[N/x]$。
  3. $y\ne x$、$y\notin\mathrm{FV}(N)$ なら $([y].M)[N/x]=[y].(M[N/x])$。
    とくに、相異なる変数 $x_1,\dots,x_n$ と CL 項 $M$ に対し $F:=[x_1].([x_2].(\cdots([x_n].M)\cdots))$ とおくと、$\mathrm{FV}(F)=\mathrm{FV}(M)\setminus\{x_1,\dots,x_n\}$ であり、$x_1,\dots,x_n$ のどれも含まない任意の $N_1,\dots,N_n$ について $FN_1\cdots N_n\to_w^*M[N_1/x_1]\cdots[N_n/x_n]$ である。
定義の 3 つの場合に分ける

すべて $M$ についての帰納法で示す。
1:場合 1 では $\mathrm{FV}(\mathsf KM)=\mathrm{FV}(M)=\mathrm{FV}(M)\setminus\{x\}$、場合 2 では $\mathrm{FV}(\mathsf I)=\emptyset$。場合 3 では帰納法の仮定から $\mathrm{FV}(\mathsf S([x].P)([x].Q))=(\mathrm{FV}(P)\cup\mathrm{FV}(Q))\setminus\{x\}$。
2:場合 1 では $\mathsf KMN\to_wM=M[N/x]$($x\notin\mathrm{FV}(M)$ なので置き換えは何もしない)。場合 2 では $\mathsf IN\to_w^*N=x[N/x]$(ex-cl-basic)。場合 3 では、帰納法の仮定を $P$ と $Q$ に使って
$$ \mathsf S([x].P)([x].Q)N\ \to_w\ ([x].P)N\,(([x].Q)N)\ \to_w^*\ P[N/x]\,Q[N/x]=(PQ)[N/x] $$
である。ここで、$A\to_w^*A'$、$B\to_w^*B'$ なら $AB\to_w^*A'B'$ であること(定義の 2 を繰り返す)を使った。
3:$y\notin\mathrm{FV}(N)$ なので、$M$ の部分項 $R$ について「$y\in\mathrm{FV}(R)$」と「$y\in\mathrm{FV}(R[N/x])$」は同値である。したがって $M$ と $M[N/x]$ には定義の同じ場合が当てはまる。場合 1 では両辺とも $\mathsf K(M[N/x])$。場合 2($M=y$)では、$y\ne x$ なので両辺とも $\mathsf I$。場合 3 では帰納法の仮定から両辺とも $\mathsf S([y].P[N/x])([y].Q[N/x])$ である。
最後の主張:1 を $n$ 回使うと自由変数の式を得る。2 と 3 から、$n$ についての帰納法で示す。$G:=[x_2].(\cdots([x_n].M)\cdots)$ とおくと、2 により $FN_1\to_w^*G[N_1/x_1]$ であり、3 を繰り返すと $G[N_1/x_1]=[x_2].(\cdots([x_n].M[N_1/x_1])\cdots)$ である($x_j\ne x_1$、$x_j\notin\mathrm{FV}(N_1)$ を使った)。これに帰納法の仮定を使えばよい。$\square$

関数完全性の 2 は、λ計算の β 簡約 $(\lambda x.\,M)N\to_\beta M[N/x]$ を、$\mathsf S$・$\mathsf K$ の簡約で真似できることを意味する。Schönfinkel の目標は、束縛変数を含む論理式を変数を含まない記号の並びで書き直すことだった。彼は $\mathsf K$・$\mathsf S$ に両立しなさを表す関数 $U$ を加えれば、述語論理の式がすべて書き直せると述べ、例で手順を示した(Sch24 §5、pp. 312–313。完全な証明は与えていない)。関数完全性は、その書き直しの算術的な部分を支える性質である。

不動点

$\mathsf A:=[x].([y].\,y(xxy))$、$\Theta:=\mathsf{AA}$ とおく。任意の CL 項 $F$ について $\Theta F\to_w^*F(\Theta F)$ である。

関数完全性を 2 回使う

$\mathsf A$ は閉じた項なので、thm-cl-completeness の 2・3 を $x$ と $y$ について 1 回ずつ使う。

詳しい証明を開く

$\mathsf A$ は閉じた項である(thm-cl-completeness の 1)。thm-cl-completeness の 2 と 3($y\ne x$、$y\notin\mathrm{FV}(\mathsf A)=\emptyset$)により $\mathsf{AA}F\to_w^*\bigl([y].\,y(xxy)\bigr)[\mathsf A/x]\,F=\bigl([y].\,y(\mathsf{AA}y)\bigr)F\to_w^*F(\mathsf{AA}F)$ である。$\square$

$\Theta$ は λ計算の Turing の不動点結合子 $(\lambda xg.\,g(xxg))(\lambda xg.\,g(xxg))$(OLT26 §41.12、p. 629)を括弧抽象で写したものである。

主定理:Church–Rosser の定理

簡約の順序を変えても結果が食い違わないことを示す。λ計算 の記事の Church–Rosser の定理と同じく並行簡約を使うが、CL では代入の補題が要らず、証明が短くなる。

並行簡約と完全展開

並行簡約 $M\Rightarrow M'$ を、次の規則で生成される最小の関係とする。

  1. 原子 $a$ について $a\Rightarrow a$。
  2. $P\Rightarrow P'$、$Q\Rightarrow Q'$ なら $PQ\Rightarrow P'Q'$。
  3. $P\Rightarrow P'$ なら $\mathsf KPQ\Rightarrow P'$。
  4. $P\Rightarrow P'$、$Q\Rightarrow Q'$、$R\Rightarrow R'$ なら $\mathsf SPQR\Rightarrow P'R'(Q'R')$。
    項 $M$ の 完全展開 $M^\circ$ を、$M$ についての再帰で、原子では $a^\circ:=a$、$(\mathsf KPQ)^\circ:=P^\circ$、$(\mathsf SPQR)^\circ:=P^\circ R^\circ(Q^\circ R^\circ)$、それ以外の適用では $(PQ)^\circ:=P^\circ Q^\circ$ と定める。

基 $\mathsf KPQ$ の部分項 $\mathsf K$、$\mathsf KP$ や、基 $\mathsf SPQR$ の部分項 $\mathsf SP$、$\mathsf SPQ$ は基ではない。したがって 2 つの基の出現は、離れているか、一方が他方の引数 $P,Q,R$ の中にあるかのどちらかで、λ計算のように基どうしが重なることはない。$M^\circ$ は、$M$ にもとからある基をすべて縮約した項である。

並行簡約の基本性質
  1. すべての $M$ で $M\Rightarrow M$。
  2. $M\to_wM'$ なら $M\Rightarrow M'$。
  3. $M\Rightarrow M'$ なら $M\to_w^*M'$。
規則ごとに確かめる

1 は項の組み立て、2 は $\to_w$ の生成、3 は $M\Rightarrow M'$ の導出についての帰納法である。

詳しい証明を開く

1:原子は規則 1、適用は規則 2 による。2:根の基は 1 と規則 3・4、文脈の中の一歩は帰納法の仮定と 1 と規則 2 による。3:たとえば規則 4 では $\mathsf SPQR\to_w^*\mathsf SP'Q'R'\to_wP'R'(Q'R')$ である。規則 2・3 も同様である。$\square$

完全展開の補題

$M\Rightarrow N$ なら $N\Rightarrow M^\circ$ である。

$M\Rightarrow N$ の導出についての帰納法
  • 規則 1:$a\Rightarrow a=a^\circ$。
  • 規則 3:$\mathsf KPQ\Rightarrow P'$ なら、帰納法の仮定 $P'\Rightarrow P^\circ$ がそのまま $P'\Rightarrow(\mathsf KPQ)^\circ$ である。
  • 規則 4:$\mathsf SPQR\Rightarrow P'R'(Q'R')$ なら、帰納法の仮定 $P'\Rightarrow P^\circ$、$Q'\Rightarrow Q^\circ$、$R'\Rightarrow R^\circ$ と規則 2 で $P'R'(Q'R')\Rightarrow P^\circ R^\circ(Q^\circ R^\circ)=(\mathsf SPQR)^\circ$。
  • 規則 2:$M=PQ\Rightarrow P'Q'$ とする。$M$ が基でなければ $M^\circ=P^\circ Q^\circ$ なので、帰納法の仮定と規則 2 でよい。$M=\mathsf KAQ$ が基なら $P=\mathsf KA$ である。$\mathsf KA$ は基でないので、$P\Rightarrow P'$ に使える規則は 2 だけで、$P'=\mathsf KA'$、$A\Rightarrow A'$ となり、これは $M\Rightarrow N$ の導出の一部である。帰納法の仮定 $A'\Rightarrow A^\circ$ と規則 3 で $N=\mathsf KA'Q'\Rightarrow A^\circ=M^\circ$。$M=\mathsf SABQ$ が基なら、同じ理由で $P'=\mathsf SA'B'$、$A\Rightarrow A'$、$B\Rightarrow B'$ であり、帰納法の仮定と規則 4 で $N=\mathsf SA'B'Q'\Rightarrow A^\circ Q^\circ(B^\circ Q^\circ)=M^\circ$。$\square$
弱簡約の Church–Rosser の定理

$M\to_w^*N_1$ かつ $M\to_w^*N_2$ なら、$N_1\to_w^*L$ かつ $N_2\to_w^*L$ となる CL 項 $L$ がある。
$$ \xymatrix{ & M \ar[dl]_{*} \ar[dr]^{*} & \\ N_1 \ar@{.>}[dr]_{*} & & N_2 \ar@{.>}[dl]^{*} \\ & L & } $$

菱形を敷き詰める

lem-cl-takahashi により、$M\Rightarrow N_1$、$M\Rightarrow N_2$ なら $N_1\Rightarrow M^\circ$、$N_2\Rightarrow M^\circ$ である(菱形性)。$\Rightarrow$ を $m$ 回続けることを $\Rightarrow^m$ と書く。
主張:$M\Rightarrow^mN_1$、$M\Rightarrow^nN_2$ なら、$N_1\Rightarrow^nL$、$N_2\Rightarrow^mL$ となる $L$ がある。
$m+n$ についての帰納法で示す。$m=0$ なら $L:=N_2$、$n=0$ なら $L:=N_1$ でよい。$m,n\ge1$ とし、$M\Rightarrow P\Rightarrow^{m-1}N_1$、$M\Rightarrow Q\Rightarrow^{n-1}N_2$ と分ける。菱形性で $P\Rightarrow R$、$Q\Rightarrow R$ となる $R$ をとる。帰納法の仮定を $P$ からの $\Rightarrow^{m-1}N_1$ と $\Rightarrow^1R$ に使って $N_1\Rightarrow L_1$、$R\Rightarrow^{m-1}L_1$ となる $L_1$ をとる。次に $Q$ からの $\Rightarrow^mL_1$($Q\Rightarrow R\Rightarrow^{m-1}L_1$)と $\Rightarrow^{n-1}N_2$ に帰納法の仮定を使う($m+n-1< m+n$)と、$L_1\Rightarrow^{n-1}L$、$N_2\Rightarrow^mL$ となる $L$ がある。$N_1\Rightarrow L_1\Rightarrow^{n-1}L$ なので $N_1\Rightarrow^nL$ である。
lem-cl-parallel-basic の 1〜3 により、$M\to_w^*N$ はある $m$ で $M\Rightarrow^mN$ となることと同値なので、主張から定理が従う。$\square$

正規形の一意性と無矛盾性
  1. $M=_wN$ であるのは、$M\to_w^*L$ かつ $N\to_w^*L$ となる $L$ があるときに限る。
  2. 項の正規形は、あればただ 1 つである。
  3. 異なる正規形どうしは弱同値でない。とくに $\mathsf S\ne_w\mathsf K$、$x\ne_wy$($x\ne y$)であり、$=_w$ はすべての項を同一視するわけではない。

thm-cl-church-rosser と、正規形からの簡約は 0 回しかないことによる。

詳しい証明を開く

1:「共通の簡約先がある」という関係は反射的・対称的で $\to_w$ を含み、thm-cl-church-rosser により推移的である。よって $=_w$ を含む同値関係であり、逆の包含は明らかである。2:$N_1,N_2$ が $M$ の正規形なら、定理の $L$ について $N_i\to_w^*L$ だが、正規形からの簡約は 0 回しかないので $N_1=L=N_2$。3:1 と、正規形からの簡約は 0 回しかないことによる。$\square$

λ計算との対応と違い

λ計算 の項(λ項)と β 簡約 $\to_\beta$、β 同値 $=_\beta$ は同記事の定義に従う。

2 つの翻訳

CL 項 $M$ の λ 翻訳 $M_\lambda$ を、$x_\lambda:=x$、$\mathsf K_\lambda:=\lambda xy.\,x$、$\mathsf S_\lambda:=\lambda xyz.\,xz(yz)$、$(PQ)_\lambda:=P_\lambda Q_\lambda$ で定める。λ項 $M$ の CL 翻訳 $M_{\mathrm{CL}}$ を、$x_{\mathrm{CL}}:=x$、$(MN)_{\mathrm{CL}}:=M_{\mathrm{CL}}N_{\mathrm{CL}}$、$(\lambda x.\,M)_{\mathrm{CL}}:=[x].M_{\mathrm{CL}}$ で定める。

$\mathrm{FV}(M_\lambda)=\mathrm{FV}(M)$ であり、thm-cl-completeness の 1 から $\mathrm{FV}(M_{\mathrm{CL}})=\mathrm{FV}(M)$ である。

弱簡約は β 簡約に写る

$M\to_wN$ なら $M_\lambda\to_\beta^*N_\lambda$ である。したがって $M=_wN$ なら $M_\lambda=_\beta N_\lambda$ である。

根の基を計算する

根の基を 2 回または 3 回の β 簡約で縮約し、文脈は $\to_\beta$ が適用の両側で閉じていることで処理する。

詳しい証明を開く

束縛変数を $P_\lambda,Q_\lambda,R_\lambda$ の自由変数と異なるように選ぶと、$(\mathsf KPQ)_\lambda=(\lambda xy.\,x)P_\lambda Q_\lambda\to_\beta(\lambda y.\,P_\lambda)Q_\lambda\to_\beta P_\lambda$、$(\mathsf SPQR)_\lambda\to_\beta^*P_\lambda R_\lambda(Q_\lambda R_\lambda)$(3 回の縮約)である。文脈の中の一歩は、$\to_\beta$ が適用の両側で閉じていることによる。後半は前半を繰り返せばよい。$\square$

CL 翻訳は β 同値を保って戻る
  1. 任意の CL 項 $P$ と変数 $x$ について $([x].P)_\lambda=_\beta\lambda x.\,P_\lambda$。
  2. 任意の λ項 $M$ について $(M_{\mathrm{CL}})_\lambda=_\beta M$。
括弧抽象の 3 つの場合

1 は括弧抽象の 3 つの場合ごとに λ 翻訳を β 簡約し、2 は 1 を使って $M$ についての帰納法で示す。

詳しい証明を開く

1:$P$ についての帰納法である。$x\notin\mathrm{FV}(P)$ なら $(\mathsf KP)_\lambda\to_\beta\lambda y.\,P_\lambda$ で、これは $x\notin\mathrm{FV}(P_\lambda)$ なので $\lambda x.\,P_\lambda$ と α 同値である。$P=x$ なら $(\mathsf{SKK})_\lambda\to_\beta\lambda z.\,\mathsf K_\lambda z(\mathsf K_\lambda z)\to_\beta\lambda z.\,(\lambda y.\,z)(\mathsf K_\lambda z)\to_\beta\lambda z.\,z$ である。$P=QR$、$x\in\mathrm{FV}(P)$ なら、新しい変数 $z$ をとり、帰納法の仮定と、$=_\beta$ が抽象と適用で閉じていることから $(\mathsf S([x].Q)([x].R))_\lambda=_\beta\lambda z.\,([x].Q)_\lambda z\,(([x].R)_\lambda z)=_\beta\lambda z.\,(\lambda x.\,Q_\lambda)z\,((\lambda x.\,R_\lambda)z)=_\beta\lambda z.\,Q_\lambda[z/x]\,R_\lambda[z/x]$ であり、右辺は $\lambda x.\,Q_\lambda R_\lambda$ と α 同値である。2:抽象では 1 と帰納法の仮定から $([x].M_{\mathrm{CL}})_\lambda=_\beta\lambda x.\,(M_{\mathrm{CL}})_\lambda=_\beta\lambda x.\,M$。変数と適用はそのまま。$\square$

2 により、どの λ項も、ある CL 項の λ 翻訳と β 同値である。数や不動点をλ計算で表す議論は、CL 翻訳を通して CL に持ち込める(ex-cl-numerals、cor-cl-fixed-point)。
しかし逆向きは成り立たない。弱簡約は、項が引数を 1 つずつ受け取って初めて動くので、λ計算の ξ 規則($M=_\beta N$ なら $\lambda x.\,M=_\beta\lambda x.\,N$)にあたる「$P=_wQ$ なら $[x].P=_w[x].Q$」が成り立たない。たとえば $\mathsf Ix=_wx$ だが、
$$ [x].(\mathsf Ix)=\mathsf S(\mathsf K\mathsf I)\mathsf I,\qquad[x].x=\mathsf I $$
はどちらも正規形で、異なるので弱同値でない(cor-cl-unique-normal-form の 3)。同じ理由で、$\lambda x.\,(\lambda y.\,y)x\to_\beta\lambda x.\,x$ の両辺の CL 翻訳はこの 2 つの項であり、β 簡約は弱簡約に写らない。

型つきの組合せ論理と Hilbert 流の命題論理

型を、型変数 $\alpha,\beta,\dots$ から $A\to B$ で組み立てた式とする($\to$ は右に結合する)。これは含意だけの命題論理の論理式と同じものである。文脈 $\Gamma$ を、相異なる変数に型を 1 つずつ割り当てた有限集合 $\{x_1{:}A_1,\dots,x_n{:}A_n\}$ とする。

型つきの組合せ論理

判断 $\Gamma\vdash M:A$ を、次の規則で生成される最小の関係とする($A,B,C$ は任意の型)。

  1. $x{:}A\in\Gamma$ なら $\Gamma\vdash x:A$。
  2. $\Gamma\vdash\mathsf K:A\to B\to A$。
  3. $\Gamma\vdash\mathsf S:(A\to B\to C)\to(A\to B)\to A\to C$。
  4. $\Gamma\vdash P:A\to B$、$\Gamma\vdash Q:A$ なら $\Gamma\vdash PQ:B$。

規則 2・3 の型は Hilbert流の証明体系 の公理図式 (A1)・(A2) と、規則 4 は前件肯定(MP)と同じ形である。たとえば $\mathsf I=\mathsf{SKK}$ には、$\mathsf S$ に $(A\to(A\to A)\to A)\to(A\to A\to A)\to A\to A$、1 つ目の $\mathsf K$ に $A\to(A\to A)\to A$、2 つ目の $\mathsf K$ に $A\to A\to A$ を当てて $\vdash\mathsf I:A\to A$ が導ける。この導出は、演繹定理 の記事の 5 行の導出「恒等式の導出」と行ごとに同じである。

型つき組合せ論理と Hilbert 流の命題論理

含意だけの論理式について、公理図式 (A1)・(A2) と MP からなる体系での導出可能性を $\vdash_{\mathrm H}$ と書く。

  1. $\Gamma\vdash M:A$ なら $\{A_1,\dots,A_n\}\vdash_{\mathrm H}A$ である($A_i$ は $\Gamma$ の型)。
  2. $\{A_1,\dots,A_n\}\vdash_{\mathrm H}A$ なら、相異なる変数 $x_1,\dots,x_n$ について $\{x_1{:}A_1,\dots,x_n{:}A_n\}\vdash M:A$ となる CL 項 $M$ がある。
  3. $\Gamma\cup\{x{:}A\}\vdash M:B$($x$ は $\Gamma$ に現れない)なら $\Gamma\vdash[x].M:A\to B$ である。
  4. $\Gamma\vdash M:A$、$M\to_wN$ なら $\Gamma\vdash N:A$ である。
規則と公理を 1 対 1 に対応させる

1:判断の導出について帰納法を使う。規則 1 は仮定、規則 2・3 は (A1)・(A2) の実例、規則 4 は MP にそのまま写る。
2:$\vdash_{\mathrm H}$ の導出の長さについての帰納法である。仮定 $A_i$ には $x_i$、(A1)・(A2) の実例には $\mathsf K$・$\mathsf S$ を当てる(規則 2・3 の型はどの $A,B,C$ にもとれる)。MP で $B$ と $B\to A$ から $A$ を得たなら、それぞれに当てた項 $Q,P$ から $PQ$ を作る(規則 4)。
3:$M$ についての帰納法で、括弧抽象の場合に分ける。$x\notin\mathrm{FV}(M)$ のとき、$M:B$ の導出は $x{:}A$ を使わないので $\Gamma\vdash M:B$ であり、$\mathsf K:B\to A\to B$ と規則 4 で $\Gamma\vdash\mathsf KM:A\to B$。$M=x$ のとき $B=A$ で、上の計算により $\Gamma\vdash\mathsf I:A\to A$。$M=PQ$、$x\in\mathrm{FV}(M)$ のとき、導出の最後は規則 4 なので、ある $C$ について $P:C\to B$、$Q:C$ が導ける。帰納法の仮定で $[x].P:A\to C\to B$、$[x].Q:A\to C$ であり、$\mathsf S:(A\to C\to B)\to(A\to C)\to A\to B$ に規則 4 を 2 回使って $\Gamma\vdash\mathsf S([x].P)([x].Q):A\to B$。
4:適用の型を導く規則は 4 だけなので、導出は項の形から逆にたどれる。根の基 $\mathsf KPQ:A$ では、$\mathsf K$ に当たる型は $D\to E\to D$ の形で $\mathsf KPQ$ の型は $D$ だから、$D=A$ で $P:A$ である。$\mathsf SPQR:A$ では、$\mathsf S$ に当たる型 $(D\to E\to C)\to(D\to E)\to D\to C$ について $P:D\to E\to C$、$Q:D\to E$、$R:D$、$C=A$ なので、$PR:E\to A$、$QR:E$ から $PR(QR):A$ である。文脈の中の一歩は、帰納法の仮定で部分項の型が保たれることによる。$\square$

3 は、演繹定理 の証明と同じ場合分けを項の上で行ったものである。演繹定理の証明が導出を機械的に書き換えるのに対し、ここでは括弧抽象が項を書き換える。1・2 と合わせると、含意だけの命題論理の導出と型つきの CL 項が対応し、Curry–Howard対応 の Hilbert 流の版になる。
型がつかない項もある。$\mathsf D=\mathsf{SII}$(ex-cl-omega)には型がつかず、したがって終わらない簡約の列をもつ $\mathsf{DD}$ にも型がつかない。

確かめを開く

まず $\mathsf I=\mathsf{SKK}$ の型はどれも $X\to X$ の形である。実際、4 の証明と同じく導出を逆にたどると、$\mathsf S$ に当たる型 $(A'\to B'\to C')\to(A'\to B')\to A'\to C'$ について 1 つ目の $\mathsf K$ の型が $A'\to B'\to C'$ で、これは $D\to E\to D$ の形なので $C'=A'$ となり、$\mathsf{SKK}$ の型は $A'\to C'=A'\to A'$ である。$\mathsf{SII}$ に型がつくとすると、$\mathsf S$ に当たる型を $(A\to B\to C)\to(A\to B)\to A\to C$ として、1 つ目の $\mathsf I$ の型 $X\to X$ から $A=X$、$B\to C=X$、2 つ目の $\mathsf I$ の型 $Y\to Y$ から $A=Y=B$ となる。すると $A=B\to C=A\to C$ だが、型 $A$ は自分より真に長い $A\to C$ と等しくなれないので矛盾する。$\mathsf{DD}$ に型がつけば、導出の最後の規則 4 から部分項 $\mathsf D$ にも型がつくので、$\mathsf{DD}$ にも型はつかない。

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

外す条件・加える主張反例成り立たなくなること
ξ 規則:$P=_wQ$ なら $[x].P=_w[x].Q$$P=\mathsf Ix$、$Q=x$$\mathsf S(\mathsf{KI})\mathsf I\ne_w\mathsf I$
外延性:新しい変数 $y$ で $My=_wNy$ なら $M=_wN$$M=\mathsf{SK}x$、$N=\mathsf{KI}x$$\mathsf{SK}x\ne_w\mathsf{KI}x$
prop-cl-to-lambda の逆$\mathsf{SK}$ と $\mathsf{KI}$λ 翻訳は β 同値だが弱同値でない
thm-cl-curry-howard の型がつくこと$\mathsf D=\mathsf{SII}$型がつかず、$\mathsf{DD}$ は終わらない簡約をもつ
表の確かめを開く

1 行目は前の節の計算である。2 行目:$\mathsf{SK}xy\to_w\mathsf Ky(xy)\to_wy$、$\mathsf{KI}xy\to_w\mathsf Iy\to_w^*y$ なので $My=_wNy$ である。一方 $\mathsf{SK}x$ は正規形($\mathsf S$ の引数が 2 つしかない)、$\mathsf{KI}x\to_w\mathsf I$ も正規形で、両者は異なるので弱同値でない(cor-cl-unique-normal-form の 3)。3 行目:$(\mathsf{SK})_\lambda\to_\beta^*\lambda yz.\,(\lambda xy'.\,x)z(yz)\to_\beta^*\lambda yz.\,z$、$(\mathsf{KI})_\lambda\to_\beta\lambda y.\,\mathsf I_\lambda\to_\beta^*\lambda yz.\,z$ で β 同値である。$\mathsf{SK}$ と $\mathsf{KI}$ はどちらも正規形で異なるので弱同値でない。4 行目は前の節の計算と ex-cl-omega による。

歴史と出典

Schönfinkel は 1920 年 12 月の Göttingen での講演で、恒等関数 $I$、定数関数 $C$(この記事の $\mathsf K$)、入れ替え関数 $T$、合成関数 $Z$、融合関数 $S$ を導入し、$I,T,Z$ が $C$ と $S$ で表せることを示した(Sch24 §3–§4、pp. 309–312。論文は H. Behmann が講演をもとにまとめた、p. 305 の脚注)。$I=SCC$ の表し方は Boskowitz が、$\mathsf B$ と同じ $Z=S(CS)C$ は Schönfinkel 自身が与えている(同 p. 312)。
括弧抽象の定義、thm-cl-completeness・thm-cl-church-rosser・prop-cl-from-lambda・thm-cl-curry-howard の証明、反例の表はこの記事で書き下ろした。Church–Rosser の定理の証明は、λ計算 の記事の並行簡約と完全展開による証明を CL に移したものである。

関連項目

参考文献

[1]
Moses Schönfinkel, Über die Bausteine der mathematischen Logik, Mathematische Annalen 92 (1924), 305–316, 1924, §1 と脚注 1 p. 305、§3(関数 I・C・T・Z・S)pp. 309–311、§4(I=SCC と脚注 3、Z=S(CS)C、T の表示)pp. 311–312、§5 pp. 312–313

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