帰納的可算集合

同義語：再帰的可算集合計算可能枚挙集合半決定可能集合recursively enumerable setcomputably enumerable set

概要

前提知識: 計算可能関数, 停止問題, 万能Turing機械

自然数の集合 $A$ について、「$x\in A$ なら、いつかそう確かめられる」手順があるとき、$A$ を 帰納的可算集合（recursively enumerable set）という。$x\notin A$ のときには手順が止まらなくてもよい。たとえば、番号 $e$ の計算が入力 $e$ で止まるような $e$ の集合（自己停止集合）は、計算を動かしてみれば止まる側だけは確かめられるので帰納的可算であるが、決定可能ではない（停止問題）。名前の「可算」（enumerable）は、空でない帰納的可算集合が、計算可能な関数 $g$ で $g(0),g(1),g(2),\dots$ と並べ上げられる集合と一致することによる。計算可能枚挙集合（computably enumerable set）、半決定可能集合 ともよばれる。
この記事では、帰納的可算集合の同値な言い換え（部分計算可能関数の定義域、計算可能関数の値域、部分計算可能関数の値域、決定可能な関係の射影）を証明し、和集合・共通部分・射影・逆像・像についての閉包性、段階ごとの近似、無限の帰納的可算集合が無限の決定可能な部分集合をもつことを示す。最後に、補集合が無限でありながら無限の帰納的可算集合を 1 つも含まない 単純集合 を構成し、帰納的可算でも決定可能でもない集合の性質の違いを見る。

記法と前提

$\mathbb{N}=\{0,1,2,\dots\}$ とする。部分関数・$f(x)\!\downarrow$・$\simeq$・部分計算可能・計算可能・決定可能の意味は計算可能関数の定義「計算可能関数」に従い、同じ記事の「記法と前提」の事実 (A)（Turing 計算可能な部分関数と μ再帰関数の一致）を使う。とくに部分計算可能関数は合成・原始再帰・μ 作用素で閉じており、原始再帰的な関係は決定可能である。有限列の符号 $\langle a_0,\dots,a_{k-1}\rangle$ と $i$ 番目の項 $(c)_i$ も同じ記事に従う（どちらも原始再帰的で、$(\langle a_0,\dots,a_{k-1}\rangle)_i=a_i$）。
番号付け $\varphi_e$ は計算可能関数の定義「標準の番号付け」のものとする。万能Turing機械の定理「万能関数の標準形」により、原始再帰的な関係 $T(e,x,s)$ と原始再帰関数 $V(e,x,s)$ があって
$$ \varphi_e(x)\simeq V\bigl(e,x,\ \mu s\,T(e,x,s)\bigr) $$
である。したがって $\varphi_e(x)\!\downarrow$ は $\exists s\,T(e,x,s)$ と同値であり、$\varphi_e(x)\!\downarrow$ かつ $\varphi_e(x)=y$ であることは
$$ \exists s\ \bigl[\,T(e,x,s)\ \land\ \forall t< s\ \lnot T(e,x,t)\ \land\ V(e,x,s)=y\,\bigr] $$
と同値である（角括弧の中は原始再帰的な関係である）。部分関数 $f\colon\mathbb{N}\rightharpoonup\mathbb{N}$ が部分計算可能であることは、ある $e$ で $f=\varphi_e$ となることと同値である（計算可能関数の命題「番号付けは部分計算可能関数をすべて並べる」）。

定義

帰納的可算集合

$A\subset\mathbb{N}^k$ が、ある部分計算可能関数 $f\colon\mathbb{N}^k\rightharpoonup\mathbb{N}$ の定義域であるとき、$A$ は 帰納的可算（recursively enumerable、計算可能枚挙、半決定可能）であるという。$e\in\mathbb{N}$ について
$$ W_e:=\operatorname{dom}\varphi_e=\{x\in\mathbb{N}\mid\varphi_e(x)\!\downarrow\} $$
とおく。$A\subset\mathbb{N}$ が帰納的可算であることは、ある $e$ で $A=W_e$ となることと同値である。

この定義は停止問題の定義「決定可能と半決定可能」の半決定可能と同じである。文字列の集合（言語）については、文字列を自然数で符号化して同じように定める。Turing 機械が受理する言語、すなわち句構造文法が生成する言語は、この意味で帰納的可算である（句構造言語の定理「Turing 機械との同値性」）。すべての入力で停止する機械が判定する言語は帰納的言語である。

