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

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

Введение
Представленная работа посвящена теории конструктивных булевых алгебр, и в ней исследуются проблемы нахождения критерия сильной конструктивизируемости булевых алгебр, а также проблемы построения конструктивных линейных порядков и булевых алгебр с некоторыми заданными алгебраическими и алгоритмическими свойствами.
Понятие сильно конструктивной модели было введено в 1968 году Ю.Л. Ершовым в его курсе лекций в Казахском университете в г. Алма-Ате, которые были опубликованы в посвященных А.И. Мальцеву трудах [5]. С этого понятия начинается ряд исследований, посвященных естественной проблеме нахождения критерия совпадения конструктивности и сильной конструктивности, а также необходимых и достаточных условий сильной конструктивизируемости. В случае булевых алгебр такие исследования были проведены в работах Н.Г. Хисамиева, С.С. Гончарова, С.П. Одинцова [8, 1, 12]. Н.Г. Хисамиевым был открыт один из первых признаков сильной конструктивности атомных булевых алгебр, состоящей в рекурсивности множества атомов [8]. Как было замечено в [6], этот признак является следствием сильной конструктивности конструктивных моделей модельно полных разрешимых теорий. В работе [4] С.С. Гончарова доказано, что от этого условия нельзя отказаться.
В работах [1, 4, 3] были введены промежуточные между сильной конструктивностью и конструктивностью понятия гг-конструктивности, а также было установлено различие этих понятий уже на классе булевых алгебр. В монографиях С.С. Гончарова [1, 2] нашли отражение базисные критерии и основные результаты этого направления. В частности, была найдена конструкция, сводящая в некоторых случаях проблемы построения критериев сильной конструктивизируемости булевых алгебр высших элементарных характеристик к критериям конструктивизируемости булевых

алгебр так называемого нижнего слоя, т.е. элементарных характеристик (0, оо,1),
(1.1.0) и (1,0,1) в терминах ограниченных теорий [3].
Дальнейшее развитие исследований в этом направлении оказалось связанным с оригинальной идеей Л. Фейнера [15, 16], предложившего специальные оценки для булевых алгебр с заданными алгоритмическими свойствами и также общую идею построения рекурсивных булевых алгебр, опровергающих эти оценки, и, таким образом, заданные алгоритмические свойства, при любом изоморфизме. Как указывает сам Л. Фейнер, его работа и постановка проблемы была инициирована А. Неро-удом, и некоторая помощь была оказана В. Ханфом. Указанный выше результат С.С. Гончарова [4] — его пример атомной конструктивной, но не сильно конструк-тивизируемой булевой алгебры, — опирается на метод Фейнера и существенно его модернизирует, так что в дальнейшем мы называем его метод “методом Фейнера-Гончарова”. Но стоит отметить, что сам метод Л. Фейнера так и остался малоиспользуемым в разделах современной теории конструктивных моделей — известен результат Дж. Реммела [17] о существовании конструктивной булевой алгебры с разрешимым множеством атомов, но с неразрешимым в любой конструктивизации идеалом Фреше, и также известна интересная работа Дж. Тёрбера [18], о которой будет подробнее сказано ниже.
Ряд положительных решений о возможности сильной конструктивизируемости булевых алгебр нижнего слоя, в частности, с элементарными характеристиками
(1.1.0) и (1,0,1), был получен С.П. Одинцовым [12, 13]:
1. Конструктивная булева алгебра элементарной характеристики (1,1,0) с разрешимым множеством атомов и безатомных элементов будет сильно конструктивизируема.
2. Конструктивная булева алгебра элементарной характеристики (1,0,1) с разрешимым множеством атомов, безатомных и атомных элементов будет сильно конструктивизируема
С.П. Одинцовым были анонсированы без доказательства [13] утверждения о возможности обобщения указанных выше результатов на высокие характеристики.
Автором диссертации В.Н. Власовым совместно с С.С. Гончаровым [21] был получен результат о сильной конструктивизируемости булевых алгебр элементарной

