# 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?

-
What if $f^{-1}(42)=\varnothing$? – Asaf Karagila Jan 6 '13 at 23:34
Are you the person who just asked this on IRC? What was wrong with the answers you received? – Chris Eagle Jan 6 '13 at 23:37
@Asaf: Freenode ##math – Chris Eagle Jan 6 '13 at 23:49
Yes, that was me. Well, I guess the answer(that f^-1 could just give me anything) just seemed a bit too "obvious" to me :) Thanks anyways. – Fabian Fritz Jan 6 '13 at 23:52

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.