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

На нравах рукописи

ПОПОВ Владимир Юрьевич

КРИТИЧЕСКИЕ ТЕОРИИ МНОГООБРАЗИЙ КОЛЕЦ

01.01.06 - математическая логика, алгебра и теория чисел

АВТОРЕФЕРАТ диссертации на соискание ученой степени Кандидата физико-математических наук

Екатеринбург-1065

Работа выполнена на кафедро алгебры и геометрии УральскоГо гьеударетпешюго университета в городе Екатеринбурге.

Научный рукоподитель:

до«1« р ф из и ко- м атематн чсск их «пук, профессор Ю.М.Важенин

Официальные оппоненты:

доктор физико-матсматическИх наук, профессор О.А.Романьков кандидат фишко-математичсскНХ наук, доненI Н. Л.Хмельницкий

МедуЖая организация:

Новосибирский технический университет

Защита диссертации состоится 30 1906 года п 1б часов

На заседании диссертационного совета К 002.07.02 в Институте математики н механики УрО РАН но адресу: 620219,г.Екатеринбург,ул.Софьи Ковалевской, 10.

Института ма-

' А.С.Кондрптьей

С диссертацией можно ознакомиться в библиотеке тематики и механики УрО РАН.

Автореферат разослан Р&Я&рЯ 1Шг

Ученый секретарь диссертационного сонета д.ф,-М,п.,профессор

Попросы разрешимости теорий первого порядка классов алгебраических систем иаходнтсн п центра внимании современной математической логики. Их общаи постановка посходит к А. Тьюрингу, Э. Посту, Л. Черчу, Л. Тарскому, А.И, Мальцеву,

