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

_ _ Российская академия наук

РГБ ОД

Сибирское отделение ~ 1. ;. '; Институт математики

На правах рукописи Пальчунов Дмитрий Евгеньевич

Теоретико-модельные свойства булевых алгебр с выделенными идеалами

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

Автореферат

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

Новосибирск -1994

Работа выполнена в Институте математики Сибирского отделения РАН

Официальные оппоненты:

доктор физико-математических наук, профессор Важенин Ю.М. доктор физико-математических наук, член-корреспондент РАО,

профессор Никитин A.A. доктор физико-математических наук, профессор Перетятькин М.Г.

Защита состоится 20 октября 1994 г. в 17 час. 00 мин. на заседании специализированного совета Д 002.23.01 при Институте математики СО РАН по адресу: 630090, Новосибирск, 90, Университетский проспект, 4.

С диссертацией можно ознакомиться в библиотеке Института математики СО РАН.

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

Омский государственный университет

Автореферат разослан

п

сентября 1994 года.

Ученый секретарь специализированного совета кандидат физико-матема:

С.Т.Федоряев

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Булевы алгебры являются одним из фундаментальнейших объектов современной математики. Точно также, как действительные числа являются математической формализацией количества, булевы алгебры являются формализацией меры истинности. Булевы алгебры исследуются и применяются во многих областях математики — в алгебре и математической логике, в функциональном анализе, кибернетике и др. Большой материал, накопленный к настоящему времени в исследованиях булевых алгебр представлен в трехтомной справочной книге по булевым алгебрам [23]. Там же содержится обширная библиография. Результаты по булевым алгебрам и их использованию в математической логике содержатся в монографиях [5, 12, 13, 21, 22, 24].

При исследовании алгебраических систем большое значение имеет изучение их теоретико-модельных свойств. В частности, представляет особый интерес исследование таких свойств как ы-категоричность и конечная аксиоматизируемость элементарных теорий, характеризация однородных, универсальных, простых и счетно-насыщенных моделей. Важно также изучение алгоритмических свойств алгебраических систем — разрешимости элементарных теорий, конструктивиэи-руемости и сильной конструктивизируемости моделей.

Исследование теоретико-модельных свойств булевых алгебр начато в работах А.Тарского [32] и Ю.Л,Ершова [9], Ю.Л.Ершов [9] положил начало исследованию теоретико-модельных свойств булевых алгебр с выделенными идеалами.

В дальнейшем булевы алгебры и их обогащения широко исследовались многими авторами [1-4, 6-8,10, И, 14-20, 24-31, 33-67].

Большое внимание исследователей привлекают различные обогащения булевых алгебр — булевы алгебры с выделенными идеалами, (которые, в дальнейшем мы будем для краткости называть /-алгебрами) [15, 25, 27, 30, 33-37, 40-62, 6467] булевы алгебры с выделенными подалгебрами и автоморфизмами [6-8,14, 26, 31, 39, 63], влементарные теории булевых алгебр в различных вариантах логики второго порядка [18, 20,29, 38].

В [9] Ю.Л.Ершовым и в [32] А.Тарским приведена влементарная классификация булевых алгебр.

М.Рубия [31] показал неразрешимость теории класса булевых алгебр с одной выделенной подалгеброй. Элементарные теории булевых алгебр с выделенными подалгебрами изучались в [6, 7, 26, 63]. В [14] показана неразрешимость теории булевых алгебр с выделенным автоморфизмом.

Большой интерес представляют исследования теорий булевых алгебр в языках с обобщенными кванторами (см., например, [20, 24, 29, 38]).

В [9, 15, 30, 41, 46] исследовалась разрешимость теорий булевых алгебр с выделенными идеалами. В частности, Ю.Л.Ершовым [9] показана разрешимость элементарной теории /-алгебры (8, /) при одном из следующих условий:

(а) В/1 конечна; (б) В атомна и существует аир (г | г 6 /}.

В [9] доказана также разрешимость класса алгебр, обладающих свойством (б).

М.Рабином [30] установлена разрешимость теории класса /-алгебр. А.С.Морозов [15] привел примеры булевых алгебр с одним выделенным идеалом и неразрешимой влементарной теорией для любой ненулевой первой характеристики Ершова — Тарского. В [41] показано, что в булевой алгебре можно выделить идеал с неразрешимой влеменгаряой теорией тогда и только тогда, когда она яе

является сулератомяой, В [46] дан критерий разрешимости элементарных теорий /-алгебр.

В [25, 27, 33-37, 40-62, 64-67] изучались теоретико-модельные свойства /алгебр. В [27, 42, 57] описаны счетно категоричные /-алгебры, а в [45, 46] — конечно аксиоматизируемые /-алгебры. В [25, 40, 41] показано, что существует континуум элементарно неэквивалентных /-алгебр. В [25, 41] охарактеризованы как несуператомные счетные булевы алгебры, имеющие континуум элементарно неэквивалентных обогащений выделенный идеалом. Автором [45, 46] и А.Тураем [33,34] получены критерии элементарной эквивалентности /-алгебр. А.Турай [33, 34] предложил обогащение языка /-алгебр, допускающее элиминацию кванторов. Автором [43, 47, 49, 52, 53, 58, 59, 67] изучались простые и счетно насыщенные /-алгебры.