характеристики (1,1,0) с разрешимым множеством атомов и с некоторым естественным условием (разложимости данной алгебры в эффективную прямую сумму конструктивных булевых алгебр с первой характеристикой 0), эквивалентному в данном случае разрешимости идеала Ершова-Тарского; это исследование и новый вариант доказательства предложены в первой главе. С.С. Гончаровым: было получено [2] и окончательное решение проблемы характеризации для случая характеристики (1,1,0) — конструктивная булева алгебра сильно конструктивизируема если, и только если, множество атомов в данной конструктивизации разрешимо, которое существенно опирается на теорему Гончарова-Власова [21].
Краткий обзор
Сделаем краткий обзор представляемой работы. Диссертация состоит из введения, трех глав, и заключения. Во введении также присутстует сводка основных обозначений и определений. Каждая глава состоит из нескольких параграфов. Основные результаты изложены в первых двух главах, третья глава носит более методологический характер.
Первая глава описывает положительные результаты о сильной конструктивизиру-емости булевых алгебр в общем случае с нулевой третьей характеристикой Ершова-Тарского и равной единице второй, при некоторых условиях на разрешимость ограниченных теорий. Исследования автора были инициированы следующей открытой проблемой, сформулированной С.П. Одинцовым [1, 12, с. 170]:
“Существует ли конструктивная, но не сильно конструктивизируемая булева алгебра характеристики Ершов а-Тарского (1,1,0), допускающая конструк-тивизацшо с разрешимым множеством атомов?”.
Как уже было указано выше, из работ С.С. Гончарова следует, что от требования разрешимости атомов нельзя отказаться.
Основные конструкции главы эффективны и основываются на методе определимости слабой теории второго порядка. Параграф 1.1 посвящен сильной конструк-тивизируемости булевых алгебр характеристики (1,1,0) при условии, разрешимости множества атомов и разложимости в эффективную прямую сумму с конструктивными

Рассмотрение всех возможных случаев закончено, при завершении построений каждого из описываемых случаев переходим к следующему шагу. В результате выполнения алгоритма получим множества М/, IV/ такие, что Ш Є N (М/ С М-+1 & Щ С Л/+1). И полагаем
Из замечания к случаю 2 имеем, что для Ci у= (J Cf, верно |(7,-| < оо, и что
fceN
dom vaCj- = Ci. Далее, так как Ух € D* (3tx yt>tx (<р{х) = <рх(х))), и мы можем корректно определить функцию Ifi следующим образом: у>,(ж) ~ lim <р*(х), при этом
(,будет инъективным отображением за исключением конечного числа элементов, указанных в замечании к случаю 2.
Лемма 2.1 Множества М{ и Л/ являются рекурсивно-перечислимыми деревьями.
(Утверждения леммы очевидны, так как во-первых при построениях присоединяются к соответствующим концевым только по два парных элемента следующего уровня. И во-вторых, — в силу эффективности всех описанных построений случаев 1-3.)
“Неформальное описание”. В пошаговом алгоритме мы отслеживаем в дереве Д-+1 появление п-безатомных элементов, точнее таких х € Л(+1, что А1п(Л{). Как только обнаруживается такой Жо, то информацию о нем мы заносим в множество С!+1 (т.е. полагаем С-+1 С] и {ж0}); на то место щ в дереве М/+1, которое должен был бы занимать элемент 1+1(х0), если х0 = а и щ = Я1+1(хо), если х — &о) мы делаем ссылку уасг(жо) Мо, и переносим дальнейшее построение в дерево Л(<+ . Дерево У/4"1 строим следующим образом: если Хо — это первый элемент такого рода в +1 , то <+1(ж0) 0, если нет, то выбираем
максимальный (в обычном порядке ГУ) концевой элемент Яо в Щ так, чтобы прообраз г0 — элемент уо из порождал п-безатомный элемент в БА Лг; и под такой элемент г0 подвешиваем >)+1(жо) *=* г0, при этом переопределяем 1р*+1(у0) Ь{г0). Далее, если С т0, мы ждем появления п-атома в дереве 0*+к, к> 1 (чтобы закрыть “вакантное место” в М*+к) — такого элемента р, чтобы &1+к(р) € А2„(Д.,-), при