Hostname: page-component-78c5997874-ndw9j Total loading time: 0 Render date: 2024-11-19T04:47:53.614Z Has data issue: false hasContentIssue false
  • English
  • Français

An introduction to hyperarithmetical functions

Published online by Cambridge University Press:  12 March 2014

Julia Robinson
Julia Robinson*
Affiliation:
University of California, Berkeley
Get access Rights & Permissions [Opens in a new window]

Extract

By functional equation we mean an equation of the form

(1)A1 … Aκ = B1 … B1.

Here the A's and B's are functions of one variable from and to the natural numbers and FG is the function obtained from F and G by composition, i.e. FG(x) = F(G(x)) for all natural numbers x. We wish to investigate finite systems of functional equations. Now if all the A's and B's of (1) are equal to the identity function I (or all equal to the zero function O), then the equation (1) is satisfied trivially. Thus, in order to make the problem of solvability of systems of equations interesting, we must have some function given which will be held fixed throughout. We take the successor function S to be this given function.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 32 , Issue 3 , 09 October 1967 , pp. 325 - 342
Copyright
Copyright © Association for Symbolic Logic 1967

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]Davis, Martin, The undecidable, Raven Press, Hewlett, New York, 1965.Google Scholar
[2]Gödel, K., Über formal unentscheidbare Sätze der Principia Mathematica und verwandter System. I, Monatshefte für Mathematik und Physik, vol. 38 (1931), pp. 173–198.CrossRefGoogle Scholar
[3]Feferman, Solomon, Some applications of the notions of forcing and generic sets, Fundamenta mathematicae, vol. 56 (1964/1965), pp. 325–345.CrossRefGoogle Scholar
[4]Grzegorczyk, A., Mostowski, A., and Ryll-Nardzewski, C., The classical and the ω-complete arithmetic, this Journal, vol. 23 (1958), pp. 188–206.Google Scholar
[5]Kleene, S. C., Hierarchies of number-theoretic predicates, Bulletin of the American Mathematical Society, vol. 61 (1955), pp. 193–213.CrossRefGoogle Scholar
[6]Kleene, S. C., Arithmetical predicates and function quantifiers. Transactions of the American Mathematical Society, vol. 79 (1955), pp. 312–340.CrossRefGoogle Scholar
[7]Kleene, S. C., Quantification of number-theoretic functions, Composito mathematica, vol. 14 (1959), pp. 23–40.Google Scholar
[8]Spector, Clifford, Recursive well-orderings, this Journal, vol. 20 (1955), pp. 151–163.Google Scholar
[9]Spector, Clifford, Hyperarithmetical quantifiers, Fundamenta mathematicae, vol. 48 (1960), pp. 313–320.CrossRefGoogle Scholar
[10]Tarski, A., Mostowski, A., and Robinson, R. M., Undecidable theories, North-Holland Publishing Company, Amsterdam, 1953.Google Scholar