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

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

С'

Баженов Николай Алексеевич

УРОВНИ АВТОУСТОЙЧИВОСТИ БУЛЕВЫХ АЛГЕБР

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

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

9 ОКТ

Новосибирск — 2014

005553077

005553077

Работа выполнена в Федеральном государственном бюджетном учреждении науки Институте математики им. С.Л. Соболева Сибирского отделения Российской академии наук.

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

Официальные оппоненты: Калимуллин Искандер Шагитович,

доктор физико-математических наук, доцент, Федеральное государственное автономное учреждение высшего профессионального образования «Казанский (Приволжский) федеральный университет», профессор кафедры алгебры и математической логики;

Коровина Маргарита Владимировна,

кандидат физико-математических наук,

Федеральное государственное бюджетное учреждение науки Институт систем информатики им. А.П. Ершова Сибирского отделения Российской академии наук, старший научный сотрудник.

Ведущая организация:

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Омский государственный университет им. Ф.М. Достоевского».

Защита состоится 14 ноября 2014 г. в 15.00 на заседании диссертационного совета Д 003.015.02 при Федеральном государственном бюджетном учреждении науки Институте математики им. С.Л. Соболева Сибирского отделения Российской академии наук по адресу: пр. Академика Коптюга 4, г. Новосибирск, 630090.

С диссертацией можно ознакомиться в библиотеке и на сайте Федерального государственного бюджетного учреждения науки Института математики им. С.Л. Соболева Сибирского отделения Российской академии наук, http://math.n3c.ru.

Автореферат разослан «_» октября 201'

Ученый секретарь диссертационного сове кандидат физико-математических наук, доцент

Общая характеристика работы

Постановка задачи и актуальность темы исследования.

Диссертация посвящена исследованию некоторых вопросов теории вычислимых (конструктивных) моделей. Теория вычислимых (конструктивных) моделей начала развиваться в середине XX века в работах А. И. Мальцева [18-20], М. О. Рабина [57], А. Фрёлиха и Дж. Шефердсона [44] и др. авторов. С тех пор теория вычислимых моделей стала одной из наиболее актуальных и активно развивающихся областей математической логики. Подробную информацию по теории вычислимых моделей можно найти в [10,32,48].

Напомним, что модель конечного языка называется вычислимой, если её носитель и предикаты являются вычислимыми множествами, а операции — частично вычислимыми функциями. Модель называется констпруктпивизируемой, если она имеет вычислимую изоморфную копию.

Конструктивизируемая модель 9Л называется автоустойчивой, если для любых вычислимых копий и модели Ш существует вычислимый изоморфизм /: —> • Автоустойчивые модели также называют вычислимо категоричными или категоричными.

Изучение автоустойчивых моделей восходит к Б. Л. ван дер Вардену [61], исследовавшему вопрос о том, всегда ли существует алгоритм построения изоморфизма между двумя алгебраическими замыканиями поля, построенными различными эффективными способами. Отрицательный ответ на этот вопрос был получен А. Фрёлихом и Дж. Шефердсоном в [44].

Систематическое исследование автоустойчивых моделей было начато в начале 1900-х гг. в работах А. И. Мальцева [18-20]. Впервые понятие автоустойчивой модели было введено в [19]. В работе [18] показано, что любая конечно порождённая вычислимая модель является автоустойчивой. В [20] доказано, что любое конечное расширение поля рациональных чисел и любая полная нильпотент-ная группа конечного ранга без кручения являются автоустойчивыми. В [19] доказано, что абелева полная группа без кручения счётного ранга конструктивизируема, но не является автоустойчивой.

Одной из фундаментальных проблем современной теории вычислимых моделей является проблема характеризации автоустойчивости:

Проблема 1. Получить описание автоустойчивых моделей в данном классе моделей (например, в классе всех булевых алгебр или в классе всех линейных порядков).

Приведём краткий обзор результатов, связанных с проблемой 1. В работах С. С. Гончарова [4] и С. С. Гончарова, В. Д. Дзгоева [9] получены общие методы, позволяющие доказывать неавтоустойчи-вость вычислимых моделей. В [4] доказана теорема о неограниченной модели и получено полное описание автоустойчивых абелевых р-групп. В [9] доказана теорема о ветвлении и в качестве её следствия получены следующие результаты:

(1) Описание автоустойчивых линейных порядков: вычислимый линейный порядок является автоустойчивым тогда и только тогда, когда он имеет лишь конечное число пар соседних элементов.

(2) Описание автоустойчивых булевых алгебр (см. теорему 3 ниже).

В дальнейшем теорема о ветвлении была обобщена в работах Ю.Г. Венцова [2] и П. Е. Алаева [1]. Отметим, что описание автоустойчивых абелевых р-групп было также независимо получено Р. Л. Смитом [60], а описание автоустойчивых булевых алгебр и линейных порядков было независимо получено Дж. Б. Ремме-лом [58,59].

В настоящее время известны критерии автоустойчивости для целого ряда классов структур, широко используемых в алгебре и математической логике. С. С. Гончаров, С. Лемпп и Р. Соломон [46] доказали, что вычислимая линейно упорядоченная абелева группа является автоустойчивой в том и только том случае, когда она имеет конечный ранг. С. Лемпп, Ч. Мак-Кой, Р. Миллер и Р. Соломон [52] дали описание автоустойчивых деревьев конечной высоты. Р. Миллер [56] доказал, что не существует автоустойчивых деревьев бесконечной высоты. Н.Т. Когабаев, О. В. Кудинов и Р. Миллер [15] доказали, что не существует автоустойчивых деревьев с выделенным начальным поддеревом, имеющих бесконечную высоту. У. Калверт, Д. Цензер, В. Харизанов и А. С. Морозов [37] получили критерий автоустойчивости для структур с эквивалентностью. Н. Т. Когабаев [14] получил описание автоустойчивых булевых алгебр с выделенным идеалом. П. Е. Алаев [1,27] получил описание автоустойчивых булевых алгебр с конечным числом выделенных идеалов и множеств атомов в факторе по этим идеалам.

