Алгебраические и структурные свойства полурешеток Роджерса в иерархии Ершова тема диссертации и автореферата по ВАК РФ 01.01.06, кандидат наук Оспичев, Сергей Сергеевич

• Оспичев, Сергей Сергеевич
• кандидат наук
• 2013

Оглавление диссертации кандидат наук Оспичев, Сергей Сергеевич

Оглавление

Введение

Определения

Иерархия Ершова

Вычислимые нумерации

1 Общие свойства вычислимых нумераций и мощность полурешеток Роджерса

1.1 Вычислимые нумерации классов Е"1 и Д"1

1.2 Двухэлементные семейства

1.3 Бесконечное семейство Е~1-множеств с единственной вычислимой нумерацией

1.4 Семейства без главных нумераций

2 Минимальные нумерации

2.1 Нумерации семейств множеств конечных уровней иерархии Ершова

2.2 Фридбергова нумерация семейства всех ^множеств

2.3 Бесконечные Е~1-вычислимые семейства без

фридберговых нумераций

Список литературы

Введение диссертации (часть автореферата) на тему «Алгебраические и структурные свойства полурешеток Роджерса в иерархии Ершова»

Введение

Теория нумераций была развита для исследования алгоритмических свойств классов абстрактных объектов методами классической вычислимости, кодированием информации о них и их связей через свойства их номеров (имен). Впервые эффективность этого подхода была продемонстрирована в классической работе К. Геделя о неполноте арифметики.

В дальнейшем, С. К. Клини [1] построил универсальную частично вычислимую функцию (другими словами, вычислимую нумерацию всех частично вычислимых функций). Результат Клини имеет огромное значение для теории вычислимости.

Понятие нумерации, как математического объекта, было введено А.Н. Колмогоровым [2], а его ученик, В. А. Успенский занимался изучением вычислимых нумераций частично вычислимых функций [3], [4].

X. Роджерс [5], [6] исследовал вычислимые нумерации семейства всех частично вычислимых функций и вычислимо перечислимых множеств. Именно им было введено понятие Com(S) всех вычислимых нумераций семейства S. Отношение сводимости ^ между вычислимыми нумерациями определяет предпорядок на классе всех вычислимых нумераций. Факторизация по отношению эквивалентности =, определяемому данным прсдпорядком, позволяет построить частично упорядоченное множество TZ(S) = (Com(S)/ = образующее верхнюю полурешетку вычислимых нумераций семейства S. Роджерс рассматривал только те вычислимые нумерации, степени которых соответствовали наибольшему элементу оиисанной полурешетки. Минимальные элементы 7l(S), а также некоторые другие свойства были позднее представлены Р. Ф. Фридбергом (R. F. Friedberg) [7], А. И. Мальцевым |8] и М. Б. Пур-Эль (М.В. Pour-El) [9].

Дальнейшее изучение и развитие теории вычислимых нумераций было продолжено Ю.Л. Ершовым [10]—[13], А. X. Лахланом (А.Н. Lachlan) [14],

A.B. Хуторецким [15]-[18], С.С. Марченковым [19], [20], В. В. Выогипым [21]-[23],

B. Л. Селивановым [24], [25], С. С. Гончаровым [26]-[30], С. А. Бадаевым ]31]-[35],

М. Куммером (lM. Kummer) [36], А. Сорби (А. Sorbi) [37], С. Ю. Подзоровьш [38], Ж. Т. Таласбаевой [39] и другими.

Результаты классической теории вычислимых нумераций нашли наибольшее применение в рекурсивной математике [40],[41]. Так, метод построения семейств вычислимо перечислимых множеств с конечным числом вычислимых фридберговых нумераций, предложенный С. С. Гончаровым в [26], послужил отправной точкой для исследования алгоритмических размерностей рекурсивных моделей [28], [29], [42].

Теория нумераций нашла применение и в классической рекурсивной теории. Например, используя упомянутую теорему Гончарова [26] о числе вычислимых фридберговых нумераций семейств вычислимо перечислимых множеств, М. Куммер [43] нашел решение известной задачи о типах рекурсивных изоморфизмов частично вычислимых функций ([5],глава 4). Точнее, он доказал, что для любого к £ ш существует вычислимая функция, обладающая ровно к типами рекурсивных изоморфизмов.

Далее в работе мы приведем обзор результатов но вычислимым нумерациям в известных иерархиях множеств, таких как иерархия Ершова (разностная иерархия) и арифметическая иерархия. В работе С. С. Гончарова и А. Сорби [37] был предложен новый общий подход к введению понятия вычислимого семейства конструктивных объектов, имеющих описание в языке, допускающем геделевскую нумерацию формул. В рамках подхода Гончарова - Сорби оказалось возможным подойти с единых позиций к понятию вычислимости семейств таких конструктивных объектов, как вычислимо перечислимые множества, конструктивные модели, семейства вычислимых морфизмов и т. д. Этот подход также позволяет ввести единообразное понятие вычислимого семейства множеств для иерархий Ершова и Клини - Мостовского (арифметической), а также понятие полурешетки Роджерса для подобных семейств. Согласно подходу Гончарова - Сорби, вычислимость нумерации а семейства множеств из данного класса /С эквивалентна определимости ее универсального множества {(х,п)\х £ сх(п)} в терминах класса /С.

