I want to show the following claim: An infinite recursively enumerable subset of the natural numbers is the image of an injective recursive function.
What I know is that given a r.e. set $A\subset \mathbb{N}$, by definition I get a recursive set $B\subset \mathbb{N}^2$ s.t. $A=\{a\in\mathbb{N}:\exists m\in\mathbb{N}s.t.(a,m)\in B\}$. To show that this is the image of a recursive function I can define $f:\mathbb{N}\rightarrow\mathbb{N}$ with $f(n)=((n)_0,(n)_1)$ if there exists an $m$ such that $(n,m)\in B$, and $f(n)=k$ otherwise, where k is any element of A and $(n)_i=\beta(n,i+1)$. This function is only injective if $A=\mathbb{N}$ though.
Any hints?
One program that will work can be constructed as follows. First, there is a computable listing of all the pairs $(x,y)$ in $\mathbb{N}^2$. For example, the listing might begin $$(0,0), (0,1), (1,0), (0,2), (1,1), (2,0), \ldots$$
On input $n$, your program will search through this enumeration in order until it finds $n$ pairs that are in $B$ and that have different first elements. Then it will return the first element of the final pair that was found, again using the order on all pairs to decide which was the "last" pair found.
The verification that this is a computable operation relies on the fact that $B$ is computable, so there is an effective way to decide whether each pair is in $B$. Also, because the original set $A$ is infinite, you can show that the program halts for all $n$ - if you run it long enough on input $n$, it must eventually find $n$ different values for the initial element of the pair, or else $A$ would be finite.
You will not produce an equation or formula for the program - just a description of how it works and a verification that it is correct (and that the method it uses is effective).