Question: If $A \subseteq \Bbb N$ and $f:\Bbb N \to \Bbb N$ is a function, then let $f(A)=\{ n \in \Bbb N \mid \exists m \in A \text{ such that } f(m)=n \}$ and $f^{-1}(A)=\{ n \in \Bbb N \mid f(n) \in A \}$.
Prove that if $f$ is a total recursive function and $A \subseteq \Bbb N$ is recursively enumerable then $f(A)$ and $f^{-1}(A)$ are recursively enumerable.
I tried:
Definition. Let $B$ be a set of $\Bbb N$. $B$ is recursively enumerable if there exists a total recursive function $g$ such that $B= \{g(0),g(1),g(2),g(3),\ldots \}$.
So a set is recursively enumerable if it is the range of some total recursive function.
$\operatorname{rng}(f(A))=\Bbb N$ so $f(A)$ is recursively enumerable.
$f^{-1}(A)=A$ so $f^{-1}(A)$ is recursively enumerable.
Hints?
Best Answer
So your definition says of $A$ that there is a total recursive function $g$ that enumerates $A$, i.e., such that $A =\{ g(0), g(1), g(2), \ldots \}$. Let us fix some such function $g$, then we have: $$ f(A) = (f(g(0)), f(g(1)), f(g(2)), \ldots \} $$ so the total recursive function $f \circ g$ that composes $f$ with $g$ enumerates $f(A)$.
To show that $f^{-1}(A)$ is recursively enumerable, it is easiest to use an alternative characterisation of recursively enumerable set: a set is recursively enumerable if it is the domain of some partial recursive function. (See here. If you don't know about this, please add a comment to say so and I can say more). To see that $f^{-1}(A)$ is recursively enumerable according to this alternative characterisation, define a partial recursive function $h$, that given an argument $x$ first calculates $y = f(x)$ and then (with $g$ as in the previous paragraph) calculates $g(0)$, g(1), $g(2), \ldots$, halting when it finds an $n$ with $y = g(n)$. The domain of $h$ is then $f^{-1}(A)$.
As a small aside: it it usual to consider the empty set to be recursively enumerable. So the definition in terms of an enumerating function should say $B$ is recursively enumerable if $B$ is empty or if there exists a total recursive function that enumerates $B$.