Свойства квази-сводимости и иерархии Ершова Батыршин Ильнур Ильдарович

Содержание к диссертации

Введение

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

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

1.2. Изолированность в Q-стеиенях 34

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

1.4. Структурные свойства Q -степеней п-в.п. множеств 67

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

Литература 100

• Q-полнота и функции без неподвижных точек
• Изолированность в Q-стеиенях
• Неизолированность в Q-степенях
• Структурные свойства Q -степеней п-в.п. множеств

Введение к работе

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

Квази-сводимость ((^-сводимость) была введена Тенненбаумом (см. [25], с.207) как один из примеров сводимости, отличающейся от Т-сводимости на классе вычислимо перечислимых множеств. Согласно этому определению, множество А квази-сводится к множеству В, если существует такая вычислимая функция Ф, что для любого х Є со выполняется: х Є А <3> W$(_x) СВ. В этом случае мы говорим, что A посредством Ф (или посредством равномерно вычислимо перечислимой (в.п.) последовательности в.п. множеств U — {U_x}_xetJ) если для всех х U_x = W$(_x)). Если A посредством Ф, мы также пишем А — Ф^в, рассматривая Ф как Q-оператор.

Q-сводимость является естественным обобщением много-одной сводимости (m-сводимости): если А <_т В посредством вычислимой функции f(x), то A посредством вычислимой функции д(х) такой, что W_g^ = {f(x)}. Также эта сводимость следующим образом связана со сводимостью по перечислимости (е-сводимостью): если A посредством вычислимой функции д(х), то ш — А <_е ш — В посредством в.п. множества W = {< x,2^v > \х Є со,у Є W_g(_x)}, т.е. (Уж)(ж Є ш - А 45- Зи(< х,и >е WhD_u С и - В)). Кроме этого, на в.п. множествах <5-^свД^им0С,1Ъ влечёт Т-сводимость, но не совпадает с ней: если некоторое в.п. множество W то W <т А, но существуют такие в.п. А, В, что А <т В, но при этом A ^q В.

Комбинаторные свойства Q-сводимости и ее различные модификации широко изучались Оманадзе [14-24]. Соловьев [29] показал, что кобесконечное

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

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

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

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

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

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

Изучение алгебраической структуры Q-степеней я-в.и. множеств было начато Арслановым и Оманадзе [36J. Они доказали, что для всех в.п. А\^Ач выполняется Лі — Ai показали, что для каждого п существует собственно д-в.п. Q-степень; построили пример 2-в.п. множества А\ — Ач такого, что для любого в.п. множества W, если /Ц — А₂ то А\ и показали, что для любого в.п. множества V = {х\Ф_х(х) 1} найдется такое 2-в.п. множество А — В, что V и Q-степень А - В не содержит в.и. множеств.

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

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

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

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

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

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

2. существует функция f _x ^ W_f(_x)) и множество

B_fiA = {x\W_g{x) С A} - в.п.

Следствие 1. В.п. множество А Q-полно тогда и только тогда, когда (Э/ _x ф ^f{x)) ^и множество Bf_tA - в.п.

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

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

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

4. существуют такие вычислимые функции а,Ь и д, что функция

^{

а(х), если а(х) Є А Ь(х), если д(х) . А,

не имеет неподвижных точек, т.е. (Vx)(W_x Ф ^/(ж)) ^и множество {х\д(х) Є А} в.п.

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

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

6. существует функция f _x ф W/(s)) и множество Bf,A является ЕЦ.

Следствие 3. Y^-множество А Е^ — Q-полно тогда и только тогда, когда (3/ _x ф W/(a;)) ^и множество Bj^a Є Е<].

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

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

8. существует функция f _x ф_т Wf(_x)) и мпожс-

ство Bf_tA является Eij.

Следствие 4. Т^-мноэюество Л Е<] — Q-полно тогда и только тогда, когда (3/ _x ^ Щ(_х)) ^и множество В^а Е.