Отметим, что в классическом определении автоустойчивости рассматриваются только вычислимые изоморфизмы. Понятие -

категоричности даёт естественное обобщение понятия автоустойчивости для случая изоморфизмов, принадлежащих фиксированному уровню гиперарифметической иерархии.

Пусть а — вычислимый ординал. Вычислимая модель называется Д°-категоричной, если для любой вычислимой копии 9t модели ЯЯ существует Д^-вы числимый изоморфизм /: ЯЯ —> ОТ. Вычислимую модель ЯЯ называют относительно Д^-категоричной, если для любой модели ОТ, такой что ОТ изоморфна ЯЯ и носитель ОТ является подмножеством множества натуральных чисел, существует Д° (£)(ОТ))-вычислимый изоморфизм /: ЯЯ —> ОТ. где £>(0Т) — атомная диаграмма модели ОТ. Нетрудно видеть, что любая относительно Д^-категоричная модель является Д°-категоричной.

Вычислимая модель ЯЯ называется А^-стабильной, если для любой вычислимой копии ОТ модели ЯЯ любой изоморфизм, действующий из 9Я на ОТ, является Д^-вы числимым. Ясно, что все Дестабильные модели являются Д'^-категоричным и.

Естественным обобщением проблемы 1 для случая автоустойчивости относительно уровней гиперарифметической иерархии является проблема характеризации Д°-категоричности:

Проблема 2. Для данного вычислимого ординала а получить описание Д®-категоричных моделей в данном классе моделей.

Исследование -категоричных моделей было начато в конце 1980-х гг. К.Дж. Эшем в работах [28-31]. Впервые понятия Д°-категоричной и Дестабильной моделей были введены в работе [30]. В [29, 30] разработана техника а-систем, являющаяся важным общим методом исследования вычислимых моделей. В [29] получен критерий -стабильности для вычислимой модели, которая удовлетворяет некоторым дополнительным эффективным условиям. В [29] также исследовалась Д'¿-стабильность для класса вычислимых ординалов. В [28] получены некоторые необходимые и достаточные условия для Д°-категоричности вычислимой структуры. Эти результаты применены для исследования Д°-категоричности суператомных булевых алгебр. В совместной с С. С. Гончаровым работе [31] исследовалась сильная Д^-категоричность.

К.Дж. Эш, Дж. Найт, М. Манассе, Т. Сламан [34] и независимо от них Дж. Чисхолм [38] получили критерий относительной Д^-категоричности вычислимой модели в терминах существования семейства бесконечных формул специального вида. Этот результат является очень важным при исследовании Д°-категоричности.

Отметим, что понятия Д„-категоричности и относительной Д®-категоричности в общем случае не совпадают. С. С. Гончаров [6] построил первый пример автоустойчивой вычислимой модели, не являющейся относительно Д^-категоричной. С.С. Гончаров, В. Ха-ризанов, Дж. Найт, Ч. Мак-Кой, Р. Миллер и Р. Соломон [45] доказали, что для любого вычислимого ординала-последователя а существует Д¡^-категоричная модель, не являющаяся относительно Д°-категоричной. Дж. Чисхолм, Е. Б. Фокина, С. С. Гончаров, В. Харизанов, Дж. Найт и С. Куинн [39] получили аналогичный результат для произвольного вычислимого предельного ординала а.

Тем не менее, если наложить некоторые дополнительные условия на Д®-категоричную модель, то можно доказать, что она является относительно Д°-категоричной. С. С. Гончаров [3] доказал, что любая 2-разрешимая автоустойчивая модель является относительно Д^-категоричной. О. В. Кудинов [16] показал, что данный результат неулучшаем в следующем смысле: существует 1-разрешимая автоустойчивая модель, не являющаяся относительно Д^-категоричной. Понятия автоустойчивости и относительной категоричности совпадают для вычислимых моделей следующих классов: булевы алгебры [9,58], линейные порядки [9,59], абелевы р-группы [36], деревья конечной высоты [52], структуры с эквивалентностью [37].

У. Калверт, Д. Цензер, В. Харизанов и А. С. Морозов исследовали Д®-категоричность для структур с эквивалентностью [37] и абелевых р-групп [36]. В частности, в [37] получено описание относительно Д^-категоричных структур с эквивалентностью и доказано, что любая вычислимая структура с эквивалентностью является относительно Дз-категоричной. Позднее А. М. Кэч и Д. Турецки [50] построили пример Д^-категоричной структуры с эквивалентностью, не являющейся относительно Д^-категоричной. В [36] получено описание относительно Д^-категоричных абелевых р-групп. Д^-категоричность абелевых р-групп также исследовалась Э.Дж. Баркером [35] и Д. И. Душениным [12,13]. Кроме того, Д°-категоричность изучалась для следующих классов структур: вполне разложимые абелевы группы (Р. Доуни, А. Г. Мельников [41,42]), линейно упорядоченные абелевы группы (А. Г. Мельников [54]), структуры с вложением (Д. Цензер, В. Харизанов, Дж. Б. Реммел [26]).

Одним из актуальных современных направлений исследований,

принадлежащих к тематике автоустойчивости моделей, является изучение спектров категоричности вычислимых моделей. Понятия степени категоричности и спектра категоричности для вычислимой модели были введены в 2010 г. в работе Е. Б. Фокиной, И. Ка-лимуллина и Р. Миллера [43].

