Содержание к диссертации
Введение
1 Д-спектры линейных порядков 9
1.1 Д -спектр 9
1.2 Линейные порядки, сильно похожие на TJ 15
1.3 Квазидискретные линейные порядки 21
2 Вычислимые алгебры Ершова 26
2.1 2-низкие алгебры Ершова 26
2.2 3-низкие алгебры Ершова 35
3 Класс вычислимых множеств 40
3.1 Теоретико-множественная структура 40
3.2 Теоретико-множественные сводимости 51
3.3 SET-1-сводимость на классе вычислимых множеств 68
Литература 77
- Линейные порядки, сильно похожие на TJ
- 3-низкие алгебры Ершова
- Теоретико-множественные сводимости
- SET-1-сводимость на классе вычислимых множеств
Введение к работе
Одной из важных задач в теории алгоритмов является изучение алгоритмической сложности различных счетных алгебраических структур на основе построения эффективных представлений этих структур на множестве натуральных чисел. В данной работе мы исследуем такие алгебраические структуры, как линейные порядки и алгебры Ершова.
Исследования в этой области были начаты Л. Фейнером в конце 1960-х и продолжены в работах Дж. Реммела, С.С. Гончарова, Дж. Найт, К. Эша и других. В частности, было показано, что существуют вычислимо перечислимые булева алгебра и линейный порядок, не имеющие вычислимые изоморфные копии (см. [1] и [2]), другими словами, являющиеся неконструк-тивизируемыми.
В последние года активно изучаются такие вопросы, как описание спектра счетных алгебраических структур. Например, Т. Сламан (см. [3]) и С. Вей-нер (см. [4]) независимо друг от друга построили такую счетную структуру А, что Spec(A) — D — {0}, где D — класс всех тьюринговых степеней. Р. Миллер в [5] доказал, что существует такой линейный порядок L, что Spec(L) П А° = А° — {0}. С. Гончаров, В. Харизанов, Дж. Найт, К. МакКой, Р. Миллер и Р. Соломон в [6] построили для любого п € ш такую структуру An, что Spec(An) = D — Ln, где Ln — класс всех п-низких степеней.
В этой работе мы докажем, что для любого п Є ш существует такой линейный порядок Сп, что Spec(Cn) П Д° = А° — Ln.
В [7] Р. Доуни и М. Мозес показали, что любой дискретный линейный порядок низкой степени имеет вычислимую копию. Мы обобщим этот результат, доказав, что каждый 2-низкий квазидискретный (и, следовательно, дискретный) линейный порядок изоморфен вычислимому порядку. Причем, покажем, что для 3-низких квазидискретных порядков этот результат не верен.
Также Р. Доуни спросил, какие еще существуют свойства линейных порядков Р, что для любого низкого линейного порядка L из P{L) следует существование вычислимой копии. В этом направлении мы докажем, что каждый низкий линейный порядок, "сильно похожий" на rj, изоморфен вычислимому порядку (причем для 2-низких это не верно).
Отечественными и зарубежными учеными активно исследуется также вопрос о та-низких булевых алгебрах и алгебрах Ершова. В [1] Л. Фейнер построил вычислимо перечислимую булеву алгебру, не изоморфную никакой вычислимой алгебре. Построенная им булева алгебра не изоморфна никакой п-низкой алгебре, ни для какого натурального п. Естественно возникает вопрос: каждая ли та-низкая (для любого та Є о») булева алгебра имеет вычислимую копию? Постановку этого вопроса можно найти, например, в [8].
В общем случае ответ на этот вопрос пока неизвестен, известны частичные ответы. В [9] Р. Доуни и К. Джокуш доказали, что каждая низкая булева алгебра изоморфна вычислимой алгебре. В [8] Дж. Найт и М. Стоб доказали, что любая 4-низкая булева алгебра имеет вычислимую копию. В этой работе мы покажем, что каждая 3-низкая алгебра Ершова изоморфна вычислимой алгебре.
В теории вычислимости особое место занимают исследования теоретико-множественных свойств различных структур, особенно теоретико-множественные свойства класса вычислимо перечислимых множеств относительно вычислимых множеств.
В третьей главе данной работы изучается теоретико-множественная структура класса вычислимых множеств относительно полиномиально вычислимых и примитивно рекурсивных. В этой главе вводится классификация вычислимых множеств и доказывается, что каждый класс введенной классификации не пуст.
В третьей главе вводятся и изучаются две так называемые теоретико-множественные сводимости. Доказаны теоремы о нормальной форме для каждой сводимости, критерии минимальности и плотности. Используя кри терий плотности, на классе вычислимых множеств доказано, что первая введенная теоретико-множественная сводимость порождает плотный частичный порядок.
При доказательстве теорем диссертации использовались методы конечных расширений, приоритета с конечными нарушениями (метод 0 -приоритета), приоритета с бесконечными нарушениями (метод 0"-приоритета). Например, теоремы 3.1.5, 3.3.11 доказывались методом конечных расширений, теорема 2.1.2 — методом приоритета с конечными нарушениями, а теорема 1.2.3 — методом приоритета с бесконечными нарушениями.
Содержание диссертации представлено в собственных публикациях автора [11] — [24]. Результаты, изложенные в данной работе, докладывались на международных конференциях "Logic Colloquium 2001" (Вена, Австрия, август 2001 г.), "Logic Colloquium 2002" (Мюнстер, Германия, август 2002 г.), "Колмогоров и современная математика" (Москва, апрель 2003 г.), "Logic Colloquium 2003" (Хельсинки, Финляндия, август 2003 г.), "Мальцевские чтения" (Новосибирск, 2003 г.), "Logic Colloquium 2004" (Турин, Италия, июль 2004 г.), а также на научных семинарах по математической логике в Казанском государственном университете.
Автор выражает глубокую признательность своему научному руководителю профессору Арсланову Марату Мирзаевичу за постановку задач, интерес к исследованиям автора и поддержку в работе.
В изложении теории вычислимости (теории алгоритмов) мы следуем в основном [10], в изложении теории счетных булевых алгебр, алгебр Ершова и линейных порядков — [25].
Ниже содержатся основные определения и обозначения, необходимые для дальнейшего изложения.
Обозначения и терминология.
Теория вычислимости. Через ш обозначается множество всех натуральных чисел с 0.
Функция (ж, у) = (ж2 + 2ху + у2 + Зж + у)/2 — стандартная вычислимая биекция из и • ш в ш.
Теоретико-множественную разность множеств X С ш и Y С ш будем обозначать через X—Y; дополнение множества ICw — через X = #„ и —Х.
Мы будем иногда отождествлять множество А С ш с его характеристической функцией Г 1, если ж Є А, Хл(х) = (О, в противном случае, так что запись А(х) — 1 означает, что ж Є А, а А(х) = 0 эквивалентно х . А.
Запись X = Y означает, что симметрическая разность (X — Y)\J(Y — X) конечна.
Будем писать А С В, если А— В конечно. Пишем А С» В, если А С. В и В% А.
Тьюринговые степени будем обозначать жирными строчными латинскими буквами a, b, ..., тьюринговую степень множества А обозначаем через deg(A).
Если / — некоторая функция, то dom(f) — область ее определения, rang(f) — область ее значений, graph(f) — график функции /: graph(f) = {(ж,у) \у = /(ж)}.
Если последовательность функций f3:u — u поточечно сходится к функции /, то будем писать / = 1ітя f„.
Функция называется примитивно рекурсивной, если она принадлежит наименьшему классу, содержащему функции 0(х) = 0, s(x) = #„ ж + 1, /(жі,... ,жп) =dfn хт и замкнутому относительно суперпозиции и примитивной рекурсии.
Функция называется вычислимой (частично вычислимой), если существует машина Тьюринга, вычисляющая эту функцию.
Функция называется полиномиально вычислимой, если она вычислима на машине Тьюринга за количество шагов, ограниченное некоторым наперед заданным полиномом.
Множество называется полиномиально вычислимым, примитивно рекурсивным, вычислимым, если его характеристическая функция является полиномиально вычислимой, примитивно рекурсивной или вычислимой, соответственно.
Множество называется вычислимо перечислимым, если оно является областью определения некоторой частично вычислимой функции.
Фе — одноместная частично вычислимая функция, вычислимая на машине Тьюринга с оракулом А с гёделевым номером є Є ш.
Для каждого е полагаем Wf —dfn іот(ф).
Оператором скачка множества А является А — {є є Є W }. По индукции можем определить та-ый скачек множества А: А п+1 = (А ) .
Для п Є ш множество А т 0 называется га-низким (или п-высоким), если А т 0 (или 0(п+1) т А , соответственно). Тьюринговая степень а называется га -низкой или та-высокой, если некоторое множество А Є а является n-низким или п-высоким, соответственно. 1-низкое (1-высокое) множество или степень называется просто низким (высоким, соответственно).
Булевы алгебры, алгебры Ершова, линейные порядки и их тью-ринговы степени.
Алгеброй Ершова называется дистрибутивная решетка с относительными дополнениями, имеющая наименьший элемент. Булевой алгеброй называется дистрибутивная решетка с относительными дополнениями, имеющая наименьший и наибольшие элементы.
Идеалом Фреше булевой алгебры V называется идеал Р{Т ) = {а Є V \ Заі,..., ап, где щ — атом или нуль, 1 і га}.
Под понятием решетки множеств понимается класс множеств V С V(w) — {А А С о»}, замкнутый относительно операций объединения и пересечения (то есть AUB, АП В Є Х для любых множеств А, В Є Т ).
Решеткой множеств с наименьшим (с наибольшим) элементом назовем решетку множеств Т , если 0 Є Т (или и Є Т , соответственно).
Под алгеброй множеств понимается решетка множеств с наименьшим и наибольшим элементами, замкнутая относительно операции теоретико-множественной разности (то есть А — В Є Т для любых А, В € Т ).
Автоморфизмом алгебры множеств Л называется такая биекция р : А — Л, что для любых А,В Є A p(A)U p(B) = p(A(jB) и р(А)Гнр(В) = ц (АГ\В).
Степень структуры В, обозначается deg(B), — это тьюринговая степень ее атомной диаграммы, закодированной геделевскои нумерацией как подмножество ш. Если сигнатура структуры В конечна, то тьюринговой степенью В является deg(#) = deg(jB) V (V?=0deg(/;)) V (Vodeg(P0), где \B\ — основное множество, {fi}i n и {Pi}i m — все функции и предикаты сигнатуры структуры В, соответственно.
Мы рассматриваем только счетные структуры, основным множеством которых является ш.
Спектром структуры А называется класс Spec(A) = {deg(B) В = А}.
Если С — некоторый класс степеней, то С-спектром называется класс Specc(A) = СП Spec(A).
Мы будем рассматривать только Д°-спектры счетных линейных порядков, то есть С = Дз — класс всех таких степеней а, что а т О , где О — степень вычислимых множеств.
Мы будем говорить, что структура А вычислима (n-низкой степени или га-высокой степени), если его степень deg(.4) вычислима (п-низкая или п-высокая, соответственно).
Линейные порядки, сильно похожие на TJ
Определение 1.2.1 Назовем линейный порядок L к-блочным порядком, если для любых х и у из F(x,y) следует \[х,у]\ к + 1. Определение 1.2.2 Линейный порядок называется сильно похожим на п (strongly п -like), если он является к -блочным для некоторого к Є ш. Легко видеть, что для любого к Є ш, во-первых, любой к -блочный линейный порядок является к+1 -блочным и, во-вторых, существуют к+1 -блочные, но не fc-блочные порядки. Также очевидно, что 0-блочными порядками являются только линейные порядки следующих порядковых типов: rj, 1 + Г], »7 + 1 и 1 + Т/ + 1. В конце раздела 1.1 доказано, что для любого к Є ш — {0} существует Д линейный порядок L = (п + к + 1 + п) - А, для некоторого порядка А, удовлетворяющий условиям теоремы 1.1.8. Таким образом, для любого к Є w существует такой Д к+1 -блочный, но не А;-блочный линейный порядок L, что L имеет копию в каждой не низкой Д 2 -степени и не имеет копии в низкой степени и, следовательно, L не имеет вычислимой копии. Далее мы докажем, что любой сильно похожий на ц линейный порядок низкой степени имеет вычислимую копию (теорема 1.2.3). Причем, можно вычислить сложность функции изоморфизма — Дд. Теорема 1.2.3 Любой сильно похожий на п линейный порядок низкой степени А -изоморфен вычислимому порядку. Доказательство. Пусть L — fc-блочный линейный порядок низкой степени, где к ш. Предположим, что L не имеет ни наименьшего, ни наибольшего элемента. Иначе порядок L представим в виде a + L0 + Ь, где а, Ъ к + 1 и L0 — А;-блочный линейный порядок низкой степени без наименьшего и наибольшего элементов. Очевидно, что если L0 Дд -изоморфен вычислимому порядку, то L также имеет вычислимую копию, посредством Дд-изоморфизма. Так как L низкой степени, то предикат 5(ж,у) есть Д. А так как L является к -блочным порядком, то предикат F(x,y) вычислим относительно L и S(x,y) и, следовательно, также А%- Тогда существует такой Aj под-порядок L = ({а0, ai,...}, ь) порядка L, что для любых г ф j -iF(aj, a,j) и для любого х Є L — L либо F(x,a,i), либо F(aj,x) для некоторого гёы. Так как L — /г-блочный порядок без наименьшего и наибольшего элементов, то легко видеть, что V является плотным линейным порядком и существует такая Ag функция р, что V =v Q. Далее построим такую функцию /:Q— {1, ...,&} и такие Sj множества А и В, что L S Е{/(р_1(«)) І Є Q} и graph(f) = А-В. Пусть {І.}. , такая Д j-последовательность конечных линейных порядков, что Lo = 0 „ С e+i и DaLa = L — V. Зафиксируем оракул Д . Шаг s=0.
Для любого і Є ш перечислим в А пару (сц, 1). Шаг s-fi. Для любого ж Є Le+i — „ найдем такой і Є и , что .Р(ж,оц) или F(a,i,x). Найдем пару (а,і,п) 6 А— В для некоторого п Є ш. Такая пара обязательно существует и единствена. Перечислим теперь (аі,п) в В, а (а,і,п + 1) в А. Описание конструкции завершено. Очевидно, что множества В С А вычислимо преречислимы относительно Дз и, следовательно, Очевидно также, что для любого і ш существует единственная пара (щ,п) Є А — В. Определим теперь функцию /, как graph(f) = А — В. Так как L является fc-блочным линейным порядком, то область значений rang(f) конечно и ограничено числом А;. Легко видеть теперь, что L E{/(V _1( ?)) І Я Є Q} Так как А есть Eij, то существует такой четырехместный вычислимый предикат І2(ж,у,і,п), что (t,n) Є А тогда и только тогда, когда 3xVyR(x,y,t,n). Заметим, что по построению множества А, если f(t) = п, то для любого п п (t,n ) Є А и для любого п" п (t,n") А. Зафиксируем для Д линейного порядка L такую вычислимую аппроксимацию конечными линейными порядками {Lts}t,sew что для любых t,s Є ш L0,« = 0, Lt,s С Lt+i, , J = limaLti„ и L = UtZfJ. Причем, порядок Lt+i,„ отличается от Lt s на один элемент. Построим теперь вычислимый линейный порядок L = (и , 2) следующим образом. Будем рассматривать натуральные числа как окрашенные в различные цвета шары, которые мы будем класть на прямую, определяя тем самым порядок L обычным способом: если шар х левее шара у, то х і у Чтобы построить вычислимый линейный порядок, мы не должны переставлять шары. Мы можем только добавлять новые шары слева, справа или между другими шарами. Каждый раз, когда необходимо добавить новый шар, мы будем добавлять шар с наименьшим, еще не использованным номером. В нашей конструкции мы будем использовать раскраску шаров. Мы предполагаем, что имеется счетное число различных цветов. Белый будет особым цветом, обозначающий отсутствие какого-либо цвета и имеющий номер —1. Остальные цвета будут иметь натуральные номера 0,1,.... Таким образом, во-первых, каждый шар будет иметь свой натуральный номер, а, во-вторых, каждый шар будет окрашен в свой цвет, который также будет иметь свой номер, возможно отличный от номера шара. Шаг 0. Определим вспомогательную последовательность x(t,n, 0) = — 1 для всех Є о и те fc + 1. Положим также t(0) = 0. Шаг s+1. Предположим, что t(s) уже определено и шары, окрашенные в один (не белый) цвет, стоят непосредственно рядом друг с другом и расположены в соответствии с порядком Ь4(я)8, то есть окрашены в цвета го,..., гт (здесь цвета перечислены так, как расположены шары, слева направо) и t(.),. = { о ,(.,,. .(.),. «г} Подшаг 1. Выберем наибольшее такое t t(s), что для любого t t Lt ,a+i = Lti,s Положим t(s + 1) = t + 1. Добьемся того, чтобы в нашей конструкции шары, окрашенные в один цвет, стояли рядом и располагались В СООТВеТСТВИИ С ПОРЯДКОМ і/((я+1),я+1 Сначала покрасим в белый цвет все шары с цветом у Lt(,)iS (если такие имеются). Затем пусть t(a+i),H-i = - ( ),л U {ж}. И пусть х — наименьший в Lt(e+i))i+i (если наибольший, то построения аналогичны). Если самый левый шар на прямой не белый, то положим левее всех шаров новый шар, окрашенный в цвет х. Если левее всех цветных шаров имеются белые, то выберем среди них шар с наименьшим натуральным номером и покрасим его в цвет х. Пусть х не является ни наименьшим, ни наибольшим в 4(,+1))Я+1, тогда выберем такие а, b Є -Ц»),8, что а Lt(,)i. х x,t(,,,, Ь — соседние в t(«),«-Если между шарами, окрашеными в цвета а и Ь есть белые шары, то вы берем среди них шар с наименьшим натуральным номером и покрасим его в цвет ж. Если же нет, то положим между крайним правым шаром цвета а и крайним левым шаром цвета Ь новый шар, окрашенный в цвет х. Подшаг 2. Для любых а Є Ьцв+1 8+1 и п к + 1 если существует такой х s, х Є и , что Vy sR(x,y,a,n), то выберем наименьший такой х и положим ж(а, та, s + 1) = ж, в противном случае положим ж(а, n, s + 1) — — 1. Далее, для любого а Є t(«+i),«+i выберем наибольший такой п к + 1, что ж(а, те, s + 1) = x(a,n,s) ф — 1. Если такого п не существует, то положим те = 1. Если число шаров цвета а меньше те, то непосредственно справа от них положим столько новых шаров, окрашенных в цвет а, чтобы всего их получилось те штук. Если же шаров цвета а больше те, то оставим самые левые те штук, а остальные покрасим в белый цвет. Заметим, что построения в подшаге 2 не портят построения в подшаге 1. Описание конструкции завершено. Так как в конструкции шары не переставляются местами, а только добавляются новые, то построеный линейный порядок L является вычислимым. Из следующих трех лемм следует, что L = J2{f((P 1{ l)) І Я Є Q} — L. Лемма 1.2.4 Для каждого шара существует предельный цвет, то есть каждый шар на некотором шаге нашей конструкции будет окрашен в некоторый не белый цвет и на последующих шагах не будет его менять. Доказательство. Докажем по индукции. Пусть для шаров с номерами х х лемма верна, докажем для шара с номером ж. В силу бесконечности V существует такой шаг s\, что шар с номером ж появляется в нашей конструкции. По предположению индукции существует такой шаг s2 si, что шары с номерами ж ж на шагах s s2 не меняют свой цвет. Далее выберем такой шаг s3 s2, что шар с номером ж окрашен в белый цвет (если такого шага не существует, то лемма доказана). После этого шага, если шар ж будет окрашен в некоторый цвет, то он всегда будет самым левым среди всех шаров, окрашенных в тот же цвет (в подшаге 2 мы можем добавить окрашенные в этот цвет шары только справа от шара ж).
3-низкие алгебры Ершова
Теорема 2.2.1 Пусть Л — подалгебра счетной алгебры Ершова без наибольшего элемента В, содержащей бесконечное число непересекающихся 1-атомов. Если любой 1-атом алгебры Л является конечным объединением 1-атомов алгебры В и алгебра В порождается алгеброй Л и атомами и 1-атомами алгебры В, лежащими ниже 1-атомов Л, то A=f В. Причем, если алгебры Ершова Л и В, а также предикаты atom(x), atomless(x), atominf(x), l-atom(x), l-atomless(x) и l-atominf(x) вычислимы относительно X, то изоморфизм f можно построить вычислимым относительно X. Доказательство. Доказательство проводится так же, как и в теореме 2.1.1, но с другим множеством S = {(а,Ь) Є А х В \ a i b w. мощность множеств 1-атомов, лежащих ниже а и Ь совпадают}, где a i Ь означает, что aAb = (а \ Ь) U (6 \ а) является объединением конечного числа 1-атомов. Оценка сложности изоморфизма следует из оценки сложности множества S. Теорема 2.2.2 Пусть Л — Д алгебра Ершова без наибольшего элемента с Дд предикатами atom{x), l-atom(x), inf(x), atomiess(x), atomic(x) и atominf(x) тогда существуют такие вычислимая алгебра Ершова В с вычислимыми предикатами atom(x), inf{x) и atomless(x), А вложение f из Л в В, что 1) В порождена элементами ran(f), новыми атомами и 1-атомами В, лежащими ниже образов 1-атомов Л, 2) если а — 1-атом алгебры Л, то f(a) является конечным объединением 1-атомов В. Доказательство. Пусть Р = {atom, inf, atomless, 1-atom, atomic, atominf}, тогда так же, как и в доказательстве теоремы 2.1.5, существуют Такие равномерные ВЫЧИСЛИМЫе ПОСЛеДОВатеЛЬНОСТИ {Аа}яЄш и { ЛяЄ" для любого Р Є Р, что Л = ИтяЛв и для любых х и Р Є Р выполнено Р(х) — limsPa(x). Без ограничения общности, можем предположить, что существует бесконечное количество таких k\, hi и кз, что а содержит новый наибольший элемент a,i = С{ V а , где і Є {1,2,3}, ( — старый наибольший элемент, а[ — атом Л, а 2 — безатомный элемент Л и а 3 — элемент, не являющийся ни атомом, ни безатомным элементом. Будем строить такие Aj-последовательность {ак}кеш конечных подалгебр алгебры Ершова Л, вычислимую последовательность {(Зк}кеш конечных подалгебр алгебры В с выделенными множествами атомов, элементов, являющихся конечными объединениями атомов, и безатомных элементов (то есть одновременно будем вычислять предикаты atoms, /в и atomlesse на элементах /.) и Д-последовательность конечных функций {pk}kw, что «fc Q оск+1, Л - Ufcttfc, рк С Pk+i, В = UkPk, Рк С pfc+i и / = UfcPfc Шог s = 0. Определяем «о = 0, /Зо = 0 и ро = 0 Шаг s + 1. Пусть построены такие алгебры „(„) и /Зв и вложение рп(„) из ап(в) в Д,, что для некоторого а Є ап(») если infs(a), то р„(„)(а) не является объединением таких у, что а отпд(у); если atomlessg(a), то ниже рп(в)(а) нет таких у, что atomeiy); если а отпгс,(а), то ниже рп (а) нет безатомных элементов В, то есть таких у, что atomlessgiy). Выберем наибольший такой к n(s), что од является подалгеброй As+i, и положим n(s + 1) = к + 1. Построим алгебры an(,+i) 2 ( +1)-1 A +i 2 & И ВЛОЖеНИе рп(з+1) Пусть е — элемент с наименьшим натуральным номером, нележащий в ап(в+1)_!. Пусть ап(л+1) — наименьшая подалгебра алгебры Л3, содержащая алгебру a:n(g+i)_i и элемент е. Случай 1. Пусть an( +i) и an(»+i)-i имеют один и тот же наибольший элемент. Без ограничения общности можем предположить, что a„(,+i) порождается элементами an(a+i)-i и элементом с, расщепляющим атом а алгебры «n(»+i)-i
Пусть Ъ = pn(8+i)-i(a). Рассмотрим сначала простые случаи. Если aiome+i (a), то ничего не делаем. Если atomlesss+i(a), то наши действия точно такие же, как и в доказательстве теоремы 2.1.5 в подслучае 1, определяем при этом - atomB{d), infe(d) и atomlessB(d) для любого ненулевого d а. Предположим, что -iatomg+i(a) и - atomlesss+i(a). Если -im/,+i(a), то наши действия точно такие же, как и в доказательстве теоремы 2.1.5 в подслучаях 2 и 3, при этом определяем - atomlessB(d), - atomlessB(b \ d), -im/s(«i) и -ііп/в(Ь \ d), если atome+i(c), то положим atomB(d), иначе - atomB(d) (случай atoms+i(a\c) рассматривается аналогично), где Ps+i(c) = d. Если - atominf8+i(a), то наши действия точно такие же, как и в доказательстве теоремы 2.1.5 в подслучаях 2 и 3, при этом если atoma+1(c), то определяй atome(d), -linfeid), - atomlessB(d), infe(b\d) и - аЬотв(Ь \ d); если atomlesss+i(a\c), то atomlessB(b\d) (случай atoma+i(a\c) рассматривается аналогично), где p„+i(c) = d. Предположим, что infa+i(a) и atominfs+i(a). Для определения функции вложения pn(s+i),s+i найдем элемент d и положим рп(я+і))Я+1(с) = d. Подслучай 1. Пусть atomica+i(a), тогда по построению ниже Ь нет таких элементов у Є $,, что atomlesseiy), а также 6 не является объединением таких у, что аЬотв(у). Подслучай 1А. Пусть - m/g+i(c) (случай - infg+i(a\c) рассматривается аналогично) и infa+i(a\c) (иначе ничего не делаем). Пусть d — объединение всех таких у, что - infs{y) (если таких нет, то расщепим такой атом у Є В с наименьшим возможным номером, что у Ъ и -iatoms(y ), для такого расщепления у" положим """ш/ у") и гп/в(у \у"))- Если atoms+i(c), то в дополнение наших действий расщепим все такие z d, что - atomB(z), и для всех таких расщеплений z положим аЬотпв(г ). Подслучай 1В. Если m/s+i(c), m/e+i(a \ с) и l-atomg+i(a), то ничего не делаем. Если infa+i(c), infa+i(a\ с) и - l-atoms+i{a), то расщепим такой атом у Є /3 с наименьшим возможным номером, что у 6 и ш/э(у ), для такого расщепления б? положим infe(d) и іп/в(у \ d). Подслучай 2. Пусть - аотгся+і(а) (напомним, что - atomlessa+i(a)). Подслучай 2А. Если atomies s„+i(c) (случай atomiessa+i(a \ с) — аналогичен), то пусть d — объединение всех таких у Ь, что atomlesseiy) (если таких нет, то определим d как новое расщепление элемента 6 и положим atomlessB(d), - atomlessB(b\d) и гп/в(Ь\с?)). Подслучай 2В. Предположим, что - aom/esa,+i(c) и -iatomlessa+i(a \ с). Если -im/,+i(c), то наши дествия аналогичны подслучаю 1А. Пусть infa+i(c). Если -iaiormc,+i(c) (случай - atomica+\(a \ с) — аналогичен) и -iatomics+i(a \ с) (иначе ничего не делаем), то пусть d — объединение всех
Теоретико-множественные сводимости
Пусть Т — решетка множеств, тогда назовем функцию Ф : 7Уп — Т теоретико-множественной по классу множеств Т , если она либо совпадает с одной из следующих: Фі(Х,У) = Xl)Y, Ф2(Х,У) = Xf)Y или Ф т(Хі, ...,Xn) = Xm (1 m ті); либо может быть получена из них применением конечного числа раз операции суперпозиции. Определение 3.2.1 Пусть Т — решетка множеств, тогда будем говорить, что множество В SET-1-сводится (SET -2-сводитсл) к множеству А по классу множеств Т и будем писать A 5ST-i В (A SET-2 В) если существуют такие множества Ri, ..., Rn Є Z и такая теоретико-множественная формула Ф : Т п+1 — V (Ф : Т п+2 — Т ), что А — Ф(В, Ri,..., Rn) (или А = Ф(2?, В, Ді,..., Rn), соответственно). Если выше описанное условие не верно, то говорим, что В не SET 1-сводится к А (В не SЕТ-2-сводится к А), и пишем А SET—I Следовательно, бинарные отношения =5вт-і и =SBT-2 являются отношениями эквивалентности. Классы эквивалентности будем обозначать WSBT-І = {В С ш \ В = ЕТ-І А}, где 1 г 2. Пусть R Є V, тогда класс [R]sET-i — наименьший элемент по 5"ЕТ-і-сводимости. Причем, [.R]?BT-I = Т . Легко видеть, что [i2]fjsT-2 — наименьшая по включению алгебра множеств, содержащая V. Следовательно, если Т — алгебра множеств, то [R]SET-2 = "D Если A SBT-I В, то очевидно A SET-2 В Очевидно также, что А =5ЕГ-2 А, ДЛЯ Любого А С U . Лемма 3.2.2 Если Т — алгебра множеств, то А SET-I В тогда и только тогда, когда А S ET-I В . Доказательство. (= ). Если А = Ф(і?, Ді,... , Д„), где Д1}..., Д„ Є Т , то А = Ф (В, Ri,... ,Rn), где формула Ф получается из формулы Ф заменой операции U на П, а П на U. Заметим, что Ді,...,Д„ Є ї , так как V — алгебра множеств. ( =) Из только, что доказаного следует, что если A 5sr-i В то А 5ВТ-1 В і то ЄСТЬ А 5ВГ-1 & Определения теоретико-множественных сводимостей достаточно неудобные для дальнейшей работы с ними, поэтому нам необходимы критерии для этих определений, так называемые нормальные формы. Далее в теоремах 3.2.3 и 3.2.7, мы видим критерии для теоретико-множественных SET-1- и 5 ?Г-2-сводимостей. Теорема 3.2.3 (О нормальной форме для 5 Г-1-сводимости). Для решетки множеств Т и для любых множеств А и В выполнено A SET-I В тогда и только тогда, когда существуют такие множества Ri, R2 Є Т , что Ri С R2 и справедливо одно из следующих представлений: Замечание 3.2.5 Представим предыдущую теорему 3.2.3 в следующей более удобной записи: Пусть Т — решетка множеств. Тогда для любых множеств А и В выполнено А 5Т-і В тогда и только тогда, когда существуют такие множества R1 Gl U{0} и Д2 V\J{w}, что Дх С Д2 и А = (Би Ді)П Д2. Заметим также, что если Ri С. R2, то (В U Ді) П R2 = (В Г\ Д2) U Ді. Доказательство теоремы 3.2.3. (= ) Пусть A SBT-I В тогДа существуют такие множества R\, ..., Кп Є Т и такая теоретико-множественная формула Ф, что А = Ф(В, Ri,..., R„). Любая теоретико-множественная формула является некоторой конечной записью специальных символов — базисных формул Фг, Ф2 и $3 т (1 тп п + 1); w. специального символа, который связывает базисные формулы операцией суперпозиции. Зафиксируем некоторую такую запись для формулы Ф. Введем понятие длины записи множества В в записи теоретико-множественной формулы Ф, которую будем обозначать через Ыф(В), как число встречающихся в записи формулы Ф символа Ф Далее будем вести индукцию по 1ПФ(В). I)
Пусть 1пФ(В) = 0, тогда А = Ф(5,Яі,..., Д„) = Ф(Ді,..., Д„), где теоретико-множественная формула Ф полностью совпадает с Ф, так как в данном случае формальный параметр В можно опустить. Следовательно, А Є V, так как V является решеткой множеств. Тогда А = (В U R) ҐЇ R и R С R, где R = А Є V. II) Если 1пф(В) = 1, то либо A = (, ,..., ) = Ф Б, !,..., /гп)иФ /(Я,Д1,...,Дп), либо А= (5, ,..., ) = ФІ(В,Ді,...,Д„)П ФІ (В,Я!,..., Rn), либо А = (5, ,..., ) = (5, ,..., ), 1 г те + 1 (в последнем случае теорема доказана), где 1п& (В) + /теф»(5) — 1. В силу коммутативности операций объединения и пересечения, без ограни чения общНОСТИ МЫ МОЖеМ ПреДПОЛОЖИТЬ, ЧТО ІПфі(В) = 1 И ІПф"(В) — 0. Тогда по случаю I Ф"(В, Ri,..., R„) Є V. Аналогично, (5, R1,...,Rn) = Ф 2(В, Ri,..., RJS& B, Ru...,Rn), где $ = U или = П, ІПфі(В) = 1 и /те$«(5) = 0. И так далее, до тех пор когда Ф , = Фз г і Для некоторого і Є {1,..., те + 1} (такой существует так как запись для Ф конечна). Таким образом, получим следующее представление формулы А (при 5 = 0 теорема доказана): А = (... ((Вад Д г)... 8,R S), где St Є {U, П} и R\ V, 1 і s. (3.1) Заметим, что В = (5и0)ГЫ и = (ВиК ПЩ (1 г s). Неоднократно применяя лемму 3.2.4, из формулы 3.1 получим, ЧТО А = (В U Pi) П Р2, где Pi Є V U {0}, Р2 Є V U {и} и Рх С Р2. III) Пусть Ыф(В) = к 1 и для любой такой формулы Ф (В, Pi,..., Rn), что ІПфі(В) к, существуют такие множества iJ GPU {0}, R" Є Т U {u }, что Л С R" и Ф (В, Лі,..., Р„) = (В U Я ) П Я". Также как и в пункте II получим следующую формулу (случай s = О очевиден): А={... (Ф (В, Pi,..., Rn)S1R[)S2 .. .) . Д „ (3.2) где й Є {и,П}, Щ е V (1 і s), Ф В.Й!,...,/ ) = Ф 1(Б,Р1,...,Яп)и Ф 2(Р, Ru...,Rn) или = Ф Х(Я, РЬ ..., Р„) П Ф 2(Р, PI, ..., Р„), где 1пФ[ (В) ф О и 1п$1 (В) ф 0 (то есть ІПфі {В) к и Zn$» (В) к). Применим индукцию к формулам Ф и Ф 2. Тогда существуют такие множества Pl5 Р3 Є V U {0} и Р2, Р4 Є Х U {w}, что Pi С Р2 и Р3 С Р4, Ф;(Р, PI, ..., ІЦ = {В U Рі) П Р2 и Ф 2(Р, Рь..., IQ = (В U Р3) П Р4. По лемме 3.2.4 имеем Ф (В, Рь ..., Р„) = (В U Р ) П Р", где Р Є U {0}, Р" Є PUM и Р С Р". Аналогично пункту II, по лемме 3.2.4 из формулы 3.2 следует, что существуют такие множества Рі Є Х U {0} и Р2 Є Т U {ш}, что Pi С Р2 и А = (PUPi)HP2. ( =). Очевидно, по определению 5 Г-1-сводимости. В силу замечания 3.2.5 следующее следствие очевидно. Следствие 3.2.6 Для решетки множеств Т с наименьшим или с наибольшим элементом и для любых множеств А и В выполнено А SST-I В тогда и только тогда, когда существуют такие множества R\, Р2 Є Т , что Pi С Р2 и справедливо одно из следующих представлений: 1) А — В U Pi (если Т — с наименьшим элементом) или А = В П Pi (если Т — с наибольшим элементом, соответственно), 2) А = {В U Pi) П Р2 = {В П Р2) U Pi. В случае, если 0, ибР, то случай 1 можно опустить. Теорема 3.2.7 (О нормальной форме для 5?Т-2-сводимости). Для решетки множеств Т и для любых множеств А и В выполнено A SBT-2 В тогда и только тогда, когда либо А SST-I В, либо А 5вт-і В Ли существуют такие множества Rx, Р2 Є Т , что А = (В U Pi) П (В U Р2).
SET-1-сводимость на классе вычислимых множеств
Следующие две леммы очевидны. Лемма 3.3.1 Если А = В, то А =SST-I В и A =5sr-i В Лемма 3.3.2 Если 7)=1 или VTZ, то А S.ET-I В тогда и только тогда, когда А 5вт-і В Во всех следующих определениях и результатах мы предполагаем, что Т = VR или V. Заметим, что в этом случае все результаты этой главы справедливы для V = VR- и для Т — V. Таким образом, возникает вопрос о изоморфизме частичных порядков IZj=vn и TZ/ =v . К сожалению, мы SET—1 SET—1 не даем ответ на этот вопрос. В последнем разделе мы приводим только достаточное условие существования этого изоморфизма. В следствии 3.3.7 мы докажем, что ни TZ/ =?к , ни TZ/=v не явля SET—X SET—1 ется верхней полурешеткой, что существенно отличает SET-1-сводимость от таких классических сводимостеи теории вычислимости, как тьюринговая сводимость, 1-сводимость, m-сводимость и другие, так как все выше перечисленные сводимости порождают верхние полурешетки (см., например, [10]). Определение 3.3.3 Вычислимое множество А называется Т -максимальным, если для любого множества В из А SJET-I В следует А =5вт-і В Предложение 3.3.4 Пусть Рх и Pi — примитивно рекурсивные множества, а множество В Т -бииммунно в Pi Coo Р2 "тогда если множество А такое, что Pi С А С Р2 и В ET-I А, то А = В. Доказательство. Пусть V = VTZ (для Т = V доказательство аналогично). Пусть множество А такое, что Pi С А С Р2 и В 5вт-і А, тогда по теореме 3.2.3 существуют такие примитивно рекурсивные множества Ri и Р2, что Pi С Р2 и В = (A U Ri) П R2. Имеем, Рх С Р С Р2. Так как Рх С В С Р2, то Рх С (Pi U Rx) С В С (Р2 П R2) С R2. Из того, что В РТ -бииммунно в Pi Coo Р2 следует, ЧТО Rx С Рх и Р2 С R2. Следовательно, Pi С AC R2. Таким образом, В = (A U Pi) П R2 = А. Следствие 3.3.5 Если множество В является V-бииммунным в 0 Соо , тогда В является Т -максимальным. Доказательство. Пусть Pi = 0 и Рг = , тогда по предложению 3.3.4 для любого такого множества А, что В SST-I & имеем А = В и, следова тельно по лемме 3.3.1, A =SET-\ & а Следствие 3.3.6 Т -максимальное множество существует. Доказательство. По теореме 3.1.5 существует Х -бииммунное в 0 Соо ш множество. Из следствия 3.3.5 следует, что оно Т -максимально. Следствие 3.3.7 Ни H/=VR. , ни TZ/=v не является верхней полуре шеткой. Доказательство. Докажем для TZ/=m (для Ttl=v доказывается ана — SET-l v — SET-l логично). Зафиксируем VTZ-бииммуиное в 0 Соо множество В из теоремы 3.1.5. Тогда В также VIZ -биимму нно в 0 Соо w. Очевидно, что оба они не являются примитивно рекурсивными множествами. Тогда из следствия 3.3.5 следует, что В л В являются РТ -максимальными. Если вычислимое множество А является точной верхней гранью для В и В, то В 5вг-і А ъ В SBT-I - -
А так как В а В являются VR,-максимальными, то A SET-I В — 1SET-I В Имеем В П В = 0 — примитивно рекурсивное множество, тогда по пред ложению 3.2.12 множество В является примитивно рекурсивным. Получили противоречие. Заметим, что в доказательстве следствия 3.3.7 построена пара множеств не имеющей ни только точной верхней грани, но не имеющей никакой верхней грани. В следующей теореме мы дадим описание всех V-максимальных множеств. Теорема 3.3.8 Множество Ъ-бииммунно в 0 Соо и, тогда и только тогда, когда Т -максимально. Доказательство. Пусть V = VR. (для Т = V доказывается аналогично). (= ). Доказано в следствии 3.3.5. ( Ф=). Пусть множество В является VIZ -максимальным, но не является "РТ -бииммунным в 0 Соо и, тогда существует такое примитивно рекурсивное множество R, что либо R бесконечно и R С В, либо R кобесконечно (то есть R бесконечно) и ВСД. Пусть для определенности выполнено первое, тогда мы построим такое вычислимое множество А, что В — A U R и не существует такого примитивно рекурсивного множества R!, что А = В ҐІ R . Тогда из предложения 3.2.13 следует В $ЕТ-І А. Что противоречит V71-максимальности множества В. Аналогично, если выполнен второй случай, нам достаточно построить такое вычислимое множество А, что В = А П R и не существует такого примитивно рекурсивного множества R , что А = В U R . Далее мы рассмотрим только первый случай, второй рассматривается аналогично. Нам надо построить такое вычислимое множество А С. В, что В = A U R и А ф В П R!, для любого примитивно рекурсивного множества R . Воспользуемся бесконечностью множества R. Пусть те(0) = 0 и п(х + 1) = п(х) + хл(ж), тогда функция п(х) вычислима (даже примитивно рекурсивна). Так как R бесконечно, то область значения функции п есть ш, то есть гапд(п) = ш. Положим ХА{%) = Хв(х), если XR(X) = 0 (таким образом, выполняется условие В = Al) R). Если %д(ж) = 1, то ХА(Х) = 1д(хв(х) рп(а.)(ж)). То есть, если хв(х) = 1 и рп(х)(х) ф 0, то ХА{Х) = 0, иначе ХА(Х) = 1. Та ким образом, обеспечиваем А ф В П R , где XR = Рп(х) Легко видеть, что А ф В П R , для любого примитивно рекурсивного множества R (так как rang(n) = а ), за исключением, возможно, примитивно рекурсивного множес тва, характеристическая функция которого имеет в эффективной нумерации номер 0, то есть функция — ро. Однако, каждая примитивно рекурсивная функция в эффективной нумерации встречается бесконечное число раз, поэ тому существует такое число к 0, что р0 — ри- Таким образом, А ф BC\R для любого примитивно рекурсивного множества R . Далее, в следующей теореме 3.3.9 мы опишем все множества, над которыми можно найти Х -максимальные множества (в смысле отношения SET-I) Теорема 3.3.9 Если В — Т -максимальное множество, то для любого вычислимого множества A 5ST-i & либо А Є Т , либо А Т -бииммунно в Ri С R2, где А= (BUR1)nR2, Ri Coo - и Ri,R2 ЄТ по теореме 3.2.3. Обратно, если А Є Х или А Т -бииммунно в R± Coo R2 для некоторых R\,R2 Т , R\ Coo R2, то существует, такое Т -максимальное множество В, что А 5вт-і & Доказательство. Пусть Т — VIZ (для Т = V доказывается аналогично). (= ). Пусть В — VTL -максимальное множество и A SET—I тогДа по теореме 3.2.3 существуют такие примитивно рекурсивные множества Ri С Ri, что А — (В U Ri) П R2 Так как В — РТ -максимальное, то из теоремы 3.3.8 СЛеДуеТ, ЧТО В "Р7-биИММуННОЄ В 0 Соо ш. Рассмотрим случаи: 1) Ri = OJ , тогда А — (В U ш) П R2 = R2, то есть А — примитивно рекурсивное множество. 2) Ri = 0, тогда А = (В U 0) П R2 = В Г) R2. Рассмотрим подслучаи: 2а) R2 = ш, тогда А — В и, следовательно, A VR-бииммунно в 0 Соо 2b) R2 — 0, тогда А = 0 — примитивно рекурсивное множество. 2с) 0 Соо R2 Соо w, тогда по предложению 3.1.4 множество А = В Ґ1 R2 VR-биИММуННО В 0 = J?i Соо 2 3) 0 Соо 1 Соо ш і тогда по предложению 3.1.4 В U R\ РТ -бииммунно в Соо ш. Так как Ri С R2, то возможны следующие подслучаи:
