Свободные и конечно определенные алгебры многообразий квазигрупп и многообразий Кантора

1. Многообразия универсальных алгебр стали предметом активных исследований в середине 30-х годов, когда были опубликованы первые работы Г. Биркгофа в этой области. Значительный вклад в формирование и становление проблематики теории многообразий универсальных алгебр внесли А. Тарский и А. И. Мальцев (см. [44, 54]).

Развитие математической логики и теории алгоритмов (К. Гёдель, А. Чёрч, С. Клини, Б. Россер, А. Тьюринг, Э. Пост, A.A. Марков) привело к появлению новой проблематики — исследованию разрешимости элементарных теорий алгебраических систем и классов таких систем. Первые основополагающие результаты в этой области принадлежат А. Тарскому (конец 40-х годов). Важнейший вклад в развитие данного направления внес А. И. Мальцев. Результаты по элементарным теориям систематизированы в обзоре [24] и монографии [23]. Существенная часть работ по элементарным теориям относится к многообразиям универсальных алгебр. Дальнейший прогресс в обсуждаемом направлении изложен в [11, 12. 26, 47, 55, 65].

Термин «квазигруппа» был введен Р. Муфанг, работы которой в середине 30-х годов поло? кили начало развитию алгебраической теории квазигрупп (см. [6, 53, 57]).

Многообразия Кантора впервые были рассмотрены в работе Б. Йон-сона и А. Тарского [64].

2. Диссертация посвящена изучению свойств свободных и конечно определенных алгебр в трех классах многообразий квазигрупп и луп, называемых далее^{-многообразиями} (г — 1,2,3), а также в многообразиях Кантора Cmjl.

Для Rj-многообразий основными рассматриваемыми проблемами являются следующие:

1. Определить число^{-многообразий} для каждого г {г = 1,2,3). Известные изначально оценки числа этих многообразий слишком велики.

2. Доказать разрешимость (или неразрешимость) элементарной теории свободной алгебры произвольного ранга из /^-многообразия (г = 1, 2, 3). Рассмотреть аналогичную задачу для классов свободных алгебр.

3. Доказать разрешимость (или неразрешимость) элементарной теории произвольной конечно определенной алгебры из Я^-много-образия (г — 1, 2, 3).

Для многообразий Кантора Ст-Гг рассматриваются следующие проблемы:

1. Исследовать разрешимость элементарной теории свободной алгебры (класса свободных алгебр) многообразия Ст^п.

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

3. Для конечно определенных алгебр многообразия Ст. п установить разрешимость (или неразрешимость) a) проблемы равенства словb) проблемы вхождения.

4. Для конечно определенных алгебр многообразия Ст-П доказать разрешимость (или неразрешимость) их элементарных теорий.

5. Исследовать разрешимость элементарной теории многообразия Г.

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

Материал распределен по главам следующим образом.

1. Акатаев A.A. О многообразиях А (т, п) // Алгебра и логика, 1970, Т. 9, N 2, С. 127−136.

2. Акатаев A.A., Смирнов Д. М. Решетки подмногообразий многообразий алгебр // Алгебра и логика, 1968, Т. 7, N 1, С. 5−25.

3. Барендрегт X. Ламбда-исчисление. Его синтаксис и семантика. — М.: Мир, 1985. — 606 с.

4. Белеградек О. В. Теория моделей локально свободных алгебр // Теория моделей и ее применения. Новосибирск: Наука, 1988. С. 3−25. (Тр. АН СССР. Сиб. отд-ние. Ин-т математикиТ.8.).

5. Белкин В. П. О некоторых решетках квазимногообразий алгебр // Алгебра и логика, 1976, Т. 15, N 1, С. 12−21.

6. Белоусов В. Д. Основы теории квазигрупп и луп. — М.: Наука, 1967. — 223 с.

7. Белоусов В. Д., Белявская Г. Б. Латинские квадраты, квазигруппы и их приложения. — Кишинев: Штиинца, 1989. — 80 с.

8. Биркгоф Г. Теория решеток. — М.: Наука, 1984. — 568 с.

9. Больбот А. Д. Об эквационально полных многообразиях тотально симметрических квазигрупп // Алгебра и логика, 1967, Т. 6, N 2, С. 13−19.

10. Бухбергер Б., Лоос Р. Упрощение алгебраических выражений. — В кн.: Компьютерная алгебра: Символьные и алгебраические вычисления / Под ред. Б. Бухбергера, Дж. Коллинза, Р.Лооса. — М.: Мир, 1986, С. 23−65.

11. Важенин Ю. М. Алгоритмические проблемы и иерархии языков первого порядка // Алгебра и логика, 1987, Т. 26, N 4, С. 419 434.

12. Важенин Ю. М. Критические теории // Сиб. мат. журн., 1988, Т. 29, N 1, С. 23−31.

