The claim is false. This is essentially a resurrection of Carl Mummert's answer with a bit more detail added:
Let $\psi_0, \psi_1, \psi_2, \ldots$ be a recursive enumeration of all primitive recursive single-argument functions, possibly with repetition. (Primitive recursive functions are exactly those that can be programmed using standard integer arithmetic, if conditionals and for loops with predetermined bounds, so for example $\psi_i$ could be defined by checking if the binary representation of $i$ is syntactically such a program -- if not $\psi_i$ will simply be the zero function).
Now define
$$f(n) = 1+\max_{i,j\le n} \psi_i(j)$$
and let $A$ be the range of $f$. Since $f$ is clearly (weakly) increasing as well as recursive, $A$ is recursive. I claim that $A$ is not the range of any primitive recursive injection.
Indirect proof. Assume that $\psi_q$ is a primitive recursive injection whose range is $A$. Since $f$ has the same range, there must be a $g:\mathbb N\to\mathbb N$ such that $\psi_q(n)=f(g(n))$ for all $n$. Since $\psi_q(n)$ is injective, so is $g$.
Since $g:\mathbb N\to\mathbb N$ is an injection, there must be infinitely many $m$ such that $g(m)\ge m$. (Namely, if $g(m)<m$ for all $m\ge N$, then let $K=\max\{N,g(0),g(1),g(2),\ldots,g(N)\}$. Then $g$ maps $\{0,1,2,\ldots,K+1\}$ injectively to $\{0,1,2,\ldots,K\}$, which is impossible).
Choose therefore $m\ge q$ such that $g(m)\ge m$. Then
$$ \psi_q(m)=f(g(m)) \ge f(m) = 1+\max_{i,j\le m} \psi_i(j) \ge 1+\psi_q(m) > \psi_q(m) $$
since $f$ is increasing and $q\le m$. But that is impossible, so $\psi_q$ cannot exist.
$A$ cannot be the range of a primitive recursive injection $\phi(x_1,\ldots,x_k)$ with more than one argument either, because if that were the case we could bundle the arguments together with a surjective tupling function whose projectionts $\pi_1,\ldots,\pi_k$ are primitive recursive (constructing such tupling functions are routine), and $A$ would then be the range of the primitive recursive $x\mapsto \phi(\pi_1(x),\ldots,\pi_k(x))$.
Best Answer
Okay, so a couple of things.
Suppose that you know the index $e$ such that $\varphi_e$ is the indicator function for a nonempty recursive set $A$ (so we are promised that $\varphi_e$ is total recursive and not identically zero). Then:
- If you don't mind repeating elements, take $f(e,n) = n$ if $\varphi_e(n) = 1$ and $f(e, n) = f(e, n-1)$ otherwise, while $f(e, 0) = \mu x(\varphi_e(x) =1)$.
- If you don't like repeating elements in your enumeration of infinite recursive sets, you are out of luck. Determining whether $\varphi_e$ is eventually $0$ (i.e., $A$ is finite) is not a computable task, nor is determining whether it is identically zero. You could solve the halting problem if you could solve this.
This function of course doesn't converge for most $n$ when $\varphi_e$ is not total recursive (or when $\phi_e$ is never $1$). If you need $f(e,n)$ to be an increasing enumeration when $\varphi_e$ is total recursive and the indicator function for a nonempty recursive set, and also be a total recursive function, you are again out of luck. Once again this would solve the halting problem.