Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

$ \beta $-recursion theory


Author: Sy D. Friedman
Journal: Trans. Amer. Math. Soc. 255 (1979), 173-200
MSC: Primary 03D60; Secondary 03E45
DOI: https://doi.org/10.1090/S0002-9947-1979-0542876-7
MathSciNet review: 542876
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We define recursion theory on arbitrary limit ordinals using the J-hierarchy for L. This generalizes $ \alpha $-recursion theory, where the ordinal is assumed to be $ {\Sigma _1}$-admissible. The notion of tameness for a recursively enumerable set is defined and the degrees of tame r.e. sets are studied. Post's Problem is solved when $ {\Sigma _1}\operatorname{cf} \beta \,\beta {\ast} $. Lastly, simple sets are constructed for all $ \beta $ with the aid of a $ \beta $-recursive version of Fodor's Theorem.


References [Enhancements On Off] (What's this?)

  • [1] Keith J. Devlin, Aspects of constructibility, Lecture Notes in Math., vol. 354, Springer-Verlag, Berlin, 1973. MR 0376351 (51:12527)
  • [2] R. Friedberg, Two r.e. sets of incomparable degrees of unsolvability, Proc. Nat. Acad. Sci. U.S. A. 43 (1957). MR 0084474 (18:867a)
  • [3] Sy D. Friedman, Recursion on inadmissible ordinals, Ph. D. Thesis, M. I. T., 1976.
  • [4] -, Post's Problem without admissibility, Advances in Math. (to appear).
  • [5] Sy D. Friedman and Gerald E. Sacks, Inadmissible recursion theory, Bull. Amer. Math. Soc. 83 (1977). MR 0505378 (58:21536)
  • [6] K. Gödel, Consistency proof for the generalized continuum hypothesis, Proc. Nat. Acad. Sci. U. S. A. 25 (1939).
  • [7] R. Jensen, The fine structure of the constructible hierarchy, Ann. Math. Logic 4 (1972). MR 0309729 (46:8834)
  • [8] G. Kreisel and G. Sacks, Metarecursive sets, J. Symbolic Logic 30 (1965). MR 0213233 (35:4097)
  • [9] S. Kripke, Transfinite recursion on admissible ordinals. I, II, J. Symbolic Logic 29 (1964).
  • [10] M. Lerman, Maximal a-r.e. sets, Trans. Amer. Math. Soc. 188 (1974). MR 0332458 (48:10785)
  • [11] M. Lerman and G. Sacks, Some minimal pairs of a-r.e. degrees, Ann. Math. Logic 4 (1972). MR 0439605 (55:12491)
  • [12] W. Maass, Inadmissibility, tame r.e. sets and the admissible collapse, Ann. Math. Logic. 13 (1978). MR 486628 (80a:03060)
  • [13] A. A. Muchnik, Negative answer to the problem of reducibility of the theory of algorithms, Dokl. Akad. Nauk SSSR 108 (1956).
  • [14] R. Platek, Foundations of recursion theory, Ph. D. Thesis, Stanford, 1966.
  • [15] E. L. Post, R. E. sets and their decision problems, Bull. Amer. Math. Soc. 50 (1944). MR 0010514 (6:29f)
  • [16] G. Sacks, Post's Problem, admissible ordinals and regularity, Trans. Amer. Math. Soc. 124 (1966). MR 0201299 (34:1183)
  • [17] G. Sacks and S. Simpson, The $ \alpha $-finite injury method, Ann. Math. Logic 4 (1972). MR 0369041 (51:5277)
  • [18] R. Shore, Splitting an a-r.e. sets, Trans. Amer. Math. Soc. 204 (1975). MR 0379154 (52:60)
  • [19] -, The r.e $ \alpha $-degrees are dense, Ann. Math. Logic 9 (1976).
  • [20] S. Simpson, Admissible ordinals and recursion theory, Ph. D. Thesis, M. I. T., 1971.
  • [21] -, Degree theory on admissible ordinals, Generalized Recursion Theory (Fenstad, Editor) Hinman, 1974.

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 03D60, 03E45

Retrieve articles in all journals with MSC: 03D60, 03E45


Additional Information

DOI: https://doi.org/10.1090/S0002-9947-1979-0542876-7
Keywords: $ \beta $-recursion theory, priority arguments, fine structure of L, $ {\Sigma _1}$-cofinality
Article copyright: © Copyright 1979 American Mathematical Society

American Mathematical Society