$m$-Reducibility with Upper and Lower Bounds for the Reducing Functions

V. N. Belyaev ; V. K. Bulitko

Matematičeskie zametki, Tome 70 (2001) no. 1, pp. 12-21

Résumé

We study pairs $(\mathfrak T^1,\mathfrak T^0)$ of classes of nondecreasing total one-place arithmetic functions that specify reflexive and transitive binary relations $\{(A,B)\mid A,B\subseteq N\mathop{\}(\exists$ g.r.f. $h$) $(\exists f_1\in \mathfrak T^0)[A\le{}_m^hB\mathop{\}f_0\trianglelefteq h\trianglelefteq f_1]\}$. (Here $k\trianglelefteq l$ means that the function $l$ majorizes the function $k$ almost everywhere.) Criteria for reflexivity and transitivity of such relations are established. Evidence of extensive branching of the arising system of bounded $m$-reducibilities is obtained. We construct examples of such reducibilities that essentially differ from the standard $m$-reducibility in the structure of systems of undecidability degrees that they generate and in the question of completeness of sets.