In "Computability: an introduction to recursive function theory", by Cutland, there is a theorem as follows:

Theorem 2.4 $\mathcal{C}_n$ is denumerable.

where $\mathcal{C}_n$ represents the set of all $n$-ary computable functions. It constructs a bijection between $\mathcal{C}_n$ and $\mathbb{N}$ to show this as follows $$ \left\{ \begin{matrix} f(0)=0 , \\ f(m+1) = \mu z \left(\Phi_z^{(n)} \neq \Phi_{f(0)}^{(n)} , \ldots , \Phi_{f(m)}^{(n)} \right) , \end{matrix} \right. $$ where $\Phi_x^{(n)}$ represents a $n$-ary function encoded as $x$ by Godel number. But the problem is that it is not computable, in my opinion since it could be reduced to halting (Functions in $\mathcal{C}_n$ are partially recursive (computable))!

Now the question is that if I find a bijection, rather than it is computable or not even computable, then the set would be denumerable or not?


For denumerability, all you need to do it to prove that a bijection exists. It need not be computable. There are $2^{\aleph_0}$ denumerable subsets of the natural numbers, and there are only countably many for which there is a computable bijection with the natural numbers.

| cite | improve this answer | |
  • $\begingroup$ Thanks for your fast response. I would accept this answer as soon as I can (At least $8$ minutes should pass so I can accept an answer.). $\endgroup$ – Ali Shakiba Mar 1 '14 at 6:30
  • $\begingroup$ There is no hurry! And do wait more than $8$ minutes, so that you have more answers to choose from. $\endgroup$ – André Nicolas Mar 1 '14 at 6:32
  • $\begingroup$ OK! Thanks for your advice, I am a newcomer to math exchange. :) $\endgroup$ – Ali Shakiba Mar 1 '14 at 6:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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