Вычислимость и разрешимость в классе булевых алгебр тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

Введение

Глава Сильно конструктивные булевы алгебры

1.1. Один признак конструктивизируемости

1.2. Критерий изоморфизма.

1.3. Оценка сложности моделей

Глава 2. Однородные булевы алгебры

2.1. Критерий вычислимости для однородных булевых алгебр

2.2. Метатеорема для а-систем

2.3. Метатеорема для фактор-алгебр.

2.4. Две вспомогательные конструкции и отношения

Глава 3. Автоустойчивые 1-алгебры

3.1. Псевдо-неразложимые 1-алгебры

3.2. Алгебраические инварианты

3.3. Критерий изоморфизма.

3.4. Теорема о ветвлении

3.5. Необходимые условия автоустойчивости.

3.6. Критерий автоустойчивости

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

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

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

Центральными проблемами теории вычислимых моделей являются вопрос о том, какие модели являются конструктивизируемыми, и насколько велико число различных вычислимых представлений у данной модели. Последнее понятие, число различных представлений, может пониматься в разных смыслах, и в литературе рассматривается несколько подходов, которые сводятся к разным определениям "эквивалентных" представлений. В настоящей диссертации используется наиболее сильный подход: две вычислимые модели А\,Аъ считаются "эквивалентными", если между ними существует вычислимый изоморфизм / : А\ —» Аг, то есть изоморфизм, одновременно являющийся вычислимой функцией на носителе Ai. В этом случае мы говорим, что модели А\ и А<± вычислимо изоморфны. Изучение этой темы было начато А.И. Мальцевым, который в [17] назвал автоустойчивыми те модели, у которых все вычислимые представления вычислимо изоморфны. Максимальное число вычислимых представлений модели А, которые не являются вычислимо изоморфными друг другу, называется алгоритмической размерностью модели A, dime (А), или авторазмерностъю (это понятие было впервые введено в

7]).

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

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

В Главе 2 решается проблема описания конструктивизируемых ш-однородных булевых алгебр. Счётная модель А является си-однородной, если для любых двух наборов её элементов a, b одинаковой длины из элементарной эквивалентности (А, а) = (А,Ъ) следует изоморфизм (А, а) = (А, Ъ). Отметим, что для произвольной (не обязательно счётной) модели понятие w-однородности обычно определяется иначе; в счётном же случае эти определения равносильны.

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

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

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

Если у данной модели существует какое-то вычислимое представление, то иногда бывает важно знать, обладает ли она вычислимым представлением с какими-то дополнительными алгоритмическими свойствами, например, в котором вычислимыми являются некоторые дополнительные определимые отношения и операции, не входящие в язык этой модели. В одной из наиболее общих постановок этот вопрос сводится к существованию сильно вычислимых представлений: вычислимая модель называется сильно вычислимой, если в ней вычислимым является любое отношение, определимое некоторой формулой первого порядка, и при этом "равномерно" по формуле. Другими словами, если существует алгоритм, который по формуле ip(x 1,., хп) и набору элементов oi,., ап определяет, истинна ли эта формула на этом наборе. Более строгое определение этого понятия приведено в начале Главы 1.

