Тьюринговые скачки в иерархии Ершова тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

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

/У

Файзрахманов Марат Хайдарович

Тьюринговые скачки в иерархии Ершова

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

Автореферат

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

2 4 ОЕЗ Ш

Казань - 2011

4856102

Работа выполнена на кафедре алгебры и математической логики Федерального государственного автономного образовательного учреждения высшего профессионального образования "Казанский (Приволжский) федеральный университет ".

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

доцент Калимуллин Искандер Шагитович,

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

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

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

высшего профессионального образования "Новосибирский государственный университет". Защита состоится «17» февраля 2011 г. в 14.30 на заседании диссертационного совета Д 212.081.24 при ФГАОУВПО "Казанский (Приволжский) федеральный университет" по адресу: 420008, г. Казань, ул. Кремлевская, д. 35., конференц-зал библиотеки им. Н. И. Лобачевского.

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

Автореферат разослан « (4 » 2011 г.

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

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

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Одним из важных понятий в теории вычислимости является понятие низкого множества, которое, интуитивно, выражает, что множество слабо вычислимо. Это связано с тем, что при изучении алгоритмических свойств множеств натуральных чисел часто возникает вопрос, при отсутствии подходящего вычислимого множества, о нахождении низкого множества, удовлетворяющего данному свойству. Например, согласно с теоремой Джокуша и Соара о низком базисе1, каждый непустой класс содержит низкое множество; по теореме Амбос-Шпииса, Джокуша и других2, каждая быстро простая степень имеет низкое дополнение наверх. С другой стороны, существует большое количество литературы, посвященной низким множествам и их свойствам, которые напоминают свойства вычислимых множеств. Например, Соар3 установил, что решетка вычислимо перечислимых (в.п.) надмножеств низкого в.п. множества изоморфна решетке всех в.п. множеств; согласно с теоремой Робинсона4, теорема Сакса о разложении справедлива в верхнем конусе любой низкой в.п. степени.

Множество А называется низким, если A' 0'. Таким образом, оператор скачка не может различать вычислимые и низкие множества. В известной

'jockusch С. G., Soare R. I. П°-classes and degrees of theories. // Trans. Amer. Math. Soc. - 1972. - V. 173. - P. 33-56.

3Ambos-Spies K., Jockusch C. G., Shore R. A., Soar« R. I. An algebraic decomposition of the recursively enumerable degrees and the coincidence of several degree classes with the promptly simple degrees, tl Transaction of the American Mathematics Society - 1984. - V. 281. - P. 109-128.

3Soare R. Automorphisms of the lattice of recursively enumerable sets Part 11: Low sets. // Annals of of Math. Logic.

- 1982.-V. 22-P. 69-107.

'Robinson R W. Jump restricted interpolation in the recursively enumerable degrees. II Annals of Math. - 1971. -V. 93.-P. 586-596.

работе Бикфорда и Миллса5 введено понятие супернизких множеств, которое естественным образом усиливает понятие низких множеств: множество А называется супернизким, если А' =„ 0'. Стандартное построение низкого простого множества уже дает супернизкое множество (как и теорема о низком базисе). Однако не каждое низкое множество является супернизким. Одним из следствий теоремы Сакса о разложении6 является существование таких низких в.п. множеств Aq, Alt что Ао Г\А\ = 0 и Аа U А\ — &. Согласно с результатом Бикфорда и Миллса7, одно из таких множеств Ао, А\ не супернизкое. Более того, Доуней, Гринберг и Вебер8 установили, что упорядоченные множества низких в.п. и супернизких в.п. степеней не элементарно эквивалентны.

В работах Ершова9 построена иерархия множеств А < j- 0', исчерпывающая весь класс множеств А ^ 0' и получившая в литературе название "иерархия Ершова". Каждый следующий уровень иерархии содержит все предыдущие и не совпадает ни с одним из них. В представленной работе изучаются новые усиленные понятия низких множеств, а именно множества, тьюринго-вые скачки которых лежат в фиксированных бесконечных уровнях иерархии Ершова. По результату Карстенса10, множества А из первого бесконечного (А'1-) уровня иерархии Ершова характеризуются условием А 0'. Поэтому первым уровнем такой иерархии скачков будет класс супернизких множеств.

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

sBickford М., Mills F. Lowness properties of r.e. sets // Manuscript, UW Madison. - 1982.

'Sacks G. E. On the degrees less than V II Ann. of Math. - 1963. - V. 2. - № 77. - P. 21) -231.

7там же

'Downey R., Greenberg N., Weber R. Totally ю-computable enumerable degrees and bounding critical triples II J. Math. Logic - 2007. - V. 7. - № 2. - P. 145-171.

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

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

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

'"Carstens Н. G. A^-mengen. II Arch.Math.Log.Gnmdlagenforsch. - 1976. - V. 18. - P. 55-65.

структурных свойств низких тьюринговых и е-степеней.

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

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

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

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

2. Установлено наличие ^'-вычислимой нумерации у семейства всех супернизких множеств.

3. Установлено существование низкой в.п. степени, неразложимой на супернизкие в.п. степени.

4. Доказано, что никакая низкая Ilf-e-степень не имеет полных дополнений в локальной структуре степеней по перечислимости.

Апробация работы.

По результатам диссертации были сделаны доклады:

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

• на международной конференции "Logic Colloquium 2009" (София, Болгария, 2009 г.);

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

• на международной конференции "Воображаемая логика Н.А. Васильева и современные неклассические логики" (Казань, 2010 г.)

• на научных семинарах и итоговых конференциях кафедры алгебры и математической логики Казанского (Приволжского) федерального университета 2007-2010 гг.

Публикации. Основные результаты опубликованы в работах [1]-[5]

Личный вклад автора. Основные результаты диссертации получены автором. Результаты §3.2 получены совместно с И. Ш. Калимуллиным [4] в процессе нераздельного сотрудничества.

Структура и объем диссертации. Диссертационная работа ихчожена на 91-й странице и состоит из введения, трех глав, разделенных на параграфы, и списка литературы, содержащего 50 наименований.

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

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

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

В §1.1 приведены определения уровней иерархии Ершова и их основные свойства. Пусть {О, <о) - клиниевская система обозначений для конструктивных ординалов.

Определение 1. Пусть дано обозначение а & О. Множество А принадлежит Б*1-уровню иерархии Ершова, если существует частично вычислимая функция от двух переменных $ такая, что х е А тогда и только тогда, когда т}г(Ь,х) | для некоторого Ь <о а и х) = 1 для <о-наименыиего элемента ¿о множества {х : х <0 а].

