多対一還元

1. 恒等写像は還元で、還元の合成は還元である。単射の合成は単射である。

2. 同じ $f$ について $x\notin A\iff f(x)\notin B$ である。

3. 特性関数について $\chi_A=\chi_B\circ f$ である。

4. $B=\operatorname{dom}\psi$ なら $A=\operatorname{dom}(\psi\circ f)$ である。$\square$

1. $\emptyset\le_{\mathrm m}A$ の還元 $f$ の値はすべて $A$ の外にあるので $A\neq\mathbb{N}$ である。逆に $a\notin A$ なら定数 $a$ が還元である。$\mathbb{N}\le_{\mathrm m}A$ についても同様である。$A\equiv_{\mathrm m}\emptyset$ なら $A\le_{\mathrm m}\emptyset$ の還元 $f$ は $x\in A\iff f(x)\in\emptyset$ を満たすので $A=\emptyset$ である。$\mathbb{N}$ も同様である。

2. $a\in A$、$a'\notin A$ をとり、$f(x):=a$（$x\in B$）、$f(x):=a'$（$x\notin B$）とおく。$B$ が決定可能なので $f$ は計算可能で、還元である。

3. $x\mapsto2x$ と $x\mapsto2x+1$ が還元である。$f,g$ がそれぞれ $A,B$ から $C$ への還元なら、$h(2x):=f(x)$、$h(2x+1):=g(x)$ が $A\oplus B$ から $C$ への還元である。

4. $\overline K\le_{\mathrm m}K$ なら prop-manyone-basic の 4 により $\overline K$ が半決定可能になり、矛盾する。$K\le_{\mathrm m}\overline K$ なら prop-manyone-basic の 2 により $\overline K\le_{\mathrm m}K$ であり、同じく矛盾する。$\square$

1. $x\mapsto\langle x,0\rangle$ は単射な還元、$\langle x,n\rangle\mapsto x$ は還元である。

2. $f$ が $A$ から $B$ への還元なら、$x\mapsto\langle f(x),x\rangle$ は単射で、$x\in A\iff f(x)\in B\iff\langle f(x),x\rangle\in B\times\mathbb{N}$ である。逆に $A\le_1B\times\mathbb{N}$ なら、1 の $B\times\mathbb{N}\le_{\mathrm m}B$ と合成して $A\le_{\mathrm m}B$ である。

3. $f$ が $A$ から $B$ への還元なら、$\langle x,n\rangle\mapsto\langle f(x),\langle x,n\rangle\rangle$ は $A\times\mathbb{N}$ から $B\times\mathbb{N}$ への単射な還元である。逆に $A\times\mathbb{N}\le_1B\times\mathbb{N}$ なら、1 により $A\le_1A\times\mathbb{N}\le_1B\times\mathbb{N}\le_{\mathrm m}B$ である。$\square$

段 1（番号の族）．$(\langle c,a\rangle,y)\mapsto\varphi_c(\langle a,y\rangle)$ に (S) を使い、計算可能関数 $r(c,a)$ で、すべての $c,a,y$ について $\varphi_{r(c,a)}(y)\simeq\varphi_c(\langle a,y\rangle)$ となるものをとる。

段 2（プログラム）．$a=\langle j,\langle e,m\rangle\rangle$ の形の数について、次の部分計算可能関数を定める。

$$g(c,\langle a,y\rangle):\simeq\begin{cases}\varphi_e(y)&(r(c,\langle i,\langle e,m\rangle\rangle)\ (0\le i\le m)\text{ が互いに異なるとき}),\\ j&(\text{そうでないとき}).\end{cases}$$

Kleeneの再帰定理 の定理により、すべての $w$ で $\varphi_c(w)\simeq g(c,w)$ となる番号 $c$ がある。この $c$ を固定し、$r_i:=r(c,\langle i,\langle e,m\rangle\rangle)$ とおく。すると $\varphi_{r_j}(y)\simeq g(c,\langle\langle j,\langle e,m\rangle\rangle,y\rangle)$ である。

