Минимальные покрытия тьюринговых степеней тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

На правах рукописи

Ишмухаметов ШАМИЛЬ ТАЛГАТОВИЧ

МИНИМАЛЬНЫЕ ПОКРЫТИЯ ТЬЮРИНГОВЫХ СТЕПЕНЕЙ

Специальность 01.01.06 — Математическая логика, алгебра и

теория чисел

Автореферат диссертации на соискание ученой степени

ццт*отглм/чгнт ияцхг

Ульяновск — 2003

Работа выполнена на кафедре «Математическая кибернетика и информатика» в Государственном образовательном учреждении высшего профессионального образования Ульяновском государственном университете

Научный консультант:

Доктор физико-математических наук, профессор член-корреспондент АН республики Татарстан Арсланов Марат Мирзаевич

Официальные оппоненты:

Доктор физико-математических наук, профессор Верещагин Николай Константинович

Доктор физико-математических наук, профессор Морозов Андрей Сергеевич |

Доктор физико-математических наук, профессор Соловьев Валерий Дмитриевич

Ведущая организация:

Институт Математики СО РАН, г. Новосибирск

Защита состоится 17 декабря 2003 г. |в 10 ч.ОО мин. на заседании диссертационного совета Д 212.278.02 при Ульяновском государственном университете по адресу: г. Ульяновск, ул. Набережная р. Свияги, д.40, ауд. 703

Отзывы по данной работе просим направлять по адресу: 432970, г. Ульяновск, ул. Л.Толстого, 42, УлГУ, УНИ

С диссертацией можно ознакомиться в библиотеке Ульяновского государственного университета

Автореферат разослан

2003 г.

Ученый секретарь совета

Веревкин А.Б.

0.О&3' А

Введение

Общая характеристика работы

Актуальность темы. Тьюринговая сводимость является наиболее общим видом сводимости, изучавшимся в теории вычислимости. Фактори-зуя класс всех множеств натуральных чисел по отношению тьюринговой сводимости, мы получим так называемую структуру тьюринговых степеней Б. Изучение этой структуры является одной из наиболее значительных задач теории вычислимости. Исследования в этой области начаты с самого зарождения теории, т.е. с начала 50-х годов, и в течение длительного периода большое количество ученых обращается к вопросам структурного строения полурешетки В, получая новые и новые результаты. Ряд проблем, поставленных еще в середине 50-х годов относительно распределения минимальных степеней и их покрытий, был решен сравнительно недавно, а некоторые вопросы не получили ответа и поныне. 13 диссертации рассматриваются три важнейшие проблемы в этой области:

• проблема построения минимальных степеней и минимальных покры-

• проблема дополнений в нижних конусах,

• проблема относительной перечислимости тьюринговых степеней,

Прогресс в решении этих проблем способствует решению главной задачи теории вычислимости в этой области - полной алгебраической харак-теризации структуры Ю.

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

Научная новизна. Все результаты, представленные в диссертации, являются новыми. Они существенно расширяют научные преставления в

тий,

таких областях как строение полурешетки тьюринговых степеней, относительная перечислимость тьюринговых степеней.

Практическая и научная ценность. Результаты диссертации представляют теоретический интерес и относятся к области так называемых фундаментальных исследований. Они расширяют научные предствления в области строения тьюринговых степеней. Могут быть использованы в учебных целях в курсах математической логики и теории алгоритмов.

Основные положения, выносимые на защиту.

Диссертант выносит на защиту следующие основные положения:

• Разработка нового перспективного метода построения минимальных степеней и минимальных покрытий для тьюринговых степеней,

• Решение известной проблемы Купера и Епштейна о дополнениях в нижних конусах,

• Решение проблемы Спектора (С. Spector [1956]) об описании класса тьюринговых степеней, обладающих строгими минимальными покрытиями, для класса р.п. множеств,

• Решение проблемы Джокуша, Доуни, Стоба (R.Downey, C.Jockusch, M.Stob об определимости класса совокупно нерекурсивных р.п. степеней (array nonrecursive degrees),

• Разработка нового простого метода построения начальных сегментов степеней ниже О',

• Изучение сложности представления начальных сегментов тьюринговых сепеней.

• Разработка явления изолированности в иерархии Ершова,

• Изучение относительной перечислимости тьюринговых степеней.

Апробация работы. Основные результаты диссертации докладывались на различных научных семинарах и конференциях, в том числе за рубежом:

на семинарах кафедры алгебры Казанского университета, на Мальцевских международных конференциях в Новосибирске, на научном семинаре школы математики Лидского университета (февраль 2001 г, Англия), на семинарах кафедр алгебры и математической логики МГУ, на Европейском логическом коллоквиуме в Мюнстере (август 2002 г., Германия). Основные результаты дисертации опубликованы в 12 статьях в журналах Известия вузов. Математика, Математические заметки, Фундаментальные методы математики и механики, Journal of Symblic Logic (США), Archive for Mathematical Logic (Германия), сборник De Gruyter Series in Mathematics, v.2. (США).

Все результаты, приведенные в диссертации, являются либо новыми, доказанными лично автором, либо ранее известными результатами (представленными в главе III с соответствующими ссылками), получившими в диссертации новые доказательства. Теорема IV.4.1. была доказана совместно с Гуохуа By и опубликована в совместной работе. Эта теорема также вошла в сосгаь докторской диссертации Г.Ву, защищенной им в 2003 году в Веллингтонском университете (Новая Зеландия).

Объем и структура работы: Диссертация состоит из введения, четырех глав, разбитых на 19 параграфов и списка литературы, насчитывающего 110 наименований. Общий объем работы - 180 страниц.

СОДЕРЖАНИЕ РАБОТЫ

История вопроса. Первая конструкция минимальной степени принадлежит К. Спектору1. Шенфильд2 ввел понятие деревьев, которое оказалось чрезвычайно полезным для формулировок и доказательств результатов о минимальных степенях и покрытиях и способствовало упрощению доказательства Спектора.

Определение. Деревом называется функция Т из множества 2<ш (т.е. из множества конечных последовательностей из 0 и 1, называемых строками) в множество 2<w такая, что:

1. Т(а) I Ат С а -4 Т(т) I определено А Т(т) С Т{ст).

'C.Spector. On degrees of recursive unsolvability, Ann. of Math. 64, 1956, pp. 581-592

2J.R. Shoenfield. A theorem on minimal degrees, j.Symb.Log. 31, 1966, 539-544

2. Если одно значение из пары Т(а * 0), Т(а * 1) определено, то определено и другое,и они несравнимы (будем использовать запись Т(а * 0)|Т(а*1)).

Дерево Т называется полным, если функция Т определена на любой строке т.

Строка принадлежит по определению дереву Т, если либо сама строка т, либо ее некоторое расширение принадлежит области значений функции Т. Множество А лежит на дереве Т, если каждый начальный сегмент характеристической функции А лежит на Т.

Переведенное на язык деревьев, доказательство Спектора основывается на двух нижесформулированных леммах, итерационное применение которых позволяет легко получить минимальную степень (полное доказательство можно найти в книге М.М. Арсланова3, с.142.

Лемма 1. Если Т-полное рекурсивное дерево и е-произвольное число, то существует полное рекурсивное поддерево Q дерева Т, такое что для любой бесконечное ветви Л, расположенной на Q, А ^ фе.

Лемма 2. Пусть Т-полное дерево, и е-произвольное число. Существует такое полное поддерево Q дерева Т, что для любого А, расположенного на Q, ф£-всюду определенная функция —> либо рекурсивна, либо А <т

Анализ доказательства Спектора показывает, что требуемые в леммах поддеревья Q могут быть найдены с помощью оракула 0", поэтому и построенная им минимальная степень находится ниже 0". Существенным признаком этой конструкции является то, что применение оракула 0" является необходимым.

Дж.Сакс4, используя частичные деревья, сумел устранить использование оракула 0" и доказал существование минимальной степени ниже 0'. Этот метод получил название метода е-штатов. Однако метод Сакса использовал оракул 0' и не позволял ответить на ряд естественно возникающих вопросов. Одним из таких вопросов был вопрос о том, какие степени принадлежат замыканию множества минимальных степеней ниже

3М.М Арсланов. Рекурсивно перечислимые мнжества и степени неразрешимости, Изд-о Казан.унив. 1986, 205 стр.

4G.E. Sacks. A minimal degree less that 0', Bull. Amer. Math. Soc. 67, 1961, p.416-419

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

Для решения этих проблем Ейтсом 5 и Купером6 был разработан новый метод построения минимальных степеней ниже 0', получившый название метода полных аппроксимаций. Особенностью этого метода является полный отказ от использования оракулов и рекурсивная аппроксимация всех требуемых в конструкции вычислений. Используя новый метод, Купер показал, что степень 0' является супремумом двух минимальных степеней, а Бйтс доказал существование минимальных степеней под каждой нерекурсивной р.п. степенью.

Следующим важным шагом в описании структуры начальных сегментов полурешеток В и 0(<0') явились вложения в них различных частично упорядоченных множеств. Первый результат такого рода принадлежит Титгемайеру7, который сначало построил минимальную степень, обла-

дающую строгим минимальным покрытием, а затем доказал, что в D вложима n-элементная цепочка как начальный сегмент для произвольного натурального числа п. Далее Сакс8 показал, что любая конечная булева решетка вложима в D как начальный сегмент, а Лахлан (A. Lachlan [1968]) доказал, что любая счетная дистрибутивная решетка с наименьшим элементом изоморфна некоторому начальному сегменту D. В доказательстве этих результатов используются так называемые униформные (uniform) или однородные ( по терминологии книги Арсланова[1986]) деревья. Описание этого метода можно найти в книге П.Одифредди9, гл.5.

Однако, несмотря на обилие методов, ряд проблем, касающихся минимальных степеней, оставался нерешенным. Важнейшими из них являются проблема Спектора о строгих минимальных покрытиях и вопрос Ейтса, каждая ли минимальная степень обладает с.м.п. Одифредди в своей моно-

5C.E.M. Yates. Initial segments of the degrees of unsolvability, Part H: Minimal degrees, J Symb.Log 35, 1970, p.243-266

6S B. Cooper. Minimal degrees and the jump operator, J. Symbolic Logic, 38,1973, p.249-271.

7D. Titgemeyer. Untersuchen über die Struktur des Ifleene- Postchen Halbverbandes des Grade der rekursiven Unlosbarkeit, Arch.Math. Logik Grundlagenforsch. 8/1-2,1962, p.45-62

8G E. Sacks. Degrees of Unsolbability, Annals of Math. Studies 55, Princeton Univesity Press, N.J., 1963

9P.Odifreddi. Classical Recursion Theory, Studies in Logic and the Foundations of Mathematics, Vol. 125,1989, North-Holland

графии на с.527 сравнивает силу различных методов построения минимальных степеней и делает заключение, что существующие методы не позволяют строить минимальную степень, не обладающую с.м.п. Следовательно, необходимы новые методы.

Один из новых подходов, предложенных автором диссертации, является изучение минимальных степеней и покрытий в рамках метода приоритета. Формулировка основных определений приводится здесь не в традиционном стиле деревьев, как во всех ранее существовавших доказательствах о минимальных степенях, а в духе современного, разработанного A. Jlax-ланом и JI. Харрингтоном подхода дерева, стратегий к методу приоритета. Поскольку все современные разновидности метода приоритета, включая мощные методы уровня 0" и выше, основываются на идее деревьев стратегий, или еще более сильном понятии итерированных деревьев стратегий10, то такой подход обеспечивает возможность применения всей силы метола приоритета к задаче исследования тьюринговых степеней не только р.п. множеств, как ранее, но и произвольных степспсй, объединяя традиционные оракульные методы построения степеней (метод начальных сегментов, метод кобесконечных расширений и т.д. с мощными конструктивными методами, разработанными первоначально для построения р.п. степеней. В первой главе диссертации мы дадим подробное описание основных идей нового метода, доказав теорему Сакса о существовании минимальной степени О'.

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

Определение. Пусть тьюринговые степени а я b удовлетворяют условию 0<а<Ь. Степень с называется дополнением степени а до степени Ь, если aUb=c я aflb=0. Если выполняется только первое (второе) из этих условий, то степень с называется дополнением вверх (вниз).

Наиболее важным является случай, когда верхняя степень b совпадает с 0'. Долгие исследования в этой области завершились результатами Познера

10S. Lempp, M. Lerman. Iterated trees of strategies and priority arguments, Archive for Mathematical Logic, 36, 1997, p.297-312

к Робинсона11,12, которые доказали, что полурешетка D(<0') дополняема, т.е. для каждого нетривиального элемента а найдется элемент Ь, удовлетворяющий соотношениям: aUb=0', аПЬ=0. Недостаток этого доказательства, состоявший в том, что приводились два совершенно различных доказательства для случая, когда а являлась низкой, и когда ее скачок находился выше 0', был исправлен Слеменем и Стилом (рукопись), которые также показали, что дополнение можно выбрать из широкого спектра степеней, например, минимальной или 1-генерической степенью. В монографии 1979 года Эпштейн13 выдвинул гипотезу о том, что в нижнем конусе D(< а-р.п.) каждая промежуточная р.п. степень обладает минимальным дополнением, и сам подтвердил ее для случая, степень а является высокой, т.е. удовлетворяет соотношению а' =0". Однако, в общем случае решить эту проблему ему не удалось. Сложность заключается в том, что построения ниже заданной р.п. степени (например, вложения частичных порядков) не могут проводиться методами, использующими оракулы (как, например, в теореме Слемека и Сетапуна). Здесь требуются эффективные методы, использующие рекурсивные аппроксимации заданных и конструируемых множеств и функционалов. Построения ниже высоких p.ri. степеней используют идею существования некоторой быстро возрастающей функции, рекурсивной в рассматриваемой степени, которая мажорирует (с некоторого номера) каждую всюду определенную рекурсивную функцию. Общий метод таких построений описан в статье Слей-мена и Шора14.

Следующий результат в этом направлении был получен в работе Купера и Эпштейна15, которые показали, что в произвольном конусе D(< а-р.п.) для каждой низкой р.п. степени b имеется несравнимая с ней минимальная степень, и, следовательно, каждая низкая степень b обладает дополнением m вниз (т.е.ЬЛт=0). Однако, в общем случае проблема решается отрицательно, т.е. существует нижний конус D(< а-р.п.), в котором некоторая

"D.В.Posner, R.W.Robinson. Degrees joining to 0', J. Symb.Log. 46,1981, p.714-721

12D.B. Posner. The upper semilattice of degrees >0' is complemented, J. Symb.Log. 46,1981, p 705-713

13R.L. Epstein. Degrees of Unsolvabffity: Structure and Theory, Lect Notes in Mathematics 759, Springer-Verlag, 1979

14R.A. Shore, T.A. Slaman. Working below a I0W2 recursively enumerable degree, Archive for Math. Logic 29, 1990, p.201-211

»S B. Cooper, R.L. Epstein. Complementing below recursively enumerable degrees, Ann. Pure Appl. Logic, 32, 1987, p.15-32

степень b<a не имеет дополнения (теорема 2, там же).

Усиливая этот результат, Слемен доказал, что существует нижний конус, в котором никакая степень Ь<а не обладает дополнением. Позднее Купер16 и независимо Слемен и Стил 17 доказали (эти доказательства, использующие различные подходы, опубликованы в одном номере журнала), что существует р.п. степень а такая, что в нижнем конусе D(< а-р.п.) некоторая р.п. степень Ь<а не дополняема вверх. Открытым остался вопрос о дополняемости минимальными степенями вниз. В работе 1986 года Купер утверждает (доказательство не опубликовано), что в некотором конусе D(< а-р.п.) найдется промежуточная степень Ь<а (не обязательно р.п.) такая, что любая минимальная степень m лежащая ниже а находится также ниже Ь. В статье 1987 года Купер и Эпштейн выдвинули гипотезу, что их теорема о дополняемости вниз низких степеней является наилучшим результатом в этом направлении. Эта гипотеза была подтверждена в работе 1998 года А.Ли и Д.Янгом, и это доказательство было .опубликовано в престижном математическом журнале18, однако, автор дисертации показал, что доказательство Ли и Янга является неверно и доказал противоположный результат о том, что для любых р.п. степеней 0<а<с найдется to- р.п. минимальная степень т<с, несравнимая с a (Ishmukhametov[2003]).

Этот результат полезно сравнить с теоремой Доуни и Стоба19 о том, что в каждом нижнем конусе D(< а-р.п.) найдется р.п. степень Ь<а , не являющаяся частью минимальной пары в классе р.п. степеней (и, следовательно, также в классе n-р.п. степеней). По нашей теореме, в каждом таком нижнем конусе каждая промежуточная р.п. степень является частью минимальной пары в классе ш-р.п. степеней. Таким образом, наш результат завершает решение указанной проблемы.

Эта теорема решает также проблему Лахлана о распределении ветвящихся степеней в ограниченных сверху конусах D(< а-р.п.) для степени О

16S.B. Cooper. The strong anti-cupping property for recursively enumerable degrees, J.Symb.Logic, 54, 1989, p.527-539

17T.A. Slaman and J.E. Steel. Complementation in the Turing degrees, J.Symb. Logic, 54,1989, p 160176

18A. Li, D Yang. Bounding minimal degrees by computably enumerable degrees, J.Symb Log, 63,1998, pp.1319-1347

19R. Downey, M Stob. Minimal pairs in initial segments of the recursively enumerable degrees, Isr.J.Math , 100, 1997, p.7-27

(степень а называется ветвящейся, если она является наименьшей верхней гранью двух степеней ai и аг, aifla^ =а). Точнее говоря, по известной теореме Лахлана20 степень 0 не является ветвящейся в некотором нижнем конусе D(< а-р.п.) (в классе р.п. степеней). Поскольку, под каждой нерекурсивной n-р.п. степенью для п Е ш всегда найдется нерекурсивная р.п. степень, то можно заключить, что теорема Лахлана выполняется также для класса п-р.н. степеней. По нашей теореме, степень 0 является ветвящейся в классе w-p.n. степеней в любом нижнем конусе D(< а-р.п.), и этот результат является наилучшим возможным. Таким образом, существует р.п. степень а такие, что элементарные теории р.п. степеней и ш-р.п. степеней в нижнем конусе D(< а-р.п.). являются различными.

Заметим, что двойственной к упомянутой теореме Лахлана является другая его известная теорема о том, что существует неполная р.п. степень а такая, что степень 0' не расщепляема в верхнем конусе D(> а). В четвертой главе (теорема IIV.3.1) мы докажем, что такое расщепление можно выполнить в классе степеней, содержащих разности р.п. множеств, что также является наилучшим результатом в этом направлении. Этот же результат был независимо доказан Дингом и Квином (D.Ding, L.Qian [ta]).

Вторая глава диссертации посвящена исследованию степеней, обладающих строгими минимальными покрытиями.

Определение. Степень m иназывается строгим минимальным покрытием степени а, если а<т и для всех Ь<т выполняется Ь<а.

Известно, что степени, являющиеся с.м.п., и степени, обладающие с.м.п., расположены достаточно близко к степени 0. Действительно, любая степень, лежащая выше 0', по теореме Фридберга о полных степенях является скачком некоторой меньшей степени, а, значит, разложима. По релятивизованной теореме Сакса о разложении любая REA-степень (т.е. степень рекурсивно-перечислимая в некоторой меньшей степени) разложима и, следовательно, также не может быть с.м.п. По теореме Познера21 каждая высокая степень перечислима в некоторой низкой степени и также не может быть с.м.п. Наилучшим результатом в описании степеней, не являющихся с.м.п. и не обладающих ими, являются результаты Доуни,

20А.Н. Lachlan. Bounding minimal pars, J Symb. Log. 44, 1979, p.626-642

21D.B. Posner [1977] High degrees, Ph.D. Dissertation, University of California, Berkeley.

Джокуша и Стоба, описавших класс степеней, названных ими совокупно нерекурсивными (с.н.) степенями22,23.

Определение. Степень а является совокупно нерекурсивной, если для любой функции / <wtt К, где K-креативное множество, найдется функция д, рекурсивная в а такая, что д(п) > /(п) для бесконечно многих п.

Непосредственно из определения вытекает, что этот класс замкнут вверх. Авторы доказали также, что каждая степень а, не являющая GL^-низкой (т.е. удовлетворяющая свойству а" > (aUO')'), является с.н.сте-пенью, однако существуют также низкие и /ом^-степени, являющиеся с.н. Наиболее важные теоретико-решеточные свойства этих степеней является то, что они замкнуты вверх, разложимы и дополняемы вверх к любым степеням, расположенных выше. Более сильным является утверждение, следующее из теоремы П.Фейера24, о том, что каждая рекурсивно предста-вимая решетка с различными наименьшим и наибольшим элементами вложима в нижний конус D(<a), ограниченный произвольной с.н.степенью, с сохранением наибольшего и наименьшего элементов и решеточных операций. Следовательно, никакая с.н.степень не может ни сама быть с.м.п., ни обладать им. В частности, все степени, обладающие с.м.п., принадлежат GL2, а степени, находящиеся ниже 0', принадлежат L2. Поэтому, все известные примеры вложений частично-упорядоченных множеств как начальных сегментов в тьюринговые степени имеют своими образами GLi-степени.

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

22R. Downey, С. Jockusch, and М. Stob [1990]. Array nonrecursive seta and multiple permitting arguments, Lect. Notes Math, 1432, Springer-Verlag, 1990,рр.141-173

23R. Downey, C. Jockusch, and M. Stob [1996]. Array nonrecursive sets and genericity, in Computability, Enumerability, Unsolvability: Directions in Recursion Theory, eds S.B. Cooper, T.A. Slaman, S.S. Wainer, London Mathematical Society, Lect. Notes Series N 224, Cambridge University Press, pp 93-104

24P. Fejer [1989]. Embedding lattices with top preserved below non-GL¡ degrees, Zeitschr.f math. Logik und Grundlagen d Math. 35 (1989), 527-539

25S.B. Cooper [1971]. Degrees of Unsolvability, Ph.D. Thesis, University of Leicester, 1971.

степень, содержащая множество из класса Е"1, обладающая с.м.п.

Возвращаясь к проблеме степеней, не обладающих с.м.п., мы дадим прямую конструкцию низкой р.п. степени, не обладающей с.м.п ниже О'. Существование таких степеней следует также неявно из вышеупомянутого результата Доуни, Джокуша и Стоба, однако они используют другую технику доказательства.

Также в этой главе мы определим новый класс степеней, названных слабо рекурсивными (weakly recursive) степенями и докажем, что каждая слабо рекурсивная степень обладает слабо рекурсивным строгим минимальным покрытием.

Определение. (Ишмухаметов [1999b]) Степень а называется слабо рекурсивной, если для любой функции f рекурсивной в а найдется слабая таблица (weak array) {Wh(n)}£Lo такая, что для каждого п € ш :

1- |WMn)| < 2П,

2. Дп) е wh[n),

3.х^у Wh[x) Л Wh[y) = 0.

Непосредственно из определения следует, что класс слабо рекурсивных степеней замкнут вниз, т.е. для любых степеней а,Ь, если а<Ь и be WR, то и аб WR.

Если слабо рекурсивная степень а находится ниже 0', то каждая функция /, рекурсивная в а, является w-p.n., т.е. имеет рекурсивную аппроксимацию f(s,n) такую, что для каждого n |{/(s,n) : s G < 2™. Поскольку произвольная р.п. степень а является ш-р.п. тогда и только тогда, когда а не является совокупно нерекурсивной, то непосредственно получаем, что класс рекурсивно перечислимых слабо рекурсивных степеней является дополнением множества совокупно нерекурсивно р.п. степеней в классе всех р.п. степеней R. Следовательно, наша теорема дает решение упомянутой выше проблеме Спектора для класса р.п. степеней R. Мы перечислим определимые свойства слабо рекурсивных р.п. степеней в следующем предложении:

Предложение. Пусть а - произвольная р.п. степень. Следующие условия являются эквивалентными:

(1) а-слабо рекурсивна,

(2) а-не является совокупно нерекурсивной,

(3) Любая степень b, Ь< а обладает строгим минимальным покрытием,

(4) Существует Ь>а, не являющая наименьшей верхней гранью минимальной пары степеней (в множестве всех степеней) (Downey26 , теорема 1.1),

(5) Существует неразложимая степень Ь>а.

Поскольку слабо рекурсивные степени замкнуты вниз, то мы получаем определимый класс минимальных степеней, обладающих с.м.п., именно, класс минимальных степеней, ограниченных сверху слабо рекурсивными р.п. степенями. Действительно, р.п. степени R определимы в D по известному результату Купера27, а слабо рекурсивные степени определимы в D по нашей теореме.

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

Одновременно мы дадим частичный ответ на вопрос Доуни, Джокуша и Стоба об определимости совокупно нерекурсивных степеней, показав, что совокупно нерекурсивные р.п. степени определимы в D (по любому из свойств, перечисленных в п.п. 1-5 вышеприведенного предложения).

В следующем параграфе мы рассмотрим слабые минимальные покрытия р.п. степеней. Понятие слабого покрытия было введено Купером и Уаем28.

Определение. Степень а называется изолированной, если она не является верхней гранью никакой последовательности степеней, находящихся строго ниже а.

Очевидно, строгие минимальные покрытия обладают свойством изолированности. В работе [1995] Купер и Уай ослабили это определение, назвав

2eR. Downey [1993] Array nonrccursive degrees and lattice embeddings of the diamond, 1П. J. Math. 37 (1993), pp.349-374

"S.B. Cooper [1991] Rigidaty and definability in the non-computable universe, Proc. 9-th In-tern.Congress of Logic, Methodology and Philosophy of Science, Uppsala, 1991, North-Holland, 1994, p. 209-236

38S.B. Cooper, and X. Yi [1993] Isolated d r.e. degrees, Preprint Series, N 17, Math. Log Quarterly, 1-27

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

В дальнейшем, степени, содержащие разности р.п.множеств, будем называть p.p.п. степенями. Степень а из теоремы Купера и Уая является верхней гранью всех р.п. степеней, находящихся строго ниже степени d. Такие степени авторы назвали изолирующими.

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

Теорема. (Ишмухаметов [1990]). Любая нерекурсивная р.п. степень является верхней гранью двух не р.п. р.р.п. степеней.

Теорема. (Ишмухаметов [1986], Купер и Уай [1995]). Для любой степени d, содержащая разности р.п.множеств, и р.п. степень a, a<d, найдется р.р.п. степень b, a<b<d.

Заметим, что существование изолированной р.р.п. степени следует также из более раннего результата Кадах29, теорема 3.2, которая доказала, что каждая низкая р.п. степень является нижней гранью двух р.п. степеней (т.е. является ветвящейся в классе р.р.п. степеней), а по результату Фейера30 не каждая низкая р.п. степень является ветвящейся в классе р.п. степеней. Дальнейшее изучение р.р.п. степеней производится в IV главе диссертации.

Третья глава диссертации посвящена изучению начальных сегментов тьюринговых степеней ниже О'. В этой главе используя наш метод построения минимальных степеней и минимальных покрытий мы дадим новые доказательства теорем о вложениях различных конечных порядков в тьюринговые степени. Используя метод деревьев стратегий, наш метод позволил получить значительное упрощение этих технически сложных доказательств. Мы передокажем теоремы Сакса и Титгемайера о ВЛОЖе-

^О. Kaddah [1993] Infima in the d.r.e. degrees, Ann. Pure Appl. Log. 62, pp. 207-263

30P. Fejer [1982]. Branching degrees above low degrees, Trans. Amer.Math.Soc 273, 1982, p. 157-180

ниях в Б(<0 ') ромба и возрастающей линейной цепи, недистрибутивной решетки N5 и произвольной конечной решетки, имеющей конечную репрезентационную таблицу.

В пятом параграфе этой главы мы рассмотрим вопрос о вложении в И счетных линейных порядков. Пусть Ь - произвольная верхняя полурешетка. При ее вложении вБв качестве начального сегмента строится нижний конус 0(<а), изоморфный Ь, причем строится отображение для каждого элемента а € Ь в некоторое множество А, представляющее тьюринговую степень, являющуюся образом элемента а. Спрашивается, а какова степень представления этого изоморфизма? Иначе говоря,, если для для элементов а,Ь 6 Ь выполняется а < Ь, то как трудно найти алгоритм, сводящий соответствующее множество А к соответствующему В? В частности, если структура Ь вычислима, то можно ли найти сводящие алгоритмы рекурсивно? Эта проблема ранее не исследовалась, но неявно считалось, что ответ должен быть положительным. В параграфе 5 мы доказываем теорему, опровергающую в сильной форме, показав, что ниже любой униформной в 0' последовательности степеней найдется ненулевая степень с, лежащая ниже каждой степени этой последовательности.

Непосредственно из этой теоремы вытекает, что если обратный линейный порядок ш*= {1 > 2 > 3 > ... > 0} изоморфен начальному сегменту Т-степеней I, то структура I не может быть униформной (в 0'), т.е. нельзя найти сводящие алгоритмы, даже используя оракул О'.

Этот результат оказался настолько неожиданым, что многие ученые, работающие в этой области, не могли поверить в его корректность. Автор диссертации обсуждал эту проблему с американцами М.Лерманом и Ш.Лем-пом, но не мог убедить их в том, что рекурсивно представимый порядок не должен обязательно иметь рекурсивно представимый образ. Первоначально поверил в этот результат Бьерн Кристиансен, ученик Теодора Слеймена из Чикаго, изучающий возможность вложения в Б бесконечных полурешеток. И он сумел убедить в этом Лермана, который прислал мне письмо, в котором признал правильность моих доводов.

В заключительной IV главе диссертации мы производим общее исследование проблемы относительной перечислимости одних степеней относительно других. Изучается класс Т-степеней, содержащих разности р.п.

множеств. Все доказательства, приводимые в этой главе, используют фундаментальное понятие ассоциативного множества, введенное первоначально, Ю.Л.Ершовым31 при исследовании индексных множеств конечных семейств р.п. множеств.

Определение. Пусть D - р.р.п. множество, и задано его некоторое перечисление. Ассоциативным множеством B[D] (относительно заданного перечисления) называется множество таких s, что некоторый элемент х перечислен в D на шаге s,Hox^D(m.e.x позднее изымается из D).

Мы доказываем в параграфе 1 предложение IV.1.1. о том, что степень ассоциативного множества инвариантна относительно выбора перечисления разности р.п. множеств D и фактически является наименьшей р.п. степенью, в которой D перечислима.

Другим важным является вопрос о распределении изолированных р.р.п. степеней. Отвечая на вопрос, поставленный Купером и Уаем. Ля Форте доказал32 существование изолированной р.р.п. степени в интервале между любыми двумя р.п. степенями. Отвечая на другой вопрос Купера и Уая, Арсланов, Лемпп и Шор33, теорема 3.2), доказали, что существует нерекурсивная р.п. степень, не являющаяся изолирующей ни для какой REA-степени.

В диссертации мы дадим новое доказательство теоремы Купера и Уая о существовании изолированных р.р.п. степенй. Наше доказательство, использующее идею ассоциативного множества для разности р.п.множеств, значительно проще оригинального доказательства Купера и Уая. Непосредственно из определения ассоцитивного множества В следует, что оно рекурсивно в р.р.п. множестве D, для которого оно определено, и D перечислимо в В. Вместе с тем мы покажем (теорема IV.2.1), что существует степень d, содержашая р.р.п.множества Di, ассоциативные множества которых тьюрингово несравнимы.

31Ю.Л. Ершов [1968]. Об одной иерархии множеств, Алгебра и логика, 7, N 1, стр.47-73

32G. LaForte [1995] Phenomena in the n-r e. and n-REA degrees. Ph.D. thesis, University of Michigan, Ann Arbor, 1995.

3,M.M. Arslanov, S. Lempp, R.A. Shore [1996] On isolating r.e. and isolated d r.e. degrees, London Math Soc., Lect. Note Series 224, Canbridge Univ.Press, 1996, p.61-80

Основная проблема состоит в том, чтобы найти условия, когда для данных степеней end, c<d, верхняя степень d перечислима в нижней степени с. Замечательный результат, характеризующих пары таких степеней, был получен Купером34:

Степень d относительно перечислима в степени с, тогда и только тогда, когда для любых степеней а и b больших с, dUa разложима над а обходя b (т.е. существуют такие степени di и d2 над с, что dUa=diUd2, и d^dj, djid2

Теорема Купера дает ответ на давний вопрос, поставленный еще Постом, об определимости операции скачка в терминах тьюрингового упорядочения степеней

Известно, что для произвольной степени с существует наибольшая степень, перечислимая относительно с, именно, степень d, являющаяся скачком степени с. Естественными являются следующие вопросы: можно ли для данной степени d найти наименьшую степень с, относительно которой d перечне пимя? Если степень d перечислима в степени с, то можно ли найти степень а<с, в которой d будет также перечислима?

Для произвольной степени d определим классы iZ[d) и Q[d] как классы степеней, состоящих соответственно из р.п. степеней и всех степеней, относительно которых d перечислима. Вышеприведенные вопросы можно переформулировать следующим образом:

Имеют ли классы J?[d] и Q[d] наименьший элемент, минимальные элементы? Ограничены ли они снизу ненулевыми элементами? Ответы на эти вопросы даются в четвертой главе диссертации. Мы покажем, что существует р.р.п. степень d, для которой класс i?[d] представляет собой верхний конус D(>a). Элемент а будем называть базой этого конуса. Мы построим также p.p.п. степень d, у которой класс i?[d] не имеет наименьшего элемента. В теореме IV.3.2. исследуя класс всех степеней относительно которых данная REA-степень d перечислима, мы покажем, что класс Q[d\ для такой степени d не может иметь наименьшего элемента, если только d не р.п., и более того, не ограничен снизу никакой ненулевой степенью.

В теореме IV.1.2 приводится необычной пример р.р.п. степени d, для который класс J?[d]nD(<d) состоит в точности из одного элемента.

34S.B Cooper [1993]. On a conjecture of KJeene and Post, Preprint Series 1993, N 7, Leeds, p.1-122

В следующем параграфе мы изучаем проблему разложимости р.п. степеней. Под разожением ненулевой степени d мы понимаем представление d=diUd2, где di и d2 - меньшие несрвнимые степени. В общем виде эта проблема была решена Купером35, который показал, обобщая теорему Сакса о разложении, что каждая п- р.п. степень для п > 2, разложима на две меньшие п- р.п. степени.

В своей известной работе36 Лахлан показал, что степень 0' не разложима в классе р.п. степеней над некоторой неполной р.п. степенью а. Встает вопрос, а можно ли это сделать в каком-нибудь более широком классе. Первый результат в решении этой проблемы был получен М.М. Арслано-вым37, который доказал разложение степени 0' в классе ш- р.п. степеней. В параграфе 3 четвертой главы мы докажем наилучший результат в этом направлении, разложив 0' в классе 2-р.п. степеней.

В следующем параграфе мы докажем, что существует изолированная пара, состоящая из высокой р.р.п. степени и низкой р.п. степени. Этим мы ответим на один вопрос Купера и Уи, а также на вопрос, поставленный Гуохуа By (Guohua Wu, New Zealand). Пара, состоящая из высокой р.р.п. степени и I0W2- р.п. степени, была построена предварительно Гуохуа By, но затем Ишмухаметову удалось улучшить этот результат, и совместный результат был опубликован в журнале Archive for Mathematical Logic (Ish-raukhametov, Wu [2002b]).

Наконец, в последнем параграфе диссертации мы рассмотрим вопрос о дистрибутивности верхних полурешеток степеней, образованных степенями по различным сводимостям, изучавшимся в теории вычислимости. Пусть г- произвольная сводимость. Обозначим через полурешетку р.р.п. г- степеней. В четвертом параграфе третьей главы мы исследуем эту полурешетку на предмет дистрибутивности для различных сводимостей г. Мы покажем, что в отличии от случая р.п. степеней структура является недистрибутивной для широкого класса сводимостей, промежуточных между bd-сводимостью и тьюринговой сводимостью. Это дает еще одно элементарное отличие полурешеток DJ и

35S.B.Cooper (1992]. A Splitting Theorem for the n-r.e degrees. Proc.AMS, v.115, N 2, 1992, 461-471

3eA.H. Lachlan [1975] A recursively enumerable degree which will not split over all lesser ones, Ann. Math. Log 9, 307-365

37М.М.Арсланов [1987]. Локальная теория степеней неразрешимости и Д§-множества, Изд-о Казан.унив. 1987, 139 стр.

Перечень основных теорем.

Теорема 1.2.1. (Ishmukhametov [2003]) Для любых р.п. степеней а,с, 0<а<с, найдется to-р.п. минимальная степень хп<с, несравнимая с а.

Следствие. В произвольной нижнем конусе D(<c-р.п. нерек.) каждая р.п.степени а, 0<а<с имеет дополнение вниз.

Теорема 1.3.1. Существует низкая р.п. степень с > 0 такая, что для любой степени а,0<а<с, найдется минимальная степень т<с, несравнимая с а.

Теорема 1.4.1. (Ишмухаметов, Купер, Ли [ta]). Для произвольных р.п. степени с и low2-CTeneHH а, 0<а<с, существует минимальная степень т<с несравнимая с а.

Теорема II. 1.1. Для любого рекурсивного ординала а существует собственная атр.п. степень а, обладающая w-p.n. строгим минимальным покрытием.

Теорема И.2.1.(Ishmukhametov [1998]) Существует низкая р.п. степень а, не имеющая с.м.п. ниже О'.

Теорема II.2.2. Для каждого рекурсивного ординала а найдется собственная a-r.e. degree а, не имеющая с.м.п. ниже О'.

Теорема II.3.1. (Ishmukhametov [1999b]) Каждая слабо рекурсивная степень а обладает строгим минимальным покрытием т.

Теорема II.3.2 Каждая слабо рекурсивная степень а имеет слабо рекурсивное с.м. покрытие т.

Теорема II.3.3. Каждая слабо рекурсивная степень имеет С = 2Ы слабо рекурсивных строгих минимальных покрытий.

Теорема II.4.1.(Cooper, Yi [1993], Ишмухаметов[1999с1]). Существует изолированная пара b,d, состоящая из собственной р.р.п. степени d и ассоциированной с ней р.п. степенью Ь.

Теорема III.l.l. (Titgemeyer[1962], Ишмухаметов[2002а]). 3-элемент-ная цепь 0<1<2 изоморфна начальному сегменту D(<0').

Теорема III.1.2.(Sacks[1962], Ишмухаметов[2002а]) Ромб вложим как начальный сегмент степеней ниже О'.

Теорема III.3.1. (Shoehfield (пеопубл.), Ишмухаметов[2002а]). Решетка М5 изоморфна начальному сегменту степеней ниже О'.

Теорема III.4.1.(Tomason [1970], Lerman[1983], Ишмухаметов[2002а]). Каждая конечная решетка, обладающая конечной униформной таблицей, изоморфна начальному сегменту тьюриновых степеней.

Определение. Представлением частично- упорядоченной структуры L называется произвольное отображение множества натуральных чисел ш на на множество \L\. Пусть а-степень. Структура | L, <ï\ называется а-прсдставкмой, если существует представление и, при котором предикат

R{i,j) = v(i) <L v{j)

является рекурсивным в а. Степень а= degrA называется сложностью представления v. Если а=0, то представление называется рекурсивным.

Теорема Ш.5.1.(Ишмухаметов [2002с]) Р={со > ci >С2... >0}-уни-

формная в 0' последовательность степеней. Найдется ненулевая степень с, находящаяся ниже каждой степени с„, п £ш.

Определение. Будем называть степени, содержащие разности рекурсивно- перечислимых множеств, р.р.п. степенями.

Теорема IV.1.1. (Ишмухаметов [1999d]) Существуют р.р.п. степень d и р.п. степень b < d такие, что b является наименьшей степенью, в которой d рекурсивно перечислима.

Теорема IV.1.2. (Ишмухаметов [1999d]) Существует р.р.п. степень d>0, перечислимая в точности в одной р.п. степени ниже d (такие степени будем называть точными).

Теорема IV.1.3. (Ишмухаметов [1999d]) Существует изолированная не точная p.p.п. степень d>0.

Для произвольной степени d R[d] обозначает класс р.п. степеней, находящихся ниже d, относительного которых d - перечислима.

Теорема IV.2.1. (Ишмухаметов [2000а]) Существует р.р.п. степень d, для которой класс R[d] не имеет наименьшего элемента.

Теорема IV.2.1. (Ишмухаметов [2000а]) Пусть d- собственная р.р.п. степень, а а - р.п. степень такие, что 0<а< d. Найдется w-p.n. степень c<d такая что d р.п. с (c-REA), и a¿c.

Теорема IV.2.2. (Ишмухаметов [2000а]) Пусть степени a,d удовлетворяют условию a<d< 0'. Если d является REA- степенью (перечислима в некоторой меньшей степени), тогда найдется степень с такая, что d=c-REA, и a¿c. .

Теорема IV.3.1. (Ишмухаметов [1996а]). Для любых р.п. степеней с и d, c<d, найдутся две р.р.п. степени а и Ь, удовлетворяющие c<a,b<d, такие, что d=aUb.

Теорема IV.4.1. (Гуохуа By Ишмухаметов [2002b]) Существуют высокая р.р.п. степень d и низкая р.п. степень а такая, что степень d изолируется степенью а.

Теорема IV.5.1. (Ишмухаметов [1993]) Существует р.п. множество С и две разности р.п. множеств А и В, что

1. С = A U В, А П В = 0,

2. Ни для каких множеств Aq, Bq, сводящихся по Тьюрингу к креативному множеству К, условие С =г Aq Л Aq <т A A Bq <т В не выполняется.

Следствие. Структура не является дистрибутивной ни для какой сводимости R, промежуточной между bd и тьюринговой.

Выводы.

Диссертация представляет и развивает новый эффективный метод построения минимальных степеней и покрытий. Этот метод был использован для решения известной проблемы Купера и Эпштейна, вывода ряда новых результатов и для получения существенно более простых доказательств известных результатов о вложениях различных упорядоченных структур в качестве начальных сегментов тьюринговых степеней. Предложенный автором подход использования техники методов приоритета для построения минимальных покрытий имеет дальнейшие перспективы для изучения структуры тьюринговых степеней.

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

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

Изучение понятия относительной перечислимости Т-степеней, выполненное автором в IV главе, позволило получить ряд новых неожиданных результатов о строении решетки степеней множеств из иерархии Ершова. Это исследование приближает нас к разрешению известной проблемы Доуни об эквивалентности классов п-р.п. степеней для п > 2.

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

Публикации автора по теме диссертации:

1. Ш.Т. Ишмухаметов [1983]. О классах разностей рекурсивно перечислимых множеств, Изв.вузов. Матем. 1983, N3, с.78-79

2. Ш.Т. Ишмухаметов [1985]. О разностях рекурсивно перечислимых множеств, Известия вузов. Матем. 1985, N8, с.3-12

3. Ш.Т. Ишмухаметов [1986]. Разности рекурсивно перечислимых множеств, их степени неразрешимости и индексные множества, Диссертация на соискание степени кандидата физико-математических наук, Новосибирск, 1986, 105 с.

4. Sh T. Ishrnukhametov [1989]. Intervals in the structure of T-degrees below 0', Abstracts of European Logic Colloquium, Berlin, 1989

5 Ш.Т Ишмухаметов [1990]. Одна теорема о разностях рекурсивно перечислимых множеств, Деп.в ВИНИТИ, N 2423-В90, 1990, 7 с.

6. Sh Т. Ishrnukhametov [1990]. Numerations of differences of recursively enumerable sets, Abstracts of Logic Biennial, Varna, Bulgaria, 1990, 1 p.

7. Ш.Т. Ишмухаметов [1992]. О разложении степени 0' на меньшие степени, содержащие разности рекурсивно перечислимых множеств. Тезисы докладов XI Международной конференции по математической логике, Казань, 1992

8. Ш.Т. Ишмухаметов [1993]. О дистрибутивности верхних полурешеток степеней ниже 0'. Изв.вузов.Матем. 1993, N1, с.17-20

9. Ш.Т. Ишмухаметов [1994]. О разложении степени 0' на меньшие степени, содержащие разности рекурсивно перечислимых множеств. Изв.вузов. Матем. 1994, N1, с.19-23

10. Sh Т. Ishrnukhametov [1996а] The splitting theorem above a r.e.degree, Фундаментальные проблемы математики и механики, вып.1, часть 2, изд-о Ульянов, госуниверситета, 1996, стр.139-143

И. Ш.Т. Ишмухаметов [1996Ь]. О точных n-р.п. степенях. Тезисы докладов XI Международной конференции по проблемам теоретической кибернетики, Ульяновск, 1996, с.80

12. Sh Т. Ishmukhametov [1997] On enumerability of d.r.e. degrees in lesser ones, Abstracts of European Logic Colloquium, Leeds, 1997

13. Sh T. Ishmukhametov [1998]. On degrees without strong minimal covers, Фундаментальные проблемы математики и механики, вып.2, изд-о Ульянов, госуниверситета, 1998, 25-31

14. Ш.Т. Ишмухаметов [1999а]. О начальных сегментах степеней неразрешимости. Тезисы докладов XII Международной конференции по проблемам теоретической кибернетики, Нижн. Новгород, 1999, с.90

15. Sh Т. Ishmukhametov [1999b]. Weak recursive degrees and a problem of Spector, de Gruyler Seiieb in Logic and Its Applications, v.2, Berlin, New-York, стр.81-87

16. Sh T. Ishmukhametov [1999c]. On embeddings of linear orderings as initial segments of Turing degrees, Тезисы докладов международной конференции по математической логике, Новосибирск, 1999, стр.87-88.

17. Sh Т. Ishmukhametov [I999d]. On the r.e. predecessors of d.r.e.degrees, Archive for Math. Logic, 38, Springer-Verlag, pp.373-386

18. Sh T. Ishmukhametov [2000a]. On relative enumerability of Turing degrees, Archive for Math. Logic,39, 2000, p.145-154

19. Sh T. Ishmukhametov [2000b]. Embeddings into Weakly Recursive degrees, Тез.докл. междун.конф."Логика и приложения", Новосибирск, 2000 г., с.118

20. Sh. Т. Ishmukhametov, Guohua Wu [2001], A High d.c.e.degree isolated by a Low c.e. degree, 2001 Annual meeting of the Assoc. for Symb. Logic, Philadelphia, USA, The Bulletin of Symbolic Logic, v.7, n.3, 2001, c.432-433

21. Ш.Т. Ишмухаметов. [2002а]. О начальных сегментах степеней неразрешимости, Фундаментальные проблемы математики и механики, Ульяновский государственный унив-т, 11, 2002, вып. 1, с.78-94

22. Sh.T. Ishmukhametov, Guohua Wu[2002b]. Isolating pairs and the Hi/Low hierarchy, Archive for Math.Logic, 41, Springer-Verlag, 2002, p.259-266

23. Ш.Т. Ишмухаметов [2002с]. О вложении счетных порядков в тьюринго-вые степени, Математические заметки, 72, 2002, N 5, с.682-687.

24. Ш.Т. Ишмухаметов, М.А. Мухин [2002d]. О распределении ассоциативных степеней разностей рекурсивно- перечислимых множеств, Тезисы докладов XIII Межд.конф. -"Пробл.теор.киберн.", Казань, 2002, с.79

25. Sh.T. Ishmukhametov [2002е]. On distribution of associated degrees, Annual European Colloquium of the Association for Symbolic Logic, Muenster, Germany, 2002, .p.36-37

26. Sh.T. Ishmukhametov [2003]. On a problem of Cooper and Epstein, J.Symb. Log, 68, 2003,N1, p.52-64

Подписано в печать 20.06.03. Формат 60x84/16. Усл.печ.л. 1,5. Тираж 100 экз. Заказ ШИ£Л

Отпечатано с оригинал-макета в лаборатории оперативной полиграфии Ульяновсокого государственного университета 432970, г.Ульяновск, ул. Л.Толстого, 42.

2оо?-4 *18953 Х

Введение.

Глава 1. Методы построения минимальных степеней

§1. Основные стратегии метода

§2. Дополнения рекурсивно перечислимых степеней в нижних конусах

§3. Дополнения произвольных степеней в нижних конусах.

§4. Дополнения в конусах, ограниченных низкими степенями.

§5. Эффективные минимальные покрытия рекурсивно-перечислимых степеней

Глава 2. Строгие минимальные покрытия и проблема Спектора

§1. Строгие минимальные покрытия о;-р.п. степеней.

§2. Степени, не имеющих строгих минимальных покрытий.

§3. Слабо рекурсивные степени и проблема Спектора.

§4. Слабые минимальные покрытия и построение изолированной степени.

• Глава 3. Начальные сегменты степеней. Метод вложения

§1. Вложение 3-элементой решетки и ромба.

§2. Методы представления конечных решеток.

§3.Специальные виды решеток.

§4. Вложение конечных решеток.

§5. Вложение счетных порядков в тьюринговые степени.

Глава 4. Относительная перечислимость тьюринговых степеней

§1. Открытые степени.

§2. Относительная перечислимость тьюринговых степеней

§3. Разложение р.п.степеней над заданной степенью.

§4. Построение высокой изолированной степени.

§5.0 дистрибутивности верхних полурешеток степеней ниже 0'.

Изучение структуры тьюринговых степеней является одной из наиболее значительных задач теории вычислимости. С самого начала зарождения этой теории, т.е. с начала 50-х годов, большое число ученых обращается к изучению структурного строения полурешетки тьюринговых степеней (или степеней неразрешимости), получая новые и новые результаты. Ряд проблем, поставленных еще в середине 50-х годов относительно распределения минимальных степеней и их покрытий, был решен сравнительно недавно, а некоторые вопросы не получили ответа и поныне. Одной из наиболее известных таких проблем, поставленной в 1956 году К.Спекто-ром, является проблема описания класса степеней, обладающих строгими минимальными покрытиями. Напомним, что степень а называется строгим минимальным покрытием (с.м.п.) для меньшей степени Ь, если для любой степени с из с<а следует, что с<Ь. Другой важной нерешенной проблемой является проблема Ейтса (С.E.M.Yates [1970]) о существовании с.м.п. у произвольной минимальной степени. Решение этих проблем позволило бы сделать существенный скачок в решении задачи описания начальных сегментов степеней неразрешимости.

Одной из важных предпосылок для дальнейшего продвижения в этой области является разработка автором диссертации нового метода построения минимальных степеней, который позволил соединить ряд методов, разработанных для изучения начальных сегментов степеней, с различными модификациями метода приоритета, включая метод приоритета с бесконечными нарушениями (т.е. методы уровня 0" и 0'" по классификации Р.Соара (R.Soare [1986]). Напомним кратко историю вопроса.

Первая конструкция минимальной степени принадлежит К.Спектору (C.Spector [1956]). Шенфильд (Shoenfield [1966]) ввел понятие деревьев, которое оказалось чрезвычайно полезным для формулировок и доказательств результатов о минимальных степенях и покрытиях и способствовало упрощению доказательства Спектора.

Определение. (Шенфильд [1966]). Деревом называется функция Т из множества 2<ш (т.е. из множества конечных последовательностей из 0 и 1, называемых строками) в множество 2<ш такая, что:

1. Т(а) | Аг С а Т(т) 4. определено А Т(т) С Т{а).

2. Если одно значение из пары Т(а * 0), Т(а * 1) определено, то определено и другое,и они несравнимы (будем использовать запись Т{р *

0)|Т(а*1)).

Дерево Т называется полным, если функция Т определена на любой строке т.

Строка принадлежит по определению дереву Т, если либо сама строка т, либо ее некоторое расширение принадлежит области значений функции Т. Множество А лежит на дереве Т, если каждый начальный сегмент характеристической функции А лежит на Т.

Переведенное на язык деревьев, доказательство Спектора основывается на двух нижесформулированных леммах, итерационное применение которых позволяет легко получить минимальную степень (полное доказательство можно найти в книге М.М. Арсланова [1986], стр.142, или учебнике П.Одифредди [1989]).

Лемма 1. Если Т-полное рекурсивное дерево и е-произвольное число, то существует полное рекурсивное поддерево Q дерева Т, такое что для любой бесконечное ветви А, расположенной на Q, А ф фе.

Лемма 2. Пусть Т-полное дерево, и е-произвольное число. Существует такое полное поддерево Q дерева Т, что для любого А, расположенного на Q, 0^-всюду определенная функция —>■ ф^-либо рекурсивна, либо А <т фе

Анализ доказательства Спектора показывает, что требуемые в леммах поддеревья 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), автор сравнивает силу различных методов построения минимальных степеней и делает заключение, что существующие методы не позволяют строить минимальную степень, не обладающую с.м.п. Следовательно, необходимы новые методы.

Один из новых подходов, предложенных автором диссертации, является изучение минимальных степеней и покрытий в рамках метода приоритета. Подробное описание этого метода, основных его идей, дается в первый параграфе диссертации. Формулировка основных определений приводится здесь не в традиционном стиле деревьев, как во всех ранее существовавших доказательствах о минимальных степенях, а в духе современного, разработанного А. Лахланом и J1. Харрингтоном подхода "дерева стратегий" к методу приоритета (подробному изложению этого подхода посвящена глава 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', aflb=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") что существует р.п. степень а такая, что в нижнем конусе D(< а-р.п.) некоторая р.п. степень Ь<а не дополняема вверх. Открытым остался вопрос о дополняемости минимальными степенями вниз. В работе [1986] Купер утверждает (доказательство не опубликовано), что в некотором конусе D(< а-р.п.) найдется промежуточная степень Ь<а (не обязательно р.п.) такая, что любая минимальная степень m лежащая ниже а находится также ниже Ь. Купер и Эпштейн (Cooper, Epstein [1987]) выдвинули гипотезу о том, что их теорема о дополняемости вниз низких степеней является наилучшим результатом в этом направлении. Эта гипотеза будет опровергнута в диссертации, и мы докажем, что для любых р.п. степеней 0<а<с найдется си- р.п. минимальная степень ш<с, несравнимая с а.

Этот результат полезно сравнить с теоремой Доуни и Стоба (R. Downey, М. Stob [1997]) о том, что в каждом нижнем конусе D(< а-р.п.) найдется р.п. степень Ь<а , не являющаяся частью минимальной пары в классе р.п. степеней (и, следовательно, также в классе n-р.п. степеней). По нашей теореме, в каждом таком нижнем конусе каждая промежуточная р.п. степень является частью минимальной пары в классе о;-р.п. степеней. Таким образом, наш результат завершает решение указанной проблемы.

Эта теорема решает также проблему Лахлана о распределении ветвящихся степеней в ограниченных сверху конусах D(< а-р.п.) для степени 0 (степень а называется ветвящейся, если она является наименьшей верхней гранью двух степеней ai и аг, aifia2 =а). Точнее говоря, по известной теореме Лахлана (A.Lachlan [1979]) степень 0 не является ветвящейся в некотором нижнем конусе D(< а-р.п.) (в классе р.п. степеней). Поскольку, под каждой нерекурсивной n-р.п. степенью для п G ш всегда найдется нерекурсивная р.п. степень, то можно заключить, что теорема Лахлана выполняется также для класса n-р.п. степеней. По нашей теореме, степень О является ветвящейся в классе cu-р.п. степеней в любом нижнем конусе D(< а-р.п.), и этот результат является наилучшим возможным. Таким образом, существует р.п. степень а такие, что элементарные теории р.п. степеней и cu-р.п. степеней в нижнем конусе 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]). Степень а является совокупно нерекурсивной, если для любой функции / К, где К-креативное множество, найдется функция g, рекурсивная в а такая, что g(n) > f(n) для бесконечно многих п.

Непосредственно из определения вытекает, что этот класс замкнут вверх. Авторы доказали также, что каждая степень а, не являющая GL2-низкой (т.е. удовлетворяющая свойству а" > (aUO')'), является с.н.степенью, однако существуют также низкие и low2-степени, являющиеся с.н. Наиболее важные теоретико-решеточные свойства этих степеней является то, что они замкнуты вверх, разложимы и дополняемы вверх к любым степеням, расположенных выше. Более сильным является утверждение, следующее из теоремы П.Фейера (Fejer [1989]), о том, что каждая рекурсивно представимая решетка с различными наименьшим и наибольшим элементами вложима в нижний конус D(<a), ограниченный произвольной с.н.степенью, с сохранением наибольшего и наименьшего элементов и решеточных операций. Следовательно, никакая с.н.степень не может ни сама быть с.м.п., ни обладать им. В частности, все степени, обладающие с.м.п., принадлежат GL2, а степени, находящиеся ниже 0', принадлежат -Z/2. Поэтому, все известные примеры вложений частично-упорядоченных множеств как начальных сегментов в тьюринговые степени имеют своими образами СХг-степени.

В главе II мы также исследуем вопрос о распределении степеней, обладающих с.м.п. среди степеней, содержащих множества из иерархии Ершова ([1968],[1970а], [1970b]). Напомним, что Купер (S.B.Cooper [1971],

1995]) построил р.п. степень, обладающую с.м.п. Кумабе (M.Kumabe [ta]) показал существование 1-генерической степени, обладающей с.м.п. Мы покажем (теорема Н.1.1.), что для каждого рекурсивного ординала а найдется собственная степень, содержащая множество из класса Е"1, обладающая с.м.п.

Возвращаясь к проблеме степеней, не обладающих с.м.п., мы дадим прямую конструкцию низкой р.п. степени, не обладающей с.м.п ниже О'. Существование таких степеней следует также неявно из вышеупомянутого результата Доуни, Джо куша и Стоба, однако они используют другую технику доказательства.

Также в этой главе мы определим новый класс степеней, названных слабо рекурсивными (weakly recursive) степенями и докажем, что каждая слабо рекурсивная степень обладает слабо рекурсивным строгим минимальным покрытием.

Определение.(Ишмухаметов [1999b]) Степень а называется слабо рекурсивной, если для любой функции f рекурсивной в а найдется слабая таблица (weak array) {W/,(„)}£L0 такая, что для каждого n е и :

1. |WMn)| < 2",

2. f(n) е wh(n),

3.x фу-> Wh{x) n Wh{y) = 0.

Непосредственно из определения следует, что класс слабо рекурсивных степеней замкнут вниз, т.е. для любых степеней а,Ь, если а<Ь и be WR, то и aG WR.

Если слабо рекурсивная степень а находится ниже 0', то каждая функция /, рекурсивная в а, является w-p.n., т.е. имеет рекурсивную аппроксимацию f(s,n) такую, что для каждого n |{/(s,n) : s € u>}\ < 2n. Поскольку произвольная р.п. степень а является ш-р.п. тогда и только тогда, когда а не является совокупно нерекурсивной (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, найдется р.р.п. степень b, a<b<d.

Заметим, что существование изолированной р.р.п. степени следует также из более раннего результата Кадах (D. Kaddah [1993],теорема 3.2), которая доказала, что каждая низкая р.п. степень является нижней гранью двух р.п. степеней (т.е. является ветвящейся в классе р.р.п. степеней), а по результату Фейера (P.Fejer [1982]) не каждая низкая р.п. степень является ветвящейся в классе р.п. степеней. Дальнейшее изучение р.р.п. степеней производится в IV главе диссертации.

Третья глава диссертации посвящена изучению начальных сегментов тьюринговых степеней ниже О'. В этой главе используя наш метод построения минимальных степеней и минимальных покрытий мы дадим новые доказательства теорем о вложениях различных конечных порядков в тьюринговые степени. Используя метод деревьев стратегий, наш метод позволил получить значительное упрощение этих технически сложных доказательств. Мы передокажем теоремы Сакса и Титгемайера о вложениях в D(<0 ') ромба и возрастающей линейной цепи, недистрибутивной решетки ЛГ5 и произвольной конечной решетки, имеющей конечную репрезентационную таблицу.

В пятом параграфе этой главы мы рассмотрим вопрос о вложении в D счетных линейных порядков. Пусть L - произвольная верхняя полурешетка. При ее вложении в D в качестве начального сегмента строится нижний конус D(<a), изоморфный L, причем строится отображение для каждого элемента а е L в некоторое множество А, представляющее тьюринговую степень, являющуюся образом элемента а. Спрашивается, а какова степень представления этого изоморфизма? Иначе говоря, если для для элементов a,b € L выполняется а < Ь, то как трудно найти алгоритм, сводящий соответствующее множество А к соответствующему В? В частности, если структура L вычислима, то можно ли найти сводящие алгоритмы рекурсивно? Эта проблема ранее не исследовалась, но неявно считалось, что ответ должен быть положительным. В параграфе 5 мы доказывает теорему, опровергающую в сильной форме, это мнение:

Теорема III.5.1.Пусть Р={Со > С! >с2 . >0}-униформная в 0' последовательность степеней. Найдется ненулевая степень с, находящаяся ниже каждой степени cn, п € со.

Непосредственно из этой теоремы вытекает, что если обратный линейный порядок и*— {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-степени.

В диссертации мы дадим новое доказательство теоремы Купера и Уая о существовании изолированных p.p.п. степенй. Наше доказательство, использующее идею ассоциативного множества для разности р.п. множеств, значительно проще оригинального доказательства Купера и Уая. Непосредственно из определения ассоцитивного множества В следует, что оно рекурсивно в р.р.п. множестве 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]). Для произвольного рекурсивного ординала а будем называть степень а собственной а-р.п. степенью, если а содержит а-р.п.множество и не содержит /З-р.п. множеств ни для какого /3 < а. Очевидно, что в классах 0-REA и l-REA-степеней для каждой степени d найдется наименьшая степень, относительно которых d перечислима, а именно, степень О. Рассмотрим первый нетривиальный класс 2-КЕА-степеней. Известно, что все р.р.п. степени являютя 2-REA, и, как доказано Джокушем и Шором в [1984], этот класс содержит собственые а-р.п. степени для каждого рекурсивного ординала а. Для произвольной степени d определим классы i?[d] и Q[d] как классы степеней, состоящих соответственно из р.п. степеней и всех степеней, относительно которых d перечислима. Вышеприведенные вопросы можно переформулировать следующим образом:

Имеют ли классы -R[d] и Q[d] наименьший элемент, минимальные элементы? Ограничены ли они снизу ненулевыми элементами? Ответы на эти вопросы даются в теоремах IV.2.1, IV.3.1 и IV.3.2. Мы покажем, что существует р.р.п. степень d, для которой класс i?[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' в классе ш-р.п. степеней. В параграфе 3 четвертой главы мы докажем наилучший результат в этом направлении, разложив 0' в классе 2-р.п. степеней.

В следующем параграфе мы докажем, что существует изолированная пара, состоящая из высокой р.р.п. степени и низкой р.п. степени. Этим мы ответим на один вопрос Купера и Уи, а также на вопрос, поставленный Гуохуа By (Huohua Wu, New Zealand). Пара, состоящая из высокой р.р.п. степени и I0W2- р.п. степени, была построена предварительно Гуохуа By, но затем Ишмухаметову удалось улучшить этот результат, и совместный результат был опубликован в журнале Archive for Mathematical Logic (Ishmukhametov, Wu [2002b]).

Наконец, в последнем параграфе диссертации мы рассмотрим вопрос о дистрибутивности верхних полурешеток степеней, образованных степенями по различным сводимостям, изучавшимся в теории вычислимости. Пусть г- произвольная сводимость. Обозначим через полурешетку р.р.п. г- степеней. В четвертом параграфе третьей главы мы исследуем эту полурешетку на предмет дистрибутивности для различных сводимос-тей г. Мы покажем, что в отличии от случая р.п. степеней структура является недистрибутивной для широкого класса сводимостей, промежуточных между bd-сводимостью (определение можно найти в книге Одиф-редди [1989]) и тьюринговой сводимостью. В этот класс попадают все табличные сводимости и часть строгих сводимостей. Это дает еще одно элементарное отличие полурешеток D^ и

1. М.М. Arslanov 1997]. Degree structures in local degree theory, Complexity, Logic and Recursion Theory (A.Sorbi, ed), Lect. Notes in Pure and Appl. Logic, v. 187, M. Dekker, New York, pp. 49-74

2. M.M. Arslanov, S. Lempp, R.A. Shore 1996]. Interpolating d.r.e. and REA degrees between r.e. degrees, Ann.Pure and Applied Logic, 78, 1996, pp.29-56

3. M.M.Arslanov, G.L. La Forte, T.A.Slaman 1998]. Relative enumerability in the difference hierarchy, J.Symb.Logic, v. 68, N2, 1998, pp. 411-420

4. S.B. Cooper 1971]. Degrees of Unsolvability, Ph.D. Thesis, University of Leicester, 1971.

