Recursively enumerable set is an image of primitive recursive function

Question

My definition of R.E set is that it is R.E if it is the image of some Partial Recursive Function. How can I show that if this set is definately non-empty then it is an image of Primitive Recursive Function?

Answer 1

Let $A \subseteq \mathbb{N}$ be nonempty and r.e.

Fix $a \in A$ and $f(x)$ partial recursive with image $A$.

Define a new function $F(x,n)$ where $ F(x,n) = \begin{cases} f(x) & f(x) \downarrow \text{in $\leq n$ steps}\\ a & \text{otherwise} \end{cases} $

Then $F$ is primitive recursive (cf. Kleene's T Predicate) and has the same image as $f$.

So $A$ is the image of a primitive recursive function, as desired.

---

Hope this helps ^_^