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)

 
 

 

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 $ \forall \exists $-theory of $ \mathcal{D}[{\mathbf{0}},\,{\mathbf{0}}' ]$, the Turing degrees below $ {\mathbf{0}}' $. The two main ingredients are a new extension of embeddings result and a strengthening of the initial segments results below $ {\mathbf{0}}' $ of [Le1]. First, given any finite subuppersemilattice $ U$ of $ \mathcal{D}[{\mathbf{0}},\,{\mathbf{0}}' ]$ with top element $ {\mathbf{0}}' $ and an isomorphism type $ V$ of a poset extending $ U$ consistently with its structure as an usl such that $ V$ and $ U$ have the same top element and $ V$ is an end extension of $ U - \{ {\mathbf{0}}' \} $, we construct an extension of $ U$ inside $ \mathcal{D}[{\mathbf{0}},\,{\mathbf{0}}' ]$ isomorphic to $ V$. Second, we obtain an initial segment $ W$ of $ \mathcal{D}[{\mathbf{0}},\,{\mathbf{0}}' ]$ which is isomorphic to $ U - \{ {\mathbf{0}}' \} $ such that $ W \cup \{ {\mathbf{0}}' \} $ is a subusl of $ \mathcal{D}$. The decision procedure follows easily from these results.

As a corollary to the $ \forall \exists $-decision procedure for $ \mathcal{D}$, we show that no degree $ {\mathbf{a}} > {\mathbf{0}}$ is definable by any $ \exists \forall $-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 $ \forall $ or $ \exists $-formula. The analysis again uses the decision procedure for the $ \forall \exists $-theory of $ \mathcal{D}$. A similar analysis is carried out for the high/low hierarchy using the decision procedure for the $ \forall \exists $-theory of $ \mathcal{D}[{\mathbf{0}},\,{\mathbf{0}}' ]$. (A jump class $ \mathcal{C}$ is $ \sigma $-invariant if $ \sigma ({\mathbf{a}})$ holds for every $ {\mathbf{a}}$ in $ \mathcal{C}$.)


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

  • [E] R. L. Epstein, Initial segments of degrees below $ {\mathbf{0}}' $, 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 $ {\mathbf{0}}' $, 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 $ \forall \exists $-sentences of $ \alpha $-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 $ {\mathbf{0}}' $, J. London Math. Soc. (2) 24 (1981), 1-14. MR 623666 (83m:03051)
  • [Sh3] -, Defining jump classes in the degrees below $ {\mathbf{0}}' $, 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)

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: https://doi.org/10.1090/S0002-9947-1988-0973174-0
Keywords: Degrees below $ {\mathbf{0}}' $, extension of embeddings, initial segments, $ \forall \exists $-theory, invariant jump classes, definability
Article copyright: © Copyright 1988 American Mathematical Society

American Mathematical Society