Свойства квази-сводимости и иерархии Ершова

• Автор: Батыршин, Ильнур Ильдарович
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 2008
• Место защиты: Казань
• Количество страниц: 106 с.

СОДЕРЖАНИЕ
Введение

Глава 1. (-полные множества и структура (-степеней

§1.1. (-полнота и функции без неподвижных точек

§1.2. Изолированность в (-степенях

§1.3. Неизолированность в (-степенях

§1.4. Структурные свойства (-степеней п-в.и. множеств

Глава 2. Тьюринговые свойства относительной перечислимости в иерархии Ершова

Литература

Введение
Работа посвящена изучению свойств квази-сводимости и структуры квазистепеней, а также изучению множеств из различных уровнен иерархии Ершова, обладающих свойством относительной перечислимости.
Квази-сводимость ((-сводимость) была введена Тенненбаумом (см. [25], с.207) как один из примеров сводимости, отличающейся от Т-сводимости на классе вычислимо перечислимых множеств. Согласно этому определению, множество А квази-сводится к множеству В, если существует такая вычислимая функция Ф, что для любого х 6 ш выполняется: х 6 А 4$ Жф) СВ. В этом случае мы говорим, что А <д В посредством Ф (или посредством равномерно вычислимо перечислимой (в.п.) последовательности в.п. множеств и = {их}хеш, если для всех х их = ЖФ(х)). Если А <<д В посредством Ф, мы также пишем А — Фв, рассматривая Ф как (-оператор.
(-сводимость является естественным обобщением много-одной сводимости (т-сводимости): если А <т В посредством вычислимой функции /(ж), то А <д В посредством вычислимой функции д(х) такой, что Жг(х) = {/(ж)}. Также эта сводимость следующим образом связана со сводимостью по перечислимости (е-сводимостью): если А <д В посредством вычислимой функции д(ж), то и) — А <е и> — В посредством в.п. множества Ж = {< ж, 2У > |.т €Е ш,у 6 Жв(х)}, т.е. (/ж)(ж € ш — А 43- 3и(< х,и >£ Ж&7)„ С ш — В)). Кроме этого, на в.п. множествах (-сводимость влечёт Т-сводимость, но не совпадает с ней: если некоторое в.п. множество Ж <о А, то Ж <т А, но существуют такие в.п. А, В, что А <т В, но при этом А В.
Комбинаторные свойства (-сводимости и ее различные модификации широко изучались Оманадзе [14-24]. Соловьев [29] показал, что кобесконечное

в.п. множество является гипергиперпростым тогда и только тогда, когда оно не содержится ни в одном <3-полном в.п. множестве. Гилл и Морис [41] доказали, что в.п. множество является субкреативным тогда и только тогда, когда оно является ф-полным. Булитко [5] изучал другие критерии (5-полноты в.п. множеств. Селиванов [26] установил связь (5-сводимости с иерархией Клини-Мостовского. Наиболее, известным результатом в этой области стало решение Марченковым [13] с помощью свойств (5-сводимости известной проблемы Поста о существовании неполной иевычислимон в.п. степени. Подробный обзор этих и других результатов можно найти в работе [47].
Отношение А <о В является рефлексивным и транзитивным, поэтому порождает отношение эквивалентности, формирующее структуру квази-стеиеней ((5-степеней) на подмножествах со. Несложно видеть, что А <о А®В и В <д А® В, поэтому квази-степени образуют верхнюю полурешетку.
Интерес к изучению алгебраической структуры -степеней возник после работ Добрицы и Белеградека, в которых исследовалась связь (5-сводимости и алгебраических отношений между группами. Добрица [6] доказал теорему, что для каждого множества X С со существует группа б, проблема равенства слов которой имеет ту же Т-степень, что и X. В действительности, доказательство его теоремы показывает, что проблема равенства слов С? имеет ту же (5-степень, что и множество X.
Позже Макинтайр [46] показал, что для любых вычислимо представимых групп О п II. проблемы равенства слов в которых имеют степени § и Ь соответственно, если g <т 1г, то О является подгруппой любой алгебраически замкнутой группы, подгруппой которой является и II. Белеградек [4] показал, что обратное неверно, но становится верным, если Г-сводимость заменить на

х Е £>1 — 1?2 <=> их С В. Для каждого х € ад на некотором шаге 5, если х $ В1—Х>2р], перечисляем в их некоторый элемент у $ В8. Позднее перечисляем х в УД, только если у попадает в В. Если позднее нужно перечислить х в В2, просто перечисляем некоторый фиксированный Ъ 0 В в Вх. Сводимость (Тф — Во) В обеспечивается вычислимой функцией /г, определенной следующим образом: ¥Ых') = 11х.
Условия Л/"(е:г) и /Р(е:г) обсСПвЧИВаЮТ ТИКЖв, ЧТО степень (£>1 — 1?г) 0 В является собственно 2-в.п. степенью (и следовательно а <р с! 2) ® Л <д А, что противоречит условию а <с Ь.
Без потери общности предполагаем, что А содержит только нечетные числа, и будем строить В и £>2 как подмножества множества всех четных чисел. Тогда, очевидно, что {Б — П2) 0 А =<2 (1Д — Т>2) и /1.
Базовый модуль для требования Л/}е)ц. Для удовлетворения условия определяем функцию ре,г такую, что или Иф ,2 (Т>1 — П2) 0 Д посредством Ф/, ШШ Ре,г вычислима И Иф <д Д посредством ре,г-
В процессе конструкции строим равномерную в.п. последовательность в.п. множеств {Лф,г,п}?геш, и для каждого п определяем ре,г(та) как индекс Хе,*,п:
= -е,г,зг-
Сначала перепишем требование в следующем виде:
Не : (ЗА:)(Фг(А;) Т V*; £ Иф&Жад С (А - В2) 0 Л V к е Иф&И*) 2 (/Д — _02) 0 -4) У (У к) {к Е Иф <—> Хе> с Д),
Используем -последовательность циклов {0,1,2
(1) Ждем, пока или к попадет в Иф,5 для некоторого в (в этом случае