Пусть «I — тьюрингова степень. Вычислимая модель ОТ называется <1 -вычислимо категоричной, если для любой вычислимой копии ОТ модели ОТ существует (1-вычислимый изоморфизм /: ОТ —>■ 01. Спектром категоричности вычислимой модели ОТ называют множество всех степеней (1, таких что ОТ является <1-вычислимо категоричной. Тьюрингова степень с!о называется степенью категоричности модели ОТ, если <1о является наименьшей степенью в спектре категоричности ОТ. Если степень с1 является степенью категоричности некоторой вычислимой модели, то говорят, что с! категорично определима. Отметим, что в литературе (см., например, [7]) вместо терминов с1-вычислимо категоричная модель, спектр категоричности и степень категоричности иногда используют термины с1 -автоустойчивая модель, спектр автоустойчивости и степень автоустойчивости соответственно.

Определение с1-вычислимой категоричности обобщает понятие А°-категоричности в следующем смысле — нетрудно видеть, что следующие понятия совпадают:

(1) О^-вычислимая категоричность и Д°+1-категоричность для п < ш;

(2) (^"'-вычислимая категоричность и Д®-категоричность для бесконечного вычислимого ординала а.

В связи с проблемами 1 и 2 естественным образом возникает проблема описания спектров категоричности, в настоящее время привлекающая внимание многих исследователей:

Проблема 3. Для данной вычислимой модели найти её спектр категоричности. Более общо, описать возможные спектры категоричности для моделей из данного класса (например, класса всех булевых алгебр).

Известны следующие результаты о степенях категоричности.

Теорема 1 (Е. Б. Фокина, И. Калимуллин, Р. Миллер [43]). (1) Пусть п е и. Если с1 — тьюрингова степень, такая что с! ^ 0<п' и (1 является 2-вычислимо перечислимой относительно О^71', то степень <1 категорично определима.

(2) Степень категорично определима.

В работе [40] получено следующее обобщение теоремы 1:

Теорема 2 (Б. Чима, Дж. Франклин, Р. Шор [40]). Пусть а — вычислимый ординал.

(1) Если с! — тьюрингова степень, такая что а ^ о(а+1) и с! является 2-вычислимо перечислимой относительно то степень с! категорично определима.

(2) Степень категорично определима.

Кроме того, в [40] доказано, что любая категорично определимая тьюрингова степень является гиперарнфметической. Р. Миллер [55] исследовал (¿-вычислимую категоричность для вычислимых полей. В частности, в [55] построено вычислимое алгебраическое поле, являющееся с!-вычислимо категоричным для некоторой низкой степени <1, но не имеющее степени категоричности. Построенное Р. Миллером поле является первым примером вычислимой модели, не обладающей степенью категоричности. Позднее, в [40] построен вычислимый граф, не имеющий степени категоричности и не являющийся Д^-категоричным ни для какого вычислимого ординала а.

Предметом исследования данной диссертации являются булевы алгебры. Булевы алгебры являются классическими объектами, возникающими в различных разделах математики. Попытка собрать хотя бы основные результаты исследований в области булевых алгебр привела к возникновению трёхтомного справочника [47]. Мы будем работать только со счётными булевыми алгебрами. Предварительные сведения по теории счётных булевых алгебр можно найти в монографии С. С. Гончарова [8]. Следуя [8], мы рассматриваем булевы алгебры как модели языка Ь в л — {V2, А2, С1; 0,1}.

Во второй главе диссертации исследуются проблема характери-зации Д°-категоричности (проблема 2) и проблема описания спектров категоричности (проблема 3) для класса булевых алгебр. Приведём краткий обзор известных результатов об уровнях автоустойчивости булевых алгебр.

Напомним, что ненулевой элемент а булевой алгебры 03 называется атомом, если УЬ(Ь < а —>■ Ь = 0). Известно следующее описание автоустойчивых булевых алгебр:

Теорема 3 (С. С. Гончаров, В. Д. Дзгоев [9]; Дж.Б. Реммел [58]). Для вычислимой булевой алгебры 23 следующие условия эквивалентны:

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

(2) 03 относительно А\-категорична;

(3) 23 содержит лишь конечное число атомов.

Если L — линейный порядок, то через 23 (L) обозначается интервальная булева алгебра, порождённая порядком L. Через и обозначается множество натуральных чисел с естественным порядком, через 1] — множество рациональных чисел с естественным порядком.

В работах [17,53] получено описание относительно А®- и относительно Ад-категоричных булевых алгебр.

Теорема 4 (Ч. Мак-Кой [53]). Для вычислимой булевой алгебры 23 следующие условия эквивалентны:

(1) 23 относительно А^-категорична;

(2) Существует конечный набор булевых алгебр 23о, 231 • • • > 23s, такой что алгебра 23 изоморфна прямому произведению ©о х 231 х ... х 233 и для каждого i ^ s либо 23i автоустойчива, либо 23j изоморфна булевой алгебре 23 (w).

Теорема 5 (Ч. Мак-Кой [17]). Для вычислимой булевой алгебры 23 следующие условия эквивалентны:

(1) 23 относительно А^-категорична;

(2) Существует конечный набор булевых алгебр 23о, 231 ■ • •, 23s, такой что алгебра 23 изоморфна прямольу произведению ©о х 23i х ... х 23s и для каждого i ^ s выполнен один из следующих случаев:

(a) 23j относительно А ^-категорична;

(b) 23i изоморфна булевой алгебре 23(w х г]);

(c) 23j изоморфна 23(w + rf).

Кроме того, в [53] показано, что любая Д^-категоричная булева алгебра, удовлетворяющая некоторым дополнительным эффективным условиям, является относительно Д^-категоричной. В параграфе 2.3 диссертации доказано, что этот результат можно обобщить, отказавшись от эффективных условий.

Напомним, что булева алгебра называется суператомной, если все её подалгебры атомные. Известно следующее описание кон-структивизируемых суператомных булевых алгебр:

Теорема 6 (С. С. Гончаров [5]). Для ненулевой суператомной булевой алгебры 23 следующие условия эквивалентны:

(1) 23 конструктивизируема;

(2) Существуют вычислимый ординал а и натуральное число п > 0, такие что 93 изоморфна булевой алгебре 23(üjq х п).

В [28] получено полное описание уровней Д'¿-категоричности для суператомных булевых алгебр.

Теорема 7 (К.Дж. Эш [28]). Пусть а — ненулевой вычислимый ординал, п — ненулевое натуральное число. Тогда булева алгебра 93 (ша х п) является относительно А^а-категоричной и не является А^-категоричной ни для какого ß < 2а.

В параграфе 2.2 диссертации этот результат уточняется следующим образом: получено описание спектров категоричности для суператомных булевых алгебр.

В третьей главе диссертации исследуются алгоритмические свойства для различных классов булевых алгебр с выделенными эндоморфизмами. Алгоритмические свойства булевых алгебр с выделенными автоморфизмами ранее исследовались в работах В. И. Мартьянова [21], A.C. Морозова [22,23], Д. Е. Пальчунова и А. В. Трофимова [24] и др. авторов. В [21] доказана неразрешимость теории булевых алгебр с выделенным автоморфизмом. В [24] исследовались автоморфизмы булевых алгебр, определяемые неподвижными элементами. В частности, в [24] доказано, что автоморфизм булевой алгебры определяется неподвижными элементами в том и только том случае, когда он является инволюцией. В работах А. С. Морозова изучались группы вычислимых автоморфизмов вычислимых булевых алгебр. В [22] доказано, что для любой вычислимой атомной булевой алгебры существует её вычислимая копия, у которой каждый вычислимый автоморфизм передвигает лишь конечное число атомов. В [23] доказан следующий результат: если 21 — вычислимая атомная булева алгебра с вычислимым множеством атомов, 23 — вычислимая булева алгебра, такие что группы вычислимых автоморфизмов этих алгебр элементарно эквивалентны, то 21 и 03 вычислимо изоморфны.

В работе Р. Р. Тухбатуллиной [25] получены некоторые необходимые и достаточные условия для автоустойчивости булевой алгебры 23 (w) с выделенным автоморфизмом. Часть результатов параграфов 3.1 и 3.2 диссертации является продолжением исследования, начатого в [25].

Цели и задачи исследования. Целями настоящей работы являются:

(I) исследование автоустойчивости относительно тьюринговых степеней и автоустойчивости относительно уровней гиперарифметической иерархии для класса булевых алгебр;

(II) исследование алгоритмических свойств различных классов булевых алгебр с выделенными эндоморфизмами.

В качестве основных задач данного исследования можно выделить следующие:

(1) получение описания -категоричных моделей для класса почти суператомных булевых алгебр;

(2) изучение спектров категоричности для суператомных булевых алгебр;

(3) нахождение критерия А^-категоричности для булевых алгебр;

(4) исследование конструктивизируемости и спектров категоричности для булевой алгебры 03 (ш) с выделенным автоморфизмом;

(5) исследование вычислимых нумераций для классов булевых алгебр с выделенными эндоморфизмами.

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

Основные результаты диссертации. На защиту выносятся следующие основные результаты диссертации:

1. Получено описание уровней Д®-категоричности для булевых алгебр вида 23(и^ х т]) (теорема 2.1.1 диссертации, опубликовано в [62]).

2. Получено полное описание спектров категоричности суператомных булевых алгебр (теорема 2.2.1 диссертации, опубликовано в [63]).

3. Доказано, что для булевых алгебр понятия категоричности и относительной Д^-категоричности совпадают. В качестве следствия этого факта получено, что никакая тьюрингова степень «1, удовлетворяющая условиям О < с! < 0', не может быть степенью категоричности булевой алгебры (теорема 2.3.2 и следствие 2.3.3 диссертации, опубликовано в [64]).

4. Получен критерий конструктивизируемости для булевой алгебры *В(ш) с выделенным автоморфизмом (теорема 3.1.1 диссертации, опубликовано в [65]).

5. Для произвольной 2-вычислимо перечислимой тьюринговой степени d построена вычислимая булева алгебра с выделенным автоморфизмом, имеющая степень категоричности d (теорема 3.2.1 диссертации, опубликовано в [66]).

6. Для ненулевого п£ш доказано, что класс всех вычислимых булевых алгебр с тг выделенными эндоморфизмами имеет Д3-вычислимую, но не имеет Д^-вы числимой нумерации с точностью до вычислимого изоморфизма (теорема 3.3.1 и следствие 3.3.1 диссертации, опубликовано в [67]).

Четвёртый из основных результатов получен в неразделимом соавторстве с Р. Р. Тухбатуллиной при равном участии обеих сторон, остальные результаты получены автором самостоятельно.

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

Методология и методы исследований. В работе использованы методы теории вычислимых моделей и методы теории счётных булевых алгебр. Среди использованных методов следует особо выделить технику пар вычислимых моделей и технику порождающих деревьев для булевых алгебр.

Апробация работы. По результатам диссертации были сделаны доклады на следующих международных конференциях: МНСК «Студент и научно-технический прогресс» (Новосибирск, 2010, 2011 гг.), «Лобачевские чтения» (Казань, 2010 г.), «Мальцевские чтения» (Новосибирск, 2010, 2011, 2012 гг.), «Logic Colloquium» (Париж, Франция, 2010 г.; Барселона, Испания, 2011 г.; Эвора, Португалия, 2013 г.). Кроме того, результаты диссертации неоднократно докладывались на совместных семинарах ИМ СО РАН и НГУ «Конструктивные модели» и «Алгебра и логика».

Публикации. Результаты автора по теме диссертации опубликованы в работах [62]- [81], из них [62]- [67] входят в перечень ВАК российских рецензируемых научных журналов, в которых должны быть опубликованы основные научные результаты диссертаций на соискание ученых степеней доктора и кандидата наук. Работы [65,70,76,77,81] написаны совместно с P.P. Тухбатуллиной при равном участии обеих сторон.

Структура и объём диссертации. Диссертация состоит из введения, трёх глав (разбитых на параграфы), заключения и списка литературы (99 наименований). Объём диссертации — 98 страниц. Основные результаты каждого параграфа (теоремы и их следствия) явным образом сформулированы во введении.

В главах все утверждения (теоремы, леммы, предложения, следствия) пронумерованы тремя числами: первое является номером главы, второе — номером параграфа в главе, третье — порядковым номером утверждения в данном параграфе. Нумерация формул состоит из одного числа, являющегося порядковым номером формулы в диссертации.

Содержание диссертации

Глава 1 посвящена необходимым предварительным сведениям. В параграфе 1.1 приводятся предварительные сведения по теории вычислимых моделей. Следуя монографии [32], для вычислимого ординала а вводятся бесконечные EQ-, Па-, и П^-формулы. Приводится определение стандартных челночных отношений Формулируется критерий относительной категоричности модели из работ [34,38]. Приводятся теоремы о парах вычислимых моделей из [32,33], позволяющие строить равномерно вычислимые последовательности вычислимых моделей, обладающие заданными свойствами. Даются предварительные сведения о вычислимых нумерациях классов моделей, спектрах степеней, предельно монотонных множествах.

В параграфе 1.2 приводятся предварительные сведения по теории счётных булевых алгебр. В диссертации булевы алгебры рассматриваются как модели языка Lba = {v2, А2, С1; 0,1} . Даётся описание стандартных челночных отношений для класса суператомных булевых алгебр, полученное в [28]. Следуя монографии [8], приводится краткое описание техники порождающих де-

ревьев для булевых алгебр.

В параграфе 1.3 даётся информация о булевых алгебрах с выделенными эндоморфизмами. Если Л — некоторое положительное натуральное число, то счётная булева алгебра с Л выделенными эндоморфизмами рассматривается как модель языка

Lx=LBAu{fl...,fl}.

и называется Е\-алгеброй. -Ел-алгебру, все выделенные эндоморфизмы которой являются автоморфизмами, называем А\-алгеброй. В параграфе 1.3 вводится понятие характера Ai-алгебры, являющееся ключевым для результатов параграфов 3.1 и 3.2.

Определение. Пусть 21* = (21, /) — yli-алгебра. Множество С, являющееся подмножеством носителя 21, называется атомной орбитой, если существует элемент а, являющийся атомом булевой алгебры 21, такой что С — {/"(а), /_п(о) | п 6 ш}.

Характером Ai-алгебры 21* называем следующее множество:

Х(2Г) ^ {(га, к) | п, к > 0 &¿ попарно различных атомных орбит мощности п в 21*}.

Нетрудно видеть, что ^-алгебры (23(cj), /) и (23(oj),g) изоморфны в том и только том случае, когда их характеры совпадают и они имеют одинаковое число бесконечных атомных орбит.

Глава 2 посвящена исследованию уровней автоустойчивости булевых алгебр. В параграфе 2.1 получено описание гиперарифметических уровней автоустойчивости для почти суператомных булевых алгебр, т. е. булевых алгебр вида 03 (wa х rj), где а — счётный ординал. Основным результатом раздела является следующая теорема:

Теорема 2.1.1. Пусть а — ненулевой вычислимый ординал. Булева алгебра 03(и!а х v¡) является относительно А^+^-категоричной и не является А®а-категоричной.

В параграфе 2.2 получено описание спектров категоричности для суператомных булевых алгебр.

Определение ( [43]). Тьюрингова степень d называется сильной степенью категоричности модели ЯЯ, если d является степенью категоричности ЯЯ и существуют вычислимые копии OTi и ОТг модели ЯЯ, такие что для любого изоморфизма /, действующего из ОТ! в ОТ2, степень d является вычислимой относительно /.

Отметим, что все известные на данный момент степени категоричности являются сильными. С помощью техники пар вычислимых моделей [32,33] в параграфе 2.2 доказана следующая теорема, уточняющая теорему 7.

Теорема 2.2.1. Пусть а — бесконечный вычислилшй ординал, п е и, т £ и \ {0}. Тогда:

(1) 0<2п+1) является сильной степенью категоричности булевой алгебры 23(шп+1 х тп);

(2) ()(2а) является сильной степенью категоричности булевой алгебры 23 х т).

