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

• Баженов, Николай Алексеевич
• кандидат наук
• 2014

Оглавление диссертации кандидат наук Баженов, Николай Алексеевич

Оглавление

Введение

1. Предварительные сведения

1.1. Теория вычислимых моделей

1.2. Счетные булевы алгебры

1.3. Булевы алгебры с выделенными эндоморфизмами

2. Уровни автоустойчивости булевых алгебр

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

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

2.3. А^-категоричность булевых алгебр

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

3.1. Конструктивизируемость булевой алгебры *3(ш) с выделенным автоморфизмом

3.2. Степени категоричности булевой алгебры с выделенным автоморфизмом

3.3. Вычислимые нумерации класса булевых алгебр с выделенными эндоморфизмами

Заключение

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

Введение диссертации (часть автореферата) на тему «Уровни автоустойчивости булевых алгебр»

Введение

Актуальность темы исследования. Диссертация посвящена исследованию некоторых вопросов теории вычислимых (конструктивных) моделей. Теория вычислимых (конструктивных) моделей начала развиваться в середине XX века в работах А. И. Мальцева [22-24], М. О. Рабина [74], А. Фрёлиха и Дж. Шефердсона [53] и др. авторов. С тех пор теория вычислимых моделей стала одной из наиболее актуальных и активно развивающихся областей математической логики. Подробную информацию по теории вычислимых моделей можно найти в [12,39,54,56,59].

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

Конструктивизируемая модель ШТ называется автоустойчивой, если для любых вычислимых копий ОТх и т2 модели ЯЯ существует вычислимый изоморфизм /: 9Тх —>■ ОТг- Автоустойчивые модели также называют вычислимо категоричными или Д®-категоричными.

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

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

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

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

пример, в классе всех булевых алгебр или в классе всех линейных порядков).

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

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

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

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

В настоящее время известны критерии автоустойчивости для целого ряда классов структур, широко используемых в алгебре и математической логике. С. С. Гончаров, С. Лемпп и Р. Соломон [57] доказали, что вычислимая линейно упорядоченная абелева группа является автоустойчивой в том и только том случае, когда она имеет конечный ранг. С. Лемпп, Ч. Мак-Кой, Р. Миллер и Р. Соломон [68] дали описание автоустойчивых деревьев конечной высоты. Р. Миллер [72] доказал, что не существует автоустойчивых деревьев бесконечной высоты. Н. Т. Когабаев, О. В. Кудинов и Р. Миллер [19] доказали, что не существует автоустойчивых деревьев с выделенным начальным поддеревом, имеющих бесконечную высоту. У. Калверт, Д. Цензер, В. Харизанов и А. С. Морозов [45] получили критерий автоустойчивости для структур с эквивалентностью. Н. Т. Когабаев [16] получил описание автоустойчивых булевых алгебр с выделенным идеалом. П. Е. Алаев [1,2,34] получил описание автоустойчивых булевых алгебр с конечным числом выделенных идеалов и множеств атомов в факторе по этим идеалам.

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

гиперарифметической иерархии.

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

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

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

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

Исследование Д°-категоричных моделей было начато в конце 1980-х гг. К. Дж. Эшем в работах [35-38]. Впервые понятия Д®-категоричной и Дестабильной моделей были введены в работе [37]. В [36,37] разработана техника а-систем, являющаяся важным общим методом исследования вычислимых моделей. В [36] получен критерий -стабильности для вычислимой модели, которая удовлетворяет некоторым дополнительным эффективным условиям. В [36] также исследовалась -стабильность для класса вычислимых ординалов. В [35] получены некоторые необходимые и достаточные условия для Д°-категоричности вычислимой структуры. Эти результаты применены для исследования Д°-категоричности суператомных булевых алгебр. В совместной с С. С. Гончаровым работе [38] исследовалась сильная Д°-категоричность.

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

очень важным при исследовании А°-категоричности.

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

Тем не менее, если наложить некоторые дополнительные условия на Ад-категоричную модель, то можно доказать, что она является относительно Д°-категоричной. С. С. Гончаров [4] доказал, что любая 2-разрешимая автоустойчивая модель является относительно А^-категоричной. О. В. Кудинов [20] показал, что данный результат неулучшаем в следующем смысле: существует 1-разрешимая автоустойчивая модель, не являющаяся относительно Д^-категоричной. Понятия автоустойчивости и относительной А^-категоричности совпадают для вычислимых моделей следующих классов: булевы алгебры [11,75], линейные порядки [11,76], абелевы р-группы [44], деревья конечной высоты [68], структуры с эквивалентностью [45].