Теорема 5. Множество /С = {(х, п)| а; є 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 сверху.

Возникает естественный вопрос: верно ли утверждение, обобщающее эти

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

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

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

Теорема 6. Для каждой пары в.п. степеней a существует собственно 2-в.п. степень d, a ; такая что а изолирует d снизу и b изолирует d сверху.

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

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

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

Теорема 7. Для каждой пары в.п. степеней, v существует такая собственно 2-в.п. степень d, что v и, и для любой в.п. степени

w, если w ; то найдется в.п. степень a такая, что a ^q w.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Предложение 12. Пусть А, В, А₀, А\ - в.п. множества, В С А, А = А₀иАі,АоПАі = Ф,Во = ВпА₀иВі=ВП А_ъ Тогда A_Q - В₀ <_Q А - В uAi-ByKqA-B.

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

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

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

Теорема 14. Пусть А - такое в.п. множество, что К ^q А. Тогда существуют такие не вычислимые в.п. мпооїсества Aq и А\, что AAq %q А 0 А\, А А\ ^.q А 0 Aq и Aq и А\ образуют минимальную пару в в.п. Q-степенях.

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

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

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

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

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

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

всех невычислимых в.п. множеств W_e существует, такое невычислимое в.п. множество Х_е, что Х_{е е e}.

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

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

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

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

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

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

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

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

Теорема 17. Для любого п > 1 если \v\o = u)^n+l, В Є A~^l, А - в.п., В <т А Ф W^A, mo существует такое мнооюество D Є Е"¹, где с <о v и \с\о = и¹¹, что В <_TD<_TAeW^A.

Следствие 13. Любая 2-GEA, А"¹ -степень является Е"¹-степенью, где \v\o = wⁿ⁺¹, с <о v и \с\о = ujⁿ (п> 1).

Сразу же возникает несколько новых естественных вопросов по поводу

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

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

10. Можно ли усилить эту теорему, сделав множество D из условия принадлежащим классу Е"¹ для некоторого а такого, что \а\о < ш^п!

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

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

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

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

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

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

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

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

же, если специально не оговорено другое, область определения и область значения являются подмножествами ш. Греческими буквами и малыми латинскими буквами обозначаются функции, большими латинскими буквами обозначаются множества и характеристические функции этих множеств, т.е. если А С о>, то А(х) обозначает следуюіцую функцию:

1, если х Є А, А(х) = I

I 0, если х $. А.

Если А С и), то А и и — А обозначают разность ш\А. Если А, В С ш, то через А — В обозначается разность А \ В, а через ті ф В - множество {2х\х Є А} У{2ж+ 1|а- Є В}. Мощность множества А обозначается через \А\. А =* В означает, что \{А-В) \J(B -А)\<оо.

Пусть Фо,Фі,Ф2, - некоторая эффективная нумерация всех частично-вычислимых (ч.в.) функций, тогда Wo, Wi, И^,... обозначает соответствующую ей эффективную нумерацию вычислимо перечислимых (в.п.) множеств. Аналогично, если Ф^Ф^, $2, - некоторая эффективная нумерация частично вычислимых от множества А функций, то Wq-, W{^A, W^,... обозначает соответствующую ей нумерацию множеств, вычислимо перечислимых относительно множества А. Вычислимыми функциями называем ч.в. функции, область определения которых совпадает с и. Через {D_n}_necJ обозначаем стандартную нумерацию всех конечных подмножеств ш, т.е. Dq — 0, и если xi,...,x_n - различные числа из ш и х = 2^Xl + ... + 2^х", то D_x = {xi,..., х_п}.

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

какую нибудь пошаговую аппроксимацию), то эта запись означает результат,

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

Запись f\x означает ограничение функции / к числам у < х. Таким образом, если Ф'^{х) определена, тогда значение ее wse-функции равно A\ip_e(A, х), и изменение А в промежутке < ір_є(А,х) разрушает это вычисление.

