Вычислимость и разрешимость в классе булевых алгебр

Диссертация посвящена решению некоторых проблем из теории вычислимых (конструктивных) моделей. Её- основные результаты относятся к вычислимым булевым алгебрам, хотя некоторые рассматриваемые вопросы имеют более широкий характер. Теория вычислимых моделей возникла в 50-х годах прошлого века в работах А. И. Мальцева. О. Рабина и др. и с тех нор активно развивается. Объём литературы, посвященной этой теме, очень велик. В качестве наиболее важных и современных источников можно указать [11, 30, 35]. Булевы алгебры, в свою очередь. тоже являются классическим объектом, привлекающим внимание математиков уже в течение полутора веков. Попытка собрать хотя бы основные достижения в этой области привели к появлению в 1989 году трёхтомного справочника [34].

Вычислимые булевы алгебры нашли многочисленные приложения в теории алгоритмов, математической логике, теории моделей и др. областях. Хорошим источником по этой теме является монография (9). в которой представлены, впрочем. достижения в первую очередь новосибирского коллектива математиков, являющегося одним из лидеров в данной области. Диссертация является, в частности, естественным продолжением этой монографии — она отвечает на некоторые поставленные там вопросы и развивает ряд затронутых тем. Неплохим обзором яв-ля™" [31].

Напомним, что модель Д конечного языка называется вычислимой, если её- носитель — вычислимое подмножество множества натуральных чисел ш, а операции и предикаты — вычислимые функции па этом подмножестве. В свою очередь, под вычислимыми функциями понимаются т. е. которые могут быть вычислены с помощью некоторой машины Тьюринга, а под вычислимыми множествалш — обладающие вычислимыми характеристическими функциями. Понятие конструктивной модели даёт нам другой подход к тому же классу объектов, который фактически основан на использовании другого языка, немного более подробно связь между ними обсуждается в начале Главы 1. Говорим, что произвольная модель, А кон-структивизируема. если она изоморфна некоторой вычислимой модели.

Центральными проблемами теории вычислимых моделей являются вопрос о том, какие модели являются конструктивизируемыми. и пасколько велико число различных вычислимых представлений у данной модели. Последнее понятие, число различных представлений, может пониматься в разных смыслах, и в литературе рассматривается несколько подходов, которые сводятся к разным определениям «эквивалентных» представлений. В настоящей диссертации используется наиболее сильный подход: две вычислимые модели А1, А2 считаются «эквивалентными», если между ними существует вычислимый изоморфизм /: А —* А2, то есть изоморфизм, одновременно являющийся вычислимой функцией на носителе, А В этом случае мы говорим, что модели, А и А2 вычислимо изоморфны. Изучение этой темы было начато А. И. Мальцевым, который в |17] назвал автоустойчивыми тс модели, у которых всс вычислимые представления вычислимо изоморфны. Максимальное число вычислимых представлений модели А, которые не являются вычислимо изоморфными друг другу, называется алгоритмической размерностью модели А, <Шпс (-4), или авторазмерностъю (это понятие было впервые введено в №.

Когда мы говорим о булевых алгебрах, в первую очередь разумно задаться вопросом об описании тех из них, которые являются конструктивизируемыми. К сожалению, на данный момент эта задача представляется неразрешимой — этот класс очень велик, и нет никаких разумных гипотез о его алгебраической характе-ризации. При этом существует несколько способов сводить проблему такого описания к некоторым другим: например, булева алгебра, А конструктивизируема тогда и только тогда, когда она может быть порождена некоторым вычислимым линейным порядком (см. [9)). Этот факт позволяет нам свести описапие конструктиви-зируемых булевых алгебр к описанию конструктивизирусмых линейных порядков. К сожалению, последняя задача является ещё- более сложной, чем предыдущая. Точно так же от вычислимых булевых алгебр можно перейти к вычислимым бинарным деревьям, или булевым кольцам.

Но при этом для некоторых важных подклассов булевых алгебр ситуация является не столь безнадёжной. Например, в |4] было найдено описание конструктиви-зируемых суператомных булевых алгебр — критерием оказалась конструктивность ординала, который является естественным рангом алгебры. В (20) была получена некоторая характеризация конструктивных атомных булевых алгебр: атомная алгебра, А конструктивизирусма тогда и только тогда, когда ее факторизация по идеалу Фреше А/Г является Дз-коиструктивизируемой (т.е. конструктивизируе-мой с оракулом 0″). В [20. 24] было получено ещё- несколько результатов, подобных.