В случае семейств вычислимо перечислимых множеств (/С = Е^), такой подход

полностью совпадает с классическим определением вычислимой нумерации (см., например, [44]) и универсальное множество {(х,п)\х £ о:(п)} представляет собой равномерно эффективную процедуру, определяющую, попадает ли элемент х во множество а(п).

В случае 1С = вычислимость а означает, что универсальное множество

для а является 0^п'-перечислимым по сильной теореме о иерархии Клипи и Поста ([5]). А значит, многие результаты классической теории нумерации могут быть релятивизованы для арифметической иерархии.

В случае /С = Е"1, любой элемент х может быть помещен в а(п) на некотором шаге равномерно эффективной процедуры, но, в отличие от классического случая, х может быть в дальнейшем удален из а(п). Число перечислений х «в» и «из» а(п) ограничено п.

Согласно концепции Ю.Л. Ершова, полурешетки Роджерса определяют алгоритмическую сложность семейств множеств в целом и во многих вопросах могут быть более полезными, чем различные понятия сложности отдельно взятых элементов этих семейств. Можно выделить три основных направления исследования полурешеток Роджерса. Первое направление связано с глобальными характеристиками полурешеток Роджерса: мощность, решетки и т. п. Второе — посвящено характеризации нумераций, порождающих в полурешетках Роджерса элементы с особыми алгебраическими свойствами: наибольшие, минимальные, неразложимые элементы и т. п. Третье — направлено на изучение локальных алгебраических свойств полурешеток Роджерса: строение сегментов, идеалов и т. п.

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

Рассмотрим эти направления подробнее и обратимся к истории изучения

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

Фридберговы и позитивные нумерации представляют собой важный случай минимальных нумераций. Основные задачи исследования минимальных нумераций можно условно разделить на два направления:

1. Поиск условий, при которых семейство Л £ Е^ обладает Е^-вычислимыми минимальными нумерациями.

2. Определение количества минимальных элементов полурешетки Роджерса заданного семейства множеств.

В классическом случае, некоторые необходимые условия существования фридберговой нумерации для семейств вычислимо перечислимых множеств были найдены А. Лахланом [45]. Затем множество достаточных условий были предложены в работах Ю.Л. Ершова [12], М. Куммера [46], [47], А.И. Мальцева [8] и других. Поскольку важнейшей частью представленной работы является изучение достаточных условий существования фридберговых нумераций в иерархии Ершова, рассмотрим подробнее подобные результаты классической теории вычислимости. Началом изучения минимальных нумераций послужила известная теорема Фридберга [7] о существовании однозначной нумерации семейства всех вычислимо перечислимых множеств. М. Пур-Эль и Г. Путпам в [48] построили пример семейства вычислимо перечислимых множеств без вычислимых однозначных (фридберговых) нумераций:

{{2х, 2х + 1}\х € К} и{{2х}, {2х + 1}|ж £ К}, где

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

В той же работе [48] М. Пур-Эль и Г. Путчам, внеся небольшие изменения в оригинальную конструкцию Фридберга, получили:

Теорема 1. (М. Пур-Элъ, Г. Путчам). Пусть А - бесконечный вычислимый класс вычислимо перечислимых множеств и Б - бесконечное вычислимо перечислимое множество. Тогда существует однозначно перечислимый класс В С, А такой что

1. X £ В\А=> X - конечно.

2. X £ В \ А => (ЗУ £ А)(Х С У и 5).

Следствие этой теоремы порождает достаточное условие существования однозначной нумерации класса вычислимо перечислимых множеств.

Следствие 2. (М. Пур-Элъ, Г. Путнам).

Пусть А - бесконечный вычислимый класс вычислимо перечислимых множеств. Если каждое конечное подмножество множества УлеЛ является элементом А, тогда А обладает однозначной нумерацией.

Пур-Эль и Говард в [49] получили условие, использующее частично вычислимую функцию, содержащую информацию о структуре данного класса.

Определение 3. (У. Говард, М. Пур-Эль).

Пусть А - семейство множеств, обозначим за Т - семейство всех конечных подмножеств элементов из А. Функцию к : Т —> со назовем высотой А, если она удовлетворяет следующим условиям:

1. к монотонна: А С В Е Т => к(А) ^ к(В),

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

3. для любого А £ Т существует В Э А из Т, такое что к(А) ф к(В).

Сопоставим функцию к : Т —> ш с частичной функцией к* : и> —> ш следующим образом: к*(г) = /г(1)г). Здесь - каноническая нумерация конечных множеств.

Теорема 4. (У. Говард, М. Пур-Элъ [49]).

Вычислимое семейство с частично вычислимой функцией высоты обладает однозначной нумерацией.

Из этой теоремы У. Говард и М. Пур-Эль получили следующее

Следствие 5. (У. Говард, М. Пур-Элъ [49])- Пусть А - бесконечное вычислимое семейство.

1. Если А состоит, только из конечных множеств и не содержит максимального по включению элемента, тогда А однозначно перечислимо.

2. Если А не содержит ш, но каждый начальный сегмент и] содержит расширение в А, тогда А однозначно перечислимо.

3. Если А замкнуто относительно конечных объединений, но не содержит иАеА А, тогда А однозначно перечислимо.

