И. Ш. Калимуллин, В. Г. Пузаренко, “О сводимости на семействах”, Алгебра и логика, 2009, том 48, номер 1,страницы 31

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

О сводимости на семействах

И. Ш. Калимуллин^a, В. Г. Пузаренко^b

^a Отдел алгебры и матем. логики, НИИ матем. мех. им. Н. Г. Чеботарёва при Казанском государственном университете, г. Казань, Россия
^b Ин-т матем. СО РАН, г. Новосибирск, Россия

Аннотация: Вводится одна сводимость на семействах подмножеств натуральных чисел, позволяющая рассматривать семейство само по себе, не фиксируя при этом его представление с помощью натуральных чисел. Эта сводимость используется для изучения серии проблем как в классической вычислимости, так и на допустимых множествах: описание индексных множеств семейств, принадлежащих $\Sigma^0_3$, обобщение теоремы полноты Фридберга для смежной сводимости на допустимых множествах и др.

Ключевые слова: семейство подмножеств натуральных чисел, допустимое множество, сводимость.

УДК: 510.5

Поступило: 29.11.2007
Окончательный вариант: 30.10.2008