Decidability and invariant classes for degree structures
Authors:
Manuel Lerman and Richard A. Shore
Journal:
Trans. Amer. Math. Soc. 310 (1988), 669692
MSC:
Primary 03D25; Secondary 03B25, 03D30, 03D55
MathSciNet review:
973174
Fulltext 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
(82m:03055), http://dx.doi.org/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, CambridgeNew York, 1980, pp. 110–139. MR 598304
(83i:03070)
 [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
(57 #16023)
 [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
(80d:03042), http://dx.doi.org/10.2307/2273510
 [KP]
S.
C. Kleene and Emil
L. Post, The upper semilattice 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 Grundlagen Math. 14
(1968), 457–472. MR 0237331
(38 #5620)
 [Le1]
Manuel
Lerman, Degrees of unsolvability, Perspectives in Mathematical
Logic, SpringerVerlag, Berlin, 1983. Local and global theory. MR 708718
(85h:03044)
 [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
(87i:03085), http://dx.doi.org/10.1007/BFb0076225
 [Le3]
Manuel
Lerman, Initial segments of the degrees of unsolvability, Ann.
of Math. (2) 93 (1971), 365–389. MR 0307893
(46 #7008)
 [Le4]
Manuel
Lerman, Degrees which do not bound minimal degrees, Ann. Pure
Appl. Logic 30 (1986), no. 3, 249–276. MR 836427
(87g:03046), http://dx.doi.org/10.1016/01680072(86)900229
 [PR]
David
B. Posner and Robert
W. Robinson, Degrees joining to 0′, J. Symbolic Logic
46 (1981), no. 4, 714–722. MR 641485
(83c:03040), http://dx.doi.org/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
(47 #1592)
 [Sa]
Leonard
P. Sasso Jr., A minimal degree not realizing least possible
jump, J. Symbolic Logic 39 (1974), 571–574. MR 0360242
(50 #12692)
 [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,
NorthHolland, AmsterdamNew York, 1978, pp. 331–353. MR 516943
(80e:03055)
 [Sh2]
Richard
A. Shore, The theory of the degrees below 0′, J. London
Math. Soc. (2) 24 (1981), no. 1, 1–14. MR 623666
(83m:03051), http://dx.doi.org/10.1112/jlms/s224.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 (89i:03084), http://dx.doi.org/10.1090/S00029939198809580854
 [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, SpringerVerlag, Berlin, 1987. A study
of computable functions and computably generated sets. MR 882921
(88m:03003)
 [Y]
C.
E. M. Yates, Initial segments of the degrees of unsolvability. II.
Minimal degrees., J. Symbolic Logic 35 (1970),
243–266. MR 0274288
(43 #53)
 [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. 110139. MR 598304 (83i:03070)
 [J2]
 , Simple proofs of some theorems on high degrees of unsolvability, Canad. J. Math. 29 (1970). 10721080. MR 0476460 (57:16023)
 [JP]
 C. G. Jockusch, Jr. and D. Posner, Double jumps of minimal degrees, J. Symbolic Logic 43 (1978), 715724. 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), 379407. MR 0061078 (15:772a)
 [La]
 A. H. Lachlan, Distributive initial segments of the degrees of unsolvability, Z. Math. Logik Grundlag. Math. 14 (1968), 457472. MR 0237331 (38:5620)
 [Le1]
 M. Lerman, Degrees of unsolvability, Perspectives in Mathematical Logic, SpringerVerlag, 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, SpringerVerlag, Berlin, Heidelberg, 1985, pp. 260270. MR 820785 (87i:03085)
 [Le3]
 , Initial segments of the degrees of unsolvability, Ann. of Math. (2) 93 (1971), 365389. MR 0307893 (46:7008)
 [Le4]
 , Degrees which do not bound minimal degrees, Ann. Pure Appl. Logic 30 (1986), 249276. MR 836427 (87g:03046)
 [PR]
 D. Posner and R. W. Robinson, Degrees joining to , J. Symbolic Logic 46 (1981), 714722. MR 641485 (83c:03040)
 [R]
 R. W. Robinson, Jump restricted interpolation in the r.e. degrees, Ann. of Math. (2) 93 (1971), 586596. MR 0313037 (47:1592)
 [Sa]
 L. P. Sasso, Jr., A minimal degree not realizing least possible jump, J. Symbolic Logic 39 (1974), 571574. 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, NorthHolland, Amsterdam, 1978, pp. 331354. MR 516943 (80e:03055)
 [Sh2]
 , The theory of the degrees below , J. London Math. Soc. (2) 24 (1981), 114. MR 623666 (83m:03051)
 [Sh3]
 , Defining jump classes in the degrees below , Proc. Amer. Math. Soc. 104 (1988), 287292. 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, SpringerVerlag, 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), 243266. MR 0274288 (43:53)
Similar Articles
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:
http://dx.doi.org/10.1090/S00029947198809731740
PII:
S 00029947(1988)09731740
Keywords:
Degrees below ,
extension of embeddings,
initial segments,
theory,
invariant jump classes,
definability
Article copyright:
© Copyright 1988
American Mathematical Society
