実現可能性

同義語:realizabilityKleeneの実現可能性Kleene realizability

概要

実現可能性(realizability)とは、算術の文と自然数の間に「その数が文を実現する」という関係を定め、選言はどちらの側か、存在はどの値か、全称と含意は計算の手順を表す数で裏づける解釈で、Kleene が Heyting算術について導入した。Heyting算術で証明できる文はすべて実現される(健全性定理)。停止問題が決定できないことから、排中律を全称化した文の否定が実現されるので、その文は Heyting算術で証明できず、否定を加えても無矛盾である。Markov の原理も実現される。

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

前提知識: Heyting算術, 計算可能関数, 自然演繹

実現可能性(realizability)とは、算術の文 $A$ と自然数 $e$ の間に「$e$ は $A$ を実現する」という関係を定め、文の意味を「その文を裏づける計算の情報」として読む解釈である。Kleene が 1945 年に Heyting算術 $\mathsf{HA}$ について導入した(Kle45)。たとえば $\forall x\exists y\,A(x,y)$ を実現する数は、各 $x$ から $y$ と $A(x,y)$ の実現を計算する計算可能関数の番号である。
主定理は健全性定理である:$\mathsf{HA}$ で証明できる文はすべて実現される(thm-rz-soundness)。実現される文は古典的に真とは限らず、たとえば「すべての $x$ で $A(x)$ か $\lnot A(x)$」の否定が実現されることがある(thm-rz-lem)。このため、実現可能性は $\mathsf{HA}$ で証明できない文を見分ける道具になる。また、Markov の原理は実現される(thm-rz-markov)。
機械学習の PAC学習 でいう「実現可能」(仮説の集合に誤差 $0$ の仮説があること)は別の意味であり、この記事では扱わない。

記号

$\varphi_e$ を番号 $e$ の部分計算可能関数とし(計算可能関数)、$\{e\}(n):=\varphi_e(n)$ と書く。$\{e\}(n)\!\downarrow$ は値が定義されることを表す。$\langle m,k\rangle$ を $\mathbb N^2$ から $\mathbb N$ への計算可能な全単射とし、その逆を $n\mapsto((n)_0,(n)_1)$ と書く。部分関数の式 $s\simeq t$ は、両辺が同時に定義され、定義されれば等しいことを表す。
$\mathsf{HA}$ の言語は $\{0,S,+,\cdot,<\}$ と等号で、論理記号は $\land,\lor,\to,\forall,\exists$ と恒偽 $\bot$ である。$\lnot A$ は $A\to\bot$ の略記である。数 $n$ の数項($0$ に $S$ を $n$ 回施した項)を $\underline n$ と書く。閉じた項は自然数を値にもち、閉じた原子論理式 $s=t$、$s< t$ は値によって真偽が決まる。$\bot$ は偽の原子論理式として扱う。

定義と例

数による実現可能性

閉じた論理式(文)$A$ と $e\in\mathbb N$ について、「$e$ は $A$ を実現する」($e\ \mathbf r\ A$ と書く)を $A$ の構成に関する帰納法で定める。

  1. $A$ が原子論理式のとき:$e\ \mathbf r\ A$ は $e=0$ かつ $A$ が真であること。
  2. $e\ \mathbf r\ (A\land B)$ は $(e)_0\ \mathbf r\ A$ かつ $(e)_1\ \mathbf r\ B$ であること。
  3. $e\ \mathbf r\ (A\lor B)$ は、$(e)_0=0$ かつ $(e)_1\ \mathbf r\ A$ であるか、$(e)_0\ne0$ かつ $(e)_1\ \mathbf r\ B$ であること。
  4. $e\ \mathbf r\ (A\to B)$ は、$a\ \mathbf r\ A$ となるすべての $a$ について $\{e\}(a)\!\downarrow$ かつ $\{e\}(a)\ \mathbf r\ B$ であること。
  5. $e\ \mathbf r\ \exists x\,A(x)$ は $(e)_1\ \mathbf r\ A(\underline{(e)_0})$ であること。
  6. $e\ \mathbf r\ \forall x\,A(x)$ は、すべての $n$ について $\{e\}(n)\!\downarrow$ かつ $\{e\}(n)\ \mathbf r\ A(\underline n)$ であること。
    $e\ \mathbf r\ A$ となる $e$ があるとき、$A$ は 実現される(realizable)という。自由変数をもつ論理式は、その全称閉包が実現されるとき実現されるという。

