Skip to main content Accessibility help

We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.

Close cookie message
×
Hostname: page-component-6bf8c574d5-j5c6p Total loading time: 0 Render date: 2025-03-04T00:50:38.829Z Has data issue: false hasContentIssue false

References

Published online by Cambridge University Press:  31 March 2017

Manuel Lerman
Manuel Lerman
Affiliation:
University of Connecticut
Get access

Summary

A summary is not available for this content so a preview has been provided. Please use the Get access link above for information on how to access this content.
Image of the first page of this content. For PDF version, please use the ‘Save PDF’ preceeding this image.'
Type
Chapter
Information
Degrees of Unsolvability
Local and Global Theory
 , pp. 293 - 297
Publisher: Cambridge University Press
Print publication year: 2017

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

Bar-Hillel, Y. 1970 Mathematical Logic and Foundations of Set Theory, (Proceedings of an International Colloquium, Jerusalem, 1968, Editor), North-Holland, Amsterdam, 1970.
Barwise, J., Keisler, H. J., Kunen, K. 1980 The Kleene Symposium (Editors), North-Holland, Amsterdam, 1980.
Birkhoff, G. 1940 Lattice Theory, American Mathematical Society Colloquium Publications XXV, Amer. Math. Soc, Providence, R.I., 1940.
Cohen, P. J. 1963/64 The independence of the continuum hypothesis I, II, Proc. Nat. Acad. Sci. USA 50 (1963) 1143-48; 57 (1964), 105-10.
Cooper, S. B. 1973 Minimal degrees and the jump operator, Jour. Symb. Logic 38 (1973), 249-71.
Cooper, S. B. 1974 Minimal pairs and high recursively enumerable degree, Jour. Symb. Logic 39 (1974), 655-60.
Crossley, J. N. 1967 Sets, Models, and Recursion Theory (Proceedings of the Summer School in Mathematical Logic and Logic Colloquium, Leicester, England, 1965, Editor), North-Holland, Amsterdam, 1967.
Cutland, N. J. 1980 Computability: An Introduction to Recursive Function Theory, Cambridge University Press, Cambridge, 1980.
Drake, F. R., Wainer, S. S. 1980 Recursion Theory: Its Generalisations and Applications (Proceedings of Logic Colloquium '79, Leeds, August 1979, Editors), London Mathematical Society Lecture Notes Series 45, Cambridge University Press, Cambridge, 1980.
Epstein, R. L. 1975 Minimal Degrees of Unsolvability and the Full Approximation Construction, Memoirs of the American Mathematical Society 162, Amer. Math. Soc, Providence, R.I., 1975.
Epstein, R. L. 1979 Degrees of Unsolvability: Structure and Theory: Lecture Notes in Mathematics 759, Springer-Verlag, Berlin, Heidelberg, New York, 1979.
Epstein, R. L. 1981 Initial Segments of Degrees Below 0’, Memoirs of the American Mathematical Society 241, Amer. Math. Soc, Providence, R.I., 1981.
Epstein, R. L., Posner, D. 1978 Diagonalization in degree constructions, Jour. Symb. Logic 43 (1978), 280-3.
Ershov, Y., Taitslin, M. A. 1963 The undecidability of certain theories, Algebra i Logika 2 (1963), 37-41.
Feferman, S. 1965 Some applications of the notions of forcing and generic sets, Fund. Math. 56 (1965), 325-45.
Feiner, L. 1970 The strong homogeneity conjecture, Jour. Symb. Logic 35 (1970), 375-77.
Fenstad, J. E., Gandy, R. O., Sacks, G. E. 1978 Generalized Recursion Theory II (Editors), Studies in Logic and the Foundations of Mathematics 94, North-Holland, Amsterdam, 1978.
Friedberg, R. M. 1957 A criterion for completeness of degrees of unsolvability, Jour. Symb. Logic 22 (1957), 159-60.
Friedberg, R. M. 1957a Two recursively enumerable sets of incomparable degrees of unsolvability, Proc. Nat. Acad. Sci. U.S.A. 43 (1957), 236-8.
Friedberg, R. M. 1957b The fine structure of degrees of unsolvability of recursively enumerable sets, In: Summaries of Cornell Summer Institute for Symbolic Logic, Communications Research Division, Inst. Def. Anal. 1957; pp. 404-6.
Groszek, M., Slaman, T. 1983 Independence results on the global structure of the Turing degrees, to appear.
Harrington, L., Kechris, A. 1975 A basis result for Σ 3 0 sets of reals with an application to minimal covers, Proc. Amer. Math. Soc. 53 (1975), 445-8.
Harrington, L., Shore, R. A. 1981 Definable degrees and automorphisms of D, Bull. Amer. Math. Soc. (new series) 4 (1981), 97-100.
Hinman, P. G. 1969 Some applications of forcing to hierarchy problems in arithmetic, Z. Math. Logik und Grund. der Math. 75 (1969), 341-52.
Hodges, W. 1972 Conference in Mathematical Logic, London, 1970 (Editor), Lecture Notes in Mathematics 255, Springer-Verlag, Berlin, Heidelberg, New York, 1972.
Hugill, D. F. 1969 Initial segments of Turing degrees, Proc. London Math. Soc. 19 (1969), 1-16.
Jockusch, C. G. Jr. 1973 An application of Z°A determinacy to the degrees of unsolvability, Jour. Symb. Logic 38 (1973), 293-5.
Jockusch, C. G. Jr. 1974 Review of Selman [1972], Mathematical Reviews 47 3155 (1974), 549.
Jockusch, C. G. Jr. 1977 Simple proofs of some theorems on high degrees of unsolvability, Can. J. Math. 29 (1977), 1072-80.
Jockusch, C. G. Jr. 1980 Degrees of generic sets, In: Drake-Wainer [1980], pp. 110-39.
Jockusch, C. G. Jr., Posner, D. 1978 Double jumps of minimal degrees, Jour. Symb. Logic 43 (1978), 715-24.
Jockusch, C. G. Jr., Posner, D. 1981 Automorphism bases for degrees of unsolvability, Israel Jour. Math. 40 (1981), 150-64.
Jockusch, C. G. Jr., Shore, R. A. 1983 Pseudo Jump Operators I: The R. E. case, Trans. Amer. Math. Soc. 275 (1983), 599-609.
Jockusch, C. G. Jr., Shore, R. A. 1983a Pseudo Jump Operators II: Transfinite iterations and minimal covers, to appear.
Jockusch, C. G. Jr., Simpson, S. G. 1976 A degree theoretic definition of the ramified analytical hierarchy, Ann. Math. Logic 10 (1976), 1-32.
Jockusch, C. G. Jr., Soare, R. I. 1970 Minimal covers and arithmetical sets, Proc. Amer. Math. Soc. 25 (1970), 856-9.
Jockusch, C. G. Jr., Solovay, R. M. 1977 Fixed points of jump preserving automorphisms of degrees, Israel Jour. Math. 26 (1977), 91-4.
Jónsson, B. 1953 On the representation of lattices. Math. Scand. 1 (1953), 193-206.
Kleene, S. C. 1943 Recursive predicates and quantifiers, Trans. Amer. Math. Soc. 53 (1943), 41-73.
Kleene, S. C. 1952 Introduction to Metamathematics, D. van Nostrand Co., New York, Toronto, 1952.
Kleene, S. C, Post, E. L. 1954 The upper semi-lattice of degrees of recursive unsolvability, Ann. Math. 59 (1954), 379-407.
Lachlan, A. H. 1965 On a question of G. E. Sacks, Proc. Amer. Math. Soc. 16 (1965), 972-9.
Lachlan, A. H. 1968 Distributive initial segments of the degrees of unsolvability, Z. Math. Logik und Grund. der Math. 14 (1968), 457-72.
Lachlan, A. H. 1971 Solution to a problem of Spector, Can. Jour. Math. 23 (1971), 247-56.
Lachlan, A. H., Lebeuf, R. 1976 Countable initial segments of the degrees of unsolvability, Jour. Symb. Logic 41 (1976), 289-300.
Lacombe, D. 1954 Sur le semi-reseau constitue par les degres d'indecidabilite recursive, C. R. Acad. Sci. Paris 239(1954), 1108-9.
Lerman, M. 1969 Some nondistributive lattices as initial segments of the degrees of unsolvability, Jour. Symb. Logic 34 (1969), 85-98.
Lerman, M. 1971 Initial segments of the degrees of unsolvability, Ann. Math. 93 (1971), 365-89.
Lerman, M. 1977 Automorphism bases for the semilattice of recursively enumerable degrees, Notices Amer. Math. Soc. 77T-E10 24 (1977), A-251.
Lerman, M., Schmerl, J. H., Soare, R. I. 1981 Logic Year 1979-80: The University of Connecticut (Editors), Lecture Notes in Mathematics 859, Springer-Verlag, Berlin, Heidelberg, New York, 1981.
Manaster, A. B. 1971 Some contrasts between degrees and the arithmetical hierarchy, Jour. Symb. Logic 36(1911), 301-4.
Martin, D. A. 1966 On a question of G. E. Sacks, Jour. Symb. Logic 31 (1966), 66-9.
Martin, D. A. 1966a Classes of recursively enumerable sets and degrees of unsolvability, Z. Math. Logik und Grund. der Math. 12 (1966), 295-310.
Martin, D. A. 1968 The axiom of determinateness and reduction principles in the analytical hierarchy, Bull. Amer. Math. Soc. 74 (1968), 687-9.
Martin, D. A. 1975 Borel determinacy, Ann. Math. 102 (1975), 363-71.
Martin, D. A., Solovay, R. M. 1970 Internal Cohen extensions, Ann. Math. Logic 2 (1970), 143-78.
Miller, W., Martin, D. A. 1968 The degrees of hyperimmune sets, Z. Math. Logik und Grund. der Math. 14 (1968), 159-66.
Muchnik, A. A. 1956 Negative answer to the problem of reducibility of the theory of algorithms (Russian), Dokl. Akad. nauk SSSR 108 (1956), 194-7.
Nerode, A., Shore, R. A. 1979 Second Order Logic and first order theories of reducibility orderings, In: Barwise-Keisler-Kunen[1980]; pp. 181-200.
Nerode, A., Shore, R. A. 1980 Reducibility orderings: Theories, definability and automorphisms, Ann. Math. Logic 18 (1980), 61-89.
Owings, J. C. Jr. 1973 Diagonalization and the recursion theorem, Notre Dame Jour. Formal Logic 14 (1973), 95-9.
Paris, J. B. 1972 ZF -Σ0 4-determinateness, Jour. Symb. Logic 37 (1972), 661-7.
Posner, D. 1977 High Degrees, Doctoral Dissertation, Univ. of Cal., Berkeley, 1977.
Posner, D. 1980 A survey of non-R. E. degrees ⩽ 0 ’, In: Drake-Wainer [1980]; pp. 52-109.
Posner, D. 1981 The upper semilattice of degrees ⩽ 0’ is complemented, Jour. Symb. Logic 46 (1981), 705-13.
Posner, D., Robinson, R. W. 1981 Degrees joining to 0 ’, Jour. Symb. Logic 46 (1981), 714-22.
Post, E. L. 1943 Formal reductions of the general combinatorial decision problem, Amer. Jour. Math. 65 (1943), 197-215.
Post, E. L. 1944 Recursively enumerable sets of positive integers and their decision problems, Bull. Amer. Math. Soc. 50 (1944), 284-316.
Post, E. L. 1948 Degrees of recursive unsolvability (Preliminary report), abstract, Bull. Amer. Math. Soc. 54 (1948), 641-2.
Richter, L. J. 1979 On automorphisms of the degrees that preserve jumps, Israel Jour. Math. 32 (1979), 27-31.
Rogers, H. Jr. 1967 Theory of Recursive Functions and Effective Computability, McGraw-Hill, New York, 1968.
Rosenstein, J. G. 1968 Initial segments of degrees, Pac. Jour. Math. 24 (1968), 163-72.
Sacks, G. E. 1961 A minimal degree less than 0’, Bull. Amer. Math. Soc. 67 (1961), 416-9.
Sacks, G. E. 1961 a On suborderings of degrees of recursive unsolvability, Z. Math. Logik und Grund. der Math. 7 (1961), 46-56.
Sacks, G. E. 1963 Degrees of Unsolvability, Annals of Mathematics studies 55, Princeton University Press, Princeton, N.J., 1963.
Sacks, G. E. 1963a Recursive enumerability and the jump operator, Trans. Amer. Math. Soc. 108 (1963), 223-39.
Sacks, G. E. 1967 On a theorem of Lachlan and Martin, Proc. Amer. Math. Soc. 18 (1967), 140-1.
Sacks, G. E. 1971 Forcing with perfect closed sets, In: Scott [1971], pp. 331-55.
Sasso, L. P. Jr. 1974 A minimal degree not realizing least possible jump, Jour. Symb. Logic 39 (1974), 571-4.
Scott, D. S. 1971 Axiomatic Set Theory I (Proceedings of the Thirteenth Symposium in Pure Mathematics of the American Mathematical Society, Los Angeles, 1967, Editor), Amer. Math. Soc, Providence, R. I., 1971.
Selman, A. L. 1972 Applications of forcing to the degree-theory of the arithmetical hierarchy, Proc. London Math. Soc. 25 (1972), 586-602.
Shoenfield, J. R. 1959 On degrees of unsolvability, Ann. Math. 69 (1959), 644-53.
Shoenfield, J. R. 1960 An uncountable set of incomparable degrees, Proc. Amer. Math. Soc. 11 (1960), 61-2.
Shoenfield, J. R. 1966 A theorem on minimal degrees, Jour. Symb. Logic 31 (1966), 539-44.
Shoenfield, J. R. 1971 Degrees of Unsolvability, Mathematics studies 2, North-Holland, Amsterdam, 1971.
Shoenfield, J. R. 1971a Unramified forcing, In: Scott [1971]; pp. 357-81.
Shore, R. A. 1977 Determining automorphisms of the recursively enumerable sets, Proc. Amer. Math. Soc. 65 (1977), 318-25.
Shore, R. A. 1978 On the V3-sentences of a-recursion theory, In: Fenstad-Gandy-Sacks [1978]; pp. 331-54.
Shore, R. A. 1979 The homogeneity conjecture, Proc. Nat. Acad. Sci. USA 76 (1979), 4218-19.
Shore, R. A. 1981 The theory of the degrees below 0’, Jour. London Math. Soc. 2, 24 (1981), 1-14.
Shore, R. A. 1981a The degrees of unsolvability: Global results, In: Lerman-Schmerl-Soare [1981]; pp. 283-301.
Shore, R. A. 1982 On homogeneity and definability in the first order theory of the Turing degrees, Jour. Symb. Logic 47 (1982), 8-16.
Simpson, S. G. 1977 First-order theory of the degrees of recursive unsolvability, Ann. Math. 105 (1977), 121-39.
Soare, R. I. 1974 Automorphisms of the lattice of recursively enumerable sets, Bull. Amer. Math. Soc. 80 (1974), 53-8.
Soare, R. I. 1978 Recursively enumerable sets and degrees, Bull. Amer. Math. Soc. 84 (1978), 1149-81.
Soare, R. I. 1984 Recursively Enumerable Sets and Degrees, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, Heidelberg, New York, to appear.
Spector, C. 1956 On degrees of recursive unsolvability, Ann. Math. 64 (1956), 581-92.
Thomason, S. K. 1970 Sublattices and initial segments of the degrees of unsolvability, Can. Jour. Math. 3 (1970), 569-81.
Thomason, S. K. 1970a A proof of Whitman's representation theorem for finite lattices, Proc. Amer. Math. Soc. 25 (1970), 618-9.
Titgemeyer, D. 1962 Untersuchen über die Struktur des Kleene-Postchen Halbverbandes der Grade der rekursiven Unlösbarkeit, Arch. Math. Logik Grundlagenforsch. 8/1-2 (1962), 45-62.
Turing, A. M. 1936/37 On computable numbers, with an application to the Entscheidungsproblem, Proc. London Math. Soc. 2, 42 (1936-7), 230-65; A correction, ibid., 43 (1937), 544-6.
Turing, A. M. 1939 Systems of logic based on ordinals, Proc. London Math. Soc. 2, 45 (1939), 161-228.
Whitman, P. M. 1946 Lattices, equivalence relations, and subgroups, Bull. Amer. Math. Soc. 52 (1946), 507-22.
Yates, C. E. M. 1965 Three theorems on the degrees of recursively enumerable sets, Duke Math. Jour. 32 (1965), 461-8.
Yates, C. E. M. 1966 Density and incomparability in the degrees less than 0 ’, Jour. Symb. Logic 31 (1966), 301-2.
Yates, C. E. M. 1967 Recursively enumerable degrees and the degrees less than 0 ’, In: Crossley [1967]; pp. 264-71.
Yates, C. E. M. 1970 Initial segments of the degrees of unsolvability: Part I: A survey, In: Bar-Hillel [1970]; pp. 63-83.
Yates, C. E. M. 1970a Initial segments of the degrees of unsolvability: Part II: Minimal degrees, Jour. Symb. Logic 35 (1970), 243-66.
Yates, C. E. M. 1972 Initial segments and implications for the structure of degrees, In: Hodges [1970]; pp. 305-35.
Yates, C. E. M. 1976 Banach-Mazur games, comeagre sets, and degrees of unsolvability, Math. Proc. of the Cambridge Phil. Soc. 79 (1976), 195-220.

Save book to Kindle

To save this book to your Kindle, first ensure [email protected] is added to your Approved Personal Document E-mail List under your Personal Document Settings on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part of your Kindle email address below. Find out more about saving to your Kindle.

Note you can select to save to either the @free.kindle.com or @kindle.com variations. ‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi. ‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.

Find out more about the Kindle Personal Document Service.

  • References
  • Manuel Lerman, University of Connecticut
  • Book: Degrees of Unsolvability
  • Online publication: 31 March 2017
  • Chapter DOI: https://doi.org/10.1017/9781316717059.018
Available formats
×

Save book to Dropbox

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Dropbox.

  • References
  • Manuel Lerman, University of Connecticut
  • Book: Degrees of Unsolvability
  • Online publication: 31 March 2017
  • Chapter DOI: https://doi.org/10.1017/9781316717059.018
Available formats
×

Save book to Google Drive

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Google Drive.

  • References
  • Manuel Lerman, University of Connecticut
  • Book: Degrees of Unsolvability
  • Online publication: 31 March 2017
  • Chapter DOI: https://doi.org/10.1017/9781316717059.018
Available formats
×