Результаты, полученные при исследовании /-алгебр, применяются также для изучения более широкого класса алгебраических систем — псевдобулевых алгебр.

Цель работы. Диссертация посвящена исследованию теоретико-модельных свойств булевых алгебр с выделенными идеалами. Изучаются конечно аксиома тиэируемые и счетно-категоричные /-алгебры; исследуется проблема существования простых и счетно-насыщенных моделей у элементарных теорий /-алгебр. Описана алгебра Линденбаума—Тарского класса /-алгебр.

Общая методика исследования. Результаты по элементарным теориям булевых алгебр с выделенными идеалами можно условно разделить на две группы. В [25, 27,33-37], начиная с А.Макинтайра и Д.Розенштейна, булевы алгебры с выделенными идеалами изучаются на основе исследования псевдобулевой алгебры идеалов булевой алгебры и ее подалгебры формульно определимых идеалов; ббльшая часть результатов сформулирована на языке псевдобулевых алгебр

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

В работа.! автора, диссертации [40-62, 64-67] при исследовании булевых алгебр с выделенными идеалами используются только понятия теории булевых алгебр. /-алгебры изучаются начиная с элементарных: двухэлементной булевой алгебры, единица которой принадлежит (не принадлежит) идеалу; безатомной булевой алгебры, которая не содержит ненулевых элементов, принадлежащих идеалу и т.д. Для построения более сложных /-алгебр введены конструкции ы-смешивания и ^смешивания [41, 42, 57[. В этих конструкциях обобщается идея построения булевых алгебр по линейным порядкам. Одновременно приведены формулы, описывающие простейшие /-алгебры, а также конструкции над этими формулами, позволяющие описать ы-смешивание и ^смешивание /-алгебр. Таким образом автором были построены последовательность формул и характеристика /-алгебр г, при помощи которых получены критерии элементарной эквивалентности /-алгебр и разрешимости их элементарных теорий [42, 44-46, 57]. Эти конструкции и критерии являются основным инструментом исследования булевых алгебр в настоящей диссертации.

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

В диссертации получены следующие основные результаты:

1) Доказано, что элементарная теория любой суператомной булевой алгебры с выделеннным идеалом имеет счетно-насыщенную модель. Показано, что для любой характеристики /-алгебры существует простая модель с данной характеристикой. Приведен пример булевой алгебры с выделенными идеалами, теория которой не имеет простой модели. Доказано, что у каждой счетной несуператом-

ной булевой алгебры существует континуум обогащений одним идеалом, теории которых имеют счетно-насыщенную модель; континуум обогащений, теории которых имеют простую, но не имеют счетно-насыщенной модели и континуум обогащений, теории которых не имеют простой модели.

2) Дано описание локальности, конечной аксиоматизируемости и у-категоричности булевых алгебр с выделенными идеалами на языке элементарной эквивалентности и прямых разложений.

5) Дано описание алгебры Линденбаума-Тарского класса булевых алгебр с выделенными идеалами, /-алгебры, конечно аксиоматизируемые относительно фильтров Фреше данной алгебры, охарактеризованы на языке премых разложений и элементарной эквивалентности.

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

Апробация результатов диссертащщ. Результаты диссертации были представлены автором в пленарных докладах на IX (Ленинград, 1988), X (Алма-Ата, 1990), XI (Казань, 1992) Всесоюзных конференциях по математической логике, в лекциях автора в университете Влез Паскаль (Клермон-Ферран, Франция, 1991), в Международном Банаховском центре (Варшава, Пальша, 1991), в университете г.Иннсбрука (Австрия, 1992).

Результаты диссертации излагались автором в докладах на УШ (Москва, 1987) и IX (Упсала, Швеция, 1991) конгрессах по логике, методологии и философии науки, Логических Коллоквиумах в Хельсинки (1990) и Клермон-Ферране

(Франция, 1994), международной алгебраической конференции (Новосибирск, 1989), международной конференции "Клини-90" (Варна, Болгария, 1990), Советско-французской коллоквиуме по теории моделей (Караганда, 1991), УШ Всесоюзной конференции по математической логике (Москва, 1986), XIX Всесоюзной алгебраической конференции (Львов, 1987), IX (Харьков, 1986) и X (Минск, 1990) Всесоюзных совещаниях по логике, методологии и философии науки, в лекциях на Всесоюзных школах по прикладной логике в Орджоникидзе (1987) и Владивостоке (1988).

Автор докладывал результаты диссертации на семинарах "Алгебра и логика", "Теория моделей", "Конструктивные модели", "Прикладная логика", "Булевы и гейтинговы алгебры", "Неклассические логики" Новосибирского университета, на научных семинарах Омского и Уральского университетов.

Часть результатов диссертации вошла в материал спецкурса "Булевы алгебры", прочитанного автором в 1991-1993 гг. в Новосибирском государственном университете.

Публикации. Результаты диссертации опубликованы в [47- 56, 58- 67 ].

