Алгебраические и структурные свойства полурешеток Роджерса в иерархии Ершова

Оспичев, Сергей Сергеевич

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

Оспичев, Сергей Сергеевич АВТОР

кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ

Новосибирск МЕСТО ЗАЩИТЫ

2013 ГОД ЗАЩИТЫ

01.01.06 КОД ВАК РФ

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

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

На правах рукописи Оспичев Сергей Сергеевич

АЛГЕБРАИЧЕСКИЕ И СТРУКТУРНЫЕ СВОЙСТВА ПОЛУРЕШЕТОК РОДЖЕРСА В ИЕРАРХИИ ЕРШОВА

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

АВТОРЕФЕРАТ

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

Новосибирск — 2013

18АПРШ

005052216

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

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

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

Бадаев Серикжан Агыбаевич, доктор физико-математических наук, профессор, Казахский национальный университет им. Аль-Фараби, профессор кафедры фундаментальной математики. Корольков Юрий Дмитриевич, доктор физико-математических наук, профессор, федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Иркутский государственный университет», директор института математики, экономики и информатики ИГУ.

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

Федеральное государственное бюджетное учреждение науки Институт систем информатики им. А. П. Ершова Сибирского отделения Российской академии наук.

Защита состоится 24 апреля 2013 г. в 17.00 на заседании диссертационного совета Д 003.015.02 при Федеральном государственном бюджетном учреждении науки Институте математики им. С. Л. Соболева Сибирского отделения Российской академии наук по адресу: пр. Академика Коптюга 4, г. Новосибирск, 630090.

С диссертацией можно ознакомиться в библиотеке Федерального государственного бюджетного учреждения науки Института математики им. С. Л. Соболева Сибирского отделения Российской академии наук.

Автореферат разослан «20» марта 2013 г.

Ученый секретарь диссертационного совета кандидат физико-математических наук ,

Общая характеристика диссертации

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

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

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

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

Результаты классической теории вычислимых нумераций нашли наибольшее применение в рекурсивной математике [10], [11]. Так, метод построения семейств вычислимо перечислимых множеств с конечным числом вычислимых фридберговых нумераций, предложенный Гончаровым в [12], послужил отправной точкой для исследования алгоритмических размерностей рекурсивных моделей [13], [14], [15].

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

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

В случае семейств вычислимо перечислимых множеств (/С = такой подход полностью совпадает с классическим определением вычислимой нумерации (см., например, [18]) и универсальное множество {(а;,п)|а; € а(п)} представляет собой равномерно эффективную процедуру, определяющую, попадает ли элемент х во множество а(п).

В случае К. = вычислимость а означает, что универ-

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

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

Согласно концепции Ю.Л. Ершова, полурешетки Роджерса определяют алгоритмическую сложность семейств множеств в целом и во многих вопросах могут быть более полезными, чем различные понятия сложности отдельно взятых элементов этих семейств. Можно выделить три основных направления исследования полурешеток Роджерса. Первое направление связано с глобальными характеристиками полурешеток Роджерса: мощность, решетки и т. п. Второе — посвящено характеризации нумераций, порождающих в полурешетках Роджерса элементы с особыми алгебраическими свойствами: наибольшие, минимальные, неразложимые элементы и т. п. Третье — направлено на изучение локальных алгебраических свойств полурешеток Роджерса: строение сегментов, идеалов и т. п. Рассмотрим эти направления подробнее и обратимся к истории изучения строения нумераций, порождающих экстремальные элементы в полурешетках Роджерса. Началом изучения минимальных нумераций послужила известная теорема Фридберга [7] о существовании однозначной нумерации семейства всех вычислимо перечислимых множеств. Пур-Эль и Путнам в [19] построили пример семейства вычислимо перечислимых множеств без вычислимых однозначных (фридберговых) нумераций:

{{2х,2х + 1}\х Е К} и{{2®},{2® + 1}|® £ К}, где

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

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

1. Поиск условий, при которых семейство А € Т,гп обладает Т,гп-вычислимыми нумерациями.

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

В классическом случае, некоторые необходимые условия существования фридберговой нумерации для семейств вычислимо перечислимых множеств были найдены Лахланом [20]. Затем множество необходимых условий были предложены в работах Ершова [21], Куммера [22], [23], Мальцева [8] и других. Для семейств множеств арифметической иерархии можно выделить следующие результаты:

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

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

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

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

мейства А

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

Теорема 4. (С. С. Гончаров, С. Лемпп, Д-Р- Соломон). Для любого п > 1 существует Е"1 -вычислимая фридбергова нумерация семейства всех Е"1 -множеств.

Теорема 5. (С. С. Гончаров, С. Лемпп, Д. Р. Соломон). Существует бесконечное Е^1 -вычислимое семейство без Е^1-вычислимой фридберговой нумерации.

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

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

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

Используя этот результат, Манат и Сорби показали в [29], что для любого а Е О существует бесконечное Е~ ^вычислимое семейство без Е"1-вычислимой фридберговой нумерации, но существует бесконечно много позитивных Е~х-вычислимых нумераций этого семейства.

Перейдем к изучению локальных алгебраических свойств полурешеток Роджерса, точнее, к вопросам существования идеалов, содержащих и не содержащих минимальные элементы. Каждый идеал полурешетки Роджерса ЩА) содержит минимальный элемент, если А - семейство вычислимых функций или А - конечное семейство [18]. Если С - семейство всех вычислимо перечислимых множеств, тогда ЩС) содержит, как идеал с минимальными элементами, так и идеал без них [21], [30]. Также, существует семейство А, такое что ЩА) не содержит минимальных элементов [31]. Для арифметических нумераций подобные исследования были начаты в [17] и [24].

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

