Свойства квази-сводимости и иерархии Ершова тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

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

0034617Э5

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

01.01.06 - математическая логика, алгебра и теория чисел

Автореферат

диссертации на соискание ученой степени кандидата физико-математических паук

1 2 ФЕЕ) ?ппд

Казань — 2008

003461795

Работа выполнена на кафедре алгебры государственного образовательного учреждения Высшего профессионального образования "Казанский государственный университет им.В.И.Ульянова-Ленина".

Научный руководитель: доктор физико-математических наук, профессор

Арсланов Марат Мирзаевич

Официальные оппоненты: доктор физико-математических наук, профессор

Ишмухаметов Шамиль Талгатович, кандидат физико-математических наук, додент Фролов Андрей Николаевич.

Ведущая организация : государственное образовательное учреждение

высшего профессионального образования Новосибирский государственный университет

Защита состоится ^12 М/) РТА 2009 года в^'^часов на заседании Диссертационного совета Д 212.081.24 при ГОУВПО Казанский государственный университет им.В.И.Ульянова-Ленина по адресу: 420008, г. Казань, ул. Кремлевская, д. 35.

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

Автореферат разослан " " 2009 г.

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

диссертационного совета Д 212.081.24 к.ф.-м.н., доц.

Еникеев А.И.

Актуальность темы.

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

Квази-сводимость (Q-сводимость) была введена Тенненбаумом как один из примеров сводимости, отличающейся от Т-сводимости на классе вычислимо перечислимых множеств. Q-сводимость является естественным обобщением много-одной сводимости (m-сводимости) и следующим образом связана со сводимостью по перечислимости (е-сводимостыо): если множество А квази-сводится к множеству В, то и — А е-сводится к множеству ш — В. Кроме этого, на в.п. множествах Q-сводимость влечёт Т-сводимоеть, по не совпадает с ней.

