Nondensity of Double Bubbles in the D.C.E. Degrees

详细信息    查看全文

• 关键词：Ershov hierarchy ; d.c.e. sets ; Lachlan sets ; exact degrees
• 刊名：Lecture Notes in Computer Science
• 出版年：2017
• 出版时间：2017
• 年：2017
• 卷：10010
• 期：1
• 页码：547-562
• 参考文献：1.Arslanov, M.M.: The lattice of the degrees below \({ 0}^{\prime }\) , Izv. Vyssh. Uchebn. Zaved. Mat. 7, 27–33 (1988). MR 968729
  2.Arslanov, M.M., Kalimullin, I.S., Lempp, S.: On Downey’s conjecture. J. Symbolic Logic 75(2), 401–441 (2010). MR 2648149
  3.Cooper, S.B.: On a theorem of C. E. M. Yates, handwritten notes
  4.Downey, R.G.: D.r.e. degrees and the nondiamond theorem. Bull. London Math. Soc. 21(1), 43–50 (1989). MR 967789
  5.Ershov, Y.L.: A certain hierarchy of sets. I. Algebra i Logika 7(1), 47–74 (1968). MR 0270911
  6.Ershov, Y.L.: A certain hierarchy of sets. II. Algebra i Logika 7(4), 15–47 (1968). MR 0270912
  7.Ershov, Y.L.: A certain hierarchy of sets. III. Algebra i Logika 9, 34–51 (1970). MR 0299478
  8.Gold, E.M.: Limiting recursion. J. Symbolic Logic 30, 28–48 (1965). MR 0239972
  9.Ishmukhametov, S.T.: On the r.e. predecessors of d.r.e. degrees. Arch. Math. Logic 38(6), 373–386 (1999). MR 1711400
  10.Lachlan, A.H.: Lower bounds for pairs of recursively enumerable degrees. Proc. London Math. Soc. 16(3), 537–569 (1966). MR 0204282
  11.Liu, J., Wu, G., Yamaleev, M.M.: Downward density of exact degrees. Lobachevskii. J. Math. 36(4), 389–398 (2015). MR 3431199
  12.Miller, D.P.: High recursively enumerable degrees, the anti-cupping property, Logic Year 1979–80: University of Connecticut, pp. 230–245 (1981)
  13.Putnam, H.W.: Trial and error predicates and the solution to a problem of Mostowski. J. Symbolic Logic 30, 49–57 (1965). MR 0195725
  14.Sacks, G.E.: On the degrees less than \(0^{\prime }\) . Ann. Math. 77(2), 211–231 (1963). MR 0146078
  15.Soare, R.I.: Recursively enumerable sets and degrees: A study of computable functions and computably generated sets. Perspectives in Mathematical Logic, Springer, Berlin (1987). MR 882921
  16.Guohua, W., Yamaleev, M.M.: Isolation: motivations and applications. Uchenye Zapiski Kazanskogo Universiteta 154, 204–217 (2012)MathSciNet
  
• 作者单位：Uri Andrews (19)
  Rutger Kuyper (19)
  Steffen Lempp (19)
  Mariya I. Soskova (20)
  Mars M. Yamaleev (21)
  
  19. Department of Mathematics, University of Wisconsin–Madison, Madison, WI, 53706, USA
  20. Faculty of Mathematics and Computer Science, Sofia University, 5 James Bourchier Blvd., 1164, Sofia, Bulgaria
  21. Lobachevsky Institute of Mathematics and Mechanics, Kazan Federal University, 18 Kremlyovskaya Street, Kazan, 420008, Russia
  
• 丛书名：Computability and Complexity
• ISBN：978-3-319-50062-1
• 卷排序：10010

文摘

In this paper, we show that the so-called “double bubbles” are not downward dense in the d.c.e. degrees. Here, a pair of d.c.e. degrees \(\mathbf{d}_1> \mathbf{d}_2 > \mathbf{0}\) forms a double bubble if all d.c.e. degrees below \(\mathbf{d}_1\) are comparable with \(\mathbf{d}_2\).