Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
add comment

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer
    
About the first one: that's just what I meant, it's finite in either case (it doesn't depend on f's definition). –  Fabian Fritz Jan 6 '13 at 23:54
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.