Recursive and recursively enumerable functions.

114 Views Asked by At

I am working on the following problem :

If $B\subseteq \mathbb{N}$ and $f : \mathbb{N} \rightarrow \mathbb{N}$ function, then let $$f(B) = \{ n\in \mathbb{N} : \exists m\in B \mbox{ such } \mbox{that } f(m) = n\}$$ and $$f^{-1}(B) = \{ n \in \mathbb{N} : f(n)\in B\}.$$ 1)Show that if $f$ is a total recursive function and $B\subseteq \mathbb{N}$ recursive, then $f^{-1}(B)$ recursive.

2)Show that if $f$ is a total recursive function and $B\subseteq \mathbb{N}$ recursively enumerable, then $f(B)$ and $f^{-1}(B)$ are recursively enumerable.

I am really struggling to come up with a proper proof for both parts. Any ideas?