Первые результаты по разрешимости элементарных теорий рм» личных классов колец были получены А. Тарским [1] и Р. Робинсо-ком [2]. И частности, была доказана неразрешимость элементарных теорий ассоциативных колец, ассоциативных коммутативных колец Ii колец с единицей. Активное изучений укачанных элементарных теорий началось в первой половина 60-х годов, И 1061 году А,И. Мальцевым [3] была доказана неразрешимость элементарной теории многообразии колец Ли простой характеристики р, такой что р ф 2. U.A. Лавров [4] в J062 году доказал неразрешимость элементарных теорий свободного кольца Ли, свободного i-нильпотентного коль* ца, свободного <-нилыютентного коммутативного кольца, свобод* ного (-нильпотеитиого антикоммутатнвного кольца при t > 3, Им же в 1063 [б] году была доказана неразрешимость элементарной тео* рии свободного «-разрешимого кольца при н > 2. Н 1ÖÖÜ гаду М.А. Тайцлиным [0] была доказана неразрешимость элементарной теории многообразия коммутативных 3-нильпотентных колец характеристики р, р ф 2. Дополняя результаты М.А, Тайцдина и А,И. Мальцева, Ю.Л. Ершов [7] н 1063 году доказал неразрешимость эле* ментарной теории многообразии коммутативных /-иильпотентных колец простой характеристики при / > 3 и многообразия колец Ли характеристики 2. П 1976 году А,П. Замятин в работе [8J получил полное описание многообразий ассоциативных колец с разрешимой элементарной теорией, Среди классов с разрешимой элементарной теорией следует отметить свободные 3-нильпотентиые алгебры над полем с разрешимой элементарной теорией (М А- Тайцлин, [9,10)) и свободные 3-нилыютентиые ассоциативные алгебры над полем в разреншмой элементарной теорией (Ж,А. Алмагамбето», (UJ), Неразрешимость элементарных теорий большинстве интересных классов колец, а также важность ряда ограниченных теорий с точки зрения, алгебры, сделала естественным изучение разрешимости ограни*„'

ченных теорий колец. Э±а задача лежит в русле общей Программы исследований разрешимости теорий первого порядка, сформулированной Л.И. Мальцевым [12]: для наиболее важных классов К и Наиболее интересных языков Ь выяснить разрешимость теории ЬК.

Наиболее активно изучались квазиэквацнональные теории различных классов колец Поскольку их разрешимость непосредственно связана с разрешимостью классической алгоритмической проблемы равенства. А.И. Ширшов [13] доказал разрешимость квазИэква-циональных теорий многообразий коммутативных и антикоМмутативных алгебр над конструктивным полеМ; Л.И. Жуков В работе [14] доказал разрешимость проблемы равенства в многообразии всех алгебр над конструктивным полем. Отвечая на вопрос А.И. Ширшова, поставленный в [15], Л.А. Бокуть [16] доказал неразрешимость квазиэквациональной теории многообразия алгебр Ли. АольшаЯ работа по описанию многообразий лиевых и ассоциативных алгебр с разрешимой квазиэквациональной теорией проведена О.Г. Харлампович и М.Б. Сапиром [см.17]. Неразрешимость проблемы равенства в многообразиях йордановых и правоальтернативных колец доказана в [18] У.У. Умирбаевым. Им же в [19,20,21] доказана неразрешимость проблемы равенства в многообразии центрально-метабелевых алгебр Ли. Разрешимость квазиэквациональной теории изучалась не только для многообразий колец, но и для некоторых других интересных классов колец: свободных Колец, конечных колец, нилЬпотентных колец, колец с одним определяющим соотношением [см.22]. Ряд интересных результатов получен И по разрешимости других ограниченных теорий колец. Так из отрицательного решения Ю.В. МатиясевичеМ в [23] 10-й проблемы Гильберта непосредственно следует неразрешимость диофантовой теории кольца Целых чисел. Обилие результатов по разрешимости ограниченных теорий вызвало необходимость описания разрешимых теорий наиболее важных классов колец. '

10.М. Ёажеиин [24] предложил удобный метод описания разрешимых теорий классов алгебраических систем на языке критических теорий. Пусть £ - элементарный язык некоторой конечной ёигнату-

ры <т, т.е. совокупность исех формул логики первого порядка этой сигнатуры, записанных в преиексной нормальной форме. Множества L С £ будем называть языками. Для класса алгебраических систем К. сигнатуры а и языка L через LK обозначим совокупность всех предложений из L, истинных на 1С, и назовем ее ¿—теорией или, просто, теорией класса 1С. Пусть Я— некоторое семейство языков, упорядоченное включением и покрывающее весь элементарный язык С- Подобные семейства будем называть иерархиями языков. Иерархия языков Н определяет для данного класса К иерархию теорий Н)С = {LfC | L € II]. Теория LK, называется критической для данной иерархии Н, если в иерархии IIK, она является минимальной неразрешимой теорией. Множество критических теорий данного класса А называется границей разрешимости и обозначается черед В(Э£). Если иерархия II рекурсивна, т.е. рекурсивно отношение включения на ней, и удовлетворяет условию минимальности, то, очевидно, для языка L Е Н теория LK, разрешима тогда и только тогда, когда она не включает в себя ни одной критической теории. Поэтому для таких иерархий описание критических теорий данного класса автоматически дает описание всех разрешимых теорий. . Ниже мы определим ряд иерархий, предложенных Ю.М.Важениным в [24]. Обозначим через {V, 3}а множество всех альтернирующих слов из V, В, включая пустое слово. Если х— некоторый символ, то х1 = х и х° - пустой символ. Пусть г» < ш\ в = -пА V; Ив = {Q¡x~ Qiy£ | / < п}. Переменной иерархией назовем следующее упорядоченное включением семейство языков:

К {R0 | n < ш}.

Пусть

Сх...Ск-Л" Vp ^ {Q^-. Q^y Д -."»«ку I

ísl jal

Qi- Qi € {V,a}",s3n d ^ p,sgn S n.egn < m,

— всевозможные наборы перемеНШх; I < к или (/ = II = СО;ту е {0,1};с/,с< € Ц

— атомные формулы ). 27-," л" V ^ У С\ ■■■Ск~'т Л" V, •

к£и>

Схемно-альтерНАтивноЙ иерархией называете^ упорядоченная включением совокупность

л"у ^ у с1...ск-.т'л"

ЗА {аГ-1М Л" \/р,С1.:.С*-<т Л" Ур |

с1...с^е{У,з}о(т1«)ре{0)1}}. ;

]

Обозначим Через 3, А, VА следу!о1цМе Совокупности яэыкой

I •

I

I

/Ы{йЬтл'у' |т,<,8б{0,1}}, |

! •

УА = {ХПУ\Х еУ,У <=А}.

Эти Иерархии будем называть схемной, аль±ернатйвной Я переменно-альтернативной иерархиями, соотйетс+вешго. |3 работе [24] доказано, что иерархии V, А, Б, УА, вА рекурсивны и удовлетворяют условию минимальности. Наиболее сложная из определенных выше иерархий иерархия БА достаточно богата. Она содержит такие известные языки, как позитивный, диофантов, универсальный и эквацйональный,

б

