The existence of computable injection

Question

Let $A\in \mathbb N$ be an infinite recursively enumerable set. Prove that there exists a computable injection $f:\mathbb N \to \mathbb N$ such that $\text{rng}f=A$

I'm not quite understand how to prove the existence. This statement doesn't follow immediately from the definitions?

Answer 1

How we solve this question depends a bit on how we define "recursively enumerable." The right definition in my opinion is

A set $A\subseteq\mathbb{N}$ is r.e. if there is some computable partial function $f$ with $dom(f)=A$.

Another definition sometimes given is

A set $A\subseteq\mathbb{N}$ is r.e. if it is the range of some total computable function $g$ (or is empty).

One reason this is a bit less satisfying is the need for a special case to handle the empty set, but there are other more subtle reasons why the former is preferable.

(We could also equivalently define a set to be r.e. if it is the range of some partial computable function; it's a good exercise to show that all three of these definitions are in fact equivalent.)

The latter definition is closer to the property in the question above; however, it still doesn't solve it trivially, since in your problem you want the function to be injective. And the former definition is about domains, not ranges, so is even further from what you want.

---

It might help build intuition to consider the following "injectivization" problem:

• Suppose $h$ is a total computable function with infinite range. Show that there is a total injective function $j$ with the same range.

If you use the second definition of r.e. given above, then this is just a more concrete (in my opinion) way to rephrase your problem; if you use the first definition of r.e. given above, then this is a different problem, but still closely related.