Этот результат имеет место и для гиперарифметической иерархии (Н. Бакланова, [32]). Также в [24] было показано, что для

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

Для иерархии Ершова Бадаевым и Таласбаевой в [34] были представлены некоторые необходимые условия для семейства Л С Е^"1) при которых полурешетка Роджерса ^^ (Л) содержит главный идеал, изоморфный полурешетке вычислимо перечислимых т-степеней. Далее в работе будет показано, что для любого бесконечного ^вычислимого семейства 5, полурешетка Роджерса Т1~1(А) содержит бесконечно много непересекающихся главных идеалов полурешетки Роджерса Т^"1^), изоморфных верхней полурешетке Ьздесь с = а +о а, если е(а) = 0 и с = 2а+оа, если е(а) = 1.

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

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

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

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

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

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

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

В [26] была доказана следующая

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

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

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

Цель исследования.

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

Новизна и научная значимость.

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

Апробация работы. Результаты диссертации прошли апробацию на следующих международных конференциях: МНСК «Студент и научно-технический прогресс» (Новосибирск, 2008, 2009, 2010 гг.), «Мальцевские чтения» (Новосибирск, 2009, 2010, 2011, 2012 гг.), «Logic Colloquium» (София, Болгария, 2009 г.; Париж, Франция, 2010 г.; Барселона, Испания, 2011 г.), «Лобачевские Чтения» (Казань, 2010 г.). Автор неоднократно докладывал результаты диссертации на семинарах Новосибирского Государственного Университета «Теория вычислимости» (2009-2012 гг.), «Алгебра и логика» (2012 г.).

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

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

2. Установлены алгоритмические свойства Е"1-вычислимых фридберговых нумераций семейств Е"1-множеств (опубликовано в [38]).

Публикации. Результаты автора по теме диссертации опубликованы в работах [37]—[51], из них [37] и [38] входят в перечень ВАК российских рецензируемых научных журналов, в которых должны быть опубликованы основные научные результаты диссертаций на соискание ученых степеней доктора и кандидата наук.

Объём и структура диссертации. Диссертация состоит из введения, определений, трех глав и списка литературы (79 наименований). Объём диссертации 74 страницы.

Содержание диссертации

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

Затем приводятся определения. Приведем здесь некоторые из них.

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

1. А(х) = limf(x,s), f(x, 0) = 0.

2. g{x, s) g{x, s + 1) 4,<0 g(x, s) <G a.

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

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

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

Определение 2. Множество А является П"1 -множеством, если в условиях предыдущего определения изменить «f(x, 0) = 0» на «f(x, 0) = 1». И множество А является А"1 -множеством, если заменить условие «f{x, 0) = 0» на «g{x,Q) определена».

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

Определение 3. Нумераи>ию rj будем называть вычислимой, если множество {< х,у > \у £ r¡x} является Ед1-множеством.

П"1- и Д^-вычислимые нумерации определяются аналогично.

Определение 4. Нумерацию ц будем называть минимальной, если для любой нумерации ип из того, что v сводится к ц следует,, что v эквивалентно ¡л.

Определение 5. Нумерацию и назовем позитивной, если множество {{п,т)\ип = 1/т} является вычислимо перечислимым (и разрешимой, если указанное множество вычислимо).

