Hostname: page-component-586b7cd67f-r5fsc Total loading time: 0 Render date: 2024-11-23T05:45:30.508Z Has data issue: false hasContentIssue false
  • English
  • Français

Recursively enumerable sets modulo iterated jumps and extensions of Arslanov's completeness criterion

Published online by Cambridge University Press:  12 March 2014

C. G. Jockusch Jr ,
M. Lerman ,
R. I. Soare  and
R. M. Solovay
C. G. Jockusch Jr
Affiliation:
Department of Mathematics, University of Illinois, Urbana, Illinois 61801
M. Lerman
Affiliation:
Department of Mathematics, University of Connecticut, Storrs, Connecticut 06268
R. I. Soare
Affiliation:
Department of Mathematics, University of Chicago, Chicago, Illinois 60637
R. M. Solovay
Affiliation:
Department of Mathematics, University of California, Berkeley, California 94720
Get access Rights & Permissions [Opens in a new window]

Extract

Let We be the eth recursively enumerable (r.e.) set in a standard enumeration. The fixed point form of Kleene's recursion theorem asserts that for every recursive function f there exists e which is a fixed point of f in the sense that We = W f(e). In this paper our main concern is to study the degrees of functions with no fixed points. We consider both fixed points in the strict sense above and fixed points modulo various equivalence relations on recursively enumerable sets.

Our starting point for the investigation of the degrees of functions without (strict) fixed points is the following result due to M. M. Arslanov [A1, Theorem 1] and known as the Arslanov completeness criterion. Proofs of this result may also be found in [So1, Theorem 1.3] and [So2, Chapter 12], and we will give a game version of the proof in §5 of this paper.

Theorem 1.1 (Arslanov). Let A be an r.e. set. Then A is complete (i.e. A has degree 0′) iff there is a function f recursive in A with no fixed point.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 54 , Issue 4 , December 1989 , pp. 1288 - 1323
Copyright
Copyright © Association for Symbolic Logic 1989

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

