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

ВВЕДЕНИЕ.

ГЛАВА 1. Свойство Чёрча-Россера и элементарные теории.

§ 1. Основные понятия и обозначения.

§ 2. Полные системы тождеств.

§ 3. Фактор-алгебры термов с предикатом нормальной формы

§ 4. Многообразия с пустой системой тождеств.

ГЛАВА 2. Дх-многообразия квазигрупп.

§ 5. Определения и леммы.

§ 6. Полные системы тождеств для с- и ¿-подмногообразий многообразия Т-^1.

§ 7. Полные системы тождеств для ¿¿-подмногообразий многообразий В1\ В2\ ВЪ1 и В

§ 8. Полные системы тождеств для с- и ¿-подмногообразий многообразий А11, Л21, АЗ1, А41 и А51.

§ 9. Полные системы тождеств для ¿-подмногообразий многообразий А1В, А2В и АЗВ.

§ 10. Теорема о числе /^-многообразий.

§ 11. Конечно определенные квазигруппы

§ 12. Свободные квазигруппы

§ 13. Дополнительные примеры

§ 14. Результаты о неразрешимости.

ГЛАВА 3. /^-многообразия луп.

§ 15. Определения и леммы.

§ 16. Полные системы тождеств для с- и ¿-подмногообразий многообразия У02.

§ 17. Полные системы тождеств для с- и ¿-подмногообразий многообразия АЗ2.

§ 18. Полные системы тождеств для многообразий AI2, А22, a42 и аъ2.

§ 19. Теорема о числе ^-многообразий.

§ 20. Конечно определенные лупы.

§ 21. Свободные лупы.

ГЛАВА 4. Лз-многообразия луп.

§ 22. Определения и леммы.

§ 23. с- и ¿-подмногообразия многообразия V^3.

§ 24. с- и ¿¿-подмногообразия многообразий Bl3-B8, Ml, М2,

§ 25. с- и ¿/-подмногообразия многообразий A33, N1, N2, CIP

§ 26. Первая теорема о числе /^-многообразий

§ 27. Полные системы тождеств для с- и ¿¿-подмногообразий многообразия Vq

§ 28. Полные системы тождеств для с- и ¿¿-подмногообразий многообразия ВI3.

§ 29. Полные системы тождеств для с- и ¿¿-подмногообразий многообразия J323.

§ 30. Полные системы тождеств для с- и ¿¿-подмногообразий многообразия ВЗ3.

§ 31. Полные системы тождеств для с- и ¿¿-подмногообразий многообразий В43 и ВЪ.

§ 32. Полные системы тождеств для с- и ¿¿-подмногообразий многообразия В

§ 33. Полные системы тождеств для с- и ¿¿-подмногообразий многообразий В7 и В8.

§ 34. Полные системы тождеств для с- и ¿¿-подмногообразий многообразий Ml, М2 и IP.

§ 35. Полные системы то?кдеств для с- и ¿¿-подмногообразий многообразия ЛЗ3.

§ 36. Полные системы тождеств для с- и ¿¿-подмногообразий многообразий N1, N2 и С1Р

§ 37. Полные системы тождеств для многообразий А13, А23,

Л43 и Л

§ 38. Вторая теорема о числе Лз-многообразий.

§ 39. Конечно определенные лупы.

§ 40. Свободные лупы.

ГЛАВА 5. Многообразия Кантора.

§ 41. Многообразия Кантора СТО;П. Вполне замкнутые представления

§ 42. Конечно определенные алгебры в многообразии Ст,п

§ 43. Свободные алгебры в многообразии Ст^п.

§ 44. Теорема вложения.

§ 45. Неразрешимость теории многообразия Ст^п.

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, С. 419434.

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 identités // 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, С. 450462.

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

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

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

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

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