Результат У. Говарда и М. Пур-Эль был усилен А. Лахлапом в [45]. Он определяет свойство (Е) для вычислимых семейств. Через обозначим семейство {И^^' £ Д}. Вычислимое семейство А обладает свойством (Е), если существует частично вычислимая функция /, такая что если Тх С А, тогда /(г,./) определена в том, и только в том случае, если семейство

и 1{ьз) ~ /¿-индекс этого семейства. Здесь ¡л - вычислимая нумерация всех вычислимых нумераций семейств вычислимо перечислимых множеств.

Теорема 6. (А. Лахлан [45])- Бесконечное вычислимое семейство удовлетворяет свойству (Е) тогда и только тогда, когда для данного конечного подсемейства ]- С А семейство А\Т однозначно перечислимо равномерно по Т. Любое семейство с частично вычислимой функцией высоты удовлетворяет свойству (Е).

Следующий результат получен А. И. Марчепковым в [19].

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

Еще одно достаточное условие существования однозначных нумераций было получено М. Куммером в [36].

Теорема 8. (М. Куммер).

Пусть 5" - вычислимое семейство, такое что существует два непересекающихся вычислимых подсемейства ^ в, таких что = 51 и

1. обладает вычислимой однозначной нумерацией,

2. любое конечное подмножество элемента имеет бесконечно много расширений в 62.

Тогда в обладает вычислимой однозначной нумерацией.

Отметим, что это единственный из упомянутых результатов, при доказательстве которого не используются приоритетные конструкции, а также то, что теорема Р. Фридберга может быть получена как простое следствие результата М. Куммера [47].

Используя вариацию конструкции Р. Фридберга, А. И. Мальцев и К. Вольф в [8], [50] получили:

Теорема 9. Пусть А - вычислимое семейство. Если существует канонически вычислимое подсемейство Т конечных множеств такое, что

1. каждый элемент из А является пределом возрастающей последовательности из Т,

2. каждое конечное подмножество элемента из А обладст собственным расширением в Т,

тогда А однозначно перечислимо.

В дальнейшем, М. Куммер в [46] усилил этот результат:

Теорема 10. (М. Куммер), Если вычислимое семейство Л содержит канонически вычислимое подсемейство Т, такое что каждое конечное подмножество элемента из Л\Т обладает бесконечным количеством расширений в Т, тогда Л однозначно перечислимо.

Отметим еще несколько результатов о числе минимальных элементов. Полное решение проблемы о числе фридберговых и позитивных вычислимых нумераций было получено С. С. Гончаровым в [26], а именно справедлива

Теорема 11. (С. С. Гончаров). Для любого п Е со и {ш} существует семейство вычислимо перечислимых множеств, имеющее в точности п (с точностью до эквивалентности нумераций) вычислимых фридберговых (позитивных) нумераций.

Нумерации а и /5 семейства Л назовем предельно эквивалентными, если они сводятся друг к другу с помощью О'-вычислимых функций.

Теорема 12. (С. С. Гончаров [51]). Если семейство вычислимо перечислимых множеств имеет две вычислимые однозначные (позитивные) нумерации, являющиеся предельно эквивалентными, то оно имеет счетное число (с точностью до эквивалентности нумераций) вычислимых однозначных (позитивных) нумераций.

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

Теорема 13. (С. А. Бадаев, С. С. Гончаров [52]). Для любого п, если Л -бесконечное ТРп+2-вычислимое семейство, то полуреш,етка Роджерса содержит бесконечно много минимальных элементов.

Этот результат сохраняется и в гиперарифметической иерархии (Н. Бакланова, [53]).

Теорема 14. (С. А. Бадаев, С. С. Гончаров [52]). Семейство А С Е°+1 обладает Евычислимой позитивной нумерацией тогда и только тогда, когда существует ТРп+2-вычислимая нумерация а семейства А, такая что множество {(ж,у)\а(х) =

«(у)} 6 Д§.

Теорема 15. (С. С. Гончаров, А. Сорби [37]). Если бесконечное семейство А С обладает ТРп+2-вычислимой позитивной нумерацией, тогда существует Е°+2-вычислимая фридбергова нумерация семейства А.

В иерархии Ершова отметим результаты, полученные в [54]:

Теорема 16. (С. С. Гончаров, С. Лемпп, Д. Р. Соломон).

Для любого п > 1 существует Е"1 -вычислимая фридбергова нумерацг1я семейства всех Е"1 -множеств.

Теорема 17. (С. С. Гончаров, С. Лемпп, Д. Р. Соломон).

Существует, бесконечное Е^1 -вычислимое семейство без Е^1 -вычислимой фридберговой нумерации.

Далее в работе эти результаты будут расширены на случай Е"1, для любого а £ О - обозначения конструктивного ординала.

Ж. Таласбаевой в [39] показано, что для любого конечного уровня п иерархии Ершова каждое бесконечное вычислимое семейство, содержащее 0 при п четном или и при п нечетном, имеет бесконечно много вычислимых позитивных неразрешимых нумераций, попарно несравнимых относительно сводимости нумераций (при п = 1 это было впервые доказано С. А. Бадаевым [35]). В дальнейшем, этот результат был обобщен Андреа Сорби и Манатом Мустафой [55] для всех уровней Е"1 иерархии Ершова, где а является обозначением любого ненулевого вычислимого ординала.

