Аннотация:
Изучаются такие пары (T1,T0) классов неубывающих тотальных одноместных арифметических функций, которые определяют рефлексивные и транзитивные бинарные отношения {(A,B)∣A,B⊆N&(∃ о.р.ф. h) (∃f1∈T0)[A⩽hmB&f0⊴h⊴f1]}. (Здесь k⊴l означает, что функция l почти всюду
мажорирует функцию k.) Установлены критерии рефлексивности и транзитивности таких отношений. Получены свидетельства высокой разветвленности возникающей системы
ограниченных сводимостей m-типа. Построены примеры таких сводимостей, существенно отличающиеся от стандартной m-сводимости в отношении структуры порождаемых ими
систем степеней неразрешимости и в вопросе полноты множеств.
Библиография: 4 названия.
Образец цитирования:
В. Н. Беляев, В. К. Булитко, “m-сводимость с верхними и нижними границами для сводящих функций”, Матем. заметки, 70:1 (2001), 12–21; Math. Notes, 70:1 (2001), 11–19