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

00306200Б

На правах рукописи

Алаев Павел Евгеньевич

ВЫЧИСЛИМОСТЬ И РАЗРЕШИМОСТЬ В КЛАССЕ БУЛЕВЫХ АЛГЕБР

01.01.06 — математическая логика, алгебра и теория чисел

Автореферат диссертации на соискание учёной степени доктора физико-математических наук

Новосибирск-2006

003062006

Работа выполнена в Институте математики им. С.Л. Соболева СО РАН.

Научный консультант: доктор физ.-мат. наук, профессор, член-корреспондент РАН Гончаров Сергей Савостьянович

Официальные оппоненты: доктор физ.-мат. наук, профессор Морозов Андрей Сергеевич доктор физ.-мат. наук, профессор Селиванов Виктор Львович доктор физ.-мат. наук, профессор Хисамиев Назиф Гарифуллинович

Ведущая организация: Московский государственный университет

Защита диссертации состоится 22 марта 2007 г. в 10 часов на заседании диссертационного совета Д 003.015.02 при Институте математики им. С.Л.Соболева СО РАН по адресу: 630090, Новосибирск, пр. Акад. Коптюга, 4.

С диссертацией можно ознакомиться в библиотеке Института математики им. С.Л.Соболева СО РАН.

Автореферат разослан «

2007 г.

Учёный секретарь диссертационного совета /^Г)

кандидат физико-математических наук А.Н. Ряскин

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

тие конструктивной модели даёт нам другой подход к тому же классу объектов, который фактически основан на использовании другого языка. Говорим, что произвольная модель А квнструктивизируема, если она изоморфна некоторой вычислимой модели.

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

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

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

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

Одним из основных результатов диссертации является критерий конструктивизируемости для ещё одного широкого класса булевых алгебр — w-однородных. Счётная модель А называется ш-однородной, если для любых двух наборов её элементов й, 6 одинаковой длины из элементарной эквивалентности (А,й) = (А,Ь) следует изоморфизм (А, й) = (А, Ь). Отметим, что для произвольной (не обязательно счётной) модели понятие w-однородности обычно определяется иначе; в счётном же случае эти определения равносильны.

