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

/ I 3 К/ .»

- 8 ДПР 1953

На правах ру?:оииси

БЕРЕЗНЮК СТАНИСЛАВ ЛЕОНИДОВИЧ

Алгебраические свойства полурешеток сводимостей

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

АВТОРЕФЕРАТ на соискание ученой степени кандидата физико-математических наук

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

Ра-бота выполнена в Институте математики нм.Соболева Сибирского Отделения Российской Академии Наук

Научный руководитель: член-корреспондент PAII

С.С.Гончаров

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

оппоненты: ких наук, профессор

В.Л.Селиванов кандидат физико-математических наук О.В.Кудинов

Ведущая организация — Омский государственный университет

Защита состоится 16 апреля 1998 года в на заседа-

нии диссертационного совета Д002.23.01 по защите диссертаций на соискание ученой степени доктора паук в Институте математики нм.Соболева СО РАН (630090, г.Новосибирск — 90, пр. академика Коптюга, 4)

С диссертацией можно ознакомиться в библиотеке Института математики нм.Соболева СО РАН.

Автореферат разослан 14 марта 1998 года

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

1) Актуальность темы (исторический обзор)

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

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

A.Н.Колмогоров ввел понятие нумерации как математического объекта и дал методологическое обоснование изучению этого понятия. Его учеником

B.А.Успенским было предпринято систематическое изучение вычислимых нумераций частично рекурсивных функций и применения их в теории алгоритмов.

X.Роджерс независимо начал исследование вычислимых нумераций семейств частично рекурсив-

ных функций и рекурсивно перечислимых множеств. Им было введено в рассмотрение семейство всех возможных вычислимых нумераций и отношение сводимости между ними, определяющее на классе всех вычислимых нумераций предпорядок. Факторизация по отношению эквивалентности, определяемому этим предпорядком, позволяет построить частично упорядоченное множество, являющееся верхней полурешеткой. Х.Роджерс исследовал наибольший элемент этой полурешетки. В дальнейшем исследовались минимальные ее элементы и другие свойства. Пур-Эль и Ховардом было начато систематическое изучение полурешеток не только вычислимых нумераций всего множества частично рекурсивных функций или рекурсивно перечислимых множеств, но и полурешеток вычислимых нумераций их подмножеств.

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

сишто перечислимых множеств, также образующие полурешетку.

Для всех подобных полурешеток, часто именуемых структурами Роджерса, возникали одни и те же проблемы: конечность/бесконечность, плотность, наибольший элемент, минимальные элементы и т.п.

Для иолурентеток семейств рекурсивно перечислимых множеств классическими являются результаты Хуторецкого и Селиванова.

Хуторецкий ([4]) показал, что если среди всех вычислимых нумераций семейства рекурсивно перечислимых множеств есть две неэквивалентных между собой, то там обязательно найдется бесконечное количество попарно неэквивалентных между собой вычислимых нумераций:

Теорема 1 Пусть семейство рекурсивно перечислимых множеств А имеет вычислимые нумерации и и ц такие что и ^ ц. Тогда существует вычислимая нумераиия т семейства А такая, что ц < т и и т.

Селиванов ([о]) продемонстрировал, что если се-

мейство рекурсивно перечислимых множеств имеет две неэквивалентные вычислимые нумерации, то по ним можно построить такие две неэквивалентные между собой нумерации, что у них не будет точной нижней грани:

Теорема 2 Если полурешетка нумераций данного семейства рекурсивно перечислимых мноэюеств нетривиальна, то она не является решеткой.

В области минимальных нумераций основной результат установлен С.Бадаевым, которому удалось получить критерий минимальности нумераций. Этот критерий позволяет связать "внешнюю" характеристику нумерации (то, что она является минимальным элементом полурешетки Роджерса) с некоторыми ее внутренними свойствами.

Добрица ([9]) продемонстрировал связь между полурешетками индексаций конструктивных моделей и полурешетками нумераций рекурсивно перечислимых множеств:

Теорема 3 Для каждого вычислимого класса К* конечных .моделей существует вычислимое семейство 5 рекурсивно перечислимых мноэ/сеств та-