Объем и структура работы. Диссертация изложена на 229 страницах. Она состоит из введения и трех глав, разбитых на 18 параграфов. Во введении приведен обзор результатов диссертации, в первой главе исследуются простые и счетно-насыщенные модели, а во второй главе счетко-категоричные и конечно-аясиоматизируемые модели теории /-алгебр. В третьей главе изучается алгебра Линденбаума—Тарского класса булевых алгебр с выделенными идеалами. Библиография содержит 83 наименования, включая работы автора по теме диссертации.

СОДЕРЖАНИЕ ДИССЕРТАЦИИ

Введение состоит из двух параграфов. В первом параграфе приведены определения и формулировки результатов по теории булевых алгебр с выделенными идеалами, необходимые для изложения диссертации. Второй параграф содержит обзор результатов диссертации.

В первой главе диссертации изучаются простые и счетно-насыщенние модели теории булевых алгебр с выделенными идеалами, а также /-алгебры, имеющие или не имеющие такие модели. Показано, что для любой характеристики /-алгебры существует простая модель с данной характеристикой. Дано необходимое условие и-насыщенности /-алгебры. Доказано, что элементарная теория любой суператомной булевой алгебры с выделенным идеалом имеет счетно-насьпценную модель. Для каждой счетной несупер атомной булевой алгебры построен континуум ее обогащений одним идеалом, элементарные теории которых различны и имеют счетно-насьпценную модель; континуум обогащений, теории которых имеют простую, но не имеют счетно-насыщенной модели и континуум обогащений, теории которых не имеют простой модели.

Глава состоит из шести параграфов.

В первом параграфе исследуются условия, достаточные для того, чтобы прямые слагаемые элементарно эквивалентных /-алгебр также были элементарно эквивалентны. Эти утверждения необходимы для исследования простых моделей теории /-алгебр, в частности, для доказательства теоремы 1.2.3.

Основным результатом первого параграфа является

ТЕОРЕМА 1.1.4. Если /-алгебры Л\ и 01 локальны, Л\ х = В1 х Вз и га, = тВг, то Л а = В2.

Во втором параграфе первой главы изучаются простые модели теории булевых алгебр с выделенными идеалами. Дано достаточное условие того, что /-алгебра является простой моделью.

ТЕОРЕМА 1.2.1. Пусть каждое разложение А = ВхС счетной /-алгебры А удовлетворяет следующим условиям:

(а) если В локальна, то для любого I € N(5) равенство = оо влечет неравенство гс(4) < со;

(б) если В нелокальна, то С локальна.

Тогда А — простая модель.

Следующие результаты показывают, что достаточно широкий класс /-алгебр имеет простую модель.

ТЕОРЕМА 1.2.8. Для любой естественной функции г существует простая модель А такая, что гд = г.

СЛЕДСТВИЕ 1.2.10. Если булева алгебра А суператомна, то ТЬ(Л,/) имеет простую модель для любого идеала / С |Л|.

СЛЕДСТВИЕ 1.2.11. Если /-алгебра А локальна, то ТЬ-А имеет простую модель.

СЛЕДСТВИЕ 1.2.15. Если /-алгебра А — простая модель, А = М х И и М — локальная /-алгебра, то М — простая модель.

В третьем параграфе первой главы исследуются влементарные теории /алгебр, имеющие простую модель, но не имеющие счетно насыщенной модели. Дано достаточное условие отсутствия у влементарной теории /-алгебры счетно-насьпценной модели.

ПРЕДЛОЖЕНИЕ 1.8.1. Пусть для естественной функции г существует бесконечное множество Ь С М(г) такое, что К, I 6 Ь, попарно независимы. Тогда не существует счетно насыщенной модели Я такой, что тм = т.

СЛЕДСТВИЕ 1.8.2. Если для /-алгебры А существует бесконечное множество I С М(А) такое, что I б Ь, независимы, то ТЬ (А) не имеет счетно насыщенной модели.

Доказано, что если счетная булева алгебра А не суператомна, то существует континуум ее /-обогащений С с различными ТЬС, имеющими простую, но не имеющими счетно насыщенной модели.

Четвертый параграф первой главы посвящен исследованию /-алгебр, характеристики которых являются минимальными среди нелокальных. Такие /-алгебры являются важным инструментом исследования теорий нелокальных /-алгебр.

ОПРЕДЕЛЕНИЕ 1.4.1. Нелокальная естественная функция г называется ступенчатой, если существует строго возрастающая последовательность натуральных чисел п е 14, такая, что для любых ц;, я 6 N если I < <„, ; > г(.) # 0 и г(У) 0, то К <

ТЕОРЕМА 1.4.2. Функция г является минимальной в классе нелокальных естественных функций тогда и только тогда, когда она ступенчатая.

ОПРЕДЕЛЕНИЕ 1.4.5. /-алгебра А называется ступенчатой, если ее характеристика гд ступенчатая.

Наиболее полезными являются такие ступенчатые /-алгебры, зная характеристику которых мы можем отвечать на вопрос "1 € /,' ?" для любого идеала, /у. Они названы строго ступенчатыми.

ОПРЕДЕЛЕНИЕ 1.4.в. Ступенчатая /-алгебра А называется строго ступенчатой, если

= {} < ^ I Для некоторого п формула К ./-неидеальная и гд(п) ф 0}.