Комбинаторные свойства Q-сводимосги и ее различные модификации широко изучались Оманадзе1. Соловьев2 показал, что кобескопсчпое в.п. множество является гипергиперпростым тогда и только тогда, когда оно не содержится пи в одном Q-полном в,п. множестве. Гилл и Морис1 доказали, что в.п. множество является субкреативпым тогда и только тогда, когда оно является (^-полным. Булитко4 изучал другие критерии Q-полноты в.п. множеств. Селиванов5 установил связь Q-сводимости с иерархией Клини-Мостоиского. Наиболее известным результатом в этой области стало решение Марчепковым® с помощью свойств Q-сводимости известной проблемы Поста о существовании неполной невычислимой в.п.

'Omanadze R.Sh. Quasi-degrees of recursively enumerable sets // Computability and models: perspectives east, and west (Cooper S.B. and Gonchamv S.S. (eds.)). - Kluwer Academic/Plenum Publishers, 2003. - P. 289-319.

2Солош>en В.Д. Q-сводимость и гинергнперпростые множества //Веронтн. методы и киберн. -Казань: изд-но КГУ. - 1974. - цып.11. - С. 121-128.

3Gill J.Т., Morris Р.Н. Ori subcreative sets and S-reducibility // J. Symbolic Logic. 1971. V.39. №4. - P. 069-077.

4Булитко B.K. О способах характеризации полных множеств // ¡I'm. АН СССР. Серии математическая. - 1991. - Т.55. - №2. - С. 227-253.

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

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

степени.

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

Позже Макинтайр8 показал, что для любых вычислимо представи-мых групп G и Я, проблемы равенства слов в которых имеют степени g и h соответственно, если g <т h, то G является подгруппой любой алгебраически замкнутой группы, подгруппой которой является и Я. Белеградек0 показал, что обратное неверно, но становится верным, если Т-сводимость заменить на Q-сводимость. Он показал, что для любых вычислимо представимых групп G и Я, если G является подгруппой любой алгебраически замкнутой группы, подгруппой которой является Я, то проблема равенства слов в группе G квази-сводится к проблеме равенства слов в группе Я. Из этих результатов следует, что получение любых результатов о структуре в.п. Q-степеней дает одновременно результаты о свойствах классов конечно порожденных подгрупп алгебраически замкнутых групп.

Изучение алгебраической структуры Q-степеней в.п. множеств было начато Фишером и Амбос-Шпиесом10, которые показали, что верхняя полурешетка в.п. Q-степепей не является дистрибутивной и не является решеткой. Первые серьезные факты об этой структуре получили До-уни, Лафорт и Ниес", которые изучили вопросы существования нижних граней в упорядочении Q-степеней, доказали теорему плотности в.п. Q-

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

"Macintyre A. Omitting quantifier free types in generic structures // J. Symbolic Logic. - 1972. - V.37.

- P. 512-520.

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

- С. 239-255.

'"Fischer P., Ambos-Spies К. Q-degrees of r.e. sets // J. Symb. Logic. - 1987. - V.52. - A4. - P. 317.

"Downey R., LaForte G.L., Nies A. Computably enumerable sets and Quasi-reduribility ,/,/ Ann. of Pure and Applied Logic. - 1998. - V.95. - P. 1-35.

степеней и показали, что 7Zq имеет неразрешимую теорию первого порядка. Изучение алгебраической структуры Q-cтепеней п-в.п. множеств было начато Арслановым и Оманадзе12, которые исследовали ряд фундаментальных свойств этой структуры.

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

В уже ставших классическими работах Ю.Л. Ершов13 построил иерархию множеств, расположенных ниже 0', теперь известную в литературе как "иерархия Ершова". Место множества А в иерархии определяется по количеству изменений в аппроксимиции множества. Как оказалось, возникающая иерархия множеств исчерпывает всю совокупность множеств, расположенных по тыоринговой сводимости ниже 0'. Каждый следующий уровень иерархии содержит все предыдущие, но не совпадает ни с одним из них.

Различные свойства иерархии Ершова широко изучались Арслановым, Джокушем, Крамером, ЛаФортом, Лемппом, Селивановым, Слама-ном, Соловеем, Соаром, Хаасом, Шором, Энштейном14 и другими.

В своей работе Арсланов, ЛаФорт и Сламап15 доказали, что если В € Д"1, С - в.п. относительно некоторого А <т С и В <т С, то существует такое множество D £ Ej1, что В <т D <т С. Этот результат показывает, что для любого п > 1 степень п-в.п. множества, которая является вычислимо перечислимой относительно некоторой в.п. степени, лежащей ниже ее, является 2-в.п. степенью. Таким образом, относитель-

12Arslariov М.М., Omanadze R.Sh. Q-degrees of ii-c.e. sets // Illinois Journal of Mathematics - 2007. - V.51. - JVM. - P. 1189-1206.

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

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

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

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

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

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

Цель работы.

Целью настоящей работы является:

1. Изучение критериев <5-полноты множеств.

2. Изучение алгебраической структуры <2-степеней, в частности, вопросов изолированности и неизолированное™ степеней, расщепляемости степеней, дополняемости степеней наверх и вниз.

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

Методы исследования.

В диссертационной работе используются методы теории вычислимости. При доказательстве теорем 6, 7, 8, 9,13,14,16 и 18 используется метод приоритета с конечными нарушениями (метод О'-приоритета). При доказательстве теорем 6, 7 и 9 наряду с методом приоритета используется также метод разрешения Ейтса, адаптированный автором для <3-сводимости.

Основные результаты диссертации.

1) Доказано, что в.п. множество А является (^-полным тогда и только тогда, когда существует такая функция без неподвижных точек / А, что множество В¡^ = {з^^ф) ^ А} - в.п., где д(х) - функция из определения квази-сводимости функции к множеству.

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

3) Доказаны плотность неизолированных снизу 2-ii.ii. (^-степеней в структуре в.11. Q-степеней и плотность вниз неизолированных сверху 2-в.и. Q-степеней в структуре в.п. Q-степеней.

4) Доказано, что расщепляемые 2-в.н. Q-стспсии существуют под каждой ненулевой 2-в.п. Q-степенью и над каждой неполной в.п. Q-стспеныо.

5) Результат Арсланова, ЛаФорта и Сламана рслятивизирован на бесконечные уровни иерархии Ершова и доказана невозможность усиления условий его релятивизации.

Научная новизна.

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

Теоретическая и практическая значимость.

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

Апробация результатов.

Результаты диссертации докладывались

о на международной конференции "Logic Colloquium 2005" (Афины,

Греция, 2005 г.);

о на международной конференции "Мальцевские чтеиия-2005" (Новосибирск, 2005 г.);

о па международной конференции "Logic Colloquium 2006" (Неймеген, Нидерланды, 2006 г.);

о на международной конференции "Logic Colloquium 2007" (Вроцлав, Польша, 2007 г.);

о па научных семинарах и итоговых конференциях кафедры алгебры и математической логики Казанского государственного университета им. В.И. Ульянова-Ленина (2005-2008 гг.).

Публикации.

