Иерархическая классификация арифметических множеств и индексные множества тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

АКАДЕМИЯ НАУК СССР СИБИРСКОЕ ОТДЕЛЕНИЕ

инстатут математики

Специализированный совет Д 002.23.01

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

СЕЛИВАНОВ Виктор Львович

уда 510.5

иемрхическая классификация аиишичеомх

множеств и индексные множества

01„01.06 - ма*емйтшгаская логика, ' алгебра и теория чисел

С7)

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

Новос1.а'ирск - 1989

. Работа выполнена в Новосибирском ордена Трудового ; Красного Знамени государственном педагогическом института

Официальна оппоненты - доктор физико-математических наук, - профессор С.С.Гончаров, доктор физико-математических наук, профессор А.Н.Дёгтев, доктор физико-математических наук Р.В.агрейвалд

Ведущая организация - Институт математики с Вычислительным | центром АН МССР

Защита состоится " "_198$ г. в_ча-г

сов на заседании Специализированного совета Д 002.23.01 при Институте математики Сибирского отделения АН СССР по адресу: , 630090, Новосибирск, 90, Университетскир проспект, 4. ^ С диссертацией можно ознакомиться в библиотеке Института

■ •. математики СО АН СССР.

^ Автореферат разослан " " 1989 г

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

Специализированно го совета /

доктор физ. -ыат.наук Е.А.Палптин

'¡Г ■

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

Работа посвящена двум большим разделам теории алгоритмов - теории иерархи? и иг -.ексным множествам. Оба раздела возникли в период формирован" т теории алгоритмов и играют в :-вй це—| нтральную роль. В замеча'изльньк работах 30-х годов Чёрча,Кли-| ни, Тьюринга и Гёделя были получены основополагающие факту о природе алгоритмов: доказана эквивалентность различных уточ- ; нений понятия вычислимой функции, сфорлулирован и обоснован тезис Чёрча, доказаны теоремы об универса".ьной функции, 5-пнг -теорема и теорема о рекурсии. На отой основа далось доказать неразрешимость мноп ; ваннеШгах алгоритмических проблем математики. Все это привело к бурному развитию теории алгоритмов, которое продолжается сейчас.

Исследование рекурсивных иерархий началось с р?"ют Клини ¡2бЗ и Мостовского [32] , в которых введена и изучена иерархия, называемая теперь иерархией Клини-Моссовского. Класс

1п<оо) этой иерархии состоит из всех подмножеств на- ; туральиого ряда О) , определимых з системе (СО*, +,», О, -3) ;

-формулой языка логики предикатов. Из-за связи с ар и?.« с— ■ таенй иерархия называется такие ерифлеткческой. Чтобы не делать некоторых исключений, будем считать Пп обозначает класс всех дополнений до ']> "-множеств, — 51 £ ^ Важным свойством арифметической иерархии являеч я наличие в любом к зжества, наиболысего по т-сводгс.гасти, называемого "2°-универсальнш, и соотношения и = , т Па • свойства являются характерными для любой иерархии. Другим ваянш свойством начнется доказанная Клшк и Постом связь с Тьюрингов»! скачком: при любом а<ш универсальноо множество рекурогазко изоморфно Т-скачку универсального множества.

дальнейшее развитие теории алгоритмов привело I; появления друг; л иерархий. Они естественно расрздедася на более грубые и более тонкие, чем ари^етическая. Важнейшей грубой иерархией является аналитическая иерархия {ЗЕ^ц-^ш » "Г£К~ зг.е введенная ¡{лини. Она с ределяется по аналогии с аряфмети-

ческой, только теперь наряду с к лторш по числам можно на-вёшиаать и кванторы по Функциям «э Ш в а) . Сразу было заме-| чено, что и.' ^ Д. , и возникла проблема характеризации I

Ц<СО 11 • т

класса ¿4 через более прэстые множества. Дцдисон заметил [15] , что эта проблема аналогична известной проблем из дес-кргативной теории множйств, если считать арифметическую иерар-¡ хию аналогом борелевской, а аналимяескую - аналогом проектив-' ной иерархии Н.Н.Лузина. Эта аналогия оказалась исключительно глубокой и плодотворной. Как выяснилось, в случае иерархий классов функций .мы по существу имеем дело с единой теорией, в | которой классические иерархии являются "предельными" случаями ! рекурсивны*. Аналогия Аддисона Хорошо поясняет решение проблемы характеризации . . Надо построить трансфинитное продолжение арифметической иерархии по асем рекурсивны' ординалам -аналог иерархии Боряля по всеа счетным ординачам., Объединение : всех уровней этой керархии, называемой гиперарифметической, и дает . £27,353 . Эта теорема Суслина-Клини замечательна тем, что дает информацию об определимости в логике второго порядка. ' Из других грубых иерархий заметную роль играет иерархия, получаемая итерированием операции гиперскачка £353 , она аналогична иерархии С-множеота,

В данной работе нас в основном будут интересовать тонкие иерархии, поскольку они наиболее полезны в изучении/ ндексных 'множеств. Первым примером такой иерархии (не считая субрдоур-Ьилных, которые здесь не рассматриваем) была иерархия Ершова [4]. Оказалось, что уЗЕ^ Яйг » к возникла ¿н&логичная рассмотренной выше проблеме задача хсрактеризации "кийссл . Она решается [4, ч.П^ также путем трансфкнитного '¡^одолкьния иерархии Ершова по всем рекурсивным ординалам:

