Branching degrees above low degrees

Fejer, Peter A.

doi:10.1090/S0002-9947-1982-0664035-X

Branching degrees above low degrees
HTML articles powered by AMS MathViewer

by Peter A. Fejer PDF

Trans. Amer. Math. Soc. 273 (1982), 157-180 Request permission

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

Peter A. Fejer, The density of the nonbranching degrees, Ann. Pure Appl. Logic 24 (1983), no. 2, 113–130. MR 713296, DOI 10.1016/0168-0072(83)90028-3
A. H. Lachlan, Lower bounds for pairs of recursively enumerable degrees, Proc. London Math. Soc. (3) 16 (1966), 537–569. MR 204282, DOI 10.1112/plms/s3-16.1.537
Alistair H. Lachlan, A recursively enumerable degree which will not split over all lesser ones, Ann. Math. Logic 9 (1976), no. 4, 307–365. MR 409150, DOI 10.1016/0003-4843(76)90016-4
A. H. Lachlan, Decomposition of recursively enumerable degrees, Proc. Amer. Math. Soc. 79 (1980), no. 4, 629–634. MR 572317, DOI 10.1090/S0002-9939-1980-0572317-9
Robert W. Robinson, Interpolation and embedding in the recursively enumerable degrees, Ann. of Math. (2) 93 (1971), 285–314. MR 274286, DOI 10.2307/1970776
Gerald E. Sacks, Degrees of unsolvability, Princeton University Press, Princeton, N.J., 1963. MR 0186554
J. R. Shoenfield, Applications of model theory to degrees of unsolvability, Theory of Models (Proc. 1963 Internat. Sympos. Berkeley), North-Holland, Amsterdam, 1965, pp. 359–363. MR 0200154

Degrees of unsolvability

The generalized diamond theorem

Robert I. Soare, The infinite injury priority method, J. Symbolic Logic 41 (1976), no. 2, 513–530. MR 429521, DOI 10.2307/2272252
Robert I. Soare, Computational complexity, speedable and levelable sets, J. Symbolic Logic 42 (1977), no. 4, 545–563. MR 485278, DOI 10.2307/2271876
Robert I. Soare, Fundamental methods for constructing recursively enumerable degrees, Recursion theory: its generalisation and applications (Proc. Logic Colloq., Univ. Leeds, Leeds, 1979) London Math. Soc. Lecture Note Ser., vol. 45, Cambridge Univ. Press, Cambridge-New York, 1980, pp. 1–51. MR 598302
S. K. Thomason, Sublattices of the recursively enumerable degrees, Z. Math. Logik Grundlagen Math. 17 (1971), 273–280. MR 299475, DOI 10.1002/malq.19710170131
C. E. M. Yates, A minimal pair of recursively enumerable degrees, J. Symbolic Logic 31 (1966), 159–168. MR 205851, DOI 10.2307/2269807