Двухместная функция (х,у), определенная как (х>у) :— ^(ж ₂^{+ х+у} для ж, у Є о;, и осуществляюіцая биективное отображение и² на со, называется шнгпоровской нумерующей функцией. Через /и г обозначаются однозначно определенные функции такие, что для всех х,у Є со, (1(х),г(х)) = х, 1((х,у)) = х,г((х,у)) = у) n-местная функция (х\,.. .х_п) при п > 2 определяется так: (хі,... х_п) — {{... (х\, Х2),хз), , х_п). Если функция / в точке х определена, то пишем f(x) |, в противном случае пишем f(x) |. Область определения функции / обозначается через dom(f), область ее значений -через rng(f).

Множество А С. си является полурекурсвивным (см. [42]), если существует такая вычислимая функция / : со² —» со, что для всех х, у, (i) /(^,2/) = х или f(x,y) = у,ъ (и) х Є AVy Є А-+ f(x, у) Є А.

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

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

(А <_т В), если (3n)(Vx)(A(x) = Ф^(#)), где Ф^ - некоторая вычислимая относительно В функция.

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

Множество А таблично сводится (или it-сводится) к множеству В (A <_tt В), если существуют такие вычислимые функции /ид, что (х Є А <г-> (Зу Є D_g(_x))(\/z < f(x))(x Є В <-» х Є D_y)) (эквивалентное определение через булевы функции и табличные условия см. в [25]).

Множество А много-одно сводится (или m-сводится) к множеству В (А <_т В), если существует такая вычислимая функция /, что (\/х){х єА<-> f(x) Є

В).

Множество А сводимо по перечислимости (или е-сводится) к множеству В (А <_е В), если (Зп){Ух)(х Є А ^ (Зу)((х,у) Є W_nhD_y С В)).

Множество А принадлежит классу Е (или является Е-множеством) для п > 0, если существует такое вычислимое отношение R(x,y\,y₂, .--іУп), что х <= A (3yi)(\/y₂)(3y₃)...(Qy_n)R(x_iyu...,y_n)₁ где Q является квантором 3, если п нечетно, и квантором V, если п четно. Множество А принадлежит классу П^, если ш — А принадлежит классу ТР_п. Множество А принадлежит классу Д^, если А Є и А є П.

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

/(0,я) = 0,

A(x) = \im_sf(s,x), и

]{s: f(s_tx)?f(s + l,x)}\

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

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

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

Пусть 0,<о - клиниевская система обозначений для конструктивных ординалов (подробное описание свойств ординалов, клиниевской системы обозначений и обзор результатов в этой области см. в [3]). Пусть даны а Є О и вычислимо перечислимая а-последователыюсть в.и. множеств 1Z — {R_x}x<_aa (т.е. предикат "у Є R_x" вычислимо перечислим и если х <о у, то R_x Q Ry)-Полагаем

S_a(K) = {z\(3x <о a)[z Є R_xhe{x) ф e(a)&(Vj/

P_a(K) = u~S_a(n), где e(x) - функция чётности на О, т.е. е(х) = 0, если х - чётный элемент порядка ({у\у <о а-}] <о) и е(х) = 1 в противном случае.

Обозначим через Е"¹ класс всех множеств вида S_a(7l), где ТІ пробегает все вычислимо перечислимые a-последовательности в.п. множеств, через П~ обозначим класс всех множеств вида Р_а(7). Определим А"¹ ^ П"¹ П Е~ .

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

Е^-множеством, если (V6 <о a)(WВ Є Т,^¹)(А фт В).

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

Пусть є о есть предел последовательности ш,ш^ш,ш^ш .... Тогда любой ординал а < q можно представить в нормальной форме:

а = щ и& + п₂ и³* + ... + п_к- иА, (а > / > ... > /З_к, щ,..., п_к < ш).

В частности, для а < ш^ш', а; = по а;"¹ + ... + n_m_i ш + п„_г.

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

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

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

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

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

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

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

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

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

Изучение алгебраической структуры Q-степеней я-в.и. множеств было начато Арслановым и Оманадзе [36J. Они доказали, что для всех в.п. А\ Ач выполняется Лі — Ai Q А\; показали, что для каждого п существует собственно д-в.п. Q-степень; построили пример 2-в.п. множества А\ — Ач такого, что для любого в.п. множества W, если /Ц — А2 Q W, ТО А\ Q W; и показали, что для любого в.п. множества V Q К = {х\Фх(х) 1} найдется такое 2-в.п. множество А — В, что V Q А - В Q К и Q-степень А - В не содержит в.и. множеств. Основные результаты работы опубликованы в [50-58]. Все стандартные обозначения и определения будут даны в конце введения. Перейдем к содержанию работы.

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

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

Изолированность в Q-стеиенях

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

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

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

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

В работах [31] и [34] было доказано, что если В Є Л \ С - в.п. относительно некоторого А т С и. В т С, то существует такое множество D Є Е "1, что В т D т С. Этот результат показывает, что степень п-в.п. множества, которая является вычислимо перечислимой относительно некоторой в.н. степени, лежащей ниже ее, является 2-в.п. степенью. Таким образом, относительная перечислимость на конечных уровнях иерархии Ершова уменьшает "сложность" этих уровней. Долгое время открытым оставался вопрос о том, обладает ли относительная перечислимость таким же свойством на бесконечных уровнях иерерхии Ершова. В главе 2 дается исчерпывающий ответ на этот вопрос. В теореме 17 доказывается обобщение этого свойства на классы множеств AVn, где vn(n 1) - произвольные обозначения клиниевской системы для L0n соответственно. Теорема 17. Для любого п 1 если \v\o = u)n+l, В Є A l, А - в.п., В т А Ф WA, mo существует такое мнооюество D Є Е"1, где с о v и \с\о = и11, что В TD TAeWA. Следствие 13. Любая 2-GEA, А"1 -степень является Е"1-степенью, где \v\o = wn+1, с о v и \с\о = ujn (п 1). Сразу же возникает несколько новых естественных вопросов по поводу дальнейших возможных обобщений данной теоремы: 1) Можно ли сохранить результат этой теоремы, если ослабить её условия, заменив класс множеств А"1 на более общий класс Е 1? 2) Можно ли усилить эту теорему, сделав множество D из условия принадлежащим классу Е"1 для некоторого а такого, что \а\о шп! 3) Можно ли обобщить эту теорему на более высокий уровень иерархии Ершова - на уровень А"1 для некоторого v такого, что \v\o = ыш! Теорема 18 дает отрицательный ответ на первый вопрос, ее следствие 14 -отрицательный ответ на второй вопрос, а теорема 19 - отрицательный ответ на третий вопрос. Теорема 18. Для любого п 0 если \а\о = шп, то существует собственно Е"1 -множество В, вычислимо перечислимое относительно некоторого в.п. множества А т В. Следствие 14. Для любого п 0 ес/ш \а\о = шп+1, то существует множество В Є Л"1, вычислимо перечислимое относительно некоторого в.п. множества А т В, такое, что (Ус о Ь)(УС Є Е 1)(5 фт С), где Ъ о а и \b\o = шп. Теорема 19. Пусть \v\o = сиш, тогда существует множество В Є А"1, вычислимо перечислимое относительно некоторого в.п. множества А т В, такое, что (V6 о v)(VC Є E )(J3 фТ С). Таковы основные результаты работы. Теперь скажем о некоторых определениях, сокращениях и договоренностях, используемых в дальнейшем. Множества, рассматриваемые ниже, являются подмножествами множества натуральных чисел ш = {0,1,2,..}. У функций, рассматриваемых ниже, если специально не оговорено другое, область определения и область значения являются подмножествами ш. Греческими буквами и малыми латинскими буквами обозначаются функции, большими латинскими буквами обозначаются множества и характеристические функции этих множеств, т.е. если А С о , то А(х) обозначает следуюіцую функцию:

Неизолированность в Q-степенях

Модуль V(e,i,j) имеет следующие возможные выходы: (A) Некоторый цикл к бесконечно ждет в пункте (2) или в пункте (4г), или достигает пункта (4в), или достигает пункта (5г). В этом случае или $j(xk) Т или Фі(у) , или Xk Ае4&\ф.(Хк) С We, или хк Є АЄіікШф Хк) % We, или у We&W$i(y) С (А - 2) У, или у Є е&И/ад (А - А) 0 V. хк свидетель того, что АЄЛІ CQ We посредством Ф - или у - свидетель того, что We Q (Z?i — D2) Ф V посредством ФІ; требование удовлетворено. При этом в случае (5г) мы нарушаем сводимость Ае Q (DI — D2), однако обеспечиваем We %Q (Di — D2) 0 V посредством Ф; и все равно удовлетворяем главное требование V(e4). (Б) Некоторый наименьший цикл к бесконечно переходит из пункта (46) в пункт (2). В этом случае Xk . АЄ)І и W$.(Xk) С We; требование удовлетворено. (B) Каждый цикл работает конечное число шагов, останавливаясь в пунк тах (За), (36), (Зв),(3г) или (46), и в процессе конструкции открывается бес конечно много циклов. В этом случае U Q V посредством se ij, что противоречит условиям теоремы. Взаимодействие между требованиями. упорядочим Требования {Afe,ij}e i,ju И {Ve,i,j}e,i,jeui в один ( -список {Qn}neu- QQ = Л/Ь, Qi = VQ) Q2 = M, Qs = Pi, ... Конфликт МЄЖДУ Требованиями -N"{ej.j) И A/(e/ /j ), ИЛИ Между N(e,ij) и P(e ,i j ) или межДУ Р(е,і,з) и P(e ,z j Для некоторых е, г, J-, e ,i ,f может возникнуть, если стратегия одного из этих требований на шаге (46), (4в) или (4г) работы некоторого цикла /с требует положить . вД, но гс запрещен стратегией другого из этих требований на шаге (Зв) работы некоторого цикла к (т.е. хк = пк ).