[A1] Arslanov, M. M., On some generalizations of a fixed point theorem, Izvestiya Vysshikh Uchebnykh Zavedeniǐ Matematika 1981, no. 5 (228), pp. 9–16; English translation, Soviet Mathematics (Iz. VUZ) , vol. 25 (1981), no. 5, pp. 1–10.Google Scholar
[A2] Arslanov, M. M., On a hierarchy of the degrees of unsolvability, Probabilistic Methods and Cybernetics, vyp. 18, Kazanskiǐ Gosudarstvennyǐ Universitet, Kazan', 1982, pp. 10–17. (Russian)Google Scholar
[A3] Arslanov, M. M., Families of recursively enumerable sets and their degrees of unsolvability, Izvestiya Vysshikh Uchebnykh Zavedeniǐ Matematika 1985, no. 4 (275), pp. 13–19; English translation, Soviet Mathematics (Iz. VUZ) , vol. 29 (1985), no. 4, pp. 13-21.Google Scholar
[A4] Arslanov, M. M., Recursively enumerable sets and degrees of unsolvability, Izdatel'stvo Kazanskogo Gosudarstvennogo Universiteta, Kazan', 1986. (Russian)Google Scholar
[A5] Arslanov, M. M., Completeness in the arithmetical hierarchy and fixed points, Algebra i Logika (to appear): English translation, Algebra and Logic (to appear).Google Scholar
[ANS] Arslanov, M. M., Nadirov, R. F., and Solov'ev, V. D., Completeness criteria for recursively enumerable sets and some general theorems on fixed points, Izvestiya Vysshikh Uchebnykh Zavedeniǐ Matematika 1977, No. 4 (179), pp. 3–7; English translation, Soviet Mathematics (Iz. VUZ) , vol. 21 (1977), pp. 1–4.Google Scholar
[D] Demuth, O., A notion of semigenericity, Commentationes Mathematicae Universitatis Carolinae, vol. 28 (1987), pp. 71–74.Google Scholar
[EHK] Epstein, R. L., Haas, R., and Kramer, R., Hierarchies of sets and degrees below 0′, Logic Year 1979–80 (Lerman, M. et al, editors), Lecture Notes in Mathematics, vol. 859, Springer-Verlag, Berlin, 1981, pp. 32–48.CrossRefGoogle Scholar
[J] Jockusch, C. G., Degrees of functions with no fixed points, Proceedings of the eighth international congress for logic, methodology and philosophy of science (to appear).Google Scholar
[JSh] Jockusch, C. G. and Shore, R. A., Pseudo jump operators. II: Transfinite iterations, hierarchies, and minimal covers, this Journal, vol. 49 (1984), pp. 1205–1236.Google Scholar
[JSo] Jockusch, C. G. and Soare, R. I., classes and degrees of theories, Transactions of the American Mathematical Society, vol. 173 (1972), pp. 33–56.Google Scholar
[K1] Kučera, A., Measure, Π classes, and complete extensions of PA, Recursion theory week (Ebbinghaus, H.-D. et al, editors), Lecture Notes in Mathematics, vol. 1141, Springer-Verlag, Berlin, 1985, pp. 245–259.CrossRefGoogle Scholar
[K2] Kučera, A., An alternative, priority free solution to Post's problem. Mathematical foundations of computer science 1986 (Gruska, J. et al, editors), Lecture Notes in Computer Science, vol. 233, Springer-Verlag, Berlin, 1986, pp. 493–500.CrossRefGoogle Scholar
[K3] Kučera, A., On the role of 0′ in recursion theory, Logic Colloquium '86 (Drake, F. R. and Truss, J. K., editors), North-Holland, Amsterdam, 1988, pp. 133–141.Google Scholar
[K4] Kučera, A., On the use of diagonally nonrecursive functions, Logic Colloquium '87 (to appear).Google Scholar
[La] Lachlan, A. H., On some games which are relevant to the theory of recursively enumerable sets, Annals of Mathematics, ser. 2, vol. 91 (1970), pp. 291–310.CrossRefGoogle Scholar
[Le] Lempp, S., Topics in recursively enumerable sets and degrees, Ph.D. thesis, University of Chicago, Chicago, Illinois, 1986.Google Scholar
[R] Rogers, H. Jr., Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967.Google Scholar
[RND] Reingold, E., Nievergelt, J., and Deo, N., Combinatorial algorithms: theory and practice, Prentice-Hall, Englewood Cliffs, New Jersey, 1977.Google Scholar
[Sa] Sacks, G. E., On a theorem of Lachlan and Martin, Proceedings of the American Mathematical Society, vol. 18 (1967), pp. 140–141.CrossRefGoogle Scholar
[Sehl] Schwarz, S., Index sets of recursively enumerable sets, quotient lattices, and recursive linear orderings, Ph.D. thesis, University of Chicago, Chicago, Illinois, 1982.Google Scholar
[Sch2] Schwarz, S., Index sets related to the high-low hierarchy, Israel Journal of Mathematics (to appear).Google Scholar
[Sco] Scott, D., Algebras of sets binumerable in complex extensions of arithmetic, Recursive function theory (Dekker, J. C. E., editor), Proceedings of Symposia in Pure Mathematics, vol. 5, American Mathematical Society, Providence, Rhode Island, 1962, pp. 117–121.CrossRefGoogle Scholar
[So1] Soare, R. I., Fundamental methods for constructing recursively enumerable degrees, Recursion theory: its generalisations and applications (Proceedings of Logic Colloquium '79; Drake, F. and Wainer, S. S., editors), London Mathematical Society Lecture Note Series, vol. 45, Cambridge University Press, Cambridge, 1980, pp. 1–51.Google Scholar
[So2] Soare, R. I., Recursively enumerable sets and degrees: a study of computable functions and computably generated sets, Springer-Verlag, Berlin, 1987.CrossRefGoogle Scholar
[ST] Scott, D. and Tennenbaum, S., On the degrees of complete extensions of arithmetic, Notices of the American Mathematical Society, vol. 7 (1960), pp. 242–243 (abstract #568-3).Google Scholar