段 3（重なりの排除）．ある $i\neq i'$ で $r_i=r_{i'}$ とする。場合分けの 2 行目により $\varphi_{r_i}$ は定数 $i$、$\varphi_{r_{i'}}$ は定数 $i'$ であるが、番号が等しいので同じ関数でなければならず、矛盾する。よって $r_0,\dots,r_m$ は互いに異なり、場合分けの 1 行目により $\varphi_{r_i}=\varphi_e$ である。

段 4．$m:=|D_n|$ とすると、$m+1$ 個の異なる数 $r_0,\dots,r_m$ の少なくとも 1 つは $D_n$ に属さない。最小の添字のものを $P(e,n)$ とする。$P$ は計算可能である。$\square$

prf-manyone-fresh の段 1 の $r$ を使う。$c,x$ から $u_c(x)$ を、$x$ についての再帰で

$$u_c(x):=P\bigl(r(c,x),\ n_x\bigr),\qquad D_{n_x}=\{u_c(0),\dots,u_c(x-1)\}$$

と定める。$(c,x)\mapsto u_c(x)$ は計算可能で、$c$ を固定すると $x\mapsto u_c(x)$ は単射であり、$\varphi_{u_c(x)}=\varphi_{r(c,x)}$ である。再帰定理により、すべての $x,y$ で $\varphi_c(\langle x,y\rangle)\simeq g(u_c(x),x,y)$ となる $c$ がある（右辺は $c,\langle x,y\rangle$ の部分計算可能関数である）。この $c$ について $u:=u_c$ とおくと、

$$\varphi_{u(x)}(y)\simeq\varphi_{r(c,x)}(y)\simeq\varphi_c(\langle x,y\rangle)\simeq g(u(x),x,y)$$

である。$\square$

準備．$\psi(\langle e,a\rangle,y):\simeq\mu s\,[\,y=a\text{ または }T(e,y,s)\,]$ に (S) を使うと、計算可能関数 $t$ で $W_{t(e,a)}=W_e\cup\{a\}$ となるものが得られる。$p$ を生産関数とするとき、$e_0:=e$、$e_{k+1}:=t(e_k,p(e_k))$、$a_k:=p(e_k)$ とおく。$W_e\subset P$ なら、$k$ についての帰納法で $W_{e_k}\subset P$、$a_k\in P\setminus W_{e_k}$ であり、$l< k$ なら $a_l\in W_{e_k}$ なので $a_k\neq a_l$ である（$\ast$）。

1. $W_e\subset\overline K$ とする。$e\in W_e$ なら $e\in K$ かつ $e\in W_e\subset\overline K$ となって矛盾するので $e\notin W_e$ である。すると $\varphi_e(e)\!\uparrow$、すなわち $e\in\overline K$ である。よって $e\in\overline K\setminus W_e$ である。

2. $p$ を $P$ の生産関数、$f$ を還元とする。(S) で $\varphi_{h(e)}(y)\simeq\varphi_e(f(y))$ となる $h$ をとると $W_{h(e)}=f^{-1}(W_e)$ である。$W_e\subset Q$ なら $W_{h(e)}\subset P$ なので、$b:=p(h(e))$ は $P\setminus W_{h(e)}$ に属する。よって $f(b)\in Q$ かつ $f(b)\notin W_e$ であり、$f\circ p\circ h$ が $Q$ の生産関数である。

3. $P=W_e$ なら $p(e)\in P\setminus P$ となって矛盾する。$W_e=\emptyset$ となる $e$ から始めると、（$\ast$）により $k\mapsto a_k$ は $P$ に値をとる単射な計算可能関数であり、その値域が求める部分集合である。

4. $p$ を生産関数とし、$p'(e)$ を $e$ についての再帰で定める。$L:=\{p'(0),\dots,p'(e-1)\}$ とおき、$a_0,a_1,\dots$ を順に計算して、次のどちらかが最初に起きた $k$ で止める。(a) $a_k\notin L$ なら $p'(e):=a_k$ とする。(b) ある $l< k$ で $a_k=a_l$ なら、$L$ に属さない最小の数を $p'(e)$ とする。$a_k$ に重なりがなければ有限集合 $L$ の外の値がいつか現れるので、計算は必ず止まり、$p'$ は単射で計算可能である。$W_e\subset P$ なら（$\ast$）により (b) は起きず、$p'(e)=a_k\in P\setminus W_{e_k}\subset P\setminus W_e$ である。$\square$

2 ⇒ 1．$K\le_{\mathrm m}C$ なので prop-manyone-basic の 2 により $\overline K\le_{\mathrm m}\overline C$ であり、prop-manyone-productive の 1・2 により $\overline C$ は生産的である。

1 ⇒ 3 の段 1（$K$ は 1 完全）．$B=W_b$ を半決定可能とする。lem-manyone-fix を $g(q,x,y):\simeq\varphi_b(x)$ に使うと、単射な計算可能関数 $u$ で $\varphi_{u(x)}(y)\simeq\varphi_b(x)$ となるものがある。$x\in B$ なら $\varphi_{u(x)}$ は全域的なので $u(x)\in K$ であり、$x\notin B$ なら $\varphi_{u(x)}$ はどこでも定義されないので $u(x)\notin K$ である。よって $B\le_1K$ である。

段 2（$K\le_1C$）．$\overline C$ の単射な生産関数 $p$ をとる（prop-manyone-productive の 4）。部分計算可能関数

$$g(q,x,y):\simeq\begin{cases}0&(\varphi_x(x)\!\downarrow\text{ かつ }y=p(q)),\\ \text{定義されない}&(\text{それ以外})\end{cases}$$

に lem-manyone-fix を使い、単射な $u$ をとる。$\varphi_{u(x)}(y)\simeq g(u(x),x,y)$ なので、$x\in K$ なら $W_{u(x)}=\{p(u(x))\}$、$x\notin K$ なら $W_{u(x)}=\emptyset$ である。$t:=p\circ u$ は単射な計算可能関数である。$x\notin K$ なら $W_{u(x)}=\emptyset\subset\overline C$ なので $t(x)\in\overline C$ である。$x\in K$ で $t(x)\in\overline C$ とすると $W_{u(x)}=\{t(x)\}\subset\overline C$ なので、生産関数の性質から $t(x)=p(u(x))\notin W_{u(x)}$ となり矛盾する。よって $t(x)\in C$ である。したがって $x\in K\iff t(x)\in C$ である。

段 3．任意の半決定可能な $B$ について、段 1・2 と prop-manyone-basic の 1 により $B\le_1K\le_1C$ である。$\square$

$f\colon A\le_1B$、$g\colon B\le_1A$ をとる。有限の部分写像の列 $\pi_0=\emptyset\subset\pi_1\subset\cdots$ で、各 $\pi_s$ が単射であり、$\pi_s$ の定義域の各 $x$ で $x\in A\iff\pi_s(x)\in B$ を満たすものを作る。

奇数段 $s+1=2n+1$（定義域に $n$ を入れる）．$n\in\operatorname{dom}\pi_s$ なら $\pi_{s+1}:=\pi_s$ とする。そうでなければ $y_0:=f(n)$ とし、$y_k\in\operatorname{ran}\pi_s$ である間は $y_{k+1}:=f(\pi_s^{-1}(y_k))$ と続ける。$y_0,y_1,\dots$ は互いに異なる。実際、$y_k=y_l$（$k< l$）となる最小の $l$ をとると、$k=0$ なら $f$ の単射性から $n=\pi_s^{-1}(y_{l-1})\in\operatorname{dom}\pi_s$ となって矛盾し、$k>0$ なら $f$ と $\pi_s^{-1}$ の単射性から $y_{k-1}=y_{l-1}$ となって $l$ の最小性に反する。$\operatorname{ran}\pi_s$ は有限なので、ある $y_k$ で $y_k\notin\operatorname{ran}\pi_s$ となって止まる。$\pi_{s+1}:=\pi_s\cup\{(n,y_k)\}$ とおく。$n\in A\iff y_0\in B\iff\pi_s^{-1}(y_0)\in A\iff y_1\in B\iff\cdots\iff y_k\in B$ なので条件は保たれる。

偶数段 $s+1=2n+2$（値域に $n$ を入れる）．$\pi_s^{-1}$、$g$ と $A,B$ の役割を入れ替えて同じことを行う。

$\pi:=\bigcup_s\pi_s$ は $\mathbb{N}$ 全体で定義された全射な単射である。各段の手続きは計算でき、$\pi(x)$ は $\pi_{2x+1}$ を計算すれば求まるので、$\pi$ は計算可能である。$\pi(A)=B$ は条件から従う。$\square$