Теорема 18. (С. А. Бадаев, Ж. Таласбаева, А. Сорби, М. Манат). Пусть 5 -Е"1 -вычислимое бесконечное семейство и 0 £ если а - обозначение четного (ш £ Б, если а - обозначение нечетного). Тогда 5 имеет бесконечно много Е"1 -вычислимых позитивных неразрешимых нумераций, попарно несравнимых относительно сводимости нумераций.

Используя этот результат, а также один из результатов автора (параграф 2.3) М. Манат и А. Сорби показали в [55], что для любого а £ О существует бесконечное Е^-вычислнмое семейство без Е^-вычислимой фридберговой нумерации, но существует бесконечно много позитивных Е^-вычислимых нумераций этого семейства, попарно несравнимых относительно сводимости нумераций.

Перейдем к изучению локальных алгебраических свойств полурешеток Роджерса, точнее, к вопросам существования идеалов, содержащих и не содержащих минимальные элементы. Каждый идеал полурешетки Роджерса 71(А) содержит минимальный элемент, если А - семейство вычислимых функций или А - конечное семейство [44]. Если С - семейство всех вычислимо перечислимых множеств, тогда 7¿(С) содержит, как идеал с минимальными элементами, так и идеал без них [12], [15]. Также, существует семейство А, такое что 71(А) не содержит минимальных элементов [56].

Для арифметических нумераций подобные исследования были начаты в [37] и [52].

Теорема 19. (С. А. Бадаев, С. С. Гончаров). Если А - бесконечное ТРп+2-вычислимое семейство, тогда для любой не 0'-универсальной Е°п+2-вычислимой нумерации а существует бесконечно много минимальных накрытий а.

Этот результат имеет место и для гиперарифметической иерархии (Н. Бакланова [59]). Также в [52] было показано, что для п > 2 существуют бесконечные семейства, полурешетки Роджерса которых содержат идеалы без минимальных элементов. Позднее С. Ю. Подзоровым, в [60], было доказано, что вне зависимости от выбора семейства класс полурешеток, являющихся главными идеалами полурешетки Роджерса этого семейства, достаточно широк: он включает в себя как фактор-решетку решетки вычислимо перечислимых множеств по модулю конечных множеств, так и семейство начальных сегментов полурешетки т-степеней, порожденных иммунными множествами.

Для иерархии Ершова С. А. Бадаевым и Ж. Таласбаевой в [61] были представлены некоторые необходимые условия для семейства А С Е^1, при которых полурешетка Роджерса И21(А) содержит главный идеал, изоморфный полурешетке

вычислимо перечислимых т-степепей. Далее в работе будет показано, что для любого бесконечного Е~1-вычислимого семейства 5, полурешетка Роджерса (Л) содержит бесконечно много непересекающихся главных идеалов полурешетки Роджерса изоморфных верхней полурешетке Ь°т, здесь с = а +© а, если

а - обозначение четного ординала и с = 2а+°а, если а - обозначение нечетного.

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

Теорема 20. (А. Б. Хуторецкий [18]). Пусть Б - семейство вычислимо перечислимых множеств.

1. Если /2^2/- вычислимые 'нумерации семейства тогда существует вычислимая нумерация 7Г семейства 5, такая что -к ^.и и ц ^-к

2. Если полурешетка Роджерса К®^) семейства 5 содержит больше одного элемента, т,огда она бесконечна.

Эта теорема верна и в арифметической иерархии. Ее утверждение следует из доказательства теоремы С. С. Гончарова и А. Сорби [37] о том, что полурешетка Роджерса неодноэлементного Е°+2-вычислимого семейства арифметических множеств бесконечна и не является решеткой.

Однако, в [62] было доказано:

Теорема 21. (С. А. Бадаев, С. Лемпп). Существует семейство Т Е^Г1 -множеств и существуют такие Е^"1 -вычислимые нумерации семейства Т, что [I ^ и и для любой Е21 -вычислимой нумерации тг семейства Т либо ¡1 ^ 7Г, либо 7Г ^ и.

Другими словами, С. А. Бадаев и С. Лсмип показали, что первая часть теоремы Хуторецкого не выполняется для второго уровня иерархии Ершова. Открытым остается вопрос о том, выполняется ли вторая часть теоремы Хуторецкого. В [54] была доказана следующая

Теорема 22. (С. С. Гончаров, С. Лемпп, Д. Р. Соломон). Существует бесконечное семейство вычислимо перечислимых множеств с единственной вычислимой нумерацией, рассматриваемой как Е2 1 -вычислимая нумерация Е^Г1 -множеств.

Далее в работе будет представлено обобщение этого результата на все конструктивные ординалы (параграф 1.3). Отметим, что недавно была независимо получена

Теорема 23. (С. А. Бадаев, М. Манат, А. Сорби). Для любого ненулевого п 6 ш и {о;} и любого обозначения ненулевого ординала а £ О существует Е"1 -вычислимое семейстпво А, содержащее ровно п множеств и ^(.Д)!"1 = 1.

Основные результаты работы

1. Построен пример Е~ ^вычислимого бесконечного семейства с одноэлементной полурешеткой Роджерса, а ф 0 (параграф 1.3, опубликовано в [69]).

2. Установлены алгоритмические свойства Е~^вычислимых фридберговых нумераций семейств Еа ^множеств, а ф 0 (глава 2, опубликовано в [70]).

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

