Showing that the number of primitive-recursion programs for each function is countably-infinite Problem Statement


  Prove that if  a function $f$ is primitive recursive, then there are countably infinite number of primitive recursive definitions of $f$


Yes, this is a homework question.

My Work

I proved that there are infinite number of definitions using the following construction

$$g_k(n) = \underbrace{P_{1}^1(P_{1}^1( \dots( P_{1}^1}_{k \text{ times}}(f(n))\dots), \ \forall \ k \in \mathbb{N}$$

Here $P_1^1$ is the projection basis function which picks the $1^{\text{st}}$ element from a vector of size $1$

Now $k$ is unbounded and we will get an equivalent definition for $f$ for each $k$

Now the issue is that this is not the only way to construct an infinite number of equivalent definitions i.e. I could have also use the multiplication operator and multiplied the output of $f$ by 1 as many times as I liked.

How can I show that there is a $1-1$ correspondence of the set of all primitive recursive definitions with the set of naturals numbers? Unlike bit strings, I am unable to comprehend in what way I should assign some number to each function. In fact I don't even know in how many ways can I create equivalent definitions, so how can I even start to enumerate these functions?

Any hints?
I proved that there are infinite number of definitions using the following construction


That works in principle, but be careful about what $f$ is in that term, formally.


  Now the issue is that this is not the only way to construct an infinite number of equivalent definitions


Right you are!


  How can I show that there is a 1−1 correspondence of the set of all primitive recursive definitions with the set of naturals numbers?


You don't have to do this explicitly.
Use that the class of countable sets is closed against taking subsets.