A uniform version of non-low(2)-ness

作者：Fan, Yun^*

来源：Annals of Pure and Applied Logic, 2017, 168(3): 738-748.

DOI：10.1016/j.apal.2016.10.013

• (Uniformly) non-lowz
• Computable Lipschitz reducibility
• Common upper bound

We introduce a property of Turing degrees: being uniformly non-low(2). We prove that, in the c.e. Turing degrees, there is an incomplete uniformly non-low(2) degree, and not every non-low(2) degree is uniformly non-low(2). We also build some connection between (uniform) non-low(2)-ness and computable Lipschitz reducibility (<=(cl)), as a strengthening of weak truth table reducibility:
(1) If a c.e. Turing degree d is uniformly non-low(2), then for any non -computable Delta(0)(2) 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-low(2) in d which is not cl-reducible to it.

• 出版日期2017-3
• 单位东南大学