The partial orderings of the computably enumerable ibT-degrees and cl-degrees are not elementarily equivalent (Q1944337)

In this article the authors complete the proof that the two partial orderings \(({\mathbf R}_{\text{ibT}},\leq)\) and \(({\mathbf R}_{\text{cl}},\leq)\) do not share the same first-order properties. \({\mathbf R}_{\text{ibT}}\) is the class of all the c.e. identity-bounded Turing degrees, and \({\mathbf R}_{\text{cl}}\) is the class of all the c.e. computable Lipschitz degrees. The first part of the paper contains the main result: (1) There is a c.e. cl-degree \({\mathbf a}>{\mathbf 0}\) such that the class of \({\mathbf a}\)-noncuppable c.e. cl-degrees is not bounded by any c.e. cl-degree strictly below \({\mathbf a}\). The first-order property (1) is not true in \(({\mathbf R}_{\text{ibT}},\leq)\), due to a result shown in [\textit{K. Ambos-Spies}, ``On the strongly bounded Turing degrees of the computably enumerable sets'' (to appear)]. Exactly, Ambos-Spies showed the following: (2) For any c.e. ibT-degree \({\mathbf a}>{\mathbf 0}\), \({\mathbf {NCu}}({\mathbf a})\subseteq\{{\mathbf b}\in{\mathbf R}_{\text{ibT}}:{\mathbf b}\leq{\mathbf a}+1\}\). In (2) \({\mathbf {NCu}}({\mathbf a})\) denotes the class of \({\mathbf a}\)-noncuppable c.e ibT-degrees, while \({\mathbf a}+1\) denotes the ibT-degree determined by \({\mathbf a}\) and the constant shift function 1; moreover, the ibT-degree \({\mathbf a}+1\) is strictly below \({\mathbf a}\) [loc. cit.; \textit{K. Ambos-Spies} et al., Theory Comput. Syst. 52, No. 1, 2--27 (2013; Zbl 1273.03140)]. The paper under review also contains a short proof of (2). In the second part of the article it is shown that the converse of (2) is not true. Actually, a more general result is shown which extends to every computable shift function, namely: (3) Given any computable shift function \(f\), there is a c.e. ibT-degree \({\mathbf a}>{\mathbf 0}\) such that the \(f\)-shift ibT-degree \({\mathbf a}_f\) of \({\mathbf a}\) cups to \({\mathbf a}\). A result similar to (3) is also shown for the c.e. cl-degrees. The paper ends with a section dedicated to some interesting open questions.