13. Гварамия A.A., Глухов М. М. Об алгоритмических проблемах для некоторых классов квазигрупп // ДАН СССР, 1967, Т. 177, N 1, С. 14−16.

14. Гварамия A.A., Глухов М. М. Решение основных алгоритмических проблем в некоторых классах квазигрупп с тождествами // Сиб. мат. журн., 1969, Т. 10, N 2, С. 297−317.

15. Глухов М. М. О свободном произведении луп с конечным числом образующих. — В сб.: Математические исследования. — Кишинев, 1967, Т. 2, вып. 2, С. 84−95.

16. Глухов М. М. О свободных произведениях и алгоритмических проблемах в Я-многообразиях универсальных алгебр // ДАН СССР, 1970, Т. 193, N 3, С. 514−517.

17. Глухов М. М. Ä—многообразия квазигрупп и луп. — В сб.: Вопросы теории квазигрупп и луп. — Кишинев, 1970, С. 37−47.

18. Глухов М. М. Свободные разложения и алгоритмические проблемы в Ä—многообразиях универсальных алгебр // Мат. сб., 1971, Т. 85, вып. 3, С. 307−338.

19. Глухов М. М. О некоторых алгоритмических проблемах и свободных произведениях в Я-многообразиях линейных П-алгебр // Фундам. и прикл. матем., 1997, Т. 3, N 2, С. 373−397.

20. Глухов М. М., Мухин А. И. Об уравнениях над квазигруппами // Сиб. мат. журн., 1977, Т. 18, N 4, С. 755−764.

21. Гретцер Г. Общая теория решеток. — М.: Мир, 1982. — 456 с.

22. Ершов Ю. Л. Неразрешимость теорий симметрических и простых конечных групп // ДАН СССР, 1964, Т. 158, N 4, С. 777−779.

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

24. Ершов Ю. Л., Лавров И. А., Тайманов А. Д., Тайцлин М. А. Элементарные теории // Успехи мат. наук, 1965, Т. 20, N 4, С. 37−108.

25. Ершов Ю. Л., Палютин Е. А. Математическая логика. — М.: Наука, 1979. — 320 с.

26. Замятин А. П. Многообразия с ограничениями на решетку конг-руенций. — Свердловск: УрГУ, 1987. — 92 с.

27. Клини С. Математическая логика. — М.: Мир, 1973. — 480 с.

28. Кон П. Универсальная алгебра. — М.: Мир, 1968. — 352 с.

29. Куратовский К., Мостовский А. Теория множеств. — М.: Мир, 1970. — 416 с.

30. Курош А. Г. Теория групп. — 2-е изд. — М.: Гостехиздат, 1953.468 с.

31. Курош А. Г. Лекции по общей алгебре. — М.: Наука, 1973. — 400 с.

32. Магнус В., Каррас А., Солитер Д. Комбинаторная теория групп. Представление групп в терминах образующих и соотношений. — М.: Наука, 1974. — 456 с.

33. Мальцев А. И. Неразрешимость элементарной теории конечных групп // ДАН СССР, 1961, Т. 138, N 4, С. 771−774.

34. Мальцев А. И. Аксиоматизируемые классы локально свободных алгебр некоторых типов // Сиб. мат. журн., 1962, Т. З, N 5, С. 729−743.

35. Мальцев А. И. Алгоритмы и рекурсивные функции. — М.: Наука, 1965. — 392 с.

36. Мальцев А. И. Тождественные соотношения на многообразиях квазигрупп // Мат. сб., 1966, Т. 69, N 1, С. 3−12.

37. Мальцев А. И. Алгебраические системы. — М.: Наука, 1970. — 392 с.

38. Марков A.A. Теория алгорифмов // Труды Матем. ин-та АН СССР им. В. А. Стеклова, Т. 42, М.-Л., 1954.

39. Мендельсон Э.

Введение

в математическую логику. — М.: Наука, 1971. — 320 с.

40. Мухин А. И. Уравнения с несколькими неизвестными в конечно-определенных квазигруппах // 16-я Всесоюз. алгебраич. конф. Тезисы докл., Ленинград, 1981, Ч. 2, С. 94−95.

41. Смирнов Д. М. Решетки многообразий и свободные алгебры // Сиб. мат. журн., 1969, Т. 10, N 5, С. 1144−1160.

42. Смирнов Д. М. Канторовы алгебры с одним порождающим. I // Алгебра и логика, 1971, Т. 10, N 1, С. 61−75.

43. Смирнов Д. М. Базисы и автоморфизмы свободных канторовых алгебр конечного ранга // Алгебра и логика, 1974, Т. 13, N 1, С. 35−62.

44. Смирнов Д. М. Многообразия алгебр. — Новосибирск: Наука, 1992. — 205 с.