この形は vOo02(著者稿 p. 5)の定義の節と同じである(選言の印を $0$ と $0$ 以外で分けた点だけが表記の違いである)。原子論理式の真偽は項の値だけで決まるので、閉じた項 $s,t$ の値が等しければ、$A(s)$ と $A(t)$ を実現する数は同じである(論理式の構成に関する帰納法)。以下この事実を断らずに使う。
定義から次がすぐにわかる。

  • $\bot$ を実現する数はない。従って $e\ \mathbf r\ \lnot A$ は「$A$ を実現する数がない」ことと同値であり、そのとき $e$ は何でもよい($\{e\}(a)$ を評価すべき $a$ がない)。
  • $\lnot\lnot A$ が実現されることは、$A$ が実現されることと同値である。
実現する数の例
  1. $\forall x\exists y\,(x< y)$ は、$n\mapsto\langle n+1,0\rangle$ を計算する機械の番号で実現される。
  2. $\forall x\,(x=0\lor\exists y\,(x=Sy))$ は、$0\mapsto\langle0,0\rangle$、$n+1\mapsto\langle1,\langle n,0\rangle\rangle$ を計算する機械の番号で実現される。
  3. $A$ を文とすると、$A\lor\lnot A$ が実現されることは「$A$ が実現されるか、実現されないか」なので、どの文についても成り立つ。実現されないことがあるのは、自由変数を量化した $\forall x\,(A(x)\lor\lnot A(x))$ の方である(thm-rz-lem)。

選言と存在を実現する数は、どちらの選言肢が成り立つか、どの値で成り立つかを含む。全称と含意を実現する数は計算の手順である。古典的な真偽との違いは、この「計算できる」という要求から生じる。

負の論理式

負の論理式では実現と真が一致する

$\lor$、$\exists$ を含まない論理式を 負の論理式 とよぶ。負の論理式 $A$ ごとに数 $c_A$ を、原子論理式では $c_A:=0$、$c_{A\land B}:=\langle c_A,c_B\rangle$、$c_{A\to B}$ と $c_{\forall xA}$ は値がつねに $c_B$、$c_A$ の全域関数の番号、と定める($c_{A(x)}$ は $x$ に依らない)。閉じた負の論理式 $A$ について、次は同値である。

  1. $A$ は真である。
  2. $A$ は実現される。
  3. $c_A\ \mathbf r\ A$ である。

3⇒2 は明らかである。1⇒3 と 2⇒1 を論理式の構成に関する帰納法で同時に示す。原子論理式と $\land$ では定義そのものである。
$A\to B$ のとき。1⇒3:$A\to B$ が真とし、$a\ \mathbf r\ A$ とする。帰納法の仮定(2⇒1)で $A$ は真、従って $B$ は真で、帰納法の仮定(1⇒3)で $c_B\ \mathbf r\ B$ である。$\{c_{A\to B}\}(a)=c_B$ なので $c_{A\to B}\ \mathbf r\ (A\to B)$ である。2⇒1:$e\ \mathbf r\ (A\to B)$ とし、$A$ が真とする。帰納法の仮定で $c_A\ \mathbf r\ A$ なので $\{e\}(c_A)\ \mathbf r\ B$ であり、$B$ は真である。
$\forall xA(x)$ のとき。1⇒3:各 $A(\underline n)$ が真なので $c_A\ \mathbf r\ A(\underline n)$ であり、$\{c_{\forall xA}\}(n)=c_A$ である。2⇒1:$e$ が実現するなら各 $\{e\}(n)$ が $A(\underline n)$ を実現し、$A(\underline n)$ は真である。$\square$

健全性定理

$\mathsf{HA}$ の証明は 自然演繹 の直観主義の体系 $\mathrm{NJ}$ で、公理は Peano算術 の公理 $1$〜$8$(後者関数・加法・乗法・$<$ の定義の公理)、帰納法の公理
$$ A(0)\land\forall x\,(A(x)\to A(Sx))\to\forall x\,A(x) $$
と、等号の公理 $x=x$、$x=y\to(A(x)\to A(y))$ である(Heyting算術 の定義に従う)。

実現可能性の健全性

$\mathsf{HA}\vdash A$ なら $A$ は実現される。より詳しく、仮定 $B_1,\dots,B_m$ から $A$ が $\mathrm{NJ}$ と $\mathsf{HA}$ の公理で導かれ、自由変数が $\vec x=(x_1,\dots,x_k)$ の中にあるとき、部分計算可能関数 $t(\vec n,b_1,\dots,b_m)$ で次を満たすものがある:$\vec n\in\mathbb N^k$ と、各 $j$ で $b_j\ \mathbf r\ B_j(\underline{\vec n})$ を満たす $b_1,\dots,b_m$ について、$t(\vec n,\vec b)\!\downarrow$ かつ $t(\vec n,\vec b)\ \mathbf r\ A(\underline{\vec n})$ である。