Определим П~ [- и Л~х-уровни, полагая

П~1 = {А:АеЕ;1},

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

Определение 2. Пара {Ос, vc), где множество Вс и функция vc, отображающая £>с о отрезок ординальных чисел меньших со0', определены следующим

образом:

Dc = {х.: 3 т,ка, ...,кт{х = (т,к0,...,к,„) 0)},

fc((w,fc0, ...,кт}) = 0)тк0 + ат-% + ... + кт, называется естественной системой обозначений.

Так как система Dc унивалентна, мы отождествляем ординалы, меньшие со°', с их обозначениями.

Теорема 1. Если множество А и ординал а < of такие, что А' £ П~\ тогда А' е 4-'.

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

Теорема 2. Пусть А' е где п > 0. Тогда А' е Л~1.

Из теорем 1 и 2 следуют отрицательные ответы на вопросы о существовании множеств, скачки которых лежат в Е~1 — А~1 и в П~х — Л~х, поставленные в работе Калимуллина11 (2007).

Теорему 2 можно использовать как базис индукции для доказательства следующей теоремы.

Теорема 3. Если множество А такое, что А! е для некоторых n, т > 0, тогда А! е

Следствие 1. Если п > 0, of ^ а < о)"+| и А' е то А' е Л~1.

Следствие 2. Множество А супернизкое тогда и только тогда, когда А! е Е~}п для некоторого п.

"Kalimullin I. Sh. Some Notes on Degree Spectra of the Structures. И Lecture Notes in Computer Science. - 2007. - V. 4497. -P. 389-398.

Следующая теорема характеризуют уровни, собственно содержащие скачки. Теорема 4. Для каждого п > О существует множество А, такое что А' е

~ К1*-

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

В §1.3 изучается вопрос о существовании вычислимых нумераций семейств низких множеств, в частности, семейства всех супернизких множеств. Нумерацией семейства множеств 5 называется произвольное сюрьективное отображение V : —>■ «Я.

Определение 3. Нумерация V называется вычислимой, если множество С, = Цх,у}: у б »(х)}

вычислимо перечислимо.

