Содержание к диссертации
Введение
Глава 1. Сильно конструктивные булевы алгебры 13
1.1. Один признак конструктивизируемости 18
1.2. Критерий изоморфизма 27
1.3. Оценка сложности моделей 32
Глава 2. Однородные булевы алгебры 37
2.1. Критерий вычислимости для однородных булевых алгебр 39
2.2. Метатеорема для а-систем 44
2.3. Метатеорема для фактор-алгебр 48
2.4. Две вспомогательные конструкции и отношения а 57
Глава 3. Автоустойчивые 1-алгебры 62
3.1. Псевдо-неразложимые 1-алгебры 64
3.2. Алгебраические инварианты 67
3.3. Критерий изоморфизма 76
3.4. Теорема о ветвлении 82
3.5. Необходимые условия автоустойчивости 91
3.6. Критерий автоустойчивости 108
Литература 115
- Критерий изоморфизма
- Две вспомогательные конструкции и отношения а
- Алгебраические инварианты
- Необходимые условия автоустойчивости
Введение к работе
Диссертация посвящена решению некоторых проблем из теории вычислимых (конструктивных) моделей. Её основные результаты относятся к вычислимым булевым алгебрам, хотя некоторые рассматриваемые вопросы имеют более широкий характер. Теория вычислимых моделей возникла в 50-х годах прошлого века в работах А.И. Мальцева, О. Рабина и др., и с тех пор активно развивается. Объём литературы, посвященной этой теме, очень велик. В качестве наиболее важных и современных источников можно указать [11, 30, 35]. Булевы алгебры, в свою очередь, тоже являются классическим объектом, привлекающим внимание математиков уже в течение полутора веков. Попытка собрать хотя бы основные достижения в этой области привели к появлению в 1989 году трёхтомного справочника [34].
Вычислимые булевы алгебры нашли многочисленные приложения в теории алгоритмов, математической логике, теории моделей и др. областях. Хорошим источником по этой теме является монография [9], в которой представлены, впрочем, достижения в первую очередь новосибирского коллектива математиков, являющегося одним из лидеров в данной области. Диссертация является, в частности, естественным продолжением этой монографии — она отвечает на некоторые поставленные там вопросы и развивает ряд затронутых тем. Неплохим обзором является [31].
Напомним, что модель А конечного языка называется вычислимой, если её носитель — вычислимое подмножество множества натуральных чисел и, а операции и предикаты — вычислимые функции на этом подмножестве. В свою очередь, под вычислимыми функциями понимаются те, которые могут быть вычислены с помощью некоторой машины Тьюринга, а под вычислимыми множествами — обладающие вычислимыми характеристическими функциями. Понятие конструктивной модели даёт нам другой подход к тому же классу объектов, который фактически основан на использовании другого языка; немного более подробно связь между ними обсуждается в начале Главы 1. Говорим, что произвольная модель А кон-структивизируема, если она изоморфна некоторой вычислимой модели.
Центральными проблемами теории вычислимых моделей являются вопрос о том, какие модели являются конструктивизируемыми, и насколько велико число различных вычислимых представлений у данной модели. Последнее понятие, число различных представлений, может пониматься в разных смыслах, и в литературе рассматривается несколько подходов, которые сводятся к разным определениям "эквивалентных" представлений. В настоящей диссертации используется наиболее сильный подход: две вычислимые модели А\, Лг считаются "эквивалентными", если между ними существует вычислимый изоморфизм / : А\ —» Л.2, то есть изоморфизм, одновременно являющийся вычислимой функцией на носителе Ai. В этом случае мы говорим, что модели А\ и Лг вычислимо изоморфны. Изучение этой темы было начато А.И. Мальцевым, который в [17] назвал автоустойчивыми те модели, у которых все вычислимые представления вычислимо изоморфны. Максимальное число вычислимых представлений модели А, которые не являются вычислимо изоморфными друг другу, называется алгоритмической размерностью модели A, dime (А), или авторазмерностъю (это ПОНЯТІЇЄ было впервые введено в
[71).
Когда мы говорим о булевых алгебрах, в первую очередь разумно задаться вопросом об описании тех из них, которые являются конструктивизируемыми, К сожалению, на данный момент эта задача представляется неразрешимой — этот класс очень велик, и нет никаких разумных гипотез о его алгебраической характе-ризации. При этом существует несколько способов сводить проблему такого описания к некоторым другим: например, булева алгебра А конструктивизируема тогда и только тогда, когда она может быть порождена некоторым вычислимым линейным порядком (см. [9]). Этот факт позволяет нам свести описание конструктиви-зируемых булевых алгебр к описанию конструктивизируемых линейных порядков. К сожалению, последняя задача является ещё более сложной, чем предыдущая. Точно так же от вычислимых булевых алгебр можно перейти к вычислимым бинарным деревьям, или булевым кольцам.
Но при этом для некоторых важных подклассов булевых алгебр ситуация является не столь безнадёжной. Например, в [4] было найдено описание конструктивизируемых суператомных булевых алгебр — критерием оказалась конструктивность ординала, который является естественным рангом алгебры. В [20] была получена некоторая характеризация конструктивных атомных булевых алгебр: атомная алгебра А конструктивизируема тогда и только тогда, когда её факторизация по идеалу Фреше A/F является Дд-конструктивизируемой (т.е. конструктивизируе-мой с оракулом 0"). В [20, 24] было получено ещё несколько результатов, подобных этому.
В Главе 2 решается проблема описания конструктивизируемых ш-однородных булевых алгебр. Счётная модель А является си-однородной, если для любых двух наборов её элементов а, Ь одинаковой длины из элементарной эквивалентности {А,а) = (А,Ь) следует изоморфизм (А,а) = (А,Ь). Отметим, что для произвольной (не обязательно счётной) модели понятие w-однородности обычно определяется иначе; в счётном же случае эти определения равносильны.
Предлагаемое решение основано на описании произвольных, не обязательно вычислимых, w-однородных булевых алгебр, полученном в [18]. Подробно об этом описании говорится в начале Главы 2, пока же приведём только условную формулировку: такие алгебры могут быть естественным образом охарактеризованы через последовательность (po,pi,.. .) гДе Ри лежащие в множестве {0,1} — некоторые алгебраические инварианты; при этом любой такой последовательность из 0 и 1 соответствует некоторая алгебра. Вопрос тем самым сводится к тому, какие из этих последовательностей соответствуют конструктивизируемым алгебрам. Эта проблема, в частности, формулировалась в сборнике проблем математической логики [16], частичный ответ (некоторые необходимые и некоторые достаточные условия) ранее был дан в [24].
Ответ на этот вопрос удалось получить в чисто алгоритмических терминах: для этого было предложено некоторое обобщение иерархии Фейнера 0 -вычислимых функций ([33]); более точно, была предложена более тонкая иерархия, которая включает в себя классы Фейнера в качестве частного случая. В терминах этой иерархии были охарактеризованы как вычислимые, так и 0(™)-вычислимые си-однородные булевы алгебры, для каждого п Є ю (Теорема 2.1.3). В частности, с помощью этого описания можно легко повторить построение хорошо известного и очень сложного примера 0 -вычислимой и неконструктивизируемой булевой алгебры, который был найден Фейнером в [33]. Кроме того, описание позволя ет показать, что при росте п класс 0(")-вычислимых однородных алгебр строго увеличивается (Следствие 2.1.9). Содержательность (т.е. в определённом смысле невырожденность) новой иерархии показана в Предложении 2.1.8.
В качестве некоторого дополнительного результата в Главе 2 строится общая конструкция (Теорема 2.3.9), которая обобщает указанные выше теоремы из [20] и [24] и позволяет получить много новых критериев, имеющих следующий общий вид: булева алгебра А конструктивизируема 3- фактор-алгебра А/Т(А) 0(°)-конст-руктивизируема, где а — некоторый конструктивный ординал, а Т — соответствие, каждой алгебре А сопоставляющее некоторый идеал Т(А) С А. Теорема говорит о том, при каких условиях нааиГ критерий такого вида имеет место. Некоторые примеры её использования можно найти в Следствии 2.3.10. Отметим, что эта общая конструкция, названная в Главе 2 "метатеоремой для фактор-алгебр", была впоследствии обобщена автором на случай булевых алгебр с одним выделенным идеалом в [49]. Кроме того, на её основе удалось описать вычислимые семейства суператомных булевых алгебр ([44]). В настоящую диссертацию последние результаты не включены для сокращения объёма текста.
Если у данной модели существует какое-то вычислимое представление, то иногда бывает важно знать, обладает ли она вычислимым представлением с какими-то дополнительными алгоритмическими свойствами, например, в котором вычислимыми являются некоторые дополнительные определимые отношения и операции, не входящие в язык этой модели. В одной из наиболее общих постановок этот вопрос сводится к существованию сильно вычислимых представлений: вычислимая модель называется сильно вычислимой, если в ней вычислимым является любое отношение, определимое некоторой формулой первого порядка, и при этом "равномерно" по формуле. Другими словами, если существует алгоритм, который по формуле р(х\,..., хп) и набору элементов oi,..., ап определяет, истинна ли эта формула на этом наборе. Более строгое определение этого понятия приведено в начале Главы 1.
Ю.Л. Ершов в [12] показал, что сильно вычислимые булевы алгебры могут быть охарактеризованы следующим образом: существует вычислимая последовательность одноместных формул (pi(x), p2(x),- • • языка булевых алгебр такая, что
б
вычислимая булева алгебра А сильно вычислима тогда и только тогда, когда все fi(x) вычислимы в ней равномерно по і, то есть является вычислимым множество {(і, х) Є oj х А А (= (pi(x)}. Эта последовательность формул имеет естественный алгебраический смысл: pi(x), например, говорит, что х — атом, фг х) что х — безатомный элемент, рз(х) — атомный, и т.п. Позже С.С. Гончаровым в [9] было доказано, что вычислимость первых п формул cpi(x),... ,срп(х) равносильна п-вычислимости А , последнее означает, что в А равномерно вычислимы все свойства, определимые п-формулами.
В [6] было показано, что существует булева алгебра А, которая п-вычислима для любого п Є w (без равномерности по п), но при этом не является сильно кон-структивизируемой, т.е. не изоморфна никакой сильно вычислимой модели. Если же мы будем рассматривать булевы алгебры с фиксированной элементарной теорией (от которой в первую очередь зависит структура формул), то определённая связь между п-вычислимостыо и сильной вычислимостью возникает. Пусть Т — некоторая теория первого порядка. Определим следующую характеристику: положим cm(T) = min{n Є из любая n-вычислимая модель теории Т обладает сильно вычислимым представлением}, и ст(Т) = оо, если указанного п не существует. Эта величина некоторым образом характеризует сложность моделей Т: она показывает, формулы какого уровня сложности необходимо уметь вычислять в данной модели для того, чтобы гарантировать возможность вычисления всех формул — если не в самой модели, то по крайней мере в некоторой её изоморфной копии (более правильно устроенной). В частности, если Т модельно полна, то cm(T) = 0.
Основным результатом Главы 1 является описание ст(Г) для всех элементарных теорий булевых алгебр, т.е. теорий вида Th(A) = {ір — предложение! А \= ср}, или, что то же самое, полных расширений теории всех булевых алгебр. Заметим, что для любой теории Т cm(T) = sup{cm(T") Т" — полное расширение Т}. В случае булевых алгебр ст(Т) имеет дополнительный алгебраический смысл — она равна наименьшему п, при котором сильная конструктивизируемость алгебры с теорией Т равносильна существованию вычислимого представления с вычислимыми формулами pi(x),...,ipn(x) Напомним, что элементарные теории булевых алгебр были описаны Тарским и Ершовым в [42] и [12]: они могут быть заданы через тройки некоторых алгебраических инвариантов (п, к, є), где n,fcGwU {о°Ь а є Є {О,1}. В силу этого вместо ст(Т) будем использовать запись cm(n, fc, є). Из той же работы [12] нетрудно вывести верхнюю оценку: cm(n+l, к, 0) 4п+3 и cm(n+l, к, 1) 4п+4 при п, к со, а ст(п + 1, оо, г) 4п + 5. Исследование вопроса о точной величине cm(n, к, є) имеет долгую историю. Например, в [5] было доказано, что cm(0,oo,e) = 1; упомянутый выше пример из [6] показывает, что ст(оо, 0,0) = оо (при этом обозначение ст(Г) в тех работах не использовалось; оно было предложено автором диссертации). Затем различным частным случаям был посвящен ещё ряд работ С. С. Гончарова, СП. Одинцова и В.Н. Власова; более подробно история этих исследований указана в начале Главы 1. Проблема полного описания cm(n, к, є) была сформулирована, в частности, в [35], а также в [16, 8, 9]. Её полное решение приведено в Теореме 1.3.4.
Перейдём теперь к вопросу о числе конструктивизаций. Для булевых алгебр он был независимо решён в [10] и [39]: если А — вычислимая булева алгебра, то dime (А) Є {1, }, причём dime (А) = 1 тогда и только тогда, когда число атомов в А конечно. Модель А с dimc(A) = 1 называем автоустойчивощ все её вычислимые представления вычислимо изоморфны друг другу. Описание автоустойчивых булевых алгебр является, очевидно, исчерпывающим: в счётном случае строение алгебр с конечным числом атомов тривиально и хорошо известно. Они разлагаются в прямое произведение безатомной и конечной алгебр, тип изоморфизма последней определяется числом атомов, а первая может быть лишь одного из двух типов: нулевой и счётной ненулевой.
Глава 3 посвящена описанию автоустойчивых булевых алгебр с конечным числом выделенных идеалов (I-алгебр), т.е. моделей вида (А , Д,..., /д), где А — булева алгебра, а /і,...,Д — идеалы в А , выделяемые добавленными в язык А новыми одноместными предикатами. Этот класс моделей тесно связан с булевыми алгебрами: например, в [48] доказано, что тип изоморфизма любой счётной и достаточно сложно устроенной булевой алгебры А (например, неразложимой в прямое произведение атомной и безатомной алгебр) однозначно определяется 1-алгеброЙ (A/S, E/S), где Е — идеал Ершова-Тарского, a S — идеал, порождённый атомами и безатомными элементами. Эта связь продолжается и на случай вычислимых алгебр: например, булева алгебра А обладает 3-вычислимым представлением тогда и только тогда, когда {A/S, E/S) б -конструктивизируема.
В [14] было найдено описание автоустойчивых 1-алгебр с одним выделенным идеалом, т.е. моделей вида (А , її), оно также оказалось достаточно простым. Однако по мере роста числа выделенных идеалов А сложность автоустойчивых I-алгебр резко возрастает, и уже при А = 3 они образуют достаточно большой и нетривиально устроенный класс. В Теореме 3.6.1 указан алгебраический критерий автоустойчивости произвольной 1-алгебры А. Для упрощения формулировки он приведён только для алгебр, в которых набор выделенных идеалов {Д,... ,/д} замкнут относительно пересечений, а также содержит идеалы {0} и А. Чтобы применить его к произвольной 1-алгебре, нужно соответствующим образом пополнить набор {/і,,.., їх} — такое пополнение не меняет алгоритмическую размерность.
Теорема 3.6.1 говорит также о том, что dimc(A) Є {1, о;}- для любой 1-алгебры А = (А , Д,..., 1\). Из неё нетрудно вывести два важных следствия:
(1) для каждого фиксированного А есть конечный набор 1-алгебр А\,..., Лдд), конечные прямые произведения элементов которого образуют класс всех автоустойчивых 1-алгебр (Следствия 3.6.5 и 3.6.6);
(2) класс автоустойчивых 1-алгебр совпадает с классом счётных 1-алгебр с а -ка-тегоричной элементарной теорией, с точностью до добавления в язык конечного числа новых идеалов, определимых формулами первого порядка (Следствие 3.6.8).
К сожалению, некоторым недостатком Теоремы 3.6.1 является то, что она не даёт какого-либо простого способа построить или указать этот набор А\,..., Ддд), равно как и определить минимально возможное число элементов в нём. С другой стороны, Следствие 3.6.8 показывает, что алгебраическое строение автоустойчивых 1-алгебр фактически совпадает со строением счётных 1-алгебр с иькатегоричной теорией (последние будем называть и-категоричными 1-алгебрами). Напомним, что теория Т называется цькатегоричной, если любые две ее не более чем счётные модели изоморфны. Для большей точности отметим, что автоустойчивые I-алгебры всегда w-категоричны, а в обратную сторону ситуация описывается в пункте (2). В силу этих причин в начале Главы 3 приводится некоторое описа ниє w-категоричных І-алгебр, на основе которого в конце этой главы проводится дополнительное исследование строения автоустойчивых 1-алгебр.
Изучением а -категоричных 1-алгебр занимался ряд исследователей. Укажем краткую историю этой работы. Пусть булевы алгебры рассматриваются как модели языка Едл = (+,•,—,0,1), где + соответствует объединению элементов, пересечению, а — дополнению. На множестве всех идеалов в булевой алгебре А определим три операции: L\ + L2 = {х + у \ х Є L\, у Є L2}, L\ • L2 = L\ П L2 и Li - L2 — {x e A I Vy x(y Є L\ —у у Є L2)}. Множество всех идеалов в А с операциями +,•,- и 0 = {0}, 1 = А образует гейтингову алгебру.
Если А = {А ,1\,...,1\) — 1-алгебра, то через HQ(A) обозначим подалгебру в этой гейтинговой алгебре, порождённую множеством {І\,...,І\}. В [37] задача описания и/-категоричных 1-алгебр возникла в связи с изучением -категоричных колец, и там был найден критерий: А cj-категорична тогда и только тогда, когда множество HQ(A) конечно и число атомов в фактор-алгебре A/L конечно для всех L Є HQ(A). К сожалению, этот критерий ничего не говорил о многообразии типов изоморфизма таких А.
В [21, 38] Д.Е. Пальчуиовым была предложена некоторая система инвариантов, позволяющая эффективно перечислить эти типы изоморфизма. Позже А. Турай в [40, 41] нашел достаточно простую характеризацию элементарных теорий произвольных 1-алгебр, из которой можно вывести ещё одно описание а)-категоричных 1-алгебр.
В начале Главы 3 предлагается ещё одно описание, которое можно рассматривать как некоторый синтез идей и методов Д.Е. Пальчунова и А. Турая. Будем говорить, что 1-алгебра А псевдо-перазложима, если из А = А\ х А2 следует A = Ai или А = А2. Типы изоморфизма псевдо-неразложимых w-категоричных 1-алгебр A = (A , Ii,...,I\) могут быть заданы парами вида (Я, є), где Н — конечная гейтингова алгебра с А выделенными порождающими элементами, в которой 1/7 является неразложимым элементом, а Є {0,1} (Теоремы 3.2.5 и 3.2.6). При этом связь инварианта (Н,є) с алгеброй А состоит в том, что Н — это гейтингова алгебра Но(А) с выделенными элементами /і,...,Уд, а є отражает строение фактор-алгебры A/L, где L — наибольший элемент в Н\ {1ц} (такой существует в силу неразложимости Іп): є = 1, если A/L двухэлементна, и є = 0, если A/L безатомна.
В свою очередь, произвольная иькатегоричная 1-алгебра А разлагается в конечную прямую сумму псевдо-неразложимых, причём разложение минимальной длины единственно (Следствие 3,2.12 и Предложение 3.1.1). Тем самым её тип изоморфизма может быть задан конечной последовательностью (Н\,е{),..., (Нк,Єк), которая соответствует компонентам минимального разложения. Более того, по произвольной конечной последовательности таких пар мы с помощью некоторого алгоритма можем определить, соответствует ли она некоторому минимальному разложению (Предложение 3.1.2 и Следствие 3.2.11).
В качестве приложения этого описания для произвольных w-категоричных I-алгебр был получен критерий изоморфизма (Теорема 3.3.5), говорящий, что тип изоморфизма такой алгебры однозначно определяется строением гейтинговой алгебры Но(А) с добавленными к ней Д,..., І\ в качестве выделенных элементов, а также атомностью и числом атомов в каждой из фактор-алгебр A/L, L Є HQ{A).
Эти результаты из Главы 3 имеют чисто алгебраический характер, они никак не связаны с теорией вычислимости. Но оказывается, что в терминах инвариантов (Я, є) можно дать и достаточно простое описание типов изоморфизма автоустойчивых 1-алгебр. Об этом говорят Теорема 3.6.4 и Следствие 3.6.5: по паре (Я, є) можно легко определить, является ли соответствующая ей псевдо-неразложимая алгебра автоустойчивой, а произвольные автоустойчивые I-алгебры являются конечными прямыми произведениями алгебр такого вида.
Поскольку минимальное разложение единственно, это позволяет эффективно перечислить все типы изоморфизма автоустойчивых 1-алгебр (Следствие 3.6.7).
Описание автоустойчивых 1-алгебр опирается на весьма сложную технику, в основе которой лежит некоторая модификация Теоремы Гончарова о ветвлении. Её исходный вариант возник в [10] и был успешно использован в решении ряда задач, связанных с описанием автоустойчивых моделей. Она основана на использовании некоторой последовательности V-формул с рядом специальных свойств. В [1] была предложена новая версия этой теоремы, которая использовала V-формулы с константами из модели. К сожалению, её доказательство было неверным, и в Главе 3 доказывается новый вариант Теоремы о ветвлении, который уточняет некоторые идеи из [1], связанные с использованием констант в V-формулах. Его формулировка приведена в Теореме 3.4.1. Отметим, что эта теорема была также успешно использована в работе [15].
Несколько слов о связи глав диссертации друг с другом. Основная часть всех необходимых для понимания текста определений и обозначения (относящихся в первую очередь к теории вычислимости и булевым алгебрам) собрана во введении к Главе 1. Во введении к каждой из остальных глав, как правило, добавляется небольшое число новых понятий, которые не были определены ранее. Поэтому перед изучением какой-либо главы читателю стоит просмотреть введения ко всем предыдущим главам. В остальном главы диссертации практически не зависят друг от друга, и доступны для чтения в любом порядке. Напротив, внутри каждой главы части текста достаточно сильно связаны друг с другом, поэтому его лучше читать последовательно.
Критерий изоморфизма
Теперь нам понадобится некоторый признак изоморфизма для булевых алгебр с несколькими выделенными идеалами. Его первый вариант (для одного выделенного идеала) был доказан в [48], а идея фактически заимствована из [19]. Пусть А — алгебра и Н А — неглавный идеал. Следуя [19], последовательность {dn}nu из Н назовем главной в (А,Н), если верно: (1) dn ф 0 для всех п Є со и dni dni = 0 при щ ф щ; (2) если d Є Н, то d do + ... + dn для некоторого п Є ш; (3) для любого х Є А найдется такое щ Є со, что dn х или dn х = 0 при всех п По- Если d= {dn}neu} — главная последовательность в (А, Н) и ж Є Л, то положим h(x) = {neoj\dn x}. Если X, Y С со, то X / Y означает, что (X \ Y) U (Y \ X) — конечное множество. Легко заметить, что если х,у Є А и хАу Є Н, то / j(a;) / /j(y). Тем самым можно говорить о Ig{xjH), которое определено с точностью до Лемма 1.2.1. Пусть А,В — алгебры, Н А и L B — неглавные идеалы. Пусть также в А есть идеалы Но и Hi, где Но Q Н С Н\, а в В есть идеалы LQ и L\, где LQ С L С Ь\. Предположим, что d = {rfn}new и d = {d„}new — главные последовательности в (А, Н) и (В, L) соответственно, и (dn, Но П dn) = (d n, LQ П d n) при п Є со. Если существует изоморфизм j : А/Н — B/L, который переводит Hi/H в Li/L, и такой, что Ij(x/H) / I i ix/H)) для любого х Є А, то (А, Н0, Н, #0 (ДЬо, ). Доказательство. Для каждого п Є со зафиксируем изоморфизм f}n : (dn,H0 П dn) - (d n,L0 П d n). Положим Vi = {(a,b) Є А х В \ а Є Н,Ь Є L и а У}, V2 = {(а,Ь) Є АкВ\аН,Ъ L,-y(a/H) = b/L и рп{а dn) = b d n для любого п Є и} и V = V1UV2. Покажем, что V является критерием изоморфизма Воота для алгебр с выделенными идеалами.
В дополнение к обычным свойствам такого критерия нужно убедиться, что а Є Щ & b Є Li для любой пары (a, b) Є V и любых идеалов (Щ,Ь{) из набора (H0,LQ), (H,L), (H\,L\). Проверим лишь самое сложное свойство: пусть (а, Ь) V и а\,а% \ а. Докажем, что найдутся 61,62 6, для которых (оі,6і), (а2,62) Є V. Если (а, 6) Є V\, то все рассуждения очевидны. Пусть (а, 6) Є V2. Рассмотрим два случая: (1) аі Є Я, a2 $. Я. Существует такое п Є ш, что ai do + ... + dn. Найдем 6i dj +... + d n такое, что /?І(ОІ di) = 61 d для всех і яи положим b2 — b — bi. Нетрудно проверить, что (ai,&i) Є V\ и (02,62) Є V2. (2) ai,02 Я. Тогда ai/Я,Ог/Я a/Я, 7(«і/- ))7(аг/Я) 6/L и найдутся такие 6І,6 2 I 6, что 7(аі/Я) = б /Ь и 7(аг/Я) = 6 2/L. В таком случае id(ai) f /j.(6i) и /j(a2) / - () Соединяя вместе определения 7j, / и главной последовательности, получим: существует п Є и такое, что при любом т п верно одно из утверждений: (dm Oi&d b[Scdm a2 = 0&d 62 = 0), (dm ai = Qhd m b[ = 0kdm а2Ш п 62) или (dm-a = 0 -6 = 0). Образуем 6i, 62 I 6 так, чтобы выполнялось 6i — (d +...+d ) = b[ — (dg + +d ) и 62 - (dj +... + d n) = 6 2 - (d 0 +... + d n), 61 d\ = 0i(ai di) и 62 d\ = #(03 fk) для всех г п. Тогда (ai,6i) и (02,62) — искомые пары. Лемма доказана. Если А — алгебра и Но, Н А, то определим идеал Н -$ Н0 как множество {х Є А Уу $С х(у Є Я —» у Є Яо)}. Обычно элементы фактор-алгебры Л/Я определяются как классы эквивалентности. Если носитель А — подмножество и, то до конца этой главы элементы А/Н будем рассматривать как натуральные числа, выбирая для этого наименьший элемент из каждого класса х/Н и определяя операции естественным образом.
Предложение 1.2.2. (1) Пусть А — вычислимая алгебра, HQ,H,H\ A,HQC Н С HI и при этом Но вычислим и Я вычислимо перечислим. Предположим, что (С, М) — вычислимая алгебра с вычислимым идеалом и существует Д2-вычислимый изоморфизм h из (С,М) па (A/H,Hi/H). Тогда (A,HQ,H,H\) = (B,Lo,L,Li), где последняя модель — вычислимая алгебра с вычислимыми идеалами; (2) если при этом идеал Я — Но вычислим в А,Т С — некоторый вычислимый идеал и х ЄТ & h(x) Є (Я — HQ)/H, mo можно дополнительно добиться того, что L -» LQ будет вычислим в В; (3) в обоих случаях можно считать, что между моделями (Я, Яо) и {L,LQ), рассматриваемыми как алгебры Ершова с выделенным идеалом, существует частично вычислимый изоморфизм. Доказательство. Если идеал Я главный и равен а, то (1 — a, Hi П 1 — а) = (А/Н,Н\/Н) = (С,М). Следовательно, заменяя в разложении А = а х (1 — а) вторую часть на (С,М), получим (1) и (2). Поэтому далее считаем, что Я — неглавный идеал. Докажем сразу (1) и (2). Пусть {Ct}teu — такая вычислимая последовательность конечных алгебр, что Ct Ct+i С при t Є и и С = Ufew Ct- Можно считать, что Со двухэлементна. Индукцией по t построим Д -последовательность {h t}teu так, чтобы h t : Ct — А были изоморфными вложениями, h t С h t+1 и h t(x)/H = h(x)/H при t Є ш и х Є Ct- Определение h 0 очевидно. Допустим, что h t : Ct —У А определено. Пусть р — атом Ct, 1,-..,- атомы Ct+i nqi,...,qn \р. Достаточно описать построение h t+1 uaqi,..., qn. По условию h(qi)/H,..., h(qn)/H \ h t(p)/H. Пусть щ = hfa) h t{p) при і Є {1,..., п}.
Положим /i+1(gi) = аі + (h tip) - {ах +... + ап)) и h t+1(qi) = щ - (аі + ... + ОІ-І) при і Є {2,..., п}. Легко проверить, что h t+1(qi),..., h t+l(qn) /i t(p). Индукцией no t покажем, что в случае (2) можно дополнительно добиться эквивалентности х Є Т & h t(x) Є Я —у Но для х Є Ct. Пусть это верно для t; рассмотрим определение h t+l(qi). Если некоторый атом qi . Т, то по условию К+ІІЧІ) - Н — Но. Если же р Є Т, то /і е(р) Є Я —» Яо и эквивалентность заведомо выполняется. Допустим, что р Т. Пусть тогда для простоты qn Т. Если qiET для некоторого г п — 1, то u i+1(&) Є (Я — Яо) + Я. Используя оракул 0 , можно найти разложение h t+1(qi) = у + z, где г/ЄЯ— ЯоигєЯ, и положить ht+i(Qi) = У, "перемещая" z в h t+1(qn). Полагая теперь h = ЦЄш К получим Д "-вложение h : С —» А, где h (x)/H = h(x)/H, а в случае (2) ещё и і Є Т Л (ж) Є Н -У Щ при любом х Є С. Найдём вычислимую последовательность конечных функций {ht}teu такую, что ht: Ct — А и h(x) = Пт$_юо (#) Для х Є С. При этом можно считать, что каждое /і — изоморфное вложение Ct в Л (поскольку /I IQ такова), и вновь іЄГ«/г((і) Є Я - #о при а; Є С(.
Две вспомогательные конструкции и отношения а
Доказательство. Описание j для і = 0,..., 3 — несложное упражнение, каждое следующее выводится из предыдущего на основе леммы 2.3.7. Сделаем некоторые комментарии к переходу Необходимость списка условий: если А 4 В, то А 3 В и В з А, отсюда сразу следуют пункты (а) - (d). Условие \B/S\ 2", п Є и , равносильно существованию &і,...,Ьп1 в В таких, что bi содержат бесконечное количество атомов. Условие At(J3/.F) п — существованию bi,...,bn Є В таких, что Ь{ — атомные элементы, bi bj = 0 при і ф j и bi/F = В(1). Исходя из описаний такого вида, нетрудно проверить необходимость каждого из условий (е) - (і). Достаточность: пусть bi,...,bn\l в В. Покажем, что существуют а\,..., ап\\ в А такие, что bi 3 &{ Можно считать, что набор Ь\,... ,Ьп разбивается на четыре части: b\,...,b — элементы с конечным числом атомов; Ь[,...,Ь к — атомные элементы, Ц/F = 1; b [,...,b"m — атомные элементы, $4/F\ = со; b { ,...,Щ — неатомные, с бесконечным числом атомов под ними. Тогда At(.B/.F) к, 9(B) к + т, \B/S\ 2k+m+l, и для А верны аналогичные неравенства. Рассмотрим только случай / ф 0, как наиболее сложный. Стратегия выбора оц,... ,ап такова: 1) а[,..., а к Є А — такие атомные элементы, что a i/F = 1. Если А = (а[ + ... + а к) ФЛЬ то 2) 0,1,...,0, — такие атомные элементы из А\, что a" $. F(A), и если А\ = (а [ + ... + а т) Ф А2,— такой набор всегда можно найти; 3) А2 нетрудно разделить на элементы а\,...,а и а ",..., а" с нужными свойствами, так как А2 неатомна. Для завершения доказательства нужно рассмотреть еще случаи I = 0, га Ф 0 и I = 0,тп = 0, что несложно. Лемма доказана. Заключительная глава диссертации посвящена в первую очередь алгебраическому описанию класса автоустойчивых 1-алгебр. Повторим наиболее важные определения и введём несколько новых. Вычислимая модель А называется автоустойчивой, если для любой изоморфной ей вычислимой модели А\ существует вычислимый изоморфизм / : А - А\, т.е. изоморфизм, одновременно являющийся вычислимой функцией на А
Отношение вычислимого изоморфизма разбивает все вычислимые изоморфные копии А на классы эквивалентности. Число таких классов называется алгоритмической размерностью, или авторазмерностъю A, dimc{A). Класс коиструктивизаций модели А эффективно бесконечен, если по любой вычислимой последовательности коиструктивизаций {Ап}пЄіІ) (т.е. по её индексу) можно эффективно построить новую вычислимую модель В = А, которая не является вычислимо изоморфной никакой АП1 пЄш. Легко понять, что в этом случае dime (Л) = и. Напомним, что V-формулы первого порядка — это формулы вида Vxi. ..Ухкф, где ф — бескванторная формула. Аналогично, Э-формулы имеют вид Зхі... Зхкф. Как и раньше, { Pk}keu стандартная нумерация всех одноместных ч.в.ф., ipk(x) — функция с номером к, a y k,t(x) результат её вычисления через к шагов. l-алгеброй называется модель вида А = (А1, Д,..., /д), где А — булева алгебра, а 1\,... ,1\ — идеалы в А , выделяемые соответствующими одноместными предикатами; при Л = 0 это просто булева алгебра. Все рассматриваемые в этой главе 1-алгебры считаются счётными, если не оговорено противное. Если х Є А, то через ХА обозначаем 1-алгебру (х, ДПх,..., 1\Г\х). Легко проверить, что А = а\ х...хап для любых аі,...,ап 1 в Л. Идеалы в 1-алгебре А — то же самое, что и в соответствующей булевой алгебре А . Об основных результатах этой главы уже было сказано во Введении к диссертации.
В наиболее сложной и объёмной её части, в 3.5, доказывается серия условий, необходимых для автоустойчивости 1-алгебры. На основе этих условий в 3.6 устанавливается критерий автоустойчивости 1-алгебры (Теорема 3.6.1). Основным инструментом для исследования автоустойчивости является некоторая модификация Теоремы Гончарова о ветвлении. Эта модификация формулируется и доказывается в 3.4 (Теорема 3.4.1). Как пример того, что и эта формулировка может быть легко усилена разными способами в случае необходимости, в конце параграфа приводится усиленная версия этой теоремы, в которой допускается бесконечный язык и вычислимые конъюнкции V-формул (Теорема 3.4.4). В конце 3.6 проводится также дополнительное исследование структуры класса автоустойчивых 1-алгебр. Оно основано на некотором описании w-категоричных 1-алгебр, построению которого посвящены 3.1 и 3.2. 1-алгебру А, следуя [34], называем псевдо-неразложимой, если из А = А\ х Аъ следует А = А\ или А = А . Теория Т называется и-категоричной (или счётно категоричной), если любые две её не более чем счётные модели изоморфны. 1-алгебра А и-категорична, если её элементарная теория обладает этим свойством. Это означает, что условия А = В н А = В равносильны для любой не более чем счётной модели В. В 3.1 доказываются некоторые вспомогательные факты о псевдо-неразложимых І-алгебрах. В 3.2 строится описание псевдо-неразложимых иькатегоричных 1-алгебр через пары (Н,є), а произвольных w-категоричных — через их прямые произведения. В 3.3 в качестве приложения этого описания выводится простой критерий изоморфизма для о)-категоричных 1-алгебр.
Алгебраические инварианты
Недостатком этого описания является то, что оно не дает нам какой-либо системы инвариантов, однозначно определяющих типы изоморфизма таких алгебр. Кроме того, неясно, как связано число атомов в A/L при различных L Є Щ{А): например, число атомов в A/{L\ L2) всегда не превосходит сумму числа атомов в A/Li и A/L2. Из этого описания следует, что класс ( -категоричных 1-алгебр замкнут относительно прямых произведений и прямых слагаемых. Ниже будет доказано, что на самом деле тип изоморфизма счётной w-категоричной I-алгебры А однозначно определяется строением множества HQ{A), а также числом атомов и существованием безатомного элемента во всех фактор-алгебрах A/L, L Щ(А). Второе описание класса w-категоричных 1-алгебр появилось в работах [21, 38]. Оно опиралось, в частности, на идею работы с псевдо-неразложимыми 1-алгебрами. Там было доказано, что любая w-категоричная І-алгебра представима в виде конечного произведения псевдо-неразложимых, и найдена система характеристик, позволяющая перечислить их типы изоморфизма.
К сожалению, это описание основано на использовании некоторой последовательности формул {Vn}necJ, которая не очень удобна при работе с автоустойчивыми 1-алгебрами. В [40,41] была найдена характеризация элементарных теорий 1-алгебр, на основе которой возник третий подход к описанию нашего класса. Ниже мы предлагаем некоторое упрощение этого описания, основанное, как и в [21, 38J, на работе с псевдо-неразложимыми 1-алгебрами. Гейтинговой алгеброй называем модель вида (Я, +,,—»,0,1), где (Я,+,-,0,1) — дистрибутивная решетка с 0 и 1, а х —» у — наибольший элемент в множестве {z Є Н z х у}. Множество всех идеалов в булевой алгебре А образует гей-тингову алгебру с указанными выше операциями +, и — , 0 = {Од/} и 1 = А . Тогда Н0{А) — подалгебра в этой гейтинговой алгебре, порожденная множеством {1\,...,1\}. Обозначим гейтингову алгебру (#0(А),+, ,-», 0,1,/г,. ..,/л) с выделенными порождающими элементами 1Х,..., Д как Н{А). Это будет модель языка (+, , —f, 0,1, ei,..., ел), где ЄІ — константы. Алгебра Я(А) будет основным инструментом нашего исследования. Лемма 3.2.2. (1) Если х Є А, то отображение L н ЬПх является гомоморфизмом из Н(А) па Н(х). Оно также является единственным гомоморфизмом из Н{А) в Н(х); (2) если Хі,...,хп 1 в А, то Н(А) изоморфна подалгебре в Н(х\) х ... х Н(хп), порожденной выделенными элементами. Доказательство. (1): нетрудно проверить: если х Є А, Ь\,Ь2 А и — одна из операций {+, , - }, то (Li д L2) П х — {L\ П х) $ {L% П х). Отсюда следует, что указанное отображение является гомоморфизмом. Поскольку любой элемент Н(А) представим термом от /i,..., 1\, такой гомоморфизм единственен. (2): изоморфизмом будет отображение L ь- (LDxi,..., ЬПхп). Лемма доказана. Приведем теперь описание элементарных теорий 1-алгебр из [40, 41]. Оно основано на использовании еще одного класса алгебр, названного Тураем гейтин-говыми sa-алгебрами. Это модели вида (Я, +,-,-)-,0,l,sa), где (Я,+,-,- ,0,1) — гейтингова алгебра, a sa — одноместная операция, удовлетворяющая тождествам: (i) (sa(x) -» х) - х = sa(x); (ii) х sa(y) = х sa(x у).
Определив на множестве всех идеалов в булевой алгебре А операцию sa(7) как {х Є А х/1 — безатомный элемент в А /1}, мы получим гейтингову sa-алгебру; все её подалгебры тоже будут лежать в этом классе. В [41] доказано и обратное — любая гейтингова sa-алгебра представима как подалгебра в алгебре такого вида. Для 1-алгебры А = (А ,/і,..., 1\) обозначим через Т А подалгебру в гейтинговой sa-алгебре всех идеалов А , порожденную множеством {Д,..., 1\}, с выделенными элементами I\,...,I\. Это будет модель языка (+, , — , 0,1, sa, е\,..., ед). Ясно, что идеалы из Н(А) образуют подмножество Т А; В общем случае они не равны. Если V — гейтингова sa-алгебра, то положим М(Т ) = {х Є V \ х — максимальный элемент в V \ {1} и sa(x) = х}, где максимальность рассматривается относительно обычного порядка в решетке V. Это множество может быть пустым. Функцию Г)А : M(VA) — и \ {0} U {оо} определим так: T]A(L) — число атомов в A/L. Это число не может быть нулем, так как A/L — ненулевая атомная алгебра при L Є М(Т А). Следующая теорема говорит о том, что пары (T A,VA) ПОЛНОСТЬЮ описывают элементарные теории 1-алгебр. Отметим, что в [41] эта теорема доказана для произвольного множества выделенных элементов, а не только конечного. Кроме того, І-алгебра в ней не обязательно счётна.
Необходимые условия автоустойчивости
В оставшейся части этой главы основным объектом будут 1-алгебры — модели вида (А, Д,..., 1\), где А — булева алгебра, а Д,..., /д — выделенные идеалы. Число Л, как правило, будет фиксированным, исключения будут специально оговариваться. Все рассматриваемые I-алгебры будут счётны. Напомним: если Іі,І2 А — два идеала в А, то можно определить три операции: Д Если через а для а Є А мы обозначим булеву алгебру, образованную множеством {b Є А \ b а}, то, как уже отмечалось в главе 3, эти операции будут перестановочны с переходом ІИЙ, т.е., например, (Д - л /г) П а = (/і П а) — а (/г Па). В силу этого будем избегать громоздких обозначений, связанных с различием между А и а. Пусть (А, Д,..., /д) — І-алгебра иібА Его характеристикой называем множество Рх = {п Л х 1п}. Легко проверить, что PQ = 0, Рх Ру при ж у и Р-с+з, = Рх U Ру (считаем, что порядок на характеристиках совпадает с включением С). Если, например, Рх = {1,..., }, то используем запись Рх— {h, - - , Iq, Iq+U ---J )- Данная работа посвящена изучению алгоритмической размерности 1-алгебр. Нетрудно заметить, что если (Л, Д,..., Д) — 1-алгебра и L А — некоторый идеал, определимый в (А, Д,..., 1\) бескванторной формулой, то при добавлении в язык нового предиката Q, выделяющего L, алгоритмическая размерность (А, Д,..., Д) не изменится. Будем говорить, что (А,Д,...,ід) замкнута относительно пересечений идеалов, если для любого {ii,...,ik} Q {! А} конечное пересечение /ij П ... П 1(к совпадает с 1п для некоторого п; и, кроме того, 1т — {0} и Д = А для некоторых m,s Л. Очевидно, что из любой алгебры (Л, Д,...,Д) можно получить замкнутую относительно пересечений идеалов, добавив в язык новые идеалы для {0}, А и всех конечных пересечений, и алгоритмическая размерность от этого не изменится.
Поэтому далее считаем, что все рассматриваемые 1-алгебры замкнуты в указанном смысле, если не оговорено противное. Лемма 3.5.1. Пусть В — булева алгебра, М, Li,..., Ln В — некоторые идеалы и х Є В. (1) если х $. M,Li,... ,Ln и х/М — безатомный элемент, то найдутся такие y,z\x, что у & Li,...,Ln,M и z g М; (2) если х $. Li,...,Ln и x/Li,...,x/Ln — безатомные элементы, то найдутся такие y,z \ х, что y,z L\,..., Ln. Доказательство. (1): рассуждаем индукцией по п. Случай п = 1: найдем такие 1,2 х, что х\,Х2 $. М, тогда либо х\ найдем х\,Х2 х со свойством X\,X2 . М. Пусть Xi Ln+i. Если х\ $. L\,...,Ln, то у = х\ и z = х-2 — искомая пара. Если же, например, х\ 6 L\,...,LS и По предположению индукции найдется такое разбиение х 2,х2 Тогда можно взять У = Х\ + х2 и z = х2. (2): положим М = L\ и, пользуясь (1), найдем такие y\,z\ \ х, что у\ L\ и z\ Li,...,Ln. Далее, найдем такие y2,z2 z\, что у2 . L2 и z2 & Li,...,Ln. Продолжая в том же духе, дойдем до уп, zn, где уп Ln и zn Lu..., Ln. Тогда у = уі + ... + уп и z = zn — искомое разбиение. Лемма доказана. Следствие 3.5.2. Пусть А — І-алгебра, х Є А — элемент характеристики Р. (1) если х 1д для некоторого q Л и x/Iq — безатомный элемент, то найдутся такие y,z \ х, что Ру = Р и z . Iq; (2) если Р = (їі,...,їч,Ід+і,...,1\) и х/Іі,...,x/Iq — безатомные элементы, то найдутся такие y,z\x, что Ру = Pz — Р. Элемент х I-алгебры А называем разложимым, если существует представление х = х\ + .. .+хп, где п 1 и PXi Рх для всех і п, и неразложимым в противном случае. Лемма 3.5.3. Для любого х Є А найдется такой набор неразложимых элементов х\,... ,хп, что xi,... ,хп х. Доказательство. Индукция по \РХ\. Если Рх = 0, то х = 0 и лемма, очевидно, верна.
По предположению индукции каждое ХІ раскладывается в сумму неразложимых. Лемма доказана. Введем понятие регулярной I-алгебры. Пусть (А, 1\,..., 1\) — 1-алгебра и п Л. Через /+ обозначим Хлтс/„ т- Если І" = W ТО считаем /+ = {0}. Тогда /+ является идеалом. Говорим, что А п-регулярна, если выполняется одно из условий: (1) 1% = h для некоторого к Л; (2) 1п = А и A/I+ а В(1). 1-алгебра А регулярна, если она п-регулярна для всех п А. Заметим, что хотя понятие п-регулярности является достаточно наглядным (оно описывает связь идеала со всеми меньшими) и легко проверяемым, работать с ним очень неудобно, так как операция 1п н- /+ не перестановочна с переходом А к- а, а п-регулярность не сохраняется при этом переходе. Определим регулярность в других терминах. Если Р — некоторая характеристика, то Р-идеал — {х \ Рх Р}, Р-сумма — сумма Р -идеалов для всех Р Р. Если Р = 0, то считаем, что Р-сумма равна Р-идеалу (который равен {0}). Легко проверить, что Р-идеал и Р-сумма являются идеалами, и что операции образования Р-идеала и Р-суммы перестановочны с переходом Лн4 а. Отметим также, что Р-идеал сохраняется при переходе к подалгебрам (если В Л, то Р-идеал в В равен пересечению В и Р-идеала в Л), а для Р-суммы это неверно. 1-алгебра А Р-регулярна, если выполняется одно из условий: (1) Р-сумма равна Р-идеалу; (2) Р-сумма равна / для некоторого к Л; (3) Р-идеал совпадает со всей А, а Р-сумма — максимальный собственный идеал в А Доказательство. Предположим, что А регулярна и Р — некоторая характеристика. Если в А нет элементов а с Ра = Р, то Р-идеал совпадает с Р-суммой. Пусть существует такой а Є А, что Ра = Р. Если Р = (Ii,...,Iq,/?+ь...,1\), то Р-идеал, очевидно, равен її П ... П Iq и равен некоторому In, п q. Нетрудно проверить, что в этом случае Р-сумма совпадает с J+: если Р Р, то Р -идеал равен 1т для некоторого т Л и 1т С 1п. Если же 1т С /„, то q + 1 га Л и Рх Р для всех В обратную сторону: пусть А Р-регулярна для всех Р и п Л. Рассмотрим характеристику Р = {1,..., А} \ {га /„ С 1т}. Пусть для простоты обозначений Р = (Д,... ,/„,/n+1,. ..,/д). Как уже было замечено, тогда Р-идеал совпадает с 1\ П ... П /„ = /„. Вновь Р-сумма совпадает с /+: если х Є Іт и 1т С /„, то п + 1 т ХпРх Р. Наоборот, если Рх Р, то х Є Іт для некоторого га, п + 1 т А, /„ % 1т, х Є /„ П /т С /„ и х Є /+. Получаем, что Л п-регулярна. Лемма доказана. Говорим, что А кусочно Р-регулярна, если А = А\ Ф ... ф Ап, где все А{ Р-регулярны, и кусочно регулярна, если все А{ регулярны. Лемма 3.5.5. Пусть А — 1-алгебра и Р — некоторая характеристика. Верно по крайней мере одно из двух утверждений: (1) А кусочно Р-регулярна; (2) найдутся такие b\,b2,b$ Є А, что Ьг- fy = О при і ф з, b\,b2 — неразложимые элементы характеристики Р, аЬз — разложимый элемент характеристики Р. Доказательство. Пусть Р = {1\,...,1р, 1р+\, ...,1\). Обозначим через М Р-идеал, через L — Р-сумму, через N — (L - 1р+{) + ... + (L — 1\). Нетрудно заметить, что неразложимые элементы характеристики Р — в точности элементы М \ L. Предположим сначала, что существует дизъюнктный набор bi,b2,d, для которого &i, Ь2 Є М \ L, a d N. Тогда d $. L - Ik для всех к, р + 1 к X, и найдутся d d, лежащие в L\Ik- Если 63 = d p+1 + ... + d \ то h,b2,b3 — нужный для (2) набор.
