Минимальные покрытия тьюринговых степеней тема диссертации и автореферата по ВАК РФ 01.01.06, доктор физико-математических наук Ишмухаметов, Шамиль Талгатович

• Ишмухаметов, Шамиль Талгатович
• доктор физико-математических наук
• 2003

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

Введение.

Глава 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^ и

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

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.