Article contents
Note on a conjecture of Skolem
Published online by Cambridge University Press: 12 March 2014
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(x1,…, xn) 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.
- Type
- Research Article
- Information
- Copyright
- Copyright © Association for Symbolic Logic 1946
References
1 In this Journal, vol. 11 (1946), pp. 26–28.
- 1
- Cited by