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

• Автор: Баженов, Николай Алексеевич
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 2014
• Место защиты: Новосибирск
• Количество страниц: 98 с.

Оглавление
Введение
1. Предварительные сведения
1.1. Теория вычислимых моделей
1.2. Счетные булевы алгебры
1.3. Булевы алгебры с выделенными эндоморфизмами
2. Уровни автоустойчивости булевых алгебр
2.1. Гиперарифметические уровни автоустойчивости для почти суператомных булевых алгебр
2.2. Степени категоричности суператомных булевых алгебр
2.3. Д°-категоричность булевых алгебр
3. Алгоритмические свойства булевых алгебр с выделенными эндоморфизмами
3.1. Конструктивизируемость булевой алгебры 53 (о>) с выделенным автоморфизмом
3.2. Степени категоричности булевой алгебры 53(о;) с выделенным автоморфизмом
3.3. Вычислимые нумерации класса булевых алгебр с выделенными эндоморфизмами
Заключение
Список литературы

Введение
Актуальность темы исследования. Диссертация посвящена исследованию некоторых вопросов теории вычислимых (конструктивных) моделей. Теория вычислимых (конструктивных) моделей начала развиваться в середине XX века в работах А. И. Мальцева [22-24], М. О. Рабина [74], А. Фрёлиха и Дж. Шефердсона [53] и др. авторов. С тех пор теория вычислимых моделей стала одной из наиболее актуальных и активно развивающихся областей математической логики. Подробную информацию по теории вычислимых моделей можно найти в [12,39,54,56,59].
Напомним, что модель конечного языка называется вычислимой, если её носитель и предикаты являются вычислимыми множествами, а операции — частично вычислимыми функциями. Модель называется конструктивизируемой, если она имеет вычислимую изоморфную копию.
Конструктивизируемая модель 9Л называется автоустойчивой, если для любых вычислимых копий ЭТ1 и 912 модели 9Я существует вычислимый изоморфизм /: 911 —>• 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] доказал, что не существует автоустойчивых деревьев бесконечной высоты. H. Т. Когабаев, О. В. Кудинов и Р. Миллер [19] доказали, что не существует автоустойчивых деревьев с выделенным начальным поддеревом, имеющих бесконечную высоту. У. Калверт, Д. Цензер, В. Харизанов и A.C. Морозов [45] получили критерий автоустойчивости для структур с эквивалентностью. H. Т. Когабаев [16] получил описание автоустойчивых булевых алгебр с выделенным идеалом. П. Е. Алаев [1,2,34] получил описание автоустойчивых булевых алгебр с конечным числом выделенных идеалов и множеств атомов в факторе по этим идеалам.
Отметим, что в классическом определении автоустойчивости рассматриваются только вычислимые изоморфизмы. Понятие Д° -категоричности даёт естественное обобщение понятия автоустойчивости для случая изоморфизмов, принадлежащих фиксированному уровню

алгебра е) изоморфна алгебре /,, так как е)/р = 23 (д;) = /•/р^, а е) и /3-атомны. В противном случае Фа^(ас) говорит о том, что /(х) не лежит в Рг+„, следовательно, е} = »(«**> хЧ)^/;
Итак, для любого 1 ф ^ ф гп мы показали, что е) = следовательно, существует изоморфизм г/-1: (25, ё) = (25,/). Заметим, что с* = /г(ё), ф = <г(/), где V — некоторые термы
Для описания стандартных челночных отношений для почти суператомных булевых алгебр нам понадобится следующее вспомогательное утверждение.
Лемма 2.1.3. Пусть а,/3 — счётные ординалы, 5 — счётный предельный ординал или ноль, к, I — натуральные числа, I ^ 0.
(а) Предположим, что 5 + к ^ 1.
(2) 23(ша х I) ^5+26 23(иУ3 х у) тогда и только тогда, когда /3+1 ^ 5 + к и а 5 + к.
(Ь) (1) 25(и/ х у) ^{+2)ь+1 23(ша х I) тогда и только тогда, когда (3^5 + киа^6 + к.
(2) *8(шах/) ^{+2к+1 23(ш^ хт;) тогда и только тогда, когда /3 ^ 5+к и а ^ 5+к+.
Доказательство. НЕОБХОДИМОСТЬ. Пусть /3 = Л + п, где А — предельный ординал или 0,
п £ СП.
(Ь.2) В 25(02^ х у) истинна следующая Ел+2п+3-формула:
Ясно, что для любых а и / 25(о/* х I) У=- Ф,. Следовательно, ô + 2k + 1 должно быть меньше А + 2п + 3, т. е. 5 + к < /3.
В 23 (и/ х у) истинна Е^+2к+1-формула
Из того, что в 23(ша х I) должна быть истинна формула Ф2, легко вывести, что 5 + к < а. (а.2) С помощью формулы <3>1 нетрудно получить следующее ограничение: 5+к ф /3 + 1. Выберем некоторый ординал 7 < 5 + к и представим его в виде 7 = ц + т, где р —
языка Ьва- Поэтому ф: (23, с) = (23, d). Лемма 2.1.2 доказана.

(1) 23(ы3 х 77) ^j+2*/ 23(w“ х Z) тогда и только тогда, когда P^S + kua^S+k.
Фі ^ 3x(Alsx+n(x) & -*Fx+n(x))