Ю.Л. Ершов в [12] показал, что сильно вычислимые булевы алгебры могут быть охарактеризованы следующим образом: существует вычислимая последовательность одноместных формул у>\{х), • • • языка булевых алгебр такая, что вычислимая булева алгебра А сильно вычислима тогда и только тогда, когда все ipi(x) вычислимы в ней равномерно по i, то есть является вычислимым множество {{i,x) € из х А | А (= (pi(x)}. Эта последовательность формул имеет естественный алгебраический смысл: <fii(x), например, говорит, что х — атом, (рг(^) что х — безатомный элемент, <рз(х) — атомный, и т.п. Позже С.С. Гончаровым в [9] было доказано, что вычислимость первых п формул ч>\(х),., <рп(х) равносильна п-вычислимости А; последнее означает, что в А равномерно вычислимы все свойства, определимые Е„-формулами.

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

Основным результатом Главы 1 является описание cm(Т) для всех элементарных теорий булевых алгебр, т.е. теорий вида ТЪ(Л) = {(р — предложение! А (= или, что то же самое, полных расширений теории всех булевых алгебр. Заметим, что для любой теории Т cm(T) = sup{cm(T") | Т' — полное расширение Т}. В случае булевых алгебр ст(Т) имеет дополнительный алгебраический смысл — она равна наименьшему п, при котором сильная конструктивизируемость алгебры с теорией Т равносильна существованию вычислимого представления с вычислимыми формулами f\(x),., <Рп(я)

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

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

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

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

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

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

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

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

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

Изучением ш-категоричных I-алгебр занимался ряд исследователей. Укажем краткую историю этой работы. Пусть булевы алгебры рассматриваются как модели языка Едл = (+,*,—, 0,1), где + соответствует объединению элементов, ■ пересечению, а — дополнению. На множестве всех идеалов в булевой алгебре А' определим три операции: Li + Ь2 = {х + у | х 6 L\, у 6 Ь2}, Ь\ • L2 = L\ П Ь2 и Li L2 = {х е А' | Vy ^ х(у 6 Li —»• у е Ь2)}. Множество всех идеалов в А' с операциями -f, •, —» и 0 = {0}, 1 = А образует гейтингову алгебру.

Если А = (A',Ii,.,Ix) — I-алгебра, то через Hq(A) обозначим подалгебру в этой гейтинговой алгебре, порождённую множеством {/i,., /д}. В [37] задача описания са-категоричных I-алгебр возникла в связи с изучением ^-категоричных колец, и там был найден критерий: А cj-категорична тогда и только тогда, когда множество Hq(A) конечно и число атомов в фактор-алгебре A/L конечно для всех L G Hq(A). К сожалению, этот критерий ничего не говорил о многообразии типов изоморфизма таких А.

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

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

В свою очередь, произвольная иькатегоричная 1-алгебра А разлагается в конечную прямую сумму псевдо-неразложимых, причём разложение минимальной длины единственно (Следствие 3.2.12 и Предложение 3.1.1). Тем самым её тип изоморфизма может быть задан конечной последовательностью (Hi,£i),., (Нк,£к), которая соответствует компонентам минимального разложения. Более того, по произвольной конечной последовательности таких пар мы с помощью некоторого алгоритма можем определить, соответствует ли она некоторому минимальному разложению (Предложение 3.1.2 и Следствие 3.2.11).

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

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

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

Описание автоустойчивых I-алгебр опирается на весьма сложную технику, в основе которой лежит некоторая модификация Теоремы Гончарова о ветвлении. Её исходный вариант возник в [10] и был успешно использован в решении ряда задач, связанных с описанием автоустойчивых моделей. Она основана на использовании некоторой последовательности V-формул с рядом специальных свойств. В [1] была предложена новая версия этой теоремы, которая использовала V-формулы с константами из модели. К сожалению, её доказательство было неверным, и в Главе 3 доказывается новый вариант Теоремы о ветвлении, который уточняет некоторые идеи из [1], связанные с использованием констант в V-формулах. Его формулировка приведена в Теореме 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. Гончаров С.С., Некоторые свойства конструктивизации булевых алгебр I j Сибирский математический журнал, т. 16, N2, 1975, с. 264-278.

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

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

8. Гончаров С.С., Счетные булевы алгебры // Новосибирск: Наука, 1988.

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

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

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

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

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

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

15. Когабаев Н.Т., Кудинов О.В., Миллер Р., Вычислимая размерность 1-деревьев бесконечной высоты // Алгебра и логика, т. 43, N6, 2004, с. 702-729.

16. Логическая тетрадь. Нерешенные вопросы математической логики. // Оперативный информационный материал. Под редакцией Ю.Л. Ершова и С.С. Гончарова. Новосибирск: Институт математики СО АН СССР, 1986.

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

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

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

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

21. Пальчунов Д.Е., Счетно-категоричные булевы алгебры с выделенными идеалами II Препринт N12, Институт Математики СО АН СССР, Новосибирск, 1986.

22. Пальчунов Д.Е., Конечно-аксиоматизируемые булевы алгебры с выделенными идеалами // Алгебра и логика, т. 26, N4, 1987, с. 435-455.

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

24. Подзоров С.Ю., Рекурсивные однородные булевы алгебры // Алгебра и логика, т. 40, N2, 2001, с. 174-191.

25. Роджерс X., Теория рекурсивных функций и эффективная вычислимость // Москва: Мир, 1972.

26. Ash C.J., Recursive labelling systems and stability of recursive structures in hyperarithmetical degrees // Transactions of the AMS, v. 298, N2, 1986, pp. 497514.

27. Ash C.J., Labelling systems and r.e. structures j j Annals of Pure and Applied Logic, v. 47, N2, 1990, pp. 99-119.

28. Ash C. J., A construction for recursive linear orderings // The Journal of Symbolic Logic, v. 56, N2, 1991, pp. 673-683.

29. Ash C.J., Knight J.F., Ramified systems // Annals of Pure and Applied Logic, v. 70, N3, 1994, pp. 205-221.

30. Ash C.J., Knight J.F., Computable structures and the hyperarithmetical hierarchy // Elsevier, 2000.

31. Downey R., On presentations of algebraic structures // Lecture notes in pure and applied mathematics, v. 187, 1997, pp. 157-205.

32. Downey R., Jockush C.G., Every low Boolean algebra is isomorphic to a recursive one // Proceedings of the AMS, v. 122, N3, 1994, pp. 871-880.

33. Feiner L., Hierarchies of Boolean algebras j j The Journal of Symbolic Logic, v. 35, N3, 1970, pp. 365-374.

34. Handbook of Boolean algebras // Elsevier, 1989.

35. Handbook of Recursive Mathematics j j Elsevier, 1998.

36. Knight J.F., Stob M., Computable Boolean algebras // The Journal of Symbolic Logic, v. 65, N4, 2000, pp. 1605-1623.

37. Macintyre A., Rosenstein J.G., -Categoricity for Rings without Nilpotent Elements and for Boolean Structures j j Journal of Algebra, v. 43, N1, 1976, pp. 129-154. ,

38. Palchunov D.E., Сountably-categorical Boolean algebras with distinguished ideals // Studia Logica, v. 46, N2, 1987, pp. 121-135.

39. Remmel J.В., Recursive isomorphism types of recursive Boolean algebras // The Journal of Symbolic Logic, v. 46, N3, 1981, pp. 572-594.

40. Touraille A., Theories d'algebres de Boole munies d'ideaux distingues. I: Tories elementaires // The Journal of Symbolic Logic, v. 52, N4, 1987, pp. 1027-1043.

41. Touraille A., Theories d'algebres de Boole munies d'ideaux distingu6s. II. // The Journal of Symbolic Logic, v. 55, N3, 1990, pp. 1092-1212.

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

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

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

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

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

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

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

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

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

51. Alaev Р.Е., Decidable Boolean algebras of characteristic (1,0,1) // Siberian Advances in Mathematics, v. 15, N1, 2005, pp. 1-10.

52. Alaev P., Computable homogeneous Boolean algebras // Proceedings of Workshop "Computability and Models", Almaty, 2002, pp. 11-12.

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

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

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

56. Алаев П.Е., Сильно конструктивные булевы алгебры // Материалы Международной конференции "Алгебра и анализ 2004", Казань, с. 15.

57. Alaev Pavel Е., Strongly computable Boolean algebras // Book of abstracts, Logic Colloquium 2004, Turin, Italy, 2004, p. 40.

58. Алаев П.Е., Сильная конструктивизируемость булевых алгебр // Материалы IV конференции молодых ученых, посвященной М.А.Лаврентьеву, Новосибирск, 2004, с. 32-35.

59. Pavel Е. Alaev, Strongly computable Boolean algebras // Abstracts of contributed talks, The Bulletin of Symbolic Logic, v. 11, N2, 2005, pp. 264-265.c. 36-38.