understanding gödel's 1931 paper - primitive recursive functions - projection and equality

Question

I am reading a translation of gödel's original, and i'm a bit confused about the primitive recursive functions.

Everywhere on the internet (or some resources like courses/classes i could put my hands on), the set of basic primitive recursive functions are defined as :

• zero
• successor
• projection
• composition
• primitive recursion

every of those functions are talked about in the paper except the "projection" one.

Did I not understand/see it in the paper ? Or how would I construct the basic PR functions "projection" from what has been drawn by Gödel ?

My main question was : how to construct the 'not', 'or', 'equal' using PR. One can find them easily on the internet, but they use this "projection" function.

At the very moment i am editing this question, I am particularily interested in the 'equal' relation.

Thank you

Answer 1

The theory of (primitive) recursive functions has been sketched by Gödel in his paper and subsequently "streamlined" by other authors.

For a detailed treatment, see :

• Elliott Mendelson, Introduction to mathematical logic (4th ed - 1997), page 174-on.

For a "older" but complete treatment, see :

• Rosza Péter, Recursive functions (2ed 1967), page 23-on.

In brief :

$a=b$ iff $sg(|a — b|) = 0$;

$|a — b|$ is p.r. becuase $|a — b| = (a \div b)+(b \div a)$;

$(a \div b)$ is defined as : $(a \div 0)=a$ and $(a \div (b+1))=pd (a \div b)$, where : $pd(0)=0$ and $pd(y+1)=y$.

Finally : $sg(x)=0$ if $x=0$ and $sg(x)=1$ if $x \ne 0$ is p.r. because it is defined by :

$sg(0)=0$ and $sg(x+1)=1$.

---

In Gödel's original paper :

A number-theoretic function $\varphi$ is said to be recursive if there is a finite sequence of number-theoretic functions [...] that ends with $\varphi$ and has the property that every function of the sequence is recursively defined in terms of two of the preceding functions, or results from any of the preceding functions by substitution, or, finally, is a constant or the successor function $x + 1$.

In turn, we can define the constant functions inductively from the constant zero function : $Z(x)=0$ and the successor :

$C_0(x)=Z(x)$ and $C_{n+1}(x)=C_n(x)+1$.

---

Gödel refined his exposition in his 1934 Priceton lectures (see : Martin Davis (editor), The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions (1965 - Dover reprint), page 43) (the notes were taken by S.C.Kleene and J.B.Rosser); here the complete definition is stated :

We define the class of recursive functions to be the totality of functions which can be generated by substitution, according to the scheme (1), and recursion, according to the scheme (2), from the successor function $x+1$, constant functions $f(x_1, \ldots, x_n) = c$, and identity functions $U_j^n(x_1, \ldots, x_n) = x_j, (1 \le j \le n)$.

---

The usual recursive definition of sum is based on the equations :

$x+0=x$, i.e. $f(x,0)=U_1^1(x)$

$x+(y+1)=S(x+y)$, i.e. $f(x,y+1)=f(x,y)+1$.

Answer 2

You can define the projections using Gödel's representation of a list of numbers $k_1, \ldots, k_m$ as the single number $p_1^{k_1}\cdots p_m^{k_m}$ (where $p_i$ is the $i$-th prime). I don't think he gives a name to the function, $\lambda_m$ say, that maps the $m$-tuple $(k_1, \ldots, k_m)$ to $p_1^{k_1}\cdots p_k^{k_m}$, but $\lambda_m$ is primitive recursive and you don't need projection to define it. He does give a name to the primitive recursive function that, given $n$ with $1 \le n \le m$, extracts $k_n$ from $\lambda_m(k_1, \ldots, k_m)$ (it's called $\mathit{item}$ in this translation). Composing these things gives you the projection functions. So the projection functions are just a technical convenience.

Mauro Allegranza has shown you how to implement the equality test function: $$ \gamma(x, y) = \left\{ \begin{array}{ll} 0 & \mbox{if $x = y$}\\ 1 & \mbox{if $x \neq y$} \end{array} \right. $$ as a primitive recursive function. As for the negation and disjunction functions: $$ \begin{array}{rcl} \alpha(x) &=& \left\{ \begin{array}{ll} 1 & \mbox{if $x = 0$}\\ 0 & \mbox{if $x \neq 0$} \end{array} \right. \\ \beta(x, y) &=& \left\{ \begin{array}{ll} 0 & \mbox{if one or both of $x, y$ ${} = 0$}\\ 1 & \mbox{if both $x, y$ are ${} \neq 0$} \end{array} \right. \end{array} $$

the following primitive recursive definitions do the job:

$$ \begin{array}{rcl} \alpha(0) &=& 1 \\ \alpha(k + 1) &=& 0 \\ \beta(0, y) &=& 0 \\ \beta(k+1, y) &=& \alpha(\alpha(y)) \end{array} $$