В параграфе 2.3 проводится исследование Д!]-категоричности булевых алгебр. Основным результатом раздела 2.3 является следующая теорема, обобщающая результат Ч. Мак-Коя [53]:

Теорема 2.3.2. Пусть 23 — вычислимая булева алгебра. Алгебра 23 является категоричной тогда и только тогда, когда она относительно А^-категорична.

Доказательство теоремы 2.3.2 опирается на технику порождающих деревьев для булевых алгебр. Отметим, что в ещё не опубликованной работе К. Харриса [49] независимо получен более общий результат: для любого п € из любая Д®+^категоричная булева алгебра является относительно Д°+1-категоричной. Доказательство К. Харриса использует технику п-систем [32].

В качестве следствия теоремы 2.3.2 получен следующий результат о спектрах категоричности:

Следствие 2.3.3. Пусть с1 — тьюрингова степень, такая что О < <1 < 0'. Тогда <1 не может быть степенью категоричности вычислимой булевой алгебры.

Глава 3 посвящена изучению алгоритмических свойств булевых алгебр с конечным числом выделенных эндоморфизмов. В параграфе 3.1 проводится исследование конструктивизируемо-сти булевой алгебры 23 (сл) с выделенным автоморфизмом. Получен следующий критерий конструктивизируемости:

Теорема 3.1.1. Пусть 23* = (*В,д) — А\-алгебра, такая что алгебра 23 изоморфна 23(и/). 23* обладает вычислимым представлением тогда и только тогда, когда выполнено одно из следующих условий:

(1) характер является конечным множеством;

(2) существует вычислимая функция /: и>хш —»■ с<Д{0}, такая что:

(a) (Чх)(/(х,0) = 1),

(b) (Ух)№)(/(х, а) делит /(х, в + 1)),

(c) для любого х существует конечный предел

(с1) для любого п € и количество атомных орбит, содержащихся в 03* и имеющих мощность п, равно количеству х, для которых Нт3 /(х, в) = п.

В качестве следствия релятивизованного варианта теоремы 3.1.1 и результатов [51] доказана следующая теорема о спектрах степеней Лх-алгебр.

Теорема 3.1.4. Существует А\-алгебра 03* = (03,/), такая что В = 03(ш), 0 не лежит в спектре степеней 03*; а любая ненулевая Д2 тьюрингова степень содержится в спектре степеней 58*.

В параграфе 3.2 исследуются спектры категоричности для булевой алгебры 03 (ш) с выделенным автоморфизмом. Доказано следующее утверждение.

Теорема 3.2.1. Пусть с! — 2-вычислимо перечислимая тьюрингова степень. Существует вычислимая А\-алгебра 03* = (03,/), такая что 03 = 03 (ш) и <1 является степенью категоричности 03*.

