Splitting an -recursively enumerable set

Author:
Richard A. Shore

Journal:
Trans. Amer. Math. Soc. **204** (1975), 65-77

MSC:
Primary 02F27

MathSciNet review:
0379154

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We extend the priority method in -recursion theory to certain arguments with no *a priori* bound on the required preservations by proving the splitting theorem for all admissible . THEOREM: *Let be a regular -r.e. set and be a nonrecursive -r.e. set. Then there are regular -r.e. sets and such that and such that is not -recursive in or *. The result is also strengthened to apply to , and various corollaries about the structure of the and recursively enumerable degrees are proved.

**1.**L. Harrington,*Contributions to recursion theory on higher types*, Ph. D. Thesis, M. I. T., Cambridge, Mass., 1973.**[1]**G. Kreisel and Gerald E. Sacks,*Metarecursive sets*, J. Symbolic Logic**30**(1965), 318–338. MR**0213233****[2]**Hartley Rogers Jr.,*Theory of recursive functions and effective computability*, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1967. MR**0224462****[3]**Gerald E. Sacks,*Degrees of unsolvability*, Princeton University Press, Princeton, N.J., 1963. MR**0186554****[4]**Gerald E. Sacks,*Higher recursion theory*, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1990. MR**1080970****[5]**Gerald E. Sacks,*Post’s problem, admissible ordinals, and regularity*, Trans. Amer. Math. Soc.**124**(1966), 1–23. MR**0201299**, 10.1090/S0002-9947-1966-0201299-1**[6]**G. E. Sacks and S. G. Simpson,*The 𝛼-finite injury method*, Ann. Math. Logic**4**(1972), 343–367. MR**0369041****[7]**Joseph R. Shoenfield,*Degrees of unsolvability*, North-Holland Publishing Co., Amsterdam-London; American Elsevier Publishing Co., Inc., New York, 1971. Dedicated to S. C. Kleene; North-Holland Mathematics Studies, No. 2. MR**0340011****[8]**Richard A. Shore,*∑_{𝑛} sets which are Δ_{𝑛}-incomparable (uniformly)*, J. Symbolic Logic**39**(1974), 295–304. MR**0419197****[9]**-,*The irregular and non-hyperregular -r.e. degrees*(to appear).**[10]**-,*The recursively enumerable -degrees are dense*, Ann. Math. Logic (to appear).

Retrieve articles in *Transactions of the American Mathematical Society*
with MSC:
02F27

Retrieve articles in all journals with MSC: 02F27

Additional Information

DOI:
https://doi.org/10.1090/S0002-9947-1975-0379154-1

Keywords:
-recursion theory,
admissible ordinals,
-recursively enumerable,
priority argument,
splitting theorem,
-degrees,
-calculability degrees

Article copyright:
© Copyright 1975
American Mathematical Society