Первые результаты по описанию границ разрешимости были пр-лученм Ю.М.Важениным в работах [24], [25]. Ряд интересных результатов опубликован в работах [26-30].

Апробация. Результаты диссертации были представлены на X (Алма-Ата,1990), XI (Казань,1992) Всесоюзных конференциях по математической логике, Советско-французском коллоквиуме по теории моделей (Караганда,1990), I (Ноьосибирск,1989), II (Варна-* ул,1901), III (Красноярск,1093) Международных конференциях ЯО алгебре, семинарах" Алгебра и логика"," Алгебраические системы", "Алгебра, логика, алгоритмы". Результаты диссертации отражены в публикациях автора [37-48]. При этом в работе [37] автору принадлежит утверждение о нилыютентных кольцах, работа [38] написана В нераздельном соавторстве, а в работе [41] автору принадлежит утверждение, касающееся альтернативных колец.

Диссертация состоит из введения, двух глав и содержит 4 теоремы. Общий объем диссертации 113 страниц. Библиография содержит 48 наименований.

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

Содержание диссертации. В главе I рассматривается разрешимость эквацнональных теорий многообразий колец. При изучении критических теорий многообразий колец эквациональные теории Имеют очень важное значение, поскольку для любого многообразия колец ЗС теорий 3-1А чЗ£ разрешима, и, следовательно, если теория ьХ неразрешима, то она включает эквациональную теорию, Заметим, что если эквациональная теория "многообразия Л неразрешима, то автоматически В(ЗС) = {V}. Кроме того, исследование эквацнональных теорий является классической алгоритмической про* .; блемой, представляющей самостоятельный интерес. А.И. МкЛЬЦЗВ ,

в работе [31] построил.конечио базируемое многообразие квазигрупп с неразрешимой эквацнональной теорией И поставил опубликованный в сборнике [32] вопрос о существовании конечно базируемых Многообразий полугрупп, групп И колец с неразрешимой эквацйо-нальной теорией. Положительный ответ на этот вопрос для полугрупп получен в [33], а для групп - в [34]. Активные исследования кьазиэквациональных теорий коммутативных и метабелевых колец .[13, 18-21], а также указанный выше вопрос, делают интересным следующий результат.

ТЕОРЕМА 1. Существуют конечно базируемые многообразия метабелевых и коммутативных колец с неразрешимой эквациональ-1ЮЙ теорией.

Сложность описания многообразий колец с разрешимой эквацио-нальноЙ теорией иллюстрирует следующая

ТЕОРЕМА 2. Существует последовательность Конечно базируемых многообразий неассоцнативных колец

^с^с^сОЗзс...

*акая, что для всех I эквациоиальная теорий 21,- неразрешима, а ■ ЭКВациональная теория разрешима.

Разрешимость эквацнональной теории некоторого Конечно базируемого Многообразия колец гаг{£} эквивалентна существованию алгоритма, определяющего по произвольному предложению ф вида

Чх}{х) гг 0 ( ; !

йьШолнимость следующего соотношения:

£ Н ф. \

!

Параллельно с этой задачей обычно рассматривается проблема выпощйМоети тождества: I

Существует ли алгоритм, выясняющий по фиксированному то-э)сдсству ф и произвольной конечной системе тождеств выпол» нимостъ соотношения И Ь ф.

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

ЕМ

Илй нет. Там же отмечено, что аналогичное утверждение справедлив Во и для ряда полугрупповых тождеств. В [36] проблема выводимо* . стм тождеств рассматривалась для групп. Следующее Предложение дает прмер кольцевого тождества с этим условием.

ПРЕДЛОЖЕНИЕ. Не существует алгоритма, определяющей По Произвольному Конечно базируемому Многообразию КолеЦ, удовлетворяет оно тождеству (ху)(я1)=0 или Яе±.

Во второй главе исследуются критические теорий многообразий над-коммутативно-ассоциативных колец и многообразий ииль* потентных колец. В работах [24,28] ГО.М. Важенин описал критические теорий многообразия всех колец, многообразия коммутативных колец, многообразия ассоциативных колец. Следующая теорема дает характеризацию типов критйЧескйх теорий для многообразий колец, включающих многообразие Коммутативных ассоциативных колец. Кроме того, она дает два новых примера границ разрешимости для многообразий колец.

ТЕОРЕМА 3. Дли любого многообразия X Э т П <£ спра-' веаливо соотношение 6 {{V), {УЗ, У-^У), {УЗ, ЗУ-Л/}}, и при этом все три случая реализуются. Однако, не существует алгоритма, определяющего по произвольному многообразию X его границу разрешимости.

