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

На правах рукописи

Трофимов Александр Викторович

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

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

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

1 2 ЯНВ 2012

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

005007376

Работа выполнена в Государственном образовательном учреждении высшего профессионального образования "Новосибирский государственный университет".

Научный руководитель:

Доктор физико-математических наук Пальчунов Дмитрий Евгеньевич. Официальные оппоненты:

Доктор физико-математических наук, профессор Морозов Андрей Сергеевич Доктор физико-математических наук, профессор Хисамиев Назиф Гарифуллинович

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

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования "Новосибирский государственный технический университет"

Защита диссертации состоится 26 января 2012 г. в 15 часов на заседании диссертационного совета Д 003.015.02 при Институте математики им. С.ЛСоболева Сибирского отделения Российской академии наук по адресу: 630090, Новосибирск, пр. Акад.Коптюга, 4.

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

Автореферат разослан 23 декабря 2011 г.

Ученый секретарь диссертационного совета

Кандидат физико-математических наук

Общая характеристика работы. Тематика диссертации.

Диссертация посвящена изучению обогащенных булевых алгебр и алгебр Ершова. Исследование теоретико-модельных свойств булевых алгебр было начато в работах Тарского [22] и Ершова [6]. Они предложили элементарную классификацию булевых алгебр. В основополагающей работе Ершова [7] предложен алгебраический метод, с помощью которого удалось описать широкий класс типов изоморфизма счетных дистрибутивных решеток с относительными дополнениями, которые после этого были названы алгебрами Ершова [3]. В частности из этой работы Ершова [7] следует характеризация Кетонена [17]. Гончаровым [2] предложена классификация типов изоморфизма счетных суператомных булевых алгебр.

Исследованию теоретико-модельных свойств булевых алгебр и их обогащений посвящено достаточно много работ. Впервые булевы алгебры с выделенными идеалами были рассмотрены Ершовым [6]. В частности, в [6] было доказано, что теория булевой алгебры с выделенным идеалом разрешима по крайней мере в следующих случаях: 1) ЗГ// конечна и 2) существует

5ир{х|х б /} и ЗГ - атомная. Рабин доказал, что теория класса булевых алгебр с выделенным идеалом разрешима [19], Рубин доказал, что теория класса булевых алгебр с выделенной подалгеброй неразрешима [20]. Из работ Воота [25] и Рылль-Нардзевского [21] следует, что элементарная теория булевой алгебры имеет счетно-категоричную теорию тогда и только тогда, когда она содержит не более конечного числа атомов. Морозовым [10] построены примеры булевых алгебр с одним выделенным идеалом и неразрешимой теорией для любой ненулевой первой характеристики Ершова-Тарского. В работах Пальчунова [11-15, 18] было доказано, что в булевой алгебре можно выделить идеал с неразрешимой элементарной теорией тогда и только тогда когда она не суператомная; получены критерии элементарной эквивалентности булевых алгебр с выделенными идеалами и разрешимости их элементарных

теорий; дано описание счетно-категоричных и конечно-аксиоматизируемых элементарных теорий; описана алгебра Лиденбаума-Тарского класса булевых алгебр с выделенными идеалами; доказано, что элементарные теории достаточно широкого класса булевых алгебр с выделенными идеалами не имеют простой модели, изучены теории, имеющие простые и счетно-насыщенные модели. Тураем [23, 24] предложено обогащение языка булевых алгебр с выделенными идеалами, допускающие элиминацию кванторов, изучались различные теоретико-модельные свойства булевых алгебр с выделенными идеалами. Мартьянов [9] исследовал разрешимость теорий булевых алгебр с выделенным автоморфизмом. Винокуров и Дулатова [1] доказали, что элементарная теория решеток подалгебр булевых алгебр неразрешима. Дулатова [4, 5] исследовала булевы алгебры с выделенной группой автоморфизмов, доказала неразрешимость теорий атомных булевых алгебр с выделенной атомной подалгеброй такой, что для каждого элемента алгебры существует наименьший элемент выделенной подалгебры, лежащий над ним. Цель работы.

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

Основные результаты

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

2. Получена элементарная классификация локальных суператомных булевых алгебр с выделенной плотной подалгеброй конечной ширины.

3. Показано, что автоморфизмы булевых алгебр, определяемые неподвижными элементами, - это в точности инволюции. Получено описание подалгебр булевых алгебр, -Которые являются множеством

неподвижных элементов автоморфизма.

4

Новизна и научная значимость работы.

Все результаты диссертации являются новыми и носят теоретический характер. Результаты и методы работы могут быть использованы для дальнейших исследований теоретико-модельных свойств алгебр Ершова, булевых алгебр и их обогащений. Апробация работы.

