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

Работа посвящена изучению свойств квази-сводимости и структуры квазистепеней, а также изучению множеств из различных уровней иерархии Ершова, обладающих свойством относительной перечислимости.

Квази-сводимость ((^-сводимость) была введена Тенненбаумом (см. [25], с.207) как один из примеров сводимости, отличающейся от Т-сводимости на классе вычислимо иеречислимых множеств. Согласно этому определению, множество, А квази-сводится к множеству В, если существует такая вычислимая функция Ф, что для любого х 6 со выполняется: х Е, А Ж^) СВ. В этом случае мы говорим, что A.

Q-сводимость является естественным обобщением много-одной сводимости (m-сводимости): если, А <т В посредством вычислимой функции f (x), то a < х, 2V > |.т G со, у е Wg (x)}, т. е. (Уж)(ж? ш — А =Ц< х, и >е WhDu С и — В)). Кроме этого, на в.п. множествах <5-своДимость влечёт Т-сводимость, но не совпадает с ней: если некоторое в.п. множество W .

Комбинаторные свойства Q-сводимости и ее различные модификации широко изучались Оманадзе [14−24]. Соловьев [29] показал, что кобесконечное 3 в.п. множество является гипергиперпростым тогда и только тогда, когда оно не содержится ни в одном Q-полном в.п. множестве. Гилл и Морис [41] доказали, что в.п. множество является субкреативным тогда и только тогда, когда оно является Q-полным. Булитко [5] изучал другие критерии Q-полноты в.п. множеств. Селиванов [26] установил связь Q-сводимости с иерархией Клини-Мостовского. Наиболее известным результатом в этой области стало решение Марченковым [13] с помощью свойств Q-сводимости известной проблемы Поста о-существовании неполной невычислимой в.п. степени. Подробный обзор этих и других результатов можно найти в работе [47]..

Отношение a .

Интерес к изучению алгебраической структуры^{-степеней} возник после работ Добрицы и Белеградека, в которых исследовалась связь Q-сводимости и алгебраических отношений между группами. Добрица [6] доказал теорему, что для каждого множества X С со существует группа G, проблема равенства слов которой имеет ту же Т-степень, что и X. В действительности, доказательство его теоремы показывает, что проблема равенства слов G имеет ту же Q-степень, что и множество X..

Позже Макинтайр [46] показал, что для любых вычислимо представимых групп G и //. проблемы равенства слов в которых имеют степени g и h соответственно, если g <т h, то G является подгруппой любой алгебраически замкнутой группы, подгруппой которой является и II. Белеградек [4] показал, что обратное неверно, но становится верным, если Т-сводимость заменить на.

-сводимость. Он показал, что для любых вычислимо представимых групп G и Ну если G является подгруппой любой алгебраически замкнутой группы, подгруппой которой является Н, то проблема равенства слов в группе G квази-сводится к проблеме равенства слов в группе Н. Из этих результатов следует, что получение любых результатов о структуре в.п. Q-степеней дает одновременно результаты о свойствах классов конечно порожденных подгрупп алгебраически замкнутых групп..

Изучение алгебраической структуры Q-степеней в.и. множеств было начато Фишером и Амбос-Шгшесом [40], которые показали, что верхняя полурешетка в.п. Q-степеней не является дистрибутивной и не является решеткой. Первые серьезные факты об этой структуре получили Доуни, Лафорт и Инее [39]. В своей работе они построили такие невычислимые в.п. множества, А и В, что, А ~т В: но, А а В образуют минимальную пару в Q-степеняхдоказали, что для любого невычислимого в.п. множества С существует такое в.п. множество А, что С^q, А и, А является неветвящимся в в.п. Q-степеняхдоказали теорему плотности в.п. Q-степеней и показали, что 7Zq имеет неразрешимую теорию первого порядка..