Следствие 2.3.3 и теорема 3.2.1 показывают существенное различие между возможными спектрами категоричности для класса булевых алгебр и класса булевых алгебр с выделенным автоморфизмом.

Параграф 3.3 посвящён исследованию вычислимых нумераций для классов .Ед-алгебр и Лд-алгебр. При исследовании используется подход, предложенный С. С. Гончаровым и Дж. Найт в [11]. Основным результатом параграфа 3.3 является следующее утверждение:

Теорема (теорема 3.3.1 и следствие 3.3.1). Пусть А — положительное натуральное число. Класс всех вычислимых Е\-алгебр имеет Д3-вычислимую, но не имеет Д®-вычислимой нумерации с точностью до вычислимого изоморфизма.

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

Все доказанные в параграфе 3.1 результаты (кроме теоремы 3.1.4) получены в неразделимом соавторстве с P.P. Тухбатул-линой при равном участии обеих сторон. Результаты главы 2 и параграфов 3.2, 3.3, а также теорема 3.1.4 получены автором самостоятельно.

В заключении излагаются итоги выполненного исследования и некоторые перспективы дальнейшей разработки темы.

Изложение работы заканчивается списком литературы.

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

Список литературы

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

2. Венцов Ю. Г. Алгоритмические свойства ветвящихся моделей // Алгебра и логика. - 198G. - Т. 25, № 4. - С. 369-383.

3. Гончаров С. С. Автоустойчивость и вычислимые семейства кон-структивизаций // Алгебра и логика. - 1975. - Т. 14, У"- 6. -С. 647-680.

4. Гончаров С. С. Автоустойчивость моделей и абелевых групп // Алгебра и логика. - 1980. - Т. 19, 1. - С. 23-44.

5. Гончаров С. С. Конструктивизируемость суператомных булевых алгебр // Алгебра и логика. - 1973. - Т. 12, .X21. - С. 31-40.

6. Гончаров С. С. О числе неавтоэквивалентных конструктивиза-ций // Алгебра и логика. - 1977. - Т. 16, Л* 3. - С. 257-282.

7. Гончаров С. С. Степени автоустойчивости относительно сильных конструктивизаций. // Алгоритмические вопросы алгебры и логики (Тр. МИАН. Т. 274) / Ред. Л. Д. Беклемишев, Е. Ф. Мищенко. - М.: МАИК, 2011. - С. 119-129.

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

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

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

11. Гончаров С. С., Найт Дж. Вычислимые структурные и антиструктурные теоремы // Алгебра и логика. - 2002. - Т. 41, № 6. - С. 639-681.

12. Душенин Д. И. Абелевы р-группы и автоустойчивость относительно оракула // Алгебра и логика. - 2013. - Т. 52, .У5 4. -С. 403-411.

13. Душенин Д. И. Арифметические изоморфизмы абелевых р-групп // Вестн. НГУ. Сер. матем., мех., информ. - 2013. - Т. 13, № 1. - С. 47-56.

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

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

16. Кудинов О. В. Автоустойчивая 1-разрешимая модель без вычислимого семейства Скотта Э-формул // Алгебра и логика. -1996. - Т. 35, № 4. - С. 458-467.

17. Мак-Кой Ч. Ф.Д. О Дз-категоричности для линейных порядков и булевых алгебр // Алгебра и логика. - 2002. - Т. 41, .У2 5. -С. 531-552.

18. Мальцев А. И. Конструктивные алгебры. I // Усп. мат. наук. -1961. - Т. 16, .Хз 3. - С. 3-60.

19. Мальцев А. И. О рекурсивных абелевых группах // Докл. АН СССР. - 1962. - Т. 146, 5. - С. 1009-1012.

20. Мальцев А. И. Строго родственные модели и рекурсивно совершенные алгебры // Докл. АН СССР. - 1962. - Т. 145, .V5 2. -С. 276-279.

21. Мартьянов В. И. Неразрешимость теории булевых алгебр с автоморфизмом // Сиб. мат. журн. - 1982. - Т. 23, -У2 3. - С. 147154.

22. Морозов А. С. О конструктивных булевых алгебрах с почти тождественными автоморфизмами // Мат. заметки. - 1985. -Т. 37, Л* 4. - С. 478-482.

23. Морозов А. С. О рекурсивных автоморфизмах атомных булевых алгебр // Алгебра и логика. - 1990. - Т. 29, Л* 4. - С. 464490.

24. Пальчунов Д. Е., Трофимов А. В. Автоморфизмы булевых алгебр, определяемые неподвижными элементами / / Алгебра и логика. - 2012. - Т. 51, 5. - С. 623-637.

25. Тухбатуллина Р. Р. Автоустойчивость булевой алгебры 25ш, обогащенной автоморфизмом // Вестн. НГУ. Сер. матем., мех., информ. - 2010. - Т. 10, Л* 3. - С. 110-118.

26. Цензер Д., Харизанов В., Реммел Док. Б. Теоретико вычислительные свойства структур с вложением // Алгебра и логика. -2014. - Т. 53, 1. - С. 60-108.

27. Alaev P. Е. Computably Categorical Boolean Algebras Enriched by Ideals and Atoms // Ann. Pure Appl. Logic. - 2012. - V. 163, N 5. - P. 485-499.

