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
×
  1. Home
  2. Books
  3. Degrees of Unsolvability
  • Cited by 4
Publisher:
Cambridge University Press
Online publication date:
March 2017
Print publication year:
2017
Online ISBN:
9781316717059
DOI:
https://doi.org/10.1017/9781316717059
Subjects:
Mathematics, Logic, Categories and Sets, Abstract Analysis, Programming Languages and Applied Logic
Series:
Perspectives in Logic (11)
Information

Book description

Since their inception, the Perspectives in Logic and Lecture Notes in Logic series have published seminal works by leading logicians. Many of the original books in the series have been unavailable for years, but they are now in print once again. In this volume, the eleventh publication in the Perspectives in Logic series, Manuel Lerman presents a systematic study of the interaction between local and global degree theory. He introduces the reader to the fascinating combinatorial methods of recursion theory while simultaneously showing how to use these methods to prove global theorems about degrees. The intended reader will have already taken a graduate-level course in recursion theory, but this book will also be accessible to those with some background in mathematical logic and a feeling for computability. It will prove a key reference to enable readers to easily locate facts about degrees and it will direct them to further results.

Refine List

Actions for selected content:

Select all | Deselect all
  • View selected items
  • Export citations
  • Download PDF (zip)
  • Save to Kindle
  • Save to Dropbox
  • Save to Google Drive

Save Search

You can save your searches here and later view and run them again in "My saved searches".

Please provide a title, maximum of 40 characters.
Cancel
×

Contents

Contents
References
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.

Metrics

Full text views

Total number of HTML views: 0
Total number of PDF views: 0 *
Loading metrics...

Book summary page views

Total views: 0 *
Loading metrics...

* Views captured on Cambridge Core between #date#. This data will be updated every 24 hours.

Usage data cannot currently be displayed.