= Д® , г^е (0» - клиниевская система орди-

'йавышх обозначений • В [4, ч.Пу получено описание иерархии Ершова через т-с-качок, аналогичное описание арифметической иерархии через Т-скачок. Аналогом иерархии Ершова в дескриптивной теории мнонеств является разностная иерархия, восходящая к Ку^ато ведому ч Хаусдорфу. Иерархия Ершова изуче- : на не столь полно, как ар -ыетическая. Так, в [4, ч.Ш^ оста- ; влены откр1Г.ли два вопроса о релятивизованных вариантах "Той

иерархии. Многими авторами (Купер, Лахлаи, Джокуп, Шор,Ы.М.Ар-1 слагав, Н.Р.Бухараев, Ш.Т,.Итмухаметов и др.) изучались вопросы'

0 Т-степенях -множеств и о связи иерархии Ершова с кяас- | сификацией высоких-низких множеств £ЗбЗ . Эти вопросы будут I рассматриваться и в .э'^й работе. .' ' ' :

Анализ теоремы ;"!у>. хииа-Клини, характеризацки и мно-

гих аналогичных фактов из дескриптивной теории множеств (С-множества, (Я-множестьа н др.) показывает естественность и важность следующей задачи: найти естественный класс иерархий 3 такое, что: гиперарифметическая иерархия принадлежи! 3 ; если Ю не дискретна в данном уровне, то найпется иерархия

1 « 3 „ являющаяся плотным утончением I в этом уровне; любая;

„ кроме гилерарн|мзтической, является плотнш утэнчвни-; ем подходящей I 6 3 в некотором уровне; любая последователь- ; ность иерархий из 9 , каждая из которых утончает предыдущую I конечна. Используемые понятия буду1? уточнены ниже. ' : смысл ! ясен из примеров: гиперарифметичвгяая иерархия - плотное угон-ченке аналитической в первом уровне,, иерархия Ершова - плотно о утончение гиперарифяетической во второй, ур^чне» иерархия Ершо~1 ва дискретна, т.е. не имеет утончений ни в каком уровне. ■

Класс 3 давал бы в определенном.смысле вдеальнуя классификацию гиперарифметических множеств с точки зрения Георга иерархий. Поэтому будем называть поставленную задачу проблемой нахождения полной иерархической классификации гкперарифмети- : ческих множеств (или ар!ф.!етическ"х множеств - последнее в том случае, когда речь в постановке задачи *лдет только о конечных уровнях). Эта пробл61/.а впервые поставлена авторам [44) . Независимо близкая задача поставлена в дескриптивной теории множеств А.Луво » Эта проблема будет решена ь данной работе.

Рекурсивные иерархии имеют много применений. Это обусловлено тем, что иерархии ввделтзт в очень сложной структуре степеней неразрешимости некоторые "эталонные" степени, с которыми ¡ложно сравнивать по сложности различные объекты. Поскольку оти эталонные степени упорядочены "почти" кгж ординалы (за исключением того, что ка.едое эталонное множество т-несравнимо со своим дополнением), поязляется возможность измерять алгоритмическую сложность . дояеетв ординалами аналогично тому, как гесме.ричоские или физические величины измеряются числа-

йп. Ситуацию поясним на рис. I. [Здесь а0, й0 - пг-степени,!

оп_ оделяемые соответственно множествами 0 и со , а "конус" со/ стоит из остальных ИХ-степенеР. Известный метод кодирования конструктивных объектов натуральными числами сильно расширяет область применимости, иерархий. Поскольку иерархии - инструмент более грубый, чем тепени неразрешимости, на первый взгляд ка-Рис. I жется, что возможность их приме-

нения невелика. Ка самом деле ото не так; естественно возника-щие мюжес.'ва, как правило, универсальны б некотором конечном •уровне подходящей иерархии и потому могут быть "измерены" топко (с точностью до рекурсивного изоморфизма), ¿тот "эмпири- , ческий" факт в лрдаенеьии к индексным множествам впервые сформулирован Роджерсом, по о тому будем его называть тезисом Род-керсн.

Для примера рассмотрим некоторые применения к логике. Хо-известный результат бефор-.1ана (см. [п} } показывает, что в любой рекурсивно перечислимоР Т-степени найдется рекурсивно ■аксиоматизируемая элементарная теория, все "естественные" рекурсивно аксиоматизируемые неразрешимые теории (например, арифметика Пеане или теория групп) универсальны в . Интерес- ] ныо результаты по харвктеризации сложности различных классов . пре,1Лоаений получены М.Г.Перетятькиньш [Ю] . Например, если - гёделева нумерация всех предложений конечной досаато'но богатой сигнатуры, то множество {п! полно и 1 имозт поостую модели универсально в П| , а имеет \

простую модель } - в .

Перейдем к индексныл множествам,,Следуя А.И.Мальцеву, . стандартную нумерацию всех частично рекурсивных функци;! ■ (ч.р.ф.) будем называть нумерацией Клини и обозначать X , а нумерация ьсех рекурсивно перечисяимых множеств (р.п.м.) бу- ' дем называть нумераций ГГоста и обозначать 31 . Индексным множеством семейства ч.р.ф. / называю"1 эе"ЧА)в-{п| А) , анаяогичш-.для р.п и. В«пл .*ная определение нумерации Клини,

видим, что лН(М можно отождествить с совокупностью всех ал- ! горитмов, вычисляющих функции из А о Известные результаты теории нумераций показывают, что индексное множество определено весьма инвариантно: индексные множества одного л того ко семейства в двух главгчс вычислимых нумер;ациях рекурсивно изоморфны. Бее ото показывает, что индексные кнсжествп являются естественными и важньш объектами п обусловливает полезность их изучения» Исследование индексных множеств мокго разбить на 3 направления! I) экстенсионально;;, т.е. по возможности без ссылок на номера, описание семейсгв, индексные шоже-ства которых лежат в данном классе данной иерархии, 2) вычисление сложности конкретных вакных для теории г. горптмов индексных множеств и 3) изменив степеней индексных множеств г.о денной алгоритмической сеодимости.

