Нетотальные степени перечислимости тема диссертации и автореферата по ВАК РФ 01.01.06, доктор физико-математических наук Солон, Борис Яковлевич

• Солон, Борис Яковлевич
• доктор физико-математических наук
• 2003

Введение диссертации (часть автореферата) на тему «Нетотальные степени перечислимости»

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

Пусть 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 наименований.