Where join preservation fails in the bounded Turing degrees of c.e. sets (Q2407100)

The main objective of this paper is to study \(r-r'\) join preservation in the c.e. degrees, where \(r\) and \(r'\) are two bounded Turing reducibilities. A reducibility \(r\) is a bounded Turing reducibility (bT-reducibility) if there is a family \(\mathcal F\) of computable functions such that given any two sets \(A\) and \(B\) of natural numbers, \(A\) is \(r\)-reducible to \(B\) if and only if \(A\) is Turing reducible to \(B\) via an oracle Turing machine whose use function is bounded by some function in \(\mathcal F\). Moreover, if \(\mathcal F\) is uniformly computable then \(r\) is called a uniformly bounded Turing reducibility (ubT-reducibility). If \(r\) is a (u)bT-reducibility and \(\mathcal F\) contains only strictly increasing functions, then \(r\) is called a monotone (u)bT-reducibility. A Turing reducibility \(r\) is strictly stronger than \(r'\) if \(r\) is strictly contained in \(r'\). Given two reducibilities \(r\) and \(r'\), \(r-r'\) join preservation holds (in the c.e. degrees) if for any three noncomputable c.e. sets of naturals numbers \(A\), \(B\) and \(C\), if the \(r\)-degree of \(C\) is the least upper bound of the \(r\)-degrees of \(A\) and \(B\), then the \(r'\)-degree of \(C\) is the least upper bound of the \(r'\)-degrees of \(A\) and \(B\). Similarly, \(r-r'\) meet preservation holds if the same condition above is true with greater lower bound in place of least upper bound. In the paper under review, the author observes that for classical reducibilities the join preservation holds, namely: given \(r,r'\in\{1,m,tt,wtt,T\}\) with \(r\) stronger than \(r'\), then \(r-r'\) join preservation holds, whereas \(r-r'\) meet preservation only holds in the case \(r=1\) and \(r'=m\). The main results of the paper concern ubT-reducibilities. She observes first that in some cases \(r-r'\) join preservation holds, namely: Let \(r\) and \(r'\) be two ubT-reducibilities such that \(r\) contains ibT, is strictly stronger than \(r'\) and \(r\) or \(r'\) is monotone. Then, \(r-r'\) join preservation holds if and only if \(r'\) is monotone. On the contrary, in the following cases join preservation fails: let \(r'\) be a monotone ubT-reducibility such that \(cl\) is strictly stronger than \(r'\); then, for \(r\in\{\mathrm{ibT},\mathrm{cl}\}\), \(r-r'\) join preservation fails. ibT is the identity bounded Turing reducibility, that is the ubT-reducibility induced by \({\mathcal F}_{\mathrm{ibT}}=\{\mathrm{id}\}\), and cl is the computable Lipschitz reducibility, that is the ubT-reducibility induced by \({\mathcal F}_{\mathrm{cl}}=\{\mathrm{id}+e:e\geq 0\}\). For what concerns meet preservation, it has been shown that \(r-r'\) meet preservation holds for bT-reducibilities \(r\) and \(r'\) with \(r\) stronger than \(r'\) and \(r'\) monotone. The final part of the paper contains a section dedicated to some interesting open problems.