Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 
 

 

Two theorems on truth table degrees


Author: R. G. Downey
Journal: Proc. Amer. Math. Soc. 103 (1988), 281-287
MSC: Primary 03D30; Secondary 03D25
DOI: https://doi.org/10.1090/S0002-9939-1988-0938684-6
MathSciNet review: 938684
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: In this article we solve two questions of Odifreddi on the r.e. $ {\text{tt}}$-degrees. First we construct an r.e. $ {\text{tt}}$-degree with anticupping property. In fact, we construct r.e. $ {\text{tt}}$-degrees $ {\mathbf{a}},{\mathbf{b}}$ with $ {\mathbf{0}} < {\mathbf{a}} < {\mathbf{b}}$ and such that for all (not necessarily r.e.) $ {\text{tt}}$-degrees $ {\mathbf{c}}$ if $ {\mathbf{a}} \cup {\mathbf{c}} \geq {\mathbf{b}}$ then $ {\mathbf{a}} \leq {\mathbf{c}}$. This result also has ramifications in, for example, the r.e. $ {\text{wtt}}$-degrees. Finally we solve another question of Odifreddi by constructing an r.e. $ {\text{tt}}$-degree with no greatest r.e. $ m$-degree.


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

  • [1] R. G. Downey, $ \Delta _2^0$ degrees and transfer theorems, Illinois J. Math. 31 (1987), 419-427. MR 892177 (89c:03070)
  • [2] R. G. Downey and C. G. Jockusch, $ T$-degrees, jump classes, and strong reducibilities, Trans. Amer. Math. Soc. 301 (1987), 103-136. MR 879565 (88c:03045)
  • [3] R. Friedberg, A criterion for completeness of degrees of unsolvability, J. Symbolic Logic 22 (1958), 159-160. MR 0098025 (20:4488)
  • [4] P. Fejer and R. Shore, Embeddings and extensions of embeddings in the r.e. $ tt$ and $ wtt$-degrees, Recursion Theory Week (Proceedings, Oberwolfach 1984) (Eds., H. Ebbinghaus, G. Müller and G. Sacks), Lecture Notes in Math., vol. 1141, Springer-Verlag, 1985, pp. 121-140. MR 820777 (87i:03084)
  • [5] L. Harrington, Plus cupping in the recursively enumerable degrees, handwritten notes, 1978.
  • [6] C. G. Jockusch, Relationships between reducibilities, Trans. Amer. Math. Soc. 142 (1969), 229-237. MR 0245439 (39:6747)
  • [7] G. N. Kobzev, On $ tt$-degrees of r.e. $ T$-degrees, Mat. Sb. 106 (1978), 507-514. MR 507813 (80e:03045b)
  • [8] J. Mohrherr, Density of a final segment of the truth table degrees, Pacific J. Math. 115 (1984), 409-419. MR 765197 (86a:03043)
  • [9] P. Odifreddi, Strong reducibilities, Bull. Amer. Math. Soc. (N.S.) 4 (1981), 37-85. MR 590818 (82k:03064)
  • [10] -, Classical recursion theory, (to appear).
  • [11] D. Posner, The upper semilattice of degrees $ \leq {\mathbf{0'}}$ is complemented, J. Symbolic Logic 46 (1981), 705-713. MR 641484 (84i:03084)
  • [12] H. Rogers, Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967. MR 0224462 (37:61)
  • [13] R. G. Downey, Recursively enumerable $ m$- and $ tt$-degrees II: the distribution of singular degrees, Arch. Math. Logik (to appear).

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC: 03D30, 03D25

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


Additional Information

DOI: https://doi.org/10.1090/S0002-9939-1988-0938684-6
Keywords: Global anticupping property, truth table degrees, $ m$-degrees
Article copyright: © Copyright 1988 American Mathematical Society

American Mathematical Society