Основные результаты опубликованы в трех статьях [ll-[3] и четырех тезисах [4]-[7], список которых приведен в конце автореферата. Результаты, полученные в совместной с научным руководителем и профессором Оманадзе работе [3], принадлежат авторам в равной мере.

Структура и объем работы.

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

Содержание работы.

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

Первая глава посвящена изучению ф-полных множеств и алгебраической структуры ^-степеней.

В §1.1. изучаются критерии Е^-ф-полноты, Ез-ф-полноты и Е!|-(2-полноты множеств. Вводится определение квази-сводимости функции к множеству, оказывающееся очень удобным для формулирования критериев (2-полноты. Основным результатом параграфа является доказательство следующего критерия квази-полноты множеств:

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

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

2) существует функция / <<з А такая, что (\/х)(\¥х Ф 1'Уд*)) множество В[<а = {х\\¥я(х) С А} - в .п.

Следствие 1. В.п. множество А <2-полно тогда и только тогда, когда (3/ <д Л)(Ух)(И/2: ф ^¡(х)) и множество В ¡а - в.п.

Доказательство этого результата релятивизируется па другие уровни арифметической иерархии для доказательства критериев Е^-полноты и Ед-полноты множеств:

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

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

2) существует функция / <д А такая, что (Ух)(\№х ф И^.)) и мио-

жество Bf^ является .

Следствие 3. ^-множество А — Q-полно тогда и только тогда, когда (3/ <q Ä)(Vx)(Wx ф Wf(x)) и множество BftA £ Е"-

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

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

2) существует функция f <q А такая, что (\fx)(Wx фт Wf^) и множество Bf A является £3.

Следствие 4. -множество А Е° — Q-полно тогда и только тогда, когда (3/ <q A)(yx){Wx ф W/(z)) и множество Bf A £ Е3.

Также этот параграф содержит приложение полученного критерия к теории сложности, где через К(х) обозначается беспрефиксная Колмо-горовская сложность:

Теорема 5. Множество К = {(z,n)| х 6 2<ш,п £ и>,К(х) < п} является Q -полным.

В §1.2. изучается вопрос существования изолированных 2-в.п. Q-степеней. Основным результатом параграфа является теорема о существовании изолированных одновременно и сверху, и снизу 2-в.п. Q-степеней: Теорема 6. Для каэ/сдой пары в.п. степеней а <q b существует собственно 2-в.п. степень d, а <q d <q Ь, такая что а изолирует d снизу и b изолирует d сверху.

Получено интересное следствие этой теоремы, наглядно показывающее отличие полурешетки Q-степеней от полу решетки Т-степеней.

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

В §1.3. продолжается изучение вопроса, затронутого в параграфе §1.2., а именно изучается вопрос существования неизолированных 2-в.п. степеней. Основными результатами этого параграфа является доказательство плотности неизолированных снизу 2-в.п. Q-степеней в структуре в.п. Q-степеней, и доказательство плотности вниз неизолированных сверху 2-