45. Смирнов Д. М. О представимости многообразий Кантора // Алгебра и логика, 1995, Т. 34, N 4, С. 464−471.

46. Смирнов Д. М. О размерностях многообразий Кантора и Поста // Алгебра и логика, 1996, Т. 35, N 3, С. 359−369.

47. Справочная книга по математической логике: в 4-х частях / Под ред. Дж. Барвайса. — М.: Наука, 1982.

48. Тайцлин М. А. Еще несколько примеров неразрешимых теорий // Алгебра и логика, 1967, Т. 6, N 3, С. 105−110.

49. Халезов Е. А. Автоморфизмы примитивных квазигрупп // Мат. сб., 1961, Т. 53, N 3, С. 329−342.

50. Хигман Г. Конечно определенные бесконечные простые группы. — В сб.: Разрешимые и простые бесконечные группы. Математика, вып. 21. — М.: Мир, 1981, С. 87−147.

51. Шенфилд Дж. Математическая логика. — М.: Мир, 1975. — 528 с.

52. Birkhoff G. On the structure of abstract algebras // Proc. Cambridge Phil. Soc., 1935, V. 31, P. 433−454.

53. Bruck R. A survey of binary systems. — Berlin New York, 1958.

54. Burris S., Sankappanavar H.P. A course in universal algebra. — N.Y., 1981.

55. Burris S., McKenzie R. Decidability and Boolean Representations // Memoirs Amer. Math. Soc., 1981, V. 32, N 246, P. 1−106.

56. Church A., Rosser J.B. Some properties of conversion // Trans. Amer. Math. Soc., 1936, V. 39, P. 472−482.

57. Denes J., Keedwell A.D. Latin squares and their applications. — Budapest: Academiai Kiado, 1974. — 547 p.

58. Dershowitz N., Manna Z. Proving termination with multiset ordering // Commun. ACM., 1979, V. 22, N 8, P. 465−476.

59. Evans T. The word problem for abstract algebras //J. London Math. Soc, 1951, V. 26, N 1, P. 64−71.

60. Evans Т. On multiplicative systems defined by generators and relations. I. Normal form theorems // Proc. Cambridge Phil. Soc., 1951, V. 47, N 4, P. 637−645.

61. Evans T. The isomorphism problem for some classes of multiplicative systems // Trans. Amer. Math. Soc., 1963, V. 109, N 2, P. 303−312.

62. Evans T. Some solvable word problems // In: Word problems II (S.I. Adian, W.W. Boone, G. Higman, eds.). — Amsterdam, 1980. —P. 87−100.

63. Huet G. Confluent reductions: abstract properties and applications to term rewriting systems //J. of ACM, 1980, V. 27, N 4, P. 797−821.

64. Jonsson В., Tarski A. On two properties of free algebras // Math. Scand., 1961, V. 9, P. 95−101.

65. McKenzie R., Valeriote M. The structure of decidable locally finite varieties // Progress in Mathematics, Birkhauser-Boston, 1989, V. 79, P. 1−212.

66. Knuth D., Bendix P. Simple word problems in universal algebras // In: Computational Problems in Abstract Algebras, ed. J. Leech, Pergammon Press, 1970. — P. 263−297.

67. Newman M.N.A. On theories with a combinatorial definition of «equivalence» // Ann. of Math., 1942, V. 43, N 2, P. 223−243.

68. Pedersen J. The word problem in absorbing varieties // Houston J. of Math, 1985, V. 11, N 4, P. 575−590.

69. Peterson G. E, Stickel M.E. Complete sets of reductions for some equational theories // J. of ACM, 1981, V. 28, N 2, P. 233−264.

70. Sade A. Quasigroupes parastrophiques. Expressions et identites // Math. Nachr., 1959, V. 20, N 1−2, P. 73−106.

71. Stein S.K. On the foundations of quasigroups // Trans. Amer. Math. Soc., 1957, V. 85, P. 228−256.

72. Swierczkowski S. On isomorphic free algebras // Fund. Math., 1961, V. 50, N 1, P. 35−44.ПУБЛИКАЦИИ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ:

73. Шабунин Л. В. Разрешимость элементарных теорий конечно-определенных группоидов // Деп. ВИНИТИ, 1986, N 8869-В86, С. 119.

74. Shabunin L.V. Decidability of 3-theories of finitely presented groupoids // Тезисы докл. 8-го Международного конгресса по логике, методологии и философии науки, Москва, 1987, Т. 1, С. 170— 171.

75. Шабунин Л. В. Об одном сведении проблемы разрешимости теорий некоторых конечно-определенных П-алгебр // Деп. ВИНИТИ, 1988, N 74-В88, С. 1−21.

