Конструктивные булевы алгебры с выделенными идеалами

Одним из наиболее интересных и актуальных направлений в современных математических исследованиях феномена вычислимости является теория конструктивных (вычислимых) моделей, которая возникла в 50-е годы прошлого столетия в работах А. Фрелиха, Д. Шефердсона, А. И. Мальцева, В. А. Кузнецова, О. Рабина и Р. Во-ота. Это направление связано с исследованием алгоритмических свойств абстрактных моделей на основе построения для них представления на натуральных числах и изучения взаимоотношений алгоритмических и структурных свойств этих моделей.

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

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

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

Булевы алгебры являются одним из фундаментальных объектов современной математики. Точно так же, как действительные числа являются математической формализацией количества, булевы алгебры являются формализацией меры истинности логических заключений. Можно выделить три основных направления в изучении булевых алгебр. Первое направление посвящено изучению алгебраических свойств булевых алгебр, к важнейшим результатам которого следует отнести теорему Стоуна о представимости булевых алгебр как алгебр подмножеств и характеризацию Кетонена типов изоморфизма счетных булевых алгебр. Второе, теоретико — модельное направление основывается на классификации полных элементарных теорий булевых алгебр, полученной в работах Ю. Л. Ершова и А. Тарского. И, наконец, третье направление — изучение алгоритмических свойств счетных булевых алгебр на основе построения эффективных представлений для них. Все эти три направления (в большей степени второе и третье) отражены в монографии [6]. Многочисленные направления в изучении булевых алгебр достаточно полно представлены в справочной книге по теории булевых алгебр [24].

В связи с появлением структур булевых алгебр в различных разделах математики, на булевых алгебрах рассматриваются дополнительные конструкции. Наиболее систематическое изучение получили булевы алгебры с выделенными идеалами (которые, в дальнейшем мы будем для краткости называть /-алгебрами). В работах многих авторов [13]—[18], [23], [25]—[30] исследовались элементарные теории /-алгебр. Результаты этих исследований демонстрируют существенные различия между классом булевых алгебр и классом /алгебр в рамках второго (теоретико — модельного) направления.

Так М. Рабином [27] установлена разрешимость теории класса /-алгебр. Однако, в [13] показано, что в булевой алгебре можно выделить идеал с неразрешимой элементарной теорией тогда и только тогда, когда она не суператомна. В [13, 23] показано, что существует континуум элементарно неэквивалентных /-алгебр. В [14, 25, 26] описаны счетно-категоричные /-алгебры, а в [15] - конечно аксиоматизируемые /-алгебры. В [15] также дан критерий разрешимости элементарных теорий /-алгебр. В [15, 28, 29] даны критерии элементарной эквивалентности /-алгебр.

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

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

Будем рассматривать /-алгебры в сигнатуре.

V, Л, С, 0,1,/1,.,/Л), где /ь.,/л — символы унарных предикатов. Теория Т класса /алгебр порождается аксиомами булевых алгебр и предложениями, которые утверждают, что предикаты /1,.,/д выделяют идеалы. В дальнейшем, если не оговорено особо, натуральное число, А ^ 1 считается фиксированным.

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

