Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
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
add comment

1 Answer

up vote 1 down vote accepted

Hint to get you started:

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.

share|improve this answer
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
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.