Важность класса строго ступенчатых /-алгебр показывает тот факт, что ха<-рактеристика г полностью описывает их элементарные теории,

ТЕОРЕМА 1.4.7. Если /-алгебры А и В строго ступенчаты, то А = В тогда и только тогда, когда г/ = тв-

Пятый параграф содержит основной результат первой главы - пример /алгебры, элементарная теория которой не имеет простой модели.

Заключительный результат первой главы приведен в шестом параграфе. Доказана

ТЕОРЕМА 1.8.1. Счетная булева алгебра А несуператомная, если и только если выполнено одно из следующих условий:

1) существует идеал / С |.Д| такой, что ТЦД,/) не имеет простой модели;

2) существует континуум идеалов / С |,Д| с различными ТК(«А, 7), не имеющими простой модели;

3) существует идеал / С \А\ такой, что Тк(Л, /) имеет простую модель, но не имеет счетно-насыщенной модели;

4) существует континуум идеалов / С |Л| с различными /), имеющими простую, но не имеющими счетно-насыщенной модели;

5) существует континуум идеалов / С |,Д| с различными ТЬ(.Д,/), имеющими счетно-насыщенную модель.

Здесь также дано необходимое условие и-насыщенности

ПРЕДЛОЖЕНИЕ 1.6.5. Пусть /-алгебра Л/- является ы-насыщекной. Тогда для любого а € -V выполнены следующие условия;

(а) для любого я 6 N если г„(я) = оо, то найдется я-простой элемент Ь < а такой, что ц(п) = оо и = оо;

(б) если элемент а нелокальный, то найдется нелокальный элемент Ь < а такой, что а \ Ь нелокальный.

Это условие является и достаточным для счетных строго ступенчатых I-алгебр.

ТЕОРЕМА 1.6.6. Пусть /-алгебра Л/-локальная либо строго ступенчатая. Тогда

1) Т'йЛГ имеет счетно-насыщенную модель;

2) если Я счетна, то Я счетно-насыщенная тогда и только тогда, когда для любого а в Я выполнены следующие условия:

(а) для любого и 6 N если г„(я) = оо, то найдется п-простой Ь < а элемент такой, что = оо и = оо;

(б) если элемент а нелокален, то найдется нелокальный элемент Ь < а такой, что а \ Ъ нелокален.

СЛЕДСТВИЕ 1.6.0. Если булева алгебра £ суператомная, то для любого идеала IС |£| теория ТК(£, /) имеет счетно-насыщенную модель.

СЛЕДСТВИЕ 1.6.12. Прямое произведение конечного числа счетно-насыщенных квазиступенчатых /-алгебр счетяо-касыщено.

СЛЕДСТВИЕ 1.6.15, Если /-алгебра М счетно-насыщенная, М=ВхС и Бквазиступеячатая (в частности, если В локальная либо строго ступенчатая), то /-алгебра В счетно-насыщенная.

В первой главе рассмотрены простые и счетно-насыщенные /-алгебры. Во второй главе диссертации изучаются два других важных класса — конечно аксиоматизируемые и счетно категоричные булевы алгебры с выделенными идеалами. Дано описание таких /-алгебр на языке елементарной эквивалентности и прямых разложений. Важным здесь является то, что при описании конечной аксиоматизируемости, локальности и минимальности характеристики /-алгебры мы не обращаемся к формулам, & используем только модели. Кроме того, при описании счетной категоричности мы не используем изоморфизма. Глава содержит пять параграфов.

В первой параграфе изложены некоторые вспомогательные результаты, которые будут полезны во второй главе.

Во втором параграфе изучается связь между конечной аксиоматизируемостью и счетной категоричностью /-алгебр. Эти свойства описываются на языке елементарной вквивалентности и прямых разложений. Будем обозначать В < А, если А = В х С для некоторой /-алгебры С, обозначим В < А если А = С XV к В = С для некоторых /-алгебр С и V.

ОПРЕДЕЛЕНИЕ 2.2.1. /-алгебру А назовем неисчезающей, если для любого.разложения А = ВхС выполнено А = В либо А = £.

ОПРЕДЕЛЕНИЕ 2.2.2. Конечно-аксиоматизируемую неисчезающую /• алгебру назовем 6шитой.

Введенная ранее автором [42, 57] последовательность формул У,(г) вме-. сте с определенной с ее помощью характеристикой г является основным инструментом для исследования теорий /-алгебр, проводимого автором. При помощи базисных /-алгебр найдено естественное описание семейства предложений У,(1).

ТЕОРЕМА 2.2.3. Последовательно спи формул Г»(1) — ¡то перечисление ¡а повторений вей полных предложений, аксиоматизирующих базисные 1-<иге(ри.

Следующий результат показывает, что для исследования строения конечно аксиоматизируемых /-алгебр достаточно рассматривать их частный случай — базисные /-алгебры.

ТЕОРЕМА 2.2.17. 1-алгебра А конечно-аксиоматизируема тогда и только тогда, когда существует разложение А = х ••• х А*, где все А^ — (лгиснае.

На языке прямых слагаемых дано описание характеристики /-алгебр г.

ТЕОРЕМА 2.2.24. ДляI-алгебр А и В следующие условия вквивалентна;

1)гл =гв ;

2) для любых конечно-аксиоматизируемьа А' <А и В' <В выполнены А' < В и В'<А\

