Hostname: page-component-586b7cd67f-tf8b9 Total loading time: 0 Render date: 2024-11-27T21:48:03.487Z Has data issue: false hasContentIssue false
  • English
  • Français

Minimal α-recursion theoretic degrees

Published online by Cambridge University Press:  12 March 2014

John M. MacIntyre
John M. MacIntyre*
Affiliation:
Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
Get access Rights & Permissions [Opens in a new window]

Extract

This paper investigates the problem of extending the recursion theoretic construction of a minimal degree to the Kripke [2]-Platek [5] recursion theory on the ordinals less than an admissible ordinal α, a theory derived from the Takeuti [11] notion of a recursive function on the ordinal numbers. As noted in Sacks [7] when one generalizes the recursion theoretic definition of relative recursiveness to α-recursion theory for α > ω the two usual definitions give rise to two different notions of reducibility. We will show that whenever α is either a countable admissible or a regular cardinal of the constructible universe there is a subset of α whose degree is minimal for both notions of reducibility. The result is an excellent example of a theorem of ordinary recursion theory obtainable via two different constructions, one of which generalizes, the other of which does not. The construction which cannot be lifted to α-recursion theory is that of Spector [10]. We sketch the reasons for this in §3.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 38 , Issue 1 , March 1973 , pp. 18 - 28
Copyright
Copyright © Association for Symbolic Logic 1973

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

BIBLIOGRAPHY

[1]Kreisel, G. and Sacks, G. E., Metarecursive sets, this Journal, vol. 30 (1965), pp. 318–338.Google Scholar
[2]Kripke, S., Transfinite recursions on the admissible ordinals, this Journal, vol. 29 (1964), pp. 161–162; Admissible ordinals and the analytic hierarchy, this Journal, vol. 29 (1964), p. 162. (Abstracts.)Google Scholar
[3]Machtey, M., Admissible ordinals and intrinsic consistency, this Journal, vol. 35 (1970), pp. 389–400.Google Scholar
[4]MacIntyre, J. M., Contributions to metarecursion theory, Ph.D. Thesis, M.I.T., Cambridge, Mass., 1968.Google Scholar
[5]Platek, R., Foundations of recursion theory, Ph.D. Thesis and supplement, Stanford University, Stanford, Calif., 1966.Google Scholar
[6]Sacks, G. E., Degrees of unsolvability, Annals of Mathematical Studies, No. 55, Princeton University Press, Princeton, N.J., 1963.Google Scholar
[7]Sacks, G. E., Post's problem, admissible ordinals and regularity, Transactions of the American Mathematical Society, vol. 124 (1966), pp. 1–23.Google Scholar
[8]Sacks, G. E., Metarecursion theory, Sets, models, and recursion theory (Crossley, J. N., Editor), North-Holland, Amsterdam, 1967.Google Scholar
[9]Shoenfield, J. R., A theorem on minimal degrees, this Journal, vol. 31 (1966), pp. 539–544.Google Scholar
[10]Spector, C., On degrees of recursive unsolvability, Annals of Mathematics (2), vol. 64 (1956), pp. 581–592.CrossRefGoogle Scholar
[11]Takeuti, G., On the recursive functions of ordinal numbers, Journal of the Mathematical Society of Japan, vol. 12 (1960), pp. 119–128.CrossRefGoogle Scholar