Свойства квази-сводимости и иерархии Ершова тема диссертации и автореферата по ВАК РФ 01.01.06, кандидат физико-математических наук Батыршин, Ильнур Ильдарович

• Батыршин, Ильнур Ильдарович
• кандидат физико-математических наук
• 2008

Оглавление диссертации кандидат физико-математических наук Батыршин, Ильнур Ильдарович

Введение

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

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

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

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

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

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

Введение диссертации (часть автореферата) на тему «Свойства квази-сводимости и иерархии Ершова»

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

Квази-сводимость ((^-сводимость) была введена Тенненбаумом (см. [25], с.207) как один из примеров сводимости, отличающейся от Т-сводимости на классе вычислимо иеречислимых множеств. Согласно этому определению, множество А квази-сводится к множеству В, если существует такая вычислимая функция Ф, что для любого х 6 со выполняется: х Е А Ж^) СВ. В этом случае мы говорим, что A <q в посредством Ф (или посредством равномерно вычислимо перечислимой (в.п.) последовательности в.п. множеств U — {UX}XEIJJ, если для всех х ux = И7^)). Если A <q В посредством Ф, мы также пишем А = Ф5, рассматривая Ф как Q-оператор.

Q-сводимость является естественным обобщением много-одной сводимости (m-сводимости): если а <т в посредством вычислимой функции f(x), то a <q в посредством вычислимой функции д(х) такой, что = {f{x)}. Также эта сводимость следующим образом связана со сводимостью но перечислимости (е-сводимостью): если a <q в посредством вычислимой функции д{х), то со — а <е ш — в посредством в.п. множества w = {< х, 2v > |.т g со,у е Wg(x)}, т.е. (Уж)(ж £ ш - а =Ц< х,и >е whdu С и - в)). Кроме этого, на в.п. множествах <5-своДимость влечёт Т-сводимость, но не совпадает с ней: если некоторое в.п. множество w <q а, то w <т а, но существуют такие в.п. а, в, что а <т в, но при этом а ^q в.

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

Отношение А <д В является рефлексивным и транзитивным, поэтому порождает отношение эквивалентности, формирующее структуру квазистепеней ((^-степеней) на подмножествах ш. Несложно видеть, что А <д А@В и В <с} А® В, поэтому квази-степени образуют верхнюю полурешетку.

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

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

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

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

Изучение алгебраической структуры (^-степеней я-в.п. множеств было начато Арслановым и Оманадзе [36]. Они доказали, что для всех в.п. А\^Ач выполняется /11 — А^ <с? Ау, показали, что для каждого п существует собственно д-в.п. (^-степень; построили пример 2-в.п. множества А\ — Ач такого, что для любого в.п. множества IV, если А\ — А2 <д W, то А\ <д IV; и показали, что для любого в.п. множества V <о К = {.г|Фж(ж) .[} найдется такое 2-в.п. множество А — В, что V А — В <<2 К и (^-степень А - В не содержит в.п. множеств.

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

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

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

Предложение 1. Для любого множества А ф ш существует такал функция / <д А, что (Ух)(\¥х ф И^)).

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

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

2) существует функция / <д А такая, что {Ух)(Шх ф Wf(x)) и множество 6

В1,А = {х\№д(х) С А} - в.п.

Следствие 1. В.п. множество А С^-полно тогда и только тогда, когда (Э/ <д А)(Ух)(\¥х ф ^/{х)) и множество BfJA - в.п.

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

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

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

2) существуют такие вычислимые функции а,Ь и д, что функция не имеет неподвижных точек, т.е. (Ух)(\¥х ф ^/(ж)) и множество {х\д(х) £ А} в.п.

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

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

2) существует функция / <с} А такая, что (Ух)(Ш'х ф ^/(х)) и множество является ЕЦ.

Следствие 3. Т^-множество А Е^ — С^-полно тогда и только тогда, когда (3/ <д т4)(\/а;)(И/а; ф и множество BfsA £ Е®.

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

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

2) существует функция / <<д А такая, что (\/х)(\¥х фт У^Цх)) и множеа(х), если д(х) е А Ь(х), если д{х) £ А, ство является £3.

Следствие 4. Т^-мноэюество Л £3 — (¿-полно тогда и только тогда, когда (3/ <д А)(ух)^х ^ И7/^)) и множество £

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