В замечательной работе [33],от-юсяще Kc.i к I), Райе получил две важных теоремы,носящих нше его имя» Пусть Д - семейство р.п.ы. Первая теорема Райса утверждает, что 1С чЛ) рекурсивно з точности тогда,когда А пусто кли совпадает i классом всех р.п.м. Вторая теорема (называемая такяе теоремой Райса-Шапиро) утверждает, что А) р.п. в точи vsи тогда, когда к пусто или является классом всех р.п. надшояеетв некоторой эффективной последовательности конечных тожеств= Впоследствии В.А.Успенскнй [14] , А.И. Мальцев н ЮЛ.Ераов (см. Г51, ) распространили эти результаты ка абстрактные классы нумерованных .множеств, БКлючающие нумераций Клини. Первая терема Ра с а показывает, что никакое негривка. ьное свойство вычислимых функций нельзя эффективна распознать по виду алгоритма? ото является отправной точкой в некоторых исследованиях по теоретическому программированию. Вторая теорема Райса сыграла свою роль в формулировке понятия нумерованного множества с аппрок- : симацией и в применении к функционалам конечных типов г5} , что таяве интересно для теоретического программирования. Исследования в направлении 1} продолжались Райссм [34] , Деякером и Майхиллом |1б'} и другими авторами. Роджерс [il] . поставил проблему экстенсионального опг акия семейств р.п.м., индексные множества которых лежат з при га ъ-1 . Этим

и близкими вопросами занимались Джокуи (см, fill , с.471), ГрасскнЛю] , Х^й |23] , автор [12,13] и другие, но

проблема оставалась нерешенной. ,

Много внимания в литературе уделялось направлению 2), По ! существу, введение любого нового класса р.п.м. сопровождалось | попытками вычислить сложность его индексного множества. Это I объясняется, помимо естественности такого вопроса, неожиданны- ' ыи и глубокими применениями некоторых из этих результатов. Так,1 Ейтс [37] использовал свою теорему о том, что для любого р.п.м.1 Т множество {а\У„ет т) универсально в "2зТ, для относите- ! льни простого доказательства теоремы Сакса о плотности р.п. I Т-степеней. Херрман £243 сумел применить оценки сложности ин- ■ дексных множеств для доказательства неразрешимости элементарной теории решетки р.п.м. Интересные результаты получены Ейтсом • [38} и С.Каплибековым [7] : для любого р.п.м. Т множества

- ыкпвщт^ , {п1т5?тзгл\ и {п-^ос^в нетривиальных случаях универсальны в Ид , а множество{п1яа^тТ

- в П3. Из других результатов отметим полученную независимо Ю.Л.Ершовым и Л.Хэй ( [4, чЛ] и [193 ) классификацию индексных множеств конечных семейств конечных множеств. Оказалось, что любое такое индексное множество универсально в одном из 51 ц,

п;1 (п<со).

Мы уделим большое внимание этой проблематике, причем впервые задача будет рассматриваться в большой общности: попытаемся классифицировать индексные множества предикатов, формульно определимых в решетке р.п.м. (Б; и,П). Очевидна связь этой задачи со сложностью элементарной теории ТЬ(Б) и с модельными свойствами ТЬ(&). При этом оказываются необходимыми описанные выше иерархии из 3 . Например, из наших результатов будет следовать, что множество 1<т,п>\Жт<=я:пл (Ят#0 У'Яц^оо)} нельзя охарактеризовать с помощью арифметической иерархии и релятивизованных вариантов иерархии Ершова. Если мы хотим сохранить упомянутый вше тезис Роджерса, надо искать новые иерархии, позволяющие оценивать такие множества. Аналогия с ситуацией, когда желание измерить диагональ единичного квадрата приводит к необходимости расширения системы рациональных чисел. Отметим, что такого рода соображения сыграли большую роль .в формулировке и решении проблемы полной иерархической классификации арифметических множеств.

В направлении 3 изучались в основном структуры т- и Т-степенеЙ индексных множеств. Интерес к этому объясняется | тем, что эта задача является в определенном смысле предельным | случаем задачи 2) и тесно связана с изучением фактор-объектов данной нумерации. В этом направлении много работала Хэй [2022] , однако полученные результаты косили в основном локальный! характер. Не было получено результатов, относящихся ко всей I структуре гп -степеней индексных множеств.

Целью диссертации является продолжение исследований упо- ; мянутых вопросов, а именно: I) исследование релятивкзованных ! вариантов иерархии Ерлова и ее соотношения с иерархией высоких1 -низких множеств, 2) построение полной иерархической классификации арифметических множеств и исследование построенных пера-. рхий, 3) разработка общих методов вычисления сложности индексных множеств, определимых в естественном языке, с помощью построенных иерархий, 4) получение общих результатов о структуре гп -степеней индексных множеств, 5) решение проблемы экстенсиональной характеризации семейств, индексные множества которых лежат в данном классе арифметической иерархии.

В соответствии с этим диссертация разбита на 5 глав. Наедая глава разбита на 4 параграфа, нумерация которых сквозная. Обдай объем работы 245 с., список литературы келвчает 94 наименования.

Наиболее принципиальные результата названы теоремами, их 10 и их нумерация сквозная по всему тексту. Нумерация оетапьны:: утверждений своя в каждом параграфе. Так, предложение 5.1 - это предлопение I из § 5. На "качественном" уровне основные результаты могаю сформулировать так: а) полностью изучено взаимное расположение иерархии Ерлова и иерархии высоких-низких мно -яеств, б) подробно исследованы редятивизованные варианты иерархии Ершова, что позволило, в частности, уточнить постанов!:;/ задачи о полной иерархической классификации арифметических множеств, в) найден естественный класс иерархий, полностью классифицирующий арифметические множества, г) найдено описание построенных иерархий с помощью теоретико-множественных операций, которое показывает, что эти иерархии начнется рекурсивным аналогом степеней Уэджа борелевских множеств [29] , д) найдены применения построенных иерархий к вычислении сложности

