Article ID Journal Published Year Pages File Type
4950585 Information and Computation 2017 11 Pages PDF
Abstract
We look at the question of join preservation for bounded Turing reducibilities r and r′ such that r is stronger than r′. We say that join preservation holds for two reducibilities r and r′ if every join in the computably enumerable (c.e.) r-degrees is also a join in the c.e. r′-degrees. We consider the class of monotone admissible (uniformly) bounded Turing reducibilities, i.e. the reflexive and transitive Turing reducibilities with use bounded by a function that is contained in a (uniformly computable) family of strictly increasing computable functions. This class contains for example identity bounded Turing (ibT-) and computable Lipschitz (cl-) reducibility. Our main result is that join preservation fails for cl and any strictly weaker monotone admissible uniformly bounded Turing reducibility (Theorem 10). We also look at the dual question of meet preservation and show that for all monotone admissible bounded Turing reducibilities r and r′ such that r is stronger than r′, meet preservation holds. Finally, we completely solve the question of join and meet preservation in the classical reducibilities 1, m, tt, wtt, and T. This is an extended version of our article [18].
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
,