帰納的可算集合の例

決定可能な集合 $A$ は帰納的可算である。$f(x):\simeq\mu y\,[\,x\in A\,]$ は $x\in A$ のときだけ定義される（停止問題の定理「決定可能性と半決定可能性」の証明の前半）。素数の全体、平方数の全体などがその例である。
自己停止集合 $K:=\{e\mid\varphi_e(e)\!\downarrow\}$ は帰納的可算で、決定可能でない（計算可能性理論の定義「自己停止集合と全域性の集合」と定理「自己停止集合の決定不能性」）。$K$ は $x\mapsto\mu s\,T(x,x,s)$ の定義域である。
$\{e\mid W_e\ne\emptyset\}$ は帰納的可算である。$e\mapsto\mu w\,T(e,(w)_0,(w)_1)$ の定義域だからである。
整数係数の多項式 $p(x_1,\dots,x_k)$ のとる $0$ 以上の値の集合 $\{p(\vec x)\mid\vec x\in\mathbb{N}^k,\ p(\vec x)\ge0\}$ は帰納的可算である。$y\mapsto\mu w\,[\,p((w)_0,\dots,(w)_{k-1})=y\,]$ の定義域だからである。

帰納的可算でない集合の例は、$K$ の補集合 $\mathbb{N}\setminus K$（cor-re-complement）や、全域的な関数の番号の集合 $\mathrm{Tot}$（計算可能性理論の定理「全域性の集合とその補集合はどちらも半決定可能でない」）である。

同値な言い換え

帰納的可算集合の言い換え

$A\subset\mathbb{N}$ について、次は同値である。

$A$ は帰納的可算である（ある部分計算可能関数の定義域である）。
$A=\emptyset$ であるか、ある計算可能関数 $g\colon\mathbb{N}\to\mathbb{N}$ の値域 $g(\mathbb{N})$ である。
$A$ はある部分計算可能関数 $\psi$ の値域 $\psi(\operatorname{dom}\psi)$ である。
決定可能な関係 $R\subset\mathbb{N}^2$ があって、$A=\{x\mid\exists y\ R(x,y)\}$ である。
原始再帰的な関係 $R\subset\mathbb{N}^2$ があって、$A=\{x\mid\exists y\ R(x,y)\}$ である。

2 は「計算可能な手順で $A$ の元を（重複を許して）並べ上げられる」こと、4 と 5 は「$x\in A$ の証拠 $y$ があり、証拠が正しいかどうかは決定できる」ことを述べている。

1 ⇒ 5 ⇒ 4 ⇒ 2 ⇒ 3 ⇒ 1 の順に示す

1 ⇒ 5：$A=W_e$ とすると、「記法と前提」により $x\in A\iff\exists s\,T(e,x,s)$ であり、$R(x,s):\Leftrightarrow T(e,x,s)$ は原始再帰的である。
5 ⇒ 4：原始再帰的な関係の特性関数は原始再帰関数なので計算可能であり、関係は決定可能である。
4 ⇒ 2：$A\ne\emptyset$ とし、$a\in A$ を 1 つとる。
$$ g(w):=\begin{cases}(w)_0 & R\bigl((w)_0,(w)_1\bigr)\text{ のとき}\\ a & \text{そうでないとき}\end{cases} $$
とおく。$g(w)=(w)_0\cdot\chi_R((w)_0,(w)_1)+a\cdot\bigl(1\mathbin{\dot-}\chi_R((w)_0,(w)_1)\bigr)$ は計算可能関数の合成なので計算可能関数である。$g$ の値は $(w)_0$（このとき $R((w)_0,(w)_1)$ なので $(w)_0\in A$）か $a$ なので、$g(\mathbb{N})\subset A$ である。逆に $x\in A$ なら $R(x,y)$ となる $y$ があり、$w=\langle x,y\rangle$ で $g(w)=x$ である。よって $g(\mathbb{N})=A$ である。
2 ⇒ 3：計算可能関数 $g$ は定義域が $\mathbb{N}$ の部分計算可能関数である。$A=\emptyset$ なら、どこでも定義されない部分計算可能関数 $\psi(x):\simeq\mu y\,[\,x+y+1=0\,]$ の値域が $\emptyset$ である。
3 ⇒ 1：$\psi=\varphi_e$ とする。「記法と前提」により、$x$ が $\psi$ の値域に属することは、ある $u,s$ について
$$ Q(x,u,s):\Longleftrightarrow T(e,u,s)\ \land\ \forall t< s\ \lnot T(e,u,t)\ \land\ V(e,u,s)=x $$
が成り立つことと同値である。$Q$ は原始再帰的な関係なので、$h(x):\simeq\mu w\,\bigl[\,Q\bigl(x,(w)_0,(w)_1\bigr)\,\bigr]$ は部分計算可能関数であり、$h(x)$ が定義されるのは $Q(x,u,s)$ となる $u,s$ があるとき、すなわち $x\in\psi(\operatorname{dom}\psi)$ のときちょうどである。よって $A=\operatorname{dom}h$ は帰納的可算である。$\square$