п.п. (З-степеней в структуре в.п. (З-степеней:

Теорема 7. Для каждой пары в.п. апепсией V <ц и существует такая собственно 2-е.п. степень с!, что V <(^ с! <д и, и для любой в.п. степени \у, если у/ <ц (1, то найдется в.п. степень а <д с! такая, что а ■¿(^ .'

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

Теорема 9. Для каэ/сдой в.п. степени у > 0 существует такая собственно 2-е.п. степень с!, что с! <ц V, и для любой в.п. степени V/ найдется в.п. степень а такая, что с1 <с$ а и с1 <^ лу —> ¿ц а.

Следствие 8. Неизолированные сверху 2-е.п. <3-степени, плотны вниз в структуре в.п. -степеней.

Также в этом параграфе построен пример 2-п.п. ^-степени, которая не изолируется снизу не только никакой в.п. (^-степенью, а, вообще, никакой <3-степенью.

Теорема 8. Существует такая собственно 2-е.п. степень с1, что для любой Ь <(з с1 найдется в.п. степень а с1 такая, что а -¿ц Ь.

В §1.4. изучаются другие фундаментальные свойства алгебраической структуры (З-степеней: раацепляемость, дополняемость наверх и дополняемость вниз. В этом параграфе показано, что расщепляемые 2-в.п. <3-степени существуют под каждой 2-в.п. (^-степенью а > 0 и над каждой в.п. <Э-степенью Ь < О'

Теорема 13. Пусть А и В - такие в.п. множества, что А — В 0. Тогда А является непересекающимся объединением таких в.п. мноэ/сеств и Ах, что А^ — В <д А — В и А^ — В ¿д А\_х — В, г = 0,1.

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

Теорема 14. Пусть А - такое в.п. множество, что К -¿.д А. Тогда существуют такие не вычислимые в.п. множества Лц и А^, что

A(BAq A(BA\, A® Ai ¿q ЛфЛо и Aq и A\ образуют минимальную пару о о. п. Q -степенях.

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

Также показано, что каждая П" Q-степень а, 0 < а < 0', образует минимальную пару в в.п. степенях с некоторой Д® Q-степенью Ь, несравнимой с а. Тем самым показано, что каждая П" Q-степень является дополняемой вниз в в.п. Q-стспенях.

Теорема 15. Для каждого П® -множества А, 0 <q A <q 0', существует такое А^-мноэ/се.ство В, 1mío A\qB и для всех в.п. множеств X, если X <Q А&Х <Q В, тогда X <q 0.

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

Теорема 16. Существует такое в.п. множеством A <q К, что для всех невычислимых в.п. множеств We существует такое певычис-лимое в.п. множество Хе, что Хе <q А и Хе <q we.

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

В этой главе дается исчерпывающий ответ на возможные релятивизации результата Арсланова, ЛаФорта и Сламана па классы множеств i где vn(ri > 1) - произвольные обозначения клипиевской системы для и>п соответственно.

Доказано, что этот результат может быть релятивизировап в следующей форме:

Теорема 17. Для любого п > 1 если |v|o = wn+l, В £ Д"1, А -в.п., В <т А ф WA, то существует такое множество D е Sj1, где c<0v и |с|0 = что В <Т D <Т A® WA.

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

Также доказаны теоремы, дающие отрицательные ответы па следующие вопросы о дальнейших возможных обобщениях этой теоремы:

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

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

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

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

Следствие 14. Для любого п > 0 если |а|о = соп+1, то существует множество В £ Д~1, вычислимо перечислимое относительно некоторого в.п. множества А <х В, такое, что (Ve b)(VC £ Е(Г1)(Б фт С). где b <о а и \b\o = .

Теорема 19. Пусть \v\o = тогда существует множество В 6 Дщ1, вычислимо перечислимте относительно некоторого в.п. множества А <т В, такое, что (V6 <о v)(VC £ Е(~1)(Б фт С).

Автор выражает глубокую признательность своему научному руководителю Арсланову Марату Мирзаевичу за постановку задач, интерес к исследованиям автора и поддержку в работе.

Публикации автора по теме диссертации в ведущих рецензируемых научных журналов, входящих в список ВАК

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

[2 ] Batyrshin I.I. Quasi-completeness and functions without fixed-points // Mathematical Logic Quarterly - 2006. - V.52. - №6. - P. 595-601.

[3 I Arslanov M.M., Batyrshin I.I., Omanadze R.Sh. Structural properties of Q-degrees of n-c.e. sets // Annals of Pure and Applied Logic. - 2008. - V.156. - P. 13-20.

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

Публикации автора no теме диссертации в журналах и изданиях, не входящих в список ВАК

[5 ] Batyrshin I.I. Relative enumerability in the Ershov's hierarchy // Logic Colloquium 2005. Book of abstracts. - Athens. - 2005. - P. 49.

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

[7 ] Batyrshin I.I. The algebraic structure of Quasi-degrees /'/ Logic Colloquium 2007. Book of abstracts. - Wroclaw. - 2007. - P. 35.

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

12

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

17

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

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

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

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

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

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

18

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

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

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

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

В).

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

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

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

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

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

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

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

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

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

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

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

20

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

31. Arslanov M.M. Truth-table complete computably enumerable sets // Computability and models: perspectives east and west (Cooper S.B. and Goncharov S.S. (eds.)). Kluwer Academic/Plenum Publishers, 2003. - P. 1-10.

32. Arslanov M.M., Cooper S.B. and Kalimullin I.Sh. Splitting properties of total enumeration degrees // Algebra and Logic. 2003. - V.42. - №1. - P. 3-25.

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

34. Arslanov M.M., Lempp S., Shore R.A. On isolating r.e. and isolated d-r.e. degrees // Computability, enumerability, unsolvability (Cooper S.B., Slaman T.A. and Wainer S.S. (eds.)). Cambridge University Press, 1996. - P. 61-80.

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

36. Bennett C.H. Logical depth and physical complexity // The universal Turing Machine. A Half-Century Survey (R. Herken (ed.)). Oxford: Oxford University Press, 1988. - P. 227-258.

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

38. Downey R., LaForte G.L., Nies A. Computably enumerable sets and Quasi-reducibility // Ann. of Pure and Applied Logic. 1998. - V.95. - P. 1-35.

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

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

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

42. Jockusch C.G., Lerman M., Soare R.I., Solovay R.M. Recursively enumerable sets modulo iterated jumps and extensions of Arslanov's completeness criterion // J. Symbolic Logic. 1989. - V.54. - P. 1288-1323.

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

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

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

46. Omanadze R.Sh. Quasi-degrees of recursively enumerable sets // Computability and models: perspectives east and west (Cooper S.B. and Goncharov S.S. (eds.)). Kluwer Academic/Plenum Publishers, 2003. - P. 289319.

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

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

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

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

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

52. Arslanov M.M., Batyrshin I.I., Omanadze R.Sh. Structural properties of Q-degrees of n-c.e. sets // Annals of Pure and Applied Logic. 2008. - V.156. -P. 13-20.

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

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

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

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

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