В §1.2. изучается вопрос существования изолированных 2-в.п. (^-степеней. Определение изолированных тыоринговых степеней 2-в.п. множеств было введено Купером и Йи, а изучение свойств таких степеней стало одним из основных направлений исследований алгебраической структуры Т-степеней. Степень с1 называется изолированной снизу, если существует в.п. степень а <д (1 такая, что для любой в.п. степени Ь, если Ь с1, то Ь <<3 а. При этом говорят, что степень а изолирует степень с! снизу. Степень (1 называется изолированной сверху, если существует в.п. степень а ><3 с! такая, что для любой в.п. степени Ь, если Ь >д <1, то Ь >д а. При этом говорят, что степень а изолирует степень с! сверху.

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

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

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

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

Теорема 6. Для каждой пары в.п. степеней а <ц Ь существует собственно 2-в.п. степень с1, а <<э с! <с$ Ь; такая что а изолирует (1 снизу и Ь изолирует с1 сверху.

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

Следствие 6. Для любой в.п. степени а, О <д а <д 0' существуют собственно 2-в.п. степени Ь,с такие, что Ь а с, а изолирует Ь сверху и а изолирует с снизу.

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

Теорема 7. Для каждой пары в.п. степеней, V <а и существует такая собственно 2-в.п. степень с!; что V <д (1 <с} и, и для любой в.п. степени 9 чг, если ллг <С2 с1; то найдется в.п. степень а <д с1 такая, что а ^ ш.

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

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

Теорема 8. Существует такая собственно 2-в.п. степень с!; что для любой Ь <с$ с1 найдется в.п. степень а <с$ с1 такая7 что а ^ Ь.

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

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

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

Теорема 9. Для каждой в.п. степени V > О существует такая собственно 2-в.п. степень с1; что с! <с$ V, и для любой в.п. степени ш найдется в.п. степень а такая, что с! <<э а«(1 <<3 —> w ^ а.

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

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

Теорема 10. Для любой в.п. степени и >д 0 существует такая собственно 2-е.п. степень <1 <<3 и7 что для, любой в.п. степени если <<э с17 то найдется в.п. степень а <д <1 такая, что а и для, любой любой в.п. степени ч/ найдется в.п. степень с такая, что с! <с} с и, с! <<э ™ ^ с.

Следствие 9. Для любой в.п. степени а > 0 существует собственно 2-в.п. степень (1 <с} а, которая не является изолированной ни сверху, ни снизу.

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

К сожалению, сложно рассчитывать на существование удобной характе-ризации расщепляемых (^-степеней. В отличие от Тыоринговой сводимости и сводимости по перечислимости, даже (^-степень креативного множества К не расщепляется в в.п. ^-степенях, как показали Фишер и Амбос-Шриес [40]. Более того, Доуни, Лафорт и Ниес [39] доказали, что если В является в.п. полурекурсивным множеством таким, что В, <д А 0 В для некоторых в.п. множеств А и В, тогда или Я <<3 А, или В <д В. Так как (^-степень К содержит полурекурсивное множество, то из этого результата следует, в частности, результат Фишера и Амбос-Шпиеса. Возникает естественный вопрос, верно ли, что для каждого в.п. полурекурсивного множества В и произвольных (не обязательно в.п.) множеств А и В, если В <д А Ф В, то или В <<д А, или В <д В? Захаров [12] доказал, что для каждого множества В, если со — В

11 является бесконечным и ретрассируемым, тогда для всех множеств А и В, из Я <д А ® В следует, что или Я <<д А, или Я <д В. Таким образом, (^-степени множеств с бесконечными ретрассируемыми дополнениями не являются расщепляемыми. Известно (см. [42]), что в.п. множества с ретрассируемыми дополнениями являются полурекурсивными, но обратное не верно. Тем не менее, Предложение 11 показаывает, что (^-степени в.п. полурекурсивных множеств совпадают с (^-степенями в.п. множеств с ретрассируемыми дополнениями.

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

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

Следствие 10. Если Я является в.п. полурекурсивным множеством, и В А® В для некоторых А и В, то или Я. <ф А, или Я <д В.

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

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

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

12

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

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

Теорема 14. Пусть А - такое в.п. множество, что К А. Тогда существуют такие не вычислимые в.п. мнооюества Аа и А\, что А(&Ао А(& А\, А © А\ А 0 Ло и Ао и А\ образуют минимальную пару в в.п. ф-степенях.

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

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

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

Теорема 15. Для каждого Пз-множества А, 0 <д А <д 0', существует такое А^-множество В, что А^В и для всех в.п. множеств X, если X <д А&Х <д В, тогда X <д 0.

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

Теорема 16. Существует такое в.п. множеством А <д К, что для

13 всех невычислимых в.п. множеств Ше существует, такое невычислимое в.п. множество Хе, что Хе <<5 А и Хе <д \¥е.

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

Говорят, что (всюду определенная) одноместная функция / является пределом последовательности (всюду определенных) фуикций если /3{х) = /(х) для почти всех (т.е. для всех, кроме конечного числа) й при любом значении х. В этом случае также говорят, что последовательность функций {Л^еш (поточечно) сходится к функции / (записывается как / = Пшз /3).

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

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

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

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

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

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

Теорема 17. Для любого п > 1 если \v\o = шп+1, В 6 А"1, А - в.п., В <т А ® WA, то существует такое множество D £ Е"1, где с <о v и \с\о = Шп, что В <Т D <Т AeWÁ.

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

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

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

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

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

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

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

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

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

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

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

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

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

Пусть Фо, Фх, Ф2,. - некоторая эффективная нумерация всех частично-вычислимых (ч.в.) функций, тогда . обозначает соответствующую ей эффективную нумерацию вычислимо перечислимых (в.п.) множеств. Аналогично, если Ф~д, Ф^, Ф2 , ■■■ - некоторая эффективная нумерация частично вычислимых от множества А функций, то И7^. И^'1. обозначает соответствующую ей нумерацию множеств, вычислимо перечислимых относительно множества А. Вычислимыми функциями называем ч.в. функции, область определения которых совпадает с и. Через {Оп}песи обозначаем стандартную нумерацию всех конечных подмножеств ш, т.е. £>о = 0, и если XI,., хп - различные числа из и и х — 2Х1 + . + 2х", то Дс = {^1,

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

17

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

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

Двухместная функция (х,у), определенная как (х,у) :— +3ж+у ж, у Е со, и осуществляю!цая биективное отображение и2 на ш, называется канторовской нумерующей функцией. Через /иг обозначаются однозначно определенные функции такие, что для всех х,у 6 и, (1(х),г(х)) = х, 1((х,у)) = х,г((х,у)) = у; п-местная функция (х\,. .хп) при п > 2 определяется так: (х1,. хп) — {{. (х1, Х2),Хз),., хп). Если функция / в точке х определена, то пишем /(х) в противном случае пишем /(х) Т- Область определения функции / обозначается через с1от(/), область ее значений -через гпд(/).

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

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

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

18

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

Множество А слабо-таблично сводится (или ^¿¿-сводится) к множеству В {A <wtt В), если (Зп)(\/ж)(А(ж) = Ф^(ж)), где Ф^ - некоторая вычислимая относительно В функция, и существует такая вычислимая функция /, что (\/x)(f(x) > и(В,п,х)), где и(В,п,х) - wse-функция вычисления Ф^(ж).

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

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

В).

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

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

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

А(х) = lims/(s,a;), и s: f(s,x)¿f(s + l,x)}\<n.

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

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

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

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

Sa{П) = <о a)[z е Rxke(x) ф e(a)&(Vj/ <о ж)[г g ЯД ра(к) = u~sa( тг), где е(ж) - функция чётности на О, т.е. е(ж) = 0, если а; - чётный элемент порядка ({у\у <о <о) и е(ж) = 1 в противном случае.

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

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

20

Е^-множеством, если {\/Ь <о а)(\/В е фт В).

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

Пусть £() есть предел последовательности ы, сиш". Тогда любой ординал а < Ео можно представить в нормальной форме:

О! = щ • + п2 • и32 + . + Пк- иА, (а> рг> . > /Зк, ть\,., пк < и).

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

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

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Батыршин, Ильнур Ильдарович, 2008 год

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

26. Селиванов В.Л. Об иерархии Ершова // Сиб. мат. журнал. 1985. - Т. XXVI. - №1. - С. 134-150.

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

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

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

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

31. 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.

32. 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.

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

34. 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.

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

36. 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.

37. Calude C.S., Nies A. Chaitin u numbers and strong reducibilities //J. Univ. Comp. Sci. 1998. - V.3. - P. 1162-1166.

38. 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.

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

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

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

42. 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.

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

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

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

46. 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. 289319.

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

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

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

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

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

52. 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.

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

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

55. Batyrshin I.I. Relative enumerability in the Ershov's hierarchy // Logic colloquium 2005. Book of abstracts. Athens. - 2005. - P. 49.

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

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