# Computable functions' set is countable

I have to prove that computable functions (by computable we mean recursive functions or functions calculated by a program with a register machine) are countable. Let $\mathcal{C}$ be the set of computable $\mathbb{N} \to \mathbb{N}$ functions

$|\mathcal{C}|\geq\omega$. Well, this is trivial because we can consider functions of the kind $n \mapsto (s\circ\cdots \circ s)(n)$ where $s$ is the successor function; these maps are trivially computable and there are $\omega$ of them.

$|\mathcal{C}|\leq\omega$. We know that (I will not go in deeper details, but it can be done!) starting from a natural $j$, we can find a program $p_j$ tha computes a recursive function. Note that there are several programs computing the same function. In turn, we can consider a computable function $f$ and, since there is an entire class of programs that calculate $f$, we can map $f$ tho the minumum program index $j$ of a program that computes $f$. So we have an injective function between $\mathcal{C}$ and $\mathbb{N}$. QED

Is thi proof correct?

-
Looks fine to me. –  Brian M. Scott Jun 22 '12 at 17:16