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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm trying to solve the following exercise from an old exam:

For a computable function $G: \mathbb{N} \to \mathbb{N} $, and a set of numbers $A$, we define $g^{-1}(A)=\{x|g(x) \in A\} $ and $g(A)=\{g(x)| x\in A\}$. If $A$ is a decidable group so.. here there were 4 options and I chose $g(A)$ is not necessarily decidable, and $g^{-1}$ is certainly decidable.

I chose this option since we are not sure that $g$ is a total computable function, and it might not stop on one of $x \in A$, but why does $g^{-1}(A)=\{x|g(x) \in A\} $ have to be decidable? we need to use $g$ to find out that $g(x) \in A$, no?

share|cite|improve this question
Please use the computability tag for questions about computability theory. The fact that they are about computability does not make them "computer science". – Carl Mummert Aug 13 '12 at 11:09
o.k, but it is still "computer science", isn't it? – Jozef Aug 13 '12 at 12:33
No, not really. Computability theory of this sort is certainly used in computer science - but not very often, and many universities don't even include a class in it for an undergrad CS major. Only a tiny amount of computer science work is related to theoretical computability. Personally my research is in computability theory, but I am not a computer scientist. – Carl Mummert Aug 13 '12 at 12:39
@Carl, although computability theory focused courses have become less common, it is still common to teach basic computability theory in the introduction to computational complexity courses. (I agree with you that the computer-science tag is not needed for computability theory questions.) – Kaveh Aug 13 '12 at 19:40
up vote 1 down vote accepted

Your reasoning works out for $g(A)$, but $g^{-1}(A)$ needn't be decidable. Just take $A=\mathbb{N}$: then in particular $g^{-1}(A)$ decidable means the domain of every partial computable function is decidable. But the recursively enumerable sets are exactly the domains of computable functions, so we'd have every r.e. set recursive.

Thanks for sharing the specific choices that were offered you in your comment below. None of them hold for an arbitrary computable function (though see below for a total one,) and we can show this without taking $A$ to be anything fancier than $\mathbb{N}$ itself. First, $g(\mathbb{N})$ may be decidable, for instance, if it's finite. $g^{-1}(\mathbb{N})$ may be decidable. For instance, if $g$ is total, $g^{-1}(\mathbb{N})=\mathbb{N}$.

$g(\mathbb{N})$ may be undecidable: take $g$ to be identity on the diagonal set $D=\{n: f_n(n) \textrm{is defined} \}$, where $f_n$ is some Godel numbering of the computable functions, and $0$ elsewhere. $g^{-1}(\mathbb{N})$ may be undecidable: take $g$ again to be identity on $D$, but now undefined elsewhere. It's immediate that these last two sets are undecidable by the diagonalization argument that you've likely seen at some point-I'll elaborate if not.

As we've agreed below, the questioner must have intended $g$ to be total. Then we see something like the first diagonal function defined above has $g(\mathbb{N})$ undecidable, but $g^{-1}(\mathbb{N})$ is decidable for decidable $A$ by simply computing $g(n)$ and seeing whether it's in $A$.

share|cite|improve this answer
needen't means what? must not be? – Jozef Aug 13 '12 at 7:34
Only "may not be," or "doesn't need to be." It's certainly decidable sometimes-in particular if $g$ is total, it's decidable for every $A$. – Kevin Carlson Aug 13 '12 at 7:38
O.k I got confused, there isn't option for both may be decidable. it's "a. both must be decidable", "b.g(A) not necessarily decidable, but g^-1(A) must be", "c.g(A) must be decidable, and g-1(a) not necessarily decidable", " of them must not be decidable". – Jozef Aug 13 '12 at 7:43
Hm. Something's wrong there. I've responded above. – Kevin Carlson Aug 13 '12 at 7:58
The question says $g$ is a computable function from $\mathbb{N}$ to $\mathbb{N}$, so I think in particular it's assumed that it's total. – Harry Altman Aug 13 '12 at 8:00

Your Answer


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.