Квазимногообразия частичных алгебр тема диссертации и автореферата по ВАК РФ 01.01.06, кандидат физико-математических наук Шеремет, Михаил Сергеевич

• Шеремет, Михаил Сергеевич
• кандидат физико-математических наук
• 2001

Оглавление диссертации кандидат физико-математических наук Шеремет, Михаил Сергеевич

Введение

Глава 1.

Семантики равенства на частичных алгебрах

1. Основные конструкции на алгебрах.

2. Предикатные представления частичных алгебр

3. Определение и простейшие свойства семантик

4. Описание алгебр, заданных соотношениями на определенность термов.

5. Исчисление тождеств для слабой семантики.

6. Исчисление тождеств в семантике Эванса

Глава 2.

Разложения в квазимногообразиях частичных алгебр

7. Характеризация квазимногообразий частичных алгебр

8. Неразложимые и подпрямо неразложимые алгебры

9. Конгруэнции

10. Квазимногообразия частичных алгебр, в которых мощности неразложимых алгебр ограничены

11. Примеры многообразий частичных алгебр, в которых классы подпрямо неразложимых алгебр не аксиоматизируемы в СооШ

Введение диссертации (часть автореферата) на тему «Квазимногообразия частичных алгебр»

Началом исследований частичных алгебр можно считать вышедшую в 1951 году работу Эванса [21], в которой он определил понятие истинности тождества на частичной алгебре и доказал, что в многообразии полных алгебр, определенном тождествами Е, однородная проблема равенства разрешима, если любая частичная алгебра, удовлетворяющая Е, вложима в полную алгебру из данного многообразия.

Вообще, широкий круг вопросов связан с изучением частичных алгебр, возникающих как "части" полных алгебр некоторого данного класса, см. [23, глава 2]. С другой стороны, алгебры с частичными операциями совершенно естественно возникают в информатике (см., например, [10], а также пункт 22.2 в [14], посвященный этому вопросу) и их изучение также требовало построения соответствующей теории.

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

Равенство s « t называется истинным в слабой семантике в частичной алгебре Л при означивании v, если из того, что значения s^fi»] и tA[v] определены, следует, что они равны. Тождества в слабой семантике рассматривались в работах Поитресс [26], Рудака [28, 29] и Бинчака [12]. В частности, в [28] строится полная и корректная система правил вывода для тождеств в слабой семантике. В [12] дается описание классов частичных алгебр, аксиоматизируемых тождествами 1 в слабой семантике.

Равенство s « t называется истинным в семантике Клини в частичной алгебре А при означивании v, если из того, что одно из значений s"4^] и tA[v\ определено, следует, что определено второе и они равны. Различные вопросы, связанные с тождествами в семантике Клини, изучались в работах Андреки, Крейга и Немети [8], Крейга [19], Робинсона [27] и Бёрнера [13]. В работе [19] детально исследованы исчисления для тождеств в семантике Клини в сигнатуре, расширенной дополнительными логическими символами (например, проекции или пустого отображения). В [27] строится полная и корректная система правил вывода для тождеств в семантике Клини. В [13] дается характериза-ция в терминах клонов и в терминах алгебраических операторов для классов, аксиоматизируемых тождествами в семантике Клини в сигнатуре с логическим символом для проекции.

Наконец, равенство s « t называется истинным в сильной семантике в частичной алгебре Л при означивании v, если значения s^ft;] и tA[v] определены и равны. В отличие от всех других семантик, в которых простейшие формулы с равенством интерпретируются как условные, для сильной семантики имеет смысл рассматривать не только тождества, но и произвольные формулы, в частности, квазитождества. В монографии [14], основу которой составляют результаты, полученные Андрекой, Бурмайстером и Немети (ср. [9], [7]), для различных фрагментов квазиэквациональной логики в сильной семантике приводятся полные и корректные системы правил вывода, а также характериза-ция классов частичных алгебр, аксиоматизируемых соответствующими предложениями. Заметим, что многообразия частичных алгебр в других семантиках являются квазимногообразиями специального вида в сильной семантике.

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

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

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

Дается алгебраическая и синтаксическая'характеризация квазимногообразий частичных алгебр, в которых мощности всех (частично) неразложимых алгебр ограничены некоторым кардиналом. Необходимо отметить, что для многообразий полных алгебр исследование свойства ограниченности мощностей подпрямо неразложимых алгебр было начато У. Тейлором в работе [33], где он дал алгебраическую и синтаксическую характеризацию таких многообразий. Позднее Болдуин и Берман [11] получили синтаксическую характеризацию многообразий полных алгебр, в которых мощности подпрямо неразложимых алгебр не превосходят некоторого конечного числа п. Ими же был поставлен вопрос, возможно ли описать свойства, рассматриваемые в [33] и [11] для более широких классов.