Предлагаемый критерий основан на описании произвольных, не обязательно вычислимых, w-однородных булевых алгебр, которое было получено в [18]. Проблема поиска такого критерия, в частности, формулировалась в сборнике проблем математической логики [16], частичный ответ (некоторые необходимые и некоторые достаточные

условия) ранее был дан в [24]. Критерий формулируется в чисто алгоритмических терминах — с использованием некоторого обобщения известной иерархии Фейнера 0(")-вычислимых функций ([33]).

С помощью этого критерия в классе (¿-однородных булевых алгебр можно легко повторить построение хорошо известного примера 0'-вычислимой и неконструктивизируемой булевой алгебры, который был построен Фейнером в [33] с помощью очень сложной и громоздкой конструкции. Кроме того, этот критерий показывает, что класс 0(")-вычислимых однородных алгебр увеличивается при росте п€ш.

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

Ю.Л. Ершов в [12] показал, что сильно вычислимые булевы алгебры могут быть охарактеризованы следующим образом: существует вычислимая последовательность одноместных формул <р\ (х),(р2(х),.. языка булевых алгебр такая, что вычислимая булева алгебра А сильно вычислима тогда и только тогда, когда все <рг(х) вычислимы в ней равномерно по i, то есть является вычислимым множество {(г,ж) € и х А | А (= щ(х)}. Эта последовательность формул имеет естественный алгебраический смысл: ч>\{х)> например, говорит, что

х — атом, tfi2(x) что х — безатомный элемент, у>з(ж) — атомный, и т.п. Позже С.С. Гончаровым в [9] было доказано, что вычислимость первых п формул <pi(x),.. .,<рп(х) равносильна п-вычислимости А; последнее означает, что в А равномерно вычислимы все отношения, определимые £„-формулами.

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

В [6] было показано, что существует булева алгебра А, которая п-вычислима для любого n € w (без равномерности по п), но при этом не является сильно констпруктпивизируемой, т.е. не изоморфна никакой сильно вычислимой модели. Это означает, что cm(Тва) — оо, где Тва — элементарная теория класса всех булевых алгебр. Если же мы будем рассматривать булевы алгебры с фиксированной элементарной теорией (от которой в первую очередь зависит структура формул), то определённая связь между n-вычислимостью и сильной вычислимостью возникает. Упомянутый выше результат заключается в описании cm (Г) для всех элементарных теорий булевых алгебр, т.е. теорий вида Th(A) = {</? — предложение! А |= </з}, или, что то же самое, полных расширений теории Тва■ Заметим, что для любой

теории Т сш(Т) = sup{cm(T") | Т' — полное расширение Т}. В случае булевых алгебр характеристика ст(Т) имеет дополнительный алгебраический смысл — она равна наименьшему п, при котором сильная конструктивизируемость алгебры с теорией Т равносильна существованию вычислимого представления с вычислимыми формулами ipi{x), .. .,tp„(x).

Решение этой задачи опирается в первую очередь на элементарную классификацию булевых алгебр, найденную А. Тарским и Ю.Л. Ершовым в [42] и [12]. При этом из некоторых результатов работы [12] нетрудно вывести серию верхних оценок для ст(Т), где Т — элементарная теория некоторой булевой алгебры. Впоследствии исследование ст(Г) для некоторых конкретных полных теорий Т проводилось в [5, 6, 19, 3, 2], этому же вопросу посвящена и часть монографии [9] (отметим, что обозначение ст(Т) там не использовалось). Проблема полного описания ст(Т) была опубликована в [16, 8, 9], а также в [35]. В диссертации приводится её полное решение.

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

Последний основной результат диссертации посвящён описанию автоустойчивых булевых алгебр с конечным числом выделенных идеалов (1-алгебр), т.е. моделей вида (A1, It,... ,/д), где А' — булева алгебра, а 1\,..., 1\ — идеалы в А', выделяемые добавленными в язык

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

Результат состоит в формулировке некоторого алгебраического критерия автоустойчивости. Заметим, что ранее в [14] было найдено описание автоустойчивых 1-алгебр с одним выделенным идеалом, т.е. моделей вида (Л', /1); оно также оказалось достаточно простым. Однако по мере роста числа выделенных идеалов А сложность автоустойчивых 1-алгебр резко возрастает, и уже при А = 3 они образуют достаточно большой и нетривиально устроенный класс.

В дополнение к этому критерию, в диссертации приводится и некоторое структурное описание класса автоустойчивых 1-алгебр: для каждого фиксированного А в явном виде строится такой конечный набор 1-алгебр, что класс автоустойчивых 1-алгебр с А выделенными идеалами равен классу всех конечных прямых произведений алгебр из этого набора.

Описание автоустойчивых 1-алгебр опирается на весьма сложную технику, в основе которой лежит некоторая модификация Теоремы Гончарова о ветвлении. Её исходный вариант возник в [10] и был успешно использован при решении ряда задач, связанных с описанием автоустойчивых моделей. Она основана на использовании некоторой последовательности У-формул с рядом специальных свойств. Для решения задачи описания автоустойчивых 1-алгебр был раз-

работай её новый, усиленный вариант, который сам по себе может рассматриваться как самостоятельный результат диссертации. Отметим, что впоследствии он был успешно использован в работе [15].

Научная новизна. Все основные результаты диссертации являются новыми.

Основные результаты диссертации.

1. Получено описание конструктивизируемых однородных булевых алгебр, основанное на использовании обобщённой иерархии Фей-нера, что является ответом на один из вопросов, опубликованных в сборнике проблем математической логики [16].

2. Найдено полное описание сильно конструктивизируемых булевых алгебр с фиксированной элементарной теорией в терминах вычислимости Еп-диаграмм, которое является решением проблемы, опубликованной в монографии [9] и справочнике [35].

3. Установлен алгебраический критерий автоустойчивости для произвольной 1-алгебры.

Теоретическая и практическая ценность. Диссертация имеет теоретический характер, её результаты могут использоваться в дальнейших исследованиях по булевым алгебрам и конструктивным моделям.

Апробация работы. По результатам диссертации были сделаны пленарные доклады на "9-м Азиатском логическом коллоквиуме" (Новосибирск, 2005), на конференциях "Алгебра и анализ 2004" (Казань) и "Мальцевские чтения 2003" (Новосибирск), а также доклады на следующих конференциях: "Logic Colloquium 2004" (Турин, Италия), "Logic Colloquium 2002" (Мюнстер, Германия), "Мальцевские чтения 2005, 2004 и 2002" (Новосибирск), "Вычислимость и модели" (Алматы, 2002), а также некоторых других. Кроме того, результаты неоднократно докладывались на совместных семинарах ИМ СО РАН и НГУ "Конструктивные модели", "Теория моделей", "Теория

вычислимости" и "Алгебра и логика", а также на научном семинаре при Кафедре математической логики и теории алгоритмов ММФ МГУ.

Публикации. Основные результаты опубликованы в работах [43 -51].

Структура и объём диссертации. Диссертация состоит из введения, трёх глав и списка литературы (59 наименований). Объём диссертации — 119 стр.

ОБЗОР СОДЕРЖАНИЯ ДИССЕРТАЦИИ

Первая глава диссертации посвящена изучению связи между п-вычислимостью и сильной вычислимостью для булевых алгебр с фиксированной элементарной теорией. Дадим сначала более строгое определение сильно вычислимой и п-вычислимой модели.

Пусть дан некоторый конечный язык и зафиксирована некоторая гёделевская нумерация всех формул ,... ,Пк), где <р(х 1,... ,Хк) — формула этого языка, а числа пу,..., п* лежат в и) (они рассматриваются как новые константные символы). Если А — модель этого языка, носитель которой является подмножеством и, то полной диаграммой А называем множество {<р{п,1,... ,Пк) \ п\,...,пк £ А и А [= <р(п1,...,пк)}.

А — сильно вычислимая модель, если её полная диаграмма вычислима, т.е. вычислимо множество гёделевских номеров элементов этой диаграммы. Т, п-диаграммой ддя п ^ 1, или просто п-диаграммой, называем множество, определяемое как выше, но составленное только из Еп-формул :р(х 1,... ,Хк). Атомная диаграмма А, или просто диаграмма А, образуется, если в качестве <р{х\,,..., Хк) берутся только атомные формулы и отрицания атомных формул.

А п-вычислима, если её Хп-диаграмма вычислима. Отметим, что А вычислима тогда и только тогда, когда вычислима её атомная

диаграмма. В последнем случае будем также говорить, что А 0-вычислима.

Напомним ещё раз, что для теории Т ст(Т) = тт{п € ш | любая п-вычислимая модель теории Т обладает сильно вычислимым представлением}, и сш(Т) = оо, если указанного п не существует. Основным результатом этой главы является описание ст(Т), где Т — элементарная теория некоторой булевой алгебры. Эти элементарные теории были описаны в [42] и [12] через тройки алгебраических инвариантов сЬ = (сЬ^сИг, сЬз), где йц.сЬг е ш и {оо}, а сЬз € {0,1} (тройку сЬ(Л) называем элементарной характеристикой булевой алгебры А). В силу этого ниже используется обозначение ст(сЬ1,сЬ2,сЬз). В следующую теорему входят как результаты, ранее полученные другими исследователями, так и принадлежащие автору диссертации. Последние примерно совпадают с пунктами (3) и (4). Более подробно история этих исследований указана в Главе 1.

ТЕОРЕМА 1.3.4. (1) ст(оо,0,0) = оо;

(2) ст(т 4- 1, оо, 0) — ст(т + 1, оо, 1) = 4т + 5 при т € ш;

(3) ст(т + 1, к, 0) = 4т + 1 при т,к 6 ш и к ^ 1;

(4) ст(т + 1, к, 1) = 4т + 2 при т,к € и;

(5) ст(0, оо, 0) = ст(0, оо, 1) = 1, ст(0, к, е) = 0 при к е и, £ е {0,1}.

Вся Глава 1 посвящена доказательству этой теоремы: в §1.1 и §1.2 строятся некоторые вспомогательные конструкции, в §1.3 на их основе доказывается основной результат.

Основным результатом Главы 2 является описание конструктиви-зируемых ^-однородных (или просто однородных) булевых алгебр, основанное на найденном в [18] достаточно простом и ясном описании произвольных счётных ¡¿-однородных алгебр. Мы не будем

приводить здесь полную формулировку последнего, ограничившись лишь краткой информацией. Однородные счётные алгебры А с конечной характеристикой сЬ1 (Л) образуют счётный класс, все элементы которого, как показано в [18], сильно конструктивизируемы. В случае же сЬх (А) = оо их типы изоморфизма в точности соответствуют всевозможным последовательностям (1{А),ро(А),р\{А),ръ{А),...), где ЦА),р^А) — некоторые естественные алгебраические инварианты, Ь(А) е {1,2,3}, арг(А) е {0,1} для всех г € из. Тем самым второй класс имеет мощность континуума.

Через Фу {г) обозначим стандартную универсальную функцию, описывающую результат работы машины Тьюринга с номером у & из и оракулом X С из на входе г € из. Запись фу (г) 4- означает определённость этого результата. Используя вместо обычных вычислимых функций вычислимые с оракулом X, мы получим понятие X-вычислимой модели. Обозначение 0(п' при п € из используется для стандартных арифметических оракулов; оно может быть естественным образом обобщено на бесконечные конструктивные ординалы а так, чтобы можно было говорить о 0(а)-вычислимых функциях и моделях. Будем также считать, что у нас зафиксирована некоторая биекция (...) : ш<ш —> из, вычислимая в естественном смысле.

Для формулировки критерия необходимо определить классы Одновременно определим и естественным образом связанные с ними классы Д° , необходимые, в частности, для формулировки вспомогательных результатов. Эти классы обобщают классы фейнеровской иерархии. Пусть д : из из — вычислимая функция и д(х) ^ I при всех х. Класс Д° состоит из таких функций / : из из, которые для некоторого к £ из могут быть заданы следующей схемой рекурсии:

{

/(о)^Г>Ь1)(0);

/(П+!)=¥>!?

0(в«/(О)...../(»)»-!)

«/(о ),...,/(")))•

Нетрудно заметить, что С Д° для любой функции д, где Д° — класс -вычислимых функций. Если д((хо,.. .,£„)) = ап + b, где а,Ь £ ш — фиксированные константы, то s является фейнеров-ским классом. Если же д((хо,.. ■, хп)) равна фиксированному числу к, то Д° 9 = ДО, т.е. классу 0^-1)-вычислимых функций.

Будем говорить, что множество М С и лежит в классе если туда попадает его характеристическая функция хм• Классы второго вида, состоят из таких множеств МСц что для некоторого к £ и характеристическая функция Хм может быть задана следующей схемой:

Хм(п Н-1) = 1 <=> (pf3i(xM{0),-'XM(n))) 1\{Х„(0),... ,Хм(п)))|.

ТЕОРЕМА 2.1.3. Если А — однородная счетная булева алгебра, chi(A) = оо, то следуюы,ие условия эквивалентны:

(1) существует вычислимая булева алгебра, изоморфная А;

(2) {n е W I рп(А) = 1} е ТРыа, где

д((е0,..., ек)) = 4 + 3(* + 1) + е0 + ... + ек.

Непосредственная релятивизация этой теоремы даёт нам, что А изоморфна 0(т)-вычислимой алгебре тогда и только тогда, когда соответствующее множество лежит в классе >9 с функцией д((е0, ■■■, £к)) = 4 + т + 3(fc + 1) + е0 + • • • + Невырожденность новой иерархии показывает

ПРЕДЛОЖЕНИЕ 2.1.8. Пусть g,h — вычислимые функции и д(х) > h(x) ^ 1 для всех х € и. Тогда существует М € \

Из него сразу вытекает

СЛЕДСТВИЕ 2.1.9. Для любого к ^ 1 существует Д°+1 -вычислимая однородная булева алгебра, не имеющая представления.

Глава 2 состоит из четырёх параграфов. §2.1 и §2.2 посвящены непосредственно доказательству этих результатов, а в §2.2 и §2.3 строится конструкция, которая не только используется в доказательстве, но и может рассматриваться как некоторый самостоятельный результат диссертации. Не будем приводить здесь его полную формулировку, указав лишь идею.

Идеальным оператором назовём соответствие, которое каждой булевой алгебре А сопоставляет идеал Т(А) С А со свойством: если А, В — булевы алгебры, а£ А, ЬеВиа^Ь, то а€ Т(А) Ь е Т{В). Теорема 2.3.9 позволяет получить целую серию критериев следующего общего вида: булева алгебра А изоморфна 0(а)-вычислимой алгебре тогда и только тогда, когда она представима в виде В/Т(В) для некоторой вычислимой булевой алгебры В, где В/Т(В) — результат факторизации В по идеалу Т(В). Условия теоремы говорят, при каких ограничениях на идеальный оператор Т и конструктивный ординал а такой критерий имеет место.

С помощью этой теоремы можно как легко повторить доказательство нескольких критериев такого вида из [20] и [24], каждый из которых ранее требовал отдельной сложной конструкции, так и получить много новых. В качестве примера укажем критерий из [20]: А изоморфна 0(2)-вычислимой алгебре тогда и только тогда, когда А представима в виде В/Е{В), где В вычислима, а — идеал Фреше. Отметим, что на основе этой теоремы в работе [44] удалось описать вычислимые семейства суператомных булевых алгебр. Позже в [49] она была обобщена на булевы алгебры с одним выделенным идеалом.

Глава 3 посвящена описанию автоустойчивых I-алгебр. Её основ-

ным результатом является прямой алгебраический критерий автоустойчивости, для формулировки которого необходимо ввести ряд понятий. Будем рассматривать булевы алгебры как модели языка Ева = (+,-,— ,0,1), где 4- соответствует объединению элементов, • пересечению, а — дополнению. Пусть А = (А', 1\,..., 1\) — 1-алгебра, где А' — булева алгебра, а ... ,1\ — выделенные идеалы. Если Ь\, 1^2 — два идеала в булевой алгебре Ато зададим на них операции Ь\ ■ Ьъ = Ьх П 1/2, Ь\ 4- 1-2 = {^1 + %2 | € ¿1,^2 € £2} и Ьг -> Ь2 = {х € А' | Уу ^ х(у <Е Ьх ->• у <Е I*)}.

Зафиксируем некоторую 1-алгебру А = (А', Д,..., /д). Будем говорить, что она замкнута относительно пересечений идеалов, если для любого набора {¿1,..., и} С {1,..., А} пересечение /¿1 П ... П совпадает с /„ для некоторого п; и, кроме того, 1т = {0} и 1а = А для некоторых ш,в ^ А. Из любой алгебры (А',1х,... ,1\) можно получить замкнутую относительно пересечений идеалов, добавив в язык новые идеалы для {0}, А и всех конечных пересечений, и алгоритмическая размерность от этого не изменится. Поэтому считаем, что рассматриваемая 1-алгебра обладает этим свойством.

Пусть элемент х € А. Его характеристикой называем множество Рх — {п ^ А | х $ /„}. Если Р С {1,..., А} — некоторая характеристика, то Р-идеал — {х \ Рх ^ Р}, Р-сумма — сумма Р'-идеалов для всех Р' < Р. Если Р = 0, то считаем, что Р-сумма равна Р-идеалу (который равен {0}). Говорим, что 1-алгебра Р-регулярна, если выполняется одно из условий:

(1) Р-сумма равна 1к для некоторого к ^ А;

(2) Р-идеал совпадает со всей А, а Р-сумма — максимальный собственный идеал в А.

Назовём её кусочно Р-регулярной, если она представима в виде конечного прямого произведения Р-регулярных 1-алгебр. Идеал Ь С А назовём с-определимым, если Ь = 1т для некоторого

S С {1,...,A}, S Ф 0, и кусочно с-определимым, если у 1-алгебры существует такое конечное прямое разложение, что L (точнее, его естественное сужение) с-определим в каждом из этих прямых сомножителей.

Наконец, назовём I-алгебру устойчивой, если она Р-регулярна для всех характеристик Р С {1,...,Л}, идеал L\ с-определим

для любых с-определимых идеалов L%, L2, в А есть наибольший собственный с-определимый идеал Lq и выполняется одно из условий:

(a) A/L безатомна для любого с-определимого идеала L;

(b) А/L0 двухэлементна, а если L с-определим и L ф Lo, то A/L безатомна.

ТЕОРЕМА 3.6.1. Пусть А = (А', Д,...,/д) — вычислимая 1-алгебра, замкнутая относительно пересечений идеалов. Следующие условия эквивалентны:

(1) А автоустойчива;

(2) dime (А) < w;

(3) А кусочно Р-регулярна для любой характеристики PC {1,..., А}, идеалы вида Li -> Ь2 кусочно с-определимы в А для любых с-определимых L\, Ь2, и А/In содержит конечное число атомов при п ^ А;

(4) А — конечное прямое произведение устойчивых алгебр.

В качестве дополнения к этому прямому критерию, в Главе 3 проводится и некоторый структурный анализ класса автоустойчивых 1-алгебр. I-алгебру А назовём псевдо-неразложимой, если из А й Ai х А2 следует А = А\ или А £ А2. Из этого анализа следует, что для каждого фиксированного числа выделенных идеалов А существует конечный набор 1-алгебр А\,...,А f(X) > конечные прямые произведения элементов которого образуют класс всех автоустойчивых 1-алгебр:

СЛЕДСТВИЕ 3.6.6. Для каждого А ^ О существует, лишь конечное множество попарно неизоморфных псевдо-неразложимых автоустойчивых 1-алгебр вида (А', Д,... ,1\). Более того, существует примитивно вычислимая функция /(А), которая для каждого А равна числу элементов в этом множестве.

Стоит также отметить, что с точностью до небольших преобразований автоустойчивые и ш-категоричные 1-алгебры образуют один и тот же класс: любая (¿-категоричная 1-алгебра после добавления в язык конечного числа новых определимых идеалов становится автоустойчивой.

СЛЕДСТВИЕ 3.6.8. Класс автоустойчивых 1-алгебр совпадает с классом (счетных) 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.

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

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

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

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

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

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

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

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

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

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

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

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

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

[23] Пальчунов Д.Е., Прямые слагаемые булевых алгебр с выделенными идеалами // Алгебра и логика, т. 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 11 Transactions of the AMS, v. 298, N2, 1986, pp. 497-514.

[27] Ash C.J., Labelling systems and r.e. structures 11 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 // The Journal of Symbolic Logic, v. 35, N3, 1970, pp. 365-374.

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

[35] Handbook of Recursive Mathematics // 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., No-Categoricity for Rings without Nilpotent Elements and for Boolean Structures // Journal of Algebra, v. 43, N1, 1976, pp. 129-154.

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

[39] Remmel J.B., Recursive isomorphism types of recursive Boolean algebras // The Journal of Symbolic Logic, v. 46, N3, 1981, pp. 572594.

[40] Touraille A., Théories d'algèbres de Boole munies d'idéaux distingués. I: théories élémentaires // The Journal of Symbolic Logic, v. 52, N4, 1987, pp. 1027-1043.

[41] Touraille A., Théories d'algèbres de Boole munies d'idéaux distingués. 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, с. 295297.

[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, с. 36-38.

[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.

Алаев Павел Евгеньевич

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

Автореферат диссертации на соискание учёной степени доктора физико-математических наук

Подписано в печать 18.01.07. Формат 60x84 1/16. Усл. печ. л. 1,5. Уч.-изд. л. 1,5. Тираж 100 экз. Заказ №20.

Отпечатано в ООО "Омега Принт" 630090, Новосибирск, пр. Лаврентьева, 6