В Главе 2 решается проблема описания конструктивизируемых^{-однородных} булевых алгебр. Счётная метель, А является и)-однородной, если для любых двух наборов её- элементов а. Ь одинаковой длины из элементарной эквивалентности {А, а) = (А, Ь) следует изоморфизм (Л, а) э? [А, Ь). Отметим, что для произвольной (не обязательно счётной) модели понятие ¡-¿—однородности обычно определяется иначев счётном же случае эти определения равносильны.

Предлагаемое решение основано на описании произвольных, не обязательно вычислимых,^{-однородных} булевых алгебр, полученном в [18]. Подробно об этом описании говорится в пачале Главы 2, пока же приведём только условную формулировку: такие алгебры могут быть естественным образом охарактеризованы через последовательность (po.pi—). где р&bdquoлежащие в множестве {0,1} некоторые алгебраические инвариантыпри этом любой такой последовательность из 0 и 1 соответствует некоторая алгебра. Вопрос тем самым сводится к тому, какие из этих последовательностей соответствуют конструктивизируемым алгебрам. Эта проблема, в частности, формулировалась в сборнике проблем математической логики 116], частичный ответ (некоторые необходимые и некоторые достаточные условия) ранее был дан в [24].

Ответ на этот вопрос удалось получить в чисто алгоритмических терминах: для этого было предложено некоторое обобщение иерархии Фейнера 0'и'-вычислимых функций ([33]) — более точно, была предложена более тонкая иерархия, которая включает в себя классы Фейнера в качестве частного случая. В терминах этой иерархии были охарактеризованы как вычислимые, так и ©-'" '-вычислимые неоднородные булевы алгебры, дая каждого п е и> (Теорема 2.1.3). В частности, с помощью этого описания можно легко повторить построение хорошо известного и очень сложного примера ©-'-вычислимой и неконструктивизируемой булевой алгебры, который был найден Фейнером в |33]. Кроме того, описание нозволяет показать, что при росте п класс 0'" '-вычислимых однородных алгебр строго увеличивается (Следствие 2.1.9). Содержательность (т.е. в определённом смысле невырожденность) новой иерархии показана в Предложении 2.1.8.

В качестве некоторого дополнительного результата в Главе 2 строится общая конструкция (Теорема 2.3.9), которая обобщает указанные выше теоремы из [20] и |24| и позволяет получить много новых критериев, имеющих следующий общий вид: булева алгебра, А конструктивизируема <=$¦ фактор-алгебра А/Т (А) 0(а)-конст-руктивизируема, где п — некоторый конструктивный ординал, а Т — соответствие, каждой алгебре, А сопоставляющее некоторый идеал Т (А) С А. Теорема говорит о том, при каких условиях напи Т критерий такого вида имеет место. Некоторые примеры сё- использования можно найти в Следствии 2.3.10. Отметим, что эта общая конструкция, названная в Главе 2 «'метатеоремой для фактор-алгебр», была впоследствии обобщена автором на случай булевых алгебр с одним выделенным идеалом в (49). Кроме того, на её- основе удалось описать вычислимые семейства суператомных булевых алгебр ([44|). В настоящую диссертацию последние результаты не включены для сокращения объёма текста.