5. S.B. Cooper 1973]. Minimal degrees and the jump operator, J. Symbolic Logic 38, pp. 249-271.

6. S.B. Cooper 1986]. Some negative results on minimal degrees below 0', item 353 (abstract), Recursive Function Theory Newsletter 34.

7. S.B. Cooper 1989] The strong anti-cupping property for recursively enumerable degrees, J.Symb.Logic, 54, 527-5399. 9. S.B.Cooper 1989]. Rigidity and Definability in the Noncomputable Universe, Preprint Series 1991, Leeds, N 17, 1-32

8. S.B.Cooper 1992]. A Splitting Theorem for the n-r.e.degrees. Proc.AMS, v.115, N 2, 1992, 461-471

9. S.B.Cooper 1993]. On a conjecture of Kleene and Post, Preprint Series 1993, N 7, Leeds, p.1-122

10. S.B. Cooper 1993] Rigidaty and definability in the non-computable universe, Log. Meth, Phil. Sci.9, 1994, p.209-235

11. S.B. Cooper 1995] Local degree theory, Handbook of Recursion Theory, North-Holland, chapt.4, p.121-153

12. S.B. Cooper 1996]. Strong minimal covers for recursively enumerable degrees, Math. Log. Quart., 42 (1996), pp.191-196

13. S.B. Cooper, R.L. Epstein 1987]. Complementing below recursively enumerable degrees, Ann. Pure Appl. Logic, 32, p. 15-32