Основные определения

Иерархия Ершова

Приведем оригинальное определение Е"1 множества (данное Ершовым в [58]), где а - обозначение для конструктивного ординала.

Определение 24. Пусть Р(х,у) вычислимый предикат, который задает частичный порядок на со. Равномерно вычислимая последовательность {Ях} вычислимо перечислимых множеств является Р-последовательностью, если для всех х, у из х <р у следует Ях С Яу.

Здесь и далее, мы будем использовать клиниевскую систему обозначения для ординалов - (О, <0) с небольшим изменениями: обозначением нулевого ординала будет 0, единичного ординала - 1. Для каждого а £ О, |а|0 - ординал а, который имеет (9-обозначение а. Мы также определяем функцию четности е(х): для каждого а £ О, е(а) = 0. если |а|0 четное и е(а) = 1, если |а|0 нечетно.

Определение 25. Определим для произвольного а £ О операции 5а и Ра, которые отображают а-последовательности {Дх}з-<0а в подмножества и, следующим образом:

= {г\3х <0 а(г 6ЙД е(х) ф е(а) & Уу <0 х{г £ Яу))}, Ра(Я) = {г\3х <0 а{г е ЙД е(х) = е(а) &

<0.ф£ /?,))}№ ~ У!

£<0а

Как видно из их определений, Ра(Я) = Яа(Я) для всех а £ О и всех а-последовательностей Я.

Определение 26. Класс Е"1^!^1) для а £ О есть по определению класс всех множеств вида За(Я) (соответственно вида Ра(Я)), где Я — {^?х}х<0а пробегает все а-последовательности вычислимо перечислимых множеств, а £ О. Обозначим

Д-^Е^ПП-1.

Теперь приведем определения, используемые для определения иерархии Ершова па конечных уровнях, а также для уровня Д^1 (эти определения довольно известны и их эквивалентность другим представленным определениям описана, например, в [63]).

Определение 27. Множество А назовем п-вычислимо перечислимым (А б Е^1,), если существует равномерно вычислимая последовательность множеств что для всех х,

Л(0) = 0, А(х) = limsAs{x), и

|{s е ы|ЛД.т) ф Л8+1(ж)}| ^ п.

Определение 28. Множество А назовем ш-вычислимым (А £ Aj1^ если существуют равномерно вычислимая последовательность множеств {As}seu) и вычислимая функция f, что для всех х,

А(х) = lims АДж), и \{seu\Aa(x)?As+1{x)}\^f(x).

И, наконец, еще одно определение иерархии Ершова, которое будет наиболее часто использоваться в данной работе. Существуют различные версии (например, [64] или [65]), однако, впервые и в наиболее общей форме данное определение появилось в статьях Р. Эпштейна, Р. Крамера и Р. Хасса [66] и В. JI. Селиванова [67],[68].

Определение 29. Для всех о, € О, множество А является Е"1 -множеством, если существуют вычислимая функция f(x,s) и частично вычислимая функция g(x,s), такие что для всех х Е и выполняются следующие условия:

1. A{x)=limf{x,s), /(z,0) = 0,

s

2. g(x, s) g(x, s + 1) l<0 g(x, s) <0 a,

3. f(x, s) ф f{x, s + 1) ->• g(x, s + 1)1? g(x, s).

Пару (f,g) будем называть E"1 -аппроксимацией множества A.

Лемма 30. Для полноты приведем доказательство эквивалентности 26 и 29 [67].

Доказательство. «4=». У нас есть вычислимая функция /(#, в) и частично вычислимая функция д(х,в). Определим а-последовательность вычислимо перечислимых множеств {Ль}.

Для всех Ъ <0 а:

Яь = и Яс и {^1(3^(3* <0 Ь)(/(ж, я) = |е(Ь) - е(а)| & в) = *)},

с<иЬ

Л = {фь <0 а{х епь& е(Ь) ф е(а) к Ус <„ Ь(х Яс))}.

«=>». Возьмем а-последовательность {/4} вычислимо перечислимых множеств. Построим вычислимую функцию /(ж, й) и частично вычислимую д(х, в). Так как {Яь} равномерно вычислимая последовательность вычислимо перечислимых множеств, существует сильно вычислимая последовательность вычислимых множеств,

— и Для всех Ь <0 а Яь = У ЯОпределим дополнительную

функцию к(х,з):

1. к(х,0) = О, Ь := а

2. (а) если х € Кцх в) или ¡1(х,3) — Ь, где Ь - обозначение для предшественника

|а|0, тогда /г(.т, й + 1) = О, Ь = к(х,

(Ь)

если х ф. тогда к(х,в + 1) — /¿С<0<(МХ> <о с) (выбираем первый с

такой, что Н(:х,в) <0 с <0Ь).

Шаг 2.2 присваивает функции к всё большие значения, а Шаг 2.1 обнуляет функцию /1 и запускает процедуру заново. Тем самым, мы получаем для функции к набор «пиков», причем каждый следующий меньше или равен предыдущему. Эти «пики» и будут значениями функции д.

Конструкция для f(x, й) и д(х, в):

1. /(.т, 0) = 0,д(х, 0) не определена.

2. (а) если х Е тогда /(х,з + 1) = \е(к(х,з)) - е(а)|, д(х,в+ 1) = к(х,в), (Ь) если х <£ Яф18), тогда /(ж, в + 1) = /(ж, в). д(х,з + 1) = д{х,в).