Р теореме 4 описываются границу разрешимости для наиболее цнтересных многообразий нн^ьпотентных колец: многообразияvlfy всех i-ицдмютентных колец и многообразия ^П? 1-нильпотеитцых колец характеристики два.

ТЕОРЕМА 4. Справедливы следующие два равенства:

В(9Ъ) = {V3, ЗУ-. Л V}, = {3V-1 Л V}.

Литератур»

1. ATareki, Fl.Robinson, A.Mostoweki, Undecidable theory, 1953.

2. R.M.Robinaon, Undecidable rings, Trans. Amer. Math. Soc. 70(1961), 137-159

3. А.И.Мальцев, Эффективная неотделимость множества тождественно истинных И множества конечно опровержимых формул Некоторых элементарных теорий, ДАН, Т.139(1901), 802-805.

4. И.А.Лавров, Неразрешимость элементарных теорий некоторых колец, Алгебра и логика.- 1962.- Т.1.- N3.- С.39-45.

5. Ершов Ю Л..Лавров И.А.,Тайманов А.Д.,Тайцлин М.А, Элементарные теории. Успеха мат. наук.- 1965 - Т.2.- Nb-- С.37-108,

6. М.А.Тайцлин, Неразрешимость элементарных теорий некоторых классов конечных коммутативных ассоциативных колец, Алгебр* и логика Т.2, N3(1963), 29-51.

7. Ю.Л.Ершов, М.А.Тайцлин, Неразрешимость некоторых теорий, Алгебра и логика Т.З, N5(1963), 37-42.

ê. A.P.Zanyatin, Varietiea of aseociatlve ringe whose elementary theory U decidable, DAN SSSR, T.229(1976), N2, 996-999.

9. М.А.Тайцлин, Разрешимость некоторых элементарных теорий. Алгебра и логика,- 1904.- Т.З.- М,- С.б-12.

10. М.А.Тайцлин, Об элементарных теориях свободных нильно-тентных алгебр. Алгебра и логика - "1964.- Т.З.- N5-6 - С.57-63.

11. Ж.А.Алмагамбетов. Разрешимость элементарных теорий некоторых классов нильпотеНтцых алгебр. Алгебра и логика - 196В<-Т.4.- W6.- С.5-14.

12. А.И.Мальцев, О Некоторых пограничных вопроса* МГебрЫ и математической логики, Между иарЬдНЫЙ конгресс матеМатйкьй) М., 1666, 217-231.

13. А.И.Ширшов, Некоторые алгоритмические проблемы ДЛИ i» алгебр, Сиб. мат. жури., 3, N1 (1062), 132-137.

14. А.И. Жуков, приведённые системы определяющих соотрошй-ИИЙ й нейссо;1иативн1йх алгебрах , МаТем. сб., 27, N2 (I960), 267-280.

16. Днестровская тетрадь. 2-е иэд, Новосибирск. 1976.

16. Л.А.Бокуть. Неразрешимость проблемы равенства и подалгебры конечно определенных алгебр Ли. Изв. АН СССР. сер. матвм^ Т.36.- N6.- 1972,- С.1173-1219.

17. O.G.Kharlampovich. M.V.Sapir. Algorithmic problem« 1й •varieties. 1996.

18. У.У.Умирбаев. Проблема равенства для ЙордаНойЫХ n Нраво-альтернативных алгебр. Некоторые Проблемы И задачи аНаЛЙза И алгебры. ИГУ. 1985. С.120-127.

19. У.У.Умирбаев, О Метабелевых бйнйрНс)-ЛИёВЫ* алгебра*, Алгебра и логика, 23, N1 (1984), 220-22?,

20. У.У.Умирбаев, Проблема равенства для метабелевых пра-воальтериативных алгебр, в сб, -Теоретико-модельная алгебра-, Алма-Ата, 1989, 130-139.

21. Ю.А.Вахтурин, Об аппроксйМйцйй алгебр Ли, Мат. заметки, 12, N6 (1972), 713-716.

22. Л.А.Вокуть Алгоритмические Ирьблемы и теоремы вложения: некоторые открытые вопросы дли колец, груш! и полугрупп. Иэв, ВУЗов. Математика.- N11.- 1982.- С.З-.11.

23. Ю.В, Матиисевич, Диофантовость перечислимм* множеств, ДАН СССР.- 1970,- Т.267.- М2,- С.763-766.

