Given the definition of recursive function as below, I need to prove that:
An infinite subset of $\Bbb N$ is recursive if and only if it is the range of a strictly increasing recursive function.
I think to prove image of increasing recursive function $\implies$ infinite recursive set, we need to construct a recursive characteristic function for the image of any strictly increasing recursive function.
For strictly increasing recursive function $f$, define function $\chi$ by:
$\chi(x) \ = \ \begin{cases} 1 & \text{if } (\exists n\le x)(f(n)=x) \\ 0 & \text{otherwise.}\end{cases}$
$\chi(x)=1$ iff $x$ is in the range of f(x), thus $\chi$ is the characteristic function of the range. As $f$ is strictly increasing and thus injective, its range is an infinite set.
And to prove that infinite recursive set $\implies$ image of increasing recursive function, we need to construct a increasing recursive function using the characterist function of the recursive set.
Given an infinite recursive set $A$ its characteristic function $\chi_A$ is a recursive function.
Define function $f$
$f(0)=min_n \lbrace\chi_A(n)=1\rbrace$
$f(n+1)=min_m\lbrace\chi_A(m)=1\land m>f(n)\rbrace$
It is a recursive function.
In the second direction, I cannot see if there is any usage of the condition: "A" is an infinite set. So may I ask if that condition is necessary?
May I please ask for checking if the argument above is correct, thanks a lot!