3) для любой конечно-аксиоматизируемой £ имеет место раеносилмсть утверждений С <А и С <В\

4) для любой базисной С и любого я 6 N имеет место равносильность утверждений Сл< А я С* <В.

Во втором параграфе конечно-аксиоматизируемые и и-категоричные I-алгебры описаны на языке базисных /-алгебр и прямых разложений. Однако, определение базисных /-алгебр использует понятие конечной аксиоматизируемости, поэтому приведенное здесь описание еще не является завершенным, оно окончательно уточняется в четвертом параграфе. Для этого необходимо описать базисные /-алгебры.

В третьем параграфе второй главы дана характеризация локальных и базисных /-алгебр, использующая только прямые разложения и элементарную эквивалентность.

ТЕОРЕМА 2.3.1. Для I-алгебр а А следующие условия эквивалентны:

1)А локальна;

2) существуют ¡-алгебры А\,...,А% такие, что если А = В х С, то В = ,Д{1 х ••• х .Д£" для некоторых к € и;

3) существуют неисчезающие А1,...,Ап такие, что А = = .41 х • • • х .Д », и если В <А, то для некоторая к1 £ и.

СЛЕДСТВИЕ 2.3.3. Если для локальной неисчезающей 1-алгебры А выполнено А£Л хА, то А конечно-аксиоматизируема.

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

ТЕОРЕМА 2.4.1. I-алгебра А конечно-аксиоматизируема тогда и только тогда, когда найдутся нейсчезакщие ¡-алгебры «4 Л» и число т < п такие, что

а) А = А1 х • • • х А т;

б) если В < А, то В = А\1 х ...х А^' для некоторых 6 и;

в) для каждой ¡-алгебры В и всех » < т выполнено любое из следующих условий:

1) если Л ¡ = Л; хА{ = В, тоВ = С = С для некоторого разложенияВ = СхС;

2) если неисчезащая В ф АI, то Ви фАц

3) еслиВф А{, то ^»Л; для некоторого пбЛ.

ТЕОРЕМА 2.4.5. Для 1-алгебры А следующие условия эквивалентны:

1) А ы-категорична;

2) найдутся неиечмаюцце 1-алгебры А\,.. .,^4», для которых выполнено любое из условий 1—3 теоремы и такие, что если А = 8хС, та В гА? х---хА1" при некоторых с; € и;

3) если А = Вх С, то В конечно-аксиоматизируема;

4) если А = А х В, то В конечно-аксиоматизируема.

В последнем, пятом параграфе второй главы показано, как можно описать локальные, счетно-категоричные и конечно-аксиоматизируемые /-алгебры не используя равенства и изоморфизма, на языке прямых слагаемых и элементарной эквивалентности.

СЛЕДСТВИЕ 2.5.1. (описание на языке {х, <,=}).

1) алгебр а А является локальной тогда и только тогда, когда существует не более конечного числа олеме ктарно неэквивалентных В со свойствами А хВ = 8 и

(*) В =М х Я влечет В =М либо В =АГ.

2) ¡-алгебра А является хонечно-аксиоматизируемой тогда и только тогда, когда А локальна и существуют А1 х ••• х Л„ = Л такие, что дли любой А{ выполнено свойство (*) и В = = А^ х А, влечет М хЯ<В для некоторых

м =м = в,

3) 1-алгебра А является и-категоричной тогда и только тогда, когда из А в А х В емтекаеп», что В. конечно-аксиоматизируема.

При исследовании элементарных теорий особое значение имеет имеет изучение алгебры выполнимых предложений — алгебры Линденбаума— Тарского теории данного класса алгебраических систем. В третьей главе диссертации дано полное решение вопроса: "Описать алгебру Линденбаума— Тарского класса булевых алгебр с выделенными идеалами".

Этот вопрос в 1987 году был предложен автору М.Г.Перетятькиным и был сформулирован в списке нерешенных вопросов теории булевых и гей-тинговых алгебр, представленном автором диссертации в пленарном докладе на Всесоюзной конференции по математической логике в г.Ленинграде в 1988г.

Третья глава состоит из пяти параграфов.

В первом параграфе для случая одного выделенного идеала введены так называемые канонические и квазикононические /-алгебры. Квазиконониче-ские /-алгебры, как показано во втором параграфе, являются конечно ак-сиоматизруемыми относительно фильтров Фреше алгебры Линденбаума— Тарского булевых алгебр с одним выделенным идеалом.

Во втором параграфе исследуется алгебра Линденбаума—Тарского С1 класса булевых алгебр с одним выделенным идеалом. Для каждого я 6 ы дано полное описание влементов множества предложений Ря(Сг) и их моделей.

Третий параграф третьей главы диссертации содержит конструкцию канонических и квазиканонических /-алгебр для случая А выделенных идеал лов. Каждой квазиканонической /-алгебре сопоставлены ранговая функция / и предложение .

Через Г» ^ обозначен я-й идеал Фреше алгебры Линденбаума — Тарского класса булевых алгебр с А выделенными идеалами.

