Decidability and invariant classes for degree structures

Authors:
Manuel Lerman and Richard A. Shore

Journal:
Trans. Amer. Math. Soc. **310** (1988), 669-692

MSC:
Primary 03D25; Secondary 03B25, 03D30, 03D55

DOI:
https://doi.org/10.1090/S0002-9947-1988-0973174-0

MathSciNet review:
973174

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We present a decision procedure for the -theory of , the Turing degrees below . The two main ingredients are a new extension of embeddings result and a strengthening of the initial segments results below of [Le1]. First, given any finite subuppersemilattice of with top element and an isomorphism type of a poset extending consistently with its structure as an usl such that and have the same top element and is an end extension of , we construct an extension of inside isomorphic to . Second, we obtain an initial segment of which is isomorphic to such that is a subusl of . The decision procedure follows easily from these results.

As a corollary to the -decision procedure for , we show that no degree is definable by any -formula of degree theory. As a start on restricting the formulas which could possibly define the various jump classes we classify the generalized jump classes which are invariant for any or -formula. The analysis again uses the decision procedure for the -theory of . A similar analysis is carried out for the high/low hierarchy using the decision procedure for the -theory of . (A jump class is -*invariant* if holds for every in .)

**[E]**R. L. Epstein,*Initial segments of degrees below*, Mem. Amer. Math. Soc. No. 241 (1981). MR**603392 (82m:03055)****[J1]**C. G. Jockusch, Jr.,*Degrees of generic sets*, Recursion Theory: Its Generalisations and Applications (F. Drake and S. Wainer, Eds.), London Math. Soc. Lecture Notes Series, no. 45, Cambridge Univ. Press, Cambridge, 1980, pp. 110-139. MR**598304 (83i:03070)****[J2]**-,*Simple proofs of some theorems on high degrees of unsolvability*, Canad. J. Math.**29**(1970). 1072-1080. MR**0476460 (57:16023)****[JP]**C. G. Jockusch, Jr. and D. Posner,*Double jumps of minimal degrees*, J. Symbolic Logic**43**(1978), 715-724. MR**518677 (80d:03042)****[KP]**S. C. Kleene and E. L. Post,*The uppersemilattice of degrees of recursive unsolvability*, Ann. of Math. (2)**59**(1954), 379-407. MR**0061078 (15:772a)****[La]**A. H. Lachlan,*Distributive initial segments of the degrees of unsolvability*, Z. Math. Logik Grundlag. Math.**14**(1968), 457-472. MR**0237331 (38:5620)****[Le1]**M. Lerman,*Degrees of unsolvability*, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, Heidelberg, New York, Tokyo, 1983, 307 pages. MR**708718 (85h:03044)****[Le2]**-,*On the ordering of classes in high/low hierarchies*, Recursion Theory Week (H. D. Ebbinghaus, G. H. Müller, and G. E. Sacks, Eds.), Lecture Notes in Math., vol. 1145, Springer-Verlag, Berlin, Heidelberg, 1985, pp. 260-270. MR**820785 (87i:03085)****[Le3]**-,*Initial segments of the degrees of unsolvability*, Ann. of Math. (2)**93**(1971), 365-389. MR**0307893 (46:7008)****[Le4]**-,*Degrees which do not bound minimal degrees*, Ann. Pure Appl. Logic**30**(1986), 249-276. MR**836427 (87g:03046)****[PR]**D. Posner and R. W. Robinson,*Degrees joining to*, J. Symbolic Logic**46**(1981), 714-722. MR**641485 (83c:03040)****[R]**R. W. Robinson,*Jump restricted interpolation in the r.e. degrees*, Ann. of Math. (2)**93**(1971), 586-596. MR**0313037 (47:1592)****[Sa]**L. P. Sasso, Jr.,*A minimal degree not realizing least possible jump*, J. Symbolic Logic**39**(1974), 571-574. MR**0360242 (50:12692)****[Sh1]**R. A. Shore,*On the*-*sentences of*-*recursion theory*, Generalized Recursion Theory. II (J. Fenstad, R. Gandy, and G. Sacks, Eds.), Stud. Logic Foundations Math., no. 94, North-Holland, Amsterdam, 1978, pp. 331-354. MR**516943 (80e:03055)****[Sh2]**-,*The theory of the degrees below*, J. London Math. Soc. (2)**24**(1981), 1-14. MR**623666 (83m:03051)****[Sh3]**-,*Defining jump classes in the degrees below*, Proc. Amer. Math. Soc.**104**(1988), 287-292. MR**958085 (89i:03084)****[Sl]**T. Slaman,*An r.e. degree which is not the top of a diamond*, in preparation.**[So]**R. I. Soare,*Recurisvely enumerable sets and degrees*, Springer-Verlag, Berlin, 1987. MR**882921 (88m:03003)****[Y]**C. E. M. Yates,*Initial segments of the degrees of unsolvability. Part*II:*Minimal degrees*, J. Symbolic Logic**35**(1970), 243-266. MR**0274288 (43:53)**

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

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

Additional Information

DOI:
https://doi.org/10.1090/S0002-9947-1988-0973174-0

Keywords:
Degrees below ,
extension of embeddings,
initial segments,
-theory,
invariant jump classes,
definability

Article copyright:
© Copyright 1988
American Mathematical Society