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

Санкт-Петербургский государственный университет

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

Солон Борис Яковлевич

Нетотальные степени перечислимости

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

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

Санкт-Петербург - 2003

Работа выполнена в Ивановском государственном химико-техноло-гическом университете.

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

Доктор физико-математических наук, профессор Арсланов Марат Мирзаевич

Доктор физико-математических наук, профессор Оревков Владимир Павлович

Доктор физико-математических наук, профессор Семенов Алексей Львович

Ведущая организация: ИМ СО РАН.

Защита состоится « »_2003 г. в часов на

заседании диссертационного совета Д 212.232.29 по защите диссертаций на соискание ученой степени доктора наук в Санкт-Петербургском государственном университете по адресу: 198504, Санкт-Петербург, Старый Петергоф, Университетский пр., д.28, математико-механический факультет.

С диссертацией можно ознакомиться в Научной библиотеке Санкт-Петербургского государственного университета по адресу: 199034, Санкт-Петербург, Университетская наб., д.7/9.

Автореферат разослан « »____ 2003 г.

Ученый секретарь диссертационного совета

Нежинский В. М.

2.0&3-А

Общая характеристика работы

Актуальность темы. В вычислениях, использующих дополнительную информацию, имеет большое значение способ, с помощью которого она становится доступной для вычислителя. Без учета временных ограничений таких принципиально различных способа два: через оракула, когда новая информация появляется на запрос немедленно, и через перечисление, когда новая информация постоянно генерируется и может быть поставлена на запрос только ее некоторая часть. Первая модель вычисления, основанная на оракулах, приводит к понятию Т-сводимости (сводимости по Тьюрингу) множеств, а вторая, основанная на перечислимости, приводит к е-сводимости (сводимости по перечислимости) множеств. В то же время обе модели вычислений совпадают, если рассматриваются только тотальные функции и нет временных ограничений. Предпосылки для развития теории относительной вычислимости (через оракула) появились в связи с открытием неразрешимости в области проблем разрешимости. Это привело к бурному развитию как самой теории вычислимости, так и разнообразных видов ее применения. Первым важным примером появления относительной вычислимости через перечисление является графическая модель Скотта для ^.-исчисления, которая предлагает ситуацию, когда новая информация постоянно порождается (или перечисляется) в порядке, который неподконтролен вычислителю. В общем случае е-сводимость моделирует ситуацию, когда дополнительная информация не всегда достижима немедленно в ответ на запрос вычислителя. Т-сводимость и связанная с ней степенная структура изучаются, начиная с 1936 года, и имеют обширную и глубокую теорию, а е-сводимость, возникшая в 1955 году, привлекла активное внимание математиков лишь в последнее десятилетие. Большинство глобальных вопросов, касающихся структуры степеней перечислимости, открыты (см. обзорная статья [11]).

Дадим более подробное описание интуитивной основы понятия сводимости по перечислимости множеств. Пусть даны

множества А и В ( - подмножества м={0,1,2,...}) и некоторое вычислительное устройство, работающее по заданной программе и снабженное входным и выходным каналами (например, некоторая модификация машины Тьюринга с внешней лентой). Время от времени вычисление прерывается для получения "входного" числа, (а затем продолжается) и также время от времени выдается "выходное" число. Если затребовано входное число, то может быть подано любое натуральное число, а также вообще не подано никакого числа. Если в качестве входных чисел подаются элементы множества В и выходные числа образуют множество А, причем это происходит независимо от того, в каком порядке подаются на вход вычислительного устройства элементы множества В, то А сводимо по перечислимости к В (символически А<гВ). Допускается, что порядок, в котором появляются элементы множества А, может изменяться в зависимости от способа подачи на вход элементов множества В, причем допускается повторение в пересчете множеств А и В. В этом случае можно сказать, что "сложность перечисления А не больше сложности перечисления В". В этой терминологии степенью перечислимости (или е-степенью) множества А можно называть класс множеств, имеющих ту же самую сложность перечисления, что и А. Будем обозначать через Ов частично упорядоченное множество е-степеней.

Степень перечислимости, содержащая график некоторой тотальной функции / из а) в (о, рассматриваемый как множество номеров упорядоченных пар (и,Ди)) для всех пвсо, называется тотальной е-степенью. Обозначим через Т множество всех тотальных е-степеней. Существует изоморфное вложение £ верхней полурешетки тьюринговых степеней Вт в верхнюю полурешетку е-степеней Бв такое, что е(От)=Т. Таким образом, сводимости по перечислимости множеств соответствует степенная структура которая расширяет и обогащает

структуру

Первый серьезный результат о е-сводимости был получен Ю. Т. Медведевым [19], а именно, было доказано, что существуют нетотальные е-степени. Так как отображение е и скачки е-степеней дают только тотальные е-степени, то многие теоремы о

степенной структуре От не могут быть автоматически перенесены на Бв (несмотря на наличие изоморфного вложения е). Это обстоятельство подтвердил результат [3] об отсутствии минимальных элементов в Бе. Этот результат допускает релятивизацию относительно любой тотальной е-степени, но не относительно любой е-степени. Имеет место теорема Купера [11] о неплотности структуры Ов. Фактически доказано, что существует нетотальная е-степень некоторого П2°-множества, которая имеет строгую минимальную накрывающую ее е-степень (которая также является нетотальной). В то же время, как доказано в [10], е-степени ¿"/-множеств плотны. Дальнейшие результаты (см. [2], [7], [13], [14], [18]) связаны с развитием локальной теории степенной структуры Ов и ее различных фрагментов.

Цель работы. Исследование нетотальных е-степеней как специального класса е-степеней. Поиск нетривиальных характеристик нетотальных е-степеней в терминах тотальных е-степеней. Изучение нетотальных е-степеней в терминах свойств некоторых их элементов, в частности, - относительной иммунности множеств. Выявление зависимости тотальности/ нетотальности е-степени от структуры степеней по более сильным сводимостям, содержащейся внутри данной е-степени.

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

Научная новизна. Все основные результаты диссертации являются новыми. Впервые дана характеризация нетотальных е-степеней в терминах тотальных е-степеней. Выделены классы множеств, е-степени которых являются нетотальными. Изучены некоторые локальные свойства частично упорядоченного множества Бе\ Т .

Теоретическая и практическая ценность. Работа имеет теоретический характер. Интерпретация е-степени как степени сложности перечисления элементов подмножества м позволяет понять существенную разницу между проблемами

перечисления множества, принадлежащего тотальной ¿-степени, и множества, принадлежащего нетотальной е-степени. Результаты диссертации могут найти применение в теории вычислимости и теории сложности.

Апробация. Основные результаты диссертации докладывались на различных всесоюзных и международных конференциях в период с 1976 г. по 2001 г. Среди них IV (Кишинев, 1976 г.), V (Новосибирск, 1979 г.), VIII (Москва, 1986 г.), IX (Ленинград, 1988 г.), X (Алма-Ата, 1990 г.) Всесоюзные конференции по математической логике; XII Межреспубликанская конференция по математической логике (Казань, 1992 г.); IX Всесоюзное совещание по логике, методологии и философии науки (Харьков, 1986 г.); I, II и III Математические чтения памяти М.Я. Суслина (Саратов, 1989, 1991 и 1994 г.г., соответственно,); Международная научная конференция, посвященная 100-летию Н.Г. Чеботарева "Алгебра и анализ" (Казань, 1994 г.); Международная конференция по алгебре, посвященная памяти А.И. Мальцева (Новосибирск, 1989 г.); Международная конференция по алгебре, посвященная памяти А. И. Ширшова (Барнаул, 1991 г.); III Международная конференция по алгебре (Красноярск, 1991 г.); Казанская школа "Рекурсивная теория и сложность" (Казань, 1997 г.); Школа по теории вычислимости (Новосибирск, 1998 г.); Международная конференция, посвященная 60-летию академика Ю.Л. Ершова "Логика и приложения" (Новосибирск, 1998 г.); Международная конференция "Вычислимость и модели" (Хайдельберг, 2001 г.); Школа по вычислимости (Новосибирск, 2001 г.); семинар лаборатории математической логики ПОМИ (Санкт-Петербург, 2001 г.)

Публикации. Основные результаты диссертации опубликованы в работах автора [33]-[50].

Структура и объем работы. Диссертация состоит из введения, шести глав и списка литературы. Общий объем - 154 АМ8ТЕХ-страниц, список литературы содержит 77 наименований.

Содержание работы. Будем придерживаться терминологии и обозначений, принятых в монографии [27]. С учетом общепринятого ныне предложения Соара, пусть

и {фх}г&а - геделева нумерация всех вычислимо перечислимых и частично вычислимых функций. Через (х,у) обозначим канто-ровский номер упорядоченной пары (х,у)&а? и через Д,с со — конечное множество с каноническим индексом и. Будем обозначать через А=а> I А. Как обычно, К-{х: хе1¥х}. Формальное определение е-сводимости множества АСа> к множеству Вссо дадим в формулировке Фридберга и Роджерса [30]:

А [ х<еА о Эи[{х,и) еИ^&Ви с 5]].

Пусть а - частичная функция из ы в со, да - область определения и ра - множество значений а. Обозначим через та = {(х, а(х)): хЕда} - график а. Будем писать а ^ф вместо га ^¿тР-Отображение Ф1:2С0-^-20>, такое, что для любого множества В

ФАВ)={х: Зи[(х,и) е №г& ОисВ]} называется оператором перечисления (или е-оператором). Итак, А^еВ *>Зг[А=Ф£В)]. Пусть, как обычно, А=еВ <=> А^В &

