Сильная конструктивизируемость булевых алгебр

• Автор: Леонтьева, Маргарита Николаевна
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 2013
• Место защиты: Новосибирск
• Количество страниц: 67 с.

Оглавление
Введение
1 Достаточность условий сильной конструктивизируемости для булевых алгебр
с ch <00
2 Минимальность условий сильной конструктивизируемости для булевых алгебр
с chi <00
2.1 Булева алгебра характеристики (1,0,1) с вычислимыми
предикатами At и Е. не имеющая сильно вычислимого представления .
2.2 Одно описание Дд-вычислимых алгебр
2.3 Булева алгебра характеристики (п, оо, 0) с вычислимыми предикатами из Фп+і{Аі„}. не имеющая сильно
вычислимого представления
2.4 Булева алгебра характеристики (п, 0,1) с вычислимыми предикатами из ®n+i{Alsn_i, Atm„_i}, не имеющая
сильно вычислимого представления
2.5 Булева алгебра характеристики (п, оо, 0) с вычислимыми предикатами из Фп+і{А1вп_і, Atm„_i}. не имеющая сильно вычислимого представления
3 Сильная конструктивизируемость булевых алгебр элементарных характеристик (п. к + 1, 0), (п, к, 1) и
(п, оо, 1) для к > 0
4 Сильная конструктивизируемость булевых алгебр
элементарной характеристики (оо, 0, 0)
Литература

Введение
Теория вычислимости начала развиваться в 30-х годах прошлого века в работах Гёделя, Тьюринга, Поста и др., и, будучи исследованием общих свойств алгоритмов, продолжает и сейчас привлекать внимание широкого круга исследователей. В данной работе речь пойдет об изучении алгоритмических свойств некоторого класса моделей на основе их представления на множестве натуральных чисел, то есть о вопросах теории вычислимых (конструктивных) моделей, которая берет истоки в 50-х годах прошлого века в трудах А.И. Мальцева [13], М.О. Рабина [23], Р. Воота [24], В.А. Кузнецова, А.Фрёлиха и Дж. Шефердсона [18]. Полученные результаты относятся к классу вычислимых булевых алгебр, изучению которых в частности посвящен ряд работ Ю.Л. Ершова, С.С. Гончарова и их учеников, а также многочисленных зарубежных исследователей.
Модель конечного языка называется вычислимой, если её носитель — вычислимое множество натуральных чисел, операции — вычислимые функции, и отношения вычислимы. Вычислимая модель называется п-вычислимой, если существует алгоритм, определяющий по конечной Е„-формуле и набору элементов, истинна ли эта формула на этом наборе. Сильно вычислимая модель — та, для которой подобный алгоритм существует для всех формул исчисления предикатов. Мы будем называть модель конструктивизируемой, если у нее существует вычислимое представление (изоморфная копия), и сильно конструктпивизируемой, если у неё существует сильно вычислимая изоморфная копия.
Понятие сильно вычислимой (сильно конструктивной) модели было введено Ю. Л. Ершовым [10] в 1968 году. Заметим, что данная теория активно разрабатывалась в математической школе А. Нероуда на основе аналогичного (по-существу, эквивалентного) понятия разрешимой модели, изучаемого также Л. Харрингтоном [21] и М. Морли [22].
В диссертации рассматриваются булевы алгебры - дистрибутивные решетки с наибольшим и наименьшим элементами, и дополнениями. В решетке у каждых двух