14. S.B.Cooper, St.Lempp, P.Watson. 1988] Weak Density and cupping in the r.e.degrees, Preprint Series 1988, N 3, 1-11

15. S.B.Cooper, L.Harrington, A,Lachlan, S.Lempp, R.Soare 1991]. The d.r.e. degrees are not dense, Ann.Pure and App.Logic ,v.55, 1991, 125151

16. S.B. Cooper, and X. Yi 1993] Isolated d.r.e. degrees, Preprint Series, N 17, Math. Log. Quarterly, 1-27

17. D. Ding, L.Qian. ta]. A splitting property of d.r.e. degrees, to appear

18. R. Downey 1989]. D.r.e. degrees and the nondiamond theorem // Bull. London Math.Soc. 21, 1989, p.43-50

19. R. Downey 1993] Array nonrecursive degrees and lattice embeddings of the diamond, III. J. Math. 37 (1993), pp.349-374

20. R. Downey, M.Stob 1997]. Minimal pairs in initial segments of the recursively enumerable degrees, Isr.J.Math., 100, 7-27 (1997)

21. R. Epstein, R.Haass, R.Kramer 1981]. Hierarchies of sets and degrees below 0', Logic Year 1979-1980 (M. Lerman, J. Schmerl and R.Soare, editors), Lecture Notes in Mathematics, vol. 859, Springer-Verlag, Berlin, pp.32-48

