Example of a recursive set $S$ and a total recursive function $f$ such that $f(S)$ is not recursive?

411 Views Asked by At

Browsing wikipedia, I stumbled on the following: "The image of a computable set under a total computable bijection is computable." Given the form of the theorem, there must be some example of a example of a recursive set $S$ and a total recursive function $f$ such that $f(S)$ is not recursive (otherwise the statement would have presumably been stronger). But I'm having difficulty dreaming up a case where this happens.

1

There are 1 best solutions below

0
On BEST ANSWER

Take any set $A$ that is recursively enumerable but not recursive (e.g. the halting problem). It is enumerated by some total recursive function $f(x)$. But $\mathbb{N}$ is recursive while $f(\mathbb{N}) = A$ is not.