ОПРЕДЕЛЕНИЕ 5.3.18. Обозначим Г» ^ {-ир | <р е К% & {А |

А (= Г» и А <р дл* некоторого предложения ¡р такого, что у>/.Р» — атом е

В втом параграфе показано, что квазиканонические /-алгебры — это модели я-атомов алгебры Сх.

ТЕОРЕМА 3.3.20. Кя = {А\ А — квазиканоническая-1-алгебра и }{А) = я} ¡л* любого »6 и.

Получено описание конечных слоев алгебры Линденбаума—Тарского класса булевых алгебр с выделенными идеалами — ее конечных фильтров Фреше.

ТЕОРЕМА 3.3.21. = {( V уд, )| Д; — кватканоничеекахI-алгебра, к£ы »<1

к /(Л;) < я} для любого я 6 и,

В четвертом параграфе дал основной результат третьей главы — описание с точностью до изоморфизма алгебры Линденбаума—Тарского класса /-алгебр.

Пусть Вы-хп ~~ это булева алгебра интервалов линейного порядка и" х!).

ТЕОРЕМА 3.4.4. Алгебра Линденбаума—Тарского класса булевмх алгебр с X выделенными идеалами изоморфна 5и>Х1).

Это описание алгебры Сх означает, что, во-первых, для любого п 6 ы алгебра С* ¡Ря — бесконечная атомная, и, во-вторых, что — безатомная булева алгебра.

СЛЕДСТВИЕ 5.4.5. Рш(£х) = {(V 9л, ) \ к £ и, а при I < к ]-алгебра А

¡<1

является хвазиканоническои}.

В пятом параграфе на языке прямых слагаемых дало описание /-алгебр, конечно аксиоматизируемых относительно фильтров Фреще алгебры £Л (названых относительно конечно аксиоматизируемыми). Здесь В < А означает, что А = В х С для некоторой С, а В < А означает, что В < А и В ф А.

ТЕОРЕМА 5.5.4. I-алгебра А относительно конечно аксиоматизируема тогда и только тогда, когда число нелокальных неисчезающих прямых слагаемых 1-алгебры А конечно и для любой минимальной нелокальной 1-алгебры В < А

а) почти для любой базисной С < В существует и единственна (с точностью до влементарной вкеивалектноети) »(сравнимая с ней базисная С< В,

б) если В <С <А и С — кеисчезакщая, то С £А для некоторого п€и,

в) существует локальная С < А такая, что для любой базисной С < А, если ££С, то £<Я для некоторой минимальной нелокальной Я < А.

Важным вопросом при исследовании элементарных теорий алгебраических систем является проблема их алгоритмической разрешимости. Для относительно конечно аксиоматизируемых /-алгебр получен положительный ответ на этот вопрос.

ТЕОРЕМА 5.5.5. а) Для любого а ( и множества предложений и Г» являются разрешимыми.

б) Элементарная теория любой относительно конечно аксиоматизируемой /алгебры разрешима.

в) Геделевская нумерация является сильной конструктивизацией булевой алгебры С* в языке первого порядка, обогащенном квантором В00 "существует бесконечно много непересекающихся".

Если же теория /-алгебры является неразрешимой, она. должна, удовлетворять следующим структурным условиям.

ТЕОРЕМА 3.5.8. Если влементарная mtopия ¡-алгебры А неразрешима, то выполнено хота бы одно из следующих условий:

а) Л имеет бесконечное количество нелокальных неисчезающих прямых слагаемых;

б) существует минимальная нелокальная В < А такая, что число базисных I-алгебр С < В, для каждой из которых существуют несравнимые с ней различные базисные С,М < В, бесконечно;

в) существуют неисчезащие локальные В,С < А такие, что В < С и С* < А для любою п € и;

г) число базисных С<А таких, что С ■¿С для любой минимальной нелокальной С <А, бесконечно.

Класс конечно аксиоматизируемых /-алгебр замкнут относительно прямых произведений, но не замкнут относительно взятия прямых слагаемых. В этом смысле его обобщение — класс относительно конечно аксиоматизируемых /-алгебр устроен лучше.

СЛЕДСТВИЕ 3.5.11. Класс относительно конечно аксиоматизируемых 1-алгебр Ки замкнут относительно прямых произведений и прямых слагаемых.

Автор признателен С.С.Гончарову за постоянное внимание к работе.

ЛИТЕРАТУРА

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

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

3. Гончаров С.С. Ограниченные теории конструктивных булевых алгебр, Сиб, мат. журн., 1976, т. 17, N 4, с, 797-812.

4. Гончаров С.С. Неавтоэквивалентные конструктивизации атомных булевых алгебр, Мат, заметки, 1976, т, 19, N 6, с. 853-858.

5. Гончаров С.С. Счетные булевы алгебры, М.: Наука, 1988.

6. Дулатова З.А. Расширенные теории булевых алгебр, Сиб. мат. журн., 1984, т. 25, N 1, с. 201-204.

7. Дулатова З.А. Булевы алгебры с выделенной подалгеброй и автоморфизмом, Некоторые проблемы дифференциальных уравнений и дискретной математики, Новосибирск, 1986, с. 130-147.

