On retraceable sets with rapid growth
HTML articles powered by AMS MathViewer
- by T. G. McLaughlin PDF
- Proc. Amer. Math. Soc. 40 (1973), 573-576 Request permission
Abstract:
We combine a refinement of a recent theorem of A. N. Degtev with a result of our own, in order to derive a general theorem about regressive sets which has the following Corollary. If $A$ is any point-decomposable $\pi _1^0$ set then $A$ has an infinite $\pi _1^0$ subset $B$ such that $B$ has “highly” dense-simple complement and, moreover, all infinite $\pi _1^0$ subsets of $B$ are effectively decomposable in a strong sense (namely, they are all retraceable).References
- A. N. Degtev, Hypersimple sets with retraceable complements, Algebra i Logika 10 (1971), 235–246 (Russian). MR 0288023
- J. C. E. Dekker, Infinite series of isols, Proc. Sympos. Pure Math., Vol. V, American Mathematical Society, Providence, R.I., 1962, pp. 77–96. MR 0142447
- 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
- Judith Gersting, A rate of growth criterion for universality of regressive isols, Pacific J. Math. 31 (1969), 669–677. MR 255397, DOI 10.2140/pjm.1969.31.669
- Carl G. Jockusch Jr., Semirecursive sets and positive reducibility, Trans. Amer. Math. Soc. 131 (1968), 420–436. MR 220595, DOI 10.1090/S0002-9947-1968-0220595-7
- A. H. Lachlan, On the lattice of recursively enumerable sets, Trans. Amer. Math. Soc. 130 (1968), 1–37. MR 227009, DOI 10.1090/S0002-9947-1968-0227009-1
- Donald A. Martin, A theorem on hyperhypersimple sets, J. Symbolic Logic 28 (1963), 273–278. MR 177887, DOI 10.2307/2271305
- T. G. McLaughlin, Strong reducibility on hypersimple sets, Notre Dame J. Formal Logic 6 (1965), 229–234. MR 193012, DOI 10.1305/ndjfl/1093958262
- T. G. McLaughlin, Hereditarily retraceable isols, Bull. Amer. Math. Soc. 73 (1967), 113–115. MR 204286, DOI 10.1090/S0002-9904-1967-11669-0 —, Thinning the branches of a semicomputable tree (to appear).
- Robert W. Robinson, A dichotomy of the recursively enumerable sets, Z. Math. Logik Grundlagen Math. 14 (1968), 339–356. MR 237334, DOI 10.1002/malq.19680142105
Additional Information
- © Copyright 1973 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 40 (1973), 573-576
- MSC: Primary 02F25
- DOI: https://doi.org/10.1090/S0002-9939-1973-0340010-X
- MathSciNet review: 0340010