Содержание к диссертации
Введение
Глава 1. Методы построения минимальных степеней
1. Основные стратегии метода 17
2. Дополнения рекурсивно перечислимых степеней в нижних конусах 26
3. Дополнения произвольных степеней в нижних конусах 39
4. Дополнения в конусах, ограниченных низкими степенями 39
5. Эффективные минимальные покрытия рекурсивно-перечислимых степеней 49
Глава 2. Строгие минимальные покрытия и проблема Спектора
1. Строгие минимальные покрытия аг-р.п. степеней 71
2. Степени, не имеющих строгих минимальных покрытий 78
3. Слабо рекурсивные степени и проблема Спектора 85
4. Слабые минимальные покрытия и построение изолированной степени... 98
Глава 3. Начальные сегменты степеней. Метод вложения
1.Вложение 3-элементой решетки и ромба 105
2. Методы представления конечных решеток 111
3.Специальные виды решеток 115
4. Вложение конечных решеток 120
5. Вложение счетных порядков в тьюринговые степени 125
Глава 4. Относительная перечислимость тьюринговых степеней
1. Открытые степени 133
2. Относительная перечислимость тьюринговых степеней 148
3. Разложение р.п.степеней над заданной степенью 158
4. Построение высокой изолированной степени 162
5.0 дистрибутивности верхних полурешеток степеней ниже 0' 166
Литература 169
- Дополнения произвольных степеней в нижних конусах
- Степени, не имеющих строгих минимальных покрытий
- Методы представления конечных решеток
- Относительная перечислимость тьюринговых степеней
Введение к работе
Изучение структуры тьюринговых степеней является одной из наиболее значительных задач теории вычислимости. С самого начала зарождения этой теории, т.е. с начала 50-х годов, большое число ученых обращается к изучению структурного строения полурешетки тьюринговых степеней (или степеней неразрешимости), получая новые и новые результаты. Ряд проблем, поставленных еще в середине 50-х годов относительно распределения минимальных степеней и их покрытий, был решен сравнительно недавно, а некоторые вопросы не получили ответа и поныне. Одной из наиболее известных таких проблем, поставленной в 1956 году К.Спекто-ром, является проблема описания класса степеней, обладающих строгими минимальными покрытиями. Напомним, что степень а называется строгим минимальным покрытием (см.п.) для меньшей степени Ь, если для любой степени с из с а следует, что с Ь. Другой важной нерешенной проблемой является проблема Ейтса (С.E.M.Yates [1970]) о существовании см.п. у произвольной минимальной степени. Решение этих проблем позволило бы сделать существенный скачок в решении задачи описания начальных сегментов степеней неразрешимости.
Одной из важных предпосылок для дальнейшего продвижения в этой области является разработка автором диссертации нового метода построения минимальных степеней, который позволил соединить ряд методов, разработанных для изучения начальных сегментов степеней, с различными модификациями метода приоритета, включая метод приоритета с бесконечными нарушениями (т.е. методы уровня 0" и 0 " по классификации Р.Соара (R.Soare [1986]). Напомним кратко историю вопроса.
Первая конструкция минимальной степени принадлежит К.Спектору (C.Spector [1956]). Шенфильд (Shoenfield [1966]) ввел понятие деревьев, которое оказалось чрезвычайно полезным для формулировок и доказательств результатов о минимальных степенях и покрытиях и способствовало упрощению доказательства Спектора.
Определение. (Шенфильд [1966]). Деревом называется функция Т из множества 2 UJ (т.е. из множества конечных последовательностей из 0 и 1, называемых строками) в множество 2 ш такая, что:
1. Т(а) ІАтСа - Т(т) 4- определено Л Т(т) С Т{а).
2. Если одно значение из пары Т(а 0), Т{о 1) определено, то определено и другое,и они несравнимы (будем использовать запись Т{р 0)Т(а 1)).
Дерево Т называется полным, если функция Т определена на любой строке т.
Строка принадлежит по определению дереву Т, если либо сама строка т, либо ее некоторое расширение принадлежит области значений функции Т. Множество А лежит на дереве Т, если каждый начальный сегмент характеристической функции А лежит на Т.
Переведенное на язык деревьев, доказательство Спектора основывается на двух нижесформулированных леммах, итерационное применение которых позволяет легко получить минимальную степень (полное доказательство можно найти в книге М.М. Арсланова [1986], стр.142, или учебнике П.Одифредди [1989]).
Лемма 1. Если Т-полное рекурсивное дерево и е-произвольное число, то существует полное рекурсивное поддерево Q дерева Т, такое что для любой бесконечное ветви А, расположенной на Q, А ф фе.
Лемма 2. Пусть Т-полное дерево, и е-произвольное число. Существует такое полное поддерево Q дерева Т, что для любого А, расположенного на Q, ф -всюду определенная функция либо рекурсивна, либо А т ф.
Анализ доказательства Спектора показывает, что требуемые в леммах поддеревья Q могут быть найдены с помощью оракула 0", поэтому и построенная им минимальная степень находится ниже О". Существенным признаком этой конструкции является то, что применение оракула 0" является необходимым.
Дж.Сакс (J.Sacks [1961]), используя частичные деревья, сумел устранить использование оракула 0" и доказал существование минимальной степени ниже О . Этот метод получил название метода е-штатов. Однако метод Сакса использовал оракул О и не позволял ответить на ряд естественно возникающих вопросов. Одним из таких вопросов был вопрос о том, какие степени принадлежат замыканию множества минимальных степеней ниже О относительно операции взятия верхней грани, и в частности, является ли степень О супремумом двух минимальных степеней. Другим является вопрос, под какими степенями существуют минимальные степени. В частности, есть ли минимальные степени под каждой нерекурсивной рекурсивно-перечислимой (р.п.) степенью?
Для решения этих проблем Ейтсом (Yates [1970] и Купером (S.B.Cooper [1972]) был разработан новый метод построения минимальных степеней ниже 0 , получившый название метода полных аппроксимаций. Особенностью этого метода является полный отказ от использования оракулов и рекурсивная аппроксимация всех требуемых в конструкции вычислений. Используя новый метод, Купер показал, что степень 0 является супремумом двух минимальных степеней, а Ейтс доказал существование минимальных степеней под каждой нерекурсивной р.п. степенью.
Другими важными результатами в изучении минимальных степеней являются теоремы Сассо (L.Sasso [1974]) о существовании минимальной степени, не являющейся низкой (степень а называется низкой, если она удовлетворяет соотношению а =0 ), а также минимальной степени ниже О , не сравнимой ни с какой нетривиальной р.п. степенью. Таким образом выяснилось, что не каждая минимальная степень ниже О находится под неполной р.п. степенью.
Следующим важным шагом в описании структуры начальных сегментов полурешеток D и D( 0 ) явились вложения в них различных частично упорядоченных множеств. Первый результат такого рода принадлежит Титгемайеру (см. D. Titgemeyer [1962]), который сначало построил минимальную степень, обладающую строгим минимальным покрытием, а затем доказал, что в D вложима n-элементная цепочка как начальный сегмент для произвольного натурального числа п. Далее Сакс (Sacks [1963]) показал, что любая конечная булева решетка вложима в D как начальный сегмент, а Лахлан (A. Lachlan [1968]) доказал, что любая счетная дистрибутивная решетка с наименьшим элементом изоморфна некоторому начальному сегменту D. В доказательстве этих результатов используются так называемые униформные (uniform) или однородные ( по терминологии книги Арсланова [1986]) деревья. Описание этого метода можно найти в книге П.Одифредди [1989], гл.5.
Однако, несмотря на обилие методов, ряд проблем, касающихся минимальных степеней, оставался нерешенным. Важнейшими из них являются проблема Спектора [1956] об описании степеней, обладающих строгими минимальными покрытиями, и вопрос Ейтса [1970] о том, каждая ли минимальная степень обладает см.п. В книге (P.Odifreddi [1989], стр.527), автор сравнивает силу различных методов построения минимальных степеней и делает заключение, что существующие методы не позволяют строить минимальную степень, не обладающую см.п. Следовательно, необходимы новые методы.
Один из новых подходов, предложенных автором диссертации, явля ется изучение минимальных степеней и покрытий в рамках метода приоритета. Подробное описание этого метода, основных его идей, дается в первый параграфе диссертации. Формулировка основных определений приводится здесь не в традиционном стиле деревьев, как во всех ранее существовавших доказательствах о минимальных степенях, а в духе современного, разработанного А. Лахланом и Л. Харрингтоном подхода "дерева стратегий" к методу приоритета (подробному изложению этого подхода посвящена глава XIV книги Р.Соара (R. Soare[1986). Поскольку все современные разновидности метода приоритета, включая мощные методы уровня 0" и выше, основываются на идее "деревьев стратегий", или еще более сильном понятии "итерированных деревьев стратегий" (см. S. Lempp, М. Lerman [1997]), то такой подход обеспечивает возможность применения всей силы метода приоритета к задаче исследования тьюрин-говых степеней не только р.п. множеств, как ранее, но и произвольных степеней, объединяя традиционные оракульные методы построения степеней (метод начальных сегментов, метод кобесконечных расширений и т.д. (см. П.Одифреди [1989], гл.5) с мощными конструктивными методами, разработанными первоначально для построения р.п. степеней.В первой главе диссертации мы дадим подробное описание основных идей нового метода, доказав теорему Сакса о существовании минимальной степени О .
Использование такого подхода позволила нам решить известную проблему дополнений для рекурсивно- перечислимых степеней в нижних конусах, поставленную Эпштейном в 1979 году (Epstein[1979]).
Определение. Пусть тыоринговые степени а и Ъ удовлетворяют условию 0 а Ь. Степень с называется дополнением степени а до степени Ъ, если aUb=c и аПЬ=0. Если выполняется только первое (второе) из этих условий, то степень с называется дополнением вверх (вниз).
Наиболее важным является случай, когда верхняя степень b совпадает с 0 . Долгие исследования в этой области завершились результатами Познера и Робинсона (D.B. Posner, R.W.Robinson [1981], Posner [1981]), которые доказали, что полурешетка D( 0 ) дополняема, т.е. для каждого нетривиального элемента а найдется элемент Ь, удовлетворяющий соотношениям: aUb=0 , аПЬ=0. Недостаток этого доказательства, состоявший в том, что приводились два совершенно различных доказательства для случая, когда а являлась низкой, и когда ее скачок находился выше О , был исправлен Сетапуном и Слеменем ( D. Seetapun, Т. Slaman [1992]),
которые также показали, что дополнение можно выбрать из широкого спектра степеней, например, минимальной или 1-генерической степенью. В монографии [1979] Эпштейн (R. Epstein [1979]) выдвинул гипотезу о том, что в нижнем конусе D( а-р.п.) каждая промежуточная р.п. степень обладает минимальным дополнением, и подтвердил ее [1981] для случая, степень а является высокой, т.е. удовлетворяет соотношению а =0". Однако, в общем случае решить эту проблему ему не удалось. Сложность заключается в том, что построения ниже заданной р.п. степени (например, вложения частичных порядков) не могут проводиться методами, использующими оракулы (как, например, в теореме Слемена и Сетапуна). Здесь требуются эффективные методы, использующие рекурсивные аппроксимации заданных и конструируемых множеств и функционалов. Построения ниже высоких р.п. степеней используют идею существования некоторой быстро возрастающей функции, рекурсивной в рассматриваемой степени, которая мажорирует (с некоторого номера) каждую всюду определенную рекурсивную функцию. Общий метод таких построений описан в статье Слеймена и Шора (R. Shore, T.Slaman [1990]).
Следующий результат в этом направлении был получен в работе [1987] Купера и Эпштейна (Cooper, Epstein [1987]), которые показали, что в произвольном конусе D( а-р.п.) для каждой низкой р.п. степени b имеется несравнимая с ней минимальная степень, и, следовательно, каждая низкая степень b обладает дополнением m вниз (т.е.ЬПт=0). Однако, в общем случае проблема решается отрицательно, т.е. существует нижний конус D( а-р.п.), в котором некоторая степень Ь а не имеет дополнения (теорема 2 там же).
Усиливая этот результат, Слемен доказал (доказательство неопубли-ковано), что существует конус D( а-р.п.), в котором никакая степень Ь а не обладает дополнением. Позднее Купер (Cooper [1989]) и независимо Слемен и Стил (Slaman, Steel [1989]) доказали (оба доказательства опубликованы в одном номере журнала "The Journal of Symbolic Logic") что существует p.п. степень а такая, что в нижнем конусе D( а-р.п.) некоторая р.п. степень Ь а не дополняема вверх. Открытым остался вопрос о дополняемости минимальными степенями вниз. В работе [1986] Купер утверждает (доказательство не опубликовано), что в некотором конусе D( а-р.п.) найдется промежуточная степень Ь а (не обязательно р.п.) такая, что любая минимальная степень m лежащая ниже а находится также ниже Ь. Купер и Эпштейн (Cooper, Epstein [1987]) выдвинули гипотезу о том, что их теорема о дополняемости вниз низких степеней является наилучшим результатом в этом направлении. Эта гипотеза будет опровергнута в диссертации, и мы докажем, что для любых р.п. степеней 0 а с найдется си- р.п. минимальная степень т с, несравнимая с а. ЭТОТ результат полезно сравнить с теоремой Доуни и Стоба (R. Downey, М. Stob [1997]) о том, что в каждом нижнем конусе D( а-р.п.) найдется р.п. степень b a , не являющаяся частью минимальной пары в классе р.п. степеней (и, следовательно, также в классе п-р.п. степеней). По нашей теореме, в каждом таком нижнем конусе каждая промежуточная р.п. степень является частью минимальной пары в классе cj-p.n. степеней. Таким образом, наш результат завершает решение указанной проблемы.
Эта теорема решает также проблему Лахлана о распределении ветвящихся степеней в ограниченных сверху конусах D( а-р.п.) для степени 0 (степень а называется ветвящейся, если она является наименьшей верхней гранью двух степеней аі а а2, аіґіаг =а). Точнее говоря, по известной теореме Лахлана (A.Lachlan [1979]) степень 0 не является ветвящейся в некотором нижнем конусе D( а-р.п.) (в классе р.п. степеней). Поскольку, под каждой нерекурсивной n-р.п. степенью для п Є ш всегда найдется нерекурсивная р.п. степень, то можно заключить, что теорема Лахлана выполняется также для класса n-р.п. степеней. По нашей теореме, степень О является ветвящейся в классе иьр.п. степеней в любом нижнем конусе D( а-р.п.), и этот результат является наилучшим возможным. Таким образом, существует р.п. степень а такие, что элементарные теории р.п. степеней и о;-р.п. степеней в нижнем конусе D( а-р.п.). являются различными.
Заметим, что двойственной к упомянутой теореме Лахлана является другая его известная теорема о том, что существует неполная р.п. степень а такая, что степень 0 не расщепляема в верхнем конусе D( а). В четвертой главе (теорема IV.3.1) мы докажем, что такое расщепление можно выполнить в классе степеней, содержащих разности р.п. множеств, что также является наилучшим результатом в этом направлении. Этот же результат был независимо доказан Дингом и Квином (D.Ding, L.Qian [ta]).
Вторая глава диссертации посвящена исследованию степеней, обладающих строгими минимальными покрытиями. Еще в работе 1956 года Спектором (C.Spector [1956]) была сформулирована проблема описания класса степеней, обладающих строгими минимальными покрытиями.
Известно, что степени, являющиеся см.п., и степени, обладающие см.п., расположены достаточно близко к степени 0. Действительно, любая степень, лежащая выше 0 , по теореме Фридберга о полных степенях является скачком некоторой меньшей степени, а, значит, разложима. По релятивизованной теореме Сакса о разложении любая REA-степень (т.е. степень рекурсивно-перечислимая в некоторой меньшей степени) разложима и, следовательно, также не может быть см.п. По теореме Познера (D. Posner [1977]) каждая высокая степень перечислима в некоторой низкой степени и также не может быть см.п. Наилучшим результатом в описании степеней, не являющихся см.п. и не обладающих ими, являются результаты Доуни, Джокуша и Стоба (R. Downey, С. Jockusch, and М. Stob [1990],[1996]), описавших класс степеней, названных ими совокупно нерекурсивными (с.н.) степенями (array nonrecursive degrees).
Определение.(R. Downey, С. Jockusch, and M. Stob [1990],[1996]). Степень а является совокупно нерекурсивной, если для любой функции / wtt К, где К-креативное множество, найдется функция д, рекурсивная в а такая, что д(п) /(п) для бесконечно многих п.
Непосредственно из определения вытекает, что этот класс замкнут вверх. Авторы доказали также, что каждая степень а, не являющая GL 2-низкой (т.е. удовлетворяющая свойству а" (aUO7) ), является с.н.степенью, однако существуют также низкие и /ог -степени, являющиеся с.н. Наиболее важные теоретико-решеточные свойства этих степеней является то, что они замкнуты вверх, разложимы и дополняемы вверх к любым степеням, расположенных выше. Более сильным является утверждение, следующее из теоремы П.Фейера (Fejer [1989]), о том, что каждая рекурсивно представимая решетка с различными наименьшим и наибольшим элементами вложима в нижний конус D( a), ограниченный произвольной с.н.степенью, с сохранением наибольшего и наименьшего элементов и решеточных операций. Следовательно, никакая с.н.степень не может ни сама быть см.п., ни обладать им. В частности, все степени, обладающие см.п., принадлежат GLi-, а степени, находящиеся ниже 0 , принадлежат Li- Поэтому, все известные примеры вложений частично-упорядоченных множеств как начальных сегментов в тьюринговые степени имеют своими образами G/ -степени. В главе II мы также исследуем вопрос о распределении степеней, обладающих см.п. среди степеней, содержащих множества из иерархии Ершова ([1968],[1970а], [1970b]). Напомним, что Купер (S.B.Cooper [1971], [1995]) построил р.п. степень, обладающую см.п. Кумабе (M.Kumabe [ta]) показал существование 1-генерической степени, обладающей см.п. Мы покажем (теорема П.1.1.), что для каждого рекурсивного ординала а найдется собственная степень, содержащая множество из класса S"1, обладающая см.п.
Возвращаясь к проблеме степеней, не обладающих см.п., мы дадим прямую конструкцию низкой р.п. степени, не обладающей с.м.п ниже О . Существование таких степеней следует также неявно из вышеупомянутого результата Доуни, Джо куша и Стоба, однако они используют другую технику доказательства.
Также в этой главе мы определим новый класс степеней, названных слабо рекурсивными (weakly recursive) степенями и докажем, что каждая слабо рекурсивная степень обладает слабо рекурсивным строгим минимальным покрытием.
Определение.(Ишмухаметов [1999b]) Степень а называется слабо рекурсивной, если для любой функции f рекурсивной в а найдется слабая таблица (weak array) {Wh,(n)}%Lo такая, что для каждого п Є со :
1. \Wh{n)\ 2",
2. f(n) Є Wh{n),
3.x фу - Wh(x) П Wh{y) = 0.
Непосредственно из определения следует, что класс слабо рекурсивных степеней замкнут вниз, т.е. для любых степеней а,Ь, если а Ь и be WR, то и ає WR.
Если слабо рекурсивная степень а находится ниже 0 , то каждая функция /, рекурсивная в а, является w-p.n., т.е. имеет рекурсивную аппроксимацию f(s,n) такую, что для каждого n {/(s,n) : s Є u }\ 2n. Поскольку произвольная p.п. степень а является ш-р.п. тогда и только тогда, когда а не является совокупно нерекурсивной (Downey, Jockusch, and Stob [1990]), то непосредственно получаем, что класс рекурсивно перечислимых слабо рекурсивных степеней является дополнением множества совокупно нерекурсивно р.п. степеней в классе всех р.п. степеней R. Следовательно, наша теорема дает решение упомянутой выше проблеме Спектора для класса р.п. степеней R. Мы перечислим определимые свойства слабо рекурсивных р.п. степеней в следующем предложении:
Предложение. ловия являются эквивалентными:
(1) а-слабо рекурсивна,
(2) а-не является совокупно нерекурсивной,
(3) Любая степень b, Ь а обладает строгим минимальным покрытием,
(4) Существует Ь а, не являющая наименьшей верхней гранью минимальной пары степеней (в множестве всех степеней) (Downey [1993], теорема 1.1),
(5) Существует неразложимая степень Ь а.
Поскольку слабо рекурсивные степени замкнуты вниз, то мы получаем определимый класс минимальных степеней, обладающих см.п., именно, класс минимальных степеней, ограниченных сверху слабо рекурсивными р.п. степенями. Действительно, р.п. степени R определимы в D по известному результату Купера (Cooper [1995]), а слабо рекурсивные степени определимы в D по нашей теореме.
Применяя нашу теорему к степени 0, а затем итерируя ее, мы получим возрастающую последовательность степеней, в которой каждая последующая является строгим минимальным покрытием для предыдущей, и значит, для любого конечного линейного порядка L найдется начальный сегмент в D, изоморфный L, состоящий из слабо рекурсивных степеней (Титгемайер [1962]).
Одновременно мы дадим частичный ответ на вопрос Доуни, Джокуша и Стоба (R. Downey, С. Jockusch, М. Stob [1996] об определимости совокупно нерекурсивных степеней, показав, что совокупно нерекурсивные р.п. степени определимы в D (по любому из свойств, перечисленных в п.п. 1-5 вышеприведенного предложения).
В следующем параграфе мы рассмотрим слабые минимальные покрытия р.п. степеней. Понятие слабого покрытия было введено Купером и Уаем (Cooper, Yi [1995]).
Определение. Степень а называется изолированной, если она не является верхней гранью никакой последовательности степеней, находящихся строго ниже а.
Очевидно, строгие минимальные покрытия обладают свойством изолированности. В работе [1995] Купер и Уай ослабили это определение, назвав изолированными степени, не являющие верхними гранями последовательностей, состоящих только из р.п. степеней. В упомянутой работе они доказали существование изолированной степени, содержащей разности р. п. множеств.
В дальнейшем, степени, содержащие разности р.п.множеств, будем называть р.р.п. степенями. Степень а из теоремы Купера и Уая является верхней гранью всех р.п. степеней, находящихся строго ниже степени d. Такие степени авторы назвали изолирующими.
Возникает вопрос, а может ли изолирующая р.п. степень быть верхней гранью не только для всех р.п. степеней, находящихся ниже а, но но и верхней гранью для всех степеней из более широкого класса р.р.п. степеней находящихся ниже а? Ответ на этот вопрос содержится в следующих двух теоремах.
Теорема. (Ишмухаметов [1990]). Любая нерекурсивная р.п. степень является верхней гранью двух не р.п. р.р.п. степеней.
Теорема .111.1.3. (Ишмухаметов [1986], Купер и Уай [1995]). Для любой степени d, содержащая разности р.п. множеств, и р.п. степень a, a d, найдется р.р.п. степень Ъ, a b d.
Заметим, что существование изолированной р.р.п. степени следует также из более раннего результата Кадах (D. Kaddah [1993],теорема 3.2), которая доказала, что каждая низкая р.п. степень является нижней гранью двух р.п. степеней (т.е. является ветвящейся в классе р.р.п. степеней), а по результату Фейера (P.Fejer [1982]) не каждая низкая р.п. степень является ветвящейся в классе р.п. степеней. Дальнейшее изучение р.р.п. степеней производится в IV главе диссертации.
Третья глава диссертации посвящена изучению начальных сегментов тьюринговых степеней ниже О . В этой главе используя наш метод построения минимальных степеней и минимальных покрытий мы дадим новые доказательства теорем о вложениях различных конечных порядков в тьюринговые степени. Используя метод деревьев стратегий, наш метод позволил получить значительное упрощение этих технически сложных доказательств. Мы передокажем теоремы Сакса и Титгемайера о вложениях в D( 0 ) ромба и возрастающей линейной цепи, недистрибутивной решетки ]\Г5 и произвольной конечной решетки, имеющей конечную репрезентационную таблицу.
В пятом параграфе этой главы мы рассмотрим вопрос о вложении в D счетных линейных порядков. Пусть L - произвольная верхняя полурешетка. При ее вложении в D в качестве начального сегмента строится нижний конус каждого элемента а Є L в некоторое множество А, представляющее тьюринговую степень, являющуюся образом элемента а. Спрашивается, а какова степень представления этого изоморфизма? Иначе говоря, если для для элементов a,b Є L выполняется а Ь, то как трудно найти алгоритм, сводящий соответствующее множество А к соответствующему В? В частности, если структура L вычислима, то можно ли найти сводящие алгоритмы рекурсивно? Эта проблема ранее не исследовалась, но неявно считалось, что ответ должен быть положительным. В параграфе 5 мы доказывает теорему, опровергающую в сильной форме, это мнение:
Теорема III.5.1.Пусть Р={со С! Сг ••• 0}-униформная в 0 последовательность степеней. Найдется ненулевая степень с, находящаяся ниже каждой степени cn, new.
Непосредственно из этой теоремы вытекает, что если обратный линейный порядок и — {1 2 3 ... 0} изоморфен начальному сегменту Т-степеней I, то структура I не может быть униформной (в 0 ), т.е. нельзя найти сводящие алгоритмы, даже используя оракул О .
Этот результат оказался настолько неожиданым, что многие ученые, работающие в этой области, не могли сразу поверить в его корректность.
В заключительной IV главе диссертации мы производим общее исследование проблемы относительной перечислимости одних степеней относительно других. Изучается класс Т-степеней, содержащих разности р.п. множеств. Все доказательства, приводимые в этой главе, используют фундаментальное понятие ассоциативного множества, введенное первоначально, по-всей видимости, Ю.Л.Ершовым, в работах[1968а,Ь], [1970] при исследовании индексных множеств конечных семейств р.п. множеств.
Определение. Пусть D - р.р.п. множество, и задано его некоторое перечисление. Ассоциативным множеством B[D] (относительно заданного перечисления) называется множество таких s, что некоторый элемент х перечислен в D на шаге s, но х ф D (т.е. х позднее изымается из D).
Мы доказываем в параграфе 1 предложение IV. 1.1. о том, что степень ассоциативного множества инвариантна относительно выбора перечисления разности р.п. множеств D и фактически является наименьшей р.п. степенью, в которой D перечислима.
Другим важным является вопрос о распределении изолированных р.р.п. степеней. Отвечая на вопрос, поставленный Купером и Уаем, Ля Форте (LaForte [1995]) доказал существование изолированной р.р.п. степени в интервале между любыми двумя р.п. степенями. Отвечая на другой вопрос Купера и Уая, Арсланов, Лемпп и Шор (М. Arslanov, S. Lempp, R.Shore [1996], теорема 3.2), доказали, что существует нерекурсивная р.п. степень, не являющаяся изолирующей ни для какой REA-степени.
В диссертации мы дадим новое доказательство теоремы Купера и Уая о существовании изолированных р.р.п. степени. Наше доказательство, использующее идею ассоциативного множества для разности р.п. множеств, значительно проще оригинального доказательства Купера и Уая. Непосредственно из определения ассоцитивного множества В следует, что оно рекурсивно в р.р.п. множестве D, для которого оно определено, и D перечислимо в В. Вместе с тем мы покажем (теорема IV.2.1), что существует степень d, содержащая р.р.п.множества Di, D2, ассоциативные множества которых тьюрингово несравнимы.
Основная проблема состоит в том, чтобы найти условия, когда для данных степеней end, c d, верхняя степень d перечислима в нижней степени с. Замечательный результат, характеризующих пары таких степеней, был получен Купером (Cooper [1990]):
Степень d относительно перечислима в степени с, тогда и только тогда, когда для любых степеней а и b больших с, dUa разложима над а обходя b (т.е. существуют такие степени di и d2 над с, что dUa=diUd2, и d dbd d2.
Теорема Купера дает ответ на давний вопрос, поставленный еще Постом, об определимости операции скачка в терминах тьюрингового упорядочения степеней т Известно, что для произвольной степени с существует наибольшая степень, перечислимая относительно с, именно, степень d, являющаяся скачком степени с. Естественными являются следующие вопросы: можно ли для данной степени d найти наименьшую степень с, относительно которой d перечислима? Если степень d перечислима в степени с, то можно ли найти степень а с, в которой d будет также перечислима?
В работе [1984] Джокуш и Шор (С. Jockusch, R. Shore [1984]) определили иерархию REA-степеней. 0-REA и 1-REA- это соответственно классы рекурсивных и р.п. степеней. n+l-REA-это степени, перечислимые относительно меньших n-REA-степеней. Авторами были исследованы классы этой иерархии и связь ее с иерархией степеней, содержащих булевы комбинации р.п.множеств (иерархией Ершова, см. [1968а],[19686], [1970]). Для произвольного рекурсивного ординала а будем называть степень а собственной а-р.п. степенью, если а содержит а-р.п.множество и не содержит /9-р.п. множеств ни для какого /? а. Очевидно, что в классах 0-REA и l-REA-степеней для каждой степени d найдется наименьшая степень, относительно которых d перечислима, а именно, степень О. Рассмотрим первый нетривиальный класс 2-11ЕА-степеней. Известно, что все р.р.п. степени являютя 2-REA, и, как доказано Джокушем и Шором в [1984], этот класс содержит собственые а-р.п. степени для каждого рекурсивного ординала а. Для произвольной степени d определим классы R[d] и Q[d\ как классы степеней, состоящих соответственно из р.п. степеней и всех степеней, относительно которых d перечислима. Вышеприведенные вопросы можно переформулировать следующим образом:
Имеют ли классы R[d] и Q[d] наименьший элемент, минимальные элементы? Ограничены ли они снизу ненулевыми элементами? Ответы на эти вопросы даются в теоремах IV.2.1, IV.3.1 и IV.3.2. Мы покажем, что существует р.р.п. степень d, для которой класс R[d] представляет собой верхний конус D( a). Элемент а будем называть базой этого конуса. Мы построим также р.р.п. степень d, у которой класс R[d] не имеет наименьшего элемента. В теореме IV.3.2. исследуя класс всех степеней относительно которых данная REA-степень d перечислима, мы покажем, что класс Q[d] для такой степени d не может иметь наименьшего элемента, если только d не р.п., и более того, не ограничен снизу никакой ненулевой степенью.
В теореме IV.1.2 приводится необычной пример р.р.п. степени d, для который класс 72[d]nD( d) состоит в точности из одного элемента.
В следующем параграфе мы изучаем проблему разложимости р.п. степеней. Под разложением ненулевой степени d мы понимаем представление d=diUd2, где di и d2 - меньшие несравнимые степени. В общем виде эта проблема была решена Купером [1992], который показал, обобщая теорему Сакса о разложении, что каждая п- р.п. степень для п 2, разложима на две меньшие п- р.п. степени.
В своей известной работе [1975] Лахлан показал, что степень О не разложима в классе р.п. степеней над некоторой неполной р.п. степенью а. Встает вопрос, а можно ли это сделать в каком-нибудь более широком классе? Первый результат в решении этой проблемы был получен М.М. Арслановым [1987], который доказал разложение степени 0 в классе ш-р.п. степеней. В результат в этом направлении, разложив 0 в классе 2-р.п. степеней.
В следующем параграфе мы докажем, что существует изолированная пара, состоящая из высокой р.р.п. степени и низкой р.п. степени. Этим мы ответим на один вопрос Купера и Уи, а также на вопрос, поставленный Гуохуа By (Huohua Wu, New Zealand). Пара, состоящая из высокой р.р.п. степени и low2- р.п. степени, была построена предварительно Гуохуа By, но затем Ишмухаметову удалось улучшить этот результат, и совместный результат был опубликован в журнале Archive for Mathematical Logic (Ishmukhametov, Wu [2002b]).
Наконец, в последнем параграфе диссертации мы рассмотрим вопрос о дистрибутивности верхних полурешеток степеней, образованных степенями по различным сводимостям, изучавшимся в теории вычислимости. Пусть г- произвольная сводимость. Обозначим через D полурешетку р.р.п. г- степеней. В четвертом параграфе третьей главы мы исследуем эту полурешетку на предмет дистрибутивности для различных сводимос-тей г. Мы покажем, что в отличии от случая р.п. степеней структура D является недистрибутивной для широкого класса сводимостей, промежуточных между bd-сводимостью (определение можно найти в книге Одиф-редди [1989]) и тьюринговой сводимостью. В этот класс попадают все табличные сводимости и часть строгих сводимостей. Это дает еще одно элементарное отличие полурешеток Dj и D.
Дополнения произвольных степеней в нижних конусах
В этом разделе мы докажем еще одну теорему, обобщающую упомянутую в прошлом разделе теорему Купера-Эпштейна. Согласно результату предыдущего параграфа, в произвольном нижнем конусе D( с-р.п.) каждая промежуточная р.п. степень а обладает минимальным дополнением. Условие а-р.п. является существенным и его нельзя ослабить, так как по результату Купера [1989] существует такая р.п. нерекурсивная степень с и промежуточная степень а, что любая минимальная степень, находящаяся ниже с, будет находиться также ниже а. Мы докажем, однако, что существует р.п. нерекурсивная степень с такая, что в нижнем конусе D( с) каждая промежуточная степень обладает минимальным дополнением вниз. Мы сможем доказать, что степень а может быть выбрана низкой. любой степени а,0 а с, найдется минимальная степень т с, несравнимая с а. Доказательство. Мы будем строить по шагам нерекурсивное р.п. множество С, удовлетворяющее условию С =т0 , и для каждого натурального числа к множество Мк т С, так, чтобы если Ак = Ф]? является всюду определенным, и С т Ак, тогда степень Мк будет минимальной и несравнимой со степенью множества Ак где {в Ф } - геделевская нумерация всевозможных пар частично-рекурсивных функционалов. Условия типа R необходимы для того, что степень множества С была низкой. Заметим, что мы не записали в этом списке условий, требующих нерекурсивноти
С, так как нерекурсивность множества С следует автоматически из нерекурсивности множеств Мк Разобьем каждое глобальное условие Л; на счетное число следующих подусловий: где ч.р.ф. Ге и Ае, є Є ш, строятся в ходе конструкции. Кроме того, для каждого г Є и мы будем строить рекурсивный функционал Slf, сводящий М{ к С. На нулевом шаге конструкции для каждой пары натуральных чисел г,у мы определим число witi(y), равным 2 (і, у), где (г, у)- номер пары (г, у) в канонической нумерации всех пар натуральных чисел. Определим исходные значения функционалов Sly (у) равными 0 с use-функцией uii{y) = witi(y)+l. Если в дальнейшем нам потребуется изменить значение Mj(y), то одновременно мы будем класть в С число wit{(y) и переопределять значение Sly (у) равным новому значению М»(у). Поскольку одновременно с Sly (у) инициализируются также все Sl (u) такие, что (г, у) 0,и), то переопределим их также равными соответствующему значению Mj(u) с новой use-функцией witj(u) + 1. Значения witj(u) переопределим так, чтобы сохранялся тот же порядок, т.е. если (к, v) (j,u), то witk(v) witj(u). Если мы сможем доказать, что для каждой пары {г, у) значение Mi(y) меняется конечное число раз, то и соответствующее значение Clf (у) будет инициализироваться не более, чем конечное число раз, и функционалы fif будут всюду определен. Основной модуль для негативных условий N остается без изменения. По-прежнему эти условия могут иметь два возможных исхода, конечный 1 и бесконечный 0, которые вносятся в дерево исходов Т. Основной модуль для условия Rk является стандартным. Именно, каждый раз когда значение Ф (&) сходится с новым большим use- значением фк(к), мы создаем Rk- ограничение, запрещающее класть в С числа из интервала, ограниченного фк(к). Далее, если мы докажем, что найдется некоторая стратегия для Rk, инизиализируемая не более, чем конечное число раз, то условие . будет выполнено. Основной модуль для условия типа Р состоит из списка процедур, каждая из который определяет одно значение функционала ЕДтг), сводящего С к АІ. Поскольку разница между основным модулем для изолированного условия Р от основного модуля для условия Р, находящегося ниже негативного условия N отличается только в способе выбора свидетелей, то рассмотрим сразу последний. Выберем произвольные значения г, е и п, и рассмотрим инструкции для процедуры (п), обслуживающей условие Рі е: 1. Ждем появления кандидата (т ,т ) условия N, точка разветвления которого zn превышает длины свидетелей процедур с меньшим номером и wit(zn) п. Назначим его свидетелем процедуры (п). 2. Ждем шага s такого, что 0 {(у) і для всех у г. После этого идем к шагу 3 и рассмотрим два случая: 3. Случай ЗА. МІ\ гп + 1фв I zn + l ( ). Напомним, что по определению Ai = Фр так, что для того, чтобы сохранить неравенство ( ), необходимо закрепить М, \ zn + 1 и С \ "4 i(Qe(zn + 1))- Перейдем к пункту 6, где устанавливается соответствующее ограничение. Случай ЗВ. Mi \ (zn + 1) = 9 \ (zn + 1). Проверим следующее условие:
Степени, не имеющих строгих минимальных покрытий
Известно, что степени, обладающие см.п., расположены близко к степени 0. Как уже упоминалось раньше, по теореме Джокуша таковыми могут являться только степени, принадлежащие классу GL2 (степень ає GL2, если a" = (aUO ) )). Однако, эта оценка является достаточно грубой, поскольку существуют низкие степени, не имеющие см.п. В этом разделе мы покажем, используяю 0" -приоритетную конструкцию, что найдется низкая р.п. степень, не имеющая см.п. ниже О . Пусть Х-креативное множество. Зафиксируем его некоторое перечисление. В нашей конструкции мы будем иметь дело с рекурсивными аппроксимациями AQ-МНОЖЄСТВ А, определенной по функционалу сводящему А к множеству К. Дадим несколько дополнительных определений. Пусть А — Фе(К), и A(s,x) = Фе (К8;х). Здесь функция A(s,x) не обязательно является общерекурсивной. Определение. Будем говорить, значение As(x) меняется на шаге s, если A(s,x) определено, и A(s,x) ф A(t, х), где t s - наибольший шаг такой, что А\х) . Обозначим через prA(s, х) наибольший t s такой, что A(t, х) меняется на шаге t, если такой t существует, и 0, в противном случае. Теорема II.2.1.Существует низкая р.п. степень а, не имеющая см.п. ниже О . Доказательство. Мы будем строить низкое р.п. множество А так, что для любого Ац-множества Ке, если Ке .т А, то найдется множество Ме т А@Ке, Т-несравнимое с А. Установим следующий набор приоритетных условий: где {Фє, Фе, 9е}еєш-рекурсивная нумерация всевозможных троек ч.р. функционалов, if-креативное множество. Каждое глобальное условие Ле мы разобьем на счетную совокупность локальных подусловий : Ниже мы опишем основные модули для каждого типа условий : Основной модуль для условия типа Р является обычной стратегией Фридберга-Мучника: (1) Выбираем свидетель х. (2) Ждем, когда в (а;) 4= 0. (3) Перечислим х в А. Основной модуль для условия Sij также является стандартным : (1) Ждем, когда ФгЛ(; ) і. (2) Ограничиваем А до аргумента ф(з). (3) Ждем когда снова Ф (j) t", затем возвращаемся к пункту 1. Модуль для условия Rej состоит из списка процедур. Процедура (0) стартует первой. Каждая последующая процедура (n + 1) запускается процедурой. Рассмотрим инструкции для процедуры (n) : (1) Выбираем кандидат уп для А я xn max{n, yn,pr -e(s,n)} для Ме. (2) Ждем, когда установится равенство Ме\хп + \ = Фгл \хп + \. Если Ке(п) изменится раньше, инициализируем свидетели и вернемся к шагу 1. Иначе, определим, Ел(п) = Ке(п) с use-функцией т(п) — max{yn, ф(хп)}. Стартуем процедуру п+ 1. (3) Ждем изменения Ке{п) или А Ї о(п) .
После этого останавливаем процедуры п. Если выполняется второй случай, вернемся к шагу 2, иначе перейдем к следующему шагу. (4) Изменим Ме(хп). Прежде, чем продолжить инструкции, приведем некоторые комментарии. Эта стратегия вносит свой фрагмент в общее построение множества Ме(хп), рекурсивного в Ке(п). Перечисление свидетеля хп в Ме на шаге 4 этого модуля предваряется изменением Ке(хп). Обеспечение сводимости Ме(хп) т Ке(хп) является глобальной задачей и имеет абсолютный приоритет. Множество Ке в нашей теореме не является р.п. и значение Ке(п) может меняться конечное (а для некоторых е и бесконечное) число раз. Если на последующем шаге значение Ке{п) вернется обратно, то мы должны вернуть назад и значение Ке(хп), чтобы обеспечить глобальное условие. Если позднее Ке(п) изменится еще, то опять мы должны изменить и Ме(хп). Будем говорить, что значение Ме(хп) связано с Ке(п). (5) Ждем возвращения значения Ке(п). После чего возвращаем Ме(хп), и запускаем приостановленные процедуры. Возвращаемся к пункту 3. Каждая процедура определяет одно значение ч.р.ф. Л(п) = Ке(п). Если функция Ке является всюду определенной, и процедура (п) не сможет удовлетворить Rej, тогда Ke(n) = ЕЛ(п). Если ни одна из процедур не может удовлетворить Rei, то либо Ке является частичным множеством, либо Ке т А посредством всюду определенного функционала Е, и тогда глобальное условие Ле будет удовлетворено. Итак, эта стратегия обеспечивает выполнение условия Rej конечным или бесконечным образом. Однако, неконтролируемая связь между значениями Ме(хп) и Ке(п) может служить препятствием для выполнения негативных условий Qej, поэтому для обеспечения этих условий добавим к основному модулю для Rej следующий пункт : (5) Если позднее уп будет перечислен в А, разорвем связь между Ке(п) и Ме(хп) и прекратим изменять Ме(хп) одновременно с Ке(п). Вернемся после этого опять к пункту 1, и начнем выполнение этой процедуры заново. Будем называть число уп "киллером"ассоциации Ке(п) - Ме{хп). Рассотрим теперь основной модуль для условия Qe,j- Пусть к — (e,j) (1) Выбираем свидетель z. (2) Ждем, когда выполнится А \ [z + 1) = Ф (Ме) f (z + 1). Рассмотрим два случая : Случай А. Нет ни одного значения Me(xn),xn ip(z), ассоциированного с каким-нибудь значением Ke(n), п Є u . Перечислим z в А, и ограничим Ме до аргумента ф(г). Случай В. Существуют значения Me(xn),xn ip(z), ассоциированные со значениями Ke(n), п Є со. Перечислим в А те " киллеры "уп для xn ip(z), которые не ограничены условиями с более высоким приоритетом, разорвем соответствующие связи, затем перечислим элемент z в А и ограничим Ме до аргумента ip(z). Если запрет на Ме \ i {z) будет позднее нарушен (а это произойдет, если мы не сможем разорвать все связи), то инициализируем модуль и начнем его выполнение заново. При выполнении последнего раздела следует уточнить, что мы понимаем под ограничениями условий с большим приоритетом. Во-первых, таковыми являются условия типа Si m (г, т) к. Их конечное число, и
Методы представления конечных решеток
В этом параграфе мы опишем основные типы решеток, дадим несколько определений. Полную теорию алгебраических структур можно найти в книге Скорнякова[1983]. Определение. Множество называется частично упорядоченным, если оно непусто и на нем зафиксирован некоторый порядок, т.е отношение удовлетворяющее свойствам: 1) рефлексивности: а аУа Є Р. 2) транзитивности: (а й)&(6 с) — (а с). 3) антисимметричности: (а Ь)&(Ь а) (а = Ь). Определение. Частично упорядоченное множество называется решёткой, если каждое его двухэлементное подмножество обладает как точной верхней (sup), так и точной нижней гранью (inf). Решетка называется конечной, если она имеет наибольший и наименьший элементы. Решетку можно рассматривать как универсальную булеву алгебру с двумя бинарными операциями: Вложения решеток рассматриваются отдельно для случая дистрибутивных решеток и для случая недистрибутивных решеток. Собственно говоря, представление недистрибутивной решетки бесконечно, и требует аппроксимации. Поэтому следущее определение очень важно. Определение. Решетка L - дистрибутивна, если для Va, b,c Є L выполняются: Определение. Решетка L - модулярна, если для Va, b,c Є L : a с, справедлив модулярный закон: (а V Ь) Л с = a V (b Л с). Определение. Решетка L с нулем и единицей называется решеткой с дополнениями, если для Va Є L 36 Є L : (a V b = l)&(a Л Ь = 0). Определение. Булева алгебра - дистрибутивная решетка с дополнениями. Теорема (Стоуна). Конечная булева алгебра изоморфна решетке всех подмножеств некоторого конечного множества. Примеры (конечных решеток) 1) дистрибутивные решетки 5-элементная модулярная недистрибутивная решетка М3 Методы представления решеток. Чтобы строить начальные сегменты, изоморфные более сложным решеткам, нам нужно иметь таблицу представления для таких решеток. Понятие таблицы представления было вперыве введено Томасоном (Тота-son) [1970] и Лерманом (Lerman) [1971], и широко использовано Лахланом (Lachlan) и Томасоном [1976], Лерманом [1983]. Таблица представления для решетки L является способом представления изоморфизма решетки L на решетку Eq(A) отношений эквивалентности над некоторым индексном множеством А. Существует два метода представления решеток: алгебраический и вычислительный (рекурсивный). Их наиболее исчерпывающее описание можно найти в статье П.Фейера (P.Fejer) [1998], где оба метода описаны достаточно детально, и связи между этими типами представления демонстрируются на простых а) (а = Ь). Определение.
Частично упорядоченное множество называется решёткой, если каждое его двухэлементное подмножество обладает как точной верхней (sup), так и точной нижней гранью (inf). Решетка называется конечной, если она имеет наибольший и наименьший элементы. Решетку можно рассматривать как универсальную булеву алгебру с двумя бинарными операциями: Вложения решеток рассматриваются отдельно для случая дистрибутивных решеток и для случая недистрибутивных решеток. Собственно говоря, представление недистрибутивной решетки бесконечно, и требует аппроксимации. Поэтому следущее определение очень важно. Определение. Решетка L - дистрибутивна, если для Va, b,c Є L выполняются: Определение. Решетка L - модулярна, если для Va, b,c Є L : a с, справедлив модулярный закон: (а V Ь) Л с = a V (b Л с). Определение. Решетка L с нулем и единицей называется решеткой с дополнениями, если для Va Є L 36 Є L : (a V b = l)&(a Л Ь = 0). Определение. Булева алгебра - дистрибутивная решетка с дополнениями. Теорема (Стоуна). Конечная булева алгебра изоморфна решетке всех подмножеств некоторого конечного множества. Примеры (конечных решеток) 1) дистрибутивные решетки 5-элементная модулярная недистрибутивная
Относительная перечислимость тьюринговых степеней
Пуст D - р.р.п. множество, и задана его рекурсивная аппроксимация {Ds}. Ds(x) является текущей гипотезой (на шаге s) значения D(x). Мы предполагаем, что для каждого х D(x) = 0, и существует не более двух различных s таких, что Ds(x) ф Ds+1(x). Предположим также, что для каждого s найдется не более одного х такого, что Ds(x) Ф Ds+1(x). Обозначим через [D] множество таких х, что найдется s, Ds(x) — 1, и через s(x) - шаг, на котором х попадает в [D]. Определение B[D] = {s(x) : х Є [D] — D} - ассоциативное множество для D. Из результатов предыдущего раздела мы знаем, что множество B[D] - р.п., рекурсивно вДи степень В является наименьшей р.п. степенью, в которой D - р.п. Ниже мы покажем, что последнее не может верным в классе всех р.р.п. множество из степени множества D. Теорема IV.2.1. Существует р.р.п. степень d, для которой класс R[d] не имеет наименьшего элемента. Доказательство. Мы построим р.р.п.множества D и {_De}ea, такие, что если D Т-эквивалентно 2-REA множеству А И л, тогда De =т D, и А 2;т Ве, где Ве - ассоциативное множество для De. Установим следующий набор приоритетных условий: где е = m, n,k,i , A = Wi, { j, Wj}jeul - геделевская нумерация всех ч.р. функционалов и р.п. множеств. Определим следующие функции длин (аппроксимации всех множеств, участвующих в определении, берутся в конце шага s — 1): /(е, а) = max{x : (Vy x)D(y) = фЦ т (у) A (A WkA) \ т у = Ф \ т у where т = ma,x{Ty,use{WkA \ ту}}, l(e,j, s) = max{x : (Vy x) A(y) = Ф (у)}, где є = m,n,k,i , A = Wi. Будем полагать, что значения всех параметров вычислений, рассматриваемые на шаге s, не превышают 5. Мы начнем с описания базисного модуля для условия Nej: Базисный модуль для Nej: (1) Выберем пару х,х + 1 свободных свидетелей. (2) Ждем шага s , l(e,s ) х + 1, после чего перечислим х в оба множества D и De.
Ограничим начальный сегмент D длины s . (3) Ждем шага s" s , на котором l(e,s") х + 1. Ограничим начальный сегмент D длины s". (4) Ждем шага s ", на котором l(e,j, s ") s". Изымем х из D, перечислим г + 1в Д , и ограничим начальный сегмент Ве длины s ". Определим De(y) для всех у, не являющихся условий Nej j Є ш, равными D(y). Ясно, что каждая стратегия для Nej действует конечное число раз и ограничивает конечный интервал, так что взаимодействие стратегий для различных Nej организуется обычным образом в приоритетной конструкции с конечными нарушениями. Проверим базисный модуль. Доказательство. Зафиксируем k = e,j и предположим, что лемма выполняется для всех к к. Предположим также, что левая часть условия Nej выполняется, и s0 - наименьший шаг, после которого условия большего приоритета, не нарушают работу стратегии для Nej. Пусть ЇИІ + 1- свидетели Nej, определенные после шага SQ. Така как liminf l(e, s) = со, каждый шаг 1,2 и 3 базисного модуля имеет место. Если условие Nej не выполнится, тогда liminf l(e,j, s) — со, и условие шага 4 также выполнится. помещаем х в V, а затем изымаем его оттуда, Фт (х) последовательно принимает значение 0,1,0. Это означает, что А Wj? \ гх меняется между шагами s и s , [тх - use-значение вычисления Фт (х) на шаге s ) и после шага s" возвращает свое старое значение, поскольку Ф \ т возвращает свое старое значение после извлечения х из D. Поэтому, найдется некоторое z тх, такое, что А ф W (z) меняется между шагами s и s", и затем возвращается к прежнему значению. Так, как А р.п. и не может меняться дважды, то меняется Wj (z ) для z — [z — 1)/2. Если исходное значение W (z ) было равно 1, тогда изменение Wj (z ) возможно только, если меняется А I т . Но А \ т равно Ф \ т на шагах s и s " и не может меняться между шагами s и s ". Поэтому, исходное значение W (z ) равно 0,иг был перечислен в W между шагами s и s". Для того, что вернуть значение W (z ), равное 0, необходимо изменить оракул А \ s", и выполняется ( ). Так, как А \ s = Ф е \ s" на шаге s ", после изменения А \ s", возникает неравенство А \ s" ф Ф е \ s", и условие Nej удовлетворено. Лемма доказана. Доказательство. Предположим, что іиж + І выбраны свидетелями условия Nej.
Дождемся шага s , на котором значение /(е, s) превысит х + 1. На шаге s , либо х будет перечислен в множества D и De, или же он ограничен требованием с большим приоритетом. В последнем случае, ни х, ни х + 1 никогда не попадут в D и De. Предположим, что выполнена первая возможность, и х был положен в оба D и De. По конструкции, если х когда-нибудь будет изъят из D, х + 1 будет перечислен в De. Значит, xgD H-x + lE De. Доказательство теоремы следует из лемм. Теперь мы будем исследовать для заданной Д -степени d 0, класс Q[d] степеней, ниже d, в которых d перечислима. Наш основной результат, касающихся таких классов, мы разобьем на две части. Сначало мы покажем, что для каждой р.р.п. степени d и любой р.п. степени a d найдется cJ-p.n. степень с такая, что d=c-REA, и а с. Затем мы обобщим этот результат на произвольные REA-степени ниже О Пусть D - р.р.п. множество. Выберем и зафиксируем рекурсивную аппроксимацию D, и пусть B[D] - ассоциативное р.п. множество для D. По прежнему, s(x) обозначает шаг, на котором х попадает в [D]. Определение. Элемент х Є D называется минимальным (относительно выбранной аппроксимации D), если Обозначим через M[.D] множество минимальных элементов D. По определению, M[D] С D. Лемма. Для любого множества Е такого, что M[D] С Е С [D], D т Е ф B[D]. Доказательство. Для того, что вычислить D{x) для произвольного числа х, найдем наименьшее s0 такое, что для любого у у у Є Е — s(y) so- Если х $ DSo, тогда х & D. Предположим, х Є Ds. Тогда, Этим завершается доказательство. Теорема IV.2.1. Пусть d- собственная р.р.п. степень, а а - р.п. степень такие, что 0 а d. Найдется и-р.п. степень c d такая что d р.п. с (c-REA), и а с. Доказательство. Пусть А -р.п. множество из степени a, D - р.р.п. множество, принадлежащее d. Зафиксируем рекурсивные аппроксимации множеств А и D. Предположим, что аппроксимация D удовлетворяет условиям, при которых выполняется лемма 2.3. В - ассоциативное множество для D, Ъ - его степень. Мы предполагаем, что а Ь, иначе, теорема доказана. Можно также предположить, что существует рекурсивная функция h такая, что каждый раз, когда когда число п перечисляется в A, h(n) попадает в В. Мы будем строить и-р.п. множество Е С [D] и определим С = {s(y) : у $ Е} (где, как и раньше, s(x) обозначает шаг, когда х попадает в [D]). Тогда, Е является C-REA. Для обеспечения D т Е@В мы будем строить Е, удовлетворяющим условию Min(D) С Е.