Proof that an inverse of a possibly noncomputable function is possibly not decidable I'm stuck with the following homework: Given an fixed function $f:\mathbb{N}\to\mathbb{N}$. $f$ is an arbitrary (possibly not computable, possibly partial) function. Show that the set $\\{f(42)\\}$ is decidable. Show that the set $f^{-1}(42)$ possibly isn't decidable. The first part is pretty easy: the set is decidable, because even though $f$ is possibly not defined, the set which contains it remains enumerable. The inverse thing $f^{-1}(42)$ is what confuses me. I can imagine that this could give me some innumerable infinite set, but couldn't this always be the case for a (possibly) noncomputable function?

I do not understand the answer given to the question about $\\{f(42)\\}$. This set is either a one-element set or possibly, in the case of a partial function, the empty set. Finite sets are all decidable: there **exists** an algorithm for determining membership in the set, even though we may not know what that algorithm is.

You can give an answer to the second question without knowing much about computable functions. Since there are no restrictions on $f$, there are uncountably many sets that could be $f^{-1}(42)$. However, there are only countably many decidable sets.

In fact there are _computable_ functions $f$ such that $f^{-1}(42)$ is not decidable.