22. R.L. Epstein 1975]. Minimal degrees of unsolvability and the full approximation construction, Memoirs Amer. Math. Soc.3, No. 162, Providence, R.I. 1975

23. R.L. Epstein 1979]. Degrees of Unsolvability: Structure and Theory, Lect. Notes in Mathematics 759, Springer-Verlag, Berlin, Heidelberg, New York, 1979

24. R.L. Epstein 1981]. Initial Segments of Degrees below 0', Memoirs Amer. Math. Soc., No. 241, Providence, R.L 1981

25. Y.L. Ersov, M.A. Taitslin 1963]. The undecibility of certain theories, Algebra i logika 2 1963, 37-41

26. P. Fejer 1982]. Branching degrees above low degrees, Trans. Amer.Math.Soc. 273, 1982, p. 157-180

27. P. Fejer 1989]. Embedding lattices with top preserved below non-GL2 degrees, Zeitschr.f.math. Logik und Grundlagen d.Math. 35 (1989), 527-539

28. E.M. Gold 1965]. Limiting recursion, J.Symb.Logic 30, 28-48

29. D.F. Hugill 1969]. Initial segments of Turing degrees, Proc. London Math. Soc. 19, 1-16

30. М. Lerman 1969]. Some nondistributive lattices as initial segments of the degrees of unsolvability, J. Symb. Log. 34, 85-98

