Hostname: page-component-586b7cd67f-dlnhk Total loading time: 0 Render date: 2024-11-26T01:15:41.752Z Has data issue: false hasContentIssue false

Note on a conjecture of Skolem

Published online by Cambridge University Press:  12 March 2014

Emil L. Post*
Affiliation:
The City College, College of the city of New York

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
Copyright
Copyright © Association for Symbolic Logic 1946

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1 In this Journal, vol. 11 (1946), pp. 26–28.