28. Ash C. J. Categoricity in Hyperarithmetical Degrees // Ann. Pure Appl. Logic. - 1987. - V. 34, N 1. - P. 1-14.

29. Ash C. J. Recursive Labelling Systems and Stability of Recursive Structures in Hyperarithmetical Degrees // Trans. Amer. Math. Soc. - 1986. - V. 298, N 2. - P. 497-514.

30. Ash C. J. Stability of Recursive Structures in Arithmetical Degrees // Ann. Pure Appl. Logic. - 1986. - V. 32, N 2. - P. 113135.

31. Ash C. J., Goncharov S. S. Strong Categoricity // Algebra and Logic. - 1985. - V. 24, N 6. - P. 471-476.

32. Ash C. J., Knight J. F. Computable Structures and the Hyperarithmetical Hierarchy. (Stud. Logic Found. Math., V. 144.) - Amsterdam: Elsevier Science, 2000. - 346+xvi p.

33. Ash C. J., Knight J. F. Pairs of Recursive Structures // Ann. Pure Appl. Logic. - 1990. - V. 46, N 3. - P. 211-234.

34. Ash C., Knight J., Manasse M., Slaman T. Generic Copies of Countable Structures // Ann. Pure Appl. Logic. - 1989. - V. 42, N 3. - P. 195-205.

35. Barker E. J. Back and Forth Relations for Reduced Abelian p-groups // Ann. Pure Appl. Logic. - 1995. - V. 75, N 3. - P. 223249.

36. Calvert W., Cenzer D., Harizanov V.S., Morozov A. Effective Categoricity of Abelian p-groups // Ann. Pure Appl. Logic. -2009. - V. 159, N 1-2. - P. 187-197.

37. Calvert W., Cenzer D., Harizanov V., Morozov A. Effective Categoricity of Equivalence Structures // Ann. Pure Appl. Logic. -2006. - V. 141, N 1-2. - P. 61-78.

38. Chisholm J. Effective Model Theory vs. Recursive Model Theory // J. Symb. Logic. - 1990. - V. 55, N 3. - P. 1168-1191.

39. Chisholm J., Fokina E.B., Goncharov S.S., Harizanov V.S., Knight J. F., Quinn S. Intrinsic Bounds on Complexity and Definability at Limit Levels //J. Symb. Logic. - 2009. - V. 74, N 3. - P. 1047-10G0.

40. Csima B. F., Franklin J. N. Y., Shore R. A. Degrees of Categoricity and the Hyperarithmetic Hierarchy // Notre Dame J. Formal Logic. - 2013. - V. 54, N 2. - P. 215-231.

41. Downey R., Melnikov A. G. Computable Completely Decomposable Groups // Trans. Amer. Math. Soc. - 2014. -V. 366, N 8. - P. 4243-4266.

42. Downey R., Melnikov A. G. Effectively Categorical Abelian Groups // J. Algebra. - 2013. - V. 373. - P. 223-248.

43. Fokina E. В., Kalimullin I., Miller R. Degrees of Categoricity of Computable Structures // Arch. Math. Logic. - 2010. - V. 49, N 1. - P. 51-67.

44. Fröhlich A., Shepherdson J. C. Effective Procedures in Field Theory // Philos. Trans. Roy. Soc. London. Ser. A. - 1956. -V. 248, N 950. - P. 407-432.

45. Goncharov S., Harizanov V., Knight J., McCoy C., Miller R., Solomon R. Enumerations in Computable Structure Theory // Ann. Pure Appl. Logic. - 2005. - V. 136, N 3. - P. 219-246.

46. Goncharov S. S., Lempp S., Solomon R. The Computable Dimension of Ordered Abelian Groups // Adv. Math. - 2003. -V. 175, N 1. - P. 102-143.

47. Handbook of Boolean Algebras. / Eds. J.D. Monk, S. Koppelberg, Ft. Bonnet. - Amsterdam: Elsevier Science, 1989.

48. Handbook of Recursive Mathematics. Volume 1: Recursive Model Theory. (Stud. Logic Found. Math., V. 138.) / Eds. Yu.L. Ershov, S. S. Goncharov, A. Nerode, J. B. Remmel. - Amsterdam: Elsevier Science, 1998. - 620+xlvi p.

49. Harris K. Categoricity in Boolean Algebras [Электронный ресурс]. - Режим доступа: http://kaharris.org/papers/cat. pdf.

50. Kach A. M., Turetsky D. A^-categoricity of Equivalence Structures // New Zealand J. Math. - 2009. - V. 39. - P. 143-149.

51. Kalimullin I., Khoussainov В., Melnikov A. Limitwise Monotonie Sequences and Degree Spectra of Structures // Proc. Amer. Math. Soc. - 2013. - V. 141, N 9. - P. 3275-3289.

52. Lempp S., McCoy C., Miller R., Solomon R. Computable Categoricity of Trees of Finite Height //J. Symb. Logic. - 2005. -V. 70, N 1. - P. 151-215.

53. McCoy C.F.D. A^-categoricity in Boolean Algebras and Linear Orderings // Ann. Pure Appl. Logic. - 2003. - V. 119, N 1-3. -P. 85-120.

54. Melnikov A. G. Computable Ordered Abelian Groups and Fields. // In: Programs, Proofs, Processes (Lect. Notes Comp. Sci. V. 6158) / Eds. F. Ferreira, B. Lowe, E. Mayordomo, L.M. Gomes. - Berlin: Springer, 2010. - P. 321-330.

55. Miller R. d-computable Categoricity for Algebraic Fields // J. Symb. Logic. - 2009. - V. 74, N 4. - P. 1325-1351.

56. Miller R. The Computable Dimension of Trees of Infinite Height // J. Symb. Logic. - 2005. - V. 70, N 1. - P. 111-141.

57. Rabin M. O. Computable Algebra, General Theory and Theory of Computable Fields // Trans. Amer. Math. Soc. - 1960. - V. 95, N 2. - P. 341-360.

