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

Оспичев, Сергей Сергеевич АВТОР
кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ
Новосибирск МЕСТО ЗАЩИТЫ
2013 ГОД ЗАЩИТЫ
   
01.01.06 КОД ВАК РФ
Диссертация по математике на тему «Алгебраические и структурные свойства полурешеток Роджерса в иерархии Ершова»
 
Автореферат диссертации на тему "Алгебраические и структурные свойства полурешеток Роджерса в иерархии Ершова"

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

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

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

АВТОРЕФЕРАТ

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

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

18АПРШ

005052216

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.

s

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