Пусть, например, М(е,г,з) требует перечислить Хк в D\ в некотором цикле к, a V jij ) запрещает это сделать, т.к. Хк совпадает с п некоторого цикла А; (остальные три случая разбираются аналогично).

Пусть (е, i,j) (е , i ,j ). Если J\f(e,i,j) требует перечислить Хк на шаге (4в) или (4г), то перечисляем Хк в D\ и инициализируем требование V(e ,i\f)- Требование Af(e,i,j) будет иметь в этом случае выход (А), и поэтому больше не будет нарушать требования с меньшим приоритетом. Если N(e,i,j) требует перечислить Хк па шаге (46), то может случиться так, что N"(e,i,j) имеет выход (Б) из-за некоторого цикла I к, и в процессе своей работы будет открывать бесконечно много циклов, которые будут требовать перечислить элементы в D\ на шаге (46). Данный конфликт решается с помощью небольшой модификации стратегии. Перечисляем Хк в D\, п если к впоследствии перечислится в С/, то ждем, когда щ перечислится в V и открываем пока цикл к + 1. Если ЭТОГО НЄ ПрОИЗОЙДеї , ТО J\f(e ij) окончательно удовлстворено Свидетелем Xk и сводимость ge ,i j требования V(e\i j ) будет нарушаться только в точке к , и т.к. существует только конечное число требований большего приоритета, то она будет нарушаться только в конечном числе точек. Если же п& перечислится В У, ТО Перечисляем Xk — Tltf В Z 2, УДОВЛеТВОряЯ требование V(e ,i ,j ) Если (e:i,j) (e ,i ,j ), и (e .i j/) имеет выход (Б), то может случиться так, что в процессе своей работы оно будет открывать бесконечно много циклов, и накладывать бесконечно много запретов. Данный конфликт решается с помощью небольшого изменения стратегии: перечисляем Xk в D\ и, если позднее к перечислится в U, то перечисляем Xk = rip в Z?2- В этом случае требование V j j ) остановится в пункте (4в) цикла к , мы будем иметь х Є Di,Zk $. (Di — D2) 0 V, и независимо от того, войдет у в множество We или не войдет, требование V j ) будет иметь выход (А), и просто инициализируем требование N(es,j)