$m=0$ の場合が前半で、$\vec n\mapsto t(\vec n)$ から全称閉包を実現する数が s-m-n定理 で得られる。この定理は vOo02(著者稿 p. 6)で基本定理として述べられているものの、仮定のない形である。

導出に関する帰納法

導出の長さに関する帰納法で $t$ を作る。部分導出に、結論にも開いた仮定にも現れない自由変数($\forall$ の導入と $\exists$ の除去の $y$ を除く)があるときは、その変数も並べて帰納法の仮定を当て、どの部分導出でもその値を $0$ とおく(実現すべき文と仮定はその値によらない)。以下、$\vec b$ は仮定の実現の列を表し、関数を作るときの計算可能性は s-m-n定理 による(引数の一部を固定した関数の番号が、固定した値から計算できる)。
仮定. $A=B_j$ なら $t(\vec n,\vec b):=b_j$ とする。
公理. 公理 $1,2,4$〜$7$ と $x=x$ は負の論理式で、どの代入でも真なので、lem-rz-negative により定数 $c_A$ で実現される。公理 $3$ $\forall x\,(\lnot x=0\to\exists y\,x=Sy)$ は、$n$ に「$a\mapsto\langle n-1,0\rangle$ を計算する機械の番号」を対応させる関数の番号で実現される($\lnot\,\underline n=0$ が実現されるのは $n\ge1$ のときだけである)。公理 $8$ は $\leftrightarrow$ を 2 つの $\to$ の $\land$ とみて、$x< y$ の向きは $\langle y-x-1,0\rangle$ を出し、逆向きは $0$ を出す計算で実現される。等号の公理 $x=y\to(A(x)\to A(y))$ では、$a\ \mathbf r\ (\underline p=\underline q)$ なら $p=q$ で $A(\underline p)$ と $A(\underline q)$ は同じ文なので、$a\mapsto(\text{恒等関数の番号})$ を計算する番号が実現する。帰納法の公理では、$\langle a,b\rangle$ が前件を実現するとき、
$$ h(0):=a,\qquad h(n+1):=\{\{b\}(n)\}(h(n)) $$
とおく。$h(n)\ \mathbf r\ A(\underline n)$ が $n$ の帰納法で成り立ち($\{b\}(n)\ \mathbf r\ (A(\underline n)\to A(\underline{n+1}))$ だから)、とくに $h$ は全域的である。$h$ の番号は $a,b$ から計算できるので、$\langle a,b\rangle\mapsto(h\text{ の番号})$ を計算する番号が実現する。
$\land$ の導入と除去. $t:=\langle t_1,t_2\rangle$、$t:=(t_1)_0$ または $(t_1)_1$ とする。
$\lor$ の導入. $A\lor B$ を $A$ から導くなら $t:=\langle0,t_1\rangle$、$B$ から導くなら $t:=\langle1,t_1\rangle$ とする。
$\lor$ の除去. $A\lor B$、仮定 $A$ を加えた $C$、仮定 $B$ を加えた $C$ の導出の関数を $t_0,t_1,t_2$ とし、$d:=t_0(\vec n,\vec b)$ とおく。$(d)_0=0$ なら $t:=t_1(\vec n,\vec b,(d)_1)$、そうでなければ $t:=t_2(\vec n,\vec b,(d)_1)$ とする。$(d)_1$ は採られた側の選言肢を実現するので、$t$ は $C$ を実現する。
$\to$ の導入. 仮定 $A$ を加えて $B$ を導く関数を $t_1(\vec n,\vec b,a)$ とし、$t(\vec n,\vec b)$ を $a\mapsto t_1(\vec n,\vec b,a)$ の番号とする。$a\ \mathbf r\ A(\underline{\vec n})$ なら $\{t\}(a)$ は定義されて $B(\underline{\vec n})$ を実現する。
$\to$ の除去. $t:=\{t_1(\vec n,\vec b)\}(t_2(\vec n,\vec b))$ とする。
$\forall$ の導入. $A(y)$ を導き、$y$ が仮定 $B_j$ に自由に現れないとする。$y$ の値を $p$ とした関数 $t_1(\vec n,p,\vec b)$ について、$t(\vec n,\vec b)$ を $p\mapsto t_1(\vec n,p,\vec b)$ の番号とする。$\vec b$ は $y$ の値によらず仮定を実現するので、この関数は全域的で、各 $p$ で $A(\underline p)$ を実現する。
$\forall$ の除去. $\forall yA(y)$ から $A(s)$($s$ の自由変数は $\vec x$ の中)を導くとき、$s(\underline{\vec n})$ の値 $p$ は $\vec n$ から計算でき、$t:=\{t_1(\vec n,\vec b)\}(p)$ は $A(\underline p)$、従って $A(s(\underline{\vec n}))$ を実現する。
$\exists$ の導入. $A(s)$ から $\exists yA(y)$ を導くとき、$t:=\langle p,t_1(\vec n,\vec b)\rangle$($p$ は $s(\underline{\vec n})$ の値)とする。
$\exists$ の除去. $\exists yA(y)$ と、仮定 $A(y)$ を加えた $C$ の導出があり、$y$ は $C$ とほかの仮定に自由に現れないとする。$d:=t_0(\vec n,\vec b)$ について $t:=t_1(\vec n,(d)_0,\vec b,(d)_1)$ とする。$(d)_1\ \mathbf r\ A(\underline{(d)_0})$ なので、$t$ は $C$ を実現する。
$\bot$ の除去. $\bot$ から $A$ を導くとき、帰納法の仮定により、$\vec b$ が仮定を実現すれば $t_1(\vec n,\vec b)$ は $\bot$ を実現する。$\bot$ を実現する数はないので、仮定を実現する $\vec b$ はない。従って $t$ は何でもよく、$t:=0$ とする。$\square$

