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

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?

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$:
1. Compute $x=F(k)$.
2. If $x\in S$ already, then continue with the next $k$.
3. Add $x$ to $S$.
4. If $|S|=n+1$, then output $x$ and stop.
5. 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.

• However, $F$ is partial, not necessarily total. – BrianO Apr 7 '16 at 9:53
• @BrianO: No -- it's easy to overlook, but the context of the claim was "The set $S$ is the range of a total recursive function or empty." The function that can be chosen to be injective (for an infinite set) is the one whose range is $S$, not the partial one in the previous paragraph whose domain was $S$. – hmakholm left over Monica Apr 7 '16 at 9:56
• Ya know, ... I did overlook it, and it was easy ;) I used just the given definition of r.e. in the first paragraph — needlessly, I now think, as OP seems OK with the first claim in the second paragraph (that context you mention). – BrianO Apr 7 '16 at 10:01
• @HenningMakholm In step 6, when you say "add $x$ to $S$, do you mean include the element $x$ in the set $S$? Thanks! – faux Apr 7 '16 at 13:33
• @faux: Yes, $S := S \cup \{x\}$. – hmakholm left over Monica Apr 7 '16 at 13:45

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):