Семейства, которые имеют вычислимые нумерации, называются вычислимыми. В работе Гончарова и Сорби12 была введена общая концепция вычислимой нумерации, согласно которой для произвольного обозначения а € О понятие И~{-вычисли.\юй нумерации можно ввести так. !

Определение 4. Нумерация V называется -вычислимой, если

Нумерация V называется Л°2-вычислимой, если 6 Таким образом нумерация ^"-вычислима тогда и только тогда, когда она ^¿"'-вычислима для

'^Гончаров С. С., Сорби А. Обобщенно вычислимые нумерации и нетривиальные палурешетки Роджерса II Алгебра и Логика. - 19?7. - Т. 36. - № 6. - С. 621-641.

некоторого а е О. Для данных обозначения а е О и семейства S определим семейство

Ja(S) = {X е S : X' е

Рассмотрим случай, когда \а\о — w н S - семейство всех в.п. множеств, то есть J„(S) состоит из всех супернизких в.п. множеств. Чтобы доказать, что семейство J„ (S) вычислимо, в силу теоремы Ейтса13 достаточно доказать, что индексное множество

I(SL\) = {е : Wc. супернизкое}

имеет ^-уровень в арифметической иерархии. Однако, оценивая уровень I(SL¡) по алгоритму Тарского-Куратовского, удается доказать только принадлежность 1(SL¡) ^'-уровню.

Определение 5. Множество А называется множеством с трассируемым скачком, если существует вычислимая функция h и равномерно вычислимо перечислимая последовательность множеств {Те}еШ, такая что для всех е выполнено

(i) |7; К h(e),

(ii) Фе(А;е) í=> Фе(А;е) 6 Те.

Легко проверить, что индексное множество всех в.п. множеств с трассируемым скачком принадлежит £у-уровню арифметической иерархии. Согласно с результатом Нииса14, класс в.п. множеств с трассируемым скачком совпадает с классом супернизких в.п. множеств. Таким образом, семейство всех супернизких в.п. множеств имеет вычислимую нумерацию. Однако в общем случае не удается описать супернизкие множества в терминах множеств с трассируемым

"Yates С. Е. М. On the degrees of index sets 11 II Trans. Amcr. Math. Soc. - 1969. - V. 135. - P. 249-266.

,4Nies A. Reals which compule little II Lecture Notes in Logic. - 2002. - V. 27. -P. 261-275.

скачком. Из результатов § 1.3 удается получить достаточные условия вычислимости семейств низких множеств и установить наличие -вычислимой нумерации у семейства всех супернизких множеств. Центральным результатом в этом параграфе является следующая теорема.

Теорема 5. Пусть даны А^-вычислимые нумерации v, ¡jl семейств 1Z и S соответственно. Тогда предикат

P(e,i) <£> \>(е)' ф n(i)

является Е°-предикатом.

С использованием теоремы 5 устанавливается искомое достаточное условие.

Теорема 6. Пусть даны обозначения а ,b е О, такие что \а\о > 0, \Ь\о > 0, и семейство множеств S, которое содержат все конечные множества. Тогда если семейство S имеет Е~х-вычислимую нумерацию, то семейство J/,(S) так же имеет Е~' - вы числимую нумерацию.

Заметим, что уровень в иерархии Ершова вычислимой нумерации семейства Jb(S) зависит только от уровня нумерации семейства S.

Следствие 3. Семейство всех супернизких множеств имеет Е^-вычислимую нумерацию.

Глава 2 посвящена изучению структурных свойств тьюринговых степеней низких множеств. В §2.1 изучается полурешетка, порожденная супернизкими в.п. степенями (обозначаем через J). По теореме Сакса о разложении, полурешетка С всех в.п. степеней состоит из всевозможных объединений пар низких в.п. степеней. Следующая теорема показывает, что J состоит из всевозможных объединений пар супернизких в.п. степеней.

Теорема 7. Пусть даны супернизкие в.п. степени bo, bi и bi. Тогда существуют супернизкие в.п. степени ао, aj, Я2, такие что

bo U bi U b2 = а0 U ai = а0 U = 3] U а2.

Центральным результатом §2.1 является утверждение о различии элементарных теорий Си J. Для доказательства этого утверждения используются понятия слабых критических троек в в.п. степенях и тотально ш-в.п. степеней, введенные Доуни15.

Определение 6. Тройка несравнимых элементов ао, Я\ и b из верхней полурешетки образует слабую критическую тройку, если ао U b = ai U b и не существует элемента с < ао, aj, такого что ао ^ b U с.

Определение 7. Степень а называется тотально со-в.п., если каждая функция g <7- а со-в.п.

Нетрудно проверить, что каждая супернизкая в.п. степень тотально со-в.п. Доуни, Гринберг и Вебер16 доказали, что тотально со-в.п. степени не ограничивают критических троек. Поэтому следующее предложение является элементарным различием между CvlJ.

Теорема 8. Существует в.п. степень Ь, такая что если в.п. степени ао, ai, Яг удовлетво[ яют соотношению

b = ао U ai = ао U аз = aj U а2,

то по крайней мере одна из степеней ао, aj, а2 не тотально со- в. п.

Следствие 4. С ф 3.

"Downey R., Greenberg N., Weber R. Totally to-computable enumerable degrees and bounding critical triples H J. Math. Logic - 2007. - V. 7. - № 2. - P. 145-171.

"там же

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

В §2.2 изучается вопрос о различии элементарных теорий упорядоченных множеств низких в.п. (обозначается D[ow) и низких 2-в.п. (обозначается D^0") степеней. Впервые, различие элементарных теорий структур Di и Di (в.п. и 2-в.п. степеней соответственно) было установлено Арслановым17: каждая 2-в.п. степень имеет относительное 2-в.п. дополнение наверх. Другие элементарные различия были найдены Купером, Лемппом и другими18 и Доунеем19. Однако ни одно из них не влечет различие элементарных теорий D1""' и Djw. Искомое элементарное различие получается из следующей теоремы.

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

Согласно с теоремой Велша20, полурешетка в.п. степеней порождется двумя главными идеалами из низких в.п. степеней. Следовательно Dl°w ф Dj""' (также этот результат другими методами независимо получил Ямалеев21).

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

17Арсланов M. M. О структуре степеней ниже 0'. // Известия вузов. Математика. - 1988. - № 7. - С. 27—34.

18Соорег S. В., Harrington I.., Lachlan A. H., Lempp S., Soare R. I. The d.r.e. degrees are not dense. // Ann. Pure Appl. Logic- 1991. - V. 55. - P. 125-151.

:®Downey R. D.r.e. degrees and the nondiamond theorem. II Bull. London Math. Soc. - 1989. - V . 21. - P. 43—50.

MWclch L. A herarchy of families of recursively enumerable degrees and a theorem of founding minimal pairs. // Ph.D. Diss. University of filions. Urbana. - 1980.

21 Ямалеев M. M. Структурные свойства тьюринговых степеней множеств из иерархии Ершова // Диссертация на соискание ученой степени к.ф.-м.н. Казанский государственный университет. Казань. - 2009.

параграф носит в основном технический характер, в нем приведены определения сводимости по перечислимости, е-степеней и их фундаментальные свойства.

В §3.2 изучаются уровни иерархии Ершова, содержащие е-скачки. Все результаты этого параграфа получены совместно с И. Ш. Калимуллиным.

Определение 8. Множество K{Á) — {z : z е 9:(А)} называется скачкам по перечислимости или е-скачком множества А, где 0Z - это оператор перечисления с геделевским номером z.

Легко видеть, что для каждого множества А

К(АФА)е=,А'.

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

Теорема 10. Пусть даны множество А и обозначения а,Ь & О, такие что К(А) е Е~1оЬ. Тогда либо К(А) е Е~\ либо К{А) е Х^1.

Определение 9. Обозначение а е О называется нормальным, если |а|0 -ф- 0 и существует частично вычислимая функция

h : {х : х <о а} х {х \ х <о а} —> {х : х <о а},

которая строго <о-возрастает относительно первого и второго аргументов.

Например, каждое естественное обозначение для и>", п > 0, является нормальным. В самом деле, в качестве h можно взять функцию, индуцированную

натуральной суммой:

а(+)/3 = ып,(т\ + т\) + ш"2('И2 + т'2) + ••• + ш"к(тк + m't),

где

а - a)nimi 4- со"2т2 -i-----1-

Р = с»"'»?', + w"2W'2 + ■•• + а>Якт'к,

Пк ^ • • • ^ «2 ^ «i и mt,m'¡ < а, которая, очевидно, строго возрастает с ростом как а, так и /i. Отметим также, что если обозначение а еО нормальное, тогда Но = (оа для некоторого а.

Согласно с теоремой 2, если е-степень множества А тотальна и К(А) е Е~}, тогда К(А) е А~1. Как показывает следующая теорема, условие "dege(A) тотальна" можно заменить на "dege(A) не квазиминимальна".

Теорема 11. Если а € О - нормальное обозначение и е-степень множества А не квазиминимальна, тогда

К(А) 6 я;1 =» К(А) е

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

Теорема 12. Пусть дано нормальное обозначение а е О. Тогда существует такое множество А, что К(А) е Е~1 — А~'.

Таким образом, если уровень Г иерархии Ершова в естественный системе обозначений собственно содержит К(А), тогда либо Г = E¡~1, либо Г является Е~„- или Л "¿-уровнем для п > 0. Для произвольных обозначений можно только сказать, что если а е О нормальное, то Е~1 содержит К(А); если один из уровней Е~1 или Л"1 содержит К(А) и \а\о > 0, тогда \а\о — а - со2, где а > 0.

В §3.3 изучаются дополнения низких степеней в структуре 0^), состоящей из всех I720-e-CTcneiieii. Элемент Ье 0', называется дополнением элемента ае ^ 0^, если ае 11Ъе — 0'е и яе ПЬе ~ 0£.. Рассмотрим отображение А i-> А ф А. Оно индуцирует однозначное отображение тьюринговых степеней в тотальные степени по перечислимости:

I :VT —Ve.

Более того, для любых тьюринговых степеней а и b справедливо

/(a U Ь) = г(а) U г(Ь),

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

Впервые вопрос о существовании дополнений в степенных структурах был изучен Эпштейном22: он показал, что в структуре тьюринговых степеней ниже 0' каждая в.п. степень имеет дополнение. Однако это уже не так в De(^ 0^): Калимуллиным23 было установлено существование /7,°-е-степени, не имеющей -дополнений. В следующей теореме устанавливается, что свойством недополняемости обладает каждая низкая Я^-е-степень.

Теорема 13. Если ае - ненулевая низкая П^-е-степень, Ъе - ненулевая степенъ и < ае U Ье, то существует такая ненулевая е-степень се, что Се ^ йе и Се ^ Ье.

^Epstein Е. L. Minimal degrees of unsolvability and the full approximation construction Ii Memoire of the American Mathematical Society. - 1974. - № 162. American Mathematical Society, Providence, RI.

23Калимуллин И. Ш. Структурные свойства верхней папурешетки степеней по перечислимости // Диссертация на соискание ученой степени к.ф.-м.н. Казанский государственный университет. Казань. - 2001.

Как показывает следующая теорема, условие "ае низкая" необходимо, и существуют дополняемые Л^-е-степени.

Теорема 14. Существуют П^-е-степень яе > 0е и А\-е-степень Ье > 0Е, такие что П Ь<> = 0е и яе и Ье = 0^.

В заключение, автор выражает глубокую признательность научному руководителю Искандеру Шагитовичу Калимуллину и руководителю научной школы, заведующему кафедрой алгебры и математической логики Марату Мирзаевичу Арсланову за постановку задач, поддержку в работе и интерес к исследованиям автора, а также своим коллегам Андрею Николаевичу Фролову, Марсу Мансуровичу Ямалееву и Максиму Витальевичу Зубкову за внимание к исследованиям автора и активное и плодотворное обсуждение.

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

1. Файзрахманов М.Х. Разложимость низких 2-вычислимо перечислимых степеней и тьюринговые скачки в иерархии Ершова Н Известия вузов. Математика. - 2010. - № 12. - С. 58-66.

2. Файзрахманов М. X. Вычислимые нумерации семейств низких множеств и тьюринговые скачки в иерархии Ершова Н Сибирский математический журнал. - 2010. - Т. 51. - № 6. - С. 1435-1439.

3. Файзрахманов М. X. О полурешетке, порожденной супернизкими вычислимо перечислимыми степенями // Известия вузов. Математика. - 2011. - № 1. - С. 85-90.

4. Faizrahmanov M.Kh., Kalimullin I. Sh. Turing and enumeration jumps in the Ershov hierarchy // Journal of Logic and Computation. - 2010. doi: 10.1093/logcom/exq039.

5. Faizrahmanov M. Kh. Splitting and antisplitting theorems in classes of low degrees И Bull. Symbolic Logic. - 2010. - V. 16. - P. 116.

Отпечатано с готового оригинал-макета в типографии Издательства Казанского (Приволжского) федерального университета Тираж 100. Заказ 117/12

420008, г.Казань, ул. Профессора Нужина, 1/37 тел.: (843) 233-73-59,292-65-60

Введение

Глава 1. Тьюринговые скачки в иерархии Ершова

§1.1. Иерархия Ершова, конструктивные ординалы и системы обозначений

§1.2. Уровни иерархии Ершова, содержащие тыорипговые скачки

§1.3. Вычислимые нумерации семейств низких множеств.

Глава 2. Элементарные теории алгебраических систем, порожденных низкими степенями

§2.1. Полурешетка, порожденная супернизкими в.п. степенями

§2.2. Низкие в.п. и низкие 2-в.п. степени не элементарно эквивалентны

Глава 3. .Е-скачки в иерархии Ершова

§3.1. Сводимость по перечислимости и е-степени

§3.2. Уровни иерархии Ершова, содержащие е-скачки.

§3.3. Дополнения низких П^-е-степеней.

Одттим из важных понятий в теории вычислимости является понятие низкого множества, которое, интуитивно, выражает, что множество слабо вычислимо. Это связано с тем, что при изучении алгоритмических свойств множеств натуральных чисел часто возникает вопрос, при отсутствии подходящего вычислимого множества, о нахождении низкого множества, удовлетворяющего данному свойству. Например, согласно с теоремой Джоку-ша и Соара о низком базисе [34], каждый непустой П®-класс содержит низкое множество; по теореме Амбос-Шпииса, Джокуша и других [15], каждая быстро простая степень имеет низкое дополнение наверх. С другой стороны, существует большое количество литературы, посвященной низким множествам и их свойствам, которые напоминают свойства вычислимых множеств. Например, Соар установил [46], что решетка вычислимо перечислимых (в.п.) надмножеств низкого в.п. множества изоморфна решетке всех в.п. множеств; согласно с теоремой Робинсона [41], теорема Сакса о разложении справедлива в верхнем конусе любой низкой в.п. степени.

Множество А называется низким, если А' =т 0'- Таким образом, оператор скачка по, может различать вычислимые и низкие множества. В известной работе Бикфорда и Миллса [17] введено понятие суперпизких множеств, которое естественным образом усиливает понятие низких множеств: множество А называется супернизким, если А' =и 0'- Стандартное построение низкого простого в.п. множества с сохранением вычисления скачка уже дает супернизкое множество (как и теорема о низком базисе). Однако не каждое низкое множество является супернизким. Одним из следствий теоремы Сакса о разложении [43] является существование таких низких в.п. множеств Ао. А\, что Ао П А\ = 0 и Ао и А\ = 0'. Согласно с результатом Бикфорда. и Миллса [17], одно из таких множеств Ао, А\ не супернизкое.

Более того, упорядоченные множества низких п.п. и супернизких п.п. степеней не элементарно эквивалентны (см. Доуней, Гринберг и Вебер [29|).

В работах Ершова [5][6][7] построена иерархия множеств А ^т 0', получившая в литературе название "иерархия Ершова". Как оказалось, возникающая иерархия исчерпывает весь класс множеств А 0'- Каждый следующий уровень иерархии содержит все предыдущие и не совпадает пи с одним из них. В представленной работе изучаются новые усиленные понятия низких множеств, а именно множества, тыоринговые скачки которых лежат в фиксированных бесконечных уровнях иерархии Ершова. По результату Карстенса [18], множества А из первого бесконечного (А"1-) уровня иерархии Ершова характеризуются условием А ^и 0'. Поэтому первым уровнем такой иерархии скачков будет класс супернизких множеств.

Первый, естественно возникающий, вопрос при изучении иерархии Ершова для скачков - будет ли каждый уровень содержать скачки, не ле-•жащие в меньших уровнях. Легко проверить, что для конечных уровней это не верно, то есть, если А' п-в.п., тогда А' в.п. В первой главе устанавливается, что и бесконечные уровни могут не содержать тыоринговые скачки. Более того, если дан ординал а < и2 и А' € А"1, тогда А супернизкое (в частности, если А' 6 тогда А' Е А"1). Вторая часть первой главы носвящена вопросу о существовании А^-вычислимых нумераций классов скачков. Впервые этот вопрос был изучен Ниисом. В работе [39] оп ввел понятие мпоэюеегпва с 7про,ссирусмым скачком и установил, что для в.п. множеств этот класс совпадает с классом суперпизких множеств. Класс множеств с трассируем скачком будем обозначать «7Т. Индексное множество в.п. множеств из <7Т принадлежит Ед-уровню арифметической иерархии. Следовательно, класс всех суперпизких в.п. множеств имеет вычислимую нумерацию. Однако, в общем случае множества с трассируемым скачком могут не быть супернизкими. Тем не менее в § 2 устанавливается, что каждый уровень иерархии скачков (в частности, семейство всех супернизких множеств) имеет А^-вычислимую нумерацию.

В последние годы с развитием алгоритмической теории случайности особое внимание стало уделяться изучению структурных свойств классов низких степеней, особенно, супернизких степеней. Даймондстоуном ¡24] было установлено существование быстро простой степени, не имеющей относительных супернизких дополнений наверх. Доунсй, Гринберг и Вебер установили [29}, что все суперпизкие в.п. степени не ограничивают критических троек, в то время как существует низкая копия конечной решетки М5. Вторая глава посвящена изучению структурных свойств тыоринговых степеней множеств, скачки которых лежат в фиксированных уровнях иерархии Ершова. По теорема Сакса о разложении полурешетка в.п. степеней порождается низкими в.п. степенями относительно операции взятия наименьшей верхней грани. Обозначим эту полурешетку через С. Аналогичным образом можно определить полурешетку J, порожденную супернизкими в.п. степенями. Очевидно, что 0 Е 3. Бикфорд и Миллс [17| установили, что О' Е 3. Основной результат первого параграфа второй главы заключается в различии полурешеток С и О". Более того, найденное различие является элементарным. Второй параграф посвящен вопросу о различии элементарных теорий упорядоченных множеств низких в.и. (обозначается и низких 2-в.п. (обозначается И1™") степеней. Впервые, различие элементарных теорий структур Их и 02 (в.п. и 2-в.п. степеней соответственно) было установлено Арслановым |2|: каждая 2-в.п. степень имеет относительное 2-в.п. дополнение наверх. Однако, пи одно из известных элементарных различий между П\ и И2 (см. [23][25]) не будет элементарным различием между В1^". Искомое элементарное различие получается из следующего предложения: для каждого обозначения конструктивного ординала существует низкая 2-в.п. степень, не являющаяся разложимой па две меньшие 1

2-в.п. степени, скачки которых принадлежат А-уровню иерархии Ершова, соответствующему этому обозначению. Согласно с теоремой Велша [49]. полурешетка в.п. степеней порождется двумя главными идеалами из низких в.п. степеней. Следовательно И1™" ф П1.™" (также этот результат другими методами независимо получил Ямалеев [14]).

Естественным обобщением понятия тыорингового скачка является понятие скачка по перечислимости, введенное Купером [21]: множество

К {А) = в2(А)} называется скачком по перечислимости множества А, где ©, - это оператор перечисления с геделевским номером г. Легко видеть, что К (А® А) =1 А1. Поэтому каждый уровень иерархии Ершова, содержащий тьюринговый скачок, содержит также скачок по перечислимости. Однако поведение скачков по перечислимости отличается от поведения тыоринговых скачков: в третьей главе, совместно с И.Ш. Калимуллиным, установлено, что Е- уровни могут содержать скачки по перечислимости, более того, существует множество А такое, что К (А) Е Е~х — А"1.

Автор выражает глубокую признательность научному руководителю Искандеру Шагитовичу Калимуллину и руководителю научной школы, заведующему кафедрой алгебры и математической логики Марату Мирза-евичу Арсланову за постановку задач, поддержку в работе и интерес к исследованиям автора, а также своим коллегам Андрею Николаевичу Фролову, Марсу Мансуровичу Ямалееву и Максиму Витальевичу Зубкову за внимание к исследованиям автора и активное и плодотворное обсуждение.

Определения и обозначения. Все рассматриваемые множества и функции заданы на множестве натуральных чисел и = {0,1,2,.}. Мы используем малые латинские буквы /, д, к для обозначения всюду определенных функций; малые греческие буквы (р^ф^О используются для обозначения частичных функций. Для частичной функции </? и аргумента х пишем ip{x) 4-5 ссли функция ip определена на аргументе ж; в противном случае пишем ip(x) t- Через dorn ip> и ran (р обозначены соответственно область определения и область значений функции (р. Для множества А его характеристическая функция обозначается ха> мы часто отождествляем А с его характеристической функцией, записывая се как А(х). Ограничение функции / на аргументы у < х записывается / \ х\ запись A f х означает Ха I х. Если Р - предикат на множестве натуральных чисел, то запись цхР{х) означает наименьшее число х такое, что Р(х).

Тьюринговый функционал с геделевским номером z записывается как Ф~. Через use(X; z,x) обозначается itse-функция функционала Ф~(Х;а;). Вместо Ф,(0) пишем ipz\ обозначим Wz — dorn ip>z - в.п. множество с геделевским номером

Для множества А обозначим через А его дополнение; запись А — В означает А П В. Мощность множества А обозначается как |Л| или card А\ наибольший элемент конечного множества А обозначается через max А; полагаем тах0 = 0. Обозначим через А ф В сочленение множеств А и В, а именно, множество {2х : х £ Ä\ U {2х + 1 : х Е В}. Образ пары (х, у) относительно стандартной функции пары х2 + 2ху + у'2 + Зж + у) обозначается как {х,у)\ запись (х\,х2,хз) означает {{х\, х^), Жз); аналогично определяется (рс\, Х2, ■ ■ ■, хп). Определим проекции щ, тг\ относительно функции пары, полагая тго((х,у)) = х и 7Гх((х,у)) = у. Для множества А обозначаем А^ — {(y,z) : (y,z) 6 А}.

1. Арсланов М. М. О структуре степеней ниже 0'. // Известия вузов. Математика. 1988. - № 7. - С. 27-34.

2. Арсланов М. М., Калимуллин И. Ш., Купер С. Б. Свойства разложимости тотальных степеней по перечислимости. // Алгебра и Логика. 2003. - Т. 42. - № 1. - С. 3-25.

3. Гончаров С. С., Сорби А. Обобщенно вычислимые нумерации и, нетривиальные полурешетки Родоюерса // Алгебра и Логика. 1997. - Т. 36.- № 6. С. 621-641.

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

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

6. Ершов Ю. Л. Теория нумераций. М.: Наука. - 1977. - 416 с.

7. Калимуллин И. Ш. Структурные свойства верхней полурешетки степеней по перечислимости // Диссертация на соискание ученой степени к.ф.-м.и. Казанский государственный университет. Казань.- 2001.

8. Медведев Ю. Т. Степени трудности массовых проблем. // ДАН СССР 1955. - Т. 104. - С. 501-504.

9. Мучник А. А. Неразрешимость проблемы сводимости теории алгоритмов И ДАН СССР 1956. - Т. 108. - С. 194-197.

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

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

12. Ямалеев М. М. Структурные свойства тьюринговых степеней множеств из иерархии Ершова, // Диссертация на соискание ученой степени к.ф.-м.н. Казанский государственный университет. Казань.- 2009.

13. Arslanov M.M., Cooper S., Li A. There is no low maximal d. c. e. degree- Corrigendum. // Mathematical Logic Quarterly 2004. - V. 50. - № 6.- P. 628-636.

14. Bickford M., Mills F. Lowness properties of r.e. sets // Manuscript, UW Madison. 1982.

15. Carstcns H. G. A\-mengen. // Arch.Math.Log.Grundlagenforsch. 1976.- V. 18. P. 55-65.

16. Cholak P., Groszek M., Slaman T. An almost deep degree. // J. Symbolic Logic. 2001. -V. 66. - № 2. - P. 881-901.20j Cooper S. B. Degrees of Unsolvability. // Ph.D. Thesis, Leicester University, Leicester, England. 1971.

17. Cooper S. B. Partial degrees and the density problem. Part, 2: The enumeration degrees of the sets are dense. // J. Symbolic Logic.- 1984. V. 49. - P. 503-513.

18. Cooper S. B., Enumeration reductibility, nondetcrministic computations and relative compitability of partial functions. // Lecture Notes in Mathematics. 1990. - V. 1432. - P.57-110.

19. Cooper S. B., Harrington L.,x Lachlan A. H., Lempp S., Soare R. I. The d.r.e. degrees are not dense. // Ann. Pure Appl. Logic 1991. - V. 55.- P. 125-151.

20. Diamondstone D. Promptness does not imply superlow cuppable. // J. Symbolic Logic. 2009. - V. 74. - № 4. - P. 1264-1272.

21. Downey R. D.r.e. degrees and the nondiamond theorem. // Bull. London Math. Soc. 1989. - V . 21. - P. 43-50.

22. Downey R. Lattice nonembeddings and initial segments of the recursively enumerable degrees. // Ann. Pure Appl. Logic. 1990. - V. 49. - № 2.- P. 97-119.

23. Downey R., Jockusch C., Stob M. Array nonrecursive sets and multiple permitting arguments. // Lecture Notes in Math. -1990. V. 1432.- P. 141-173.

24. Downey R., Jockusch C., Stob M. Array nonrecursive degrees and genericity. // London Math. Soe. Lecture Note Ser. 1996. - V. 224.- P. 93-104.

25. Downey R., Greenberg N., Weber R. Totally u-computable emimerable degrees and bounding critical triples // J. Math. Logic 2007. - V. 7.- № 2. P. 145-171.

26. Epstein E. L. Minimal degrees of unsolvability and the full approximation construction // Memoirs of the American Mathematical Society. 1974.- № 162. American Mathematical Society, Providence, RI.

27. Friedberg R. M. Two recursively enumerable sets of incomparable degrees of unsolvability. // Proc.Natl. Acad. Sci. USA 1957. - V. 43. - P. 236238.

28. Friedberg R. M., Rogers H. Reducibilty and completeness for sets of integers // Z. Math. Logic and Grundl. Math. 1959. - V.2. - № 2.- P. 117-125.

29. Greenberg N., Nies A. Benign cost functions and lowness properties, j/ To appear.

30. Jockusch C. G., Soare R. I. U°rcla sses and degrees of theories, j j Trans. Amer. Math. Soc. 1972. - V. 173. - P. 33-56.

31. Kalimullin I. Sh. Some Notes on Degree Spectra of the Structures. // Lecture Notes in Computer Science. 2007. - V. 4497. -P. 389-398.

32. Kalimullin I. Sh. Splitting properties of n-c.e. enumeration degrees. // J. Symbolic Logic. 2002. - V. 67. - № 2. - P. 537-546.

33. Lachlan A. H. Lower bounds for pairs of recursively enumerable degrees. // Proc. London Math. Soc. 1966. - V. 16. - P. 537-569.i

34. Miller D. P. High recursively enumerable degrees and the anticupping property. // Lecture Notes in Math. 1981. - V .859. -P. 230—245.

35. Nies A. Reals which compute little // Lecture Notes in Logic. 2002.- V. 27. -P. 261-275.

36. Nies A. Computability and Randomness. New York.: Oxford University Press. - 2009. - 442 p.

37. Robinson R W. Jump restricted interpolation in the recursively enumerable degrees. // Annals of Math. 1971. - V. 93. - P. 586-596.

38. Sacks G. E. A minimal degree less than 0'. // Bull. Amer. Math. Soc.- 1961 V. 67. - P. 416-419.43j Sacks G. E. On the degrees less than 0' // Ann. of Math. 1963. - V. 2.- № 77. P. 211-231.

39. Sacks G. E. The recursively enumerable degrees are dense, j j Ann. of Math. 1964. - V. 80. - № 2. - P. 300-312.45| Schacffer B. Dynamic notions of genericity and array noncomput ability, j j' Ann. Pure Appl. Logic. 1998. - V. 95. - P. 37-69.

40. Soare R. Automorphisms of the lattice of recursively enumerable sets Part II: Low sets. // Annals of of Math. Logic. 1982. - V. 22 - P. 69-107.

41. Walk S. Towards a definition of the array computable degrees, j j PhD thesis, University of Notre Dame. 1999.

42. Wcinstein B. On embeddings of the 1-3-1 lattice into the recursively enumerable degrees, j/ PhD thesis, University of California, Berkeley. 1988.

43. Welch L. A herarchy of families of recursively enumerable degrees and a theorem of founding minimal pairs. // Ph.D. Diss. University of Illions. Urbana. 1980.

44. Yates C. E. M. On the degrees of index sets 11 j j Trans. Amer. Math. Soc. 1969. - V. 135. - P. 249-266.