$\mathsf{HA}$ に対する Gödelの不完全性定理 の第 2 不完全性定理と矛盾しないことに注意する。健全性定理の証明は、自然数についての古典的な推論と、実現の関係そのもの(算術の階層のどの段にも収まらない)を使っており、$\mathsf{HA}$ の中で行っているわけではない。$\mathsf{HA}$ の中に実現の関係を論理式として書き、健全性の各段を $\mathsf{HA}$ で証明する 形式化された実現可能性 もあり、vOo02(著者稿 p. 7)はその形を Troelstra に従って述べている。

証明できないことの判定

健全性定理の対偶から、実現されない文は $\mathsf{HA}$ で証明できない。また、$B$ が実現されるなら $\lnot B$ は実現されない($\lnot B$ の実現は $B$ の実現がないことを意味する)ので、$\mathsf{HA}\nvdash\lnot B$、すなわち $\mathsf{HA}+B$ は無矛盾である。

排中律の全称化の否定が実現される

自己停止集合 $K:=\{n\mid\{n\}(n)\!\downarrow\}$ を MRDPの定理 により $n\in K\iff\exists\vec y\,\bigl(p(n,\vec y)=q(n,\vec y)\bigr)$ と表す($p,q$ は自然数係数の多項式)。$D(x):=\exists y_1\cdots\exists y_r\,\bigl(p(x,\vec y)=q(x,\vec y)\bigr)$ とおくと、次が成り立つ。

  1. $\forall x\,(D(x)\lor\lnot D(x))$ は実現されない。
  2. $\lnot\forall x\,(D(x)\lor\lnot D(x))$ は実現される。
  3. $\mathsf{HA}\nvdash\forall x\,(D(x)\lor\lnot D(x))$ であり、$\mathsf{HA}+\lnot\forall x\,(D(x)\lor\lnot D(x))$ は無矛盾である。
実現する数から停止問題が解ける

$D(\underline n)$ を実現する数は、$\vec y$ の値と原子論理式の実現 $0$ を並べたものなので、$D(\underline n)$ が実現されることと $n\in K$ は同値である。$\lnot D(\underline n)$ が実現されることは、$D(\underline n)$ が実現されないこと、すなわち $n\notin K$ と同値である。
1:$e$ が $\forall x\,(D(x)\lor\lnot D(x))$ を実現するとすると、$n\mapsto(\{e\}(n))_0$ は全域的な計算可能関数で、$0$ なら $D(\underline n)$ が実現され $n\in K$、$0$ 以外なら $\lnot D(\underline n)$ が実現され $n\notin K$ である。これは $K$ が決定可能でないこと(停止問題)に反する。
2:1 より、否定を実現する数の定義(何でもよい)から従う。
3:前半は 1 と thm-rz-soundness による。後半は 2 と本節の初めの注意による。$\square$

$\mathsf{PA}$ は排中律により $\forall x\,(D(x)\lor\lnot D(x))$ を証明するので、2 は「実現される文が古典的に偽でありうる」ことも示している。同じ論法で、vOo02(著者稿 p. 6)が述べる通り、$\lnot\forall x\,(A(x)\lor\lnot A(x))$ が $\mathsf{HA}$ と無矛盾になる論理式 $A$ があり、二重否定のずらし $\forall x\lnot\lnot A(x)\to\lnot\lnot\forall xA(x)$ は $\mathsf{HA}$ の導出規則ではない。

