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)

 
 

 

Splitting an $ \alpha $-recursively enumerable set


Author: Richard A. Shore
Journal: Trans. Amer. Math. Soc. 204 (1975), 65-77
MSC: Primary 02F27
DOI: https://doi.org/10.1090/S0002-9947-1975-0379154-1
MathSciNet review: 0379154
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We extend the priority method in $ \alpha $-recursion theory to certain arguments with no a priori bound on the required preservations by proving the splitting theorem for all admissible $ \alpha $. THEOREM: Let $ C$ be a regular $ \alpha $-r.e. set and $ D$ be a nonrecursive $ \alpha $-r.e. set. Then there are regular $ \alpha $-r.e. sets $ A$ and $ B$ such that $ A \cup B = C,A \cap B = \phi ,A,B{ \leq _\alpha }C$ and such that $ D$ is not $ \alpha $-recursive in $ A$ or $ B$. The result is also strengthened to apply to $ { \leq _{c\alpha }}$, and various corollaries about the structure of the $ \alpha $ and $ c\alpha $ recursively enumerable degrees are proved.


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

  • 1. L. Harrington, Contributions to recursion theory on higher types, Ph. D. Thesis, M. I. T., Cambridge, Mass., 1973.
  • [1] G. Kreisel and G. E. Sacks, Metarecursive sets, J. Symbolic Logic 30 (1965), 318-338. MR 35 #4097. MR 0213233 (35:4097)
  • [2] H. Rogers, Jr., Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967. MR 37 #61. MR 0224462 (37:61)
  • [3] G. E.. Sacks, Degrees of unsolvability, Ann. of Math. Studies, no. 55, Princton Univ. Press, Princeton, N. J., 1963. MR 32 #4013. MR 0186554 (32:4013)
  • [4] -, Higher recursion theory, Springer-Verlag (to appear). MR 1080970 (92a:03062)
  • [5] -, Post's problem, admissible ordinals and regularity, Trans. Amer. Math. Soc. 124 (1966), 1-23. MR 34 #1183. MR 0201299 (34:1183)
  • [6] G. E. Sacks and S. G. Simpson, The $ \alpha $-finite injury method, Ann. Math. Logic 4 (1972), 343-368. MR 0369041 (51:5277)
  • [7] J. R. Shoenfield, Degrees of unsolvability, North-Holland, Amsterdam, 1971. MR 0340011 (49:4768)
  • [8] R. A. Shore, $ {\Sigma _n}$ sets which are $ {\Delta _n}$ incomparable (uniformly), J. Symbolic Logic 39 (1974), 295-304. MR 0419197 (54:7229)
  • [9] -, The irregular and non-hyperregular $ \alpha $-r.e. degrees (to appear).
  • [10] -, The recursively enumerable $ \alpha $-degrees are dense, Ann. Math. Logic (to appear).

Similar Articles

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: $ \alpha $-recursion theory, admissible ordinals, $ \alpha $-recursively enumerable, priority argument, splitting theorem, $ \alpha $-degrees, $ \alpha $-calculability degrees
Article copyright: © Copyright 1975 American Mathematical Society

American Mathematical Society