Enumerating general recursive functions with a primitive recursive function

78 Views Asked by At

I am reading "Set Theory and the Continuum Hypothesis", a monograph by Paul Cohen. In the preliminary chapter, he gives a proof that not all recursively enumerable sets are recursive. He begins by enumerating all possible finite set of equations involving a function symbol $f$. Denoting by $f_n$ any function defined by the nth system of equations, we can enumerate all deductions of the type $f_n(a)=b$. He then claims that after choosing the correct enumerations, "it can be easily shown" that there exist primitive recursive functions $\phi_1,\phi_2, \phi_3$ such that if $f_n(a)=b$ is the mth deduction of that form, then $\phi_1(m)=n$, $\phi_2(m)=a$, $\phi_3(m)=b$. Lacking a strong background in logic and set theory, I am at a loss as to why these might exist. If anyone could explain why these functions exist, and how one would go about constructing them, I would be thankful.