# For a one-to-one function is the pullback of a recursively enumerable set $f^{-1}[W_e] = W_{g(e)}$ where $g$ is one-to-one?

Let $\phi_e : \mathbb{N} \to \mathbb{N}$ be the recursive function coded by $e$ and $W_e = \{ x : \phi_e(x) \text{ is convergent}\}$.

A set $A$ is recursively enumerable if $A = W_e$ for some $e$.

Is it true that given a recursive one-to-one function $f : \mathbb{N} \to \mathbb{N}$, that there exists a recursive one-to-one function $g : \mathbb{N} \to \mathbb{N}$ such that $W_{g(e)} = f^{-1}[W_e]$?

I am pretty sure there is a function which does this, since $$x \in f^{-1}[W_e] \iff f(x) \in W_e \iff \phi_e(f(x)) \text{ is convergent}.$$

So $f^{-1}[W_e] = W_{e'}$ for some $e'$ as $\phi_{e'} = \phi_e \circ f$ is recursive. So we let $g(e) = e'$. I think there is some way to apply the $S^m_n$ theorem to get that $g(x)$ is recursive.

Is there a way to show that $g$ is one-to-one? Is it even true that $g$ must be one-to-one? This came up in another proof, and seems like it should be possible for two recursively enumerable sets to pullback to the same set. But I could not find a counter example, and it would help a lot if it were the case.

Can anyone lead me in the right direction?

Edit: Apparently the way the $S^m_n$ functions are defined, they are one-to-one. So the work is in showing $g = S^m_n$ for some $m, n$ and some inputs. Been working on it, but can't seem to hit the nail on the head.

-
Is the one-to-one function you mean is bijective? Or just injective? –  Chao Chen Mar 6 '13 at 7:57
Just injective. –  Danikar Mar 6 '13 at 8:20

Given $f$ unary partial recursive (computable), then the following function is partial recursive as well:
$\Psi (e,x) = \begin{cases} 0 & if \quad f(x)\in W_e\\ \uparrow & \quad \text{otherwise} \end{cases}$
so by the S-M-N Thm we can get a total recursive unary $g$ s.t. $\phi_{g(e)}(x)=\Psi (e,x)$. You can then check that $x\in W_{g(e)}$ iff $f(x)\in W_e$.
There is a generalization of the S-M-N Thm such that the $g$ thus obatained is also injective.
Thanks. I edited my original post with an adaptation of the $S^m_n$ theorem which I think gives me $g(e)$ recursive and injective. I was hoping not to have to actually talk about the the codes at all though. Oh well. –  Danikar Mar 6 '13 at 8:16