24. Ю.М.Вйжёнин, Алгоритмические проблемы и иерархии языков первого порядка, Алгебра и логика, 26, NA (1987),41fli-434.

26. Ю.М.Нажении, Критические теории некоторых классов неассоциативных колец, Алгебра и логика, 28, Nb (1989),

26. Ю.М.Важенин, Критические теории, Сиб. мат. журн.- 1988.-Т.29.-ЛЛ.-С.23-31.,

27, ЮМНаженцн, О границах, разрешимости матричных колец. Вторые математические чтения памяти М.Я.Суслина. Сборник тезисов. Саратов. 1991. С.83.

28. ЮМ.Важенин, Проблема равенства в неассоциатлвпых кольцах, Алгебра и логика, 29, N6 (1990).

20. Ю М.Важенин, А.Ю.Глухих, О критических теориях конечно определенных колец. Вторые математические чтения памяти М.Я.Суслина. Сборник тезисов. Саратов. 1091. С.84.

30. Ю М.Важенин, В.А.Тюков, О критических теориях свободных ассоциативных колец с единицей. Вторые математические чтения памяти М.Я.Суслина. Сборник тезисов. Саратов. 1091. С.85.

31. А.И.Мальцев, Тождественные соотношения на многообразиях квазигрупп, Матем. сб., 60, N1 (10ti6), 3-12.

32. Коуровскап тетрадь, 10-е изд., Новосибирск, 1986.

33. В.Л.Мурский, Несколько примеров многообразий полугрупп, Магем. заметки, 3, N 6 (1968), 663-670.

34. Ю.Г.Клейман, О юждествах в группах, Труды Моск. мат. о-ва, 44 (1082), 62-108.

35. В.Л.Мурский, Нераспознаваемые свойства конечных систем тождественных соотношений, ДАН СССР, 196, iV3(1971), 520-522.

36. Ю.Г.Клейман, Тождества н некоторые алгоритмические проблемы в группах, ДАН СССР, Т.244, 1979, N4, 115-119.

Список публикаций по теме диссертации.

37. Важенин Ю.М,Попов В.Ю.,Шибаков А.Ю- Критические теории свободных нильпотентных колец и кольца целых чисел с делимостью // Тезисы. Новосибирск. 1989.

38. Ю.М.Важенин, В.Ю.Попов, Критические теории свободных нильпотентных колец некоторых типов, Изв. вузов, Математики, 1991, N3, 74-76.

30. В-Ю-Нонов, Разрешимые теории йордановых колец, Тезисы X Всесоюзной конференции по математической логике, Алма-Ата, 1990, 134.

40. to.to.Попов, Разрешимое теорий альтерпАтйЫМх кЬЛец, 'fe-dticfci Советско-французского коллоквиума по теорий МодеЛеЙ, kd-рагаПДа, 1990, 41.

41. Ю.М.Важенин, В.Ю.Попов, Границы разрешимости многообразий конечных полугрупп, групп и колец. Третья международная конференция Но алгебре. Сборник тезисов. Красноярск. 1993. С.61. : '

42. В.Ю.Попов, Об эквациональных ±еорййх метабелвш* и коммутативных колец. Вторые МаТеМатйЧескИе чтения НаМйтй М.Я.Суслйна. Сборник тезисов. Саратов. 1991. С.91.

43. В.Ю.Попов, О рекурсивНостИ экйациональных теорий Многообразий Колец. Международная конференция по алгебре НосйяиШЙ-ная памяти А.М.Ширшова. Сборник тезисов. Барнаул. 1992. С.113.

44. В.Ю.Попов, О критических теориях над-КоМмутативно-ассо-ЦНатйВных многообразий Колец. Одиннадцатая меж республик АЙ-Ская конференция по математической логике. Сборник тезйсой. fcd-заны 1991. С.87.

45. В.Ю.Попов, О {фоблеМе ЙЫйодИМосШ ТоАдёстй длЯ колеЦ. Третья международная коМфереШШ по алгебре. СборЙЙк *ёзйсаВ. Красноярск. 1993. С.272.

46. В.Ю.Попов, Критические 1еорйи йад-комму1атпвно-аеемШ-тийных многообразий колец. Снб. мат. журн. 1995. Т.Зб.

4?. В.Ю.Попой, ЭкйационаЛЬнь<е теории Многообразий метабёлё-оых и коммутативных колец. Алгебра Й логика, 34, N3 (1996),

48. V.U.Popov, Critical thiotiesof varieties of nilpotent tings, leittcfcti Нижний Новгород, 1996,