Далее строятся два примера, показывающие, что в частичном случае различие между классами (частично) неразложимых и подпрямо (частично) неразложимых частичных алгебр является существенным (для полных алгебр все эти классы совпадают). В первом примере строится счетно базируемое многообразие частичных алгебр Vo в семантике Клини такое, что все неразложимые в Vo частичные алгебры не более чем счетны, а класс подпрямо неразложимых в V0 частичных алгебр не аксиоматизируем в логике Соош- Во втором примере строится конечно базируемое многообразие частичных алгебр Vi в семантике Клини такое, что класс подпрямо неразложимых в Vi частичных алгебр не аксиоматизируем в логике £оооо

Эти примеры представляют интерес в связи со следующим результатом: если Q — квазимногообразие частичных алгебр и мощность его сигнатуры меньше Л, где Л ^ ш, то класс (частично) неразложимых алгебр аксиоматизируем в логике С\ш. Это утверждение является непосредственным следствием характеризации главных Q-конгруэнций в терминах специального вида формул первого порядка, конгруэнц-формул. В полных алгебрах конгруэнц-формулы являются ключевым звеном, связывающим формульные свойства решеток относительных конгруэнций с формульными свойствами самого квазимногообразия. Поэтому эти примеры показывают, что введенное нами понятие (частичного) разложения является в частичном случае более перспективным чем понятие (частичного) подпрямого разложения.

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

Основными результатами работы являются следующие.

1. Построена полная и корректная система правил вывода для тождеств в семантике Эванса

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

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

4. Получена синтаксическая характеризация квазимногообразий частичных алгебр, в которых мощности (частично) неразложимых алгебр ограничены.

5. Построены многообразия Vo и Vi частичных алгебр в семантике Клини, обладающие следующими свойствами:

Vo имеет счетную сигнатуру и счетный базис тождеств; класс неразложимых в Vo частичных алгебр состоит, с точностью до изоморфизма, из конечного числа не более чем счетных частичных алгебр; класс подпрямо неразложимых в Vo частичных алгебр не является проективным в логике С^ш'-,

Vi имеет конечную сигнатуру и конечный базис тождеств; класс подпрямо неразложимых в Vi частичных алгебр не является проективным в логике С0000.

В работе используются алгебраические методы теории квазимногообразий (см. монографию В.А.Горбунова [3]), применяемые к предикатным представлениям частичных алгебр, а также методы универсальной алгебры.

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

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

Результаты диссертации докладывались на международной конференции "Мальцевские чтения" (Новосибирск, 2000), на IV Международной конференции, посвященной 60-летию со дня рождения Ю. И. Мерзлякова (Новосибирск, 2000), на III Международной школе "Пограничные вопросы теории моделей и универсальной алгебры" (Эрлогол, 1999), а также на семинарах "Алгебра и логика", "Нестандартные логики" и "Универсальная хорнова логика" Новосибирского государственного университета.

Все основные результаты диссертации опубликованы в работах [34]-[39]. Результаты совместной работы [34] получены в неразделимом соавторстве с В. А. Горбуновым.

Диссертация состоит из введения, двух глав, разбитых на одиннадцать параграфов, и списка литературы. Нумерация параграфов — сквозная. Утверждения нумеруются двумя цифрами: первая — номер параграфа, а вторая — номер утверждения в нем. Аналогичная нумерация используется для формул. Список литературы содержит 39 наименований, объем диссертации составляет 81 страницу.

Список литературы диссертационного исследования кандидат физико-математических наук Шеремет, Михаил Сергеевич, 2001 год

1. В. А. Горбунов, Мощности подпрямо неразложимых систем в квазимногообразиях, Алгебра и логика, 25, N 1 (1986), 3-50.

2. В. А. Горбунов, Строение решеток многообразий и решеток квазимногообразий: сходство и различие. I, Алгебра и логика, 34, N 2 (1995), 142-168.

3. В. А. Горбунов, Алгебраическая теория квазимногообразий, Новосибирск, Научная книга, 1999.

4. В. А. Горбунов, В. И. Туманов, Строение решеток квазимногообразий, Труды Ин-та матем. СО АН СССР, 2 (1982), 12-44.

5. А. И. Мальцев, Подпрямые произведения моделей, Докл. АН СССР, 109, N 2 (1956), 264-266.

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

7. Н. Andreka, P. Burmeister and I. Nemeti, Quasi-equational logic of partial algebras, Polish Acad. Sci. Inst. Philos. Sociol. Bull. Sect. Logic, 9, no. 4 (1980), 193-199.