76. Шабунин Л. В. О разрешимости теорий некоторых неассоциативных конечно-определенных алгебр // Тезисы докл. 9-й Всесоюзн. конф. по матем. логике, Ленинград, 27−29 сентября 1988, С. 177.

77. Шабунин Л. В. Разрешимость элементарных теорий конечно-определенных алгебр многообразия алгебр, заданного пустой системой тождеств // Мат. заметки, 1989, Т. 45, вып. 5, С. 93−102.

78. Шабунин Л. В. Разрешимость элементарной теории конечно-определенной квазигруппы // Мат. заметки, 1990, Т. 47, N 4, С. 138−146.

79. Шабунин Л. В. Разрешимость теорий конечно-определенных квазигрупп в некоторых классах квазигрупп с тождествами // Тезисы докл. 10-й Всесоюзн. конф. по матем. логике, Алма-Ата, 1−3 ноября 1990, С. 165.

80. Шабунин Л. В. Разрешимость теорий конечно-определенных квазигрупп из Д-многообразий квазигрупп // Сиб. мат. журн, 1991, Т. 32, N 3, С. 201−211.

81. Шабунин Л. В. Разрешимость элементарных теорий некоторых конечно-определенных алгебр // Алгебра и логика, 1991, Т. 30, N 4, С. 457−476.

82. Шабунин Л. В. Об элементарных теориях конечно-определенных луп со свойством обратимости // Дискретная математика, 1991, Т. 3, 1 4, С. 79−90.

83. Шабунин Л. В. Разрешимость теорий некоторых бесконечных конечно-определенных квазигрупп // Изв. вузов. Матем, 1992. N 3, С. 74−79.

84. Шабунин Л. В. Об элементарных теориях^{-многообразий} луп с условием ~~1х = х// Тезисы сообщений 11-й Межреспубл. конф. по матем. логике, Казань, 6−8 октября 1992, С. 154.

85. Шабунин Л. В. О числе Д-многообразий луп с условием ~1х = х~1 // Деп. ВИНИТИ, 1993, N 916-В93, С. 1−26.

86. Шабунин Л. В. О проблеме элементарной эквивалентности конечно-определенных алгебр многообразия алгебр, заданного пустой системой тождеств // Деп. ВИНИТИ, 1993, N 1595-В93, С. 1−6.

87. Шабунин JI.В. Разрешимость одного фрагмента элементарной теории свободной универсальной алгебры с дополнительным предикатом и эквивалентностью // Деп. ВИНИТИ, 1994, N 2920-В94, С. 1−9.

88. Шабунин Л. В. Теоремы о нормальной форме для Я-многообразий луп // Деп. ВИНИТИ, 1994, N 2921-В94, С. 1−23.

89. Шабунин Л. В. Полные системы тождеств для Я-многообразий луп с условием ~lx = х~1 // Деп. ВИНИТИ, 1995, N 286-В95, С. 1−72.

90. Шабунин Л. В. О Я-многообразиях квазигрупп и луп // Тезисы Второй Международной конф. «Математические алгоритмы» (Нижний Новгород, 26 июня 1 июля 1995 г.). — Нижний Новгород: Изд-во Нижегородского ун-та, 1995, С. 60.

91. Шабунин Л. В. Элементарные теории конечно-определенных квазигрупп //В сб.: Актуальные задачи математики и механики / Чуваш, ун-т. Чебоксары, 1995. С. 131−133.

92. Шабунин Л. В. Неразрешимость теории бесконечной конечно-определенной квазигруппы с дополнительным предикатом // Деп. ВИНИТИ, 1996, N 1892-В96, С. 1−4.

93. Шабунин Л. В. О конечно-определенных и свободных алгебрах многообразий Кантора // Сиб. мат. журн., 1997, Т. 38, N 2, С. 450 462.

94. Шабунин JI.В. О свободных алгебрах многообразия квазигрупп и многообразий Кантора // Естественные науки: сегодня и завтра: Тезисы докладов юбилейной итоговой научной конференции. — Чебоксары: Изд-во Чуваш, гос. ун-та, 1997, С. 100.

95. Шабунин Л. В. Об элементарной эквивалентности свободных алгебр многообразий Кантора // Алгебра и логика, 1999, Т. 38, N 2, С. 228−248.

96. Шабунин Л. В. Теорема вложения для многообразий Кантора // Тезисы докладов на Международной конф. по математической логике (Новосибирск, 10−15 августа 1999 г.) — Новосибирск: Ин-т дискретной математики и информатики, 1999, ISBN 5−88 119−119−6, С. 64−66.

97. Шабунин Л. В. Неразрешимость элементарных теорий многообразий Кантора // Деп. ВИНИТИ, 1999, N 2807-В99, С. 1−18.

98. Шабунин Л. В. Парастрофные^{-многообразия} квазигрупп // Деп. ВИНИТИ, 1999, N 3095-В99, С. 1−48.