Hostname: page-component-586b7cd67f-gb8f7 Total loading time: 0 Render date: 2024-11-28T06:55:22.011Z Has data issue: false hasContentIssue false
  • English
  • Français

A classification of jump operators

Published online by Cambridge University Press:  12 March 2014

John R. Steel
John R. Steel*
Affiliation:
University of California at Los Angeles, Los Angeles, California 90024
Get access Rights & Permissions [Opens in a new window]

Extract

The structure (D, ≤) of the Turing degrees under Turing reducibility is quite complicated. This is true even if we restrict our attention to the substructure (R, ≤) of r.e. degrees. However, the theorems which imply that these structures are complicated all involve ad hoc constructions of sets having the desired reducibility relations. The complexity disappears when we turn to degrees occurring in nature. Of the degrees in R, only 0 and 0′ seem natural. In D, only 0, 0′, 0″, …, 0ω, 0ω+1, … (and on into the transfinite) seem natural. Thus the natural degrees appear to be wellordered, with successors given by Turing jump.

If this is true, one would like to prove it. Of course the first problem is to make the concept of naturalness more precise. The following requirements seem plausible: a natural degree should be definable, its definition should relativise to an arbitrary degree, and this relativisation should preserve reducibility relations among natural degrees. Thus to each natural degree c is associated a definable fc: D → D so that fc(0) = c and ∀d(d ≤ fc(d)). Moreover, b ≤ c iff ∀d(fb(d) ≤, fc(d)). To be specific, let us take the definability of fc to mean that fc ∈ L(R).

If P is a property of degrees, we say P holds almost everywhere (a.e.) iff ∃c∀d ≥: c P(d). For f, g: D → D, let f ≤mgiff f(d) ≤ g(d) a.e. Define f′ by f′(d) = f{d)′, and let M = {f: D → D/f ∈ L(R) ∧ d ≤ f(d) a.e.}. The following conjecture is due to D. A. Martin:

Conjecture. M is prewellordered by ≤m. If f ∈ M has rank α in ≤m, then f′ has rank α + 1.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 47 , Issue 2 , June 1982 , pp. 347 - 358
Copyright
Copyright © Association for Symbolic Logic 1982

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]Becker, H., Partially playful universes, Cabal Seminar, 1976–1977, Lecture Notes in Mathematics, vol. 689, Springer-Verlag, Berlin and New York, 1978, pp. 55–91.CrossRefGoogle Scholar
[2]Hodes, H., Jumping through the transfinite: the master-code hierarchy of Turing degrees, this Journal, vol. 45 (1980), pp. 204–220.Google Scholar
[3]Jensen, R. B., The fine structure of the constructible hierarchy, Annals of Mathematical Logic, vol. 4 (1972), pp. 229–308.CrossRefGoogle Scholar
[4]Jockusch, C. and Simpson, S., A degree-theoretic definition of the ramified analytic hierarchy, Annals of Mathematical Logic, vol. 10 (1976), pp. 1–32.CrossRefGoogle Scholar
[5]Kechris, A. S., AD and projective ordinals, Cabal Seminar, 1976–1977, Lecture Notes in Mathematics, vol. 689, Springer-Verlag, Berlin and New York, 1978, pp. 91–133.CrossRefGoogle Scholar
[6]Lachlan, A. H., Uniform enumeration operation, this Journal, vol. 40 (1975), pp. 401–409.Google Scholar
[7]Martin, D. A., The axiom of determinateness and reduction principle in the analytical hierarchy, Bulletin of the American Mathematical Society, vol. 74 (1968), pp. 687–689.CrossRefGoogle Scholar
[8]Sacks, G. E., On a theorem of Lachlan and Martin, Proceedings of the American Mathematical Society, vol. 18 (1967), pp. 140–141.CrossRefGoogle Scholar
[10]Steel, J., Descending sequences of degrees, this Journal, vol. 40 (1975), pp. 59–61.Google Scholar
[11]Wesep, R. Van, Wadge degrees and descriptive set theory, Cabal Seminar, 1976–1977, Lecture Notes in Mathematics, vol. 689, Springer-Verlag, Berlin and New York, 1978, pp. 151–171.CrossRefGoogle Scholar