8. Дулатова З.А. О теории булевых алгебр с локально конечной группой автоморфизмов, Сиб. мат. журн., 1987, т, 28, N 3, с. 89-90.

9. Ершов Ю.Л. Разрешимость элементарной теории дистрибутивных структур с относительными дополнениями и теории фильтров, Алгебра и логика, 1964, т. 3, N 3, с. 17-38.

10. Ершов Ю.Л. Конструктивные модели, Избранные вопросы алгебры и логики, Новосибирск, 1973, с. 111-130.

11. Ершов Ю.Л. Дистрибутивные решетки с относительными дополнениями, Алгебра и логика, 1979, т. 18, N 6, с. 680-722.

12. Ершов Ю.Л. Проблемы разрешимости и конструктивные модели, М.: Наука, 1980.

13. Кейслер Г., Чэн Ч.Ч. Теория моделей, М.: Мир, 1977.

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

15. Морозов A.C. О разрешимости теорий булевых алгебр с выделенным идеалом, Сиб. маг. журн., 1982, т. 23, N 1, с, 199-201.

16. Морозов А.С, Сильная конструктивизируемость счетных насыщенных булевых алгебр, Алгебра и логика, 1982, т. 21, N 2, с, 193-203.

17. Морозов A.C. Счетные однородные булевы алгебры Алгебра и логика, 1982, т. 21, N 3, с. 269-282.

18. Палютин Е.А. О булевых алгебрах, имеющих категоричную теорию в слабой логике второго порядка, Алгебра и логика, 1971, т. 10, N 5, с. 523534.

19. Перетятькин М.Г. Сильно конструктивные модели и нумерации булевой алгебры рекурсивных множеств, Алгебра и логика, 1971, т. 10, N 5, с. 535-557.

20. Пинус А.Г. Теория булевых алгебр в исчислении с квантором "существует бесконечно много", Сиб. мат. журн., 1976, т. 17, с. 1417-1421.

21. Сикорский Р. Булевы алгебры, М.: Мир, 1969.

22. Haimos P. Lectures on Boolean algebras, Pmceaton, 1963,

23. Handbook of Boolean algebras, v. 1-3, ed. J.D.Monk with R-Bonnet, North-Holland, Amsterdam, 1989.

24. Heindorf L. Beitrage zur Modelltheorie der Booleschen Algebren, Seminarbericht N 53, Humboldt-Univ., Berlin, 1984.

25. June P.-F., Touraille A. Idéaux elementairement equivalents dans one algebre booleienne. Comptes Rendns de L'Academie des sciences, 1984, v. 299, Serie I, N 10, p. 415-418.

26. Koppelberg S, On Boolean algebras with distinguished eubalgebras, Enseignement

math., 1982, v. 28, p. 233-252.

27. Madntyre A., Rosenstein J.G. No-Categoricity for rings without nilpotent elements and for Boolean structures, Journal of Algebra, 1976, v. 43, N 1, p. 129-154.

28. Mead J. Recursive prime models for Boolean algebras, Colloq. Math.,' 1979, v. 41, N 1, p. 25-33.

29. Mohan. B. Die Theorie der Booleschen Algebren in der Logik mit Ramsey-Qtiantor, Diss.(A), Humboldt-Univ., 1981.

30. Rabin M.O. Decidability of the second order theories and automata on infinity trees, Trans. Amer. Math. Soc., 1969, N 141, p. 1-35.

31. Rubin. M. The theory of Boolean algebras with a distinguished subalgebra is undecidable, Ann. sci. Univ. Clermont Fr., 1976, v. 60, p, 129-134.

32. Tarski A. Arithmetical classes and types of Boolean algebras, Bull. Amer. Math. Soc., 1949, v. 55, p. 64.

33. Touraille A. Elimination des quantificateurs dans la theorie elementaire des algebres de Boole munies d'une famille d'idéaux distingues, Comptes Rendus de L'Academie des sciences, 1985, Serie I, v. 300, N 5, p. 125-128.

34. Touraille A. Theories d'algebres de Boole munies d'idéaux distingues. I: Theories élémentaires, The Journal of Symbolic Logic, 1987, v. 52, N 4, p. 1027-1043.

35. Touraille A. Heyting* algebras, topological Boolean algebras and P.O. systems, Algebra Universalis, 1987, v. 24, p. 21-31.

36. Tburaille A. The word problem for Heyting* algebras, Algebra Universalis, 1987, v. 24, p. 120-127.

37. Touraille A. Theories d'algebres de Boole munies d'idéaux distingues. H, The Journal of Symbolic Logic, 1990, v. 55, N 3, p. 1192-1212.

38. Weese M. The decidability of the theory of Boolean algebras with cardinality Quantifiers. Bui. De l'Academie Polon. Des Sc., 1977, v. 25, N 2, p. 93-97.

39. Wolf A. Decidability for Boolean algebras with automorphisms, Notices Amer. Math. Soc. 7 SU - E73, 1975, v. 22, N 164, p. A-648.

РАБОТЫ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

40. Пальчунов Д.Е. К вопросу о харакгеризадии булевых алгебр с выделенными идеалами, 7-я Всесоюзная конференция по математической логике: Тезисы докладов, Новосибирск, 1984, с. 135.

