RUS  ENG
Full version
JOURNALS // Algebra and Discrete Mathematics // Archive

Algebra Discrete Math., 2005 Issue 2, Pages 1–19 (Mi adm299)

RESEARCH ARTICLE

On bounded $m$-reducibilities

Vladimir N. Belyaev

Department of Computer Algebra and Discrete Mathematics, Odessa National University, Dvoranskaja st. 2, Odessa, Ukraine, 65026

Abstract: Conditions for classes ${\mathfrak F}^1,{\mathfrak F}^0$ of non-decreasing total one-place arithmetic functions to define reducibility
$\leq_m[^{{\mathfrak R}^1}_{{\mathfrak R}^0}]\leftrightharpoons\{(A,B)|A,B\subseteq\mathbb N\ \&\ (\exists r.f. \ h) (\exists f_1\in{\mathfrak F}^1)(\exists f_0\in{\mathfrak F}^0) $ $[A\le_m^h\,B\ \&\ f_0\unlhd h\unlhd f_1]\}$ where $k\unlhd l$ means that function $l$ majors function $k$ almost everywhere are studied. It is proved that the system of these reducibilities is highly ramified, and examples are constructed which differ drastically $\leq_m[^{{\mathfrak R}^1}_{{\mathfrak R}^0}]$ from the standard $m$-reducibility with respect to systems of degrees. Indecomposable and recursive degrees are considered.

Keywords: bounded reducibilities, degrees of unsolvability, singular reducibility, cylinder, indecomposable degree.

MSC: 03D20, 03D25, 03D30

Received: 11.04.2005
Revised: 04.07.2005

Language: English



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024