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

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

Исследование теоретико-модельных свойств булевых алгебр было начато в работах А. Тарского [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. Винокуров С. Ф., Дулатова З. А. О решетках подалгебр булевых алгебр. 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, No 3, 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.

11. Пальчунов Д. Е. О неразрешимости теорий булевых алгебр с выделенными идеалами. Алгебра и логика, 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. Пальчунов Д. Е., Трофимов A.B. Локальные и неисчезающие суператомные булевы алгебры с выделенной плотной подалгеброй. Алгебра и логика, 50, No 6, 2011.

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

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

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

20. Jurie P.-F. Touraille A. Ideaux elemetairement equivalents dans une algebre booleinee. C.R.Acad. Sci. Paris, Ser.Math., 299, No 10, 415−418, 1984.

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

22. Pal’chunov D.E. Countably categorical Boolean algebras with distinguished ideals. Studia Logica, 46, No 2, 121−135, 1987.

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

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

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

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

27. Touraille A. Elimination des quantificateurs dans la theorie elementaire des algebres de Boole munies d’une famille d’ideaux distingues. C. R. Acad. Sci. Paris. Ser. Math., 300, No 5, 125−128, 1985.

28. Touraille A. Theories d’algebres de Boole munies d’ideaux distingues. I: Theories elementaires. J. Symbolic Logic, 52, No 4, 1027−1043, 1987.

29. Trofimov A.V. Isomorphy types of superatomic Boolean algebras with one distinguished ideal. Sib AM, 7, No 4, 79−96, 1998.

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