элементов х и у есть точная нижняя и верхняя грань, которые, следуя [19], будем символически обозначать как х ■ у к х + у, соответственно. Дополнение элемента х до наибольшего элемента булевой алгебры обозначаем (—ж). Говоря о вычислимой булевой алгебре, будем подразумевать, что она вычислима, как модель в языке Т,ВА = {+, •, —, 0,1}, где 0 и 1 соответствуют наименьшему и наибольшему элементам.
Булевы алгебры являются классическими объектами, возникающими в различных разделах математики и привлекающими внимание исследователей уже в течении полутора веков. Попытка собрать хотя бы основные достижение в этой области привела к появлению трехтомного справочника [19]. Мы будем работать со счетными булевыми алгебрами, называя их кратко алгебрами; в качестве источника предварительных сведений по теории булевых алгебр будем использовать [6]. С точки зрения теории вычислимых моделей одним из наиболее естественных вопросов является описание тех булевых алгебр, которые являются сильно конструктивизируемыми.
Перейдем к описанию задач, которым посвящена данная диссертация. Для этого сначала сформулируем ряд понятий и обозначений.
Для произвольных идеалов ф и 1г булевой алгебры будем использовать следующее обозначение: ф + 12 = {х + ух 6 Д, у € I2}.
Пусть 23 — алгебра. Ненулевой элемент а 6 23 называется атомом, если V6(Ь < а =4* Ъ = 0). Множество атомов алгебры © обозначим At0(23). Элемент a £ 23 называется атомным, если Уж ^ а(ж ф 0 => (3 у ^ ж (у £ Ato(23)))). Атомные элементы образуют идеал, который мы будем обозначать как Atm о (23). Элемент а € 23 называется безатомным, если Уж а (х ф Аф(23)); безатомные элементы также образуют идеал, и он обозначается Als0(23). Через F0(23) обозначим идеал Фреше (идеал, порожденный атомами), Е(23) = Als0(23) + Atm0(23) — идеал Ершова-Тарского. Пусть {Еп} — последовательность итерированных идеалов Ершова-Тарского, то есть Е0(23) = {0}, Еп+1(23) = (ЕпоЕ)(23) = {х € 231 ж/Еп € Е(23/Еп)}. Для каждого к £ и) обозначим через At*, предикат, выделяющий в каждой алгебре множество таких элементов ж, что ж/Е*, — атом. Аналогично определяются предикаты F^, Als* и Atm*,. Для предикатов At0, F0, Als0, Atm0, Ei будут иногда использоваться обозначе-

когда среди &1,Ът нет элементов из Е„(23).
Элементы &і/Е„,Ът/Е„ делят единицу в 93/Е„. По лемме 6 существуют элементы ci,...,cm|l в 21/Е„. со свойством с, Ъг/Еп. Можно найти элементы а1:...,ат, разбивающие единицу алгебры 21, такие что аг/Еп = с, для всех і Є [1,пг]. Поскольку элементы аг и 6г являются ?г-чистыми, по предположению индукции имеем Ьг <£_і вг, откуда по лемме 6 получаем 21 <£ 25. Лемма доказана.
Докажем теперь ещё одну теорему, которая продолжает теорему 8 на случай характеристик (п, 0,1), где п > 1. По сути она является следствием той теоремы: мы лишь немного усложним конструкцию за счёт одного дополнительного приёма. Теорема 11. Для любого п > 0 существует вычислимая алгебра элементарной характеристики (п,0,1) с вычислимыми предикатами из множества а = Ф„{Л/зп_1, Atrrin-i), не имеющая сильно вычислимого представления.
Доказательство. Для п = 1 существование алгебры с требуемыми свойствами доказано в теореме 8. Поэтому далее предполагаем, что п > 1.
Воспользуемся теоремой 7. Для этого возьмем Т = E„_i о Т1; где Ті = (Atm —> F) + Atm. 230 = 23i = 23 ((w + r/)n~1 x (1 + u> x rj + (2 + r]) x 77)) обозначим эту алгебру за 25, а = Фп{А1з„-1, Atmn_i}, а — 5, G = {0}. В качестве алгебры 21 возьмем Д ^-вычислимую алгебру, у которой нет Д^-вычислимого представления.
Е и Ti - стабильные идеальные операторы, что доказано в лемме 4 из [4] и лемме 4 данной работы, соответственно. Композиция стабильных операторов является стабильным оператором по лемме 12, поэтому Т — тоже стабильный идеальный оператор. В силу выбранной нумерации для алгебры Т(23) - вычислимое подмножество в 25. Заметим также, что 23/Т = (03/Е„_!)/Тх = 23(1), так как 23/ЕП_! изоморфна алгебре из теоремы 8. По лемме 5а- локальный набор, согласованный с Т.
Проверим выполнение условий (а) и (Ь) теоремы 7. Воспользуемся леммой 14. Алгебра 23 является чистой, кроме того, для всех г Є [0,п — 1] выполняется 23/Finat, = 23 ((w + х (1 --ш х у + (2 + 77) х rf). Следовательно, 23 является (п — 1)-чистой,
что справедливо и для алгебр вида а, где а € 23 или а Є 23 х 23. В ходе доказательства теоремы 8 было показано, что ä' а' х 23' для любого а' 0 Т(23'), где