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)



Branching degrees above low degrees

Author: Peter A. Fejer
Journal: Trans. Amer. Math. Soc. 273 (1982), 157-180
MSC: Primary 03D25; Secondary 03D30
MathSciNet review: 664035
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: In this paper, we investigate the location of the branching degrees within the recursively enumerable (r.e.) degrees. We show that there is a branching degree below any given nonzero r.e. degree and, using a new branching degree construction and a technique of Robinson, that there is a branching degree above any given low r.e. degree. Our results extend work of Shoenfield and Soare and Lachlan on the generalized nondiamond question and show that the branching degrees form an automorphism base for the r.e. degrees.

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

  • [1] P. A. Fejer, The density of the nonbranching degrees, Ann. Math. Logic (to appear). MR 713296 (85g:03062)
  • [2] A. H. Lachlan, Lower bounds for pairs of r.e. degrees, Proc. London Math. Soc. (3) 16 (1966), 537-569. MR 0204282 (34:4126)
  • [3] -, A recursively enumerable degree which will not split over all lesser ones, Ann. Math. Logic 9 (1975), 307-365. MR 0409150 (53:12912)
  • [4] -, Decomposition of recursively enumerable degrees, Proc. Amer. Math. Soc. 79 (1980), 629-634. MR 572317 (81i:03065)
  • [5] R. W. Robinson, Interpolation and embedding in the recursively enumerable degrees, Ann. of Math. (2) 93 (1971), 285-314. MR 0274286 (43:51)
  • [6] G. E. Sacks, Degrees of unsolvability, rev. ed., Ann. of Math. Studies, no. 55, Princeton Univ. Press, Princeton, N. J., 1966. MR 0186554 (32:4013)
  • [7] J. R. Shoenfield, Application of model theory to degrees of unsolvability, Sympos. Theory of Models, North-Holland, Amsterdam, 1965, pp. 359-363. MR 0200154 (34:53)
  • [8] -, Degrees of unsolvability, North-Holland, Amsterdam, 1971.
  • [9] J. R. Shoenfield and R. I. Soare, The generalized diamond theorem. Recursive Function Theory Newsletter (1978), No. 19, Abstract 219.
  • [10] R. I. Soare, The infinite injury priority method, J. Symbolic Logic 41 (1976), 513-530. MR 0429521 (55:2534)
  • [11] -, Computational complexity, speedable and levelable sets, J. Symbolic Logic 42 (1977), 545-563. MR 0485278 (58:5125)
  • [12] -, Fundamental methods for constructing recursively enumerable degrees, Recursion Theory: Its Generalizations and Applications, Proc. Logic Colloq. 1979, Leeds, August, 1979, London Math. Soc. Lecture Note Series 45, Cambridge Univ. Press, Cambridge, 1981. MR 598302 (82j:03051)
  • [13] S. K. Thomason, Sublattices of the recursively enumerable degrees, Z. Math. Logik Gundlag. Math. 17 (1971), 273-280. MR 0299475 (45:8523)
  • [14] C. E. M. Yates, A minimal pair of r.e. degrees, J. Symbolic Logic 31 (1966), 159-168. MR 0205851 (34:5677)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 03D25, 03D30

Retrieve articles in all journals with MSC: 03D25, 03D30

Additional Information

Keywords: Recursively enumerable degree, branching degree, low degree, generalized nondiamond question, automorphism base
Article copyright: © Copyright 1982 American Mathematical Society

American Mathematical Society