31. M. Lerman 1971]. Initial segments of the degrees of unsolvability, Ann. Math. 93, 365-389

32. M. Lerman 1983]. Degrees of Unsolvability, Perspectives in Mathematical Logic, Omega Series, Springer-Verlag, Berlin, Heidelberg, London, New York, Tokyo.

33. A. Li, D.Yang 1998]. Bounding minimal degrees by computably- enumerable degrees, J.Symb.Log, 1998, 63, pp. 1319-1347

34. Martin D.A.1963]. A theorem on hyperhypersimple sets, J.Symb.Log. 28, 1963, pp. 273-278

35. P. Odifreddi 1989] Classical Recursion Theory, Studies in Logic and the Foundations of Mathematics, Vol. 125, North-Holland, Amsterdam, New York, Oxford, Tokyo.

36. D.B. Posner 1977] High degrees, Ph.D. Dissertation, University of California, Berkeley.

37. D.B. Posner 1981]. The upper semilattice of degrees >0' is complemented, J. Symb.Log. 46, pp. 705-713

38. D.B.Posner, R.W.Robinson 1981]. Degrees joining to 0', J. Symb.Log. 46, pp. 714-721

39. H. Putnam 1965] Trial and error predicates and the solution to a problem of Mostowski, J.Symb. Logic, 30, 49-57