В<Л А<еВоА<;еВ&В£ еА, А \еВ А£ еВ&В£ А ,я= с1е(А)={В: Д=(!Л} - степень перечислимости (или е-степень) множества/* и

сЦЛ) ^ сЦй) А*еВ частичное упорядочение е-степеней. Обозначим через Ое множество е-степеней, упорядоченное отношением 5, а)={х ёОв: х^ а}. Хорошо известно [8], что Бв образует верхнюю полурешетку, не решетку с наименьшим элементом 0е={№г7:гЕа>}. Будем обозначать через и операцию взятия супремума и через П частичную операцию взятия инфимума в Обозначим для любых А,ВСа) через А®В-{2х: хеА}и{2х+1: хеВ}, тогда

еЦА)и ае{В)=с1с{А®В). То, что операция П является частичной, доказано Кейсом в [8] с помощью конструкции для построения двух е-степеней, не имеющих инфимума в Бе.

Пусть £т _ отношение Тьюринговой сводимости или (Т-сво-димости) на 2Ш и (¡¡{А) - Т-степень множества, тогда для любых А,ВСсо

А £Т/? с а св ,

где сА(п) - характеристическая функция А, то есть сл(п)=1, если пЕА, и сА(п)=0, если пфА. Следовательно, отображение е:

: е(с1т{А))г=с1е(тсА) является изоморфным вложением в Бв, сохраняющим точную верхнюю границу. Достаточно очевидно, „ что £фт) =Т .

В §1 Главы 1 исследуются различные интуитивные определения и формальные аналоги понятия сводимости по перечислимости. Для формализации интуитивного определения сводимости по перечислимости множеств использованы два подхода. Первый, основанный на модификации машины Тьюринга с внешней лентой, дает общепринятое формальное определение е-сводимости, принадлежащее Фридбергу и Роджерсу [30], которое используется в данной работе. Второй подход связан с понятием вычислимой операции, введенного В.А. Успенским [29], частным случаем которой является оператор перечисления.

В скачок множества А - это множество А', которое решает проблему остановки для вычислимых относительно множества А процедур: "Для любого данного иеед пеИ^„А или нет?" В скачок А должен быть таким множеством, которое отвечает на вопрос: "Для любого данного иегц пеФ„(А) или нет?" или "Для любых данных п.хещ хеФ„(А) или нет?". Другими словами, е-скачок множества А вОе- это наименьшее (по е-сводимости) множество, к которому е-сводится характеристическая функция св каждого множества В, е-сводимого к А. Одно из определений е-скачка множества А приводится в [17]. Пусть Ае={х: хеФл(А)}, е-скачком множества А называется множество

1(А) = Ае® Iе

Обозначим через а'=с1^(А)) е-скачок е-степени а=^с1е(А), тогда для произвольной е-степени а имеем

ЛеГ/ <к> А <|е К<*а <. 4/ К)= 0/ АеП2°о А£е Кос1е( А)* О/ Ле4/=2/Г1#/«>Л5т К.

Легко убедится, что любая тотальная е-степень 0/содержит некоторое Д/-множество, но существуют также и нето-

тальные е-степени, содержащие ^/-множества. Известно, что I'2°\А2°*0. е-степени, принадлежащие классу 21/ \ Л2°, называются собственно .Г/ - е-степенями. Свойства собственно - е-степеней изучались Купером и Копестайк в статье [12].

Приемлемая формализация понятия е-скачка множеств должна удовлетворять естественному условию равенства степеней перечислимости е-скачков е-эквивалентных множеств, а также соответствовать требованию, которое было выдвинуто выше. В §1 главы 1 приводится определение е-скачка, которое с точностью до вычислимого изоморфизма совпадает с Г-скачком (но использует понятие оператора перечисления, то есть сформулировано в терминах е-сводимости), но при этом невозможно корректно перенести этот е-скачок на е-степени.

Одна из первых формализаций е-скачка принадлежит Розинасу [20]. В монографии [5] с помощью р/и-сводимости множеств, (которая является усилением е-сводимости множеств), строится скачок множеств через понятие универсального оператора. Это удается сделать и для е-сводимости, и с помощью лемм 1.1.21 и 1.1.22 доказано, что формализация понятия е-скачка, основанная на понятии универсального е-оператора, соответствует интуитивным требованиям, которые были выдвинуты выше. Заключает §1 ряд теорем, в которых изучены соотношения между различными определениями е-скачков и Г-скачка.

Так как тсаес^т{А) для любого множества А, то при изучении Т- степеней можно идентифицировать ^{А) характеристической функцией с а- Для е-степеней эта ситуация невозможна. Ясно, что любая нетотальная е-степень не содержит никаких характеристических функций. Не столь очевидно, что тотальные е-степени не содержат графики характеристических функций всех своих множеств. Другими словами, можно доказать (и это сделано в [44]), что ¿/{А)<£ (1е(тс а) для любого Лс<у.

В §2 Главы 1 изучены соотношения между Г-степенями и е-степенями, как классами множеств, относительно теоретико-множественного включения. В частности, доказано, что любая

тотальная е-степень не может быть подмножеством некоторой Г-степени. В то же время, как было показано в [32], существуют Г-степени, содержащие целиком некоторые е-степени. Из этого результата следует, что внутри каждой Г-степени ъ.0т"содержится нетотальная е-степень.

Предположение о том, что каждая нетотальная е-степень содержится (как подмножество) в некоторой Г-степени опровергается теоремой 1.2.6, в которой построена нетотальная е-степень, не содержащаяся ни в какой Г-степени.

Ю.Т, Медведев в [19], как уже было сказано выше, показал, что De\ Т *0. Он построил такое не вычислимо перечислимое множество А, что для любой тотальной функции /, если / =se А, то/- вычислимая функция. Так как De не имеет минимальных элементов, то е-степени, содержащие медведевские множества, в последствии стали называться квазиминимальными. Из определения следует, что если а - квазиминимальная е-степень, то она нетотальная и

De(s а)ПТ= {(?„}. Обозначим через Q множество квазиминимальных е-степеней. Если а - минимальная Г-степень, то е-степень Ъ =е(а) строго выше 0е, и все е-степени, лежащие между 0е и b являются квазиминимальными. Известно [16], что множество Q несчетно. В [24] доказано, что существуют минимальные Г- степени ниже От', поэтому для каждой такой минимальной Г- степени а<0т' существует счетное множество квазиминимальных е-степеней ниже е{а)<Ое'. Итак, Qfl^0* 0, более того, существует счетное множество квазиминимальных е-степеней ниже 0е'.

На полезность понятия категории множества в топологическом пространстве при сравнении множеств степеней впервые было указано Майхиллом [16]. Базой В в 2ю служит совокупность множеств вида Eq={A:DQA} для всевозможных конечных множеств D (включая 0). Множество A Q2<0 называется замкнутым, если 2ш\АеВ. Замыкание [А] множества А определяется как пересечение всех замкнутых надмножеств А. Говорят, что А - множество первой категории, если А есть конечное или счетное объединение

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

категории для любой е-степени а, а Ве(>я) - множество второй категории. Само множество Ое имеет вторую категорию. Майхилл показал, что множество квазиминимальных е-степеней О имеет вторую категорию. Так как множество минимальных Т-степеней имеет первую категорию, и, следовательно, множество квазиминимальных е-степеней, расположенных под е-степенями вида е(а), где а - минимальная Г-степень, также имеет первую категорию, а множество Q имеет вторую категорию, то существуют квазиминимальные е-степени, не лежащие под е-степенями указанного выше вида.

В [4] вводится понятие полурекурсивного множества и доказывается, что каждая ненулевая Г-степень содержит полурекурсивное множество А, такое, что А и А оба не вычислимо перечислимы и с1е(А) А). В [1] Арсланов, Купер и Калимуллин показали, что в этом случае е-степень с1е(А) квазиминимальная (и с1е( А) квазиминимальная тоже). Отсюда, в частности, следует, что для любой тотальной е-

степени а*0е, и что А? содержит нетотальные е-степени.

е-степень а называется расщепляемой, если существуют е-степени А и с, такие, что Ое<Ь<а и Ое<с<а и а^ЫЗс. Из цитируемого выше результата [1] следует, что любая ненулевая тотальная е-степень расщепляема в квазиминимальных е-степенях. В то же время достаточно очевидно, что существуют тотальные е-степени, которые не расщепляемы в тотальных е-степенях.

Ненулевые е-степени а и Ь, по определению, образуют минимальную пару, если аПЬ=Ое. Из приведенного выше результата [1] следует, что любая ненулевая тотальная е-степень ограничивает минимальную пару, образованную квазиминимальными е-степенями.

В §1 главы II вводятся некоторые обобщения понятия квазиминимальности и устанавливается связь между квазиминимальностью и генеричностью множеств и их степеней.

Впервые понятие генеричности для частичных функций было введено в терминах коэновского форсинга относительно языка арифметики 1-го порядка Кейсом в [8]. Одно из свойств генерических функций, полученных Кейсом, позволяет доказать, что любая е-степень, содержащая график генерической функции (generic function), является квазиминимальной. Джокуш ввел понятие п-генерической функции (new) и доказал, что каждая е-степень, содержащая график 1-генерической функции, квазиминимальна. В [9] приведено определение Копестайк множественной и-генеричности (set п-generic) для множеств. Она доказала, что существуют 1-гене-рические е-степени, под которыми нет минимальных пар в De.

Из приведенного выше обзора результатов о нетотальных е-степенях можно сделать ошибочный вывод, что все нетотальные е-степени являются квазиминимальными. Однако релятивизация понятия квазиминимальной е-степени позволяет построить нетотальные е-степени, которые не являются квазиминимальными. Напомним, что, как и в [25], е-степень а называется с-квазиминимальной, (где с - данная е-степень), если с<а и f& a-*fs с для любой тотальной е-степени /. Обозначим через Qc множество с-квазиминимальных е-степеней. Ясно, что Q = Qo и любая с-квазиминимальная е-степень нетотальна. В [25] показано, что для каждой е-степени с множество Qc Можно доказать, как это сделано для Q, что Qc является множеством второй категории для любой е-степени с.

Представляет определенный интерес выявить соотношения между семействами Qc для различных ceDe относительно теоретико-множественного включения с. В теореме 2.1.7 доказаны некоторые из таких соотношений, в частности, если a, beQc, то

яПаеОо <*>QanQb*j0[ В §4 доказано, что для произвольных е-степеней e,AeQc возможны обе ситуации: a U b eQc и a U b £ Qc.

Пусть с««- произвольные е-степени и ' - оператор е-скачка, определенный на Ов, тогда с'■<■ а', поэтому рассматриваемый как отображение совокупности е-степеней Бв(г:с), имеет область значений, содержащуюся в Теорема Фридберга (реляти-

визированный критерий полнота) утверждает, что эта область значений в случае Тьюринговых степеней и скачка, определенного на От, равна в точности От(а=с'Имеет место аналог теоремы Фридберга, который утверждает , что отображение ' и на совокупности 0С имеет область значений Заметим,

что этот результат получен ранее в [17] для случая с = 0е.

Наконец, в §1 главы II приводится наиболее общее понятие относительной квазиминимальности, принадлежащее Сламану и Сорби [28], - понятие так называемой, 1-квазиминимальной е-степени, где ЮЭе - произвольное множество е-степеней. Е-степень а называется I-квазиминимальной, если

(¡) с <а для любой се/,

(И) /< а <=>(Эс с] для любой тотальной е-степени

В частности, если /= {с}, то /-квазиминимальная е-степень - это с-квазиминимальная е-степень. В [28] доказано, что для каждого счетного идеала /, /-квазиминимальные е-степени существуют. С помощью этого понятия в главе V будет дана характеризация нетотальных е-степеней.

В §2 изучаются цепи и антицепи с-квазиминимальных е-степеней. В [45] автором доказано, что для любой е-степени с в существуют несчетные антицепи и несчетные возрастающие цепи.

Общий подход к пониманию структуры верхней полурешетки Ив е-степеней, а также структуры нетотальных е-степеней (то есть частично упорядоченного множества Ов\Т) состоит в изучении решеток, которые можно или нельзя вложить в Частично упорядоченное множество Р=(/>,йр) называется счетно-универсальным, если каждое, не более чем счетное частично упорядоченное множество изоморфно некоторому подпорядку Р. Известным примером счетно-универсального частично упорядоченного множества является семейство вычислимо перечислимых множеств Е, упорядоченное

отношением теоретико-множественного включения с. В монографии Соара [27] показано, что 0'т) является счетно-универсальным частично упорядоченным множеством Т-степеней. В [9] показано, что ниже любой 1-генерической е-степени а (фактически, в 1-генерические е-степени < а) изоморфно вложимо любое множество с вычислимо перечислимым частичным порядком.

В §3 главы II доказано (теорема 2.3.2), что если с<а и а -тотальная е-степень, то частично упорядоченное множество Ос(<а) с-квазиминимальных е-степеней <а является счетно-универсальным частично упорядоченным множество. Так как е-скачок с'любой е-степени с является тотальной е-степенью, то из теоремы 2.3.2 следует, что в частично упорядоченное множество 0с(<с) изоморфно вложимо любое, не более чем счетное, частично упорядоченное множество. Оказывается подобным свойством универсальности обладают также и некоторые его собственные подмножества, а именно, частично упорядоченное множество

Аь= {а: яе<2с&а\Ь&с<а<Ь/), где Ь - произвольная е-степень, для которой с<Ь и Ь'<.с'. Более точно, теорема 2.3.9 утверждает, что если с<Ь - произвольные е-степени, то в частично упорядоченное множество Аь изоморфно вложимо любое, не более чем счетное, частично упорядоченное множество.

В §4 главы II исследуется вопрос о возможности дополнения данной е-степени Ь>с до с-минимальной пары в <ЦС, то есть о построении такой е-степени «еОс, чтобы было выполнено условие аПЬ =с. Впервые подобный вопрос был поставлен в статье МакИвойя и Купера [18] и решен положительно: любая ненулевая е-степень дополняема до минимальной пары. В теореме 2.4.6 показано, что для любых е-степеней А и с, таких, что с<Ь и с'-Ь', существует о квазиминимальная е-степень а<с\ такая, что аГ\Ь=с. Как следствие, из этого результата можно вывести, что любая низкая е-степень (то есть такая е-степень а<0е' для которой а=0е) дополняема до минимальной пары в О. Доказана также теорема 2.4.13, которая утверждает, что любая

низкая е-степень с дополняема до минимальной пары в 0(< а), где а>с и а- ¿¿"-высокая е-степень.

В статье [13] Купером и Сорби доказано, что существуют не дополняемые до минимальной пары е-степени в е-степенях, содержащих ¿^"-множества. Калимуллин в [7] показал, что существуют е-степени, содержащие П[°- множества, не дополняемые до минимальной пары в Д?°. Таким образом, не любая е-степень Ь>с дополняема до с-минимальной пары в определенном, достаточно широком классе е-степеней. В теореме 2.4.16 доказано, что в классе Qc любая е-степень Ь>с дополняема до с-минимальной пары.

Говорят, что с - ветвящаяся е-степень, если существуют е-степени а, Ь> с, такие, что с = а П Ь. Розинасом было замечено, что любая е-степень является ветвящейся в Т. Теорема 2.4.2 утверждает, что любая е-степень с является ветвящейся в 0С. Более сильный вариант этого утверждения дает теорема 2.4.3: для любой е-степени с и любой тотальной е-степени е г с" существует пара с-квазиминимальных е-степеней а и А, такая, что вП6 = сия'=А'=г.

Четырехэлементную решетку Ю1={а,Ь,с,<1} с операцией ^

будем называть ромбом, если ак Ь^ с/, а<. с-£ с1, Ы с \Л с< Ь. При

этом элемент аЕДИ будем называть нижней, (¡ЕЛИ - верхней вершинами ромба. В §5 главы II исследуется вопрос о вложимости ромба в (2С с сохранением с как нижней вершины. В теореме 2.5.2 доказано, что такое вложение возможно. В то же время, для любой е-степени с существуют с-квазиминимальные е-степени а и Ь, такие, что а\Л>0Цс. Достаточно очевидно, что в этом случае супремум е-степеней а и Ь не существует в

В статье [14] вводится понятие дополняемости е-степени а наверх (до е-степени с>а): е-степень а называется дополняемой наверх, если существует Ь<с, такая, что аиЬ=с. Е-степень Ь называется с-дополнением а, если аиЬ=с' и аГ\Ь=с. Если с=0е,то говорят просто о дополнении. Ясно, что с' является тривиальным с-дополнением для любой е-степени с. В то же время, в [14] показано, что существует е-степень а>0е , такая, что аиЬ<0 'е для

всех b<0'e. Поэтому существуют е-степени, не имеющие нетривиальных дополнений. Ясно, что если е-степени а и b -взаимные с-дополения друуг друга, то существует вложение ромба в De с сохранением с как нижней и с'как верхней вершин ромба. В теореме 2.5.10 доказано, что любая с-квазими-нимальная е-степень а дополняема наверх в Qc до е-степени из Qc, а если еще а'-с', то дополняема наверх в Qc(<cДругими словами, в Qc вложим ромб с сохранением с как нижней вершины и а как одной из боковых вершин.

е-степень Ъ называется разложимой, если существуют е-степени а0<Ь и aj<b, такие, что a0Ua/=A. Теоремы о разложении Г-степеней доказывались Саксом, Робинсоном, Лахланом. В статье [1] показано, что 0/ разложима в Л2°, а в [2], что существуют неразложимые е-степени, содержащие Л2°-множества. Из теоремы 2.5.14 следует, что е-скачок с'любой е-степени с разложим в Qc. На самом деле доказан более общий результат: для любой тотальной е-степени fee'существуют с-квазиминимальные е-степени а0 и а/, такие, что aoU«/=A, то есть любая тотальная е-степень ¿ас'разложима в Qc.

В рамках Международных школ "Рекурсивная теория и сложность", Казань, 1997 г., "Теория вычислимости", Новосибирск, 2000 г. и "Вычислимость и модели", Хайдельберг, 2001 г. обсуждались проблемы характеризации тех или иных классов е-степеней в терминах свойств их элементов. В этой связи представляет определенный интерес проблема характеризации нетотальных е-степеней. В качестве примера положительного решения подобной проблемы можно привести результат из статьи Кейса [8]: тотальные и только тотальные е-степени содержат ретрассируемые множества.

В статьях [40] и [46] вводятся специальные классы иммунных

множеств, е-степени которых нетотальны. Пусть a0,ai.....ап,... -

элементы бесконечного множества А, расположенные в порядке возрастания, или прямой пересчет А. Множество А называется е- гипериммунным, если не существует тотальной функции g:<y-»ft>, такой, что g^eA и g(n) для всех neat, то есть никакая тотальная функция, е-сводящаяся к А, не мажорирует прямой

пересчет А. Бесконечное множество А называется е-иммунным, если для любой тотальной функции/&еА р/с А—> конечное.

В главе III изучаются е-степени, содержащие е-иммунные множества. Как было показано Розинасом в [21], если А и В -иммунные или гипериммунные множества, то е-степень с]е(А®В) обязана содержать иммунное или гипериммунное множество, соответственно. Для е-иммунных множеств могут быть различные ситуации, то есть существуют е-иммунные множества А и В, такие, что А \ еВ и с1е{А®В) содержит е-иммунное множество и, напротив, существуют е-иммунные множества А и В, для которых с!е{А®В) не содержит е-иммунных множеств.

В предложении 3.4 доказано, что если А - е-иммунное множество, В — Л-квазиминимальное множество, то е-степень <1е(В) содержит е-иммунное множество, то есть имеется частичное наследование свойства е-степени содержать е-иммунное множество вверх в Ое. Однако, как было показано в теореме 3.5, существуют интервалы в Ов , не содержащие е-иммунных е-степеней, то есть полного наследования свойства е-степени содержать е-иммунные множества нет. Из теоремы 3.5, в частности, следует, что выше е-степени произвольного е-иммунного множества существуют нетотальные е-степени, не содержащие е-иммунных и, следовательно, е-гипериммунных множеств. Это дает ответ на вопрос из статьи [40]. Независимо, Сламан и Сорби в [28] дали пример нетотальной е-степени, не содержащей е-гипериммунных множеств. В то же время показано (теорема 3.6 и следствия 3.7 и 3.8), что для любого ретрас-сируемого множества В существует несчетное семейство е-иммунных множеств строго выше В в отношении

Обозначим через I класс иммунных, Е1 - класс е-иммунных, ЕН1 - класс е-гипериммунных е-степеней. Доказано, что ЕН1сЕ1с1 и 1ПОсЕ1. Кроме того, все е-степени из класса Е1 являются нетотальными, но, в то же время, существуют иммунные нетотальные е-степени, не принадлежащие Е1. С помощью теоремы 3.9 можно построить е-иммунные множества

А и В так, что е-степень с1е(А®Б) является тотальной. Ясно, что в этом случае обязательно А \ еВ.

Одним из традиционных вопросов в теории сводимостей является вопрос о внутреннем строении степеней. Рассмотрим одно усиление е-сводимости, введенное Д. Г. Скордевым [26]: множество А рс-сводимо к В посредством частично вычислимой функции ф, если

\/лг[хе/1 <*> хедф & О^ с В]. Будем писать А^рсВ, если существует частично вычислимая функция ф, для которой А рс-сводится к В посредством ф. Как обычно, (¡рс(А)= {В:В^рсА & А^рсВ} - рс-степенъ множества А. Очевидно, что произвольная е-степень состоит из некоторой совокупности рс-степеней. Если е-степень с/е(А) содержит более, чем одну /?с-степень, то говорят, что с1е(А) распадается на рс-степени. Ясно, что 0е не распадается на ^остепени, то есть состоит из единственной /?с-степени. С.Д.Захаров [6] построил ненулевые е-степени, состоящие из единственной /?с-степени. .Как показано автором в [42], любая ненулевая тотальная е-степень содержит, по крайней мере, две различные рс-степени (см. также теорему 4.7 в главе IV). Поэтому, если е-степень состоит из единственной />с-степени, то она нетотальная. Как показано в теореме 3.17, это достаточное условие нетотальности е-степени не является необходимым. Оказывается, любая неквазиминимальная е-сгепень, содержащая е-иммунное множество, распадается на /»остепени.

Вопрос о том, каким образом дополнительные ограничения на е-сводимость (и, вообще, на любую сводимость) "дробят" е-степени, всегда вызывает большой интерес в теории вычислимости. В частности, /?с-сводимость множеств, как наиболее естественное усиление е-сводимости, является важным объектом для исследования. Обозначим через Бврс(Л) частично упорядоченное множество /?с-степеней внутри е-степени множества А. В [33] автором доказано, что е-степени гипериммунных ретрассируемых множеств содержат счетные возрастающие цепи, а также счетные антицепи />с-степеней. В последующей работе [35] доказан более общий результат о том, что в частично упорядоченное множество рс-степеней внутри е-

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

Как видно из доказательства теоремы 4.1 столь "богатую" структуру множество Вврс(А) имеет благодаря гипериммунности множества А. Если отказаться от этого условия, но сохранить тотальность с1е(А), то можно доказать теорему 4.7, из которой следует, что Барс(Л) содержит счетную антицепь рс-степеней.

Как уже отмечалось выше, е-степени, состоящие из единственной /«.'-степени, являются нетотальными. Чтобы доказать, что существуют нетотальные е-степени, содержащие более одной /?с-степени, в главе IV вводится релятивизация понятия гипериммунности множеств. Пусть ЕСсо - произвольное множество. Как и в [40] назовем бесконечное множество А Е-ггтериммунным, если условие

& ^п[а„<. 5<и)]

не выполняется ни для какой тотальной функции g, где {а„}„еа> -прямой пересчет множества А. Если Е - вычислимо перечислимое множество, то £-гипериммунное множество А является гипериммунным. В нашей терминологии, е-гипериммунное множество А это - Л-гипериммунное множество. Существование 2?-гипериммунных множеств для любого Е^ш доказано с помощью теоремы 4.9, а е-гипериммунных множеств - теоремы 4.10. Из теоремы 4.12 следует, что выше любого множества В существуют несчетные возрастающие цепи е-гипериммунных множеств.

Очевидно, что для е-гипериммунных множеств верна теорема 3.5 (с заменой е-иммунности на е-гипериммунность). В то же время, как показано в теореме 4.14, под е-скачком любого множества Е существуют е-гипериммунные множества. Более того, если Е - ретрассируемое множество, то интервал (с1е(Е),с1е(^1(Е))с Бе содержит е- гипериммунные е-степени (следствие 4.15).

Выше было отмечено, что класс ЕН1 е-гипериммунных е-степеней является подклассом класса Н1 гипериммунных е-степеней, то есть ЕН1СН1. Несовпадение этих классов следует, например, из того, что существуют гипериммунные множества, которые принадлежат тотальным е-степеням, в то время, как е-гипериммунные е-степени обязательно нетотальные (теорема 4.17). Кроме того, класс Н1 замкнут относительно е-степеней подмножеств бесконечных гипериммунных множеств, а класс ЕН1 нет (теорема 4.17). В теореме 4.19 доказано, что существуют нетотальные гипериммунные е-степени, не содержащие е-гипериммунных множеств.

В теореме 3.16 было показано, что неквазиминимальные е-степени, содержащие е-иммунные множества, распадаются на рс- степени. Пусть 77- счетное, частично упорядоченное множество, для каждого элемента которого существует не более конечного числа предшественников. Используя результат Сакса [24], в теореме 4.23 доказано, что существует е-гипериммунное множество А, для которого 77 изоморфно вложимо в Ъарс(А), а следствие 4.24 показывает, что для любого е-гипериммунного множества В, такого, что А^еВ, в Иврс(В) изоморфно вложимо частично упорядоченное множество П.

В предыдущих главах рассматривались классы нетотальных е-степеней 0С (где с - произвольная е-степень), Е1 и ЕН1. В главе V показано, что эти классы не исчерпывают все нетотальные е-степени, и предложена некоторая глобальная характеризация нетотальных е-степеней с помощью обобщения понятия относительной квазиминимальности, введенной Сламаном и Сорби в [28]. В теореме 5.2 строится е-гипериммунное множество А, е-степень которого а=с1е{А), следовательно, нетотальна и не является /-квазиминимальной для любой тотальной е-степени /<а. Это означает, что класс с-квазиминимальных е-степеней, где с - произвольная е-степень, не исчерпывает множество всех нетотальных е-степеней. Пусть в - семейство тотальных е-степеней, образующих строго возрастающую последовательность, тогда, как показано в предложении 5.3, существует в - квазиминимальная е-степень

а, которая не является /"-квазиминимальной для любой тотальной е-степени f<a. Теорема 5.4 дает следующую характеризацию нетотальных е-степеней: любая нетотальная е-степень а является /чсвазиминимапьной для некоторой тотальной е-степени /<а или G-квазиминимальной для некоторого семейства тотальных е-степеней G= образующего возрастающую последовательность go<gi<-..<gs<-<a.

В главе V строится еще один класс множеств, е-степени которых нетотальны и не содержат е-иммунных множеств. В [33] автор вводит понятие строго нетотального множества. Множество ЛСю называется строго нетотальным, если А - не вычислимо перечислимо и

\/я[Ф„(Л) бесконечно—»(3 g-вычислимая функциями)

\Pg(u)QA & {*: 3 i[(x,g(/))efFn]} бесконечно]]. Пусть SNT - класс е-степеней, содержащих строго нетотальные множества. В теореме 5.12 доказано, что класс SNT имеет несчетную мощность, SNT с Q и SNT П I = 0. Таким образом, е-степени строго нетотальных множеств не принадлежат классу El е-степеней е-иммунных множеств..

Глава VI посвящена доказательству недистрибутивности операций U и частичной операции П в отрезке [c,c']cDe. Напомним, что бинарная операция U дистрибутивна в частично упорядоченном множестве (D, s) , если для любых ai,a,b,cED

a = bUc&a,s a-*{3b,s b)(3c,s c)[a,= b, U cy] Дистрибутивность операции П определяется двойственным образом (с учетом частичности операции П ). Доказана теорема

б.6, которая утверждает, что в любой отрезок [с,с ]с De может быть изоморфно вложена недистрибутивная пятиэлементная решетка с наименьшим элементом с и с-квазиминимальными остальными элементами. Ранее, в статье [18] было доказано, что любая решетка, вложенная в низкие вычислимо перечислимые Г-степени, может быть вложена в частично упорядоченное семейство е-степеней 77;°-множеств. Отсюда следует, что результат Лахлана [15] о вложении недистрибутивной пяти-элементной решетки в низкие вычислимо перечислимые Т-

степени дает вложение такой решетки в е-степени П/°-множеств.

В теореме 6.1 доказано, что операции U и П "локально" дистрибутивны, то есть в De вложимы конечные полурешетки, удовлетворяющие условию

в=АПс & a/ba-^a/=(a,UA)n(e/Uc) и двойственному ему

a=bUc & a, sa—«/=(«/ HA)U (а,Г)с). Из теоремы 6.1 получен ряд интересных следствий. В частности, следствие 6.2 утверждает, что для любой е-степени а и любых е-степеней />га и baa существует а-квазиминимальная е-степень с, такая, что любая е-степень qG[a,p]<z De представима в виде инфимума е-степеней bUq и cUq.

Литература

1. Арсланов, Купер, Калимуллин (М. Arslanov, S. Barry Cooper, I.S. Kalimullin) Splitting properties of total e-degreesll University of Leeds Pure Mathematics. - Preprint Series. - 2000. - No. 7 (revised 17/7/00).

2. Ахмад и Лахлан (S. Ahmad and A.H. Lahlan). Some special pairs of e-degrees properties of - enumeration degreesII Math. Logic Quarterly. - 1998. - V. 44. - P. 431 - 444.

3. Гаттеридж (L. Gutteridge). Some results on e-reducibility II Diss., Simon Fraser University, Burnaby. - 1971.

4. Джокуш (C.G. Jockusch, Jr.). Semirecursive sets and positive reducibilityll Trans. Amer. Math. Soc.- 1968.-V.131.-P.420-436.

5.Ершов Ю.Л. Теория нумераций!! -1977. "Наука". Москва.

6. Захаров С.Д. О внутреннем строении е-степенейИ Тезисы IX Всесоюзн.конф.по матем.логике . - Ленинград. - 1988. - С. 61.

7. Калимуллин И.Ш. Относительные дополнения в Л2 -степенях по перечислимости!I Алгебра и логика. -2000.-№5. -С.547 - 566.

8. Кейс (J. Case). Enumeration reducibility and partial degrees!! Annals Math Logic. - 1971. - V.2. - № 4. - P.419 - 439.

9. Копестайк (C.S. Copestake). 1-genericity in the e-degreesll J. Symbolic Logic. - 1988. - V. 53. - P. 878 - 887.

10. Купер (S.B. Cooper). Partial degrees and the density problem. Part 2. The enumeration degrees of the sets are dense.ll J. Symbolic Logic. - 1984. -v. 49. - № 2. -P. 503—513.

11. Купер ( S. B. Cooper). Enumeration reducibility, nondeter-ministic computations and relative computability of partial functionsII Recursion Theory Week, Oberwolfach. -1989, (eds. K. Ambos-Spies, G. Muller, and G. S. Sacks), Lecture Notes in Math. 1432, Springer-Verlag, Heidelberg. -1990. - p. 57-110.

12. Купер и Копестайк (S.B. Cooper and C.S. Copestake). Properly I2 e-degreesll Z.math. Logik Grundlag. Math. - 1988. - V. 34. P. 491-522.

13. Купер, Сорби (S.B. Cooper and A. Sorbi). Noncappable e-degrees below 0'// J. Symbolic Logic. - 1996.- V.61.- №4.

14. Купер, Сорби, Йи (S.B. Cooper, A. Sorbi, X. Yi). Cupping and noncupping in the e-degrees of S2 sets!/ Annals of Pure and Applied Logic. - 1997. - V.82. - P. 317-342.

15. Лахлан (A.H. Lachlan). Embedding nondistributive lattices in the r.e. degrees// Lecture Notes in Mathematics. - 1972. - V.255. -Springer - Verlag, Berlin.

16. Майхилл (J. Myhill). Note on degrees of partial functions!I Proc. of the Amer. Math. Society. - 1961. - V. 12. - P. 519 - 521.

17. МакИвой (К. McEvoy). Jumps of quasi-minimal enumeration degreesll J. Symbolic Logic. - 1985. - V.50. - P. 839 - 848.

18. МакИвой, Купер (К. McEvoy and S.B. Cooper). On minimal pairs of enumeration degrees!! J. Symbolic Logic. - 1985. -V. 50. -P.983 -1001.

19. Медведев Ю.Т. Степени трудности массовых проблем // ДАН СССР,- 1955.- 104. -№ 4. -С. 501-504.

20. Розинас М.Г. Операция скачка для некоторых видов сво-димостей/1 ВИНИТИ Деп. 3185-76.

21. Розинас М.Г. Частичные степени иммунных и гипериммунных множеств!! Сибирский математический журнал. -1978.- Т. 19. - №5. - С. 866-870.

22. Розинас М.Г., Солон Б.Я. Слабо полурекурсивные множества// Известия вузов. Математика. - 1979. - Т.211. -№12. — С.48 -50.

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

24. Сакс (G.E. Sacks) Degrees of unsolvability// Annals of mathematics studies. Princeton, NJ. - 1963. - V.55.

25. Cacco (L.P. Sasso). A survey of partial degrees!/ J. Symbolic Logic. - 1975. - V. 40. - № 1. - P. 130 - 140.

26. Скордев Д.Г. О частичной конъюктивной сводимости// Тезисы II Всесоюзн. конф. по матем. логике .- Москва. - 1972.-С. 43-44.

27. Coap (Robert I. Soar). Вычислимо перечислимые множества и степени// - 2000. "Казанское математическое общество". -Казань.

28. Сламан и Сорби (Т.А. Slaman and A. Sorbi). Quasi-minimal enumeration degrees and minimal Turing degrees!/ Preprint —1996.

29. Успенский B.A. О вычислимых операциях!! Доклады АН СССР, - 1955.-Т. 103.-С. 773-776.

30. Фридберг и Роджерс (R. Fridberg and Н. Rogers). Reducib-ility and completness for sets of integers!! Z. math. Logic Grundl. Math. -1959. - № 5. - P. 117 - 125.

31. Ходжаянц М.Ю. О структуре е- степеней!! Известия АН АрССР "Математика". - 1980. - Т. 15. - № 3. - С. 165 - 175.

32. Ходжаянц М. Ю. е-степени, Т- степени и аксиоматические теории/У ДАН АрССР "Математика". - 1981.- T.LXXI11. -№2. - С.73-77.

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

33. Солон Б.Я. е-степени гипериммунных ретрассируемых множеств//Сибирский матем. журнал. - 1978. - Т. 19. - №1. - С. 172 -179.

34. Солон Б.Я. е-степени продуктивных множеств.//V Всесоюзн. конф.по матем. логике. Тезисы докладов. - Новосибирск, -1979.-С. 145.

35. Солон Б.Я. рс-степени внутри е-степени гипериммунного ретрассируемого множества!! Алгебраические системы.. — Межвузовский сборник научных трудов. - Иваново. - 1981. - С. 203-217.

36. Солон Б.Я. е-гипергшмуные множества!! Тезисы докладов ÍX Всесоюзн. совещ. по логике, методологии и философии науки. - Харьков. - 1986. - С. 97.

37. Солон Б.Я. Продуктивные е-степени распадаются на рс-степени // VII Всесоюзн. конф. по матем. логике. -Тезисы. -Москва. 1986.-С.142.

38. Солон Б.Я. Степени жестких множеств!! Известия вузов. Математика. - 1989. - Т.ЗЗ 1 -№12. - С.44-47.

39. Солон Б.Я. The weak pm-reducibilityll XI Межреспубликанская конф. по математической логике. - Тезисы. - Казань.-1992.-С. 131.

40. Солон Б.Я. е-гипериммунные множества!! Сибирский математический журнал.- 1992.-Т.ЗЗ. -№2.-С.211 -214.

41. Solon В. Quasi-minimal enumeration degrees!I III Междунар. конф. по алгебре. Тезисы докладов. - Красноярск. - 1993. - С. 434-444.

42. Солон Б.Я. Теорема о разложении тотальных е- степеней/! Тезисы докладов Юбилейной научной конференции Ивановского гос. университета. - Иваново. - 1994. - С.185.

43. Solon В. About enumerations of sets!! Алгебра и анализ. Часть 1: Тезисы докладов междунар. конф., посвященной 100-летию со дня рождения Н.Г. Чеботарева. - Казань.- 1994. - С. 146-147.

44. Солон Б.Я. Соотношения между е- степенями и Т-степенямиИ Известия вузов "Математика". - 1995. - Т.394. -№3. -С.51-61.

45. Solon В. e-reducibility and the problem of the nontotal property of e-degreesll Recursion Theory and Complexity, Proceeding of the Kazan'97 Workshop (ed. Marat M.Arslanov and StefTan Lempp), Walter de Gruyter, Berlin. New York. - 1999. - P. 173-191.

46. Солон Б.Я. е-иммунные множества!! Сибирский матем. журнал. - 2000. - Т. 41. - №3. - С. 676 - 691.

47. Солон Б.Я. The nondistributivity of Z2 e-degrees, Международная конф. «Логика и приложения»,- Тезисы докладов. -2000. - Новосибирск. - С.141-142.

48. Солон Б.Я. Characterising the non-total e-degrees// Com-putability and Models. - 2001. - Forschungsberichte Math. Logik und Theoretisch informatik . - V.50. - Universität Heidelberg.

49. Solon В. Local properties of non-total enumeration degrees!/ Computability and Models (ed. S.Barry Cooper and Sergei S. Goncharov), Kluwer Academic/Plenum Publishers, New York.-2003.-P.388-412.

50. Солон Б.Я. С-квазиминималъные степени перечислимости// Сибирский матем. журнал. - 2003. - Т.44. -№1.- С. 211 — 223.

Отпечатано в учреждении «Издательство ИГХТУ «Политех»

г. Иваново, пр. Ф. Энгельса, д. 7 Усл.печ.л. /65 Тираж /оо экз. Заказ ¡29

1?4О2 P 134 0 2

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

Пусть cj = {0,1,.} — множество натуральных чисел. Одноместная функция / и> —► и называется алгоритмически вычислимой или вычислимой с помощью эффективной процедуры (в интуитивном смысле), если существует алгоритм, позволяющий по данному входу « получить выход /(г). Опуская слово "алгоритмически", мы получаем понятие вычислимой функции (computable function), если f — тотальная функция, и частично вычислимой (partial computable), если / — частичная функция.

Уточнения или, как принято говорить, формализации понятий алгоритма и вычислимой функции были сделаны в 30-е годы прошлого века К лини [23], Черчем [77], Тьюрингом [70], Геделем и другими. Как один из результатов - создание теории вычислимости и соответствующей терминологии, в которой термин "рекурсивный", введенный К лини [22] для обозначения функций, вычислимых по К лини (recursive function), стал использоваться и для назваг ния функций, вычислимых по Тьюрингу, и в случае других формализации. Это привело к появлению "Теории рекурсивных функций" (Recursive Function Theory). Различие в использовании терминов "вычислимый" и "рекурсивный" было стерто в монографии Роджерса [49] "Теория рекурсивных функций и эффективная вычислимость". Как было сказано в предисловии "От редактора перевода" В.А. Успенским, в этой книге "систематически излагается общая теория рекурсивных функций, то есть функций, вычислимых посредством алгоритмов". Термин "рекреивный" стал использоваться также и в смысле "разрешимый" (decidable), в результате множества, характеристическая функция которых рекурсивна (разрешимые множества), были названы рекурсивными, а множества, которые являются областями определения подходящих частично-рекурсивных функций, — рекурсивно перечислимыми (recursively enumerable).

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

В диссертации нумерация определений, предложений, лемм я теорем сплошная внутри каждого параграфа или главы, (если она не разбита на параграфы). В введении номер утверждения состоит из одного числа. В главах I и II номер состоит из трех чисел: "номер главы.номер параграфа.порядковый номер утверждения". В главах III -VI номер утверждения состоит из двух чисел: "номер параграфа, порядковый номер утверждения".

Приведем обозначения и терминологию, которые будут использованы в тексте диссертации. Многие из них такие же, как и в монографии [49]. С учетом общепринятого ныне предложения Соара, пусть {Wn}n£w и {фп)п£ы - геле-лева нумерация всех вычислимо перечислимых (в.п.) множеств и частично вычислимых (ч.в.) функций, {W*},ew — конечная вычислимая аппроксимация вычислимо перечислимого множества Wn. Как обычно, Du — конечное множество с каноническим индексом м € со, таким, что если Du = {«i,., хп} и a?i < • • • < хп, то u = 2*1 + • • • + 2и Dq = 0, (k,l) - канторовский номер упорядоченной пары (fc, I). Если t — канторовский номер пары (fc, /), то (i)i = к и {<>2 = I. Обозначим для множества В через (В)i = {х : 3u((z,«) 6 В)}, через (х, D) = (г, и), где D — Du. Через \А\ будем обозначать мощность множества AQ а/, то есть\А\ = Ко, если А — бесконечное множество, |Л| — число элементов конечного множества А ф 0 и |0| = 0. Иногда будем писать |Л| = оо, если А - бесконечное и |.А| < оо, если А - конечное множество. Пусть, как обычно, К = {х : х € W0} и R — ы\К, Ко = {(х,n) : х € Wft}. Хорошо известно, что К вычислимо изоморфно /Го (и, следовательно, R г К о).

Для функции «:«-»« через jar будем обозначать область определения, ра — область значений и тог = {(г, а(г)) : х € - график а. Тот факт, что х 6 8а будем записывать как ог(ае) а х 8а, как а{х) f. Буквы f,g будем использовать только для обозначения тотальных функций, т.е. 8f = 8g = ш.

Обозначим для множества А через •—. ■ если х € А если х ^ А — характеристическую и если х € А если х £ А — частичную характеристическую функции множества А. Множество А называется однозначным, если А = та для некоторой функции а.

В вычислениях, использующих дополнительную информацию, имеет большое значение способ, с помощью которого она становится доступной для вычислителя. Без учета временных ограничений таких принципиально различных способа два: через оракула, когда новая информация появляется на запрос немедленно, и через перечисление, когда новая информация постоянно генерируется и может быть поставлена на запрос только ее некоторая часть. Первая модель вычисления, основанная на оракулах, привсздит к понятию Т-сводимости (сводимости по Тьюрингу) множеств, а вторая, основанная на перечислимости, приводит к е-сводимости (сводимости по перечислимости) множеств. Т-сводимость и связанная с ней степенная структура изучаются, начиная с 1936

-<*>={о! года, и имеют обширную и глубокую теорию, а е-сводимость, возникшая в 1955 году, привлекла активное внимание математиков лишь в последние десятилетие.

Напомним определение Фридберга и Роджерса из [74], которое мы принимаем за основное. С интуитивной точки зрения, множество А сводится по перечислимости или е-сводится к множеству В (символически, А <в В), если существует равномерный алгоритм для получения некоторого перечисления элементов А из любого перечисления элементов В. Формально,

О пределение 1.

А<вВ <=> 3 nVx[x 6Л 3«[(ж, и) € Wn Л А, С В]}.

В $1 главы 1 дадим подробное обоснование данного формального определения. Обозначим через Ф»(В) = {ж : Э«((х, и) € Wn Л Du С В)}, тогда А <е В ■<=>■ Зп(А =5 ФП(В)). Отображение ФЛ : 2м —► 2м называется оператором перечисления или е-оператором с индексом п (как и Wn> определяющее Фп). Хорошо известно, что е-операторы монотонны и непрерывны, т.е. для любого п 6 и> и любых А, В С и>

АС В Фп(А) С Фп(В) и

Уф 6 Фп(Л) (3D - кonc4uoe)[D С А Л х € Ф»(£)]].

Пусть, как обычно, А &ш В <=> А <е В Л В <е A, de(A) - {В: В =еА}-е-степенъ множества А (для обозначения е-степеней будем также использовать малые жирные латинские буквы: например, а = de(A)) и de(A) < de(B) <==> А <е В - частичное упорядочение е-степеней. Если е-степени а и b несравнимы относительно <, то обозначим это через а| Ь, а< Ъ, если а< Ъ и Ъ^С а. Будем писать для функций а, /? а <в А или а <е /?, если та <е А или та <в Обозначим через Vt множество е-степеней, упорядоченное отношением <, 2>е(< а) = {х 6 Ре : х < a}, [a,b]e = {х € Ve : а < х < b}, (a,b)e = {х € 2>в : а < х < Ь}, Хорошо известно (см., например, [21]), что 2>е образует верхнюю полурешетку, не решетку с наименьшим элементом 0е = {Wn i п € w}. е-степени, содержащие графики тотальных функций, называются тотальными. Обозначим через Т частично упорядоченное множество тотальных е-степеней. Обозначения Т(< а) и Т(< а) используются в обычном смысле.

Термин нетотальная е-степень применим, таким образом, к степеням перечислимости, которые не содержат графиков ни одной тотальной функции. Как было показано Кейсом в [21], по любому перечислению любого множества А, принадлежащего тотальной е-степени и только тотальной е-степени, можно эффективно получить некоторое фиксированнное перечисление элементов этого множества А. Отождествим произвольное перечисление множества А с некоторой тотальной функцией р: w —► А, область значений котрой рр = А. Пусть Р(Л) - семейство всех перечислений множества А, частично упорядоченное отношением <е. Результат Кейса, процитированный выше, означает, что de(A) — тотальная Р (.А) «имеет наименьший элемент.

Для любого множества из нетотальной е-стелени, следовательно, имеет место следующее утверждение

Предложение 2. Для любого множества. А de(A) — нетотальная <=> Р(Л) не имеет наименьшего элемента.

Бели a—de(A) и b=d6(B), то наименьшая верхняя грань (или супремум) е-степеней а и b равна aUb = de(A®B), где А®В = {2х : х € А}U{2as+1: х Е В}. Обозначим через а Г) b наибольшую нижнюю грань е-степеней (или инфимум) а и Ь. В [21] впервые показано, что существуют е-степени а и Ъ, для которых нет наибольшей нижней грани а П b в Т>е. Таким образом, бинарная операция П является частичной. В то же время, как было показано Розинасом в [52], любая е-степень с является наибольшей нижней гранью некоторых тотальных е-степеней а, Ъ > с. В общем случае можно говорить о возможности представления произвольной е-степени как наибольшей нижней грани двух е-степеней, принадлежащих определенному классу S С Ve. В этом случае е-степень с наг зывается ветвящейся в S. Таким образом, М.Г.Розинас в [52] показал, что любая е-степень является ветвящейся в Т. '

Обозначим через Vt верхнюю полурешетку Т-степеней. Так как для всех А, В Си>

А <т В <=> сл <« св> то отображение е : Vt —*■ Ve : c(dx(-A)) — de(rCA) является изоморфным вложением Vt в Ре, сохраняющим нибольшую верхнюю границу.

Предложение 3. Если в— dr{A ф В) является наименьшей верхней границей Т-степеней а= dr(A) и b= dr{B), то е(в) является наименьшей верхней границей е-степеней с(а) = Лс(тса) ж е(Ь) = 4е(тсв)- В частности, е(От) — 0в.

Доказательство. Пусть С — тел Ф тсв, докажем, что С =е телфв• Имеем тсаъв - {<2я?, 1) : х 6 A} U {{2х +1,1) : х 6 В} U «2*,0) : х £ A} U {<2* +1,0) : х£В}нС= {2{х, 1) : х С 4}U{2(х, 0) : х £ A}U{2<*, 1)+1: х € В}и{2<®, 0) + 1 : х £ В}. Ясно, что С <е тсд^в и тс^фв <е С. Так как c(s) = de(rcA$B) и С € e(s), то c(s) является наименьшей верхней границей е(а) и с(Ь).

Так как е-степень а тотальна тогда и только тогда, когда существует В £ а, такое что В =в сд, то Т = {Ле(тсв) : В С со). Ясно, что Т - педполурешетка

Vet так как dt(rcA) U de(rcjj) = Ле(тсА$в)' Таким образом, е(2?т) = Т и Т изоморфна "От

Заметим, что вложение с может не сохранять точную нижнюю границу Т-степеней. В самом деле, в [52] показано,

VI € 2>е)(Эа, b € Г)(а|ъ л i = а п ъ).

Как было замечено выше, в этом случае существуют множества А € а и В G Ъ, такие, что тс а € а и тсв € Ъ, тогда c(rfr(-4)) = а и с(йт{В)) = Ъ. Предположим, что i является нетотальной е-степеныо, тогда i ф с(х) для любой Т-степени х. Поэтому, даже если существует наибольшая нижняя грань dx(A) П dx(B) = rfj(CT), ее образ при вложении e(dr(C)) = djjcc) не может быть равен i.

Так как тса € dr{A) для любого ЛСцто при изучении Т-степеней можно идентифицировать dr(A) характеристической функцией с а- Для е-степеней эта ситуация невозможна. Ясно, что любая нетотальная е-степень не содержит никаких характеристических функций. Не столь очевидно, что тотальные е-степени не содержат графики характеристических функций всех множеств, принадлежащих им. Другими словами, можно -доказать (и это сделано в [66]), что dr(A) % dtijCA) для любого А С и/. В то же время, как легко заметить, de(A) содержит т\а Для всех А С и.

В §2 Главы 1 изучены соотношения между Т-степеиями и е-степенями, как классами множеств, относительно теоретико-множественного включения. В частности, доказано, что никакая тотальная е-степень не может быть подмножеством некоторой Т-степени. В то же время, как было показано в [75], существуют Т-степени, содержащие целиком некоторые е-степени. Из этого результата следует, что внутри каждой Т-степени >0у содержится нетотальная е-степень.

Предположение о том, что каждая нетотальная е-степень содержится (как подмножество) в некоторой Т-степени опровергается теоремой 1.2.6, в которой построена нетотальная е-степень, не содержащаяся ни в какой Т-степени.

Включение Т-степеней в е-степени возможно только в тривиальном случае: От С0е, где О? состоит из всех вычислимых множеств, а 0е - из всех в.п. множеств.

В Vt скачок множества А — это множество А', которое решает проблему остановки для вычислимых относительно множества А процедур: "Для любого данного п 6 ы, n g W* или нет?" В Р« скачок А должен быть таким множеством, которое отвечает на вопрос: "Для любого данного я 6 u, п £ Фп(А) или нет?" или "Для любых данных п,х € w, х 6 Фп(-А) или нет?". Другими словами, е-скачок множества А в 1>е — это наименьшее (по е-своднмости) множество, к которому е-сводится характеристическая функция каждого множества, е-сводимого к А, то есть множество J(A) — е-скачок множества А тогда и только тогда, когда выполнено требование

J) VB[(B <еА — св <е ЦА)) A VC[(B <е А — св <. G) — J(A) <в С\]. Одно из определений е-скачка множества А приводится в [40]:

J(A) = тсА. =ЛефЖ, где Ае = {х : х € Ф«(Л)}.

Определим и множества, образующие арифметическую иерархию, как это сделано в [58].

Определение 4. Пусть А — произвольное фиксированное множество. i) В € £о = По В-А - вычислимо; ii) В 6 ££ (является — множеством), где п > 1, если существует такое А-вычислимое отношение R(x, yi, Уг> • • • > Уп), что € В (3yi)(Vy2). • • (Qyn)B{x, .Уп), где Q является квантором 3, если п нечетно, и квантором V, если п четно; iii) В € (является П£ — множеством), если х е В (Vyi)(3y2). (Qyn)R(x, уг, у2,., уп), где Q является квантором 3, если » четно, и квантором V, если п нечетно; iv) В € А* В е Е£ Л П£; у) множество В называется арифметическим относительно А, если В €

Если А — вычислимая множество, то приставку А из термина "А- вычислимое" опускаем и вместо П£, Д^ пишем, соответственно, Е£, П°, .

Следующая теорема связывает иерархию Т-степеней, определенную с помощью Т-скачка, с арифметической иерархией. . - .

Теорема 5 (Релятивнзнрованная теорема Поста). Для любого п € ш (i) В € Е£+1 В е.». относительно А^; (и) В <Т А<я> В €

Пусть Ру*' множество всех в.п. Т-степеней. Обозначим через р^"-®-®-множество всех ко-в.п. е-степеней, то есть — {rfe(A) : Л — в.п.}.

Так как С VT(< 0^), то e(V%') - С Х>с(< 0'е). Используя терминологию арифметической иерархии множеств, можно сказать, что dc(A) € V?—-*- А - П? - множество.

Обозначим через (Уе = de(K) = t/e(J(0)) и через а' = tfe(J(A)) для произвольной е-степени a=de(A). Достаточно хорошо известно (см. также лемму 1.1.27), что для любого множества А и его е-степени а = dt(A) i) лег^ ^ а<о;; ii) Ае Д§ <=> А<тК <=* АфЛ<е R.

Легко убедиться, что любая тотальная е-степень < содержит А®- множество, но обратное утверждение неверно, то есть существуют нетотальные А множества, не принадлежащие тотальным е-степеням. е-степени, содержащие Eg-, но не А°-множества, называются собственно Е^-е-степенями. Очевидно, что собственно Е2-е"степени нетотальны. Свойства Е^-е-степеней изучались в статье [31].

Докажем теперь, что вложение с : Т>т —*■ Ve сохраняет скачок степеней. Ранее этот факт отмечен в [40].

Следствие 6. Для любой Т-степешя dr(A) c(dT(A')) = de(3(rcA)).

Доказательство. Так как б(<£г(А)) = <fe(r<u) и тса» =е 3(тса), то

1Г(А')) = de(rcAt) = de(3(rcA)).

Итак, отображение е осуществляет изоморфное вложение алгебраической структуры (Ру, <, U,'), где < - частичный порядок на Т>т> U г бинарная операция взятия супремума, ' - операция Т-скачка в алгебраическую структуру (Ре> <>и/), где <,U,' - соответствующие операции в Ре, причем е(2?г) = Т.

В §1 Главы I приводится одно из интуитивных определений Тьюринговой сводимости, анализируется основное свойство Т-скачка множества А — множества, с помощью которого можно решить проблему разрешимости для любого множества, Т-сводимого к А. С помощью машины Тьюринга с оракулом строится формализация понятия Тьюринговой сводимости множеств и Т-скачка множеств, в основном, как это сделано в [58].

Для формализации интуитивного определения сводимости по перечислимости множеств использованы два подхода. Первый, основанный на модификации машины Тьюринга с внешней лентой, дает общепринятое формальное определение е-сводимости, принадлежащее Фридбергу и Роджерсу [74], которое используется в данной работе. Второй подход связан с понятием вычислимой операции, введенного В.А. Успенским [71], частным случаем которой является оператор перечисления.

Приемлемая формализация понятия е-скачка множеств должна удовлетворять естественному условию равенства е-скачков е-эквивалентных множеств, а также соответствовать требованию (J). Привадится определение е-скачха, которое с точностью до вычислимого изоморфизма совпадает с Т-скачком (но использует понятие оператора перечисления, то есть сформулировано в терминах е-сводимости), но при этом невозможно корректно перенести этот е-скачок на е-степени.

Одна из первых формализация е-скачха принадлежит Розинасу [50]. Знании тельно позже и, по-видимому, независимо были даны еще два определения е-скачха множеств в [40] и [28]. В монографии [16] с помощью рш-сводимости множеств, (которая является усилением е-сводимости множеств) строится скат чок множеств через понятие универсального оператора. Это удается сделать и для е-сводимости, причем доказано и существование универсальных е- операторов, и независимость е-цилиндрификации множества от выбора универсального е-оператора. Приводятся основные свойства е-цилиндрификаций и е-цилиндров, в частности, с помощью лемм 1.1.21 и 1.1.22 доказано, что формат лизация понятия е-скачха, основанная на понятии универсального е-оператора, соответствует интуитивным требованиям, которые были выдвинуты выше. Заключает §1 ряд теорем, в которых изучены соотношения между различными определениями е-скачков и Т-скачка.

Первый серьезный результат о е-сводимости был получен Ю.Т. Медведевым [43], а именно, было доказано, что существуют нетотальные е-степени, то есть, что "DC\T ф 0. Медведев построил такую частичную функцию -ф : w —»w, которая не является частично вычислимой и для любой тотальной функции /, если / <в ф, то / - вычислимая функция. Кейс в [21] назвал е-степени, содержащие графики функций, обладающих указанным выше свойством, клаэиминималъ-чыми. Заметим, что при рассмотрении е-сводимости на 2", есть смысл дать определение квазиминимального множества в следующей форме: А — квдак-минималъное множество, если А не в.п. и для любой тотальной функции /, если / <в А, то / - вычислимая функция. Из определения следует, что если а - квазиминимальная е-степень, то она нетотальная и Ve(< а) ПТ = {Ов}. Обозначим через Q множество квазиминимальных е-степеней.

На полезность понятия категории множества в топологическом пространстве при сравнении множеств степеней впервые было указано Майхиллом [38]. Определим на 2" топологическое пространство. Базой В будет служить совокупность множеств вида "Do — {А : D С А} для всевозможных конечных множеств D (включая 0). Множество А С 2" называется замкнутым, если 2е" \ А 6 В. Замыкание [Л] множества А определятся как пересечение всех замкнутых надмножеств А. Множество А элементов топологического пространства называется нигде не плотным, если его замыкание не содержит ни одного непустого элемента из В. Говорят, что А — множество первой категории, если А есть конечное или счетное объединение нигде не плотных множеств.

Всякое множество А, не имеющее первой категории, называется множеством " второй категории.

Всякая совокупность е-степеней определяет некоторое подмножество вУ. Поэтому понятие категории можно использовать, чтобы сравнивать множества е-степеней. Если А = {Л}, то, как легко понять, А - множество первой категории. Так как любая е-степень представляет собой счетную совокупность множеств, то А = dc(A) — множество первой категории. По таким же соображения, Ve(< а) — множество первой категории для любой е-степени a, a Z?e(> а) множество второй котегории. Само множество 2?в имеет вторую категорию. Существуют также несчетные множества е-степеней, имеющие первую категорию. В [79] показано, что семейство е-степеней, содержащих продуктивные множества, имеет первую категорию. В [38] показано, что множество квазиминимальных е-степеней Q имеет вторую категорию.

Существование нетотальных е-степеней можно обосновать с помощью вложения с. Пусть а — минимальная Т-степень, то есть

От < а Л (Vx € VT)[x < а х = От), существование которой впервые доказано в [69]. Рассмотрим е-степень b = е(а). Ясно, что b ф 0е. В [8] показано, что Ре не имеет минимальных элементов, поэтому существует е-степень с ф 0в, такая, что с < Ь. Если предположить, что с является тотальной е-степенью, то существует множество С 6 с, такое, что С =е сс. Рассмотрим dr(C). Так как c(iy(C7)) = с, то dr(0) < а и поэтому dx(C) — От (то есть С — рекурсивное множество). Тогда, с = с (Ох) = 0е, что противоречит первоначальному предположению. Итак, с является нетотальной е-степенью. Из предыдущих рассуждений следует, что все е-степени, кроме 0в, расположенные строго ниже е-степени b = е(а) (сама е-степень b является тотальной), где а — какая-либо минимальная Т-степень, являются нетотальными, и, более того, квазиминимальными. Кроме того, из отсутствия минимальных е-степеней в 2>в и факта, что множество минимальных Т-степеней является множеством первой категории (см. [53]), a Q

- множество второй категории (см. [38]) следует, что существуют квазиминимальные е-степени, которые не лежат под образами минимальных Т-степеней при вложении е.

В [53] доказано, что существуют минимальные Т-степени ниже Оу, поэтому для каждой такой минимальной Т-степени а < 0у существует счетное множество квазиминимальных е-степеней ниже с(а) < Итак, Q(< 0^) Ф 0, более того, Q(< О;) = К0.

В [13] вводится понятие полурекурсивного множества: A Q ы полу рекурсивно, если существует рекурсивная функция f \ и? и, для которой

С) Я*,у)п{*,у}^0, ii) {г,у}ПА?&0-+/(г,у) €A длявсехг,у €о/.

Там же доказано, что каждая ненулевая Т-степень содержит полурекурсивное множество А, такое, что А и Л оба не вычислимо перечислимы и de(A)\de(A). В [3] показано, что в этом случае е-степень de(A) квазиминимальная (и de(A) квазиминимальная тоже). Так как тел =т А =г Л, de(rcA) — dt(A) U de(A) и de(A) П de(A) =0e (см. также [3]), то каждой ненулевой тотальной е-степени а можно сопоставить ромб, вложенный в Ve(< а), нижняя вершина которого — 0е, верхняя — а и две боковые вершины — квазиминимальные е-степени de(A) и de(A). Отсюда, в частности, следует

Предложение 7. Ve(< а) П Q ф 0 для любой тотальной е-степени а ф 0в.

Из предложения 7 следует, в частности, что существуют нетотальные е-степени, содержащие Дмножества. е-степень а называется расщепляемой, если существуют е-степени Ъ и с, такие, что 0(<b<a,0e<c<aia=bUc. Таким образом, любая тотальная е-степень расщепляема в квазиминимальных е-степеиях. В то же время достаточно очевидно, что существуют тотальные е-степени, которые не расщепляемы в тотальных е-степенях.

Ненулевые е-степени а и b образуют минимальную пару, если а П b = 0С. Из приведенного выше результата следует, что любая ненулевая тотальная е-степень ограничивает минимальную пару, образованную квазиминимальными е-степенями.

В §1 главы П вводятся некоторые обобщения понятия квазиминимальности и» устанавливается связь между квазиминимальностью и генеричностью множеств и их е-степеней.

Впервые понятие генеричности для частичных функций было введено Кейсом [21] в терминах коэновского форсинга относительно языка арифметики 1-го порядка. Одно из свойств генерических функций, полученных в [21], позволяет доказать, что любая е-степень, содержащая график генерической функции (generic function), является квазиминимальной. В [14] Джокуш ввел понятие п-генерической функции (п 6 ш) и доказал, что каждая е-степень, содержащая график 1-генерической функции, квазиминимальна. В [30] приведено определение Копестейк множественной п-генеричности (set n-generic) для множеств. В [24] она доказала, что существуют 1-генерические е-степени, под которыми нет минимальных пар в Ре.

Из приведенного выше обзора результатов о нетотальных е-степенях можно сделать ошибочный вывод, что все нетотальные е-степени являются квазиминимальными. Однако релятивизация понятия квазиминимального множества позволяет легко построить нетотальные е-степени, которые не являются кваг зиминимальными. Напомним, что, как и в [55], множество А называется С-к в аэнмчним ильным, (где С — данное множество) если С <е А и / <е А —► <е С для любой тотальной функции /. В этом случае е-степень de(A) называется с-клазжм*н*мальчой} где с= de(C). Обозначим через Qc множество с-квазиминимальных е-степеней. Ясно, что Q — Qo и любая с-квазиминимальная е-степень нетотальна. В [55] показано, что Qc ф 0 для каждой е-степени с. Можно доказать, как это сделано для Q, что Qa является множеством второй категории для любой е-степени с.

Представляет определенный интерес выявить соотношения между семействами Qc для различных с € Ve относительно теоретико-множественного включения С. В теореме 2.1.7 доказаны некоторые из таких соотношений.

Наконец, в §1 главы П приводится наиболее общее понятие относительной квазиминимальности, принадлежащее Сламану и Сорби [57], — понятие, так называемой, I-квазиминимальной е-степени, где X С Ve — произвольной множество е-степеней. Это понятие будет использовано нами в главе V для харак-теризации нетотальных е-степеней.

В $2 изучаются цепи и антицепи с-квазиминимальных е-степеней. В [67] автором доказано, что для любой е-степени с в Qa существуют несчетные антицепи и несчетные возрастающие цепи.

Общий подход к пониманию структуры верхней полурешетки Z?e е-степеней, а также структуры нетотальных е-степеней (то есть частично упорядоченного множества Ре \ Т) состоит в изучении решеток, которые можно или нельзя вложить в 2?е> В §3 главы П доказано (теорема 2.3.1), что если с < а и а - тотальная е-степень, то в частично упорядоченное множество Qc(< а) с-квазиминимальных е-степеней < а изоморфно вложимо любое, не более чем счетное частично упорядоченное множество. Так как е-скачок с' любой е-степени с является тотальной е-степенью, то из теоремы 2.3.1 следует, что в частично упорядоченное множество Qc(< с') изоморфно вложим любое, не более чем счетное, частично упорядоченное множество. Оказывается, подобным свойством универсальности обладают также и некоторые его собственные подмножества, а именно, частично упорядлченное множество

Ль = {а : а € Qe А а|Ъ А с < а < Ъ'}, где Ъ - произвольная е-степень, для которой с < Ъ и V < с\ Более точно, теорема 2.3.9 утверждает, что если с < Ъ - произвольные е-степени, то в частично упорядоченное множество Ль изоморфно вложимо любое, не более чем счетное, частично упорядоченное множество.

В §4 главы II исследуется вопрос о возможности дополнения данной е- степени b > с до с- минимальной пары в QC) то есть о построении такой е-степени а 6 Qc, чтобы было выполнено условие а П b = с. Впервые подобный вопрос был поставлен в статье [41] и решен положительно: любая ненулевая е-степень дополняема до минимальной пары. В теореме 2.4.$ показано, что для любых е-степеней Ь и с, таких, что с < Ъ и с* = Ъ', существует с- квазиминимальная е-степень а < с', такая, что аПЪ = с. Как следствие, из этого результата можно вывести, что любая низкая е-степень (то есть такая е-степень а < 0^, для которой а = 0^,) дополняема до минимальной пары в Q. Используя метод, предложенный в статье [41], доказана теорема 2.4.13, которая утверждает, что любая низкая е-степень дополняема до минимальной пары в Q{< а), где а > с и а - Е^-высокая е-степень.

В статье [32] Купером и Сорби доказано, что существуют не дополняемые до минимальной пары е-степени, содержащие множества. В статье [19] Калимуллин доказал, что существуют е-степени, содержащие множества, не дополняемые до минимальной пары в А °. Таким образом, не любая е-степень Ъ > с дополняема до с-минимальной пары в определенном классе е-степеней. В теореме 2.4.16 доказано, что в классе Qa любая е-степень Ъ > с дополняема до с-минимальной пары.

Четырехэлементную решетку Rh = {а, 6, с, <£} с операцией < будем называть ромбом, если а < b < d, а < с < </, Ь jt с и с jt Ь. При этом элемент а € Rh будем называть нижней, d € Rh - верхней вершинами ромба. В §5 главы II исследуется вопрос о вложимости ромба в Qc с сохранением с как нижней вершины. В теореме 2.5.2 доказано, что такое вложение возможно. В то же время, для любой е-степени с существуют с-квазиминимальные е-степени а и Ъ, такие, что a U b Qc. Достаточно очевидно, что в этом случае супремум е-степеней а я b не существует в Qa.

В статье [33] вводится понятие дополняемости е-степени а наверх (до е-степени с > а): е-степень а называется дополняемой наверх, если существует b < с, такая, что a U b = с. В теореме 2.5.10 доказано, что любая с- квазиминимальная е-степень а дополняема наверх в Qc ДО е-степени из Qc, а если еще а' = с', то дополняема наверх в Qc(< с'). е-степень b называется разложимой, если существуют е-степени ао < b и ai < b, такие, что aoUai = b. Теоремы о разложении Т-степеней доказывались Саксом, Робинсоном, Лахланом. В статье [3] показано, что (Уе разложима в А®, а в [4], что существуют неразложимые е-степени, содержащие А^-множества. Из теоремы 2.5.14 следует, что е-скачок с' любой е-степени с разложим в Qc.

В рамках Международных школ "Рекурсивная теория и сложность", Казань, 1997 г., "Теория вычислимости", Новосибирск, 2000 г. и "Вычислимость и модели", Хайдельберг, 2001 г. обсуждались проблемы характеризации тех или иных классов е-степеней в терминах свойств их элементов. В этой связи представляет определенный интерес проблема характеризации нетотальных е-степеней. В качестве примера положительного решения подобной проблемы можно привести результат из статьи Кейса [21]: тотальные и только тотальные е-степени содержат ретрассируемые множества.

В статьях [63] и [68] автор вводит специальные классы иммунных множеств, е-степени которых нетотальны. Пусть во, «1,., o«,. - элементы бесконечного множества А, расположенные в порядке возрастания, или прямой пересчет А. Множество А называется е-гипсриммунным, если не существует тотальной функции д : ы —► а/, такой, что j <« Л и о« < д(п) для всех л € а/, то есть никакая тотальная функция, е-сводящаяся к А, не мажорирует прямой пересчет А. Бесконечное множество А называется е-иммунпым, если для любой тотальной функции / <е А pf С A—* pf — конечно.

В главе Ш изучаются е-степени, содержащие е-иммунные множества. Как было показано Розинасом в [51], если Ai и Ач — иммунные или гипериммунные множества, то е-степень <2e(Ai Ф А2) обязана содержать иммунное или гипериммунное множество, соответственно. Для е-иммунных множеств могут быть различные ситуации, то есть существуют е-иммунные множества А\ и А2, таг кие, что Ai|eA2 и de(A± ф Аз) содержит е-иммунное множество и, напротив, существуют е-иммунные множества А\ и Аг, для которых de(Ai ф Аг) не содержит е-иммунных множеств.

В предложении 3.4 доказано, что если А — е-иммунное множество, В — А-квазиминимальное множество, то е-степень dc(B) содержит е-иммунное множество, то есть имеется частичное наследование свойства е-степени содержать е-иммунное множество вверх в Однако, как показано в теореме 3.5, существуют интервалы в 2?е> не содержащие е-иммунных е-степеней, то есть полного наследования свойства е-степени содержать е-иммунные множества нет. Из теоремы 3.5., в частности, следует, что существуют нетотальные е-степени, не содержащие е-иммунных множеств. Это дает ответ на вопрос из статьи [63]. В то же время показано (теорема 3.6 и следствия 3.7 и 3.8), что для любого ретрассируемого множества В существует несчетное семейство е-иммунных множеств строго выше В в отношении <е.

Обозначим через I класс иммунных, EI — класс е-иммунных, Б HI - класс е-гипериммунных множеств. Доказано, что EHIcEIcI и IriQcEI. Кроме того, все е-степени из класса EI являются нетотальными, но, в то же время, существуют иммунные нетотальные е-степени, не принадлежащие EI. С помощью теоремы 3.9 можно построить е-иммунные множества А\ и Аг так, что е-степень dt(A\ ф А2) является тотальной. Ясно, что в этом случае обязательно

Ai|eA2.

Одним из традиционных вопросов в теории сводимостей является вопрос о внутреннем строении степеней. Рассмотрим одно усиление е-сводимости, введенное Скордевым [56]: множество А рс-сводимо к В посредством частично вычислимой функции фу если т.

Vasfas 6 А х 6 6ф Л С В].

Будем писать А <ро В, если существует ч.в.ф. ф, для которой А рс-сводится к В посредством ф. Как обычно, dpc(A) = {В : В <р0 At\A <рс В} - рс-степень множества А. Очевидно, что А <ре В —* А <е В, поэтому произвольная е-степень состоит из некоторой совокупности рс-степеней. Если е-степень de (А) содержит более, чем одну рс-степень, то говорят, что de(A) распадается на рс-степени. Ясно, что О не распадается на рс-степени, то есть состоит из единственной рс-степени. С.Д.Захаров [18] показал, что существуют ненулевые е-степени, состоящие из единственной рс-степени. Как показано автором в [65], любая ненулевая тотальная е-степень содержит, по крайней мере, две различные рс-степени (см. также теорему 4.7 в главе IV). Поэтому, если е-степень состоит из единственной рс-степени, то она нетотальная. Как показано в теореме 3.17, это достаточное условие нетотальности е-степени не является необходимым. Оказывается, любая неквазиминимальная е-степень, содержащая е-иммуниое множество, распадается на рс-степени.

Вопрос о том, каким образом дополнительные ограничения на е-сводимость (и, вообще, на любую сводимость) "дробят" е-степени, всегда вызывает большой интерес в теории вычислимости. В частности, рс-сводммость множеств, как наиболее естественное усиление е-сводимости, является важным объектом для исследования. Обозначим через Р£в(А) частично упорядоченное множество рс-степеней внутри е-степени множества А. В [59] автором доказано, что е-степени гипериммунных ретрассируемых множеств содержат счетные возрастающие цепи, а также счетные антицепи рс-степеней. В последующей работе [61] доказан более общий результат о том, что в частично упорядоченное множество рс-степеней внутри е-степени гипериммунного ретрассируемого множества А изоморфно вложим любой, не более чем счетный частичный порядок. Этот результат вытекает из теоремы 4.1, которая утверждает, что решетка вычислимо перечислимых множеств изоморфно вложима в Dg*(A).

Как видно из доказательства теоремы 4.1 столь "богатую" структуру множеств 2f е(А) имеет благодаря гипериммунности множества А. Если отказаться от этого условия, но сохранить тотальность dc(A), то можно доказать теорему 4.7, из которой следует, что Р£С(А) содержит счетную антицепь рс-степеней.

Как уже отмечалось выше, е-степени, состоящие из единственной рс-степени, являются нетотальными. Чтобы доказать, что существуют нетотальные е-степени, содержащие более одной рс-степени, в главе IV вводится релятивизация понятия гипериммунности множеств. Пусть Е С и> — произвольное множество. Как в [59] назовем бесконечное множество А Е-гип ер иммунным, если условие д<еЕлУп(ап<д(п)) не выполняется ни для какой тотальной функции д, где {an}ngw - прямой пересчет множества А. Бели Е - вычислимо перечислимое множество, то Е-гипериммунное множество А является гипериммунным. В нашей терминологии, е-гипериммунное множество А — это А-гипериммунное множество. Существование Л2-гипериммунных множеств для любого Е С и/ доказано с помощью теоремы 4.9, а е-гипериммунных множеств — теоремы 4.10. Из теоремы 4.12 следует, что выше любого множества В существуют несчетные возрастающие цепи е-гипериммунных множеств.

Очевидно, что для е-гипериммунных множеств верна теорема 3.5 (с заменой е-иммунности на е-гипериммунность). В то же время, как показано в теореме 4.14 под е-скачхом любого множества Е существуют е-гипериммунные множества. Более того, если Е — ретрассируемое множество, то интервал (de(E), de(J(E)))a содержит е-гипериммунные е-степени (следствие 4.15).

Выше было отмечено, что класс EHI е-гипериммунных множеств является частью класса HI гипериммунных множеств, то есть EHICHI. Несовпадение этих классов следует, например, из того, что существуют гипериммунные множества, которые принадлежат тотальным е-степеням, в то время, как е-гипериммунные е-степени обязательно нетотальные (теорема 4.17). Кроме того, класс HI замкнут относительно подмножеств, а класс EHI нет (теорема 4.17). В теореме 4.19 доказано, что существуют нетотальные гипериммунные е-степени, не содержащие е-гипериммунных множеств.

В теореме 3.16 показано, что неквазиминимальные е-степени, содержащие е- иммунные множества, распадаются на рс-степени. Разумеется, этот результат имеет место и для неквазиминимальных е-степеней, содержащих е-гипериммунные множества. Пусть П — счетное, частично упорядоченное множество, каждый элемент которого имеет не более конечного числа предшественников. Используя результат Сакса [54], в теореме 4.23 доказано, что существует е-гипериммунное множество А, для которого П изоморфно вложимо в Z>§e(A), а следствие 4.24 показывает, что для любого е-гипериммунного множества В, такого, что А <е В, в 72%С(А) изоморфно вложимо частично упорядоченное множество П.

В главе V (теорема 5.2) строится е-гипериммунное множество А, е- степень которого а = de(A), следовательно, нетотальна и не является f- квазиминимальной для любой тотальной е- степени f < а. Пусть G - семейство тотальных е- степеней, образующих строго возрастающую последовательность, тогда, как показано в предложении 5.3, существует (7- квазиминимальная е-степень а, которая не является f-квазиминимальной для любой тотальной е-степени f < а. Теорема 5.4. дает следующую характеризацию нетотальных е-степеней: любая нетотальная е-степень а является f- квазиминимальной для некоторой тотальной е-степени f < а или (7-квазиминимальной для некоторого семейства тотальных е-степеней G = {g«}»eu>, образующего возрастающую последовательность go < gi < • • • < g. < • • • < а.

В главе V строится класс множеств, е-степени которых нетотальны. В [67] автор вводит понятие строго нетотального множества. Множество АС. и называется строго нетоталъчым, если А — не вычислимо перечислимо и

Уя[ФА(Л) бесконечно —► (Зд вычислимая ^уяк«1«я)(Уи)[Др(и) С АЛ

А{® : 3<((ar,0(*)) € Wn)} бесконечно)).

Пусть SNT — класс строго нетотальных множеств. В теореме 5.12 доказано, что класс SNT имеет несчетную мощность, SNTc Q и SNTnI= 0.

Глава VI посвящена доказательству недистрибутивности операций U и частичной операции Пв^ф С этой целью доказана теорема 6.6, которая утверждает, что в любой отрезок [с, может быть изоморфно вложена недистрибутивная пяти элемента ая решетка с наименьшим элементом с и с- квазиминимальными остальными элементами. Ранее, в статье [41] было доказано, что любая решетка, вложенная в низкие вычислимо перечислимые Т-степени, может быть вложена в . Отсюда следует, что результат Лахлана [36] о вложении недистрибутивной пяти элементной решетки в низкие вычислимо перечислимые Т-степени дает вложение такой решетки в

В теореме 6.1 доказано, что операции Пии "локально" дистрибутивны, то есть в Ve вложи мы конечные полурешетки, удовлетворяющие условию a=bncAai >а—*аг = (aiUb)n(aiUc) и двойственному ему a=bUcAai <а—*ai =s (ainb)U(ainc). Из теоремы 6.1 получен ряд интересных следствий.

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

Работа носит теоретический характер. Бе результаты могут найти применение в различных областях математической логики, в особенности в теории алгоритмов и теории сложности.

Результаты диссертации докладывались на различных всесоюзных и международных конференциях в период с 1976 г. по 2001 г. Среди них IV (Кишинев, 1976 г.), V (Новосибирск, 1979 г.), VIII (Москва, 1986 г.), IX (Ленинград, 1988 г.), X (Алма-Ата, 1990 г.) Всесоюзные конференции по математической логике; XII (Казань, 1992 г.) Межреспубликанская конференция по математической логике; IX Всесоюзное совещание по логике, методологии и философии науки (Харьков;*1986 г.); I, II и III Математические чтения памяти М.Я. Суслина (Саратов, 1989,1991 и 1994 г.г., соответственно,); Международная научная конференция, посвященная 100-летию Н.Г. Чеботарева "Алгебра и анализ" (Казань, 1994 г.); Международная конференция по алгебре, посвященная памяти А. И. Мальцева (Новосибирск, 1989 г.); Международная конференция по алгебре, посвященная памяти А. И. Ширшова (Барнаул, 1991 г.); III Международная конференция по алгебре (Красноярск, 1991 г.); Казанская школа "Рекурсивная теория и сложность" (Казань, 1997 г.); Школа по теории вычислимости (Новосибирск, 1998 г.); Международная конференция, посвященная 60-летию академика Ю.Л. Бршова "Логика и приложения" (Новосибирск, 1998 г.); Международная конференция "Вычислимость и модели" (Хайдельберг, 2001 г.); Школа по вычислимости (Новосибирск, 2001 г.); семинар лаборатории математической логики ПОМИ (Санкт-Петербург, 2001 г.)

Основные результаты диссертации опубликованы в работах автора [59] — [68]. Диссертация состоит из введения, шести глав и списка литературы. Общий объем — 154 AMSTEX-страниц. список литературы содержит 77 наименований.