Глава 2 посвящена проблеме вычислимости класса всех конструктивных /-алгебр. В параграфе 2.1 дано полное описание всех конструктивных /-алгебр с точностью до рекурсивного изоморфизма в терминах порождающих бинарных деревьев и идеальных подмножеств в этих деревьях. В параграфе 2.2 построена равномерно эффективная процедура, которая по заданному натуральному п конструирует вычислимую /-алгебру с номером п. Предложенная конструкция позволяет доказать существование универсальной вычислимой нумерации {(21^, 1/*) | п? М} для класса всех конструктивных /-алгебр, то есть такой нумерации, к которой сводится любая вычислимая нумерация любого подкласса конструктивных I-алгебр. Поскольку универсальная нумерация очевидно является главной, то можно утверждать о строгой вычислимости класса всех конструктивных /-алгебр. В параграфе 2.3 рассматривается вопрос единственности (с точностью до изоморфизма нумераций) построенной универсальной нумерации конструктивных /-алгебр. Используя понятие полной нумерации абстрактного множества [11], доказывается, что любые две универсальные вычислимые нумерации конструктивных /-алгебр сводятся друг к другу с помощью рекурсивных перестановок.

Таким образом, основной результат главы 2 можно сформулировать в виде следующих двух утверждений:

Теорема 2.2.1. Последовательность {(21^,^) | п 6 К} является универсальной вычислимой нумерацией класса конструктивных 1-алгебр. В частности, класс конструктивных I-алгебр строго вычислим.

Следствие 2.3.1. Любые две универсальные вычислимые нумерации класса всех конструктивных 1-алгебр рекурсивно изоморфны.

В главе 3, на основе результатов предыдущей главы, изучаются отдельные свойства вычислимых нумераций конструктивных /алгебр и сопряженные с ними вопросы алгоритмической сложности индексных подмножеств. Наличие универсальной вычислимой нумерации позволяет дать точные оценки арифметической сложности некоторых естественных подклассов конструктивных /-алгебр. В параграфе 3.1 найдены оценки сложности для таких классов, как атомные /-алгебры, безатомные /-алгебры, автоустойчивые /алгебры и другие. Далее в параграфе 3.2 изучается вопрос мощности верхней полурешетки Роджерса вычислимых нумераций класса конструктивных /-алгебр. Доказано, что существует бесконечное число попарно несравнимых по сводимости вычислимых нумераций рассматриваемого класса алгебр, то есть полурешетка Роджерса бесконечна и имеет счетную ширину. В параграфе 3.3 показано, что нумерационная эквивалентность (с точностью до рекурсивного изоморфизма) любой вычислимой нумерации класса конструктивных /-алгебр принадлежит классу ?3 арифметической иерархии, но не принадлежит классу Л3. Это утверждение обобщает результат С. С. Гончарова и Дж. Ф. Найт [21] об отсутствии однозначных вычислимых нумераций для класса конструктивных булевых алгебр. Более того, класс конструктивных /-алгебр не имеет позитивных и негативных (с точностью до рекурсивного изоморфизма) вычислимых нумераций.

Основными результатами главы 3 являются:

Предложение 3.2.3. Класс всех конструктивных I-алгебр имеет бесконечное число попарно несравнимых по сводимости вычислимых нумераций.

Предложение 3.3.1. Для произвольной вычислимой нумерации, а класса всех конструктивных I-алгебр нумерационная эквивалентность ва € ?3 Л3.

Следствие 3.3.1. Класс всех конструктивных I-алгебр не имеет однозначных, позитивных, негативных вычислимых нумераций.

Глава 4 посвящена исследованию алгоритмической размерности конструктивных булевых алгебр с одним выделенным идеалом. В [3, 7] установлено, что конструктивизируемая булева алгебра автоустойчива тогда и только тогда, когда она имеет лишь конечное число атомов. В данной главе найден критерий автоустойчивости булевых алгебр с одним выделенным идеалом, причем необходимые и достаточные условия автоустойчивости являются алгебраическими. В параграфе 4.1 описаны все неавтоустойчивые конструктиви-зируемые булевы алгебры с одним выделенным идеалом. Доказано, что каждая неавтоустойчивая булева алгебра с одним выделенным идеалом имеет эффективно бесконечный класс конструктивизаций. Параграф 4.2, напротив, посвящен описанию класса всех автоустойчивых булевых алгебр с одним выделенным идеалом. В параграфе 4.3 сформулирован и доказан окончательный критерий автоустойчивости. Описан спектр всех возможных авторазмерностей булевых алгебр с одним выделенным идеалом.

Основными результатами главы 4 являются:

Теорема 4.3.1. Конструктивизируемая I-алгебра (05,/) автоустойчива тогда и только тогда, когда выполнены следующие три условия:

1) Множество атомов алгебры 05 конечно.

2) Идеал J {х е | (Vy ^ х)(у .

3) Множество атомов фактор-алгебры 05/I конечно.

Следствие 4.3.1. Авторазмерность булевых алгебр с выделенным идеалом может принимать лишь три значения: 0,1,и>.

Следствие 4.3.2. Класс конструктивизаций любой неавтоуст-ойчивой булевой алгебры с выделенным идеалом эффективно бесконечен.

Основные результаты данной диссертации представлены в работах автора [31]-[35], а также докладывались на международной научной конференции Logic Colloquium 2000, и на семинарах «Алгебра и логика», «Конструктивные модели», «Терия нумераций» Новосибирского Государственного Университета.

Пользуясь случаем, автор выражает глубокую признательность своему научному руководителю профессору С. С. Гончарову за постановку задач, постоянное внимание к исследованиям автора, и всестороннюю поддержку в работе.

1. Ю. Г. Венцов, Алгоритмические свойства ветвящихся моделей, Алгебра и логика, 25, № 4 (1986), 369−383.

2. С. С. Гончаров, Автоустойчивость и вычислимые семейства кон-структивизаций, Алгебра и логика, 14, № 6 (1975), 647−680.

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

4. С. С. Гончаров, Автоустойчивость моделей и абелевых групп, Алгебра и логика, 19, № 1 (1980), 23−44.

5. С. С. Гончаров, Проблема числа неавтоэквивалентных кон-структивизаций, Алгебра и логика, 19, № 6 (1980), 621−639.

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

7. С. С. Гончаров, В. Д. Дзгоев, Автоустойчивость моделей, Алгебра и логика, 19, № 1 (1980), 45−58.

8. С. С. Гончаров, Ю. Л. Ершов, Конструктивные модели, Научная книга, Новосибирск, 1999.

9. В. П. Добрица, Вычислимость некоторых классов конструктивных алгебр, Сиб. мат. журн., 18, № 3 (1977), 570−579.

10. В. П. Добрица, Локальные классы и вычислимые индексации, Алгебра и логика, 26, № 2 (1987), 165−190.

11. Ю. Л. Ершов, Теория нумераций, Наука, Москва, 1977.

12. А. Т. Нуртазин, Сильные и слабые конструктивизации и вычислимые семейства, Алгебра и логика, 13, № 3 (1974), 311−323.

13. Д. Е. Палъчунов, О неразрешимости теорий булевых алгебр с выделенным идеалом, Алгебра и логика, 25, № 3 (1986), 326 346.

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

15. Д. Е. Палъчунов, Конечно-аксиоматизируемые булевы алгебры с выделенными идеалами, Алгебра и логика, 26, № 4 (1987), 435−455.

16. Д. Е. Палъчунов, Прямые слагаемые булевых алгебр с выделенными идеалами, Алгебра и логика, 31, № 5 (1992), 499−537.

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

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

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

20. X. Роджерс, Теория рекурсивных функций и эффективная вычислимость, Мир, Москва, 1972.

21. S.S.Goncharov, J. F. Knight, Computable structure/non-structure theorems, Algebra and logic, to appear.

22. Handbook of Recursive Mathematics, Yu.L.Ershov, S.S.Goncharov, A. Nerode and J.B.Remmel, (eds.), 1−2, Elsevier, Amsterdam, 1998.

23. P.-F.Jurie, A. Touraille, Ideaux elementairement equivalents dans une algebre booleienne, C. R. Acad. Sci. Paris, Ser. I, 299, № 10 (1984), 415−418.

24. S. Koppelberg, Handbook of Boolean Algebras, 1−3, North-Holland, Amsterdam-New York, 1989.

25. A. Macintyre, J.G.Rosenstein, No-Caregoricity for Rings without Nilpotent Elements and for Boolean structures, J. Algebra, 43, № 1 (1976), 129−154.

26. D.E.PaVchunov, Countabably-categorical Boolean algebras with distinguished ideals, Studia Logica, 46, № 2 (1987), 121−135.

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

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

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

30. A. Touraille, Theories d’algebres de Boole munies d’ideaux distingues. II., J. Symbolic Logic, 55, № 3 (1990), 1192−1212.Работы автора по теме диссертации.

31. Н. Т. Когабаев, Автоустойчивость булевых алгебр с выделенным идеалом, Сиб. мат. журн., 39, № 5 (1998), 1074−1084.

32. Н. Т. Когабаев, Универсальная нумерация вычислимых булевых алгебр с выделенным идеалом, Структурные и сложност-ные проблемы вычислимости, Новосибирск, 1999. Вычислительные системы, Вып. 165, 139−152.

33. Н. Т. Когабаев, Универсальная нумерация конструктивных I-алгебр, Алгебра и логика, 40, № 5 (2001).

34. Н. Т. Когабаев, О вычислимых нумерациях конструктивных I-алгебр, Вестник НГУ, Серия: матем., механика, информ., 1, № 1 (2001), 54−66.

35. N.T.Kogabaev, Strictly Computability of Class of Constructive I-algebras, Abstracts of Contributed Papers, LC 2000 and ELSS 2000, Paris, La Sorbonne, 23−31 juillet 2000, p. 156.