Gödel's β-function lemma

Statement

By an ingenious use of the Chinese remainder theorem, we can constructively define such a recursive function $\beta$ (using simple number-theoretical functions, all of which can be defined in a total recursive way) fulfilling the specifications given above. Gödel defined the $\beta$ function using the Chinese remainder theorem in his article written in 1931. This is a primitive recursive function.

Thus, for all n and for any n-length sequence of natural numbers $\langle a_0,\dots a_{n-1} \rangle$, there exists an appropriate natural number a, called the Gödel number of the sequence such that $\beta(a,i) = a_i$.

Our specific solution will depend on a pairing function—there are several ways to implement the pairing function, so one method must be selected. Now, we can abstract from the details of the implementation of the pairing function. We need only to know its "interface": let $\pi$, K, and L denote the pairing function and its two projection functions, respectively, satisfying specification:

$$K\left(\pi\left(x,y\right)\right) = x$$

$$L\left(\pi\left(x,y\right)\right) = y$$

We shall use another auxiliary function that will compute the remainder for natural numbers. Examples:

• $$\mathrm{rem}(5, 3) = 2$$
• $$\mathrm{rem}(7, 2) = 1$$

It can be proven that this function can be implemented as a recursive function.