кое, что Ь(К") = ¿(5). Семейство 5' по классу К" находится эффективно.

Кроме того, Добрица рассмотрел различные свойства вычислимых индексаций для классов конструктивных моделей со сводимостью по автоэквивалентности ([(>]) и по локальным классам ([7, 8]). В этих же работах он рассмотрел некоторые аналоги условия Хуторецкого:

Теорема 4 Пусть К* — вычислимый класс конструктивных систем, а — такой его подкласс, что для некоторых вычислимых индексаций а,(3

класса К* индексные множества. /^-.,/7-» леэ/сат

"о о

в различных т-степенях (можно считать, что 1к* и существует бесконечное число раз-

личных по т-эквиваленгпности множеств /1, удовлетворяющих свойству <т А <т /д-.. Тогда у класса К* существует- бесконечное число неэквивалентных между собой вычислимых индексаций.

Теорема 5 Если К^ — некоторый подкласс класса К*, и (А/, и) £ Л'о — локально влолсимая модель для класса К" такая что для некоторой вычислимой индексации 7 класса К*индексное множество

1 д-. — не т-полное 11^-множесгпво, то у класса К* существует бесконечное число неэквивалентных вычислимых индексаций.

Теорема 6 Если у класса конструктивных систем сугцествуют две вычислимые индексации а 7, то у этого класса имеется бесконечное число неэквивалентных относительно сводимости по локальным классам вычислимых индексаций.

Теорема 7 Пусть в вычислимом классе К* две модели — (М„,г/), — и эффективная последовательность конструктивных систем {(М,-,^,-)|г £ /}, где I С ш и является начальным отрезком, удовлетворяют условиям:

1. ц и, щ = у;

2. М„ <->л. М^, М„;

3. (У(МА, А) € А'*)(У0(Эг € 1)[М{ м- А/,-];

^ И-

Тогда у класса К* существует бесконечное число несравнимых вычислимых индексаций.

Другим разделом теории рекурсии, где часто оперируют с полурешетками, является теория степеней. Наиболее важными с этой точки зрения являются степени перечислимости, или е-степени, так как сводимость по перечислимости позволяет применять наработанную технику оперирования с частично рекурсивными функциями, а многие важные классы степеней (например, Тыорииговы степени) естественно вкладываются в е-степени. Здесь также имеются стандартные классы проблем: начальные сегменты, несравнимые элементы, взаиморасположение степеней обладающих каким-нибудь особым свойством и т.п. В этой области большую работу проделали С.Б.Купер, А.Сорби, К.Мак-Эвой, С.И, Ю.Суй, Д.Дин и др.

Полурешетка е-стенепей имеет минимальный элемент. Поэтому, говоря о минимальных степенях, здесь следует иметь в виду минимальные над 0е степени. Но Гаттеридж ([16]) показал, что минимальных е-стеиеней (в указанном смысле) не существует:

Теорема 8 Если 6е&е(В) — минимальное накры-

И

4 ■

тие для с^ДА), то В £ А£

Теорема 9 Если В £ Д° не является рекурсивно перечислимым, то существует е-оператор 0 такой чтоф <с QB <е В. Следовательно, минимальных е-степеней не существует.

Более того, Купер ([18]) показал, что структура е-степеней ниже 0' является плотной:

Теорема 10 Структура е-степеней ниже 0' является плотной.

Потому для характеризации начальных сегментов ниже 0' нужно использовать степени, обладающие каким-либо особым свойством (например, степени). Купер и Купстэйк ([20]) показали, что существуют So-high собственно £¡2 е-степени:

Теорема 11 Существуют Е2-high собственно Е2 е-степени.

В настоящее время основные исследования ведутся в области минимальных пар, то есть не сравнимых друг с другом степеней. Степени, для которых не существует несравнимых, могут служить важной характеристикой начальных сегментов. Примером может служить следующий результат ([26]):

Теорема 12 Существует, линейно упорядоченный начальный сегмент е-степенеи.

2)Цель работы

Целью работы является алгебраическая характе-ризация полурешеток Роджерса, в том числе решение "проблем Хуторецкого-Селиванова" для полурешеток вычислимых индексаций (то есть доказательство бесконечности полурешетки в случае ее нетривиальности и нахождение условий, при которых она не является решеткой), а также выяснение расположения собственно е-степеней в структуре всех степеней перечислимости.

3) Научная новизна

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

4)Практическая ценность

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

алгоритмов, читаемых на математических факультетах высших учебных заведений.

5)Апроба1щя работы, публикации

Факты, содержащиеся в работе, публиковались в [11, 14, 15], докладывались на XI Межреспубликанской конференции по математической логике (Казань, 1992), Конференции посвященной 85-й годовщине со дня рождения А.И.Мальцева (Новосибирск, 1994), Европейском логическом коллоквиуме (Лидс, Великобритания, 1997), и Международной школе-конференции "Теория Рекурсии и Теория Сложности" (Казань, 1997).

6)Структура и объем. Краткое содержание

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

Определение 1 Если 5 — семейство рекурсивно перечислимых множеств, то нумерацию и : ш —> 5' этого семейства будем называть вычислимой, если множество {{х,у)\у £ их} рекурсивно перечислимо.

Определение 2 Если ,5" — семейство рекурсивно перечислимых множеств, Р — набор его вычислимых нумераций, то 7(ж, у) — вычислимая индексация Р, если

1)(Ух € ш)(3/3 € Р)Ыж,-) = £(•)];

У, ~)|-г' £ 7(2/1 2)} рекурсивно перечислимо.

Доказано, что такие полурешетки (т.н. полуре-шетпки Роджерса) всегда бесконечны. Рассматривается два возможных случая, в каждом из которых применяется своя техника доказательства, основанная на методе приоритета с конечными на-рушениеми:

Теорема 2.1: Пусть Р — набор попарно неэквивалентных вычислимых нумераг^ий семейства рекурсивно перечислимых множеств Б, содержащий не менее двух различных элементов. Пусть