Определение 6. Нумерацию г) будем называть фридберговой, если для любых п ^ т. г)п ф г)т.

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

Определение 7. Е"1 -вычислимую нумерацию V семейства 5 назовем главной, если любая Е"1 -вычислимая нумерация /х семейства Б сводится к и.

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

Во втором параграфе главы исследуются двухэлементные семейства Е~1-множеств. Показано, что любое такое семейство обладает бесконечным числом попарно несравнимых (относительно сводимости нумераций) Е~ ^вычислимых нумераций, где с = а +о а, если е(а) — 0 и с = 2а+°а, если е(а) = 1. Для примера, любое двухэлементное семейство вычислимо перечислимых множеств обладает бесконечным числом попарно несравнимых нумераций уже начиная с третьего уровня иерархии Ершова. В дальнейшем результаты данного параграфа будут использованы при доказательстве одного из основных результатов работы.

Третий параграф главы посвящен обобщению результата Гончарова, Лемппа, Соломона [26] о существовании семейства Е^"1-множеств-с единственной Е^^вычислимой нумерацией, а именно доказывается:

Теорема 1.10. Пусть а € О. Существует бесконечное семейство Е"1 -множеств с единственной вычислимой нумерацией.

В главе 2 работы исследуются свойства минимальных нумераций в иерархии Ершова. В первом параграфе, используя конструкцию Гончарова, Лемппа, Соломона построения Е~ ^вычислимой фридберговой нумерации семейства всех Е~а-множеств, получена:

Теорема 2.4. Для любого к существует 2к-вычислимая фрид-бергова нумерация семейства всех к-вычислимо перечислимых множеств. А также существует вычислимая функция, которая т-сводит фридбергову нумерацию семейства всех к-1-вычислимо перечислимых множеств к фридберговой нумерации семейства всех к-вычислимо перечислимых множеств. Причем эта фридбер-гова нумерация и сводящая функция строятся равномерно по к.

Здесь «/с-вычислимая» означает «Е^Г ^вычислимая». Затем полученный результат используется для доказательства одного из основных результатов работы:

Теорема 2.8. Существует минимальная ш-вычислимая нумерация семейства всех множеств из и Е^Г1.

кеы

Во втором параграфе, как и в первом, используется результат Гончарова, Лемппа, Соломона о Е~ ^вычислимой фридберговой нумерации семейства всех Е~1-множеств. Этот результат обобщается на все конструктивные ординалы, т. е. показано существование Е~1-вычислимой фридберговой нумерации семейства всех Е"1-множеств. Затем, используя результаты параграфа 1.1, доказывается существование Е~ ^вычислимой нумерации семейства всех Д~ ^множеств.

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

Теорема 2.16. Семейство всех Е"1 -множеств обладает бесконечным числом попарно несравнимых Е"1 -вычислимых фридбер-говых нумераций.

Обратимся вновь к результату Бадаева, Маната, Сорби и Та-ласбаевой. Объединяя его с результатами параграфа 1.2, получаем один из основных результатов работы:

Теорема 2.18. Для любого Е"1 -вычислимого семейства 5, такого что |5| > 1 существует бесконечно много Е"1 -вычислимых непозитивных нумераций, попарно несравнимых относительно сводимости нумераций, где с — а +о а, если е(а) = 0 и с — 2а+°а, если е(а) = 1.

М. Куммер показал, что если Е^-вычислимое семейство <5 можно представить в виде объединения двух непересекающихся подсемейств ¿>1 и с>2, где ¿п обладает Е^-вычислимой фридбер-говой нумерацией, а любое конечное подмножество элемента из 52 имеет бесконечно много расширений в 51, то 5 обладает Е^1-вычислимой нумерацией. Из результата Куммера мы будем использовать только разбиение семейства на два подсемейства, одно из которых обладает фридберговой нумерацией. Внесем некоторые изменения в конструкцию для фридберговой нумерации и получим.

Предложение 2.21. Пусть £2 - бесконечные семейства множеств, такие что:

1. £>1 П £2 = 02. Бх обладает Е"1 -вычислимой нумерацией.

3. 52 обладает Е^1 -вычислимой фридберговой нумерацией, если е(а) = 0 и П^1-вычислимой фридберговой нумерацией, если е(а) = 1.

Тогда 5 = 5] и £2 обладает Е^^-вычислимой фридберговой нумерацией.