У. Калверт, Д. Цензер, В. Харизанов и А. С. Морозов исследовали Д°-категоричность для структур с эквивалентностью [45] и абелевых р-групп [44]. В частности, в [45] получено описание относительно Д^-категоричных структур с эквивалентностью и доказано, что любая вычислимая структура с эквивалентностью является относительно Ад-категоричной. Позднее А. М. Кэч и Д. Турецки [64] построили пример Аз-категоричной структуры с эквивалентностью, не являющейся относительно Д^-категоричной. В [44] получено описание относительно А^-категоричных абелевых р-групп. Д°-категоричность абелевых р-групп также исследовалась Э. Дж. Баркером [43] и Д. И. Душениным [14,15]. Кроме того, Ад-категоричность изучалась для следующих классов структур: вполне разложимые абелевы группы (Р. Доуни, А. Г. Мельников [50,51]), линейно упорядоченные абелевы группы (А. Г. Мельников [70]), структуры с вложением (Д. Цензер, В. Харизанов, Дж. Б. Реммел [33]).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В работах [21,69] получено описание относительно Д°- и относительно Дд-категоричных булевых алгебр.

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

(1) 03 относительно категорична;

(2) Существует конечный набор булевых алгебр ОЗо, 03:..., 035, такой что алгебра 03 изоморфна прямому произведению ОЗо х ОЗ1 х ... х 03« и для каждого г ^ в либо 93* автоустойчива, либо 03 ^ изоморфна булевой алгебре 03 (ш).

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

(1) 03 относительно Дд-категорична;

(2) Существует конечный набор булевых алгебр 03о,031... ,035, такой что алгебра 03 изоморфна прямому произведению 03о х 03х х ... х 93а и для каждого г ^ з выполнен один из следующих случаев:

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

(b) ОЗг изоморфна булевой алгебре 03(и х г/);

(c) ОЗг изоморфна *3(и + г]).

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

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

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

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

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

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

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

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

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

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

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

и

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

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

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

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

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

3. нахождение критерия Д°-категоричности для булевых алгебр;

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

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

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

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

1. Получено описание уровней Д^-категоричности для булевых алгебр вида 03 (и/3 х 77) (опубликовано в [80]).

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

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

4. Получен критерий конструктивизируемости для булевой алгебры 23 (о;) с выделенным автоморфизмом (опубликовано в [83]).

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

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

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

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

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

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

Публикации. Результаты автора по теме диссертации опубликованы в работах [80]-[99], из них [80]- [85] входят в перечень ВАК российских рецензируемых научных журналов, в которых должны быть опубликованы основные научные результаты диссертаций на соискание ученых степеней доктора и кандидата наук. Работы [83,88,94,95,99] написаны совместно с Р. Р. Тухбатуллиной при равном участии обеих сторон.

