Содержание к диссертации
Введение
Глава I. Тыоринговая сводимость и сводимость по перечислимости 19.
1 Т-скачок и е-скачок множества 19.
2 Соотношения между Тьюринговыми степенями и степенями перечислимости 32.
Глава II. С-квазиминимальные множества 37.
1 Квазиминимальность и генеричность множеств 37.
2 Цепи и антицепи С-квазиминимальных множеств 43.
3 Теоремы о вложении 51.
4 Дополняемость в Qc до с-минимальной пары 64.
5 Дополняемость наверх в Qa 73.
Глава III. Иммунные множества .86.
Глава IV. Гипериммунные множества 100.
Глава V. Характеризадия нетотальных е-степеней 125.
Глава VI. Недистрибутивность 2>е 138.
Литература 149.
- Соотношения между Тьюринговыми степенями и степенями перечислимости
- Цепи и антицепи С-квазиминимальных множеств
- Дополняемость в Qc до с-минимальной пары
- Гипериммунные множества
Введение к работе
Основные определения н обзор результатов.
Пусть ы = {0,1,...} — множество натуральных чисел. Одноместная функция / : и — и называется алгоритмически вычислимой или вычислимой с помощью аффективной процедуры (в интуитивном смысле), если существует алгоритм, позволяющий по данному входу т получить выход /(г). Опуская слово "алгоритмически", мы получаем понятие вычислимой функции (computable function), если / — тотальная функция, и частично вычислимой (partial computable), если / — частичная функция.
Уточнения или, как принято говорить, формализации понятий алгоритма и вычислимой функции были сделаны в 30-е годы прошлого века Клини [23], Черчем [77], Тьюрингом [70], Геделем и другими. Как один из результатов - создание теории вычислимости и соответствующей терминологии, в которой термин "рекурсивный", введенный Клини [22] для обозначения функций, вычислимых по Клини (recursive function), стал использоваться и для названия функций, вычислимых по Тьюрингу, и в случае других формализации. Это привело к появлению "Теории рекурсивных функций" (Recursive Function Theory). Различие в использовании терминов "вычислимый" и "рекурсивный" было стерто в монографии Роджерса [49] "Теория рекурсивных функций и эффективная вычислимость". Как было сказано в предисловии "От редактора перевода" В.А. Успенским, в этой книге "систематически излагается общая теория рекурсивных функций, то есть функций, вычислимых посредством алгоритмов". Термин "рекрсивный" стал использоваться также и в смысле "разрешимый" (decidable), в результате множества, характеристическая функция которых рекурсивна (разрешимые множества), были названы рекурсивными, а множества, которые являются областями определения подходящих частично-рекурсивных функций, — рекурсивно перечислимыми (recursively enumerable).
В 1995 г. Роберт Соар предложил вернуться к исходной терминологии и использовать термин "вычислимый" в смысле Геделя и Тьюринга, а термин "рекурсивный" только для определений по рекурсии (то есть сузить понятие "рекурсивный" до его фактического смысла). Это предложение стало общепринятым и теперь название предмета из "Теории рекурсии" изменено на "Теория вычислимости", "рекурсивные функции" (в широком смысле) называются "вычислимыми", "рекурсивно перечислимые множества" — "вычислимо перечислимыми" и т.д.
В диссертации нумерация определений, предложений, лемм и теорем сплошная внутри каждого параграфа или главы, (если она не разбита на параграфы). В введении номер утверждения состоит из одного числа. В главах I и II но мер состоит из трех чисел: номер главы.номер параграфа.порядковый номер утверждения". В главах III -VI номер утверждения состоит из двух чисел: "номер параграфа, порядковый номер утверждения".
Приведем обозначения и терминологию, которые будут использованы в тексте диссертации. Многие из них такие же, как и в монографии [49]. С учетом общепринятого ныне предложения Соара, пусть {Wn}ntw и {фп}пеш геде-лева нумерация всех вычислимо перечислимых (в.п.) множеств и частично вычислимых (ч.в.) функций {W,J}#e« — конечная вычислимая аппроксимация вычислимо перечислимого множества Wn. Как обычно, Du — конечное множество с каноническим индексом ti Є w, таким, что если Du = {xi,..., хп} и a?i • • • хп, то и = 2 1 + • • + 2е", и А) = 0 { 0 - канторовский номер упорядоченной пары (к, /). Если t — канторовский номер пары (к, /), то ( )i = k и {t)i = I. Обозначим для множества В через (В)і — {я : 3tt((x, tt) Є В)}, через (х, D) — (х, и), где D — Du. Через А будем обозначать мощность множества А С. и, то есть А = Ко, если А — бесконечное множество, \А\ — число элементов конечного множества А ф 0 и 0 = 0. Иногда будем писать \А\ = со, если А - бесконечное и \А\ со, если А - конечное множество. Пусть, как обычно, К = {х : х Є Wm} ж R = (j\K, KQ = {(х,п) : х Є Wft}. Хорошо известно, что К вычислимо изоморфно .Ко (и, следовательно, К s KQ).
Для функции а : ы — ы через Sot будем обозначать область определения, ра — область значений и та = {(х, а(х)) : € а} - график а. Тот факт, что х Є Sat будем записывать как аг(х) , а х аг, как а(х) f. Буквы /, д будем использовать только для обозначения тотальных функций, т.е. Sf — Sg — w. Обозначим для множества А через •— . f 1, если х Є А ел{х) = л . . \ 0, если х . А — характеристическую и . ч ГО, если х Є А Х »( )=і + л , [_ у, если х А — частичкою га акте истяческую доккчян множества А. Множество А называется однозначным, если А = та для некоторой функции а.
В вычислениях, использующих дополнительную информацию, имеет большое значение способ, с помощью которого она становится доступной для вычислителя. Без учета временных ограничений таких принципиально различных способа два: через оракула, когда новая информация появляется на запрос немедленно, и через перечисление, когда новая информация постоянно генерируется и может быть поставлена на запрос только ее некоторая часть. Первая модель вычисления, основанная на оракулах, приводит к понятию Т-сводимости (сводимости по Тьюрингу) множеств, а вторая, основанная на перечислимости, приводит к е-слодимости (сводимости по перечислимости) множеств. Т-сводимость и связанная с ней степенная структура изучаются, начиная с 1936
года, и имеют обширную и глубокую теорию, а е-сводимость, возникшая в 1955 году, привлекла активное внимание математиков лишь в последние десятилетие.
Напомним определение Фридберга и Роджерса из [74], которое мы принимаем за основное. С интуитивной точки зрения, множество А сводится по перечислимости или е-сеодитсм к множеству В (символически, А в В), если существует равномерный алгоритм для получения некоторого перечисления элементов А из любого перечисления элементов В. Формально, Определение 1. А е В «= ЗпУф ЄЛ«- Зи[(х,«) Є W» Л Д, В]}. В §1 главы 1 дадим подробное обоснование данного формального определения. Обозначим через Ф»(В) = {х : Э«((ж, ti) Є Wn Л Du С В)}, тогда А в В • =• Зп(А — ФП(В)). Отображение Фп : 2 " -+ 7Ґ называется оператором перечислений или е-оператором с индексом п (как и Wn определяющее Фп). Хорошо известно, что е-операторы монотонны и непрерывны, т.е. для любого п Є u и любых А, В Cut . і А С В - ФП(Л) С ФЛ(В) и Уф Є Фп(А) - (3D - кожечмое)[1) С А Л ж Є $n(D)]]. Пусть, как обычно, А ==е В = -А е В Л В « A, de(A) - {В : В =еА}-е-степечь множества А (для обозначения е-степеней будем также использовать малые жирные латинские буквы: например, a = de(A)) и de(A) de(B) == А е В — частичное упорядочение е-степеней. Если е-степени а и b несравнимы относительно , то обозначим это через а Ь, а Ь, если а b и bj а. Будем писать для функций а, /? а в А или а е /Ї, если та е А или та е т&. Обозначим через Vt множество е-степеней, упорядоченное отношением , #е( а) = {х Є Ре : х а}, [a,b]e = {х Є Ve : а х Ь}, (а,Ь)е = {х € X e : а х Ь}, Хорошо известно (см., например, [21]), что Ve образует верхнюю полурешетку, не решетку с наименьшим элементом 0e = {Wn : п Є ш}. е-степени, содержащие графики тотальных функций, называются тотальными. Обозначим через Т частично упорядоченное множество тотальных е-степеней. Обозначения Т( а) и Т( а) используются в обычном смысле.
Термин нетоталъиам е-степеиь применим, таким образом, к степеням перечислимости, которые не содержат графиков ни одной тотальной функции. Как было показано Кейсом в [21], по любому перечислению любого множества А, принадлежащего тотальной е-степени и только тотальной е-степени, можно эффективно получить некоторое фиксированнное перечисление элементов этого множества А. Отождествим произвольное перечисление множества А с некоторой тотальной функцией р: ш —• А, область значений котрой рр = А. Пусть Р(Л) - семейство всех перечислений множества А, частично упорядоченное отношением е. Результат Кейса, процитированный выше, означает, что de(A) — тотальном = Р(А)имеет наименьший элемент. Для любого множества из нетотальной е-степени, следовательно, имеет место следующее утверждение Предложение 2. Для любого множества. А de(A) — нетотальная • = Р(Л) не имеет наименьшего элемента. Бели &=de(A) и b=de(B)y то наименьшая верхняя грань (или супремум) е- степеней а и b равна aUb = de(A®B), где А®В — {2х : х Є A}U{2x+l: х Є В}. Обозначим через а П Ъ наибольшую нижнюю грань е-степеней (или инфимум) а и Ь. В [21] впервые показано, что существуют е-степени а и Ь, для которых нет наибольшей нижней грани а П Ъ в Ve. Таким образом, бинарная операция П является частичной. В то же время, как было показано Розинасом в [52], любая е-степень с является наибольшей нижней гранью некоторых тотальных е-степеней a, b с. В общем случае можно говорить о возможности представления произвольной е-степени как наибольшей нижней грани двух е-степеней, принадлежащих определенному классу S С Ve. В этом случае е-степень с называется еетвящейся в S. Таким образом, М.Г.Розинас в [52] показал, что любая е-степень является ветвящейся в Т. Обозначим через Т т верхнюю полурешетку Т-степеней. Так как для всех А,ВСи А т В = сл « ев, то отображение е : Т т — Ve : €(dr(A)) = fe(rc i) является изоморфным вложением VT В Vet сохраняющим нибольшую верхнюю границу. Предложение 3. ЕСЛИ В— dr{A ф В) является наименьшей верхней границей Т-степеней а= dr(A) и Ь— dr{B), то е(в) является яаименьпгеіг верхней границей е-степеней с(а) = dc(TCA) и б(Ь) = rfe(rce). В частности, е(От) — 0«. Доказательство. Пусть С — тел Ф тсв, докажем, что С =е ТСА$В Имеем ТСАЪВ = {{2х, 1) : х Є A} U {(2х +1,1) : х Є В} U «2 , 0) :xA}\J {(2х +1,0) : х Б}иС={2( ,1) : х Є А}и{2(х,0) : х А}и{2 ,1)+1: х Є B}U{2( ,0) + 1 : х В}. Ясно, что С е TCAQB и тедфв е С. Так как e(s) = de(rcA$B) и С Є e(s), то c(s) является наименьшей верхней границей «(а) и «(b). Так как е-степень а тотальна тогда и только тогда, когда существует В Є а, такое что В =в сд, то Т = {&е(тсв) : В С а;}. Ясно, что Т - подполурешетха Pe» так как Ле(тсл) U de(rcjj) = de(rcA$B) Таким образом, е(2?т) = Т и Т изоморфна 2 у. Заметим, что вложение є может не сохранять точную нижнюю границу Т-степеней. В самом деле, в [52] показано, (VI Є 2 е)(Эа, Ъ Є Г)(аЪ Л і = а Л Ъ). Как было замечено выше, в этом случае существуют множества А Є а и В Є Ъ, такие, что тс А Є а И ТСВ Є Ъ, тогда с(йт{А)) = а и e(dx(J5)) = Ь. Предположим, что і является нетотальной е-степенью, тогда і ф е(х) для любой Т-степени х. Поэтому, даже если существует наибольшая нижняя грань dr(A) П dx{B) = rfx(C0» ее образ при вложении e(ij(C7)) = djjcc) не может быть равен і.
Так как ТСА Є dr{A) для любого ЛСцто при изучении Т-степеней можно идентифицировать dr(A) характеристической функцией с А- Для е-степеней эта ситуация невозможна. Ясно, что любая нетотальная е-степень не содержит никаких характеристических функций. Не столь очевидно, что тотальные е-степени не содержат графики характеристических функций всех множеств, принадлежащих им. Другими словами, можно -доказать (и это сделано в [66]), что dr(A) % de(rcA) для любого А С и. В то же время, как легко заметить, de(A) содержит Т\А для всех А С ш.
В §2 Главы 1 изучены соотношения между Т-степенями и е-степенями, как классами множеств, относительно теоретико-множественного включения. В частности, доказано, что никакая тотальная е-степень не может быть подмножеством некоторой Т-степени. В то же время, как было показано в [75], существуют Т-степени, содержащие целиком некоторые е-степени. Из этого результата следует, что внутри каждой Т-степени 0Т содержится нетотальная е-степень.
Предположение о том, что каждая нетотальная е-степень содержится (как подмножество) в некоторой Т-степени опровергается теоремой 1.2.6, в которой построена нетотальная е-степень, не содержащаяся ни в какой Т-степени.
Включение Т-степеней в е-степени возможно только в тривиальном случае: От С0е, где От состоит из всех вычислимых множеств, а 0е - из всех в.п. множеств.
В VT скачок множества А — это множество А\ которое решает проблему остановки для вычислимых относительно множества А процедур: "Для любого данного п Є ш, п Є W или нет?" В Р« скачок А должен быть таким множеством, которое отвечает на вопрос: "Для любого данного п Є о/, п Є Фп(А) или нет?" или "Для любых данных п,/ Є w, і Є &п(А) или нет? . Другими словами, е-скачок множества АъТ)е — это наименьшее (по е-сводимости) множество, к которому е-сводится характеристическая функция каждого мно жества, е-сводимого к А, то есть множество J (А) — е-скачок множества А тогда и только тогда, когда выполнено требование (J) VB[(B еА — св е 3(A)) Л VC[(# е А — св . С) — 3(A) в С\]. Одно из определений е-скачка множества А приводится в [40]: 3(A) = тсА = Ае ФА , где Ав = {ж : ж Є Ф«(А)}. Определим Е°— и П°— множества, образующие арифметическую иерархию, как это сделано в [58]. Определение 4. Пусть А — произвольное фиксированное множество. (і) В Є So = П Ч= В-А- вычислимо , (ii) J? Є » (является Ej — JtNosKecroeoJc), где п 1, если существует такое А-вычислимое отношение R(xt yi, уг • • • У») что є5 •«= (Зуі)(Уу2)...(с?уЛ)Л( ,уі,у2 Уп), где Q является квантором 3, если п нечетно, и квантором V, если п четно; (ііі) В Є Hj (является П — множеством)) если хеВ 4= - (Уу!)(3у2)...(Qyn)R(x,Уі,У2,...,уп), где Q является квантором 3, если п четно, и квантором V, если я нечетно; (iv) В Є А = В Є Е; Л П; (v) множество 2? называется арифметическим относительно А, если В Є Uew(E; un2). Если А — вычислимая множество, то приставку А из термина "А- вычислимое" опускаем и вместо Ej , П, AJ пишем, соответственно, Е, П°, А°. Следующая теорема связывает иерархию Т-степеней, определенную с помощью Т-скачка, с арифметической иерархией. .. _ . . Теорема 5 (Релятивиэированная теорема Поста). Для любого п € ш (і) В Є Е«+і = • В е.». относительно А ; (и) В Т А я = 5Є Aj +1. Пусть Ру " множество всех в.п. Т-степеней. Обозначим через 2?««-«.«. множество всех ко-в.п. е-степеней, то есть Т) е ь — {de(A) : А — в.п.}. Так как Щ С VT( (Ут), то е(Щ -) - V?- - - С Ve( 0 е). Используя терминологию арифметической иерархии множеств, можно сказать, что dc(A) Є V?- • « = А - П? - множество. Обозначим через (Уе — de(K) = c/e(J(0)) и через a = de(J(A)) для произвольной е-степени a=de(A). Достаточно хорошо известно (см. также лемму 1.1.27), что для любого множества А и его е-степени a = d6(A) (і) А =2% = & Уеі (іі) АЄД§ = А тК = A®A R. Легко убедиться, что любая тотальная е-степень 0 содержит Д f- множество, но обратное утверждение неверно, то есть существуют нетотальные Д §-множества, не принадлежащие тотальным е-степеням. е-степени, содержащие Ej-) но не Д -множества, называются собственно Е -е-степенями. Очевидно, что собственно Е -е-степени нетотальны. Свойства Е -е-степеней изучались в статье [31]. Докажем теперь, что вложение є : Т т — Ve сохраняет скачок степеней. Ранее этот факт отмечен в [40]. Следствие в. Для любой Т-степеня dr(A) e(dT(A )) = de(3(rcA)). Доказательство. Так как е(с1т(А)) — de(rcA) и тсА =е 3(тсА), то €{dT{A!)) = de(TCAi) = de(3(rcA)). Итак, отображение є осуществляет изоморфное вложение алгебраической структуры {Х т» »и/), где - частичный порядок на VT U г бинарная операция взятия супремума, - операция Т-скачха в алгебраическую структуру (ї е» fs U/)f где ,U/ - соответствующие операции в Ve, причем е(1 т) = Т.
В §1 Главы I приводится одно из интуитивных определений Тьюринговой сводимости, анализируется основное свойство Т-скачка множества А — множества, с помощью которого можно решить проблему разрешимости для любого множества, Т-сводимого к Л. С помощью машины Тьюринга с оракулом строится формализация понятия Тьюринговой сводимости множеств и Т-скачка множеств, в основном, как это сделано в [58].
Для формализации интуитивного определения сводимости по перечислимости множеств использованы два подхода. Первый, основанный на модификации машины Тьюринга с внешней лентой, дает общепринятое формальное определение е-сводимости, принадлежащее Фридбергу и Роджерсу [74], которое используется в данной работе. Второй подход связан с понятием вычислимой операции, введенного В.А. Успенским [71], частным случаем которой является оператор перечисления.
Приемлемая формализация понятия е-скачка множеств должна удовлетворять естественному условию равенства е-скачков е-эквивалентных множеств, а также соответствовать требованию (J). Приводится определение е-скачка, которое с точностью до вычислимого изоморфизма совпадает с Т-скачком (но использует понятие оператора перечисления, то есть сформулировано в терминах е-сводимости), но при этом невозможно корректно перенести этот е-скачок на е-степени.
Одна из первых формализации е-скачха принадлежит Розинасу [50]. Значительно позже и, по-видимому, независимо были даны еще два определения е-скачка множеств в [40] и [28]. В монографии [16] с помощью рт-сводимости множеств, (которая является усилением е-сводимости множеств) строится скачок множеств через понятие универсального оператора. Это удается сделать и для е-сводимости, причем доказано и существование универсальных е- операторов, и независимость е-цилиндрификации множества от выбора универсального е-олератора. Приводятся основные свойства е-цилиндрификаций и е-цилиндров, в частности, с помощью лемм 1.1.21 и 1.1.22 доказано, что формализация понятия е-скачка, основанная на понятии универсального е-оператора, соответствует интуитивным требованиям, которые были выдвинуты выше. Заключает §1 ряд теорем, в которых изучены соотношения между различными определениями е-скачков и Т-схачка.
Первый серьезный результат о е-сводимости был получен Ю.Т. Медведевым [43], а именно, было доказано, что существуют нетотальные е-степени, то есть, что Ve\T ф 0. Медведев построил такую частичную функцию ф : из — а , которая не является частично вычислимой и для любой тотальной функция /, если / в ф, то / - вычислимая функция. Кейс в [21] назвал е-степени, содержащие графики функций, обладающих указанным выше свойством, клаэиминимлль-ными. Заметим, что при рассмотрения е-сводимости на 2", есть смысл дать определение квазиминимального множества в следующей форме: А — «свде« минимальное множество, если А не в.п. и для любой тотальной функции /, если / в А, то / - вычислимая функция. Из определения следует, что если а - квазиминимальная е-степень, то она нетотальная и Ve( а) Г! Т = {0е}. Обозначим через Q множество квазиминимальных е-степеней.
На полезность понятия категории множества в топологическом пространстве при сравнении множеств степеней впервые было указано Майхиллом [38]. Определим на 2м топологическое пространство. Базой В будет служить совокупность множеств вида VD = {A : D С А} для всевозможных конечных множеств D (включая 0). Множество Л С f называется замкнутым, если 2"\Леб. Замыкание [А] множества А определятся как пересечение всех замкнутых надмножеств А. Множество А элементов топологического пространства называется кнгде не плотным, если его замыкание не содержит ни одного непустого элемента из В. Говорят, что А — множество первой категории, если А есть конечное или счетное объединение нигде не плотных множеств.
Всякое множество А, не имеющее первой категории, называется множеством " второй категории.
Всякая совокупность е-степеней определяет некоторое подмножество ВҐ. Поэтому понятие категории можно использовать, чтобы сравнивать множества е-степеней. Если А = {А}, то, как легко понять, А - множество первой категории. Так как любая е-степень представляет собой счетную совокупность множеств, то A = dc(A) — множество первой категории. По таким же соображения, Ve( а) — множество первой категории для любой е-степени а, а 2 е( а)
— множество второй категории. Само множество 2?в имеет вторую категорию. Существуют также несчетные множества е-степеней, имеющие первую категорию. В [79] показано, что семейство е-степеней, содержащих продуктивные множества, имеет первую категорию. В [38] показано, что множество квазиминимальных е-степеней Q имеет вторую категорию.
Существование нетотальных е-степеней можно обосновать с помощью вложения с. Пусть а — минимальная Т-степень, то есть От а Л (Vx Є 2 т)[х а - х = От), существование которой впервые доказано в [69]. Рассмотрим е-степень Ъ = с(а). Ясно, что Ь ф 0е. В [8] показано, что Ре не имеет минимальных элементов, поэтому существует е-степень с ф 0е, такая, что с Ь. Бели предположить, что с является тотальной е-степенью, то существует множество С Є с, такое, что С =в ее. Рассмотрим dr(C). Так как e(dr(C)) = с, то йт(С) а и поэтому dx(C) — От (то есть С — рекурсивное множество). Тогда. с = с(0т) = 0е, что противоречит первоначальному предположению. Итак, с является нетотальной е-степенью. Из предыдущих рассуждений следует, что все е-степени, кроме 0«, расположенные строго ниже е-степени Ъ = е(а) (сама е-степень Ъ является тотальной), где а — какая-либо минимальная Т-степень, являются нетотальными, и, более того, квазиминимальными. Кроме того, из отсутствия минимальных е-степеней в 2 в и факта, что множество минимальных Т-степеней является множеством первой категории (см. [53]), a Q
- множество второй категории (см. [38]) следует, что существуют квазиминимальные е-степени, которые не лежат под образами минимальных Т-степеней при вложении е.
В [S3] доказано, что существуют минимальные Т-степени ниже 07, поэтому для каждой такой минимальной Т-степени а 0у существует счетное множество квазиминимальных е-степеней ниже с(а) 0 е. Итак, Q( 0 ) Ф 0, более того, Q( о;) = Н0.
В [13] вводится понятие полурекурсивного множества: А С ы полу рекурсивно, если существует рекурсивная функция / : ы? — uf для которой
(і) Н ,у)П{х,у}ФЬ
(ii) {х,у}П АфЪ-+ f(x,у) Є А для всех x,y Є u .
Там же доказано, что каждая ненулевая Т-степень содержит полурекурсивное множество Ay такое, что А и Л оба не вычислимо перечислимы и dt(A)\de(A). В [3] показано, что в этом случае е-степень de(A) квазиминимальная (и de(A) квазиминимальная тоже). Так как тсд =т А =т Л, de(rcA) — dt(A) U de(A) и de(A) П de(A) =0« (см. также [3]), то каждой ненулевой тотальной е-степени а можно сопоставить ромб, вложенный в Ve( а), нижняя вершина которого — 0е, верхняя — а и две боковые вершины — квазиминимальные е-степени de(A) и de(A). Отсюда, в частности, следует
Предложение 7. Ре( а)ПЙ Й для любой тотальной е-степени а ф 0в.
Из предложения 7 следует, в частности, что существуют нетотальные е-степени, содержащие Дз-множества.
е-степень а называется расщепляемо если существуют е-степени Ъ и с, такие, что 0« b а, О, с аяа= bUe. Таким образом, любая тотальная е-степень расщепляема в квазиминимальных е-степенях. В то же время достаточно очевидно, что существуют тотальные е-степени, которые не расщепляемы в тотальных е-степенях.
Ненулевые е-степени а и b образуют минимальную пару, если аПЬ = 0е. Из приведенного выше результата следует, что любая ненулевая тотальная е-степень ограничивает минимальную пару, образованную квазиминимальными е-степенями.
В §1 главы П вводятся некоторые обобщения понятия квазиминимальности и» устанавливается связь между квазиминимальностью и генеричностью множеств и их е-степеней.
Впервые понятие генеричности для частичных функций было введено Кейсом [21] в терминах хоэновского форсинга относительно языка арифметики 1-го порядка. Одно из свойств генерических функций, полученных в [21], позволяет доказать, что любая е-степень, содержащая график генерической функции (generic function), является квазиминимальной. В [14] Джокуш ввел понятие п-генерической функции (п Є w) и доказал, что каждая е-степень, содержащая график 1-генерической функции, квазиминимальна. В [30] приведено определение Копестейк множественной п-генеричности (set n-generic) для множеств. В [24] она доказала, что существуют 1-генерические е-степени, под которыми нет минимальных пар в Vc.
Из приведенного выше обзора результатов о нетотальных е-степенях можно сделать ошибочный вывод, что все нетотальные е-степени являются квазиминимальными. Однако релятивизация понятия квазиминимального множества позволяет легко построить нетотальные е-степени, которые не являются квазиминимальными. Напомним, что, как и в [55], множество А называется С-кбазимчнпмллькыму (где С — данное множество) если С е А и / е А —
/ e С для любой тотальной функции /. В этом случае е-степень de(A) называется с-клазим% ималъной, где с= dt{G). Обозначим через Qc множество с-квазиминимальных е-степеней. Ясно, что Q — Со и любая с-квазиминимальная е-степень нетотальна. В [55] показано, что Qc Ф 0 для каждой е-степени с. Можно доказать, как это сделано для Q, что Q0 является множеством второй категории для любой е-степени с.
Представляет определенный интерес выявить соотношения между семействами Qa для различных с Є Ре относительно теоретико-множественного включения С. В теореме 2.1.7 доказаны некоторые из таких соотношений.
Наконец, в §1 главы П приводится наиболее общее понятие относительной квазиминимальности, принадлежащее Сламану и Сорби [57], — понятие, так называемой, Х-квазиминимальной е-степени, где X С Рв — произвольной множество е-степеней. Это понятие будет использовано нами в главе V для харак-теризации нетотальных е-степеней.
В §2 изучаются цепи и антицепи с-квазиминимальных е-степеней. В [67] автором доказано, что для любой е-степени с в Qa существуют несчетные антицепи и несчетные возрастающие цепи.
Общий подход к пониманию структуры верхней полурешетки Рв е-степеней, а также структуры нетотальных е-степеней (то есть частично упорядоченного множества 2 е \ Т) состоит в изучении решеток, которые можно или нельзя вложить в Ре» В §3 главы П доказано (теорема 2.3.1), что если с а и а - тотальная е-степень, то в частично упорядоченное множество QQ( а) с-квазиминимальных е-степеней а изоморфно вложимо любое, не более чем счетное частично упорядоченное множество. Так как е-скачок с любой е-степени с является тотальной е-степенью, то из теоремы 2.3.1 следует, что в частично упорядоченное множество Qo( с ) изоморфно вложим любое, не более чем счетное, частично упорядоченное множество. Оказывается, подобным свойством универсальности обладают также и некоторые его собственные подмножества, а именно, частично улорядлченное множество
Ль = {а: а Є Qe Л аЪ Л с а Ъ },
где Ъ - произвольная е-степень, для которой с Ъ и V с . Более точно, теорема 2.3.9 утверждает, что если с Ъ - произвольные е-степени, то в частично упорядоченное множество Ль изоморфно вложимо любое, не более чем счетное, частично упорядоченное множество.
В §4 главы II исследуется вопрос о возможности дополнения данной е- степени b с до с- минимальной пары в Qe то есть о построении такой е-степени а Є Се, чтобы было выполнено условие а П b = с. Впервые подобный вопрос был поставлен в статье [41] и решен положительно: любая ненулевая е-степень дополняема до минимальной пары. В теореме 2.4.$ показано, что для любых е-степеней Ь и с, таких, что с Ъ и с = Ъ , существует с- квазиминимальная е-степень а с , такая, что аПЪ = с. Как следствие, из этого результата можно вывести, что любая низкая е-степень (то есть такая е-степень а (УеУ для которой а = 0 ,) дополняема до минимальной пары в Q. Используя метод, предложенный в статье [41], доказана теорема 2.4.13, которая утверждает, что любая низкая е-степень дополняема до минимальной пары в Q( а), где а с и а - Е -высохая е-степень.
В статье [32] Купером и Сорби доказано, что существуют не дополняемые до минимальной пары е-степени, содержащие Е -множества. 6 статье [19] Калимуллин доказал, что существуют е-степени, содержащие П°-множества, не дополняемые до минимальной пары в Д °. Таким образом, не любая е-степень Ъ с дополняема до с-минимальной пары в определенном классе е-степеней. В теореме 2.4.16 доказано, что в классе Qa любая е-степень Ъ с дополняема до с-минимальной пары.
Четырехэлементную решетку Rh = {а, 6, с, d} с операцией будем называть ромбом, если а Ь dy а с dt & jt с и с j( &. При этом элемент а Є Rh будем называть неясней, d Є Rh - верхней вершинами ромба. В §5 главы II исследуется вопрос о вложимости ромба в Qc с сохранением с как нижней вершины. В теореме 2.5.2 доказано, что такое вложение возможно. В то же время, для любой е-степени с существуют с-квазиминимальные е-степени а и Ъ, такие, что a U b Q0. Достаточно очевидно, что в этом случае супремум е-степеней а я Ъ не существует в Qa.
В статье [33] вводится понятие дополняемости е-степени а наверх (до е-степени с а): е-степень а называется дополняемой налсрху если существует Ъ с, такая, что a U b = с. В теореме 2.S.10 доказано, что любая с- квазиминимальная е-степень а дополняема наверх в Qc до е-степени из Qc, а если еще а = с , то дополняема наверх в Qc( с ).
е-степень b называется разложимой, если существуют е-степени ао b и ai b, такие, что aoUaj. = b. Теоремы о разложении Т-степеней доказывались Саксом, Робинсоном, Лахланом. В статье [3] показано, что (Ул разложима в Д§, а в [4], что существуют неразложимые е-степени, содержащие Д-множества. Из теоремы 2.5.14 следует, что е-схачок с любой е-степени с разложим в Qe.
В рамках Международных школ "Рекурсивная теория и сложность", Казань, 1997 г., "Теория вычислимости", Новосибирск, 2000 г. и "Вычислимость и модели", Хайдельберг, 2001 г. обсуждались проблемы характеризация тех или иных классов е-степеней в терминах свойств их элементов. В этой связи представляет определенный интерес проблема характеризации нетотальных е-степеней. В качестве примера положительного решения подобной проблемы можно привести результат из статьи Кейса [21]: тотальные и только тотальные е-степени содержат ретрассируемые множества.
В статьях [63] и [68] автор вводит специальные классы иммунных множеств, е-степени которых нетотальны. Пусть оо, ві,..., о»,... - элементы бесконечного множества А, расположенные в порядке возрастания, или прямой пересчет А. Множество А называется е-гмпсриммунным, если не существует тотальной функции д : ы — а/, такой, что д « А и о» д(п) для всех л Є о/, то есть никакая тотальная функция, е-сводящаяся к А, не мажорирует прямой пересчет А. Бесконечное множество А называется с-нммунным, если для любой тотальной функции / е А
pf QA—+ pf — конечно.
В главе Ш изучаются е-степени, содержащие е-иммунные множества. Как было показано Розинасом в [51], если At и А% — иммунные или гипериммунные множества, то е-степень de{A\ ф Лг) обязана содержать иммунное или гипериммунное множество, соответственно. Для е-иммунных множеств могут быть различные ситуации, то есть существуют е-иммунные множества А\ иАг, таг кие, что А\\еАъ и de(Ai ф Аг) содержит е-иммунное множество и, напротив, существуют е-иммунные множества А\ и А для которых de{A\ ф Лг) не содержит е-иммунных множеств.
В предложении 3.4 доказано, что если А — е-иммунное множество, В — А-квазиминимальное множество, то е-степень dc(B) содержит е-иммунное множество, то есть имеется частичное наследование свойства е-степени содержать е-иммунное множество вверх в Z e. Однако, как показано в теореме 3.5, существуют интервалы в 2?е не содержащие е-иммунных е-степеней, то есть полного наследования свойства е-степени содержать е-иммунные множества нет. Из теоремы 3.5., в частности, следует, что существуют нетотальные е-степени, не содержащие е-иммунных множеств. Это дает ответ на вопрос из статьи [63]. В то же время показано (теорема 3.6 и следствия 3.7 и 3.8), что для любого ретрассируемого множества В существует несчетное семейство е-иммунных множеств строго выше В в отношении в.
Обозначим через I класс иммунных, БІ — класс е-иммунных, БНІ - класс е-гипериммунных множеств. Доказано, что ЕНІсЕІСІ и iTlQcEI. Кроме того, все е-степени из класса EI являются нетотальными, но, в то же время, существуют иммунные нетотальные е-степени, не принадлежащие EI. С помощью теоремы 3.9 можно построить е-иммунные множества А\ и Аг так, что е-степень de(Ai ФА2) является тотальной. Ясно, что в этом случае обязательно і4іеЛ2.
Одним из традиционных вопросов в теории сводимостей является вопрос о внутреннем строении степеней. Рассмотрим одно усиление е-сводимости, введенное Скордевым [56]: множество А рс-сводимо к В посредством частично вычислимой функции ф, если V»[ Є А = хЄ8фЛ D4( )) С В].
Будем писать А ре В, если существует ч.в.ф. ф, для которой А рс-сводится к В посредством ф. Как обычно, dpc(A) = {В : В р0 AAA рс В} - рс-степекъ множества А. Очевидно, что А ре В — А е В, поэтому произвольная е-степень состоит из некоторой совокупности рс-степеней. Если е-степень de(A) содержит более, чем одну рс-степень, то говорят, что de(A) распад аетсж на ре-степепи. Ясно, что О не распадается на рс-степени, то есть состоит из единственной рс-степени. С.Д.Захаров [18] показал, что существуют ненулевые е-степени, состоящие из единственной рс-степени. Как показано автором в [65], любая ненулевая тотальная е-степень содержит, по крайней мере, две различные рс-степени (см. также теорему 4.7 в главе IV). Поэтому, если е-степень состоит из единственной рс-степени, то она нетотальная. Как показано в теореме 3.17, это достаточное условие нетотальности е-степени не является необходимым. Оказывается, любая яехвазиминимальная е-степень, содержащая е-иммунное множество, распадается на рс-степени.
Вопрос о том, каким образом дополнительные ограничения на е-сводимость (и, вообще, на любую сводимость) "дробят" е-степени, всегда вызывает большой интерес в теории вычислимости. В частности, рс-сводммость множеств, как наиболее естественное усиление е-сводимости, является важным объектом для исследования. Обозначим через VIа(А) частично упорядоченное множество рс-степеней внутри е-степени множества А. В [59] автором доказано, что е-степени гипериммунных ретрассируемых множеств содержат счетные возрастающие цепи, а также счетные антицепи рс-степеней. В последующей работе [61] доказан более общий результат о том, что в частично упорядоченное множество рс-степеней внутри е-степени гипериммунного ретрассируемого множества А изоморфно вложим любой, не более чем счетный частичный порядок. Этот результат вытекает из теоремы 4.1, которая утверждает, что решетка вычислимо перечислимых множеств изоморфно вложима в V e(A).
Как видно из доказательства теоремы 4.1 столь "богатую" структуру множеств VIе (А) имеет благодаря гипериммунности множества А. Бели отказаться от этого условия, но сохранить тотальность dc(A)t то можно доказать теорему 4.7, из которой следует, что V C{A) содержит счетную антицепь рс-степеней.
Как уже отмечалось выше, е-степени, состоящие из единственной рс-степени, являются нетотальными. Чтобы доказать, что существуют нетотальные е-степени, содержащие более одной рс-степени, в главе IV вводится релятивизация понятия гипериммунности множеств. Пусть Е С и — произвольное множество. Как в [59] назовем бесконечное множество А Е-гипериммуннымг если условие д ,ЕлУп{ап д(п)) не выполняется ни для какой тотальной функции д, где {ап}пш - прямой пересчет множества А. Бели Е - вычислимо перечислимое множество, то Е-гипериммунное множество А является гипериммунным. В нашей терминологии, е-гипериммунное множество А — это А-гипериммунное множество. Существование 22-гипериммунных множеств для любого Е Си/ доказано с помощью теоремы 4.9, а е-гипериммунных множеств — теоремы 4.10. Из теоремы 4.12 следует, что выше любого множества В существуют несчетные возрастающие цепи е-гипериммунных множеств.
Очевидно, что для е-гипериммунных множеств верна теорема 3.5 (с заменой е-иммунности на е-гипериммунность). В то же время, как показано в теореме 4.14 под е-скачхом любого множества Е существуют е-гипериммунные множества. Более того, если Е - ретрассируемое множество, то интервал (de(E),de(3(E)))e содержит е-гипериммуяные е-степени (следствие 4.15).
Выше было отмечено, что класс БНІ е-гипериммунных множеств является частью класса HI гипериммуниых множеств, то есть БНІСНІ. Несовпадение этих классов следует, например, из того, что существуют гипериммунные множества, которые принадлежат тотальным е-степеням, в то время, как е-гипериммунные е-степени обязательно нетотальные (теорема 4.17). Кроме того, класс HI замкнут относительно подмножеств, а класс БНІ нет (теорема 4.17). В теореме 4.19 доказано, что существуют нетотальные гипериммунные е-степени, не содержащие е-гипериммунных множеств.
В теореме 3.16 показано, что неквазиминимальные е-степени, содержащие е- иммунные множества, распадаются на рс-степени. Разумеется, этот результат имеет место и для неквазиминимальных е-степеней, содержащих е-гипериммунные множества. Пусть П — счетное, частично упорядоченное множество, каждый элемент которого имеет не более конечного числа предшественников. Используя результат Сакса [54], в теореме 4.23 доказано, что существует е-гипериммунное множество Л, для которого П изоморфно вложимо в Р§е(л), а следствие 4.24 показывает, что для любого е-гипериммунного множества Ву такого, что А е В, в V ,C{A) изоморфно вложимо частично упорядоченное множество П.
В главе У (теорема 5.2) строится е-гипериммунное множество А е- степень которого a = de(A)t следовательно, нетотальна и не является f- квазиминимальной для любой тотальной е- степени f а. Пусть G — семейство тотальных е- степеней, образующих строго возрастающую последовательность, тогда, как показано в предложении 5.3, существует О- квазиминимальная е-степень а, которая не является f-квазиминимапьной для любой тотальной е-степени f а. Теорема 5.4. дает следующую характеризацию нетотальных е-степеней: любая нетотальная е-степень а является х- квазиминимальной для некоторой тоталь-- ной е-степени f а или (7-квазиминимальной для некоторого семейства тотальных е-степеней G — {g«} образующего возрастающую последовательность go gi • • • g. • • • а.
В главе V строится класс множеств, е-степени которых нетотальны. В [67] автор вводит понятие строго нетотального множества. Множество АС. и называется строго нетоталънъш, если А — не вычислимо перечислимо и Уп[Фа(Л) бесконечно — (Зд вычислимая фипкция) /и)[Од С АЛ А{х : 3t{(x,g{i)) Є Wn)} бескопечпо)).
Пусть SNT — класс строго нетотальных множеств. В теореме 5.12 доказано, что класс SNT имеет несчетную мощность, SNTc Q и SNTnI= 0.
Глава VI посвящена доказательству недистрибутивности операций U и частичной операции П в [с,с/]е С этой целью доказана теорема 6.6, которая утверждает, что в любой отрезок [с, d\e может быть изоморфно вложена недистрибутивная пятиэлементная решетка с наименьшим элементом сие- ква-зиминимальными остальными элементами. Ранее, в статье [41] было доказано, что любая решетка, вложенная в низкие вычислимо перечислимые Т-степени, может быть вложена в 2) -ле-. Отсюда следует, что результат Лахлана [36] о вложении недистрибутивной пятиэлементной решетки в низкие вычислимо перечислимые Т-степени дает вложение такой решетки в ї) - - -.
В теореме 6.1 доказано, что операции Пии "локально9 дистрибутивны, то есть в Ve вложимы конечные полурешетки, удовлетворяющие условию а=ЬПсЛаі а— &i = (aiUb)n(aiUc) и двойственному ему a=bUcAai а— &i = (аіПЬ)и(аіПс). Из теоремы 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 наименований.
Соотношения между Тьюринговыми степенями и степенями перечислимости
Исследуем вопрос о соотношениях по включению между de(A) и dr(A). Основная часть результатов в этом направлении опубликована в [66]. Из определений е-сводимости и Т-сводимости очевидно следует, что dr(R) С е(0), где R — некоторое вычислимое множество. Заметим кстати, что dr(R) состоит из всех вычислимых множеств, a Ze(0) состоит из всех вычислимо перечислимых множеств. Докажем сначала, что любая тотальная е-степень не содержится как подмножество ни в какой Т-степени. Напомним, что бесконечное множество А называется ретрассирусмым, если существует частично вычислимая функция фу такая, что А С 8ф, ф(ао) = ао и ф(ап) = an-i для всех п 0, где {&п}пъы - прямой пересчет множества А. Таорема 1.2.1. Для любого множестве А Доказательство. Так как de(AoA) - тотальная е-степень, то можно без потери общности считать, что А — ретрассируемой множество (см. Предложение 2.9 в [21]). Заметим, что в этом случае А е А. Обозначим через В = {х : х Є ФЯ(А)}. Как показано в Теореме 1.1.19(і), В =е А, а в Лемме 1.1.22, В е А. Допустим, что В =т А тогда В ф В =е А Ф А =е А. В частности, В ф В е А, откуда следует, что В е А, что противоречит выбору множества В. Таким образом, В Є de(A) = de(A ф А) и В $ dx{A) = dx{A ф А), то есть de(A ф А) 2 rfT(A Ф Л). Заметим, что если предположить, что de(A ф А) С с(г(С) для некоторого множества С, то А ф А =т С и (г(С) = /т(Л ф Л), и мы возвращаемся к ситуации, рассмотренной в Теореме 1.2.1. Следствие 1.2.2. Если е-степень содержится в некоторой Т-степеми, то ояа нетотальная. Следствие 1.2.3. Внутри каждой Т-стенени 0 содержится нетотальная е-стеяеяь. Доказательство. В статье [75] показано, что внутри каждой Т-степени 0 содержится некоторая е-степень. По следствию 1.2.2 такая е-степень должна быть нетотальной. Прежде чем перейти к следующему вопросу отметим, что существуют тотальные pm-стелени, содержащиеся в Т-степенях целиком. Сначала напомним определение частичной т-сводимости множеств, введенной Ю.Л. Ершовым (см., например, в [16] стр. 237): Определение 1.2.4. Множество А рт-сводится к В (обозначание: А рт В)у если существует частичная вычислимая функция ф, такая, что А С іф и для всех х Є іф х Є А = ф(х) Є В. Как обычно, рт-степеиь множества А — класе dpm(A) = {В : В рт AAA рт В}. Пусть Арт — {х : фя(х) J. Лфя(х) єА}пК = {х:хЄ We}, тогда, очевидно, Rpm Щт R- Так как для любых множеств Am В то В Є dpm R) — R т, В т Rpm для любого множества В. Кроме того, Rpm т R поэтому dpmiR) С dT(R). Ясно, что К Ф R щт R и dpm(R) -тотальная рш-степень. По Теореме 1.2.1, однако, de(R) % dr(R). Вернемся вновь к Следствию 1.2.2. Возникает естественный вопрос — существуют ли нетотальные е-степени, не содержащиеся ни в какой Т-степени? Дадим на этот вопрос утвердительный ответ, но сначала напомним определение простого множества и докажем лемму. Вычислимо перечислимое множество Р называется простым если его дополнение Р бесконечно, и Р Л W ф 0 для любого бесконечного вычислимо перечислимого множества W. Лемма 1.2.5. Пусть Р — простое множество, тогда существует квазиминимальная е-сгелеиь de(A), такая, что Р еАА. Доказательство. Построим по шагам множества А, удовлетворяющее следующим требованиям: Обозначим через An — часть множества А, построенную к концу шага п. В ходе конструкции будет также построено вспомогательное множество Zt в которое будут зачисляться числа, не могущие попасть в Л; через Zn обозначим часть Z, построенную к концу шага п. Конструкция организована таким образом, что Ап и Zn - конечные множества, Ап С Лп+і, Zn С п+ь -An П m = 0 для всех m,n Є и.
Пусть с» = тах(Ап U Zn), A = Un« »» Urte« Zn Ясно, что А П Z = 0. После выполнения всех действий, предписанных на данном шаге, переходим к следующему шагу. Символ D будем использовать как переменную для конечных множеств. Шаг 0. ПолагаемAO = ZO = 0HCO = O. Шаг Зп+1. Проверим выполнимость условия Если условие (1) выполнено, то обозначим через z наименьшее z, удовлетворяющее (1). Полагаем Zsn+i ZSn U { } и Л3п+і = Лзп. Бели условие (1) не выполнено, то Wn С Азп- В этом случае полагаем Zan+i — %зп и Азп+і = Азп U {can + 1}. Шаг Зп+2. Проверим выполнимость условия Если условие (2) выполнено, то обозначим через D конечное множество с наименьшим каноническим индексом, удовлетворяющее (2). Полагаем Zsn+2 = Zzn+i и Asn+2 = Авп+і U D . Если условие (2) не выполнено, то полагаем Zsn+2 = Zsn+l И Азп+2 — Азп+1 Если условие (3) выполнено, то обозначим через 27 конечное множество с наименьшим каноническим индексом, удовлетворяющее (3). Полагаем Zsn+з — Zsn+г и - Зтг+з — Азп+2 U D . Если условие (3) не выполнено, то полагаем 8п+2 = %9п+1 И Лзп+2 = -Авл+1
Цепи и антицепи С-квазиминимальных множеств
Следующая теорема представляет собой релятивизированный вариант теоремы МакИвоя из [40], в которой термин квазиминимальная е-степень" заменен на "с-квазиминимальная е-степень", где с - произвольная е-степень. Как уже отмечалось 1, прямая релятивизация вида aUc, где а является квазиминимальной е-степенью, не дает результата, так как не обязательно aU с является с- квазиминимальной е-степенью, а также равенство (aUc) =bUc для а =Ъ выполнено для любых е-степеней а и с. Теорема 2.2.1. Пусть с - произвольная е- степень, тогда для любой тотальной е-степени Ь с существует с-квазиминимальиая е-степень а, такая, что а =Ь. Доказательство. Пусть С Є с и В Є Ъ, такое, что В =в св Воспользуемся конструкцией из доказательства теоремы МакЗвоя, чтобы построить с-квазиминимальную е-степень а = Ъ. Обозначим через D переменную, значениями которой являются конечные множества. Будем писать F Ср D, если F С D A max F min D\F или F = 0 Л D ф 0. Построим по шагам последовательность конечных множеств Fo F±,..., F„..., такую, что Ft Ср Ft+i для всех Є w. Обозначим через А — С ф U#gw F» и а== е(Л). Шаг 0. Полагаем F0 = 0. Шаг 4з+1. Пусть zu — 1 + max F4», проверим выполнимость условия Если (1) выполнено, то полагаем і 4«+і — F4»U{z4»+l}} и если (1) не выполнено, то полагаем i 4 +i = F4$U{z4»}. Так как Ф (С) е-сводится к С7, то c ,(cr) еЗ(С) и проверка (1) эффективна относительно произвольного пересчета 3(C). Шаг 4з+2. Проверим Если (2) выполнено, то полагаем -F-u+2 = -D где D удовлетворяет (2) и .» имеет наименьший канонический индекс. Бели (2) не- выполнено, то полагаем Рассмотри множество Ясно, что Vi е С, поэтому проверка условия (2) состоит в решении проблемы "( , Fii+i) Є Vi?" и поэтому эффективна относительно J (С). Шаг 4 +3. Проверим Бели (3) выполнено, то полагаем Fu+я = D , где D имеет наименьший канонический индекс среди D ф 4«+2 удовлетворяющих (3). Если (3) не выполнено, то полагаем /4,+8 = - 4«+2 Заметим, что и в этом случае для проверки условия (3) необходимо знать ответ на вопрос w(#, F +z) Є V , где Ясно, что VJS e О и поэтому ответ на этот вопрос можно получить эффективно относительно произвольного пересчета 3(C). Шаг 4 +4 Пусть 4«+з = 1 + max.F4«+3 полагаем /4,+4 = /4,+3 U { 4«+з} еСЛИ $ Є В И F4«+4 = -Р4«+3 U { 4«+3 + 1} в03 В. Конец конструкции. Из описания конструкции следует, что шаги 4 +1, 4«+ 2, в Є w делают множество Л С-квазиминимальным, а шаги 4 4-3, 4 4-4, в Є w дают J(A) =e 2?. Кроме того, шаги 4 + 1, іЄи обеспечивают А ф & {G) для всех Є w, то есть, что А е С. Из построения видно, что V«( Є С = 2а? + 1 Є А), то есть С е А и поэтому С7 е А. Теорема доказана. Следствие 2.2.2. Дня любого С С а существует С-квазиминимальное множество А, такое, что A еЗ(С) и 3(A) =в 3(C). Доказательство. Возьмем в Теореме 2.2.1 в качестве Ъ е-степень с , тогда построенная с-квазиминимальная е-степень а будет удовлетворять равенству а = Ъ = с , поэтому а с/. Следствие 2.2.3. Для любой е-степени c=de(C) и любой тотальной е-степенн Ъ с существует счетная возрастающая последовательность С- квазимннн-мальных множеств Ао в А\ е е Ап е ..., таких, что 3(АП) =е
В, где В Є Ъ, для всех пбо;. Доказательство. Пусть Ао - (7-квазиминимальное множество, построенное в ходе доказательства теоремы 2.2.1, то есть Ао е В и 3(Ао) =е В (на шагах As 4- 1, 4 + 2 и 4 + 3, 6w построение Ло вычислимо в J(C7), а на шагах 4« 4- 4, в Ею вычислимо в В и В =е сд). Повторим конструкцию, заменяя 7 на AQ для Ъ = de(J(-Ao)) = а0. В результате получим Ло-квазиминимальное множество A\t такое, что 3(Ai) =е В. Заметим» что так как 3(C) с В} то все шаги этого построения вычислимы в.В. Так как AQ - С-квазиминимальное множество, то Лі - также С7-квазиминимальное множество и С е AQ е А\ е В. Далее повторим ту же конструкцию, заменяя С на А\ для b=rfe(J(-4i))=ai и получим С-квазиминимальное множество A%t такое, что Ai в Аъ е В и 3(А2) = Вн т.д. Следствие 2.2.4. Дм любого С С ш существует счетная возрастающая последовательность С-квазиминимальных множеств AQ е At е е -Ап е ..., таких, что С в Лп е J(C7) для всех п Є tj. Доказательстло. Возьмем в следствии 2.2.3 В =е J (С), тогда построенная счетная возрастающая последовательность С-квазиминимальных множеств С е Ао е АІ. е -" е An е ... обладает требуемыми свойствами: С е An е 3(Ап) =е В =е 3(G) для всех пбы. Следствие 2.2.4, в частности, показывает, что интервал (с, с )в содержит счетную возрастающую цепь с- квазиминимальных е-стеленей. Этот результат вытекает из Теоремы 2.3.1 (см. 3), которая утверждает, что если с а и а Є Tt то в частично упорядоченное множество Qc( а) с- квазиминимальных е-степеней а изоморфно вложимо любое, не более чем счетное частично упорядоченное множество. В частности, Qc( с ) содержит строго возрастающую последовательность, упорядоченную по типу натуральных чисел, а также упорядоченную и по типу целых чисел: а_2 a_i ao ai "« a« .... Бели говорить о Vt целиком, то такие линейно упорядоченные множества могут быть несчетными, при этом любой начальный сегмент не более чем счетен. Теорема 2.2.5. Для любого С С и существует несчетная линейно упорядоченная совокупность С-квазиминимальных множеств. Докажем сначала две леммы, которые будем использовать в дальнейшем. Лемма 2.2.в. Пусть MQ qeMi е е М, е ... — строго возрастающая последовательность С-квазиминимальных множеств, тогда существует такое С-квазиминимальное множество А, что М, е А для любого S Є ш. Доказательстло. Чтобы получить множество At построим по шагам последовательность множеств {Л,},ео/ в которой А, С At+i для всех в Є w. Пусть D и F - переменные для конечных множеств и Mt — {( ,«) : х Є Мв}, N, = {(п, х) : п в Л п, х Є w} для всех $ Є ш. Шаг 0. Полагаем AQ = MQ. Шаг a+1. Предположим, что А, построено на шаге s. Проверим выполнимость условия Бели (1) выполнено, то полагаем -4,+1 = A, U M#+i U JD , где D - конечное множество с наименьшим каноническим индексом, удовлетворяющее (1). Если (1) не выполнено, то имеет место Полагаем A,+i = A, U M +i. Пусть А = и#Єа Л4. Докажем ряд утверждений, из которых будет следовать, что АСи обладает требуемыми свойствами. V. А, - С-клазиминимальпое множество для всех л Є о;. В самом деле, А, — U»o » и » где - " некоторое конечное множество. Так как МІ =е Af,- и М,- е Af» для всех t в, то А, =в Л/, и Л» является С-квазиминимальным вместе с М, для всех « Є CJ. 2. Af« в А для всех ш. Возьмем произвольный пересчет множества А и выделим из него все элементы вида («, х). Множество М = {а?: {«, ж) Є А} отличается от М# самое большее на конечное множество, которое добавлено к М на шагах і, где і в случае, когда условие (1) выполнено. Поэтому М, е М е А Предположим, что А» е Af, для некоторого в Є о;, тогда, например, Af +i е А е Af», что противоречит нашему выбору последовательности {M,},gw. З0. А - С-кваз%м н малъное множество. Пусть / е А для некоторой тотальной функции /, то есть г/ = Ф,(А) для некоторого $ Є ш. Рассмотрим шаг + 1 и покажем, что на этом шаге не выполняется условие (1). Предположим, что (1) выполнено, тогда Фв(А, U D) неоднозначно для некоторого конечного множества D С N, н D , которое выбрано в этом случае, будет подмножеством А и, следовательно, Ф»{А) также неоднозначное множество, что противоречит первоначальному предположению. Теперь проверим, что Ф»(А, UNt) однозначное множество. Предположим, что это неверно, тогда Ф#(-0) не является однозначным для некоторого конечного D С Ал U N, и условие (1) должно быть удовлетворено, что невозможно по нашему предположению. Следовательно, Ф»(А, UN,)- однозначное множество. Мы имеем, г/ = Ф»(А) С Ф,(Ав U N,) н f : ш — и - тотальная функция. Поэтому, г/ = Ф»(А, U N,) и т/ е A, U JV", в Ал. Используя 1, мы получаем, что f е Си, следовательно, А - С-квазиминимальное множество, что и требовалось доказать. Лемма 2.2.7. Пусть М — произвольное О-квазиминнмальное множество, тогда существует С-квазямннимальное множество Q, такое, что М „ Q. Доказательство. Обозначим через Q, часть множества Q, построенную на шаге
Дополняемость в Qc до с-минимальной пары
Определение 2.4.1. е-степени а и b образуют с-минжмальную пару, если с а, с Ьис = аПЪ. В этом случае будем говорить,что с - летвящажся е-стелень. Бели с = 0е, то е-степени а и Ъ образуют минимальную пару е-степеней. Впервые минимальные пары были построены в [21]. В статье [41] построена минимальная пара ниже О". В [52] показано, что любая е-степень с является ветвящейся в Т. Теорема 2.4.2. Для любой е-стелевя с существует пара с-квазиминимальных е-степеией аяЬ, таких, что с = а П Ь, Другими словами, любая е-стелень с является ветвящейся в Qc Доказательство. Так как любая е-стелень с ветвится в 7", то есть что для любой е-степени с существуют тотальные е-степени d с и е с, такие, что с = dfle. Из теоремы 2.3.2 следует, в частности, что в этом случае существуют с-квазиминимальные е-степени а d и b е. Очевидно, что с = а П Ь. В самом деле, пусть х а и х Ь, тогда х d и х е, поэтому х с. Теорема 2.4.3. Для любой е-степеии с и любой тотальной е-степени е с" существует пара с-квазиминимальных е-степеней а я Ъ, такая, что а П Ъ = с я Доказательство. Пусть С Є с и Е Є е, причем Е =е тсв Обозначим через D, D(0\D(l) переменные для конечных множеств. В конструкции будем использовать обозначения из доказательства теоремы 2.2.1. Построим С-квазиминимальные множества А и 2?, удовлетворяющие требованиям: Для этого определим в ходе конструкции две последовательности конечных множеств JF o Ср Fiti Ср - Ср F{t, Ср ..., » Є {О,1}, так, чтобы множества А = С ф U«gw Но,» я В — С ф U#Pw 1 УДовлетвоРили вышеуказанным требованиям, а их е-степени a = de(A) и b = de(B) условию теоремы. Пусть .\» = 1 +max Pi,,. Шаг 0. Полагаем Fito = 0 и zija = 0 для Є {0,1}. Шаг $9+1. Проверим выполнимость условий для » Є {0,1} Бели (l.i) выполнено, то полагаем если (l.i) не выполнено, то полагаем Если (2.1) выполнено, то полагаем -Ft,e«+2 = D y где D имеет наименьший канонический индекс среди D, удовлетворяющих (2.і). Если (2.і) не выполнено, то полагаем Fi,e,+2 — Fite,+i. Шаг 6s+3. Пусть $ — (fc, /), проверим Если (3) выполнено, то пусть JD(0) И DW имеют наименьшие канонические индексы среди І3() и D t соответственно, удовлетворяющих (3).
Полагаем Fi,e»+& = D для всех і Є {0,1}. Если (3) не выполнено, то полагаем Fite»+s = Fitee+2 для всех » Є {0,1}. Шаг 6з+4- Пусть » = (/, ж), проверим Если (4) выполнено, то пусть D имеет наименьший канонический индекс среди J9, удовлетворяющих (4). Полагаем і о,в«+4 = -Fo,e +s и 1,в#+4 = -D - Если (4) не выполнено, то полагаем l »,e +4 = -Fi.e.+a для всех Є {0,1}. Шаг 6з+5. Проверим для каждого і Є {0,1} Если (5.І) выполнено то полагаем Рш,в»+Б — D , где D имеет наименьший канонический индекс среди Dt удовлетворяющих (5.І). В противном случае полагаем Fi e,+e = -F ,e#+4. Шаг 6в+6. Полагаем для каждого Є {0,1}, если в Є Е Описание конструкции закончено. Шаги 6« + 1 и 6« + 2, в Є со, обеспечи вают С-квазиминимальность множеств А та В. Докажем, что для всех Jfc, ІЄ и удовлетворено требование МРк,і. Предположим, что Фк{А) = Фі(В). Пусть «=(, 7), докажем, что в этом случае ... .. „.... Фк(А) = {х : 3DW{F0,e.+ Ср D Ах Є Фк(Сф Я(0 ))}. Обозначим через Очевидно, Ф (Л) С G. Докажем обратное включение. Пусть х и Х () такие, что х Є Ф (С ф JD J) И .Fo,e#+8 Ср І3(0). В этом случае должно выполняться условие так как, в противном случае, шаг 6« + 3 даст неравенство Ф&(Л) Фі(В), что противоречит предположению. Поэтому на шаге бе + 4, где в = (7, ж), будет обеспечено, чтобы х Є Ф (-А) = Фі(-В), то есть G С Фк(А). Итак, G = Фк(А) = Фі(В). Из определения множества G следует, что G е С, я требование MPkj удовлетворено. Так как проверка условия (3) вычислима в с" на каждом шаге, поэтому вся конструкция вычислима в е с". Шаги 6 + 5 и 6 + 6, «« обеспечивают выполнимость требований JA и JB. Теорема доказана.
Гипериммунные множества
Пусть {an}n6fa) — прямой пересчет бесконечного ретрассируемого множества А, тогда существует частичная вычислимая функция ф} такая, что А С 8ф, ф(ао) = ао и (Vn 0)(ф(ап) — ол_і). Легко понять, что если В — бесконечное подмножество ретрассируемого множества А, то А е В. Реализуя идею построения вычислимо перечислимого множества, не являющегося Т-полным, Пост определил класс гиперпростых множеств, как совокупность в. п. множеств с гипериммунными дополнениями. Как выяснилось позже, гиперпростые множества не дали решение проблемы Поста, но понятие гипериммунного множества позволило получить значительную информацию о структуре е-степеней гипериммунных множеств. Напомним, что множество А называется гжпериммунхыМу если ни для какой вычислимой функции /(п) не выполняется V"(on /(")) Другими словами, А — гипериммунно, если никакая вычислимая функция не мажорирует прямой пересчет множества А. В статье автора [59] рассмотрены е-степени гипериммунных ретрассируе-мых множеств. Доказано, что е-степени гипериммунных ретрассируемых множеств содержат счетные возрастающие цепи, а также счетные антицепи рс-степеней. В последующей работе [61] доказан более общий результат о том, что в частично упорядоченное множество рс-степеней внутри е-степени гипериммунного ретрассируемого множество изоморфно вложим любой, не более чем счетный частичный порядок. Этот результат вытекает из следующей теоремы. Напомним, что через Т С(А) мы обозначаем частично упорядоченное множество рс-степеней внутри е-степени множества А. Пусть Зі - решетка в.п. множеств, тогда Теорема 4.1. ЕСЛИ А — гипериммунное ретрассируемое множество, то решетка. Ж изоморфно вложима в V?C(A). Доказательство. Пусть А — гипериммунное ретрассируемое множество, {вп}пбо» прямой пересчет А. Построим множества AotAi)...iAny... так, чтобы Ал =е А для всех п Є w и А,- е Aj - =Ф- Wi С Wj для всех ф j. Рассмотрим список натурального ряда и и меток /»(&), » ф к и а, к Є ш. Через с(і,к) обозначим номер метки 7t-(Jb) в эффективной нумерации всех пар (г, у), в которых х ф у. Метка /;(Jb) может находится только около чисел из своей траектории Li(k) = {( ,ktm) : т 1}. Обозначим через Ni = {(і,хуу) : х%у Є a;}, Si = ш \ Ni, і Є ш. В ходе конструкции около чисел из списка натурального ряда будем ставить знаки (+) или (-), при этом ни один знак не будет изменяться на другой, и все В этом случае метка 7,() ставит (+), поставим (+) около всех остальных чисел множества L\(k). Метка U(k) индуцирует (-) около чисел из множества Все метки с номерами, большими c(t, к), которым соотнесены числа с индуцированными (-), сдвинем по их траекториям на ближайшие свободные числа и скажем, что метка U(k) ударила эти метки. Если метку, имеющую ( ) ударяет другая метка, то ( ) сохраняется. Метку h(k) закрываем, и если она имела ( ), то ( ) снимаем.
Переходим к подшагу у. Бели метка /;(&) отмечена ( ), то переходим к подшагу у. Бели метка Іі(к) не отмечена ( ), то метка U(k) ставит (-) и сдвигается по своей траектории на ближайшее свободное число. Метка /»(к) получает ( ), и переходим к подшагу 7 Подшаг у. Все незакрытые метки /»(&) к, (і, к, t(», к)) , не сдвинутые на подшаге /?, ставят (+) и сдвигаются на ближайшие свободные числа своих траекторий. Подшаг S. Рассматриваем все метки, имеющие ( ). Их конечное число, так как на каждом шаге конструкции появляется не более одной метки, имеющей ( ). Пусть метка U(k) получила ( ) на шаге і і I, тогда явиться (+) или (-). Если все числа множества -D fc ((», , «(», ))) стали несвобод ными, то удаляем ( ) с метки h(k). Если все числа множества - ь((», ,#«( , ))) имеют при этом (+), то метку к(к) закрываем и ставим (+) около всех чисел множества L\(k). Если при этом появляется возможность снять ( ) с других меток, то повторяем подшаг & еще раз. Описание конструкции закончено. Докажем четыре леммы, из которых будет следовать теорема. Лемма 4.2. Ап =е А для всех п Єю. Доказательство леммы 4.2. Так как множество А ретрассируемо, то из любого пересчета множества А можно эффективно получить прямой пересчет А. Действительно, пусть ч.в.ф. ф(х) регрессирует множество Л, тогда для любого х Є А последовательность чисел ж, ф(г),..., фк{х)і где А? Є о; таково, что 0 +1(ж) = фк(х), состоит из первых к + 1-го элемента множества Л, расположенных в порядке убывания. На всех шагах конструкции выполняются операции, рекурсивные относительно прямого пересчета множества А, то есть ВІ е А для всех t Є ш. Очевидно, что в этом случае U»ew - - » е Л. Покажем, что A i Ап для всех т» Є о». Пусть Wn — 0, тогда Ап = А и, тривиально, A i An. Пусть теперь Wn ф 0, тогда существует і о Є Wn и ВІ0 С Лп. Пусть jo Ф i o, по построению Таким образом, в этом случае Л i Ап посредством вычислимой функции /(г) = 0 о» г ) и лемма доказана. Лемма 4.3. Пусть R — вычислимо перечислимое множество и {гп}Пш некоторое эффективное перечисление R, возможно, с повторениями. Тогда, если для некоторой ч.в.ф. фк{х) значение фк{ п) ие вычисляется за an шагов для всех п Є ш, то существует число г Є R, такое, что фк(т) ие определено. Доказательство леммы j.S. Предположим, что значения фк(г) определены для всех г Є R. Рассмотрим функцию Функция An.m (n) является вычислимой и mfc(n) ап для всех пби, что противоречит гипериммунности множества А. Лемма 4.4. СІ ре. ВІ ДЛЯ всех і Є о». Доказательство леммы 4-4- С помощью индукции по c(i,k) докажем следующие утверждения: а). С{ рс ВІ посредством ч.в.ф. фк{х)\ Ь). Существует шаг о, такой, что все числа множества L\{k) получат только (+); с). Метка їі(к) имеет ( ) лишь на конечном числе шагов. Докажем утверждения а), Ъ), с) для с(», к) = 0. Бели метка 1{(к) закрыта на подшаге /? шага о то имел место один из случаев (1), (2) или (3). Во всех этих случаях фк(( к} t0(», к))) определено и (, ,# .( . ) Є С ««= ь«ьМ«оСь ) ) 2 ВІ. ВІ. При этом Ц(к) содержит только числа, имеющие (+), а метка U(k) не получает ( ). Таким образом, выполнены утверждения Ь) и с).