Изучение алгебраической структуры Q-степеней я-в.п. множеств было начато Арслановым и Оманадзе [36J. Они доказали, что для всех в.п. A, A.

Основные результаты работы опубликованы в [50−58]. Все стандартные обозначения и определения будут даны в конце введения. Перейдем к содержанию работы..

В главе 1 излагаются результаты, продолжающие, дополняющие и обобщающие изложенные выше исследования. В этой главе изучаются свойства Q-полных множеств и алгебраическая структура Q-степеней..

В § 1.1. изучаются критерии Е^-ф-полноты, Е^-ф-полноты и Ез-ф-полноты множеств. Существуют два вида критериев полноты в.п. множеств относительно той или другой сводимости [32]. Первый из них характеризует полные в.п. множества через свойства продуктивности их дополнений, второйпосредством некоторой диагонально невычислимой функции, или функции без неподвижной точки, сводящейся к этому множеству. В § 1.1. изучаются критерии второго вида для (2-сводимости и доказывается критерий квазиполноты, сформулированный в духе этих теорем, но содержащий необходимые для этой сводимости уточнения. Доказательство этого результата реля-тивизируется на другие уровни арифметической иерархии. Также этот параграф содержит приложение полученного критерия, а именно, доказательство Q-иолноты множества К, = {(ж, п) х 6 2<�ш, п 6 и, К{х) < п}, где через К (х) обозначается беспрефиксная Колмогоровская сложность..

Предложение 1. Для любого множества, А ф ш существует такал функция f .

Теорема 2. Для любого множества, А С и (не обязательно в.п.) следующие условия эквивалентны:.

1) все в.п. множества Q-сводятся к множеству А,.

2) существует функция f .

Bf, A = {xWg (x) С A} - в.п..

Следствие 1. В.п. множество A Q-полно тогда и только тогда, когда (э/ .

В качестве следствия этого результата получено усиление известного в литературе критерия га-полноты:.

Следствие 2. Для любого множества, А С ш следующие условия эквивалентны:.

1) все в.п. множества т-сводятся к множеству А,.

2) существуют такие вычислимые функции а, Ь и д, что функция не имеет неподвижных точек, т. е. (Vx)(Wx Ф ^/(ж)) и множество {xg (x) G А} в.п..

Теорема 3. Для любого множества, А С ш следующие условия эквивалентны:.

1) все Т^-множества Q-сводятся к множеству А,.

2) существует функция f .

Следствие 3. Е2-множество, А Е^ — Q-полно тогда и только тогда, когда (3/ .

Теорема 4. Для любого множества, А С ш следующие условия эквивалентны:.

1) все Е3-множества Q-сводятся к множеству А,.

2) существует функция f .

Следствие 4. Т^-мноэюество Л ?3 — Q-полно тогда и только тогда, когда (3/ .

Теорема 5. Множество /С = {(ж, n)] х е 2< п} является Q-полным..

В § 1.2. изучается вопрос существования изолированных 2-в.п. Q-степеней. Определение изолированных тыорипговых степеней 2-в.п. множеств было введено Купером и Йи, а изучение свойств таких степеней стало одним из основных направлений исследований алгебраической структуры Т-степеней. Степень d называется изолированной снизу, если существует в.п. степень a q d такая, что для любой в.п. степени Ь, если b >q d, то b >q а. При этом говорят, что степень, а изолирует степень d сверху..

Купер и Йи (неопубликовано) построили пример изолированной снизу 2-в.п. Т-степени, пример неизолированной снизу 2-в.п. Т-степени и поставили ряд вопросов о дальнейшем изучении свойств изолированности в тьюрин-говых степенях. Изучение этих вопросов впоследствии активно проводилось рядом исследователей. Лафорт [45] показал, что для каждой пары тьюрин-говых в.п. степеней, а < b существует изолированная снизу 2-в.п. степень d между ними, а < d < b. By [49] показал, что существуют такие в.п. степени a, b и 2-в.п. степень d, что, а < d < b, а изолирует d снизу и b изолирует d сверху..

Возникает естественный вопрос: верно ли утверждение, обобщающее эти 8 две теоремы, а именно, верно ли, что для каждой пары тьюринговых в.п. степеней, а < b существует такая 2-в.п. степень d между ними, что, а изолирует d снизу и b изолирует d сверху?.

Арсланов, Лемпп и Шор [35] показали, что существует невычислимая в.п. степень а, которая не изолирует никакой 2-в.п. степени d снизу. Ефремов [11] показал, что существует такая в.п. степень Ь, которая не изолирует никакой 2-в.п. степени d сверху. Таким образом, для тьюринговых степеней этот результат не имеет места..

Теорема 6 показывает, что это утверждение, однако, верно для квазистепеней..

Теорема 6. Для каждой пары в.п. степеней a .

