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. Higher Recursion Theory
  • Cited by 6
Publisher:
Cambridge University Press
Online publication date:
March 2017
Print publication year:
2017
Online ISBN:
9781316717301
DOI:
https://doi.org/10.1017/9781316717301
Subjects:
Mathematics, Logic, Categories and Sets, Computer Science, Programming Languages and Applied Logic
Series:
Perspectives in Logic (2)
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. This volume, the second publication in the Perspectives in Logic series, is an almost self-contained introduction to higher recursion theory, in which the reader is only assumed to know the basics of classical recursion theory. The book is divided into four parts: hyperarithmetic sets, metarecursion, α-recursion, and E-recursion. This text is essential reading for all researchers in the field.

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
Bibliography
Aczel, P, Richter, W (1972) Inductive definitions and analogues of large cardinals. In: Conference in Math. Log., London 1970. Springer, Berlin Heidelberg New York, p 1–9
Bailey, C (1984) Beta-degrees for weakly inadmissible sets. Ph.D. Thesis, Harvard University, Cambridge, MA
Barwise, J (1979) Admissible sets and structures. Springer, Berlin Heidelberg New York
Cenzer, D (1976) Monotonic inductive definitions over the continuum J. Symb. Log. 41: 188–198
Chong, CT, Lerman, M (1976) Hyperhypersimple α-r.e. sets. Ann. Math. Log. 9: 1–42
Chong, CT (1979) Generic sets and minimal α-degrees, Trans. Amer. Math. Soc. 254: 157–169
Chong, CT (1984) Techniques of Admissible Recursion Theory. Springer, Berlin Heidelberg New York
Church, A, Kleene, SC (1937) Formal definitions in the theory of ordinal numbers. Fund. Math. 28: 11–21
Dekker, JCE (1954) A theorem on hypersimple sets. Proc. Amer. Math. Soc. 5: 791–796
Devlin, K (1984) Constructibility. Springer, Berlin Heidelberg New York
Driscoll, GC Jr. (1968) Metarecursively enumerable sets and their metadegrees, J. Symb. Log. 33: 389–411
Feferman, S, Spector, C (1962) Incompleteness along paths in progressions of theories. J. Symb. Log. 27: 383–390
Feferman, S (1965) Some applications of the notions of forcing and generic sets. Fund. Math. 56: 325–345
Fenstad, JE (1980) General recursion theory. Springer, Berlin Heidelberg New York
Friedberg, R (1957a) A criterion for completeness of degrees of unsolvability, J. Symb. Log. 22:159–160
Friedberg, R (1957b) Two recursively enumerable sets of incomparable degrees of unsolvability. Proc. Nat. Acad. Sci. USA 43: 236–238
Friedman, SD (1976) Recursion on Inadmissible Ordinals. Ph.D. Thesis, Massachusetts Institute of Technology
Friedman, SD, Sacks, GE (1977) Inadmissible recursion theory, Bull. Math. Soc. 83: 255–256
Friedman, SD (1979) βrecursion theory. Trans. Amer. Math. Soc. 255: 173–200
Friedman, SD (1981a) Uncountable admissibles II: compactness. Israel J. Math. 40: 129–149
Friedman, SD (1981b) Negative solutions to Post's problem. II. Ann. Math. 113: 25–43
Gandy, RO (1960) Proof of Mostowski's conjecture. Bull. Acad. Polon. Sci. Math. 8: 571–575
Gandy, RO (1967) General recursive functionals of finite type and hierarchies of functionals. Ann. Fac. Sci. Univ. Clermont-Ferrand 35: 202–242
Gandy, RO, Sacks, GE (1967) A minimal hyperdegree, Fund. Math. 61: 215–223
Green, J (1974) Σ1 compactness for next admissible sets. J. Symb. Log. 39: 105–116
Griffor, ER (1980) E-Recursively Enumerable Degrees. Ph.D. Thesis, Massachusetts Institute of Technology
Griffor, ER, Normann, D (1982) Effective confinalities and admissibility in Erecursion. Preprint, University of Oslo
Grilliot, T (1969) Selection functions for recursive functionals. Notre Dame Jour. Formal Log. p. 225–234
Harrington, L (1973) Contributions to recursion theory, in higher types. Ph.D. Thesis, (Massachusetts Institute of Technology, Cambridge MA)
Harrington, L, MacQueen, D (1976) Selection in abstract recursion theory, J. Symb. Log. 41: 153–158
Hinman, P (1978) Recursion–Theoretic Hierarchies. Springer, Berlin Heidelberg New York
Homer, S, Sacks, GE (1983) Inverting the half-jump. Trans. Amer. Math. Soc. 278: 317–331
Hoole, T (1982) Abstract extended 2-sections. Ph.D. thesis, Oxford University (Note: the date and title of this reference are approximate.)
Jech, T (1978) Set Theory. Academic Press, New York
Jockusch, C, Simpson, S (1976) A degree-theoretic definition of the ramified analytical hierarchy, Ann. Math. Log. 10: 1–32
Kleene, SC (1943) Recursive predicates and quantifiers, Trans. Amer. Math. Soc. 53: 41–73
Kleene, SC (1952) Introduction to Metamathematics. Van Nostrand, New York.
Kleene, SC (1955a) Arithmetical predicates and function quantifies, Trans. Amer. Math. Soc. 79:312–340
Kleene, SC (1955b) Hierarchies of number-theoretic predicates, Bull. Amer. Math. Soc. 61: 193–213
Kleene, SC (1955c) On the forms of the predicates in the theory of constructive ordinals II, Amer. J. Math. 77: 405–428
Kleene, SC (1959) Recursive functionals and quantifies of finite types I. Trans. Amer. Math. Soc. 91:1–52
Kleene, SC (1963) Recursive functionals and quantifies of finite types II, Trans. Amer. Math. Soc. 108: 106–142
Kreisel, G (1961) Set theoretic methods suggested by the notion of potential totality. In: Infinitistic Methods. Pergamon, Oxford, 325–369
Kreisel, G (1962) The axiom of choice and the class of hyperarithmetic functions, Indag. Math. 24: 307–319
Kreisel, G, Sacks, GE (1963) Metarecursive sets I, II (abstracts), J. Symb. Log. 28: 304–305
Kreisel, G (1965) Model-theoretic invariants: applications to recursive and hyperarithmetic operations. In: Theory of models. North-Holland, Amsterdam, p 190–205
Kreisel, G, Sacks, GE (1965) Metarecursive sets, J. Symb. Log. 30 p 318–338
Kreisel, G (1971) Some reasons for generalizing recursion theory. In: Logic Colloquium ’69. North-Holland Amsterdam, p 139–198
Kripke, S (1964) Transfinite recursion on admissible ordinals I, II (abstracts), J. Symb. Log. 29:161–162
Lachlan, AH (1966) Lower bounds for pairs of recursively enumerable degrees. Proc. London Math. Soc. 16: 537–569
Lachlan, AH (1975) A recursively enumerable degree which will not split over all lesser ones. Ann. Math. Log. 9: 307–365
Levy, A (1963) Transfinite computability (abstract), Notices Amer. Math. Soc. 10: 286
Lerman, M, Sacks, GE (1972) Some minimal pairs of αrecursively enumerable degrees. Ann. Math. Log. 4: 415–42
Lerman, M (1974) Maximal α-r.e. sets. Trans. Amer. Math. Soc. 188: 341–386
Lerman, M (1983) Degrees of unsolvability. Springer, Berlin Heidelberg New York
Louveau, A (1980) A separation theorem for Σ1 1 sets, Trans. Amer. Math. Soc. 260: 363–378
Maass, W (1977a) Minimal pairs and minimal degrees in higher recursion theory. Zeit. Math. Logik 18: 169–186
Maass, W (1977b) Contributions to α- and βrecursion theory. Habilitationsschrift, Universität München
Maass, W (1978a) The uniform regular set theorem in arecursion theory. J. Symb. Log. 43: 270–279
Maass, W (1978b) Inadmissibility, tame r.e. sets and the admissible collapse. Ann. Math. Log. 13: 149–170
Machover, M (1961) The theory of transfinite recursion. Bull. Amer. Math. Soc. 67: 575–578
Machtey, M (1970) Admissible ordinals and intrinsic consistency. J. Symb. Log. 35: 389–400
Macintyre, JM (1968) Contributions to metarecursion theory. Ph.D. Thesis, M.I.T., Cambridge MA
Macintyre, JM (1973) Minimal αrecursion theoretic degrees. J. Symb. Log. 38: 18–28
MacQueen, D (1972) Recursion in finite types. Ph.D. Thesis. M.I.T., Cambridge MA
Moldstad, J (1977) Computations in higher types. Lecture Notes in Math. 574. Springer, Berlin Heidelberg New York
Moschovakis, YN (1966) Many-one degrees of the Ha(x) predicates. Parif. Jour. Math. 18: 329–342
Moschovakis, YN (1980) Descriptive set theory. North-Holland, Amsterdam
Muchnik, AA (1956) On the unsolvability of the problem of reducibility in the theory of algorithms. Dokl. Akad. Nauk SSSR, N.S. 108: 194–197
Normann, D (1974) Imbedding of higher type theories. Preprint Series in Math. 16: Oslo
Normann, D (1975) Degrees of functionals. Preprint Series in Math. 22: Oslo
Normann, D (1978a) Set recursion. In: Generalized recursion theory II. North-Holland, Amsterdam, 303–320
Normann, D (1978b) Recursion in 3 E and a splitting theorem. In: Essays on mathematical and philosophical logic. D. Reidel, Dordrecht, p 275–285
Ohashi, K (1970) On a question of G.E. Sacks. J. Symb. Log. 35: 46–50
Owings, JC Jr. (1969) Π1 1-sets, ω-sets and metacompleteness. J. Symb. Log. 34: 194–204
Platek, R (1966) Foundations of recursion theory, Ph.D. Thesis. Stanford University, Stanford CA
Post, EL (1944) Recursively enumerable sets of positive integers and their decision problems. Bull. Amer. Math. Soc. 50: 284–316
Richter, W (1967) Constructive transfinite number classes. Bull. Amer. Math. Soc. 73: 261–265
Rogers, H Jr. (1967) Theory of recursive functions and effective computability. McGraw-Hill, New York
Sacks, GE (1963a) Recursive enumerability and the jump operator. Trans. Amer. Math. Soc. 108: 223–239
Sacks, GE (1963b) On the degrees less than 0′. Annals of Math. 77: 211–231
Sacks, GE (1964) The recursively enumerable degrees are dense. Ann. of Math. 80: 193–205
Sacks, GE (1966) Post's problem, admissible ordinals and regularity. Trans. Amer. Math. Soc. 124:1–23
Sacks, GE (1969) Measure theoretic uniformity in recursion theory and set theory. Trans. Amer. Math. Soc. 142: 381–420
Sacks, GE (1970) Recursion in objects of finite type. Proc. Internat. Cong. Math. 1: 251–254
Sacks, GE (1971) Forcing with perfect closed sets. In Axiomatic set theory, Proc. Symposia in Pure Math. Amer. Math. Soc. 13: 331–355
Sacks, GE, Simpson, S (1972) The α-finite injury method. Ann. Math. Log. 4: 343–367
Sacks, GE (1974) The 1-section of a type n-object. In: Generalized recursion theory. North-Holland, Amsterdam, p 81–96
Sacks, GE (1976) Countable admissible ordinals and hyperdegrees. Advances in Math. 19: 213–262
Sacks, GE (1977) The k-section of a type n-object. Amer. J. Math. 99: 901–917
Sacks, GE (1980) Post's problem, absoluteness and recursion in finite types. In The Kleene Symposium, North-Holland, Amsterdam, p 201–222
Sacks, GE (1985) Post's problem in Erecursion. In Proceedings of symposia in pure mathematics. Amer. Math. Soc. 42: 177–193
Sacks, GE (1986) On the limits of E-recursive enumerability. Ann. of Pure and Applied Logic 31: 87–120
Sacks, GE, Slaman, TA (1987) Inadmissible forcing. Advances in Math. 66: 1–30
Sacks, GE (199?) Set forcing over E-closed structures (to appear)
Shore, RA (1974) Σ n sets which are ∆ n incomparable (uniformly). J. Symb. Log. 39: 295–304
Shore, RA (1975a) The irregular and non-hyperregular α-r.e. degrees, Israel J. Math. 22: 28–411
Shore, RA (1975b) Splitting an αrecursively enumerable set. Trans. Amer. Math. Soc. 204: 65–78
Shore, RA (1975c) Some more minimal pairs of arecursively enumerable degrees (abstract). Notices Amer. Math. Soc. 22: A524–525
Shore, RA (1976a) The recursively enumerable α-degrees are dense. Ann. Math. Log. 9: 123–155
Shore, RA (1976b) Combining the density and splitting theorem for α-r.e. degrees (abstract). Notices Amer. Math. Soc. 23: A598
Simpson, SG (1971) Admissible Ordinals and Recursion Theory. Ph.D. Thesis, M.I.T., Cambridge MA
Simpson, SG (1974a) Degree theory on admissible ordinals. In Generalized recursion theory, Proceedings of the 1972 Oslo Symposium. North-Holland, Amsterdam, p 165–194
Simpson, SG (1974b) Post's problem for admissible sets. In Generalized recursion theory, Proceedings of the 1972 Oslo Symposium, North-Holland, Amsterdam, p 437–441
Slaman, TA (1981) Aspects of E-Recursion. Ph.D. Thesis. Harvard University, Cambridge MA
Slaman, TA (1983) The extended plus-one hypothesis–a relative consistency result. Nagoya Math. J. 92: 107–120
Slaman, TA (1985a) Reflection and forcing in Erecursion theory. Ann. Pure Appl. Log. 29: 79–106
Slaman, TA (1985b) The Erecursively enumerable degrees are dense. In Proceedings of symposia in pure mathematics. Amer. Math. Soc. 42, 195–213
Soare, RI (1987) Recursively enumerable sets and degrees. Springer, Berlin Heidelberg New York
Spector, C (1955) Recursive well-orderings, J. Symb. Log. 20: 151–163
Spector, C (1956) On degrees of recursive unsolvability, Ann. of Math. 64: 581–592
Spector, C (1959) Hyperarithmetic quantifiers, Fund. Math. 48: 313–320
Stoltenberg-Hansen, V (1977) Finite injury argument in infinite computation theories. Preprint Series in Math. 12: Oslo
Suzuki, Y (1964) A complete classification of the Δ1 2 functions, Bull. Amer. Math. Soc. 70: 246–253
Takeuti, G (1960) On the recursive functions of ordinal numbers. J. Math. Soc. Japan 12: 119–128
Tanaka, H (1968) A basis result for Π1 1-sets of positive measure. Comment. Math. Univ. St. Paul 16: 115–127
Tugué, T (1964) On the partial recursive functions of ordinal numbers. J. Math. Soc. Japan 16: 1–31
vande, Wiele J (1982) Recursive dilators and generalized recursion. In Proceedings of the Herbrand Symposium. North-Holland, Amsterdam, p 325–332
Yang, DP (1984) On the embedding of α-recursive presentable lattices in the a-recursive degrees below 0′. J. Symb. Log. 49: 488–502
Yates, CEM (1966) A minimal pair of recursively enumerable degrees. J. Symb. Log. 31: 159–168

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.