On the relations between some rate-of-growth conditions

McLaughlin, T. G.

doi:10.1090/S0002-9939-1978-0498050-0

On the relations between some rate-of-growth conditions
HTML articles powered by AMS MathViewer

by T. G. McLaughlin PDF

Proc. Amer. Math. Soc. 69 (1978), 151-155 Request permission

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

A. N. Degtev, Hypersimple sets with retraceable complements, Algebra i Logika 10 (1971), 235–246 (Russian). MR 0288023
Erik Ellentuck, On the degrees of universal regressive isols, Math. Scand. 32 (1973), 145–164 (1974). MR 332462, DOI 10.7146/math.scand.a-11451
H. Gonshor, Recursive density types. II, Trans. Amer. Math. Soc. 140 (1969), 505–509. MR 250870, DOI 10.1090/S0002-9947-1969-0250870-2
Donald A. Martin, Classes of recursively enumerable sets and degrees of unsolvability, Z. Math. Logik Grundlagen Math. 12 (1966), 295–310. MR 224469, DOI 10.1002/malq.19660120125
T. G. McLaughlin, Trees and isols. I, Rocky Mountain J. Math. 5 (1975), 401–418. MR 414335, DOI 10.1216/RMJ-1975-5-3-401
T. G. McLaughlin, Trees and isols. II, Z. Math. Logik Grundlagen Math. 22 (1976), no. 1, 45–78. MR 429529, DOI 10.1002/malq.19760220106
Gerald E. Sacks, A maximal set which is not complete, Michigan Math. J. 11 (1964), 193–205. MR 166090
S. Tennenbaum, Degree of unsolvability and the rate of growth of functions, Proc. Sympos. Math. Theory of Automata (New York, 1962) Polytechnic Press of Polytechnic Inst. of Brooklyn, Brooklyn, N.Y., 1963, pp. 71–73. MR 0167406