同じ証明で、$A\subset\mathbb{N}^k$ が帰納的可算であることは、決定可能な（原始再帰的な）関係 $R\subset\mathbb{N}^{k+1}$ で $A=\{\vec x\mid\exists y\ R(\vec x,y)\}$ と書けることと同値である（1 ⇒ 5 では $\varphi^{(k)}_e(\vec x)\simeq\varphi_e(\langle\vec x\rangle)$ を使う）。無限集合については、2 の $g$ を単射にとれること、狭義単調増加にとれるのは $A$ が決定可能なときに限ることが計算可能関数の定理「無限集合の枚挙」にある。

閉包性

帰納的可算集合の閉包性

$A,B\subset\mathbb{N}$ を帰納的可算集合、$R\subset\mathbb{N}^2$ を帰納的可算な関係、$f\colon\mathbb{N}\to\mathbb{N}$ を計算可能関数、$\psi$ を部分計算可能関数とする。このとき次の集合はどれも帰納的可算である。

和集合 $A\cup B$ と共通部分 $A\cap B$。
射影 $\{x\mid\exists y\ R(x,y)\}$。
逆像 $f^{-1}(A)$ と像 $\psi(A\cap\operatorname{dom}\psi)$。

要点：thm-re-equivalent の 5 の形 $A=\{x\mid\exists s\ P(x,s)\}$、$B=\{x\mid\exists s\ P'(x,s)\}$（$P,P'$ は原始再帰的）に直し、存在量化された変数を 1 つの符号にまとめる。

詳しい証明を開く

1：$x\in A\cup B\iff\exists s\,[\,P(x,s)\lor P'(x,s)\,]$、$x\in A\cap B\iff\exists w\,[\,P(x,(w)_0)\land P'(x,(w)_1)\,]$ で、角括弧の中は原始再帰的なので、thm-re-equivalent の 5 ⇒ 1 による。2：定理の後の注意により $R=\{(x,y)\mid\exists s\ P''(x,y,s)\}$（$P''$ は原始再帰的）と書けるので、$\exists y\,R(x,y)\iff\exists w\ P''(x,(w)_0,(w)_1)$ である。3：$x\in f^{-1}(A)\iff\exists s\ P(f(x),s)$ で、$P(f(x),s)$ は決定可能なので 4 ⇒ 1 による。像については、$\psi=\varphi_e$ として、$y$ が像に属することは $\exists w\,\bigl[\,P((w)_0,(w)_1)\land Q'\bigr]$ と同値である。ここで $Q'$ は $(w)_0=u$、$(w)_2=s$ について「$T(e,u,s)\land\forall t< s\,\lnot T(e,u,t)\land V(e,u,s)=y$」を表す原始再帰的な関係である。よって 5 ⇒ 1 による。$\square$

補集合については閉じていない。

補集合が帰納的可算でない集合

$K$ の補集合 $\mathbb{N}\setminus K$ は帰納的可算でない。一般に、帰納的可算な $A$ の補集合が帰納的可算であるのは、$A$ が決定可能なときに限る。

後半は停止問題の定理「決定可能性と半決定可能性」そのものである。$K$ は帰納的可算で決定可能でない（ex-re-examples の 2）ので、後半により $\mathbb{N}\setminus K$ は帰納的可算でない。$\square$

段階ごとの近似と決定可能な部分集合

$W_e$ は、計算を $s$ 段まで動かして分かる部分の和として、決定可能な有限集合の増大列で近似できる。

段階ごとの近似

$W_{e,s}:=\{x< s\mid\exists t< s\ T(e,x,t)\}$ とおく。関係「$x\in W_{e,s}$」は $(e,s,x)$ について原始再帰的であり、各 $W_{e,s}$ は有限集合で、$W_{e,s}\subset W_{e,s+1}$、$W_e=\bigcup_sW_{e,s}$ である。とくに $\{\langle e,x\rangle\mid x\in W_e\}$ は帰納的可算である。

要点：有界量化子は原始再帰性を保ち、$x\in W_e$ なら $T(e,x,t)$ となる $t$ をとって $s> \max(x,t)$ とすればよい。

詳しい証明を開く

$\exists t< s$ は有界な存在量化なので、関係は原始再帰的である。$W_{e,s}\subset\{0,\dots,s-1\}$ は有限で、$s$ を増やすと条件が弱まるので単調増加である。$x\in W_e$ なら $T(e,x,t)$ となる $t$ があり、$s:=\max(x,t)+1$ で $x\in W_{e,s}$ である。逆は「記法と前提」の同値による。最後の集合は $\{z\mid\exists s\ [\,z=\langle(z)_0,(z)_1\rangle\land(z)_1\in W_{(z)_0,s}\,]\}$ で、thm-re-equivalent の 5 ⇒ 1 による。$\square$

無限の決定可能な部分集合

無限の帰納的可算集合 $A$ は、無限の決定可能な部分集合をもつ。

要点：$A$ を並べた列から、それまでの最大値を更新する項だけを拾うと、狭義単調増加な計算可能関数が得られる。

詳しい証明を開く

thm-re-equivalent により $A=g(\mathbb{N})$ となる計算可能関数 $g$ をとる。$h(0):=g(0)$、$h(n+1):=g\bigl(\mu k\,[\,g(k)> h(n)\,]\bigr)$ とおく。$A$ は無限集合なので、どの $v$ についても $g(k)> v$ となる $k$ があり、μ 作用素の探索は止まる。よって $h$ は全域的な μ再帰関数、すなわち計算可能関数で、狭義単調増加であり、$h(\mathbb{N})\subset A$ は無限集合である。計算可能関数の定理「無限集合の枚挙」の 2 により $h(\mathbb{N})$ は決定可能である。$\square$

単純集合

補集合が無限の帰納的可算集合 $A$ が決定可能でないことを示す典型的な方法は、$K$ を $A$ に還元することである（計算可能性理論）。ところが、還元とは別の形で決定可能でないことが分かる帰納的可算集合がある。

単純集合

帰納的可算集合 $S\subset\mathbb{N}$ で、補集合 $\mathbb{N}\setminus S$ が無限集合であり、しかも $\mathbb{N}\setminus S$ が無限の帰納的可算集合を 1 つも部分集合として含まないものを 単純集合（simple set）という。言い換えると、$S$ はどの無限の帰納的可算集合とも共通部分をもつ。

単純集合の存在

単純集合が存在する。単純集合は決定可能でない。

各 $W_e$ から $2e$ より大きい元を 1 つずつ取る

段 1（構成）。
$$ \psi(e):\simeq\Bigl(\mu w\,\bigl[\,T\bigl(e,(w)_0,(w)_1\bigr)\land(w)_0> 2e\,\bigr]\Bigr)_0 $$
とおく。$\psi$ は部分計算可能関数である。$\psi(e)$ が定義されるのは $W_e$ に $2e$ より大きい元があるときちょうどであり、そのとき $\psi(e)$ はそのような元の 1 つである（$T(e,(w)_0,(w)_1)$ から $(w)_0\in W_e$）。$S:=\psi(\operatorname{dom}\psi)$ とおく。thm-re-equivalent の 3 により $S$ は帰納的可算である。
段 2（補集合は無限）。$n\ge1$ とする。$S$ の元で $2n$ 以下のものは、$\psi(e)\le2n$ となる $e$ の値 $\psi(e)$ である。$\psi(e)> 2e$ なので $2e< 2n$、すなわち $e< n$ であり、そのような $e$ は $n$ 個しかない。よって $\{0,1,\dots,2n\}$ の $2n+1$ 個の数のうち $S$ に属するのは $n$ 個以下で、$n+1$ 個以上が補集合に属する。$n$ は任意なので、補集合は無限集合である。
段 3（無限の帰納的可算集合と交わる）。$C$ を無限の帰納的可算集合とし、$C=W_e$ とする。$C$ は無限なので $2e$ より大きい元をもち、段 1 により $\psi(e)$ が定義されて $\psi(e)\in W_e\cap S$ である。よって $C\not\subset\mathbb{N}\setminus S$ である。以上で $S$ は単純集合である。
段 4（決定可能でない）。単純集合 $S$ が決定可能なら、補集合 $\mathbb{N}\setminus S$ も決定可能なので帰納的可算であり（ex-re-examples の 1）、無限集合である。これは $\mathbb{N}\setminus S$ に含まれる無限の帰納的可算集合なので、定義に反する。$\square$

この構成は Post による（Pos44 §5、pp. 298–299。そこでは正の整数の集合で同じ構成をしている）。単純集合は、帰納的可算で決定可能でないという点では $K$ と同じだが、補集合の性質が違う。Post はさらに、創造的集合、とくに $\{\langle e,x\rangle\mid x\in W_e\}$ に当たる彼の完全な集合を、単純集合へ有界な真理表による還元（多対一還元はその特別な場合）で還元できないことを示した（Pos44 §6–§7、p. 304。この記事では証明しない）。完全な集合にはすべての帰納的可算集合が多対一還元されるので、単純集合は計算可能性理論の定義「完全な計算可能枚挙集合」の意味で完全ではない。Post は単純集合を、$K$ より決定の難しさの低い、決定可能でない帰納的可算集合の候補として導入した（Pos44 p. 299）。
単純集合の補集合は無限集合だが、prop-re-decidable-subset の結論が成り立たない。無限の決定可能な部分集合があれば、それは帰納的可算なので単純集合の定義に反するからである。

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

外す条件	反例	成り立たなくなること
cor-re-complement の「$A$ が決定可能」	自己停止集合 $K$	$K$ は帰納的可算だが、補集合は帰納的可算でない
thm-re-equivalent の 4 の「ある $y$ が存在する」（「すべての $y$ について」に替える）	$\mathbb{N}\setminus K=\{x\mid\forall s\ \lnot T(x,x,s)\}$	決定可能な関係の全称量化で書けるが、帰納的可算でない
prop-re-closure の 1 の「2 つの集合」（有限個）	$\mathbb{N}\setminus K=\bigcup_{x\notin K}\{x\}$	1 点集合は帰納的可算だが、無限個の和集合は帰納的可算とは限らない
prop-re-decidable-subset の「$A$ が帰納的可算」	単純集合の補集合	無限集合だが、無限の決定可能な部分集合をもたない

反例の確かめ

$K$ が帰納的可算で決定可能でないことは ex-re-examples の 2、補集合が帰納的可算でないことは cor-re-complement による。
「記法と前提」により $x\in K\iff\exists s\ T(x,x,s)$ なので、$x\notin K\iff\forall s\ \lnot T(x,x,s)$ であり、$\lnot T(x,x,s)$ は原始再帰的な関係である。それでも $\mathbb{N}\setminus K$ は帰納的可算でない（cor-re-complement）。
1 点集合 $\{x\}$ は決定可能なので帰納的可算である。$\mathbb{N}\setminus K$ はそれらの和集合だが帰納的可算でない。prop-re-closure の証明は 2 つの集合の証拠を 1 つの符号にまとめるので、無限個では「どの集合の証拠か」を計算できる形で選べない。
thm-re-simple の単純集合 $S$ について、$\mathbb{N}\setminus S$ は無限集合で、すぐ上の段落により無限の決定可能な部分集合をもたない。

補足

呼び名．「帰納的」は recursive の訳で、計算可能関数をかつて帰納的関数（recursive function）とよんだことによる。現在は computably enumerable（c.e.）の呼び名もよく使われる（OLT26 §30.10、p. 455）。
算術の論理式との関係．thm-re-equivalent の 5 は、帰納的可算集合が「原始再帰的な関係に存在量化子を 1 つ付けた形」で書ける集合であることを述べている。決定可能な集合はこの形とその否定の形（全称量化子 1 つ）の両方で書ける集合である（cor-re-complement）。
文献．thm-re-equivalent と同じ内容は OLT26 Theorem 30.9（p. 455、証明は pp. 456–457）と Theorem 30.10（p. 457）に、和集合と共通部分の閉包性は Theorem 30.13（pp. 458–459）にある。