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

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.
• 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.). – Ali Shakiba Mar 1 '14 at 6:30
• There is no hurry! And do wait more than $8$ minutes, so that you have more answers to choose from. – André Nicolas Mar 1 '14 at 6:32