Hostname: page-component-78c5997874-8bhkd Total loading time: 0 Render date: 2024-11-09T06:28:26.475Z Has data issue: false hasContentIssue false
  • English
  • Français

Forcing and reducibilities

Published online by Cambridge University Press:  12 March 2014

Piergiorgio Odifreddi
Piergiorgio Odifreddi*
Affiliation:
Istituto Matematico, Università di Torino, Torino, Italy10100 University of California, Los Angeles, California 90024
Get access Rights & Permissions [Opens in a new window]

Extract

We see far away, Newton said, if we stand on giants' shoulders. We take him seriously here and moreover (as appropriate to recursion-theorists) we will jump from one giant to another, since this paper is mostly an exegesis of two fundamental works: Feferman's Some applications of the notions of forcing and generic sets [4] and Sacks' Forcing with perfect closed sets [19]. We hope the reader is not afraid of heights: our exercises are risky ones, since the two giants are in turn on the shoulders of others! Feferman [4] rests on the basic works of Cohen [2], who introduced forcing with finite conditions in the context of set theory; Sacks [19] relies on Spector [24], who realized—in recursion theory—the necessity of more powerful approximations than the finite ones.

To minimize the risk we will try to keep technicalities to a minimum, choosing to give priority to the methodology of forcing. We do not suppose any previous knowledge of forcing in the reader, but we do require some acquaintance with recursion theory. After all, our interest lies in the applications of the forcing method to the study of various recursion-theoretic notions of degrees. The farther we go, the deeper we plunge into recursion theory.

In Part I only very basic notions and results are used, like the definitions of the arithmetical hierarchy and of the jump operator and their relationships.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 48 , Issue 2 , June 1983 , pp. 288 - 310
Copyright
Copyright © Association for Symbolic Logic 1983

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]Addison, J. W., The undefinability of the definable (abstract), Notices of the American Mathematical Society, vol. 12 (1965), p. 347.Google Scholar
[2]Cohen, P. J., The independence of the continuum hypothesis. I, II, Proceedings of the National Academy of Sciences. U.S.A., vol. 50 (1963), 1143–1148; vol. 51 (1964), pp. 105–110.CrossRefGoogle Scholar
[3]Enderton, H. B. and Putnam, H., A note on the hyperarithmetical hierarchy, this Journal, vol. 35 (1970), pp. 429–430.Google Scholar
[4]Feferman, S., Some applications of the notion of forcing and generic sets, Fundamenta Mathematicae, vol. 56 (1965), pp. 325–345.CrossRefGoogle Scholar
[5]Friedberg, R. M., Two recursively enumerable sets of incomparable degrees of unsolvability, Proceeding of the National Academy of Sciences. UJS.A., vol. 43 (1957), pp. 236–238.CrossRefGoogle ScholarPubMed
[6]Friedberg, R. M., A criterion for completeness of degrees of unsolvability, this Journal, vol. 22 (1957), 159–160.Google Scholar
[7]Hinman, P. G., Some applications of forcing to hierarchy problems in arithmetic, Zeitschrift fur Mathematische Logik and Grundlagen der Mathematik, vol. 15 (1969), pp. 341–352.CrossRefGoogle Scholar
[8]Jockusch, C., Degrees of generic sets, London Mathematical Society Lecture Notes, vol. 45 (1980), pp. 110–139.Google Scholar
[9]Jockusch, C. and Simpson, S.G., A degree-theoretic definition of the ramified analytic hierarchy, Annals of Mathematical Logic, vol. 10 (1975), pp. 1–32.CrossRefGoogle Scholar
[10]Kleene, S.C. and Post, E.L., The upper semi-lattice of degrees of recursive unsolvability, Annals of Mathematics, vol. 59 (1954), pp. 379–407.CrossRefGoogle Scholar
[11]Macintyre, J.M., Transfinite extensions of Friedberg's completeness criterion, this Journal vol. 42 (1977), pp. 1–10.Google Scholar
[12]Muchnik, A.A., On the unsolvability of the problem ofreducibility in the theory of algorithms, Doklady Akademii Nauk SSSR, vol. 108 (1956), pp. 194–197.Google Scholar
[13]Nerode, A. and Shore, R.A., Second order logic and first order theories ofreducibility orderings, Proceedings of the Kleene Symposium, North-Holland, Amsterdam, 1980, pp. 181–200.CrossRefGoogle Scholar
[14]Nerode, A. and Shore, R.A., Reducibility orderings: Theories, definability and automorphisms, Annals of Mathematcal Logic, vol. 18 (1980), pp. 61–89.CrossRefGoogle Scholar
[15]Odifreddi, P.G., Classical recursion theory (to appear).Google Scholar
[16]Posner, D., High degrees, Doctoral dissertation, University of California, Berkeley, 1977.Google Scholar
[17]Rogers, H., Theory of recursive functions and effective computability, McGraw Hill, New York, 1967.Google Scholar
[18]Sacks, G.E., Degrees of unsolvability, Annals of Mathematical Studies, no. 55, Princeton University Press, Princeton, N.J., 1963.Google Scholar
[19]Sacks, G.E., Forcing with perfect closed sets, Proceedings of Symposia in Pure Mathematics, vol. XIII, part I, American Mathematical Society, Providence, R.I., 1971, pp. 331–355.Google Scholar
[20]Selman, A.L., Applications of forcing to the degree-theory of the arithmetical hierarchy, Proceedings of the London Mathematical Society, vol. 25 (1972), pp. 586–602.CrossRefGoogle Scholar
[21]Shoenfield, J.R., On degrees of unsolvability, Annals of Mathematics, vol. 69 (1959), pp. 644–653.CrossRefGoogle Scholar
[22]Shoenfield, J.R., Mathematical logic, Addison-Wesley, Reading, Mass., 1967.Google Scholar
[23]Shoenfield, J.R., Unramified forcing, Proceedings of Symposia in Pure Mathematics, vol. XIII, part I, American Mathematical Society, Providence, R.I., 1971, pp. 357–381.Google Scholar
[24]Spector, C., On degrees of recursive unsolvability, Annals of Mathematics, vol. 64 (1956), pp. 581–592.CrossRefGoogle Scholar