41. Пальчунов Д.Е. О неразрешимости теорий булевых алгебр с выделенным идеалом, Алгебра и логика, 1986, т. 25, N 3, с. 326-346.

42. Пальчунов Д.Е. Счетно-категоричные булевы алгебры с выделенными идеалами, Новосибирск, 1986, 48 с. (Препринт N 12 Института математики СО АН СССР)

43. Пальчунов Д.Е. О простых и счетно-насыщенных булевых алгебрах с выделенными идеалами, 8-я Всесоюзная конференция по математической логике: Тезисы докладов, Москва, 1986, с. 147.

44. Пальчунов Д.Е. Элементарные теории булевых алгебр с выделенными идеалами, Логика и системные методы анализа научного знания, Тезисы докладов 9-го Всесоюзного совещания по логике, методологии и философии науки, Харьков, 1986, с. 42-43.

45. Пальчунов Д.Е. Конечно-аксиоматизируемые булевы алгебры с выделенными идеалами, Тезисы конференции молодых ученых Сибири и Дальнего Востока, Новосибирск, 1987, с. 66-69.

46. Пальчунов Д.Е. Конечно-аксиоматизируемые булевы алгебры с выделенными идеалами, Алгебра и логика, 1987, т. 26, N 4, с. 435-455.

47. Пальчунов Д.Е. Нелокальные булевы алгебры с выделенными идеалами, Советско-французский коллоквиум по теории моделей, Караганда, 1990, с. 35-36.

48. Пальчунов Д.Б. Прямые слагаемые булевых алгебр с выделенными идеалами, 10-я Всесоюзная конференция по математической логике: Тезисы докладов, Алма-Ата, 1890, с. 126.

49. Пальчунов Д.Е. Простые и счетно-насыщенные /-алгебры, Труды советско-французского коллоквиума по теории моделей, Караганда, 1991.

50. Пальчунов Д.Е. Семантическое вложение класса булевых алгебр с выделенными идеалами в класс коммутативных колец, 11-я Межреспубликанская конференция по математической логике: Тезисы докладов, Казань, 1992, с. 109.

51. Пальчунов Д.Е. Прямые слагаемые булевых алгебр с выделенными идеалами, Алгебра и логика, 1992, т. 31, N 5, с. 499-537.

52. Пальчунов Д.Е. Простые и счетно-насыщенные булевы алгебры с выделенными идеалами, Труды Института математики СО РАН, т. 25, Новосибирск, 1993, с. 82-103.

53. Пальчунов Д.Е. Теории булевых алгебр с выделенными идеалами, не имеющие простой модели, Труды Института математики СО РАН, т. 25, Новосибирск, 1993, с. 104-132.

54. Пальчунов Д.Е. Полугруппа элементарных типов булевых алгебр с выделенными идеалами, Тезисы 3-й Международной алгебраической конференции, Красноярск, 1993.

55. Пальчунов Д.Е. Алгебра Линденбаума—Тарского класса булевых алгебр с одним выделенным идеалом, Алгебра и логика, 1994, т. 33, N 2, с. 179-210.

56. Пальчунов Д.Е. Алгебра Линденбаума—Тарского булевых алгебр с выделенными идеалами, Новосибирск, 1994, 45 с. (Препринт N 7 Института математики СО РАН)

57. Pal'chunov D.E. Conntably-categorical Boolean algebras with distinguished ideals, Studia. Lógica, 1987, v. 46, N 2, p. 121-135.

58. Pal'chunov D.E. On the finitely axiomatizable and prime Boolean algebras with

distinguished ideals, Proc. International conference on algebra, Model theory, Novosibirsk, 1989, p. 98.

59. Pal'chunov D.E. On the prime models of the theory of Boolean algebras with distinguished ideals, Summer School & Conference "Kleene-90", Sofia, 1990, p. 59.

60. Pal'chunov D.E. Direct summands of Boolean algebras with distinguished ideals, Logic Colloquium^, Helsinki, 1990, p. 60.

61. Pal'chunov D.E. Direct summands of Boolean algebras with distinguished ideals, The Journal of Symbolic Logic, 1991, v. 56, N 3, p. 1138.

62. Pal'chunov D.E. Quantifier elimination for the theory of Boolean algebras with distinguished ideals, Международная конференция по алгебре, посвященная памяти А.И.Ширшова, Барнаул, 1991, с. 101.

63. Pal'chunov D.E. Subalgebras of superatomic Boolean algebras, там же, с. 102.

64. Pal'chunov D.E. Lindenbaum—Tkrski algebras of Boolean algebras with ideals, Heyting algebras and commutative rings, Logic Colloquium'92, Hungary, 1992.

65. Pal'chunov D.E. Elementary types semigroup of Boolean algebras with distinguished ideals, Logic Colloquium'93, Keele, England, 1993.

66. Pal'chunov D.E. Relatively finitely axiomatizable Boolean algebras with distinguished ideals, Logic Colloquium'94, Clermont-Ferrand, France, 1994, p. 99.

67. Pal'chunov D.E. Prime and countably-eaturated Boolean algebra with distinguished ideals, SIBAM, 1994, v. 4, N 3, p. 83-108.