В третьем параграфе рассматривается обобщение результат Гончарова, Лемппа, Соломона о Е;Г ^вычислимом бесконечном семействе без Е ^-вычислимых фридберговой нумерации на все конструктивные ординалы.

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

Некоторые модификации приведенной в доказательстве конструкции позволяют получить семейство Е~ ^множеств с более сложной структурой, а именно справедливо следующее.

Следствие 2.23. Пусть а € О - обозначение непредельного ординала, тогда существует бесконечное Е"1 -вычислимое семейство Ед1 -множеств без Е"1 -вычислимой фридберговой нумерации, но обладающее Е^"1 -вычислимой

фридберговой нумерацией, где Ь - обозначение последователя \a\o-

Третья глава посвящена построению примера семейства Е"1-множеств без главных нумераций. Основным результатом главы является.

Теорема 3.4. Пусть 5 — семейство А^-множеств, б С Б — Е"1 -направленное подсемейство, и пусть множество иб, если е(а) = 1 или множество (")(?> если е(а) = 0 не принадлежит 5. Тогда для любой Д2- вычислимой нумерации а семейства 5 существует Е"1 -вычислимая нумерация /3 семейства 0 такая, что

Учитывая, что класс Дд является объединением всех Е"1 для всех а 6 О, заметим, что семейство из Теоремы 2.1 не будет обладать главной нумерацией ни на одном уровне Е^"1. Рассмотрим в качестве примера семейство начальных сегментов натурального ряда, точнее Т = {0, {0}, {0,1},... }. У семейства Т нет Е"1-вычислимой главной нумерации для любого а € О, однако для семейства Т{}{ш} такая нумерация есть.

Изложение работы заканчивается списком литературы.

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

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

[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] Ershov Yu.L., Goncharov S.S., Nerode A., Remmel J.B. (eds.), Handbook of Recursive Mathematics. Volume 1. Recursive model theory. Amsterdam, Elsevier, 1998

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

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

13] 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.

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

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

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

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

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

19] М. В. Pour-El, Н. Putnam. Recursively enumerable classes and their applications to sequences of formal theories. Arch. Math. Logik und Grundlagenforschung, 1965, Vol. 8, p. 104-121.

20] A. H. Lachlan, On recursive enumeration without repetition. Z. Math. Logik Grundl. Math., 1965, Vol. 11, No. 3, p. 209-220.

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

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

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

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

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

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

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

[28] Бадаев С. А., О позитивных нумерациях. Сибирский математический журнал. 1977, т. 18, № 3, с. 483-496.

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

с. 759-780.

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

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

[32] Бакланова H.A., Минимальные элементы и минимальные накрытия в полурешетке Роджерса вычислимых нумераций в гиперарифметической иерархии, Вестник НГУ. Серия: математика, механика и информатика, 2011, т. 11, № 3,

с. 77-84.

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

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

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

[36] 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.

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

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

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

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

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

[41] 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.

[42] 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,

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

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

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

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

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

[48] 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. 7475.

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

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

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

Оспичев Сергей Сергеевич

АЛГЕБРАИЧЕСКИЕ И СТРУКТУРНЫЕ СВОЙСТВА ПОЛУРЕШЕТОК РОДЖЕРСА В ИЕРАРХИИ ЕРШОВА

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

Формат 60 х 84 1/16 Тираж 100 экз.

Подписано в печать 14.03.2013 Заказ №53

Редакционно-издательский центр НГУ. 630090, Новосибирск-90, ул.Пирогова 2

Текст научной работы диссертации и автореферата по математике, кандидата физико-математических наук, Оспичев, Сергей Сергеевич, Новосибирск

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

Оспичев Сергей Сергеевич

АЛГЕБРАИЧЕСКИЕ И СТРУКТУРНЫЕ СВОЙСТВА ПОЛУРЕШЕТОК РОДЖЕРСА В ИЕРАРХИИ ЕРШОВА

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

I4" ДИССЕРТАЦИЯ

О 00 со

на соискаиие ученой степени кандидата

СО

т— физико-математических наук

СО 8

О -

СМ ю

Новосибирск — 2013

Оглавление

Введение 3

Определения 15

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

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

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

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

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

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

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

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

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

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

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

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

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

Введение

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

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

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], что для любого а £ О существует бесконечное Е^-вычислнмое семейство без Е^-вычислимой фридберговой нумерации, но существует бесконечно много позитивных Е^-вычислимых нумераций этого семейства, попарно несравнимых относительно сводимости нумераций.

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