Результаты работы докладывались на Международной конференции «Мальцевские чтения» в 2000 году, международной конференции «Мальцевские чтения» в 2001 году, Международной конференции «Мальцевские чтения» в 2010 году. Результаты докладывались на семинарах «Конструктивные модели», «Теория вычислимости», «Алгебра и логика» и «Прикладная логика» Новосибирского государственного университета. Публикации.

Основные результаты диссертации опубликованы в журналах, входящих в перечень ВАК, ведущих рецензируемых научных журналов и изданий, где должны быть опубликованы основные научные результаты диссертации на соискание ученой степени кандидата физико-математических наук [27-30]. Структура и объем диссертации.

Диссертация состоит из введения, трех глав и списка литературы, который содержит 30 наименований. Объем диссертации составляет 92 страницы. Содержание диссертации. Введение.

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

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

В этой главе обогащенные идеалами алгебры Ершова рассматриваются в сигнатуре а = (и;п,\Д/, ,...,1Л), где - символы унарных предикатов,

выделяющие идеалы. Число Я считаем фиксированным. Алгебру Ершова с выделенными идеалами, имеющую наибольший элемент, принято называть /алгеброй.

Определение 1.1.1. Пусть дано семейство 1-алгебр Тогда следующая

/-алгебра называется а -смешиванием /-алгебр {31

ГГог /Ь Г^I ЮГ ^еЦтеЪ^ЭконечноеК^К }игЛ0/ Л

где операции и,п,\ и предикаты /,,/2определяются покомпонентно:

(/ п g)(i) = ДО п (/ и *Х0 = /(0 и 8(г), (/ \ *Х0 = ДО \ 8( 0, / е /, о 3*(((У/< Ш0 е ) & ((У/" > £)(/(/) = 0))).

а-степенью алгебры ЗГ называется т-смешивание счетного числа /-алгебр, изоморфных 3£.

Определение 1.1.2. Алгебру Ершова с выделенными идеалами 3£ назовем

неразложимой, если из ЗС = ЯЛ х 91 следует ЗГ = ЯК или 31 = 91.

Для целей настоящей главы обозначим, ЗС < ЯЛ, если 9Я = 31x91 и 31 £ 5Я.

Во втором параграфе первой главы изучаются суператомные алгебры Ершова с выделенными идеалами, имеющими конечный ранг Фреше. Получены следующие результаты. Теорема 1.2.1. Справедливы следующие утверждения:

(1) Алгебра Ершова с выделенными идеалами, имеющая конечный ранг Фреше, однозначно (с точностью до изоморфизма) представима в виде прямого произведения конечного числа неразложимых алгебр Ершова, несравнимых по отношению <

(2) Для любого натурального числа п существует конечное число счетных неразлоокимых алгебр Ершова с выделенными идеалами, имеющих ординальный тип п.

(3) Любая неразложимая алгебра Ершова с выделенными идеалами, имеющая конечный ранг Фреше, является со-степенью некоторой I-алгебры или является прямой суммой изоморфных копий некоторой неразложимой алгебры. В третьем параграфе первой главы изучаются суператомные алгебры Ершова с выделенными идеалами, имеющие счетный ранг Фреше. Теорема 1.3.5. Для алгебры Ершова с выделенными идеалами Ж и ОС -счетного ординала следующие условия эквивалентны:

(1) Любая алгебра Ершова с выделенными идеалами, элементарно эквивалентная 21, ординального типа ОС представима в виде прямого произведения конечного числа неразложимых алгебр.

(2) Найдется не более счетного числа попарно неизоморфных алгебр Ершова с выделенными идеалами, элементарно эквивалентных ЗГ, имеющих ординальный тип ОС.

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

В четвертом параграфе дано определение характеристической функции ЦТ, при помощи которой получено описание типов изоморфизма счетных Алгебр Ершова с выделенными идеалами, которые в факторе по идеалу Фреше Р содержат не более одного атома.

Теорема 1.3.10 .Пусть 2С и Ж - произвольные счетные суператомные ачгебры Ершова с выделенными идеалами, ординальный тип которых равен СО.

Предположим, что ^/р (Щ) содержат не более одного атома.

Тогда если 'Я и 23 являются одновременно булевыми алгебрами или специальными алгебрами Ершова, то ЗГ^ЯЗ тогда и только тогда, когда

совпадают характеристические функции =

Вторая глава.

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

Булевы алгебры будем рассматривать в сигнатуре <т = (п,и,С,0,1). Пусть

а = сги{Р}, где Р символ унарного предиката. Алгебраическую систему ЗГ

сигнатуры с* будем называть булевой алгеброй с выделенной подалгеброй, если

а/, ,

множество Рж = {аеЗГ|ЗГ|=.Р(а)} определяет подалгебру в булевой алгебре

Определение 2.1.4. Подалгебру 93 булевой алгебры ЗГ назовем плотной, если ЗГ = л'ыбгс (5Б,,Р(ЗГ)) - наименьшая подалгебра алгебры ЗГ, содержащая в себе подалгебру 33 и идеал Фреше ^(ЗГ) .

Определение 2.1.5. Подалгебру 33 булевой алгебры ЗГ назовем подалгеброй ширины п, если под любым атомом подалгебры 33 найдется не более п атомов алгебры ЗГ, лежащих под ним, и любой атом алгебры ЗГ лежит под некоторым атомом подалгебры 33.

Определение 2.1.8. Алгебраическую систему ЗГ назовем неисчезающей, если из ЗГ з Ш х 5Д следует ЗГ = 501 или ЗГ = . Обозначим ЗГ < 33, если найдется Е такая, что 93 = ЗГ х (Е.

Определение 2.1.9. Алгебраическую систему ЗГ назовем локальной, если существует не более конечного числа элементарно неэквивалентных неисчезающих алгебраических систем 23 < ЗГ, т.е. найдутся ЯЗ,,...,33 А такие, что если 33 < ЗГ и 33 -неисчезающая, то 33 = 33для некоторого ¡<к. Для каждого п е N определим следующий класс:

Кг = ЩЖ-суператомшя булева алгебра с выделеннойплотной подалгеброй ширины п

Далее зафиксируем число п е N и будем рассматривать булевы алгебры с выделенной подалгеброй только из К„.

Во втором параграфе второй главы построена последовательность формул Т>. (х) к е < языка а с одной свободной переменной и при ее помощи для каждой алгебры Ж е Кп определена характеристическая функция % :Лг-> Л'^ {со}. Значение функции ^(й) есть количество непересекающихся элементов алгебры 21, на которых истина формула Тк(х). Сформулирован и доказан ряд свойств построенной последовательности формул и характеристической функции. В четвертом параграфе дано синтаксическое описание всех реализуемых характеристических функций.

Первый результат настоящий главы определяет необходимое и достаточное условие локальности алгебры в классе Кп.

Теорема 2.3.14. Для того чтобы булева алгебра с выделенной подалгеброй ^е Кп была вокальной необходимо и достаточно, чтобы множество было конечным.

Следующий результат дает описание элементарной эквивалентности локальных алгебр.

Теорема 2.3.15. Пусть Ж и № произвольные локальные булевы алгебры с выделенными подалгебрами, принадлежащими классу К„. Тогда, для того

чтобы Ж = Ю необходимо и достаточно, чтобы = .

Булеву алгебру с выделенной подалгеброй 2Г назовем к-простой, если Ж\=ЭхТк(х) и для любого натурального числа / из 2Г(= 3x7] (х) следует, что на классе Кп истинно предложение Тк (х) -> (Зу < х)Т, (у).

Завершает параграф следующая теорема Теорема 2.3.17. Пусть Ж - локальная булева алгебра с выделенной подалгеброй, принадлежащая классу Кп. Тогда Ж - неисчезающая тогда и только тогда, когда Ж - к-простая и либо Ж |= Тк(1), либо щ(к) = оо.

Четвертый параграф третей главы дает описание всех характеристических функций. Для этой цели синтаксически определяется естественная функция и доказывается следующая

Теорема 2.4.1. Функция ы: N -> N и {ос} - естественна тогда и только тогда, когда найдется алгебраическая система ШеК„ такая, что\\> = м\.я. Третья глава.

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

Первый параграф третьей главы содержит постановку задачи. Определение 3.1.1. Пусть 2С - булева алгебра и /:ЗГ -> - ее автоморфизм. Обозначим: X, = {а е ЗС|/(в) = а} - множество неподвижных элементов автоморфизма / Подалгебру булевой алгебры Ж, основным множеством которой является множество неподвижных элементов Х}, будем называть неподвижной подалгеброй автоморфизма /; для простоты эту подалгебру также будем обозначать через Хг Будем говорить, что автоморфизм / определяется неподвижными элементами, если для любого автоморфизма g■.?t-*Ж т Хг = Хг следует / =

Очевидно, что автоморфизм однозначно определяет подалгебру своих неподвижных элементов. Естественным образом возникает обратный вопрос; Вопрос 1. В каком случае по подалгебре однозначно восстанавливается автоморфизм, множеством неподвижных элементов которого она является. Иными словами, какие подалгебры булевых алгебр являются неподвижными подалгебрами автоморфизмов, определяемых неподвижными элементами. Этот вопрос был поставлен С.С.Гончаровым.

Вопрос 2. Какие автоморфизмы булевых алгебр определяются своими неподвижными элементами.

Следующая теорема дает полный ответ на первый вопрос.

Теорема 3.1.2. Подалгебра В булевой алгебры И является неподвижной подалгеброй некоторого автоморфизма, определяемого неподвижными элементами, тогда и только тогда, когда выполнено следующее условие-, для любого а е найдутся Ь,с,с1 е 2Г такие, что: Р\. (а = Ьис)&(Ьпс = 0)&(ап<1 = 0)&(с,Ьис1 еВ) Р2. (Уе<Ь)(ефО-+егВ) РЗ.(\/р<с1)(рфО-*р£В) РА. (Уе < Ь)(3р < с!)(е и ре В) Р5. (Vр < (1) (Эе < Ь)(е и р е В)

Следствие 3.1.3. К = \р1,Х/)\/определяетсянеподвижнътиэлементаии) -

конечно-аксиоматизируемый класс.

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

Теорема 3.1.4. Автоморфизм / алгебры определяется неподвижными элементами тогда и только тогда, когда / = {или, что то же самое, когда

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

Следствие 3.3.1. Каждая булева алгебра изоморфна неподвижной подалгебре некоторого автоморфизма, определяемого неподвижными элементами.

И

Теорема 3.3.2.,Для атомной булевой алгебры Ж и автоморфизма / следующие условия эквивалентны:

1) /определяется неподвижными элементами;

2) / = /-';

3) X/ является подалгеброй ширины 2.

Предложение 3.3.3. Существует счётная суператомная булева алгебра 2Г с выделенной подалгеброй В ширины 2 такая, что В ф Х} для любого автоморфизма / булевой алгебрыЖ.

Предложение 3.3.4. Каждая плотная подалгебра конечной ширины атомной булевой алгебры является неподвижной подалгеброй некоторого автоморфизма. В частности, выделенная подалгебра любой алгебры из Кп является неподвижной подалгеброй некоторого автоморфизма. Следствие 3.3.5. Выделенная подалгебра алгебры ЖеКп является неподвижной подалгеброй некоторого автоморфизма, определяемого неподвижными элементами, тогда и только тогда, когда Ж еК .

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

1. Винокуров С.Ф., Дулатова З.А. О решетках подалгебр булевых алгебр. 17

Всесоюз. алгебраическая конф., Минск, 39-40,1983.

2. Гончаров С.С. Конструктивизируемость суператомных булевых алгебр. Алгебра и логика, 12, No 6, 853-858,1976.

3. Гончаров С.С. Счетные булевы алгебры и разрешимость. Новосибирск. Научная книга, 356 с., 1996.

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

5. Дулатова З.А. Булевы алгебры с выделенной локально-конечной группой автоморфизмов. 8 всесоюз. конф. по мат. Логике, Москва, 62,1986.

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

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

8. Ершов Ю.Л., Палютин Е.А. Математическая логика. Москва. Наука, 1987.

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

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

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

12. Пальчунов Д.Е. Конечно-аксиоматизируемые булевы алгебры с выделенными идеалами. Алгебра и логика, 26, No 4, 121-135,1987.

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

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

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

16. June P.-F. Touraille A. Idéaux elemetairement equivalents dans une algebre booleinee. C.R.Acad. Sci. Paris, Ser.Math., 299, No 10,415-418,1984.

17. Ketonen J. The structure of countable Boolean algebras. Ann of Math., 108, No 1,41-89,1978.

18. Pal'chunov D.E. Countably categorical Boolean algebras with distinguished ideals. StudiaLogica,46,No 2,121-135,1987.

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

20. Rubin M. The theory of Boolean algebras with a distinguished subalgebra is undecidable. Ann. Sci. Univ. Clermont 60, Math., 13,129-134,1976.

21. Ryll-Nardzewski C. On the categoriciti in power Xo. Bull. Acad. Polon. Sci. -Ser. Sci. Math. Astron. Phis., 7, 545-548,1959.

22. Tarski A. Arithmetical classes and types of Boolean algebras. Bull. Amer. Math. Soc., 55,63, 1949.

23. Touraille A. Elimination des quantificateurs dans la theorie elementaire des algebres de Boole munies d'une famille d'idéaux distingues. C. R. Acad. Sci. Paris. Ser. Math., 300, No 5,125-128, 1985.

24. Touraille A. Theories d'algebres de Boole munies d'idéaux distingues. I: Theories élémentaires. J. Symbolic Logic, 52, No 4, 1027-1043,1987.

25. Vaught R. Topics in the Theory of Arithmetical Classes and Boolean Algebras. Doctoral Thesis, University of California, Berkeley, 1954.

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

26. Трофимов A.B. Типы изоморфизма суператомных булевых алгебр с одним выделенным идеалом. Вычислительные системы, 156, 123-147, 1996

27. Trofimov A.V. Isomorphy types of superatomic Boolean algebras with one distinguished ideal. SibAM, 7, No 4,79-96,1998.

28. Трофимов A.B. Типы изоморфизма обогащенных суператомных алгебр Ершова. Математические труды, 3,No 2,182-201,2000.

29. Пальчунов Д.Е., Трофимов A.B. Локальные и неисчезающие суператомные булевы алгебры с выделенной плотной подалгеброй. Алгебра и логика, 50, No 6,2011.

30. Д.Е.Пальчунов А.В.Трофимов. Автоморфизмы булевых алгебр, определяемые неподвижными элементами. ДАН, 442, No 3,2012.

Подписано в печать 14.12.2011, формат бумаги 60x84/16, отпечатано на ризографе, шрифт №10, изд. л. 0.9, заказ № 72, тираж 100. СибГУТИ 630102, Новосибирск, ул. Кирова, 86

61 12-1/388

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

На правах рукописи

Су

Трофимов Александр Викторович

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

и алгебр Ершова

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

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

1

Научный руководитель д.ф.-м.н. Пальчунов Д.Е. Новосибирск - 2011

СОДЕРЖАНИЕ

Введение..................................................................................3

Глава 1. Типы изоморфизма счетных суператомных алгебр Ершова с выделенными идеалами...............................................8

1. Основные определения и обозначения...................................8

2. Типы изоморфизма суператомных алгебр Ершова конечного ординального типа..........................................................14

3. Алгебры Ершова счетного ординального типа........................22

Глава 2. Локальные и неисчезающие суператомные булевы алгебры с выделенной плотной подалгеброй.................................39

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

2. Построение семейства формул Тк(х), ..................................45

3. Локальные алгебры класса Кп, п> 2....................................56

4. Существование булевой алгебры с выделенной

подалгеброй для любой естественной функции......................74

Глава 3. Автоморфизмы булевых алгебр, определяемые неподвижными элементами........................................................78

1. Формулировка основного результата....................................78

2. Доказательство основных результатов....................................80

3. Следствия результатов, сформулированных в

первом параграфе.........................................................88

Литература................................................................................93

Введение.

Диссертация посвящена изучению обогащенных булевых алгебр и алгебр Ершова.

Исследование теоретико-модельных свойств булевых алгебр было начато в работах А. Тарского [26] и Ю. Л. Ершова [6]. Ими была предложена элементарная классификация булевых алгебр. В основополагающей работе Ершова [7] представлен алгебраический метод, с помощью которого удалось описать широкий класс типов изоморфизма счетных дистрибутивных решеток с относительными дополнениями (которые после этого были названы алгебрами Ершова [3]). В частности, из работы [7] следует характеризация Кетонена [21]. С. С. Гончаровым [2] предложена классификация типов изоморфизма счетных суператомных булевых алгебр.

Исследованию теоретико-модельных свойств булевых алгебр и их обогащений посвящено достаточно много работ. Впервые булевы алгебры с выделенными идеалами были рассмотрены Ершовым в [6]. В частности, там было доказано, что теория булевой алгебры с выделенным идеалом разрешима по крайней мере в следующих случаях:

1) 2С// конечна;

2) существует 8ир(х|х е /} и % - атомная.

М. Рабин доказал, что теория класса булевых алгебр с выделенным идеалом разрешима [23], М. Рубин доказал, что теория класса булевых алгебр с выделенной подалгеброй неразрешима [24]. Из работ Р. Воота [30] и

Ч. Рылль-Нардзевского [25] следует, что элементарная теория булевой алгебры имеет счетно категоричную теорию тогда и только тогда, когда она содержит не более чем конечное число атомов. А. С. Морозовым [10] построены примеры булевых алгебр с одним выделенным идеалом и неразрешимой теорией для любой ненулевой первой характеристики Ершова-Тарского.

В работах Д. Е. Пальчунова [11-15, 22] доказано, что в булевой алгебре можно выделить идеал с неразрешимой элементарной теорией в точности тогда, когда она не является суператомной, получены критерии элементарной эквивалентности булевых алгебр с выделенными идеалами и разрешимости их элементарных теорий, дано описание счетно категоричных и конечно аксиоматизируемых элементарных теорий, описана алгебра Лиден-баума-Тарского класса булевых алгебр с выделенными идеалами, доказано, что элементарные теории достаточно широкого класса булевых алгебр с выделенными идеалами не имеют простой модели, изучены теории, имеющие простые и счетно насыщенные модели.

А. Тураем [27, 28] предложено обогащение языка булевых алгебр с выделенными идеалами, допускающее элиминацию кванторов, изучены различные теоретико-модельные свойства булевых алгебр с выделенными идеалами. В. И. Мартьянов [9] исследовал разрешимость теорий булевых алгебр с выделенным автоморфизмом. С. Ф. Винокуров и 3. А. Дулатова [1] показали, что элементарная теория решеток подалгебр булевых алгебр неразрешима. Дулатова [4, 5] исследовала булевы алгебры с выделенной

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

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

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

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

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

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

Результаты диссертации докладывались на Международной конференции «Мальцевские чтения» в 2000-2001 и 2010 гг., а также на семинарах «Конструктивные модели», «Теория вычислимости», «Алгебра и логика» и «Прикладная логика» Новосибирского государственного университета.

Первая глава диссертации посвящена описанию типов изоморфизма счетных суператомных алгебр Ершова с выделенными идеалами. Доказано, что произвольная счетная суператомная алгебра Ершова с выделенными идеалами, имеющая конечный ранг Фреше, однозначно представима в виде прямого произведения конечного числа неразложимых алгебр Ершова, несравнимых по отношению "<".

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

IV.: N -» N и {сю}

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

С. С. Гончаровым поставлена следующая

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

Третья глава диссертации посвящена решению этой задачи. Здесь в явном виде указывается предложение логики предикатов первого порядка, характеризующее указанные подалгебры. Из полученного описания следует, что класс таких булевых алгебр с выделенной подалгеброй является,

конечно, аксиоматизируемым. Приводится описание всех автоморфизмов, определяемых неподвижными элементами, а именно, доказывается, что такие автоморфизмы - это в точности инволюции.

Глава 1.

ТИПЫ ИЗОМОРФИЗМА СЧЕТНЫХ СУПЕР АТОМНЫХ АЛГЕБР ЕРШОВА С ВЫДЕЛЕННЫМИ ИДЕАЛАМИ

Настоящая глава посвящена исследованию обогащенных счетных суператомных алгебр Ершова. Следуя [3], алгебрами Ершова мы называем дистрибутивные решетки с относительными дополнениями. Булевы алгебры с выделенными идеалами принято называть 1-алгебрами.

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

1. Основные определения и обозначения

С простейшими свойствами булевых алгебр и алгебр Ершова можно познакомиться в работах [3,8].

Пусть сг = (и,п, С,0,1) - сигнатура булевых алгебр. Для любой счетной

суператомной алгебры Ершова Ж найдется счетный ординал а такой, что = ^ > где Га (ЗС) - итерированная последовательность идеалов Фреше, определенных в [3]:

- (а е Щ а состоит из конечного числа атомов};

Ра(Ц)~ и^(З^), если ординал а предельный.

Р«Х .

Наименьший ординал а, для которого "^/р ~~ 0дн0элементная алгебра Ершова или ур ^^ содержит не более чем конечное число атомов, называется ординальным типом алгебры Ершова % и обозначается через

Понятия атома, атомного и безатомного элементов обогащенной алгебры Ершова, суператомной обогащенной алгебры Ершова совпадают с соответствующими понятиями для алгебр Ершова.

В настоящей главе алгебры Ершова рассматриваются в сигнатуре <ух - (и,п,\,0,1Л), где Л <оо - некоторое фиксированное натуральное

число. Через будем обозначать 5-й идеал алгебры Ершова "К.

Булеву алгебру с выделенными идеалами Ж назовем простейшей, если % а= 33со<х и для любого 5 < Л либо = {о}, либо = Ж. Для построения

более сложных алгебр Ершова используются конструкции прямой суммы алгебраических систем и ¿у-смешивания.

Определение 1.1.1. Пусть дано семейство /-алгебр ; }

геЛГ '

Обозначим

ieN

Следующая /-алгебра называется со -смешиванием /-алгебр {2С

геДГ ■

со

{И,,...,*.,..} =

/е

(3 конечное

К с Щ (V* е N \ К (ДО = 0*') V

■,и,п,\,0,/15...,/

я >

где операции и предикаты /,,/2,...,/А определяются покомпонентно:

(/ п £)(/) = Л0 п ¿КО, (/ ^ = ДО ^ ¿КО, (/ \ g)(i) = /(0 \ ^(0,

/ е /, 3£)/(/) е //*) & ((У/- > ¿)(/(у) = 0)))

со-Степенью /-алгебры 2С (обозначение: Ж"г) называется ¿у-смешивание счетного числа/-алгебр, изоморфных 2С, т.е. Ж10 =со{Ж1,...,Жт,..}1 где т = Ж для всех т.

Заметим, что для любого разнозначного отображения т множества натуральных чисел на себя справедливо

Семейство (последовательность) /-алгебр {^...Д,,,...} назовем представлением Ж, если Ж £ ю{Ж!,... ,Ж т,...} и, кроме того, о(Ж,) < о(Ж) для всех г.

Пусть {2С2С„,...} - произвольное семейство /-алгебр. Прямую сумму /алгебр 2СИ определим стандартным образом [3]:

¿еЛГ

¿еЛГ

(3 конечноеК с е N \ А" /(*) = О

где операции определяются точно так же, как и при ¿»-смешивании, а

предикаты , /2,... ,/я определяются правилом

Семейство/-алгебр {ЗС 2,... назовем а-представлением Ж, если

Ж г ^Ж п и о(2С,.) < о(Ж) для всех г.

пеИ

Прямой степенью /-алгебры 2С назовем алгебру где

/еЛГ геЛГ

Алгебра Ершова 2С называется специальной [3], если не существует ординала у < о(Ж), для которого ^^ имеет наибольший элемент.

Легко заметить, что алгебра Ершова является специальной в том и только том случае, когда существует <т -представление для Ж.

Для целей нашего исследования в этой главе будем писать 2С<33, если существует алгебраическая система © такая, что 33 = Ж х ©. Будем говорить, что 2С<Ш,если и^аз.

Определение 1.1.2. Алгебру Ершова с выделенными идеалами Ж назовем неразложимой, если из Ж = 5Шхследует Ж = Ш или Ж = SR.

Типом изоморфизма (или просто типом) алгебры Ершова Ж назовем класс г0Г Множество всех типов изоморфизма обозначим через Т.

Для каждого типа t е Т зафиксируем некоторую алгебру Ершова, принадлежащую t, которую обозначим через Ш,. Будем писать t<q, если Ш, <SBс/,

и t <q, если t < q и t±q. Тип t еТ назовем неразложимым, если Ш , - неразложимая алгебра. Множество неразложимых типов обозначим через Т*.

Пусть А - {2Сj,...,ЗСи,...} - произвольное семейство /-алгебр. Для /-алгебры (£ обозначим через мощность ||t€ г\А|| множества п А. Для i еТ

положим х (А) = z®, (А), х(А) = {xt (A)Lг •

Пусть Ж и Ш - счетные алгебры Ершова с выделенными идеалами. Множество 5с=2£хЗЗ назовем критерием изоморфизма, если S удовлетворяет следующим условиям:

Ах 1. (0,0) е S;

Ах 2. (a,b) gS —>(а = 0 <г^Ь = 0);

АхЗ. (a,b)eS-^■(\/c3bl,b2((ar^c,b]),(a\c,b\bl),(c\a,b2)eS ; Ах 4. (a,b) gS^■(Ve3a1,a2((al,bгле),(а \ax,b\e,),(a2,e\b) eS ; Ax 5. (a,b)eS ^(\/s<A)(aeIs <->be/s).

Теорема 1.1.3. Пусть Ж и S3 - счетные алгебры Ершоеа с выделенными идеалами. Тогда 2С = S3 в том и только том случае, когда существует критерий изоморфизма.

Доказательство практически дословно повторяет доказательство теоремы 1.5.3 (Воота об изоморфизме) из [3].

Предложение 1.1.4. Пусть 2£ = <у{2С15...,2im,..} - со-смешивание 1-ал-гебр и для каждого числа т справедливо Жт = S32m+1 xS32n)+2. Тогда Ж = Со{® з,...

Доказательство. Пусть /т : ^-S32m+1 xS32m+2 - изоморфизм. Рассмотрим отображение / = |J/m. Следующее множество будет критерием

т> 1

изоморфизма:

S = {(а,Ъ)\{о{а) < о(Ж) ->b= f(a))&(о(а) = о(Ж) -> 6 = 1 \ /(1 \ а))}. Предложение доказано.

Предложение 1.1.5. Пусть А является представлением для 1-алгебры Ж, В - представлением для 1-алгебры 33. Тогда для того, чтобы 2С = S3, достаточно, чтобы z(^)= Х(В) •

Доказательство аналогично доказательству предложения 1.1.4.

2. Типы изоморфизма суператомных алгебр Бршова конечного ординального типа

Целью настоящего параграфа является доказательство следующей теоремы.

Теорема 1.2.1. Справедливы следующие утверждения:

(1) Счетная суператомная алгебра Ершова с выделенными идеалами, имеющая конечный ординальный тип, однозначно (с точностью до изоморфизма) представима в виде прямого произведения конечного числа неразложимых алгебр Ершова, несравнимых по отношению

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

(3) Любая счетная неразложимая суператомная алгебра Ершова с выделенными идеалами, имеющая конечный ординальный тип, является О)-степенью некоторой 1-алгебры или прямой степенью некоторой неразложимой алгебры.

Доказательство вытекает из следующих утверждений.

Лемма 1.2.2. (а) Любая счетная суператомная алгебра Ершова с выделенными идеалами, имеющая конечный ординальный тип, представима в виде прямого произведения конечного числа неразложимых алгебр Ершова.

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

Доказательство леммы проведем индукцией по ординальному типу.

Базис индукции. Если Ж имеет ординальный тип 0, то найдутся простейшие /-алгебры Ж1,...,Жп, для которых Ж = Ж1х...хЖп. Ясно, что Ж1 -

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

Шаг индукции. Пусть Ж — произвольная счетная суператомная алгебра Ершова с выделенными идеалами, имеющая конечный ординальный тип а, и А = {Ж1,...,Жп,..} - некоторое семейство /-алгебр. Достаточно рассмотреть два случая.

Случай 1. Семейство А является а -представлением алгебры Ершова Ж. Так как о(Ж1) <о(Ж), то, принимая во внимание индукционное предположение, можно считать, что /-алгебра Ж1 является неразложимой для всех г. Пусть 5,(ЗС) = ^е7,*||^П^||>0}. По индукционному предположению 11 ||< со. Пусть ) = ,¿2,.../„}• Положим хк =\\1к Тогда имеет

место следующее разложение:

кеЫ к<=Ы

где

{¿1 > • • • ¿Л = {* ^ п\х, = *>}> Ь\> • • •>Л} = п\хг <бУ)> е \ е ■

Очевидно, что это разложение является искомым. Если для каждого числа к существует не более Бк неразложимых алгебр Ершова ординального типа к, то существует не более 8а_х неразложимых алгебр Ершова, удовлетворяющих условию случая 1.

Случай 2. Семейство А является представлением для Ж. Пусть Ж i -неразложимая /-алгебра для всех г. Положим

З^ЗС) = е Г*|0 <|| ? ГМ ||< о}). По индукционному предположению || ^(ЗС) ||< со. Пусть || ||= 0. В этом случае /-алгебра Ж неразложима. Действительно, пусть Ж = Пред-

положим для определенности, что о(2К) < о (Ж). Тогда Ш<Ж1х...хЖп.

Значит, существуют алгебры Шх <Ж1,...,Шп <Жп, для которых = х.. . Пусть алгебра . такова, что Ж1 = хЭ1.. Тогда либо Ж; = , либо Ж= 5Нг. С учетом предложения 1.1.5, получаем

Следовательно, /-алгебра Ж неразложима. Пусть || Б (Ж) ||> 0 и = {г^...,^}. Положим хк =|[ tk Г\А\\. Тогда найдется последовательность индексов {/,„}шеЛ, такая, что = х...х(Ш^у- х со^Ж.,...,Ж. ,...}. В силу

доказанного ¿»{2С,- неразложима, и требуемое разложение получено.

Легко заметить, что неразложимых алгебр Ершова, имеющих ординальный тип а, не более чем +2*° + ...+ . Лемма доказана.

Следствие 1.2.3. Для любого натурального числа п существует ровно счетное число неизоморфных счетных суператомных алгебр Ершова с выделенными идеалами, имеющих ординальный тип п.

Доказательство фактически получено при доказательстве леммы 1.2.2.

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

Доказательство следует из следствия 1.2.4 и леммы 1.2.2.

Для каждой счетной суператомной неразложимой алгебры Ершова с выделенными идеалами Ж, имеющей конечный ординальный тип, определим множество типов Тп следующим образом:

^( *1 1

(1) если Ж - простейшая алгебра Ершова, то Ту еТ |ЯЗг <Ж);

(2) если Ж - неразложимая /-алгебра, то найдутся неразложимые /алгебры Жг,...,Жп такие, что Ж = (Жгх...хЖ^ и

^/чК^ик);

1<п 1<П

(3) если Ж - специальная неразложимая алгебра Ершова, то найдется неразложимая /-алгебра ЯП, для которой Ж = ив этом случае

/еЛГ

й/е/

полагаем = Тш и }.

Лемма 1.2.5. Пусть Ж - произвольная сче