Let $\varphi_0,\varphi_1,\varphi_2,\dots$ be an acceptable programming system. A function $f$ is extensional if, for all $x$ and $y$, $\varphi_x=\varphi_y$ implies that $\varphi_{f(x)}=\varphi_{f(y)}$. Now, let $A$ and $B$ index sets such that $A\leq_{m}B$ ($A$ is many-one reducible to $B$). Is there an extensional function $f$ such that $f$ is an $m$-reduction from $A$ to $B$?

## 1 Answer

There is not always such an $f$. Here's a proof.

Let $A$ be the index set of programs computing the total function whose output is $0$ on every input. Let $g$ be the function which takes each $e$ to the program that outputs $e$ on input $0$ and diverges on all other inputs. Let $B$ be the set of programs which have the same behavior as some program in the image of $g$ on $A$. That is, $a$ is in $B$ if it is the code for a program which outputs some $e$ on input $0$ and diverges on all other inputs and $e$ is in $A$.

Note that $A$ is a $\Pi^0_2$-complete set. The idea now is that if there is an extensional many-one reduction from $A$ to $B$ then $A$ is $\Delta^0_2$.

Suppose $f$ is an extensional many-one reduction of $A$ to $B$. Since all programs in $A$ have the same behavior, $f$ must send $A$ to a set of programs in $B$ which all have the same behavior. And by our choice of $B$, that behavior has to be outputting some $e$ on input $0$ and diverging on all other inputs. But this means $A$ is equal to $\{a \mid \phi_{f(a)}(0)\downarrow = e\} \setminus \{a \mid \text{for some } n > 0, \phi_{f(a)}(n)\downarrow\}$. Since these are both r.e. sets, $A$ is the difference of two r.e. sets, hence $\Delta^0_2$. This contradicts the fact that $A$ is $\Pi^0_2$-complete.