Структура и объём диссертации. Диссертация состоит из введения, трёх глав (раз-

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

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

Обзор содержания диссертации.

Глава 1 посвящена необходимым предварительным сведениям. В параграфе 1.1 приводятся предварительные сведения по теории вычислимых моделей. Следуя монографии [39], для вычислимого ординала а вводятся бесконечные £а-, Па-, и Щ-формулы. Приводится определение стандартных челночных отношений Формулируется критерий относительной -категоричности модели из работ [42,46]. Приводятся теоремы о парах вычислимых моделей из [39,40], позволяющие строить равномерно вычислимые последовательности вычислимых моделей, обладающие заданными свойствами. Даются предварительные сведения о вычислимых нумерациях классов моделей, спектрах степеней, предельно монотонных множествах.

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

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

ьх = ьва и{/11,...,/л1}.

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

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

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

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

Нетрудно видеть, что Лх-алгебры (03(и>),/) и (93 (ш), д) изоморфны в том и только том случае, когда их характеры совпадают и они имеют одинаковое число бесконечных атомных орбит.

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

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

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

Определение ([52]). Тьюрингова степень с! называется сильной степенью категоричности модели £Ш, если с! является степенью категоричности Ш и существуют вычислимые копии 9Тх и ОТг модели 9Л, такие что для любого изоморфизма /, действующего из 9Тх в ОТг, степень с! является вычислимой относительно /.

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

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

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

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

В параграфе 2.3 проводится исследование Д^-категоричности булевых алгебр. Основ-

ным результатом раздела 2.3 является следующая теорема, обобщающая результат Ч. Мак-Коя [69]:

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

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

Список литературы диссертационного исследования кандидат наук Баженов, Николай Алексеевич, 2014 год

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

1. Алаев П. Е. Автоустойчивость атомно-идеальных обогащений вычислимых булевых алгебр // Докл. АН. - 2010. - Т. 433, № 2. - С. 151-153.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

17. Когабаев Н. Т. Класс проективных плоскостей невычислим // Алгебра и логика. - 2008. -Т. 47, № 4. - С. 428-455.

18. Когабаев Н. Т. Универсальная нумерация конструктивных /-алгебр // Алгебра и логика. - 2001. - Т. 40, № 5. - С. 561-579.

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

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

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

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

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

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

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

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

27. Морозов А. С. О рекурсивных автоморфизмах атомных булевых алгебр // Алгебра и логика. - 1990. - Т. 29, № 4. - С. 464-490.

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

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

30. Соар Р. И. Вычислимо перечислимые множества и степени. - Казань: Казанское математическое общество, 2000. - 576 с.

31. Семухин П. М. Спектры степеней определимых отношений на булевых алгебрах // Сиб. мат. журн. - 2005. - Т. 46, № 4. - С. 928-941.

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

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

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

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

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

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

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

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

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

41. Ash C. J., Knight J. F. Relatively Recursive Expansions // Fundam. Math. - 1992. - V. 140, N 2. - P. 137-155.

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

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

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

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

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

47. 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-1060.

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

49. Downey R. G., Kach A. M., Turetsky D. Limitwise Monotonie Functions and Their Applications // In: Proc. of the Eleventh Asian Logic Conf. / Eds. T. Arai, Q. Feng, B. Kim, G. Wu, Y. Yang. - Singapore: World Scientific, 2011. - P. 59-85.

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

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

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

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

54. Goncharov S. S. Computability and Computable Models // In: Mathematical Problems from Applied Logic II / Eds. D. M. Gabbay, S. S. Goncharov, M. Zakharyaschev. - N.Y.: Springer, 2006. - P. 99-216.

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

56. Goncharov S., Khoussainov B. Open Problems in the Theory of Constructive Algebraic Systems // In: Computability Theory and its Applications / Eds. P. A. Cholak, S. Lempp, M. Lerman, R. A. Shore. - Providence: Amer. Math. Soc., 2000. - P. 145-170.

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

58. Handbook of Boolean Algebras, j Eds. J. D. Monk, S. Koppelberg, R. Bonnet. - Amsterdam: Elsevier Science, 1989.

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

60. Harizanov V. S. Pure Computable Model Theory. In: 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. - P. 3-114.

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

62. Harris K. 77-representation of Sets and Degrees //J. Symb. Logic. - 2008. - V. 73, N 4. -P. 1097-1121.

63. Harrison J. Recursive Pseudo-well-orderings // Trans. Amer. Math. Soc. - 1968. - V. 131, N 2. - P. 526-543.

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

65. Kach A. M., Turetsky D. Limitwise Monotonic Functions, Sets, and Degrees on Computable Domains // J. Symb. Logic. - 2010. - V. 75, N 1. - P. 131-154.

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

67. Knight J. F. Degrees Coded in Jumps of Orderings //J. Symb. Logic. - 1986. - V. 51, N 4. -P. 1034-1042.

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

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

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

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

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

73. Montalbán A. On the Triple Jump of the Set of Atoms of a Boolean Algebra // Proc. Amer. Math. Soc. - 2008. - V. 136, N 7. - P. 2589-2595.

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

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

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

77. Sacks G. E. Recursive Enumerability and the Jump Operator // Trans. Amer. Math. Soc. -1963. - V. 108. N 2. - P. 223-239.

78. 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. 302-311.

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

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

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

80. Баженов Н. А. О категоричности булевых алгебр типа 93 х rj) в гиперарифметической иерархии // Вестн. НГУ. Сер. матем., мех., информ. - 2012. - Т. 12, № 3. - С. 35-45.

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

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

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

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

85. Баженов Н. А. О вычислимых нумерациях класса булевых алгебр с выделенными эндоморфизмами // Алгебра и логика. - 2013. - Т. 52, № 5. - С. 535-552.

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

86. Bazhenov N. A. Hyperarithmetical Categoricity of Boolean Algebras of Type 93(cj° x 77) // Journal of Mathematical Sciences. - 2014. - V. 202, N 1. - P. 40-49.

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

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

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

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

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

91. Баженов Н.А. О Д°-категоричности булевой алгебры 58 (и/ х rj) // Мальцевские чтения

2010. Тезисы докладов. - Новосибирск: 2010. - С. 45.

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

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

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

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

96. Bazhenov N. On Д° Categoricity of the Boolean Algebra /(и& x rf) // Bull. Symb. Logic. -

2011. - V. 17, N 2. - P. 287-288.

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

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

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