[Math] All infinite recursive sets can be enumerated by an injective function

computabilityrecursion

Definition: We call a set recursive if its characteristic function is recursive.

Claim: If the recursive set $A\subset\mathbb N$ is infinite then $A=Range(f)$ for some primitive recursive injective function $f$.

Attempt: I already have that recursive sets are the range of some primitive recursive function. I can't find a way to point out such injections for infinite recursive sets.

Best Answer

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))$.

Related Question