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

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]**Richard L. Epstein,*Initial segments of degrees below 0′*, Mem. Amer. Math. Soc.**30**(1981), no. 241, vi+102. MR**603392**, 10.1090/memo/0241**[J1]**Carl G. Jockusch Jr.,*Degrees of generic sets*, 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. 110–139. MR**598304****[J2]**Carl G. Jockusch Jr.,*Simple proofs of some theorems on high degrees of unsolvability*, Canad. J. Math.**29**(1977), no. 5, 1072–1080. MR**0476460****[JP]**Carl G. Jockusch Jr. and David B. Posner,*Double jumps of minimal degrees*, J. Symbolic Logic**43**(1978), no. 4, 715–724. MR**518677**, 10.2307/2273510**[KP]**S. C. Kleene and Emil L. Post,*The upper semi-lattice of degrees of recursive unsolvability*, Ann. of Math. (2)**59**(1954), 379–407. MR**0061078****[La]**A. H. Lachlan,*Distributive initial segments of the degrees of unsolvability*, Z. Math. Logik Grundlagen Math.**14**(1968), 457–472. MR**0237331****[Le1]**Manuel Lerman,*Degrees of unsolvability*, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1983. Local and global theory. MR**708718****[Le2]**Manuel Lerman,*On the ordering of classes in high/low hierarchies*, Recursion theory week (Oberwolfach, 1984) Lecture Notes in Math., vol. 1141, Springer, Berlin, 1985, pp. 260–270. MR**820785**, 10.1007/BFb0076225**[Le3]**Manuel Lerman,*Initial segments of the degrees of unsolvability*, Ann. of Math. (2)**93**(1971), 365–389. MR**0307893****[Le4]**Manuel Lerman,*Degrees which do not bound minimal degrees*, Ann. Pure Appl. Logic**30**(1986), no. 3, 249–276. MR**836427**, 10.1016/0168-0072(86)90022-9**[PR]**David B. Posner and Robert W. Robinson,*Degrees joining to 0′*, J. Symbolic Logic**46**(1981), no. 4, 714–722. MR**641485**, 10.2307/2273221**[R]**Robert W. Robinson,*Jump restricted interpolation in the recursively enumerable degrees*, Ann. of Math. (2)**93**(1971), 586–596. MR**0313037****[Sa]**Leonard P. Sasso Jr.,*A minimal degree not realizing least possible jump*, J. Symbolic Logic**39**(1974), 571–574. MR**0360242****[Sh1]**Richard A. Shore,*On the ∀∃-sentences of 𝛼-recursion theory*, Generalized recursion theory, II (Proc. Second Sympos., Univ. Oslo, Oslo, 1977) Stud. Logic Foundations Math., vol. 94, North-Holland, Amsterdam-New York, 1978, pp. 331–353. MR**516943****[Sh2]**Richard A. Shore,*The theory of the degrees below 0′*, J. London Math. Soc. (2)**24**(1981), no. 1, 1–14. MR**623666**, 10.1112/jlms/s2-24.1.1**[Sh3]**Richard A. Shore,*Defining jump classes in the degrees below 0’*, Proc. Amer. Math. Soc.**104**(1988), no. 1, 287–292. MR**958085**, 10.1090/S0002-9939-1988-0958085-4**[Sl]**T. Slaman,*An r.e. degree which is not the top of a diamond*, in preparation.**[So]**Robert I. Soare,*Recursively enumerable sets and degrees*, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1987. A study of computable functions and computably generated sets. MR**882921****[Y]**C. E. M. Yates,*Initial segments of the degrees of unsolvability. II. Minimal degrees.*, J. Symbolic Logic**35**(1970), 243–266. MR**0274288**

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