Конструкция. Определим для требований V(e,i,j) множество точек, в которых нарушается сводимость U Q V: Me ijjS = {т Є U\3(e\ i ,j )((e ,i ,j ) (e,i)&Xeiij,m,s Vs&(m = ve/,i/j/,ifc/ V m = i Wjjfc/)}, где vse ljlk, - свидетель требования Af(e ti j ), a tsdi, jlk, - свидетель Vpfj). Определим функцию длины для требований V/ea\ : l(e,i,j,s) = max(VZ n)(l Me j s —» (/ Є v "" n s U - Xc ijj С V[s])) -1-ій функцию максимальной длины: m(e,i,j,s) = max/(e,/,.7, t). Аналогичным образом определим множество M ei s и функ t s ции / (е, /, j, s) и m (e,i,j, s) для требований J\f(e,ij) Шаг S=0. ДЛЯ ВСеХ Є, i,j,n Є О; положим Хе п,0 — e,»,n,0 = e,ij,n,0 = [/n0 = Аег-0 = )1)0 = 2,о = 0- Для каждого цикла к требования A/"(e,i.j назначаем свидетеля У к — (0, е, i} j, &), для каждого цикла к требования V(e4,j) назначаем свидетеля tQe k = (1, е,г, j, к). Фиксируем элементы й tjL U, DУи dg-Di. Шаг s+1. Для всех е,г,х s, если /x,s = 0 и х DiiS, перечисляем й в Ux,s+1, ЄСЛИ Ye,i,x,s = 0 И Ж 0 ЛЄ)г,5, ТО перечисляем J В Fe,i,a;,s+1 Для всех (e,i,j) 8 если fc = l(e,i,j,s) $ Us и пока не имеет Р-ассоциированного свидетеля, то V-ассоциируем с ним наименьший і = e.ij.fc - 1,s) больший всех участвовавших в конструкции чисел, и определяем U s+\ — {к}. Для всех (e,i,j) s если к = l (e,i,j,s) $ Us и пока не имеет ЛГ-ассоциированного свидетеля, то N-ассоциируем с ним наименьший v — vseiAk $ i,s, больший всех участвовавших в конструкции чисел, и определяем UVtS+i = {к}. Для всех e,i,j, к s если fc имеет "Р-ассоциированного свидетеля t = tSe,i,j,k & Dis, к Є Us и Xeiitjik = 0, то определяем Ut}S+i = Ut 8 {J{u}. Для всех e, г, j, A; s если А; имеет Л/"-ассоциированного свидетеля v = vl4j,k & i,s? к eUs я Zetijtk = 0, то определяем t/ +i = 4,s UW

Структурные свойства Q -степеней п-в.п. множеств

Модуль имеет следующие возможные выходы: (A) Некоторый (наименьший) цикл ко или ждет бесконечно на шаге (2), или достигает шага (За). В этом случае мы успешно удовлетворяем требование 1Zi e с помощью цикла ко. (B) В конце концов или каждый цикл к ждет бесконечно на шаге (4), ожидая изменения К (к), или останавливается на шаге (4а) или (6). В этом случае, К Q А, противоречие с условиями теоремы.

Таким образом, мы имеем выход (А), при котором успешно удовлетворяем требование 7Zi,e Единственный возможный конфликт между действиями стратегий 7х ,е для различных (г, е) может быть следующим: для некоторых г и е стратегия требования 7j,e требует положить некоторый элемент в Аг, который запрещен стратегией некоторого требования R\-ij с большим приоритетом. Однако стратегия каждого 1Z запрещает только один элемент (после этого она удовлетворена), и все требования 7t могут быть нарушены только конечное число раз.

Стратегия требования A/ e,ij является стандартной стратегией построения минимальной пары в.п. степеней с одним небольшим изменением. Стандартная стратегия: ждем, когда начальный отрезок, на котором We Q-сводится к AQ И А\ увеличится, и определяем частчично вычислимую характеристическую функцию сцг для We. После этого разрешаем изменяться только одному из множеств AQ И А\ у use-функции Q-операторов, сводящих элементы из области определения Cw Особенность Q-сводимости, которая требует внести небольшое изменение в эту основную стратегию, заключается в следующем. В случае Т-сводимости, автоматически гарантируется, что если W = Ф- = Ф-1, то для каждого х, (W(x) = Фг (х) = j1{x))[s] на почти всех (за исключением конечного числа) шагах s. Это обеспечивает, что limsup функции длины стремится к бесконечности, и что существует бесконечно много расширяющих шагов, которые могут быть использованы в конструкции. В случае же Q-сводимости, как было замечено в [39], может случиться так, что на каждом шаге s, некоторый у Є We[s], но, к примеру W $ .(y} 2 Ao[s], хотя W$.(y) С AQ. В этом случае не будет существовать бесконечно много расширяющих шагов, и limsup не будет стремиться к бесконечности. В [39] были использованы специальные технические конструкции, чтобы избежать этой трудности, но в нашем случае существует другой путь решить эту проблему: если на шаге s существует у Є We s и, к примеру, некоторый z Є 1 V$,(y) — AQ[S], просто запрещаем перечислять этот z в AQ. Таким образом, We Q AQ посредством Фу, и требование будет удовлетворено.

Конструкция. По каждым {Aoit}t s и {Ai)t}t s определим следующие функции: l((e,i,j),s) = max{x(V?/ х)(УУФіАу) С A0,s - W$jM С Au - х Є WejS)}, m((e,i,j),s) = max{l((e,ij),t)\t s}. Шаг s называется (e, i,.j)-расширяющим, если s = О или /((e,? ,j),s) m((e,i,j),s- 1). Шаг s = 0. A0fi = Aifl = 0. Определим q(l, e, 0) = 0 для Іб{0,1},еЄш. Шаг s + 1. Определим r(0, s) следующим образом. Пусть t - наибольший О-расширяющий шаг s, положим r(0,s)= у , if Зх, у(х Є W hy Є И/ф0дх) - Аол); тогда для t s У = №ІУ Є 0lt(x) - Л),г) для некоторого x Є Wo, ; О, если нет такого у, и s - O-expansionaiy; t, в ином случае. Для {e,i,j) О определим r((e,i,j),s) следующим образом. Если для некоторого t s, Зх,у(х Є WejL(y є (И ф.і(ж) - А0, ) U (W$j.t(a;) - Аи))), тогда пусть r((e,i,j),s) - наименьший такой у. В ином случае определяем r {{eihj)is) как максимум из (i) r((e,i,j) -l,s), (ii) наибольший t s, такой что r({e,i,j) — l,t) r({e,i,j) — l,s), (Hi) наибольший из (e,?, -расширяющих шагов, такой, что r((e- h j) 1}) = г ((е, г, ) — 1, s), если s не является (е, г, -расширяющим. Говорим, что 72-о,е требует внимания, если нет таких ж, у, что ж Є A))S, 2/ Є W$e(a;))S - Ам и В этих случаях говорим, что х из этих условий привлекает внимание типа (і) или (И) соответственно. Аналогично, 1Z e требует внимания, если то же самое выполняется с (0, е — 1, s) вместо (1, е — 1, s) и Ai,s вместо Л0,5. Выберем наименьший такой е s, / Є {0,1}, что 7 )Є требует внимания, и наименьшие A;, га, п для этого 7;)Є. Если имеет место случай (і), то перечисляем а; в .A/iS+i и определяем g(i, е, s+1) = g(/, е, s). Если имеет место случай (И), то перечисляем х в Ais+i и определяем q(l, е, s+1) = max{2n+l, q(l, е-1, s)}.

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

Алгебраические и структурные свойства полурешеток Роджерса в иерархии ЕршоваОспичев, Сергей Сергеевич

Структурные свойства тьюринговых степеней множеств из иерархии ЕршоваЯмалеев Марс Мансурович

Структурная иерархия нитрида бора и ее связь со свойствамиДедков, Владимир Станиславович