Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 
 

 

On the relations between some rate-of-growth conditions


Author: T. G. McLaughlin
Journal: Proc. Amer. Math. Soc. 69 (1978), 151-155
MSC: Primary 02F25
DOI: https://doi.org/10.1090/S0002-9939-1978-0498050-0
MathSciNet review: 0498050
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We discuss the implications and nonimplications between four rate-of-growth properties of sets useful in certain areas of recursion theory; all nonimplications are established within the boolean algebra generated by the recursively enumerable sets.


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

  • [1] A. N. Degtev, Hypersimple sets with retraceable complements, Algebra i Logika 10 (1971), 235-246. (Russian) MR 44 #5221. MR 0288023 (44:5221)
  • [2] E. Ellentuck, On the degrees of universal regressive isols, Math. Scand. 32 (1973), 145-164. MR 48 # 10789. MR 0332462 (48:10789)
  • [3] H. Gonshor, Recursive density types. II, Trans. Amer. Math. Soc. 140 (1969), 505-509. MR 40 #4102. MR 0250870 (40:4102)
  • [4] D. A. Martin, Classes of recursively enumerable sets and degrees of unsolvability, Z. Math. Logik Grundlagen Math. 12 (1966), 295-310. MR 37 #68. MR 0224469 (37:68)
  • [5] T. G. McLaughlin, Rees and isols. I, Rocky Mountain J. Math. 5 (1975), 401-418. MR 54 #2438. MR 0414335 (54:2438)
  • [6] -, Trees and isols. II, Z. Math. Logik Grundlagen Math. 22 (1976), 45-78. MR 0429529 (55:2542)
  • [7] G. E. Sacks, A maximal set which is not complete, Michigan Math. J. 11 (1964), 193-205. MR 29 #3368. MR 0166090 (29:3368)
  • [8] S. Tennenbaum, Degree of unsolvability and the rate of growth of functions, Proc. Sympos. Math. Theory of Automata, New York, 1962, 71-73. MR 29 #4679. MR 0167406 (29:4679)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC: 02F25

Retrieve articles in all journals with MSC: 02F25


Additional Information

DOI: https://doi.org/10.1090/S0002-9939-1978-0498050-0
Keywords: Retraceable, cohesive, $ \Sigma _1^0$
Article copyright: © Copyright 1978 American Mathematical Society

American Mathematical Society