40. J.G. Rosenstein 1968] Initial segments of degrees, Рас.J.Math. 24, 163-172

41. G.E. Sacks 1961]. A minimal degree less that 0', Bull. Amer. Math. Soc. 67, 416-419

42. G.E. Sacks 1963]. Degrees of Unsolbability, Annals of Math. Studies 55, Princeton Univesity Press, N.J., 1963

43. L. Sasso 1974]. A minimal degree not realizing least possible jump, J. Symb.Logic, 39, 1974, p.p.571-573

44. D. Setapun, T.A. Slaman 1992]. Minimal complements, unpublished manuscript.

45. J.R. Shoenfield 1966]. A theorem on minimal degrees, j.Symb.Log. 31, 539-544

46. R.A. Shore, T.A. Slaman 1990] Working below a low2 recursively enumerable degree, Archive for Math, logic 29, 201-211

47. T.A. Slaman, W.H.Woodin 1986] Definability in the Turing degrees, Illinois J. Math. 30, 320-334

48. T.A. Slaman and J.R. Steel 1989]. Complementation in the Turing degrees, J.Symb. Logic, 54, 160-176

49. R.I. Soare 1987] Recursively Enumerable Sets and Degrees, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, Heidelberg, London, New Yourk, Paris, Tokyo. 437p, 1987.