Легко заметить, что все свойства второго определения удовлетворяются функциями /(ж, з) и д{х, в). □

Определение 31. Множество А является П~х -множеством, если в условиях предыдущего определения изменить «/(ж,0) = 0» на <?/(ж,0) = 1». И множество А является А'1-множеством, если заменить условие «/(ж,0) = 0» на «д(х,0) определена».

Отметим, что если множество А принадлежит Е~х, то его дополнение А принадлежит П"1, а любое множество из класса А"1 принадлежит как Е"1, так и П"1.

Определенную выше Е^-аппроксимацию (/, д) множества А можно усилить, добавив некоторые свойства для функций / и д.

Предложение 32. Если А обладает Е"1 -аппроксимацией (ф,^), то А обладает Е"1 -аппроксимацией (/, д) с заданными свойствами:

1. Правильная четность:

если f(x,s) = 0, то е(д(х,з)) = е(а) или д(х,з) не определена, если /(ж, й) = 1, то е(д(х, в)) = 1 — е(а).

2. Замедление:

для любого в € со и любого х > в /(ж, в) = О,

для любого в £ со и любого х > в д(ж, .ч) не определена.

Доказательство. Правильная четность. Пусть /(ж, з) = ф(ж, 5) для всех ж£ со.

1. Если ф{х, й) не определена, тогда д(х, в) также не определена.

2. Если ф^х.в) определена, тогда

Список литературы диссертационного исследования кандидат наук Оспичев, Сергей Сергеевич, 2013 год

Список литературы

[1] Клини С. К., Математическая логика. М.: Мир, 1973.

[2] Колмогоров А.Н., Успенский В. А., К определению алгоритма. Успехи математических наук, 1958, т. 13, № 4(82), с. 3-28.

[3] Успенский В. А., Системы перечисления множеств и их нумерации. Доклады АН СССР, 1955, т. 105, № 6, с. 1155-1158.

[4] Успенский В. А., Лекции о вычислимых функциях. М.: Физматиз, 1960, 492 с.

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

[6] Rogers Н., Godel numberings of partial computable functions. J. Symb. Logic, 1958, Vol. 23, No. 3, p. 49-57.

[7] Friedberg Richard M., Three theorems on recursive enumeration. I. Decomposition. II. Maximal set. III. Enumeration without duplication. J. Symb. Logic, 1958, Vol. 23., p. 309 316.

[8] Мальцев А.И., Алгоритмы и рекурсивные функции. М.: Наука, 1965.

[9] Pour-El М.В., Godel numberings versus Friedberg numberings. Proc. Am. Math. Soc., 1964, Vol. 15, No. 2, p. 252-255.

[10] Ершов Ю.Л., Нумерации семейств общерекурсивных функций. Сибирский математический журнал. 1967, т. 8, № 5, с. 1015-1025.

[11] Ершов Ю.Л., Максимальные и всюду определенные функционалы. Алгебра и Логика, 1974, т. 13, № 4, с. 374-397.

[12] Ершов Ю. Л., О вычислимых нумерациях. Алгебра и Логика. 1968, т. 7, № 5, с. 71-99.

[13] Ершов Ю. Л. Верхняя полурешетка нумераций конечного множества. Алгебра и Логика, 1975, т. 14, № 3, с. 258-284.

[14] Lachlan A. H., On the lattice of r.e. sets. Trans. Amer. Math. Math. Soc., 1968, Vol. 130, No. 1, p. 1-37.

[15] Хуторецкий А. Б., Две теоремы для существования для вычислимых нумераций. Алгебра и Логика. 1969, т. 8, № 4, с. 483-492.

[16] Хуторецкий А. Б., О сводимости вычислимых нумераций. Алгебра и Логика. 1969, т. 8, 2, с. 251-264.

[17] Хуторецкий А. Б., О неглавных нумерациях. Алгебра и Логика. 1969, т. 8, № 6, с. 726-732.

[18] Хуторецкий А. Б., О мощности верхней полурешетки вычислимых нумераций. Алгебра и Логика. 1971, т. 10, № 5, с. 561-569.

[19] Марченков С. С., О минимальных нумерациях систем рекурсивно перечислимых множеств. Доклады АН СССР. 1971, т. 198, № 3, с. 530-532.

[20] Марченков С. С., О существовании семейств без позитивных нумераций. Математические заметки. 1973, т. 13, № 4, с. 597-604.

[21] Вьюгин В. В., О дискретных классах рекурсивно перечислимых множеств. Алгебра и Логика. 1972, т. 11, № 3, с. 243-256.

[22] Вьюгин В. В., О минимальных нумерациях вычислимых классов рекурсивно-неречислимых множеств. Доклады АН СССР. 1973, т. 212, № 2, с. 273-275.

[23] Вьюгин В. В., О некоторых примерах верхних полурешеток вычислимых нумераций. Алгебра и Логика. 1973, т. 12, № 5, с. 512-529.

[24] Селиванов В. Л., О нумерациях семейств общерекурсивпых функций. Алгебра и Логика. 1976, т. 15, № 2, с. 205-226.

[25] Селиванов В. Л., Две теоремы о вычислимых нумерациях. Алгебра и Логика.

1976, т. 15, № 4, с. 470-484.