дехснкх множеств, что позволило полностью классифицировать булевы комбинации А-преднкатов Лахлана и ответить на один вопрос! Со ара [36] , е) 'показано, что проблема экстенсионального опи- \ саниа вдек ных множеств решается положительно при П>В и | отрицательно при п = , ж) найдена глубсчая связь м...яду теорией полных нумераций и иекоторы..и вопросами теории алгоритмов, что приводит к многочисленным применениям теории полных нумераций к степеням неразрешимости, вычислению сложности конкретных индексных множеств и к изучению структуры т-степеней кн-! дексных множеств.

Применяемые методы исследования весьма разнообразны. Ори-; гянальны алгебраические катоды в главах 2 и 3, где проблемы-решаются путем "наведения" подходящей алгебраической структур и достаточно глубокого ее изучения. На протяжегчи всей работы исподьзуютсд теорема о рекурсии для предполньк нумераций, нумерованные множества с аппроксимацией и теория, полных нумераций. В главах 2, '4 и'5 используются идеи из теории операций над ¡жожестзамь, а в главах 3 и 5 - из теории конструктивных к : 1 р.п. алгебраических систем. В главе I используется оригинальная комбинация метода приоритета и метода "китайских ящиков" Лахлдна.

Результаты диссертации докладывались на семинарах "Теория 1 нумераций" V! "Алгебра и логика" в Новосибирском университете, ■ на семинарах по математической логике и теории алгоритмов в Казанском, Московском, Казахском и Латвийском университетах, в, ЛСМИ АН СССР, в пленарных докладах на 8 и 9 Всесоюзных конфе- , ренциях по математической логико, в секционном докладе на 8 М&адушродном конгрессе по логике, методологии и философии науки е г.Москве.

Все основные результаты диссертации Являются новьми и ; опубликованы в [39-54] .

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

В главе I ..зучавтся иерархия Ершова. Пусть 6т>- П-я итерация Т-скачка, М^й^Ц

стоит из всех ¿tt-множеств, не Т-экБивалентных никакому j йа -множеству, Dn состоит из всех Д~а-множеств, не Т-экви-j валентных никакому множеству из У Л 5V . Следствием теоремы |

I является следующее утверждение, пол'стыо описывающее взаимное расположение иерархии Ершова и иерархии высоких-низких ■

множеств - двух важнейших

, О t

классификаций йг -множеств : ; классы SanLa.nf> Saf\ Hrt+1 : и SaHM непусты при всех I

