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


Branching in the {\Sigma^0_2} -enumeration degrees: a new perspective
Authors:Maria L Affatato  Thomas F Kent  Andrea Sorbi
Institution:(1) Dipartimento di Scienze Matematiche ed Informatiche “Roberto Magari”, Università di Siena, Pian dei Mantellini 44, 53100 Siena, Italy
Abstract:We give an alternative and more informative proof that every incomplete $${\Sigma^{0}_{2}}$$ -enumeration degree is the meet of two incomparable $${\Sigma^{0}_{2}}$$ -degrees, which allows us to show the stronger result that for every incomplete $${\Sigma^{0}_{2}}$$ -enumeration degree a, there exist enumeration degrees x 1 and x 2 such that a, x 1, x 2 are incomparable, and for all b  ≤  a, b  =  (bx 1 ) ∧ (bx 2 ). The first author would like to thank her advisor, Andrea Sorbi, whose guidance made this paper possible. The second author has been supported by a Marie Curie Incoming International Fellowship of the European Community FP6 Program under contract number MIFI-CT-2006-021702.
Keywords:Enumeration reducibility  Semirecursive set  Branching element
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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