首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Generics for computable Mathias forcing
Authors:Peter A Cholak  Damir D Dzhafarov  Jeffry L Hirst  Theodore A Slaman
Institution:1. Department of Mathematics, University of Notre Dame, 255 Hurley Building, Notre Dame, IN 46556, USA;2. Department of Mathematics, University of Connecticut, 196 Auditorium Road, Storrs, CT 06269, USA;3. Department of Mathematical Sciences, Appalachian State University, 342 Walker Hall, Boone, NC 28608, USA;4. Department of Mathematics, University of California, Berkeley, 970 Evans Hall, Berkeley, CA 94720, USA
Abstract:We study the complexity of generic reals for computable Mathias forcing in the context of computability theory. The n-generics and weak n-generics form a strict hierarchy under Turing reducibility, as in the case of Cohen forcing. We analyze the complexity of the Mathias forcing relation, and show that if G is any n  -generic with n≥2n2 then it satisfies the jump property G(n−1)TG⊕∅(n)G(n1)TG(n). We prove that every such G has generalized high Turing degree, and so cannot have even Cohen 1-generic degree. On the other hand, we show that every Mathias n-generic real computes a Cohen n-generic real.
Keywords:03D80  03E40  03D32  03E75
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号