Следствие 5. Существует 2-в.п. степень, которая Q-несравнима ни с какой нетривиальной (отличной от 0 и 0') в.п. степенью..

Следствие 6. Для любой в.п. степени а, О .

В § 1.3. продолжается изучение вопроса, затронутого в параграфе § 1.2., а именно изучается вопрос существования неизолированных 2-в.п. степеней. Арсланов, Лемгш и Шор [35] показали, что неизолированные снизу Т-степени плотны в стуктуре в.п. Т-степеней. Теорема 7 показывает, что э тот результат имеет место и для Q-степеней..

Теорема 7. Для каждой пары в.п. степеней, v .

Следствие 7. Неизолированные снизу 2-е.п. Q-степени плотны в структуре в.п. Q-степеней..

Теорема 8 показывает, что существует 2-в.п. Q-степень, которая не изолируется снизу не только никакой в.п. Q-степенью, а, вообще, никакой Q-степенью..

Теорема 8. Существует такая собственно 2-в.п. степень dчто для любой b .

В 1984 году Хэй и Шор (неопубликовано) построили 2-в.п. Т-степень d такую, что между d и О' нет в.п. Т-степеней, т. е. фактически доказали существование изолированной сверху Т-степени..

Систематическое изучение изолированных сверху Т-степеней было начато в работах [10] и [11], в которых было показано, что над любой неполной в.п. степенью существует изолированная сверху степень, а также построена невычислимая в.п. степень, под которой все 2-в.п. степени являются неизолированными сверху. Тем самым, было показано, что изолированные сверху 2-в.п. Т-степени не плотны в структуре в.п. Т-степеней..

Теорема б показывает, что для Q-степеней имеет место обратный результат: изолированные сверху 2-в.п. Q-степени плотны в структуре в.п. Q-степеней. Теорема 9 показывает, что неизолированые сверху 2-в.п. Q-степени плотны вниз в структуре в.п. Q-степеней..

Теорема 9. Для каждой в.п. степени v > О существует такая собственно 2-в.п. степень d, что d w^q a..

Следствие 8. Неизолированные сверху 2-в.п. Q-степени плотны вниз в.

10 структуре в.п. Q-степеней..

Теорема 10. Для любой в.п. степени u >q 0 существует такая собственно 2-в.п. степень d .

Следствие 9. Для любой в.п. степени, а > 0 существует собственно 2-в.п. степень d .

В § 1.4. изучаются другие фундаментальные свойства алгебраической структуры Q-степеней: расщеп ляемость, дополняемость наверх и дополняемость вниз. Результаты этого параграфа получены в нераздельном сотрудничестве с Арслановым и Оманадзе..

К сожалению, сложно рассчитывать на существование удобной характе-ризации расщепляемых Q-степеней. В отличие от Тыоринговой сводимости и сводимости по перечислимости, даже Q-степень креативного множества К не расщепляется в в.п.^{-степенях,} как показали Фишер и Амбос-Шриес [40]. Более того, Доуни, Лафорт и Ниес [39] доказали, что если R является в.п. полурекурсивным множеством таким, что R .

11 является бесконечным и ретрассируемым, тогда для всех множеств, А и В, из R .

Предложение 11. Для любого в.п. не вычислимого полурекурсивного множества, А существует в.п. множество В с ретрассируемым дополнением такое, что A =q В..

Следствием этого предложения является усиление результата, полученного в [39]..

Следствие 10. Если R является в.п. полурекурсивным множеством, и R .

Известно, что любое п-в.п. полурекурсивное множество для всех п < и или является в.п., или его дополнение является в.п. (Джокуш и Оуингс [44]). Поэтому если (^-степень, а содержит п-в.п. полурекурсивное множество для некоторого п < ш, то, а не является расщепляемым в (^-степенях. Однако теоремы 13 и 14 показывают, что расщепляемая 2-в.п. степень есть под каждой 2-в.п. степенью, а > 0 и над каждой в.п. степенью b < О'..

Предложение 12. Пусть А, В, А0, А — в.п. .множества, В С А, А = АоиА1, АопА1 = 0! Во = ВпАоиВ1=ВГ >1Ь Тогда Л — В0 .

Теорема 13. Пусть, А и В — такие в.п. множества, что, А — В фq 0..

Тогда, А является непересекающимся объединением таких в.п. множеств А0 и Ai, что Ai — В .

Следствие 11. Под любым, 2-в.п. множеством, А — В фq О существует расщепляемая 2-в.п. степень..

Теорема 14. Пусть, А — такое в.п. множество, что К А. Тогда существуют такие не вычислимые в.п. мнооюества Aq и А, что A (&Aq, А 0 Ai, А © А^g, А 0 Ао и Aq и, А образуют минимальную пару в в.п. Q-степенях..

Следствие 12. Пусть, а < О' - в.п. Q-степень. Тогда существует расщепляемая, в.п. степень над а..

Вопрос о существовании расщепляемой в.п. степени между любыми двумя в.п. степенями пока остается открытым..

Так как О' является нерасщепляемой Q-степеныо, то не существует дополняемой наверх Q-степени. Дополняемые вниз Q-степени существуют (впервые это было показано в [39], где была построена минимальная пара Q-степеней). Теорема 15 показывает, что каждая П®Q-степень а, О < а < (У, образует минимальную пару в в.п. степенях с некоторой Q-степенью Ь, несравнимой с а. Тем самым показано, что каждая Щ Q-степень является дополняемой вниз в в.п. Q-степенях..

Теорема 15. Для каждого Пз-множества А, 0 .

Теорема 16 показывает, что в теореме 15 в общем случае множество В нельзя сделать в.п. множеством..

Теорема 16. Существует такое в.п. множеством A .

13 всех невычислимых в.п. множеств We существует, такое невычислимое в.п. множество Хе, что Хе .

Второе направление исследований связано с изучением множеств из различных уровней иерархии Ершова, обладающих свойством относительной перечислимости..

Говорят, что (всюду определенная) одноместная функция / является пределом последовательности (всюду определенных) фуикций {fs}seu, если fs{x) = f (x) для почти всех (т.е. для всех, кроме конечного числа) s при любом значении х. В этом случае также говорят, что последовательность функций {/s}seш (поточечно) сходится к функции / (записывается как / = lims fs)..

Полезной характеристикой множеств, по тыоринговой сводимости расположенных ниже 0', является следующее их свойство: А <т 0' тогда и только тогда, когда существует такая вычислимая функция /(s, х), что .А (з-) = limsf (s, x). В уже ставших классическими работах Ю. Л. Ершов [7−9] построил иерархию множеств, расположенных ниже 0', теперь известную в литературе как «иерархия Ершова». Место множества, А в иерархии определяется по количеству изменений в аппроксимиции множества, А с помощью описанной выше вычислимой последовательности, т. е. по количеству различных пар соседних элементов этой последовательности. Иерархия Ершова состоит из «конечных» и «бесконечных» уровней. К конечным уровням иерархии Ершова относятся множества, у которых количество таких изменений ограничено некоторым натуральным числом. В противном случае множество принадлежит одному из бесконечных уровней иерархии Ершова. Бесконеч.

14 ные уровни иерархии определяются с помощью бесконечных конструктивных ординалов..

Как оказалось, возникающая иерархия множеств исчерпывает всю совокупность множеств, расположенных по тьюринговой сводимости ниже 0', степени креативного множества. Каждый следующий уровень иерархии содержит все предыдущие, но не совпадает ни с одним из них..

В работах [31] и [34] было доказано, что если В е Л~ С — в.п. относительно некоторого, А <т С и В <т С, то существует такое множество D <Е Е¹, что В <т D <т С. Этот результат показывает, что степень п-в.п. множества, которая является вычислимо перечислимой относительно некоторой в.п. степени, лежащей ниже ее, является 2-в.п. степенью. Таким образом, относительная перечислимость на конечных уровнях иерархии Ершова уменьшает «сложность» этих уровней. Долгое время открытым оставался вопрос о том, обладает ли относительная перечислимость таким же свойством на бесконечных уровнях иерерхии Ершова..

В главе 2 дается исчерпывающий ответ на этот вопрос..

В теореме 17 доказывается обобщение этого свойства на классы множеств AVn, где vn (n > 1) — произвольные обозначения клиниевской системы для соп соответственно..

Теорема 17. Для любого п > 1 если vo = шп+1, В 6 А" 1, А — в.п., В <т, А ® WA, mo существует такое множество D? Е" 1, где с <о v и со = ип, что В <Т D <Т AeWA..

Следствие 13. Любая 2-GEA, А'1 -степень является Е" 1 -степенью, где Мо = шп+1, с <о v и со = ujn (п> 1)..

Сразу же возникает несколько новых естественных вопросов по поводу дальнейших возможных обобщений данной теоремы:.

1) Можно ли сохранить результат этой теоремы, если ослабить её- условия, заменив класс множеств А" 1 на более общий класс Е¹?.

2) Можно ли усилить эту теорему, сделав множество D из условия принадлежащим классу Е" 1 для некоторого, а такого, что ао <.

3) Можно ли обобщить эту теорему на более высокий уровень иерархии Ершова — на уровень А" 1 для некоторого v такого, что vo =.

Теорема 18 дает отрицательный ответ на первый вопрос, ее следствие 14 -отрицательный ответ на второй вопрос, а теорема 19 — отрицательный ответ на третий вопрос..

Теорема 18. Для любого п > 0 если ао = то существует собственно Е" 1 -множество В, вычислимо перечислимое относительно некоторого в.п. множества, А <т В..

Следствие 14. Для любого п > 0 ec. au ао = шп+1, то существует множество В? Л" 1, вычислимо перечислимое относительно некоторого в.п. множества, А <т В, такое, что (Ус <о Ь)(УС? Е~1)(5 фт С), где Ъ <о, а и Ьо = ш11..

Теорема 19. Пусть vo = тогда существует множество В? А" 1, вычислимо перечислимое относительно некоторого в.п. множества, А В, такое, что (V6 <0 v)(VC? E¹)(J5 С)..

Таковы основные результаты работы..

Теперь скажем о некоторых определениях, сокращениях и договоренностях, используемых в дальнейшем..

Множества, рассматриваемые ниже, являются подмножествами множества натуральных чисел из = {0,1,2,.}. У функций, рассматриваемых пи.

16 же, если специально не оговорено другое, область определения и область значения являются подмножествами ш. Греческими буквами и малыми латинскими буквами обозначаются функции, большими латинскими буквами обозначаются множества и характеристические функции этих множеств, т. е. если ACw, то А (х) обозначает следующую функцию: то через, А — В обозначается разность, А В, а через, А ф В — множество {2х х Е А}- У{2ж+1 |ар Е By. Л^ощность множества, А обозначается через, А |. А =* В означает, что {А-В) J (BА) | < оо..

Пусть Фо, ФьФ2,.- - некоторая эффективная нумерация всех частично-вычислимых (ч.в.) функций, тогда Wo, И^,. обозначает соответствующую ей эффективную нумерацию вычислимо перечислимых (в.п.) множеств. Аналогично, если Ф^, Ф^, Ф2 > ¦¦¦ ~ некоторая эффективная нумерация частично вычислимых от множества, А функций, то. W^, W4[.. обозначает соответствующую ей нумерацию множеств, вычислимо перечислимых относительно множества А. Вычислимыми функциями называем ч.в. функции, область определения которых совпадает с и. Через {Dn}&bdquo-еш обозначаем стандартную нумерацию всех конечных подмножеств ш, т. е. Dq — 0, и если xi,., xn — различные числа из и и х — 2Xl +. + 2х", то Dx = {^i,., хп}..

Результат, полученный к концу шага s в процессе вычисления обозначаем через Ф^(ж)[з]. Например, если множество, А в. п. (или допускает какую нибудь пошаговую аппроксимацию), то эта запись означает результат,.

Если, А С ш, то, А и и — А обозначают разность ш А. Если А, В С ш, полученный за s шагов работы е-ой машины Тьюринга на входе х с оракулом A[s], последнее означает подмножество множества А, перечисленное к концу шага s (соответственно, аппроксимацию множества, А к концу шага s). Если Фе (А-.т) определена, то значение ее wse-функции записывается как сре (А, х). По определению, <�ре (А, х) = 1+ наибольшее число, использованное в этом вычислении. Аналогично определяется.

Запись fx означает ограничение функции / к числам у < х. Таким образом, если Фе (ж) определена, тогда значение ее 'use-функции равно, А [</?е (А, х), и изменение, А в промежутке < ipe (A, x) разрушает это вычисление..

Двухместная функция (х, у), определенная как (х, у) : — +зж+у для ж, у Е со, и осуществляю! цая биективное отображение и'2 на ш, называется канторовской нумерующей функцией. Через /иг обозначаются однозначно определенные функции такие, что для всех х, у 6 и, (l (x), r (x)) = х, 1((х, у)) = х, г ((х, у)) = уn-местная функция (х,. .хп) при п > 2 определяется так: (xi,. хп) — {{. (xi, хч)^хз),., хп). Если функция / в точке х определена, то пишем f (x) j, в противном случае пишем f (x) ТОбласть определения функции / обозначается через dom (f), область ее значенийчерез rng (f)..

Множество АС. Ш является полурекурсвивным (см. [42]), если существует такая вычислимая функция /: ш2 —" ш, что для всех ж, у, (i) ffay) = х или f (x, y) = у, п (и) х Е /IV у 6 А f (x, у) е А..

Множество, А называется 2-СЕА множеством, если существует такое в.п. множество В <т А, что, А = Wf для некоторого е..

Множество, А сводится по Тьюрингу (или Т-сводится) к множеству В.

А <т В), если (Зп)(/х)(А (х) — Ф"(х)), где Ф®- - некоторая вычислимая относительно В функция..

Множество, А слабо-таблично сводится (или ги//-сводится) к множеству В (Л и (В, п, х)), где и (В, п, х) — wse-функция вычисления.

Множество, А таблично сводится (или й-сводится) к множеству В (А <и В), если существуют такие вычислимые функции /ид, что (х G, А (3 у G Dg (x))(/z < f (x))(x G В х G Dy)) (эквивалентное определение через булевы функции и табличные условия см. в [25])..

Множество, А много-одно сводится (пли m-сводится) к множеству В (А <т В), если существует такая вычислимая функция /, что (Ух)(х G, А /(-г) Е.

В)..

Множество, А сводимо по перечислимости (или е-сводится) к множеству В (А <е В), если (Зп)(Уж)(т Е, А ^ (3у)((х, у) G WnhDy С В))..

Множество, А принадлежит классу Е^ (или является Е°-множеством) для п > 0, если существует такое вычислимое отношение R (x, у, у2,., уп), что х <= A (3yi)(yy2)(3y3).(Qyn)R (x, yi, .,?/"), где Q является квантором 3, если п нечетно, и квантором V, если п четно. Множество, А принадлежит классу П^, если со — А принадлежит классу Множество, А принадлежит классу если A G Е° и A G.

Множество, А называется n-в.п. множеством (или принадлежит классу Е" 1) для некоторого п > 1, если существует вычислимая функция f (s, x) такая, что для каждого х: /(о, ж) = О,.

А (х) = lims/(s, a-), и s: f (s, x)^f (s + l, x)}.

Степень, а называется п-в. п. степенью для п > 1, если она содержит п-в. п. множество, и она называется собственно п-в. п. степенью, если она содержит п-в. п. множество, но не содержит т-в. п. множеств для т < п..

Пусть / - произвольная всюду определенная одномес тная функция. Множество, А называется /-вычислимо перечислимым, если существует такая вычислимая функция д, что для произвольных s их.

А (х) = limsg (s, x), и аА, д{х) < /(ж), где сна>д (х) = |{s|g (s, ж) ф g (s + 1, ж)}|. Множество, А называется ш-в.п. множеством, если оно /-b.il для некоторой вычислимой функции /..

Пусть 0,<о — клиниевская система обозначений для конструктивных ординалов (подробное описание свойств ординалов, клиниевской системы обозначений и обзор результатов в этой области см. в [3]). Пусть даны, а Е О и вычислимо перечислимая а-последователыюсть в.п. множеств 7Z = {Rx}x.

Sa{П) = {z{3x <о a)[z Е Rxke (x) ф e (a)&(Vj/ <о x)[z? Ry]], Ра (К) = u~Sa (П), где е (ж) — функция чётности на О, т. е. е (ж) = 0, если х — четный элемент порядка ({уу <о <о) и е (х) = 1 в противном случае..

Обозначим через Е" 1 класс всех множеств вида Sa (7Z), где 7Z пробегает все вычислимо перечислимые a-последовательности в.п. множеств, через П~1 обозначим класс всех множеств вида Ра (Щ. Определим А" 1 ^ П" 1 П Е" 1..

Будем говорить, что некоторое множество, А Е 1 является собственно.

Е^-множеством, если (Vb <о a)(WB G фт В)..

Через хо будем записывать ординал, обозначением которого является х..

Пусть ?() есть предел последовательности ы, uf^. Тогда любой ординал, а < eq можно представить в нормальной форме:.

О! = щ • + п2 • L082 +. + пкиА, (а> pi>. > /Зк, ть,., пк < и)..

В частности, для, а < а = по • сош +. + nmi • ш + пт..

Пусть <г — любая из вышеперечисленных сводимостей, тогда <г является рефлексивным и транзитивным отношением, поэтому для каждой такой сводимости можно определить отношение эквивалентности множеств относительно этой сводимости: говорим, что множества, А и В г-эквивалентны (А ~г В), если, А <г В и В <г А. Для каждого множества, А определим его г-степень: degr (A) = {ЙС шВ =г А}..

Говорим, что в.п. множество, А r-полно, если все в.п. множества г-сводятся к А. Говорим, что Е°-множество, А r-полно, если все Е°-множества сводятся к А..

Эти определения, а также основные результаты, касающиеся данной тематики, могут быть найдены в книгах [1], [25], [28], [30] и [48]..

1. Арсланов М. М. Рекурсивно перечислимые множества и степени неразрешимости. — Казань: изд-во КГУ. — 1986. — 206 с..

2. Арсланов М. М. Локальная теория степеней неразрешимости и Д2-множества. Казань: изд-во КГУ. — 1987. — 140 с..

3. Арсланов М. М. Иерархия Ершова. Спецкурс для студентов мехмата. -Казань: Казанский государственный университет, 2007 86 с..

4. Белеградек О. В. Об алгебраически замкнутых трупах // Алгебра и логика. 1974. — Т.13. — т. — С. 239−255..

5. Булитко В. К. О способах характеризации полных множеств // Изв. АН СССР. Серия математическая. 1991. — Т.55. — № 2. — С. 227−253..

6. Добрица В. П. О проблеме равенства слов на рекурсивно определенных группах // Третья Всес. конф. по мат. логике. Тезисы докладов. Новосибирск. — 1974. — С. 63−65..

7. Ершов Ю. Л. Об одной иерархии множеств, I // Алгебра и Логика. 1968. Т.7. -№ 3. С. 47−75.8j Ершов Ю. Л. Об одной иерархии множеств, II // Алгебра и Логика. 1968. Т.7. -т. С. 15−48..

8. Ершов Ю. Л. Об одной иерархии множеств, III // Алгебра и Логика. -1970. Т.9. — № 1. — С. 34−52..

9. Ефремов С. С. Изолированные сверху d-в.п. степени, I// Известия высших учебных заведений. Математика. 1998. — № 2. — С. 20−28..

10. Ефремов С. С. Изолированные сверху d-в.п. степени, II// Известия высших учебных заведений. Математика. 1998. — № 7. — С. 18−25..

11. Захаров С. Д. О еи s-степенях // Алгебра и логика. — 1984. — Т.23. — № 4. С. 395−406..

12. Марченков С. С. Об одном классе неполных множеств // Математические заметки. 1976. — Т.20. — № 4. — С. 473−478..

13. Оманадзе Р. Ш. О сводимости на классе рекурсивно перечислимых множеств // Сообщ. АН ГССР. 1978. — Т.91. — № 3. — С. 549−552..

14. Оманадзе Р. Ш. Об ограниченной Q-сводимости // Сообщ. АН ГССР. -1980. Т. 100. -т.- С. 57−60..

15. Оманадзе Р. Ш. О верхней полурешетке рекурсивно перечислимых Q-степеней // Алгебра и логика. 1984. — Т.23. — № 2. — С. 175−184..

16. Оманадзе Р. Ш. Q-сводимость и нигде не простые множества // Сообщ. АН ГССР. 1987. — Т. 127. — № 1. — С. 29−32..

17. Оманадзе Р. Ш. О Q-степенях неускоряемых множеств // Труды ИПМ им. И. Н. Векуа ТГУ. 1987. — Т.20. — С. 21−31..

18. Оманадзе Р. Ш. О плотности неускоряемых Q-степеней // Сообщ. АНГССР. 1988. — Т.131. — т. — С. 485−488.10 120| Оманадзе Р. Ш. Классы рекурсивно перечислимых множеств и Q-сводимость // Математические заметки. 1989. — Т.42. — № 2. — С. 79−82..

19. Оманадзе Р. Ш. Соотношения между некоторыми сводимостями // Со-общ. АН Грузии. 1990. — Т.140. — № 3. — С. 473−476..

20. Оманадзе Р. Ш. Об одном усилении (^-сводимости // Сообщ. АН Грузии.- 1991. Т. 142. — № 3. — С. 481−484..

21. Оманадзе Р. Ш. О верхней полурешетке рекурсивно перечислимых sQ-степеней // Алгебра и логика. 1991. — Т.ЗО. — № 4. — С. 405−413..

22. Оманадзе Р. Ш. О зф-полноте рекурсивно перечислимых множеств // Математические заметки. 1992. — Т.52. — № 3. — С. 102−107..

23. Роджерс X. Теория рекурсивных функций и эффективная вычислимость.- М.: Мир, 1972. 624 с..

24. Селиванов B.JI. Об индексных множествах в иерархии Клини-Моетовского // Труды ИМ СО АН СССР. 1982. — Т.2. — № 3. — С. 135−158..

25. Селиванов В. Л. Об иерархии Ершова // Сиб. мат. журнал. 1985. — Т. XXVI. — Ш. — С. 134−150..

26. Соар Р. И. Вычислимо перечислимые множества и степени. Казань: Казанское математическое общество, 2000. — 576 с..

27. Соловьев В. Д. Q-сводимость и гипергиперпростые множества //Вероятн. методы и киберн. Казань: изд-во КГУ. — 1974. — вып.11. — С. 121−128..

28. Шенфилд Дж. Степени неразрешимости. Москва: Наука, 1977. — 192 с..

29. Arslanov M.M. Degree structures in the Local degree theory // Lecture Notes in pure and applied mathematics. 1997. — V.187. — P. 49−74..

30. Arslanov M.M. Truth-table complete computably enumerable sets // Computability and models: perspectives east and west (Cooper S.B. and Goncharov S.S. (eds.)). Kluwer Academic/Plenum Publishers, 2003. — P. 1−10..

31. Arslanov M.M., Cooper S.B. and Kalimullin I.Sh. Splitting properties of total enumeration degrees // Algebra and Logic. 2003. — V.42. — № 1. — P. 3−25..

32. Arslanov M.M., LaForte, G.L., Slaman, T.A. Relative enumerability in the difference hierarchy // J. Symbolic Logic. 1998. — V.63. — P. 411−420..

33. Arslanov M.M., Lempp S., Shore R.A. On isolating r.e. and isolated d-r.e. degrees // Computability, enumerability, unsolvability (Cooper S.B., Slaman T.A. and Wainer S.S. (eds.)). Cambridge University Press, 1996. — P. 61−80..

34. Arslanov M.M., Omanadze R.Sh. Q-degrees of n-c.e. sets // Illinois Journal of Mathematics. 2007. — V.51. — №. — P. 1189−1206..

35. Bennett C.H. Logical depth and physical complexity // The universal Turing Machine. A Half-Century Survey (R. Herken (ed.)). Oxford: Oxford University Press, 1988. — P. 227−258..

36. Calude C.S., Nies A. Chaitin и numbers and strong reducibilities //J. Univ. Сотр. Sci. 1998. — V.3. — P. 1162−1166..

37. Downey R., LaForte G.L., Nies A. Computably enumerable sets and Quasi-reducibility // Ann. of Pure and Applied Logic. 1998. — V.95. — P. 1−35..

38. Fischer P., Ambos-Spies K. Q-degrees of r.e. sets // J. Symb. Logic. 1987. V.52. №. — P. 317..

39. Gill J.T., Morris P.H. On subcreative sets and S'-reducibility // J. Symbolic Logic. 1974. — V.39. — № 4. — P. 669−677..

40. Jockusch C.G. Semirecursive sets and positive reducibility // Trans. Amer. Math. Soc. 1968. — V.131. — P. 420−436..

41. Jockusch C.G., Lerman M., Soare R.I., Solovay R.M. Recursively enumerable sets modulo iterated jumps and extensions of Arslanov’s completeness criterion // J. Symbolic Logic. 1989. — V.54. — P. 1288−1323..

42. Jockusch C.G., Owings J.C. Weakly semirecursive sets // J. Symbolic Logic.- 1990. V.55. — P. 637−644..

43. LaForte G.L. Phenomena in the ro-r.e. and n — RE A degrees. Ph. D. ThesisMichigan: University of Michigan, 1995..

44. Macintyre A. Omitting quantifier free types in generic structures // J. Symbolic Logic. 1972. — V.37. — P. 512−520..

45. Omanadze R.Sh. Quasi-degrees of recursively enumerable sets // Computability and models: perspectives east and west (Cooper S.B. and Goncharov S.S. (eds.)). Kluwer Academic/Plenum Publishers, 2003. — P. 289 319..

46. Odifreddi P. Classical recursion theory. Amsterdam: North-Holland. — 1989. 610 P..

47. Wu G. Bi-isolation in the d.c.e. degrees //J. Symbolic Logic. 2004. — V.69. — № 2. — P. 409−420.Работы автора по теме диссертации.

48. Батыршин И. И. Относительная перечислимость в иерархии Ершова // Математические заметки. 2008. — Т.84. — вып.4. — С. 506−515..

49. Батыршин И. И. Изолированные 2-вычислимо перечислимые Q-степени // работа принята к печати в журнале «Известия высших учебных заведений. Математика» ..

50. Batyrshin I.I. Quasi-completeness and functions without, fixed-points // Math. Log. Quart. 2006. — V.52. — № 6. — P. 595−601..

51. Arslanov M.M., Batyrshin I.I., Omanadze R.Sh. Structural properties of Q-degrees of n-c.e. sets // Annals of Pure and Applied Logic. 2008. — V.156. -P. 13−20..

52. Batyrshin I.I. Non-isolated Quasi-degrees // работа принята к печати в Mathematical Logic Quarterly..

53. Batyrshin I.I. Quasi-completeness and functions without fixed-points // The Bulletin of Symbolic Logic. 2007. — V.13. — № 2. — P. 266−267..

54. Batyrshin I.I. Relative enumerability in the Ershov’s hierarchy // Logic colloquium 2005. Book of abstracts. Athens. — 2005. — P. 49..

55. Batyrshin I.I. Quasi-completeness and functions without fixed-points // Logic Colloquium 2006. Book of abstracts. Nijmegen. — 2006. — P. 3..

56. Batyrshin I.I. The algebraic structure of Quasi-degrees // Logic Colloquium 2007. Book of abstracts. Wroclaw. — 2007. — P. 35..