Hostname: page-component-cd9895bd7-7cvxr Total loading time: 0 Render date: 2024-12-25T02:05:43.117Z Has data issue: false hasContentIssue false
  • English
  • Français

Effective discontinuity and a characterisation of the superjump

Published online by Cambridge University Press:  12 March 2014

John P. Hartley
John P. Hartley*
Affiliation:
University of Leeds, Leeds LS2 9JT, England
Get access Rights & Permissions [Opens in a new window]

Extract

One of the most fundamental results of higher-type recursion theory was first proved by Thomas Grilliot [3]. He showed that the functional embodying number quantification, 2E, is computable from a type-2 object F if and only if F has an effective discontinuity. For the background to this work we recommend Normann's book [9] or his summary [10], and for an example of its many applications Normann-Wainer [11].

The purpose of §1 of this paper is to give an effective proof of the “only if” part of this result: i.e. a construction of a discontinuity of F from the information 2E = {e}F. This contrasts with Grilliot's argument which is topological and nonconstructive, and shows that “Grilliot's trick” for computing 2E from a discontinuity of F is essentially the only method.

We then apply the method to two more general situations in which it gives new results. In §2 we treat type-3 objects in which 3E is computable (assuming AC and CH), and obtain a strengthening of the result of Hartley [5, §5]. In §3 we consider the superjump and characterise it as the least among a class of functionals with a particular sort of family of discontinuities.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 50 , Issue 2 , June 1985 , pp. 349 - 358
Copyright
Copyright © Association for Symbolic Logic 1985

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

REFERENCES

[1] Aczel, P. and Hinman, P. G., Recursion in the superjump, Generalized recursion theory (Fenstad, J. E. and Hinman, P. G., editors), North-Holland, Amsterdam, 1974, pp. 3–41.Google Scholar
[2] Gandy, R. O., Generalized recursive functionals of finite type and hierarchies of functions, Annales de la Faculté des Sciences de l'Université de Clermont-Ferrand, vol. 35 (1967), pp. 5–24.Google Scholar
[3] Grilliot, T. J., On effectively discontinuous type-2 objects, this Journal, vol. 36(1971), pp. 245–249.Google Scholar
[4] Harrington, L. A., The superjump and the first recursively Mahlo ordinal, Generalized recursion theory (Fenstad, J. E. and Hinman, P. G., editors), North-Holland, Amsterdam, 1974, pp. 43–52.Google Scholar
[5] Hartley, J. P., The countably based functionals, this Journal, vol. 48 (1983), pp. 458–474.Google Scholar
[6] Hinman, P. G., Recursion-theoretic hierarchies, Springer-Verlag, Berlin, 1978.CrossRefGoogle Scholar
[7] Kechris, A. S. and Moschovakis, Y. N., Recursion in higher types, Handbook of mathematical logic (Barwise, J., editor), North-Holland, Amsterdam, 1977, pp. 681–737.CrossRefGoogle Scholar
[8] Lavori, P., Recursion in the extended superjump, Illinois Journal of Mathematics, vol. 21 (1977), pp. 752–758.CrossRefGoogle Scholar
[9] Normann, D., Recursion on the countable functionals, Lecture Notes in Mathematics, vol. 811, Springer-Verlag, Berlin, 1980.CrossRefGoogle Scholar
[10] -, The recursion theory of the continuous functionals, Recursion theory: its generalisations and applications (Drake, F. R. and Wainer, S. S., editors), London Mathematical Society Lecture Notes Series, vol. 45, Cambridge University Press, London, 1980, pp. 171–183.CrossRefGoogle Scholar
[11] Normann, D. and Wainer, S. S., The 1-section of a countable functional, this Journal, vol. 45 (1980), pp. 549–562.Google Scholar
[12] Shoenfield, J. R., A hierarchy based on a type-2 object, Transactions of the American Mathematical Society, vol. 134 (1968), pp. 103–108.CrossRefGoogle Scholar