50. R.I. Soare, M. Stob 1982]. Relative recursive enumerability, Proceedings of the Herbrand Symposium Logic Colloquium'81 (J. Stern,ed.), North-Holland, Amsterdam, New York, Oxford.

51. C.Spector 1956] On degrees of recursive unsolvability, Ann. of Math. 64, pp. 581-592

52. D. Titgemeyer 1962]. Untersuchen uber die Struktur des Kleene-Postchen Halbverbandes des Grade der rekursiven Unlosbarkeit, Arch.Math. Logik Grundlagenforsch. 8/1-2 (1962), p. 45-62

53. C.E.M. Yates 1970] Initial segments of the degrees of unsolvability, Part II: Minimal degrees, J.Symb.Log. 35 (1970) pp. 243-266ПУБЛИКАЦИИ на русском языке:

54. М.М. Арсланов 1985]. Структурные свойства степеней ниже О', ДАН СССР, 1985, т.283, No 2, с.302-309

55. М.М.Арсланов 1986]. Рекурсивно перечислимые мнжества и степени неразрешимости, Изд-о Казан.унив. 1986, 205 стр.

56. М.М.Арсланов 1987]. Локальная теория степеней неразрешимости и Аз-множества, Изд-о Казан.унив. 1987, 139 стр.

57. Н.Р. Бухараев 1981]. О Т-степенях разностей рекурсивно перечислимых множеств, Известия вузов.Математика, 1981, No 5, с.40-49

58. А.Н. Дегтев 1979а]. О сводимостях табличного типа, Успехи мат. наук, 1979, 34, No 3, с.137-168

59. А.Н. Дегтев 1979Ь]. Несколько результатов о верхних полурешетках и m-степенях, Алгебра и логика, Новосибирск, 18, 1979, N 6, с. 664-679

60. Ю.Л. Ершов 1968а]. Об одной иерархии множеств, Алгебра и логика, 7, N 1, стр.47-73

61. Ю.Л. Ершов 1968Ь]. Об одной иерархии множеств, Алгебра и логика, 7, N 4, стр. 15-47

62. Ю.Л. Ершов 1970]. Об одной иерархии множеств, Алгебра и логика, 9, N 1, стр.34-51

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

64. В.Л. Селиванов 1985]. Об иерархии Ершова, Сибир.матем.журнал, 36, No 1, 134-149ПУБЛИКАЦИИ автора, использованные в диссертации.

65. Ш.Т. Ишмухаметов 1983]. О классах разностей рекурсивно перечислимых множеств, Изв.вузов.Матем. 1983, N3, с.78-79

66. Ш.Т. Ишмухаметов 1985]. О разностях рекурсивно перечислимых множеств, Изв.вузов.Матем. 1985, N8, с.3-12

67. Ш.Т. Ишмухаметов 1986]. Разности рекурсивно перечислимых множеств, их степени неразрешимости и индексные множества, Диссертация на соискание степени кандидата физико-математических наук, Новосибирск, 1986, 105 с.

68. Sh Т. Ishmukhametov 1989]. Intervals in the structure of T-degrees below 0', Abstracts of European Logic Colloquium, Berlin, 1989

69. Ш.Т. Ишмухаметов 1990]. Одна теорема о разностях рекурсивно перечислимых множеств, Деп.в ВИНИТИ, N 2423-В90, 1990, 7 с.

70. Sh Т. Ishmukhametov 1990]. Numerations of differences of recursively enumerable sets, Abstracts of Logic Biennial, Varna, Bulgaria, 1990, 1 P

71. Ш.Т. Ишмухаметов 1992]. О разложении степени 0' на меньшие степени, содержащие разности рекурсивно перечислимых множеств. Тезисы докладов XI Международной конференции по математической логике, Казань, 1992

72. Ш.Т. Ишмухаметов 1993]. О дистрибутивности верхних полурешеток степеней ниже 0'. Изв.вузов.Матем. 1993, N1, с. 17-20

73. Ш.Т. Ишмухаметов 1994]. О разложении степени 0' на меньшие степени, содержащие разности рекурсивно перечислимых множеств. Изв.вузов.Матем. 1994, N1, с.19-23

74. Sh Т. Ishmukhametov 1996а] The splitting theorem above a r.e.degree, Фундаментальные проблемы математики и механики, вып.1, часть 2, изд-о Ульянов, госуниверситета, 1996, стр.139-143

75. Ш.Т. Ишмухаметов 1996b]. О точных n-р.п. степенях. Тезисы докладов XI Международной конференции по проблемам теоретической кибернетики, Ульяновск, 1996, с.80

76. Sh Т. Ishmukhametov 1997] On enumerability of d.r.e. degrees in lesser ones, Abstracts of European Logic Colloquium, Leeds, 1997

77. Sh T. Ishmukhametov 1998]. On degrees without strong minimal covers, Фундаментальные проблемы математики и механики, вып.2, изд-о Ульянов, госуниверситета, 1998, 25-31

78. Ш.Т. Ишмухаметов 1999а]. О начальных сегментах степенй неразрешимости. Тезисы докладов XII Международной конференции по проблемам теоретической кибернетики, Нижн. Новгород, 1999, с.90

79. Sh Т. Ishmukhametov 1999b]. Weak recursive degrees and a problem of Spector, de Gruyter Series in Logic and Its Applications, v.2, Berlin, New-York, стр.81-87

80. Sh T. Ishmukhametov 1999c]. On embeddings of linear orderings as initial segments of Turing degrees, Тезисы докладов международной конференции по математической логике, Новосибирск, 1999, стр.8788.

81. Sh Т. Ishmukhametov 1999d]. On the r.e. predecessors of d.r.e.degrees, Archive for Math. Logic, 38, Springer-Verlag, pp.373-386

82. Sh T. Ishmukhametov 2000a]. On relative enumerability of Turing degrees, Archive for Math. Logic,39, 2000, p.145-154

83. Sh T. Ishmukhametov 2000b]. Embeddings into Weakly Recursive degrees, Тез.докл. междун.конф."Логика и приложения", Новосибирск, 2000 г., с. 118

84. Sh. Т. Ishmukhametov, Huohua Wu 2001], A High d.c.e.degree isolated by a Low c.e. degree, 2001 Annual meeting of the Assoc. for Symb. Logic, Philadelphia, USA, The Bulletin of Symbolic Logic, v.7, n.3, 2001, c.432-433

85. Ш.Т. Ишмухаметов. 2002а]. О начальных сегментах степеней неразрешимости, Фундаментальные проблемы математики и механики, Ульяновский государственный унив-т, 11, 2002, вып. 1, с. 78-94

86. Sh.T. Ishmukhametov, Huohua Wu2002b], Isolating pairs and the Hi/Low hierarchy, Archive for Math.Logic, 41, Springer-Verlag, 2002, p.259-266

87. Ш.Т. Ишмухаметов 2002с]. О вложении счетных порядков в тьюринговые степени, Математические заметки, 72, 2002, N 5, с.682-687.

88. Ш.Т. Ишмухаметов 2002d]. О распределении ассоциативных степеней разностей рекурсивно- перечислимых множеств, Тезисы докладов XIII Межд.конф. -"Пробл.теор.киберн.", Казань, 2002, с.79

89. Sh.T. Ishmukhametov 2002е]. On distribution of associated degrees, Annual European Colloquium of the Association for Symbolic Logic, Muenster, Germany, 2002, p.36-37

90. Sh.T. Ishmukhametov 2003]. On a problem of Cooper and Epstein, J.Symb.Log, 68, 2003,N1, p.52-64

91. S.B.Cooper, Sh.T. Ishmukhametov, A.Li ta]. Complementing com-putably enumerable degrees in lower cones, готовится к печати, 15 P

92. Sh.T. Ishmukhametov ta2]. Minimal covers for Turing Degrees, monograph, готовится к печати, 180 pp.