8. H. Andreka, W. Craig, I. Nemeti, A system of logic for partial functions under existent dependent Kleene equality, J. Symb. Logic 53, N 3 (1988), 834-839.

9. H. Andreka, I. Nemeti, Generalizations of the concept of variety and quasivariety to partial algebras through category theory, Diss. Math., 204 (1983).

10. H. Andreka and I. Nemeti, Importance of universal algebra for computer science, Proc. 25. Arbeitstag. Allgemeine Algebra, Darmstadt, 1983, Res. Expo. Math. 4 (1984) 204-215.

11. J. T. Baldwin, J. Berman, The number of subdirectly irreducible algebras in a variety, Algebra Univers., 5, N 3 (1975), 397-389.

12. G. Binczak, A charachterization theorem for weak varieties, Algebra Univers., 45, N 1 (2001), 53-62.

13. F. Borner, Varieties of partial algebras, Contrib. to Algebra and Geometry, 37, N 2 (1996), 259-287.

14. P. Burmeister, A model-theoretic oriented approach to partial algebras. Part I, Berlin, Akademie-Verlag, 1986. r

15. P- Burmeister, Subdirect representations by epimorphisms in quasi-varieties of partial algebras, Preprint 2010, Techn. Univ. Darmstadt, 1998.

16. P- Burmeister, F. Rossello, L. Rudak, On Hofts charachterization of weak model classes, Algebra Univers., 34, N 2 (1995), 214-219.

17. P- Burmeister, M. Siegmund-Schultze, Subdirect representations of partial algebras, Preprint 867, Techn. Univ. Darmstadt, 1984.

18. S. Burrris, Polynomial time uniform word problems, Math. Logic Quart., 41 (1995), 173-182.

19. W. Craig, Near-equational and equational systems of logic for partial functions, J. Symb. Logic, 54, N 3,4 (1989), 795-827, 1181-1215.

20. A. C. Davis, A characterization of complete lattices, Pacif. J. Math., 5 (1955), 311-319.

21. T. Evans, The word problem for abstract algebras, J. London Mat. Soc., 26 (1951), 64-71.

22. T. Evans, Embeddability and the word problem, J. London Mat. Soc., 28 (1953), 76-80.

23. G. Gratzer, Universal algebra, 2nd ed., Springer-Verlag, New York, 1979.

24. H. Hoft, Weak and strong equations in partial algebras, Algebra Univers., 3, N 2 (1973), 203-215.

25. Model-theoretic logics, ed. by J. Barwise, S. Feferman, Springer— Verlag, 1985.

26. V. S. Poythress, Partial morphisms on partial algebras, Algebra Univers., 30 N 2 (1973), 182-202.

27. A. Robinson, Equational logic for partial functions under Kleene equality: a complete and incomplete set of rules, J. Symb. Logic, 54, N 2 (1989), 354-362.

28. L. Rudak, A completeness theorem for weak equational logic, Algebra Univers., 16 N 3 (1983), 331-337.

29. L. Rudak, Algebraic characterization of conflict-free varieties of partial algebras Algebra Univers., 30 N 1 (1993), 89-100.

30. J. Slominski, Peano-algebras and quasi-algebras, Diss. Math., 62 (1968).

31. A. Tarski, A lattice theoretical fixpoint theorem and its applications, Pacif. J. Math., 5 (1955), 285-309.

32. W. Taylor, Some constructions of compact algebras, Annals of Math. Logic, 3, N 4 (1971), 395-436.

33. W. Taylor, Residually small varieties, Algebra Univers., 2, N 1 (1972), 33-53.Работы автора по теме диссертации

34. В. А. Горбунов и М. С. Шеремет, Хорновы классы предикатных систем и многообразия частичных алгебр, Алгебра и логика, 39, N 1 (2000), 23-36.

35. М. С. Шеремет, Ретрактные разложения компактных систем, Алгебра и теория моделей 2, А. Г. Пину с и К. Н. Пономарев, ред., Новосибирск, 1999, 136-139.

36. М. С. Шеремет, Теорема полноты для логики тождеств Эванса, препринт 56, НИИ Дискретной математики и информатики, Новосибирск, 2001.

37. М. С. Шеремет, Неразложимые алгебры в квазимногообразиях частичных алгебр, препринт 55, НИИ Дискретной математики и информатики, Новосибирск, 2001.

38. М. С. Шеремет, Исчисление тождеств в семантике Эванса, Материалы XXXIX Междунар. студ. конф., Математика, Новосибирск, 2001, 16-17.

39. М. С. Шеремет, Неразложимые алгебры в квазимногообразиях частичных алгебр, Материалы XXXIX Междунар. студ. конф., Математика, Новосибирск, 2001, 17-18.