среди нумераций, входящих в Р есть такая нумерация и, что P\{is] вычислим. Тогда:

1)Р вычислим;

2)существует счетное число попарно несравнимых вычислимых индексаций набора Р.

Теорема 2.3: Пусть Р бесконечный вычислимый набор вычислимых нумераций семейства рекурсивно перечислимых множеств S с бесконечным числом попарно неэквивалентных нумераций. Тогда существует счетное число попарно несравнимых вычислимых индексаций набора Р.

Кроме того найдены достаточные условия того, что подобные полурешетки не являются решетками:

Теорема 2.6: Если множество классов П^-эквивалентных индексаций данного набора нумераций Р семейства рекурсивно перечислимых .множеств R нетривиально, то полурешетка классов эквивалентности вычислимых индексаций этого набора tie является решеткой.

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

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

Литература

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

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

[3] R. I. Soare. Recursively Enumerable Sets and Degrees. Perspectives in Mathematical Logic, Omega Series. Springer-Verlag, Heidelberg, 1987.

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

[5] В.Л.Селиванов Две теоремы о вычислимых нумерациях. "Алгебра и логика", т. 15 (1976), №4, с.470-484.

[6] В.П.Добрица Сложность индексного мноэюс-ства конструктивной модели. "Алгебра и логика", т.22 (1983), №4, с.372-381.

[7] В.П.Добрица Структурные свойства вычислимых классов конструктивных люделей. "Алгебра и логика", т.26 (1987), №1, с.36-62.

[8] В.П.Добрица Локальные классы и вычислимые индексации. "Алгебра и логика", т.26 (1987), №2, с.165-190.

[9] В.П.Добрица О полурешетках вычислимых индексаций классов конструктивных моделей.. "Алгебра и логика", т.26 (1987), №5, с.558-576.

[10] С.Л.Березнюк О мощности полного набора вычислимых индексаций вычислимых нумераций одного семейства рекурсивно-перечислимых множеств. "XI межреспубликанская конференция по математической логике. Тезисы сообщений", Казань, 1992, с.22.

[11] С.Л.Березнюк О числе неэквивалентных вычислимых индексаций фиксированного семейства множеств. "Алгебра и логика", т.32 (1993), №1, с.34-44.

[12] S.L.Bereznyuk The number of nonequivaknt computable indexations for a fixed family of sets. (English. Russian original). "Algebra Logika", v.33 (1993), №.1, p.17-23.

[13] С.Л.Березнюк Верхняя полурешётка вычислимых индексаций семейства рекурсивно перечислимых множеств. "Международная конференция по математической логике, посвященная 85-летию со дня рождения Л.И.Мальцева. Тезисы сообщений", Новосибирск, 1994, с.26-27.

[14] С.Л.Березнюк, М.В.Гай лит Обобшения теоремы Селиванова. "Сибирский математический журнал", т.37 (1996), №.3, с.506-518.

[15] С.Л.Березнюк, Р.Коулз, А.Сорби Расположение собственно с-стспеней. препринт №22, издательство НИИ МИОО НГУ, 1997, 20 стр.

[16] L.Gutteridge Some Results on Enumeration Re-docibility. Ph.D. Dissertation, Simon Frazer University, 1971

[17] W. C. Calhoun. T. A. Slaman. The 11° e-degrees are not dense. .J. Symbolic Logic, to appear.

[18] S. B. Cooper. Partial degrees and the density problem. Pari 2: The enumeration degrees of the E2 sets are dense. J. Symbolic Logic, 49:503-513, 1984.

[19] S. B. Cooper. Enumeration reducibility, nondeter-ministic computations and relative computability of partial functions. B K. Ambos-Spies, G. Muller, and G. E. Sacks, editors. Recursion Theory Week, Oberwolfach 1989, volume 1432 of Lecture Notes in Mathematics, pp.57-110, Heidelberg, 1990. Springer-Verlag.

[20] S. B. Cooper and C. S. Copestake. Properly E2 enumeration degrees. Z. Math. Logik Grundlag. Math., 34:491-522, 1988.

[21] C. G. Jockusch, Jr. Semirecursive sets and positive reducibility. Trans. Amcr. Math. Soc., 131:420-436, 1968.

[22] K. McEvoy. Jumps of quasi-minimal enumeration degrees. J. Symbolic Logic, 50:839-848, 1985.

[23] K. McEvoy and S. B. Cooper. On minimal pairs of enumeration degrees. J. Symbolic Logic, 50:839-848, 1985.

[24] J. R. Shoenfield. On degrees of unsolvability. Ann. of Math., 69:644-653, 1959.

[25] A. Sorbi. The enumeration degrees of the

B A. Sorbi, editor, Complexity, Logic and Recursion Theory. Marcel Dekker, New York, to appear.

[26] S. B. Cooper, A.Sorbi Initial Segments of the Enumeration Degrees, to appear

Подписано в печать 12.03.98 Печать офсетная Заказ № 106 Тираж 100

Формат 60x84/16 Уч.-изд. л. 1

Участок оперативной полиграфии НГУ; 630090, Новосибирск-90, ул. Пирогова, 2