A semi-recursive infinite set is the range of some injective recursive total function

Question

The wikipedia article for semi-recursive sets (formally titled "recursively enumerable sets") claims:

A set S of natural numbers is called recursively enumerable if there is a partial recursive function whose domain is exactly S, meaning that the function is defined if and only if its input is a member of S.

The set S is the range of a total recursive function or empty. If S is infinite, the function can be chosen to be injective.

Why in the infinite case can we demand injectivity for the function?

Answer 1

Supposed $F$ is a total recursive function that takes infintely many different values. Then let $G(n)$ be defined by

1. Read $n$.
2. Let $S$ be the empty set.
3. Repeat the following for $k=0,1,2,3\ldots$:
   4. Compute $x=F(k)$.
   5. If $x\in S$ already, then continue with the next $k$.
   6. Add $x$ to $S$.
   7. If $|S|=n+1$, then output $x$ and stop.
   8. Otherwise continue with the next $k$.

Then $G$ has the same range as $F$, and is injective.

Informally $F:\mathbb N\to\mathbb N$ can be viewed as a sequence of natural numbers. The above algorithm corresponds to removing the second and later occurrences of any output in the sequence. As long as there are infinitely many different numbers in the sequence, this still results in an infinite sequence, which will be computable.

Answer 2

When $f$ is a partial recursive function with an infinite range (hence an infinite domain), we can define $g$ by $$ g(n) = f(\,\mu_x(x\in dom(f) \land x\notin range(g\!\restriction\! n))\,) $$ or, less tersely, $$ g(n) = f(x), \text{where $x$ is least s.t. $x\in dom(f)$ and $x\notin range(g\!\restriction\! n))$}. $$ An iterative algorithm for $g$ goes something like this:

def g(n):
    x = 0
    halted = set()    # empty set
    while True:
        # Assertions:
        #     halted = set of pairs (k, f(k))
        #              where k < x and f halts on k in < x steps
        #     |halted| < n
        for each k <= x:
            # Here, dom(halted)   = {1st_coord_of(pair) | pair in halted}
            #       range(halted) = {2nd_coord_of(pair) | pair in halted}
            if k not in dom(halted) and (f halts on k in x steps with value y):
                if y not in range(halted):
                    add (k, y) to halted
                    if |halted| == n:
                        return y
        x = x + 1

This is a bit inefficient (it could save computations that haven't yet halted, and each time through the loop just do one more step for those) but here we're not concerned about complexity.