Markov の原理は実現される

$A(x)$ を $x$ 以外に自由変数をもたない論理式とする。Markov の原理
$$ \forall x\,(A(x)\lor\lnot A(x))\land\lnot\lnot\exists x\,A(x)\to\exists x\,A(x) $$
は実現される。

止まることが保証された探索

入力 $d$ に対し、$e:=(d)_0$ として $n=0,1,2,\dots$ の順に $\{e\}(n)$ を計算し、初めて $(\{e\}(n))_0=0$ となった $n$ で $\langle n,(\{e\}(n))_1\rangle$ を出す機械の番号を $r$ とする。$r$ が実現することを示す。
$d$ が前件を実現するとする。$e=(d)_0$ は $\forall x\,(A(x)\lor\lnot A(x))$ を実現し、$\lnot\lnot\exists xA(x)$ が実現されるので $\exists xA(x)$ は実現される。従って $A(\underline m)$ が実現される $m$ がある。各 $n$ で $\{e\}(n)$ は定義される。$(\{e\}(m))_0\ne0$ なら $\lnot A(\underline m)$ が実現され、$A(\underline m)$ に実現がないことになって矛盾するので、$(\{e\}(m))_0=0$ である。よって探索は $m$ 以下で止まり、止まった $n$ で $(\{e\}(n))_1\ \mathbf r\ A(\underline n)$ なので、出力は $\exists xA(x)$ を実現する。$\square$

探索が止まることの証明には、「$A(\underline m)$ が実現される $m$ がある」という存在を、その $m$ を計算せずに使っている。実現可能性の定義は、このような古典的な推論を理論の外で用いる。

関連する結果

引用する結果

次はこの記事では証明しない。

  1. Church の規則:$\mathsf{HA}\vdash\forall x\exists y\,A(x,y)$ なら、$\mathsf{HA}\vdash\exists e\,\forall x\,\bigl(\{e\}(x)\!\downarrow\land A(x,\{e\}(x))\bigr)$ となる($\{e\}(x)\!\downarrow$ などは Kleene の計算述語で $\mathsf{HA}$ の中に書いたもの)。実現を $A$ 自身の成立と組み合わせた q-実現可能性で示される(vOo02 著者稿 p. 8)。
  2. 形式化された実現可能性の公理化:$\mathsf{HA}$ の中で「実現される」ことと同値になるのは、拡張された Church の提言 $\mathrm{ECT}_0$ を加えた理論で証明できることである。Markov の原理を加えても同様である(Dragalin と Troelstra による。vOo02 著者稿 p. 9)。とくに Church の提言と Markov の原理を同時に $\mathsf{HA}$ に加えても無矛盾である。
  3. 論理の不完全性:直観主義命題論理で証明できないが、どの算術の代入例も実現される命題論理式がある(Rose、のちに Ceitin。vOo02 著者稿 p. 8)。実現可能性は直観主義論理の完全な意味論ではない。

$\mathsf{HA}$ の選言性と存在性(Heyting算術 の系「選言性と存在性」)も、実現の定義に「$\mathsf{HA}$ で証明できる」という条件を貼り合わせた変種から導かれる(vOo02 著者稿 p. 6)。
実現可能性は算術の外にも広がる。計算可能な部分関数の代わりに一般の部分組合せ代数を使う実現可能性があり、組合せ論理 の項もその例になる。Hyland は実現可能性から 有効トポス(effective topos)を構成した(Hyl82)。この トポス で自然数対象についての一階算術の真偽は Kleene の実現可能性と同値になる(vOo02 著者稿 pp. 15–16)。

例と反例

主張反例満たされない条件
実現される文は真であるthm-rz-lem の $\lnot\forall x\,(D(x)\lor\lnot D(x))$負の論理式であること(lem-rz-negative では一致する)
真な文は実現される$\forall x\,(D(x)\lor\lnot D(x))$選言の選び方が $x$ から計算できること
実現される文は $\mathsf{HA}$ で証明できる$\lnot\forall x\,(D(x)\lor\lnot D(x))$文が $\mathsf{PA}$ で反証されないこと(健全性定理の逆は成り立たない)

3 行目の確かめ:$\mathsf{PA}$ は $\forall x\,(D(x)\lor\lnot D(x))$ を証明し、$\mathsf{PA}$ は無矛盾なので、$\mathsf{PA}$ の部分である $\mathsf{HA}$ はその否定を証明しない。

関連項目

参考文献

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