[26] Гончаров С. С., Однозначные вычислимые нумерации. Алгебра и Логика. 1980, т. 19, № 1, с. 23-44.

[27] Гончаров С. С., Позитивные нумерации семейств с однозначными нумерациями. Алгебра и Логика. 1983, т. 22, № 5, с. 481-488.

[28] Cholak P., Goncharov S. S., Khoussainov В., Shore R. A., Computably categorical structures and extensions by constants. J. Symb. Logic, 1999, Vol. 64, No. 1, p. 13-37.

[29] Гончаров С. С., Хусаинов В., О спектре степеней вычислимых отношений, Доклады РАН, 1997, т. 37, № 1, с. 21-34.

[30] Гончаров С. С., Позитивные вычислимые нумерации, Доклады РАН, 1993, т. 332, № 2, с. 142-143.

[31] Бадаев С. А., О несравнимых нумерациях, Сибирский математический журнал, 1974, т. 15, № 4, с. 730 -738.

[32] Бадаев С. А., О вычислимых нумерациях семейств общерекурсивных функций, Алгебра и Логика, 1977, т. 16, № 2, с. 129-148.

[33] Бадаев С. А., О мощности полурешеток нумераций недискретиых семейств, Сибирский математический журнал, 1993, т. 34, № 5, с. 3-10.

[34] Бадаев С. А., Минимальные нумерации позитивно вычислимых семейств, Алгебра и Логика, 1994, т. 33, № 3, с. 233-254.

[35] Бадаев С. А., О позитивных нумерациях, Сибирский математический журнал,

1977, т. 18, iV® 3, с. 483-496.

[36] Kummer M., Numberings of VJF, Computer Science Logic 1988, (Eds. E. Borger, H. Kleine biining, M.M. Richter), Lecture Notes in Computer Science 385, Springer Verlag, Berlin, 1989, p. 166-186.

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

[38] Подзоров С. Ю., Арифметические т-степени, Сибирский математический журнал, 2008, т. 49, № 6, с. 1391-1410.

[39] Таласбаева Ж. Т., О позитивных нумерациях семейств множеств иерархии Ершова, Алгебра и логика, 2003, т. 42, № 6, с. 737-746.

[40] Ershov Yu. L., Goncharov S. S., Nerode A., Remmel J. B. (eds.), Handbook of Recursive Mathematics, Recursive model theory, Amsterdam, Elsevier, 1998, Vol. 1.

[41] Ershov Yu. L., Goncharov S.S., Nerode A., Remmel J. B. (eds.), Handbook of Recursive Mathematics, Recursive Algebra, Analysis and Combinatorics, Amsterdam, Elsevier, 1998, Vol. 2.

[42] Венцов Ю.Г., Семейство рекурсивно перечислимых с конечными классами неэквивалентных однозначных нумераций, Вычисл. Системы, 1987, т. 120, с. 105-142.

[43] Kummer М. Some applications of computable one-one numberings, Arch. Math. Logic, 1990, Vol. 30, No. 4, p. 219-230.

[44] Ершов Ю.Л., Теория нумераций. M.: Наука, 1977.

[45] Lachlan А.Н., On recursive enumeration without repetition. Z. Math. Logik Grundl. Math., 1965, Vol. 11, No. 3, p. 209-220.

[46] Kummer M., Recursive enumeration without repetition revisited, Lecture Notes in Mathematics, 1990, Vol. 1432, p. 255-275.

[47] Kummer M., An easy priority-free proof of a theorem of Friedberg, Theoretical Computer Science, 1990, Vol. 74, No. 2, p. 249-251.

[48] Pour-El M.B., Putnam H., Recursively enumerable classes and their applications to sequences of formal theories. Arch. Math. Logik und Grundlagenforscliung, 1965, Vol. 8, p. 104-121.

[49] Pour-El M.B., Howard W. A., A structural criterion for recursive enumeration without repetition, Z. Math. Logik Grundlag. Math 10(1964), 105-114.

[50] Wolf C.E., Standard recursively enumerable classes I., Notices Amer. Math. Soc. 11, (1964), 186.

[51] Гончаров С. С., Предельно эквивалентные конструктивизации, Труды Ин-та математики СО АН СССР, 1982, т. 22, с. 4-12.

[52] Бадаев С. А., Гончаров С. С., О полурешетках Роджерса семейств арифметических множеств, Алгебра и логика, 2001, т. 40, № 5, с. 507-522.

[53] Бакланова Н. А., Неразрешимость элементарных теорий полурешеток Роджерса на предельных уровнях арифметической иерархии, Вестник НГУ. Серия: математика, механика и информатика, 2011, т. 11, № 4, с. 3-7.

[54] Гончаров С. С., Лемпп С., Соломон Д. Р., Фридберговские нумерации семейств n-вычислимо перечислимых множеств, Алгебра и логика, 2002, т. 41, № 2,

с. 143-154.

[55] Манат М., Сорби А., Позитивные неразрешимые нумерации в иерархии Ершова, Алгебра и логика, 2011, т. 50, № 6, с. 759-780.

[56] Бадаев С. А., Минимальные нумерации, в сб. «Математическая логика и теория алгоритмов» (Труды ин-та матем. СО РАН, 25), 1993, 3-34.

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