58. Remmel J. B. Recursive Isomorphism Types of Recursive Boolean Algebras // J. Symb. Logic. - 1981. - V. 46, N 3. - P. 572-594.

59. Remmel J.B. Recursively Categorical Linear Orderings // Proc. Amer. Math. Soc. - 1981. - V. 83, N 2. - P. 387-391.

60. Smith R. L. Two Theorems on Autostability in p-groups // In: Logic Year 1979-80 (Lect. Notes Math. V. 859) / Eds. M. Lerman, J. H. Schmerl, R. I. Soare. - Berlin: Springer-Verlag, 1981. - P. 302311.

61. van der Waerden B.L. Eine Bemerkung über die Unzerlegbarkeit von Polynomen // Mathematische Annalen. - 1930. - V. 102, N 1. -P. 738-739.

Работы автора по теме диссертации

Оригинальные статьи

62. Баженов Н. А. О категоричности булевых алгебр типа 03 (wQ х ■q) в гиперарифметической иерархии // Вестн. НГУ. Сер. ма-тем., мех., информ. - 2012. - Т. 12, Л* 3. - С. 35-45.

63. Баженов Н. А. Степени категоричности суператомных булевых алгебр // Алгебра и логика. - 2013. - Т. 52, > 3. - С. 271-283.

64. Баженов Н. А. О Д^-категоричности булевых алгебр // Вестн. НГУ. Сер. матем., мех., информ. - 2013. - Т. 13, № 2. - С. 3-14.

65. Баженов Н.А., Тухбатпуллина P.P. Конструктивизируемость булевой алгебры 03 (w) с выделенным автоморфизмом // Алгебра и логика. - 2012. - Т. 51, Л* 5. - С. 579-607.

66. Баженов Н. А. О 2-вычислимо перечислимых степенях категоричности булевых алгебр с выделенным автоморфизмом // Вестн. НГУ. Сер. матем., мех., информ. - 2014. - Т. 14, 1. -С. 19-27.

67. Баженов Н. А. О вычислимых нумерациях класса булевых алгебр с выделенными эндоморфизмами // Алгебра и логика. -

2013. - Т. 52, 5. - С. 535-552.

Переводы оригинальных статей на английский язык

68. Bazhenov N. A. Hyperarithmetical Categoricity of Boolean Algebras of Type 03 (wQ X77) // Journal of Mathematical Sciences. -

2014. - V. 202, N 1. - P. 40-49.

69. Bazhenov N.A. Degrees of Categoricity for Superatomic Boolean Algebras // Algebra and Logic. - 2013. - V. 52, N 3. - P. 179-187.

70. Bazhenov N.A., Tukhbatullina R.R. Constructivizability of the Boolean algebra 03 (w) with a Distinguished Automorphism // Algebra and Logic. - 2012. - V. 51, N 5. - P. 384-403.

71. Bazhenov N. A. Computable Numberings of the Class of Boolean Algebras with Distinguished Endomorphisms // Algebra and Logic. - 2013. - V. 52, N 5. - P. 355-366.

Тезисы конференций

72. Баженов Н. А. О Д^-категоричности булевых алгебр // Лобачевские чтения — 2010 (Тр. Мат. центра им. Н. И. Лобачевского. Т. 40). - Казань: Казанское математическое общество,

2010. - С. 54-55.

73. Баженов Н. А. О -категоричности булевой алгебры 23 (w* х г/) // Мальцевские чтения 2010. Тезисы докладов. - Новосибирск: 2010. - С. 45.

74. Баженов Н.А. Об автоустойчивости булевых алгебр типа Ъ(шп х г]) относительно арифметических степеней // Материалы XLVIII Международной студенческой конференции «Студент и научно-технический прогресс». Математика. - Новосибирск: НГУ, 2010. - С. 21.

75. Баженов Н. А. Степени категоричности суператомных булевых алгебр // Мальцевские чтения 2012. Тезисы докладов. - Новосибирск: 2012. - С. 37.

76. Баженов Н.А., Тухбатпуллина P.P. О конструктивизируемо-сти булевой алгебры 23 (w) с выделенным автоморфизмом // Мальцевские чтения 2011. Тезисы докладов. - Новосибирск:

2011. - С. 101.

77. Баженов Н. А., Тухбатпуллина Р. Р. Об автоустойчивости булевой алгебры 23 (w). обогащенной автоморфизмом // Материалы XLIX Международной студенческой конференции «Студент и научно-технический прогресс». Математика. - Новосибирск: НГУ, 2011. - С. 23.

78. Bazhenov N. On Д° Categoricity of the Boolean Algebra /(оУ3 x rj) 11 Bull. Symb. Logic. - 2011. - V. 17, N 2. - P. 287-288.

79. Bazhenov N. On Categoricity Spectra of Boolean Algebras // Bull. Symb. Logic. - 2012. - V. 18, N 3. - P. 440-441.

80. Bazhenov N. On Computable Enumerations of Boolean Algebras with Distinguished Endomorphisms // Logic Colloquium 2013. Scientific Program and Abstracts. - Evora: 2013. - P. 81.

81. Tukhbatullina R., Bazhenov N. On Computable Categoricity of Boolean Algebra ©(w) Distinguished by Automorphism // Bull. Symb. Logic. - 2012. - V. 18, N 3. - P. 4G7-468.

Баженов Николай Алексеевич

УРОВНИ АВТОУСТОЙЧИВОСТИ БУЛЕВЫХ АЛГЕБР

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

Подписано в печать11.09.2014 г. Печать цифровая. Бумага офсетная. Формат 60x84/16. Усл. печ. л. 1 Тираж 100 экз. Заказ № 226

Отпечатано в типографии «Срочная полиграфия» ИП Малыгин Алексей Михайлович

630090, Новосибирск, пр-т Академика Лаврентьева, 6/1, оф.104 Тел. (383)217-43-46, 8-913-922-19-07