Если у данной модели существует какое-то вычислимое представление, то иногда бывает важно знать, обладает ли она вычислимым представлением с какими-то дополнительными алгоритмическими свойствами, например, в котором вычислимыми являются некоторые дополнительные определимые отношения и операции, не входящие в язык этой модели. В одной из наиболее общих постановок этот вопрос сводится к существованию сильно вычислимых представлений: вычислимая модель называется сильно вычислимой, если в ней вычислимым является любое отношение, определимое некоторой формулой первого порядка, и при этом «равномерно» по формуле. Другими словами, если существует алгоритм, который по формуле Ц>{Х., хп) и набору элементов (??,., а&bdquoопределяет, истинна ли эта формула на этом наборе. Более строгое определение этого понятия приведено в начале Главы 1.

Ю.Л. Ершов в [12| показал, что сильно вычислимые булевы алгебры могут быть охарактеризованы следующим образом: существует вычислимая последовательность одноместных формул <�Р1(х), 1р2(х), языка булевых алгебр такая, что вычислимая булева алгебра, А сильно вычислима тогда и только тогда, когда все <�р,(х) вычислимы в ней равномерно по г. то есть является вычислимым множество {(¿-.я) € х, А | А (= ^(г)}. Эта последовательность формул имеет естественный алгебраический смысл: <рЛх)> например, говорит, что х — атом,^г (гв) что х — безатомный элемент. <�рз (х) — атомный, и т.н. Позже С. С. Гончаровым в |9] было доказано, что вычислимость первых га формул ч>(х).<�Рп (х) равносильна п-вычислимости А: последнее означает, что в, А равномерно вычислимы все свойства, определимые Е"-формулами.

В [6] было ноказано, что существует булева алгебра А, которая п-вычислима для любого леи (без равномерности по га), но при этом не является сильно кон-структивизируемой, т. е. не изоморфна никакой сильно вычислимой модели. Если же мы будем рассматривать булевы алгебры с фиксированной элементарной теорией (от которой в первую очередь зависит структура формул), то определенная связь между п-вычислимостью и сильной вычислимостью возникает. Пусть Т — некоторая теория первого порядка. Определим следующую характеристику: положим ст (Т) = тш{га € и> | любая п-вычислимая модель теории Т обладает сильно вычислимым представлением}, и сш (Г) = оо, если указанного га не существует. Эта величина некоторым образом характеризует сложность моделей Т. она показывает, формулы какого уровня сложности необходимо уметь вычислять в данной модели для того, чтобы гарантировать возможность вычисления всех формул — если не в самой модели, то по крайней мере в некоторой её- изоморфной копии (более правильно устроенной). В частности, если Т модельно полна, то ст (Т') = 0.

Основным результатом Главы 1 является описание ст (Т) для всех элементарных теорий булевых алгебр, т. е. теорий вида ТЬ (Л) — {<р — предложение! А (= (?>}, или, что-то же самое, полных расширений теории всех булевых алгебр. Заметим, что для любой теории Т сга (Т) = вир{еш (Г') | Т' — полное расширение У}. В случае булевых алгебр ст (Т) имеет дополнительный алгебраический смысл — она равна наименьшему га, при котором сильная конструктивизируемость алгебры с теорией Т равносильна существованию вычислимого представления с вычислимыми формулами V?! (х).>рп (х).

Напомним, что элементарные теории булевых алгебр были описаны Тарским и.

Ершовым в [42] и |12): они могут быть заданы через тройки некоторых алгебраических инвариантов (п. к. е), где п, к е ш и {оо}, а е е {0,1}. В силу этого вместо ст (Т) будем использовать запись ст (п, к, е). Из той же работы |12] нетрудно вывести верхнюю оценку: сш (п+1. к, 0) ^ 4п+3 и сш (п+1, к. 1) < 4п+4 при п. к < ос. а сш (п + 1. оо, е) ^ 4п + 5. Исследование вопроса о точной величине ст (п, к, е) имеет долгую историю. Например, в [5] было доказано, что ст (0, оо. е) = 1- упомянутый выше пример из [6] показывает, что ст (оо, 0,0) = оо (при этом обозначение ст (Т) в тех работах не использовалосьоно было предложено автором диссертации). Затем различным частным случаям был посвящен ещё- ряд работ С. С. Гончарова. С. П. Одинцова и В Н. Власоваболее подробно история этих исследований указаг на в начале Главы 1. Проблема полного описания ст (п. к. е) была сформулирована, в частности, в (35|. а также в [16. 8, 9|. Её- полное решение приведено в Теореме 1.3.4.

Перейдём теперь к вопросу о числе конструктивизаций. Для булевых алгебр он был независимо решён в [10] и (39]: если, А — вычислимая булева алгебра, то сПтс (Л) 6 {1-^}, причём сНтс (А) = 1 тогда и только тогда, когда число атомов в, А конечно. Модель, А с (ШпсСА) = 1 называем автоустойчивой: все её- вычислимые представления вычислимо изоморфны друг другу. Описание автоустойчивых булевых алгебр является, очевидно, исчерпывающим: в счётном случае строение алгебр с конечным числом атомов тривиально и хорошо известно. Они разлагаются в прямое произведение безатомной и конечной алгебр, тип изоморфизма последней определяется числом атомов, а первая может быть лишь одного из двух типов: нулевой и счётной ненулевой.

Глава 3 посвящена описанию автоустойчивых булевых алгебр с конечным числом выделенных идеалов (I-алгебр), т. е. моделей вида (А', 1.1). где А' — булева алгебра, а 1,. ,/л — идеалы в А', выделяемые добавленными в язык А' новыми одноместными предикатами. Этот класс моделей тесно связан с булевыми алгебрами: например, в [48] доказано, что тип изоморфизма любой счётной и достаточно сложно устроенной булевой алгебры, А (например, неразложимой в прямое произведение атомной и безатомной алгебр) однозначно определяется 1-алгеброй (А/БуЕ/Б), где Е — идеал Ершова-Тарского, а 5 — идеал, порождённый атомами и безатомными элементами. Эта связь продолжается и на случай вычислимых алгебр: например, булева алгебра, А обладает 3-вычислимым представлением тогда и только тогда, когда (A/S.E/S) 0'-конструктивизируема.

В [14| было найдено описание автоустойчивых I-алгебр с одним выделенным идеалом, т. е. моделей вида (А1, /,), оно также оказалось достаточно простым. Однако по мере роста числа выделенных идеалов, А сложность автоустойчивых I-алгебр резко возрастает, и уже при Л = 3 они образуют достаточно большой и нетривиально устроенный класс. В Теореме 3.6.1 указан алгебраический критерий автоустойчивости произвольной I-алгебры А. Для упрощения формулировки он приведён только для алгебр, в которых набор выделенных идеалов {/j./а} замкнут относительно пересечений, а также содержит идеалы {0} и А. Чтобы применить его к произвольной I-алгебре, нужно соответствующим образом пополнить набор {/]. /л} — такое пополнение не меняет алгоритмическую размерность.

Теорема 3.6.1 говорит также о том, что dimc (, 4) € {l, w} для любой 1-алгебры, А = (А', h./а). Из неё- нетрудно вывести два важных следствия:

1) для каждого фиксированного, А есть конечный набор I-алгебр А.. A/ja). конечные прямые произведения элементов которого образуют класс всех автоустойчивых I-алгебр (Следствия 3.6.5 и 3.6.6);

2) класс автоустойчивых I-алгебр совпадает с классом счётных I-алгебр с и)-категоричной элементарной теорией, с точностью до добавления в язык конечного числа новых идеалов, определимых формулами первого порядка (Следствие 3.6.8).

К сожалению, некоторым недостатком Теоремы 3.6.1 является то, что она не даёт какого-либо простого способа построить или указать этот набор А[.А/(), равно как и определить минимально возможное число элементов в нём. С другой стороны. Следствие 3.6.8 показывает, что алгебраическое строение автоустойчивых I-алгебр фактически совпадает со строением счётных I-алгебр с w-категоричной теорией (последние будем называть и-категоричными 1-алгебрами). Напомним, что теория Т называется w-категоричной, если любые две её- не более чем счётные модели изоморфны. Для большей точности отметим, что автоустойчивые I-алгебры всегда и-категоричны, а в обратную сторону ситуация описывается в пункте (2). В силу этих причин в начале Главы 3 приводится некоторое онисапие .¿—категоричных 1-алгебр, на основе которого в конце этой главы проводится дополнительное исследование строения автоустойчивых 1-алгебр.

Изучением^{-категоричных} 1-алгебр занимался ряд исследователей Укажем краткую историю этой работы. Пусть булевы алгебры рассматриваются как модели языка Ев<4 = (+., —, 0,1), где + соответствует объединению элементов, ¦ пересечению, а — дополнению. На множестве всех идеалов в булевой алгебре А' определим три операции: ?1 + Х^ = {х + у | х 6 Ь, у € ?1 • Ьг = Ь П Ьг и Ьъ = {г 6 А' | Уу ^ ту 6 Ь —> у 6 ¿-г)}- Множество всех идеалов в Л' с операциями +.-.—" и 0 = {0}. 1 = А образует гейтингову алгебру.

Если, А = (А1, ¡-1./д) — 1-алгебра, то через На (А) обозначим подалгебру в этой гейтинговой алгебре, порождённую множеством {/1./л}. В [37] задача описания^{-категоричных} 1-алгебр возникла в связи с изучением (¿—категоричных колец, и там был найден критерий: А о>-категорична тогда и только тогда, когда множество Н0(А) конечно и число атомов в фактор-алгебре А/Ь конечно для всех Ь 6 Н0(А). К сожалению, этот критерий ничего не говорил о многообразии типов изоморфизма таких А.

В [21, 38] Д. Е. Пальчуновым была предложена некоторая система инвариантов, позволяющая эффективно перечислить эти тины изоморфизма. Позже А. Турай в [40, 41] нашел достаточно простую характеризацию элементарных теорий произвольных 1-алгебр, из которой можно вывести ещё- одно описание ¡-¿—категоричных [-алгебр.

В начале Главы 3 предлагается ещё- одно описание, которое можно рассматривать как некоторый синтез идей и методов Д. Е. Пальчунова и А. Турая. Будем говорить, что 1-алгебра, А пссвдо-тразложима, если из, А = А х Аг следует, А = А или, А = А%. Типы изоморфизма псевдо-перазложимых^{-категоричных} 1-алгебр, А = (А', Д, — /*) могут быть заданы парами вида (Я. г), где Н — конечная гейтингова алгебра с, А выделенными порождающими элементами, в которой 1д является неразложимым элементом, а с е {0,1} (Теоремы 3.2.5 и 3.2.6). При этом связь инварианта {Н, е) с алгеброй, А состоит в том, что Н — это гейтингова алгебра Нц (А) с выделенными элементами А,. ,/а, а е отражает строение фактор-алгебры А/Ь, где Ь — наибольший элемент в Н {!#} (такой существует в силу неразложимости 1/)): е = 1. если A/L двухэлементна, и е = 0. если A/L безатомна.

В свою очередь, произвольная^{-категоричная} I-алгебра, А разлагается в конечную прямую сумму псевдо-неразложимых. причём разложение минимальной длины единственно (Следствие 3.2.12 и Предложение 3.1.1). Тем самым её- тин изоморфизма может быть задан конечной последовательностью (H?. ?,),?*)• которая соответствует компонентам минимального разложения. Более того, по произвольной конечной последовательности таких пар мы с помощью некоторого алгоритма можем определить, соответствует ли она некоторому минимальному разложению (Предложение 3.1.2 и Следствие 3.2.11).

В качестве приложения этого описания для произвольных ш-категоричных I-алгебр был получен критерий изоморфизма (Теорема 3.3.5), говорящий, что тип изоморфизма такой алгебры однозначно определяется строением гсйтинговой алгебры Н0(А) с добавленными к ней 1 —, /д в качестве выделенных элементов, а также атомностью и числом атомов в каждой из фактор-алгебр A/L, L € Н0(А).

Эти результаты из Главы 3 имеют чисто алгебраический характер, они никак не связаны с теорией вычислимости. Но оказывается, что в терминах инвариантов (Я. е) можно дать и достаточно простое описание типов изоморфизма автоустой-чивьгх I-алгебр. Об этом говорят Теорема 3.6.4 и Следствие 3.6.5: по ггаре (Н.е) можно легко определить, является ли соответствующая ей псевдо-неразложимая алгебра автоустойчивой, а произвольные автоустойчивые I-алгебры являются конечными прямыми произведениями алгебр такого вида.

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

Описапие автоустойчивых I-алгебр опирается на весьма сложную технику, в основе которой лежит некоторая модификация Теоремы Гончарова о ветвлении. Ее исходный вариант возник в [10) и был успешно использован в решении ряда задач, связанных с описанием автоустойчивых моделей. Она основана на использовании некоторой последовательности V-формул с рядом специальных свойств. В |1| была предложена новая версия этой теоремы, которая использовала V-формулы с константами из модели. К сожалению, её- доказательство было неверным, и в Главе 3 доказывается новый вариант Теоремы о ветвлении, который уточняет некоторые идеи из |1], связанные с использованием констант в У-формулах. Его формулировка приведена в Теореме 3.4.1. Отметим, что эта теорема была также успешно использована в работе |15].

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

1. Венцов Ю. Г., Алгоритмические свойства ветвящихся моделей / Алгебра и логика, т. 25, N4, 1986, с. 369−383.

2. Власов В. Н., Конструктивизируемостъ булевых алгебр элементарной характеристики (1,0,1) // Алгебра и логика т. 37, N5. 1998, с. 499−521.

3. Власов В Н. Гончаров С. С., О сильной конструктивизируемости булевых алгебр элементарной характеристики (1.1,0) / Алгебра и логика, т. 32, N6, 1993, с. 618−630.

4. Гончаров С. С., Конструктивизируемостъ суператомных булевых алгебр // Алгебра и логика, т. 12, N1, 1973, с. 31−40.

5. Гончаров С. С., Некоторые свойства конструктивизации булевых алгебр // Сибирский математический журнал, т. 16, N2, 1975, с. 264−278.

6. Гончаров С. С., Ограниченные теории конструктивных булевых алгебр /Сибирский математический журнал, т. 17, N4, 1976, с. 797−812.

7. Гончаров С. С., Группы с конечным числом конструктивизаций // Доклады Академии Наук, 1981, т. 256, N2, с. 269−272.

8. Гончаров С. С-, Счетные булевы алгебры // Новосибирск: Наука, 1988.9| Гончаров С. С., Счетные булевы алгебры и разрешимость / Новосибирск: Научная книга, 1996.

9. Гончаров С. С., Дзгоев В. Д., Автоустойчивость моделей // Алгебра и логика, т. 19, N1, 1980, с. 45−58.

10. Гончаров С. С., Ершов Ю. Л., Конструктивные модели / Новосибирск: Научная книга, 1999.

11. Ершов Ю. Л., Разрешимость элементарной теории дистрибутивных структур с относительными дополнениями и теории фильтров / Алгебра и логика, т. 3, N3, 1964, с. 17−38.

12. Кейслер Г. Чэн Ч. Ч., Теория моделей/ М.: Мир. 1977.

13. Когабаев Н. Т. Автоустойчивость булевых алгебр с выделенным идеалом // Сибирский математический журнал, т. 39, N5. 1998, с. 1074−1084.

14. Мальцев А. И., О рекурсивных абелевых группах / Доклады Академии наук, т. 146, N5, 1962, с. 1009−1012.

15. Морозов А. С. Счетные однородные булевы алгебры // Алгебра и логика, т. 21. N3, 1982, с. 269−282.

16. Одинцов С. П. Ограниченные теории конструктивных булевых алгебр нижнего слоя // Препринт N21. Институт математики СО АН СССР. 1986.

17. Одинцов С. П., Селиванов В. Л., Арифметическая иерархия и идеалы нумерованных булевых алгебр / Сибирский математический журнал, т. 30. N6. 1989. с. 140 149.

18. Пальчунов Д. Е. Прямые слагаемые булевых алгебр с выделенными идеалами // Алгебра и логика, т. 31, N5,1992. с. 499−537.

19. Handbook of Boolean algebras / Elsevier. 1989.35| Handbook of Recursive Mathematics / Elsevier. 1998.

20. Touraille A., Thiones d’algkbres de Boole munies d’idiaux distmgues. II. / The Journal of Symbolic Logic, v. 55, N3, 1990, pp. 1092−1212.

21. Tarski Alfred, Arithmetical classes and types of Boolean algebras / Bulletin of the AMS, v. 55, N1, 1949, p. 64. Работы автора по теме диссертации.

22. Алаев П. Е., Вычислимые однородные булевы алгебры // Доклады Академии Наук, т. 387, N4, 2002, с. 439−442.

23. Алаев П. Е., Вычислимые семейства суператомных булевых алгебр // Сибирский математический журнал, т. 44, N4, 2003, с. 717−725.

24. Алаев П. Е., Вычислимые однородные булевы алгебры и одна метатеорема // Алгебра и логика, т. 43, N2, 2004, с. 133−158.

25. Алаев П. Е., Автоустойчивые булевы алгебры с выделенными идеалами // Доклады Академии Наук, т. 394, N3, 2004, с. 295−297.

26. Алаев П. Е. Автоустойчивые 1-алгебры / Алгебра и логика, т. 43, N5. 2004, с. 511−550.

27. Алаев П. Е., Разрешимые булевы алгебры характеристики (1,0.1) /Математические труды, т. 7, N1, 2004, с. 3−12.

28. Алаев П. Е., Гиперарифметические булевы алгебры с выделенным идеалом // Сибирский Математический журнал, т. 45, N5, 2004, с. 963−976.

29. Алаев П. Е. Сильно конструктивные булевы алгебры / Алгебра и логика, т. 44, N1, 2005, с. 3−23.

30. Alaev P., Computable homogeneous Boolean algebras 11 Logic Colloquium-2002, Program Booklet, Abstracts of contributed talks, Munster, Germany, p. 25.

31. Алаев П. Е., Вычислимо-категоричные I-алгебры // Материалы III конференции молодых ученых, посвященной М. А. Лаврентьеву, Новосибирск. 2003, с. 36−38.

32. Pavel Alaev. Computable homogeneous Boolean algebras / Abstracts of contributed talks, The Bulletin of Symbolic Logic, v. 9, N1. 2003. p. 85.

33. Pavel Е. Alaev, Strongly computable Boolean algebras // Abstracts of contributed talks. The Bulletin of Symbolic Logic, v. 11. N2, 2005. pp. 264−265.