[58] Ершов Ю. Л., Об одной иерархии множеств III, Алгебра и логика. 1970, т. 9, № 1,

c. 34-51.

[59] Бакланова Н.А., Минимальные элементы и минимальные накрытия в полурешетке Роджерса вычислимых нумераций в гиперарифметической иерархии, Вестник НГУ. Серия: математика, механика и информатика, 2011, т. 11, Л'а 3, с. 77-84.

[60] Подзоров С.Ю., Начальные сегменты в полурешетках Роджерса вычислимых нумераций, Алгебра и логика, 2003, т. 42, № 2, с. 211-226.

[61] Badaev S., Talasbaeva Zh., Compntability in the Ershov hierarchy, Abstracts of paper of the 9th Asian logic Conference. Novosibirsk, 16-19.08.2005, p. 60-61.

[62] Badaev S.A., Lempp S., A Decomposition of the Rogers semilattice of a family of

d.c.e. sets, J. Symb. Logic, 2009, Vol. 74, No. 2, p. 618-640.

[63] Арсланов M. M., Иерархия Ершова. Спецкурс для студентов мехмата, Казань, Казанский государственный университет, 2007.

[64] Husainov В., Stephan F., Yang Y., Computable categoricity and the Ershov hierarchy, Annals of Pure and Applied Logic, 2008, v. 156, p. 86-95

[65] Stephan F., Yang Y., Yu L., Turing Degrees and The Ershov Hierarchy, Proceedings of the Tenth Asian Logic Conference, Kobe, Japan, 1-6 September 2008, World Scientific, pages 300-321, 2009.

[66] Epstein R., Kramer R.,Hass R., Hierarchies of sets and degrees below 0', Proceedings, Logic Year 1979-80, The University of Connecticut, Lecture Notes in Mathematics 859 Springer-Verlag, (1981), pp. 32-48

[67] Селиванов В. Л., Об иерархии предельных вычислений. Сиб. Мат. Журнал. 1984, т. 25, № 5, с. 146-156.

[68] Селиванов В. Л., Об иерархии Ершова. Сиб. Мат. Журнал. 1985, т. 26, № 1, с. 134-149.

Работы автора по теме диссертации

[69] С. С. Оспичев, Бесконечное семейство Е~ ^множеств с единственной вычислимой нумерацией, Вестник НГУ. Серия: математика, механика и информатика, 2011, т. 11, № 2, с. 89-92.

[70] С. С. Оспичев, Некоторые свойства нумераций различных классов иерархии Ершова. Вестник НГУ. Серия: математика, механика и информатика. 2010, т. 10, № 4, с. 125 132.

[71] S. Ospichev, Infinite family of E^-sets with a unique computable numbering, Journal of Mathematical Sciences, 2013, Vol. 188, Issue 4, p. 449-451.

[72] S. Ospichev, Properties of nuinberings in various levels of the Ershov hierarchy, Journal of Mathematical Sciences, 2013, Vol. 188, Issue 4, p. 441-448.

[73] S. Ospichev, Computable family of E^-sets without Friedberg numberings. In 6th Conference on Computability in Europe, CiE 2010, 6th Conference on Computability in Europe, CiE 2010, Ponta Delgada, Azores, 2010, p. 311-315.

[74] S. Ospichev, Families with Infinite Rogers Semilattices in Ershov Hierarchy, CiE-2011, Abstract and Handout Booklet, Sofia, Bulgaria, June 27-July 2, 2011, p. 174-179,

[75] С. С. Оспичев, Вычислимые нумерации в иерархии Ершова, Материалы XLVIII международной студенческой конференции «Студент и научно-технический прогресс», Математика, Новосибирск 10-14 апреля 2010 г., с. 28.

[76] С. С. Оспичев, Некоторые свойства нумераций различных классов иерархии Ершова, Материалы XLVII международной студенческой конференции «Студент и научно-технический прогресс», Математика, Новосибирск 1015 апреля 2009 г., с. 90.

[77] С. С. Оспичев, Некоторые свойства нумераций различных классов иерархии Ершова, Материалы научной конференции Мальцевские чтения - 2009, 24-28 августа, 2009, Новосибирск.

[78] С. С. Оспичев, Фридберговы нумерации в иерархии Ершова, Материалы научной конференции Мальцевские чтения - 2010, 2-6 мая, 2010, Новосибирск.

[79] С. С. Оспичев, С. Ю. Подзоров, Главные нумерации в иерархии Ершова, Материалы научной конференции Мальцевские чтения - 2011, 11-14 октября, 2011, Новосибирск.

[80] S. Ospichev, Some Properties of Computable Numberings in Various Classes in Difference Hierarchy, Abstracts, Logic Colloquium 2009, July 31-August 5, Sofia, Bulgaria, 2009, p. 74-75.

[81] S. Ospichev, Friedberg Numberings in Ershov's Hierarchy, Abstracts, Logic Colloquium 2010, July 25-31, Paris, France, 2010, p. 41.

[82] S. Ospichev, About one construction of Goncharov, Lempp, Solomon, Abstracts, Logic Colloquium 2011, July 11-16, Barcelona, Spain, 2011, p. 22.

[83] С. С. Оспичев, Вычислимые нумерации в иерархии Ершова, Труды Математического центра имени Н. И. Лобачевского, Казанское математическое общество, 2010, т. 40, с. 255-256.