# Index sets and extensional many-one reductions

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$$?

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.