Note on a conjecture of Skolem

Extract

In his excellent review of four notes of Skolem on recursive functions of natural numbers Bernays states: “The question whether every relation y = f(x₁,…, x_n) with a recursive function ƒ is primitive recursive remains undecided.” Actually, the question is easily answered in the negative by a form of the familiar diagonal argument.

We start with the ternary recursive relation R, referred to in the review, such that R(x, y, 0), R(x, y, 1), … is an enumeration of all binary primitive recursive relations.