RUS  ENG
Полная версия
ЖУРНАЛЫ // Математические заметки // Архив

Матем. заметки, 2001, том 70, выпуск 1, страницы 12–21 (Mi mzm713)

Эта публикация цитируется в 1 статье

$m$-сводимость с верхними и нижними границами для сводящих функций

В. Н. Беляев, В. К. Булитко

Одесский национальный университет им. И. И. Мечникова

Аннотация: Изучаются такие пары $(\mathfrak T^1,\mathfrak T^0)$ классов неубывающих тотальных одноместных арифметических функций, которые определяют рефлексивные и транзитивные бинарные отношения $\{(A,B)\mid A,B\subseteq N\mathop{\&}(\exists$ о.р.ф. $h$) $(\exists f_1\in \mathfrak T^0)[A\le{}_m^hB\mathop{\&}f_0\trianglelefteq h\trianglelefteq f_1]\}$. (Здесь $k\trianglelefteq l$ означает, что функция $l$ почти всюду мажорирует функцию $k$.) Установлены критерии рефлексивности и транзитивности таких отношений. Получены свидетельства высокой разветвленности возникающей системы ограниченных сводимостей $m$-типа. Построены примеры таких сводимостей, существенно отличающиеся от стандартной $m$-сводимости в отношении структуры порождаемых ими систем степеней неразрешимости и в вопросе полноты множеств.
Библиография: 4 названия.

УДК: 517.1

Поступило: 07.02.2000

DOI: 10.4213/mzm713


 Англоязычная версия: Mathematical Notes, 2001, 70:1, 11–19

Реферативные базы данных:


© МИАН, 2024