A uniform version of non-low₂-ness

详细信息    查看全文

• 作者：Yun Fan¹ ; ^{fanyun@seu.edu.cn}
• 关键词：03D25 ; 03D30
• 刊名：Annals of Pure and Applied Logic
• 出版年：2017
• 出版时间：March 2017
• 年：2017
• 卷：168
• 期：3
• 页码：738-748
• 全文大小：356 K
• 卷排序：168

文摘

We introduce a property of Turing degrees: being uniformly non-low2low2. We prove that, in the c.e. Turing degrees, there is an incomplete uniformly non-low2low2 degree, and not every non-low2low2 degree is uniformly non-low2low2. We also build some connection between (uniform) non-low2low2-ness and computable Lipschitz reducibility (≤cl≤cl), as a strengthening of weak truth table reducibility:(1) If a c.e. Turing degree d is uniformly non-low2low2, then for any non-computable Δ20 real there is a c.e. real in d such that both of them have no common upper bound in c.e. reals under cl-reducibility.(2) A c.e. Turing degree d is non-low2low2 if and only if for any Δ20 real there is a real in d which is not cl-reducible to it.