а« О .(о^О и классы DanLRH, да.(\ Нц^ и ОапМ непусты при ti<.w> и предельном ае О ; Da~0 при любом непредельном а g О. р Этот результат заверша-

ет ряд работ в этом направлении. Так, из теоремы Мучнина-Фрид-берга следует непустота ВаП Ц при |dl G = , из теоремы Сакса о скачке следует непустота классов SQnLnHy SaH НгИ при lal0 - 1 , теорема Мартина-Лахлана-Сакса устанавливает непустоту SanM при iа) 0 -1 , см. [il^ . Непустота Sa при lal

0 - 2 установлена Купером,' а при ¡a(Q со - Эпстей- _ ном, Хаасом и Крамером [I?j . Непустота Sa для всех а>М и непустота Оц для предельных a установлена автором {41, 47] , близкие результаты независимо получены в [21 и [25 J . Непустота классов SanLrif.fî S4n Нш, и $afiM при !cl0=2 установлена Ш.Т.Ишмухаметовьм '[6^ . Его доказательство использует специфику разностей р.п.м. и не проходит, на кой взгляд, для других уровней. Наше доказательство основано на других идеях, годится для всех уровней и намного короче.

В § 3 решены дез вопроса о релптивизованных вариантах иерархии Ершова, поставленные в [4, ч.И j . Основной является

ТЕОРЕМА 2. Включение <= строгое для

универсального множества Т . Классы ' .и

совпадают для любого рекурсивного ординала d. , тг

Здесь 2 ц' - иерархия Ерзюва, релятивизованная относительно X . Отметим, что утверждение о Г1%универсальном X

"1,0 О 0м

независимо доказано в . Равенство ' ~

вакно для дальнейшего. Оно наводит на мысль, что при изучении гиперарифметических множеств достаточно ограничиться рассмотрением иерархий по системе О . Под иерархией будем понимать , последовательность {!> а}аеО » удовлетворяющую условиям: при

любом ае О класс ~2.а замкнут вниз по т-сводимости и имеет; универсальное множество ба ; равномерно по а-<0б выполняются, соотношения ба©ба «£т е'б и рпг(ба") • Здесь © :

и рт - операции прямой суммы и рт-цилиндрификации |4,ч.Ш].! Из условия рпг(ёа")«от€а вытекает существование естественной нумерации для и соотношение . Отметим, что в ;

определении иерархии можно заменить рт(йа) =ет ёа на более слабое условие 6а , постановка задачи иерархической ;

классификации при этом не меняется. Условие ргп (ба) получается автоматически из решения этой задачи.

В § 4 дается точная постановка задачи. Иерархию ^а\аеО называем утончением иерархии { аео в уровне б^О , если , € и е .Утончение

плотное, если = . Иерархию назы~

ваем дискретной, если она не имеет утончений ни в каком уровне Ь Ф А . Примером дискретной иерархии является иерархия Ершова. Это вытекает из предложения 1.1 о том, что все классы С.6 ф -О имеют универсальные множества. После этих определений поставленная выше проблема полной иерархической классификации становится точной.

Эта проблема решается в главе 2. Точнее, здесь рассмотрен более простой вариант этой проблемы, когда в приведенной выше постановке задачи речь идет только о конечных уровнях. Этого достаточно для последующих применений. Общий случай рассмотрен : в [44] .

В теореме 3 строится естественный.класс иерархий 3 , дающий полную иерархическую классификацию арифметических мно~ ■ жеста. Конечные уровни всех иерархий из 3 можно расположить : : в последовательность е^ир^, такую,

что П^ и Др. при °(.<$,<е0.

'¡сорема 3 опубликована в 1933 году. В том же году поязи-

лась работа А.Луво £29") , в которой ставится и решается про- , блема полной иерархической классификации борелевских множеств.1 Постановки задач з обеих работах схожи, но реоения по виду , сильно различаются. У нас иерархии получаются итерированием | некоторой трехместной операции в , осоздающей операции Ш--и Т-скачка, и дапцей универсальные множества во всех уровнях ! всех иерархий. У Луво иерархии описываются с помощью довольно эзотических теоретико-множественных операций. Поэтому интере-, сно сравнить полученные решения.

В теореме 4 дается описание классов (<*< еа) с помощью операций Луво. Оно показывает, что, по-видмому, наши иерархии.можно рассматривать как рекурсивный аналог иерархий Луво. Это подтверждает их естественность. Отметим, впрочем, что эта аналогия не такая полная, как аналогия между гиперарифметической и борелевской иерархиями. Например, иерархия Ершова (а также остальные иерархии из е! , за исключением ги-перари^ыетической) не экстенсиональна, т.е. возможен случай, когда ^ ПРИ о ~ о ' Отличие также в том, что структура гп -степеней очень сложна, в то время как ее клас- ; сический аналог - степени Уэджа борелевских множеств - "почти" вполне упорядочена (за исключением того, что степень множества может быть не эквивалентна степени дополнения этого множества). Таким образом, для степеней Уэджа борелевских множеств рис. I выроядается до отмеченных точек и их прямых • сумм, хотя соответствующий ординал очень велик.

Точная формулировка теоремы 4 громоздка, поэтому приведем для примера описание некоторых Так, совпадает с

при к < из , а совпадает с , где «¿0»о, и***.

Более общо, пусть р(о,к) = к, р0н»,1с)= шр<а'>0 . Тогда

•^ЭСп.км) совпадает с классом иерархии Ершова, ре-

лятивизованной относительно 0Са\ Универсальное множество в 2и)1.к получается к.-й итерацией гп-скачка начиная с -универсального множества. Строение трех классов поясним на рисунке:

Например, состоит из множеств, представимых в виде

объединения заштрихованных частей, лежащих в указанных классах и отделимых р.п. множествами так, как указано на рисунке. Отметим, что классы вроде и Тщ^ю сильно отлича- ;

ются от классов, изучавшихся до работы [44^ . Так, 51 а,+со~ универсальное множество нельзя получить никакой итерацией по , системе О операторов пх -скачка, релятивизованных относительно 0Ш1 Сп.<со") . В то же время оно лежит в и к : нему т.-сводятся ^-универсальное множество и его допол- ' нение.

Свойства последовательности наводят на мысль,

что она может служить "шкалой", на которой реализуется тезис Роджерса, т.е. любое "просто определимое" индексное множество универсально в одном из , Пл (оС<£0) . Частичным подтвер-. ждением этого и "внешним" оправданием иерархий из 3 служат результаты главы 5, в которой эти иерархии применяются для классификации индексных множеств, п. -местный предикат на решетке р.п.м. ё называется А-предикатом [281 , если его истинность на наборе р.п.м, (б.,,..., полностью определяется условиями на число элементов в множествах, определяющих ; атомы булевой алгебры, порожденной множествами ба. Примером А-предиката может служить предикат \ Л к,пбг|=3 Л [^П^НБ л 15.,П52|»0. ) ТЕОРЕМА 9. Индексное множество любой булевой комбинации А-предикатов универсально в одном из , П^ («¿ссо10), [: и .все возможности реализуются.

; Эта теорема является первым.примером полной классифика- ,

; ции индексных множеств довольно замкнутого класса формульно Г'определимых в 8 предикатов. Результат интересен также тем, ! что обосновывает необходимость введения "экзотических" клас- ; 1 сов ¿Г^ . Без них невозможно было бы измерить даже такое про-

стое . дцексное множество, как ^<т,п> \ л I

Л (Ящ^Р* у ТГц ^ш)) .Из доказательства теоремы 9 еле-,' дует, что оно универсально в 1. •

В § 20 с использованием теоремы 9 доказывается ;

ТЕОРИЙ 10, Если б - индексное множество формульно оп-, ределимого в -б предиката, то либо б универсально в одном I из , ^а1 {а со) , либо любое -множество т- ' сводится к <6 >, либо любое П^-множество ш -сводится к б . | Здесь же-доказано, что этот результат не переносится на I решето'ЧЯые предикаты (т.е. предикаты, инвариантные относите- ; льно автоморфизмов решетки 5 ). Из этих результатов следует ; сущес$вЬ!в$#гё решеточного не формульного предиката с индек- | сный ^{йбк&Ством из Аг . Это отвечает на один вопрос Соара из ;

;В § Доказаны также результаты, усиливающие и упрощаю-; щие !бЬЙЗе 'ранние результаты Ю.Л.Ершова [4] , Хэй [19, 23] и ГраШМа ¡[-18[] ро близкой проблематике.

&Й«е»г1й1, что автором доказаны и другие результаты, час- , тй*1йо 'ЬОДТвёр'ждающие гипотезу [44]о том, что индексное множе-с^вб -Мбс/го!формульного предиката универсально в одном из

Они не вошли в диссертацию во избежание ее чрезмерного'увеличения. Приведем два из них. Для любого найдется '^йрмульный предикат, индексное множество которого

универсально в Для люб. о предложения ^ языка )

индексное 'множество класса всех р.п.м. 6 , у которых решетка V (о) 1р.'п. надмножеств по модулю конечных множеств является булевой алгеброй и удовлетворяет , универсально в одном из ,'ПЛ (об<е0).

Основным достижением главы 3 является установление тесной взаимосвязи между теорией полных нумераций А.И.Мальцева 1, Ю.Л.Ершова и некоторыми традиционными вопросами теории алгоритмов. Нумерацию V назовем Т-предполной, если для любой ч.р, относительно Т функции найдется рекурсивная функция

д такая, что \>§(зг)== при условии, что \у(х) определе-; -

но. Нумерацию V называем Т-полной, если.выполняется это жо условие и есть некоторый фиксированный элемент в слу-

чае, когда не определено. Нумерации V называем Х-2-

полной, если она X -полная и для любого «е^/ найдется | рекурсивная функция 1 такая, что у^ог,^) ■= v»: при у ^ и V ^ равно некоторому фиксированному элементу при . Через Н0Св), Н< (£) и Hj.CS) обозначим совокупности всех X -предполных, г-полных и X-2-полных нумераций вода V: ш —р- Э соответственно. Опишем предпорядки где $ - отношение сводимости нумераций.

Пусть (Р-,б) - произвольный предпорядок, А и В - конечные подмножества Р . Назовем В обобщенной верхней гранью {о.в.г.) для А » если авб для всех а« А, бе В , и для всякого хер из (авж) следует ЗБ^ВСвеж) .

Предпорядок (Р;е) назовем дискретной обобщенной лолурететкой (д.о.п.) ранга- п , если; для любого непустого конечного Аср существует В1» Р такое, что « п , В есть о.в.г. двя А и А есть обобщенная нижняя грань для В ; существует А 5 Р , не имеющее о.в.г. мощности <П .

Из предложений 9.1, 10,3 и теоремы 5 вытекает следующее утверждение о предпорадках (Н'(Б); «О для конечного Б : в (Н0(3)-, е) никакое непустое конечное множество без наибольшего элемента не имеет о.в,г.; (Н^Св)»«) есть д.о.п. ранга { (Н2(3); <) есть д.о.п. ранга 48|2 .

Заметим, что-в доказательстве теоремы 5 существенно используются результаты главы 2.

Нумерацию у назовем универсальной Т-предполной, если она х -предполная и любая X --предполная нумерация является ее фактор-объектом. Аналогично вводятся понятия универсальной х -полной и универсальной Т-2-полной нумерации.

В § 9 и 10 установлены некоторые свойства таких нумераций. Изучены также свойства частичных порядков вида (А; «*»*), где ы. - т -предполная нумерация множества А , ^ - нетривиальный р.п. относительно X порядок на А с наименьшим и наибольшим элементами. Получены также некоторые общие результаты об индексных множествах таких нумераций.

В теореме 6 из § II устнонлено, что многие важные для теории алгоритмов нумерации являются либо универсальными т -предполными, либо универсальными г -полными, либо универсальными X -2-полными для подходящего те аз. К числу таких

нумераций относятся: нумерации Клини и Поста; факторизации ну-j мерации Поста относительно любой нетривиальной решеточной кон-| груэнции на U,п) , содержащей равенство по модулю коне-j

чных множеств; факторизации стандартной нумерации класса "Za , (аеО, по эквивалентности относительно обычных алгори-

тмических сводимо стей, а также относительно сводимости

Зп(б",1«тгс*') ; декартовы степени указанных нумераций и многие другие нумерации.

В доказательстве этого используется теорема М.М.Арсланова [l3 об та-неподвижной точке и теорема Р.Соловея [36, гл. 12-3 о .

В § 12 излагаются многочисленные приложения, которые полу-г чаются применением к нумерациям из теоремы б результатов из § 9 и § 10. Наиболее неожиданными из них являются применения к степеням неразрешимости по различным видам сводимости. Так, для г-степеней (где Г - сильная сводимость или -сводимость) -множеств справедливо утверждение Уа ( о«;а<-I -»36 (афв л 6 ^Фй.)) . Для сильных сводимостей это широкое обобщение теоремы С.Д.Денисова [З3 о р.п. m -степенях, а для 4 -сводимости - усиление теоремы Мартина-Лахлана о том,что существуют -несравнимые р.п.множества. Для степеней множеств по сильным сводимостям получается также утверждение

Va-M 36 6 <; •») , обобщающее другой результат С.Д.Денисова Сз1 . А вот пример со^ем нового результата: Sm-степени п-ок попарно не пересекающихся р.п.м. [бЗ плотно упорядочены.

Второй круг приложений связан с вычислением сложности конкретных индексных множеств. Показано, что для нумерованного множества *f =sr) , где 0.<¡M и Г - сильная сводимость,

справедлив аналог цитированных выше теорем Ейтса [383 и ^.Кал-либекова [73 . Отметим, что эти результаты следуют также из критерия rri-полноты М.М.Арсланова, но у нас они получаются еще проще - как следствия известных свойств предполных нумераций. Кроме того, мы доказываем новые результаты, которые ! не получаются по критерию m-полноты и для которых не было известно прямых доказательств. Например, если О-^й,,*1 tti<••• ~ Г -степени -множеств, то индексные множества семейств

л а,4гх) и {х!с0<г универсальны в классе всех раз-; ностей ¿[^-множеств, индексное множество семейства {г|(а0*гзгл;

Л а1 х) V аг«гзс} универсально в классе всех мно-

жеств вида (б^б^и^ (б^^®) и так далее. Отметим, что все результаты из последних двух абзацев доказываются довольно просто и без метода приоритета. •

Третий круг приложений связан с исследованием структуры I всех ш-степеней индексных множеств нумерации V „ Как следствие теоремы 5 получается, что если V - нумерация ^ Клини или факта из ация 2а по — у , то (Х^» — д.о.п. ранга 2. Отсюда получается много следствий, например, любые два несравнимых элемента не имеют точной верхней грани. С помощью результата из [9] выводится, что ТЬ. . =ёгд) рекурсивно изоморфна арифметике второго порядка. Если V -- нумерация Поста или ее факторизация по любой нетривиальной решеточной конгруэнции, то (Х^, % «и) есть д.о.п. ранга 4. Отметим, что работа автора £39} была первой, где удалось получить общие результаты о Впоследствии эта проблематика успешно развивалась £8,301 .

В главе 4 решается проблема Роджерса об.экстенсиональном описании семейств р.п.м. с индексным множеством из при

а 2. , Заметим, что на самом.деле задача решена для довольно широкого класса нумераций, а не только для нумерации Поста.

Пусть = {А 1 ЗГЧА") р.п.} - класс всех вполне перечислимых семейств, - эффективная иерархия Еореля, построенная из булевой алгебры, порожденной классом

, {Э п,к}к. - иерархия Ершова, построенная из

ТЕОРЕМА 7. {А|тс"ЧА)«2п,Л в 2(;,1> при. всех к»*.

В частности, {А^'Ш-Зап при п^з. Поскольку иерархии } и определены экстенсионально, это положительно решает проблему Роджерса для П^З . Наряду с этим в § 15 даны положительные решения для 2П)К (ч=Н,2.") в некоторых частных случаях, обобщающие некоторые ранние результаты [18, 13] .

В 3 16 показано, что в случаях, не вошедших в теорему V, трудно надеяться на существование простого экстенсионального описания.

ТЕОРИИ 8о При Я--1, , а таяжо при п."2, к. >.4

существует алгоритм9 строящий по любой -вычислимоР. по-

следовательности индексных множеств индексное мно:к; зтво из » не принадлежащее этой последовательности. Таким образом, в этих случаях совокупность всех индексных множеств из продуктивна в нумерации м г з то время

как в условиях теоремы 7 ста совокупность ^-вычислима. Эта! разница и объясняет отсутствие простого описания в условиях ! теоремы 8; в частности, Ехлвчения... <={А <з

строгие. I

Установлена телке определенная "оптимальность" других пэ-| . лояительных результатов из § 15. Например, в предложении 15Л установлено соотношение . {А^'ЧА) ® - о а в пред-

ложении 13.2 - соотношение {А^5Г'(А)е П^ \ *г

Л И Т Е Р А Т.У Р А |

1

о

1. Арсланов М.М. Полнота в арифметической иерархии и множества //Автореферат докт.диссертации. - Новосибирск, 1988.

2. Бухараев Н.Р. О степенях неразрешимости множества иерархии Ю.Л.Ершова //Матер. 6 Всес. конф. ш мат.логике. - < Тбилиси, 1582. - С.27,

3. Денисов С.Д. Об га -степенях рекурсивно перечислимых множеств //Алгебра и логика. - 1970. - Т.9, Р 4. - С.422-427.

4. Ершов Ю.Л. Об одной иерархии множеств I, П, Ш //Алгебра и логика. - 1968. - Т.7, № I. - С.47-74; »4. - С. 15-41; 1970. - Т.9, * I. - С.34-51.

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

6. Йшмухаметов Ш.Т. Разности рекурсивно перечислимых множеств, их степени неразрешимости и индексные множества, - Канд. диссертация. - Казань, 1986.

7. Каллибеков С. Об индексных множествах т -степеней// Сиб.матем. к. - 1971. - Т.12, № 6. - С.1292-1300.

8. Кузьмина Т.М. Структура пг-степеней индексных множеств семейства частично рекурсивных функций //Алгебра и логика. -1081. - Т.20, К! I. - С.55-68.

9. Мальцев Ан.А. Верхние полурешетки нумераций //Пре -принт ИМ СО АН СССР. - Новосибирск, 1980.

10. Перетятькин М.Г, Конечно аксиоматизируемые тотально трансцендентные теории //Груды ИМ СО АН СССР. - 1982, - Т.2. -С .88-134.

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

12. Селиванов В.Л. Несколько, замечаний о классах рекурсивно перечислим« мнокеств //Сиб. матем» к. - 1978. - Т.19,

3 I. - СЛЕЗ-160.

'13. Селиванов В.Л. О вычислимых нумерациях* - Канд. диссертация. - Казань, 1978,

14. Успенский В.А. Системы перечислимых множеств и их нумерации //ДАН СССР. - 1955. - Т. 105, !,' 6. - С. 1156-1158.

:5» Addison J.Y7. Analogies in the Borcl, Luain and Kleene hierarchies //Bull. Amer. Math- Soc. - 1955» - V- 61, IT 1< - Р» 75»

16» Dekker J.C., Myhlll J» Cn classes of recursively enumerable eats //Trans. Amer. Math. Soc. - 1958. - V» 89. -P. 29-59»

17» Epstein R.L., Нааз R.L., Kramer R. Hierarchies of sets and degrees below o? //Leo. Botes 'Math. - 1981. - II 859— P. 32-48.

■ 18. Grassin J» Index sets in Ershov hierarchy //J. Symbol. Logic. - 1974» - V. 39, II 1. - P. 97-104.

19» Hay L» Index sets of finite classes of recursively епшаегаЫе seta //J. Symbol. Logic. - 1969» - V» 34, HI. -P. 39-44»

20» Hay L. A discrete chain of degrees of index sets V/J. Symbol. Logic. - 1972» - V» 37, И 1» « Р» 139-149»

21» Яау L» Discrete CO -sequences in index-seta //Trans» Amer. Math» Soo. - 1973» - V. 183» - P. 293-311»

22. Hay L. Index sets in о! // Алгебра и логика . -1973» - Т. 12, Н б» - С. 713-729» • ■ •

23» Hay L. Rice theorems for d»r»e. sets //Canad. J. Math. - 1975» - V. 27, H 1» - P. 352-365»

24» Herrmann E, Definab" boolean pairs in the lattice . of recursively enumerable sete //Proc. 1 Easter Conf. in' Model Theory. - Diedrichshagen.1983» - P. 42-67»

' 25» Jockusch C.G., Shore R.A. Poeudojump operators II //J, Symbol. Logic - 1984» - V. 49, H 4» - P. 1205-1236.

26» Kleene 3.C. Recursive predicates and quantifiers //Trans. Amer. Math. Soc. - 1943» - V. 53» - Р» 41-73»

27. Kleene S.C. Hierarchies of number theoretic predicates //Bull. Amer. Math. Soc. - 1955» - V» 61, H 1. -P. 75»

28. Lachlan A.H. On the lattice of recursively enumerable sets //Trans. Amer. Math. Soc. - 1968. - V. 130. - P. 1-37»

29. bouTcau-A. So.-tw results in the V/adgo hierarchy of Borel ceta //I.ec. Hotao in Г-ath. - 1983. - H 1019. - P. 285530. Hohrherr J. К.'.еепэ index jets and functional tTL-¿»егеез //J. Symbol. logic. - 1933. - V. 48, N 4. - ?. 629840,

3t. Mohrherr J. A conjecture of Ertihov for a relative-hierarchy falls nuav 0 // Алгебра и логика . - 1983« - Т. 22, N2. - Ь 232-23532. tlosto.vakv A. On do finable- neto- of positive integers //Fund. Koth. - 1947- - V. 34, Я 1. - P. 31-112.

33. Rice H.G- С1асаез of recursively enumerable nets and their derision problems //Trans. Aaer. Math. Soc. - 1953« -V. 74- v 356-366«

34- Hice II. G. On completely recursively enumerable clas-nca-enii their key-nrrayo //J. Symbol. Logic. - 1956. - V. 21, , H 3» - 304-308,35 > Spector Co Recursive re 11 orderlnga //J. Syiabol. logic. - 1955. -V* 20, ¡1 2, i>. 153-160.

36« So*»re R.I. Recursively enumerable seto and degrees.-Berlinг Springer, 1937«

37« Yates С.Е.Ы. On the dstgrees of index eeto I //Srans. iimer» Math. Зое.-.1966. - V. 121. - P. 309-32S.

33* Yates C.2.K, Oa ths degrees of indej; not a Hr //Tranti. Ater. Math. Soc. - V. 135- - P< 249-2(56«

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

39. Селиванов B.J1. О структуре степеней неразрешимости индексных множеств //Алгебра и лсгика. - 1979. - 7.18, К 4.

С. 463-490. ¡

40. Селиванов В.Л. Об индексных множестэах б иерархии Кл кни -Í !о сто в ско го //Труды ИМ СО АН СССР. - К82. - Т.2. -С.135-158.

41. Селиванов В.Л. Об иерархии Ериова //Матер. 6 Всес. конф. по мат. логике. - Тбилиси, 1982. - С.165. ; :

42. Селиванов В.Л. О структуре степеней обобщенных кнде-i ксных множеств //Алгебра и логика. - 1982. - Т.21, № 4. - i . С. 472-491. ¡

43. Селиванов B.JÍ. Индексные множества з гиперарифмети- ¡ ческой иерархии //Матер. 6 Всес. конф. по мат.логике. - Тби- I лиси, 1982. - С.164.

44. Селиванов В.Л. Иерархии гиперарифметических мнэжее-л' и функций //Алгебра я логика. - 1933. - Т.22, № 6. - С.666- ; 692. !

45. Селиванов В.Л. Индексные множества в гиперарифлети- ; ческой иерархии //Сиб. матэм. ж. - 1984. - Т.25, .V 3. -

с. 164-ю х. ¡ :

46. Селиванов В,Л. Об иерархии продельных вычислений// Сиб. матом, ж. - Т.25, № 5. - C.I46-I56.- 1934 г. \

47. Селиванов В.Л. Об иерархии Ерагава //Сиб. матем. ж. -i •■'''' Т.26, № I. - С. 134-149. - IS05 г. . | '.

43. Селиванов В.Я. Об т.-степенях индексных множеств// Матер. 8 Есес. кокф. по дат. логике. - У., 1986. - C.I72.

49. Selivanov V.L. Eierarchies and jjidex seta //8 Int. i . Cong. of IMP3, Abatracto.-IS87.-iIoscow.- V.l.-P.I >7-169. j-

50. Selivanov V.L. Ind^.s eete of fa'iíor-objects of Post ¡ numboring //Loo.Hotos Comp. Sci.-I9S7.-V.278.- Р. 336-400.

51. Caíкванов В.Л. Степени.неразрешимости и индексные ¿ множесгьа классов иерархии Ероова //Натер. 2 Всес. конф. г» . ipraui. логике. - Новосибирск, IS88. - C.2I4-2I6. ^ í ■;

52. Селиванов В.Л. Тонкие иерархии и определимое;дждек'- V; i v! сные множества //Матер. 9 Всес. конф. по мат. логике. гнин-град, 1988. - С. 148. __ ......■ -

1 ' , » \ 'I ' ' ' .

■»

53. Селиванов В .Л. Индексные множества фактор-рбздктов нумерации Посте//Алгебра и логика. - 1988. - Т.27, # 3« -С.343-358.

54. Селиванов В.Л. Иерархии Ершова и Т-скачо|с//Двгебра л логика. - 1988. - Т.27, # 4. - С.464-478.

Подписано к печати 7.07« 1989 г. Ш 9 10318

Формам бумаги 60x80„ 1/16„ Объем Хс5 п.л.9 уч.-изд.л.

Заказ № 235 . Тираж 100 экз.

Ротапринт Института математики СО АН СССР 630090, Новосибирск, 90