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

Введение

ГЛАВА 1. ГРУППЫ И МОНОИДЫ ЦЕЛОЧИСЛЕННЫХ

МАТРИЦ.

§1. Формулировка результатов и предварительные сведения

§2. О границе разрешимости полной линейной группы

§3. О границе разрешимости полного линейного моноида.

ГЛАВА 2. КОЛЬЦА ЦЕЛОЧИСЛЕННЫХ МАТРИЦ.

§4. Формулировки основных результатов.

§5. О границе разрешимости классов колец целочисленных матриц.

ГЛАВА 3. КОЛЬЦА МАТРИЦ И МАТРИЧНЫЕ АЛГЕБРЫ

НАДКОЛЬЦАМИ.

§6. Основные понятия и формулировки результатов.

§7. О граничной эквивалентности колец и матричных колец над ними.

§8. О граничной эквивалентности колец и некоторых матричных алгебр над ними.

ГЛАВА 4. ГРУППЫ ПРЕОБРАЗОВАНИЙ БЕСКОНЕЧНЫХ

МНОЖЕСТВ.

§9. Исходные понятия и формулировка основного результата

§10. О границе разрешимости бесконечной симметрической группы.

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

Огромная роль матричных групп и колец, которую они игра,ют r а.гпгебре, обуславливает важность их исследования в рамках теории моделей. Начало изучению элементарных свойств классических линейных групп было положено А.И. Мальцевым. В [32] им доказана взаимная определимость произвольного поля F нулевой характеристики в полной линейной группе GL{n,F) и в специальной линейной группе SL(ni,F) для любых п > 2, т > 3. Это означает одновременную разрешимость или неразрешимость элементарных теорий £GL(n, F), £SL(m, F) и EF. Везде ниже через R мы будем обозначать ассоциативное кольцо с единицей. Определяющей для дальнейших исследований разрешимости теорий матричных групп и колец явилась работа [31], в которой исследовано соответствие между кольцом R и группой UT(n, R) всех унитреугольных матриц порядка п над R. А именно, показана определимость кольца R в группе UT(3,R) (£/Т(3, R); ,¿12,^23), где ¿.¿j = E + e-ij, Е — единичная матрица, a et-j — матричная единица. Используя этот результат, нетрудно доказать определимость произвольного кольца R в группе UT(n,R) ^ (UT(n, R); -,-1, ii2, - - ■ ,tn-\,n) для любого п > 3. Отсюда и из очевидной определимости группы UT(n, R) в кольце R непосредственно следует, что теории £UT(n,R) и £R одновременно разрешимы или неразрешимы. Продолжая исследования элементарных свойств унитреугольных групп, О.В. Беле-градек [2] доказал, что если кольцо R коммутативно или является кольцом без делителей нуля, то элементарная теория группы UT(n,R), рассматриваемой в сигнатуре без констант, разрешима тогда и только тогда, когда разрешима элементарная теория кольца R. В этой же работе показано, что для произвольного ассоциативного кольца с единицей это неверно, ибо существует такое кольцо R, для которого теория £R неразрешима, а теория £UT(n, R) разрешима для любого п > 3.

Обозначим через Rnxn кольцо всех матриц порядка п > 1 над R. Если R коммутативно, то оно очевидным образом выделяется в кольце RnXn при помощи формулы <р(х) — Уу(ху = ух). Отсюда и из непосредственной определимости кольца Rnxn в самом кольце R следует, что для любого п > 1 теория £RnXn разрешима тогда, и только тогда, когда разрешима теория £R. Нетрудно понять, что произвольное кольцо R определимо в кольце Rnxn при помощи констант en, ei2,. •, ег„, откуда легко следует, что элементарная теория кольца Rnxn в сигнатуре с этими константами разрешима тогда и только тогда, когда разрешима элементарная теория самого кольца R. Обозначим через NT(n, R) тесно связанное с группой UT(n, R) кольцо всех верхних нильтре-угольных матриц порядка га над R. Б. Роуз [51] применил рассуждения из [31] к кольцу NT(n, R) для произвольного R и доказал определимость R в кольце NT (п. R) (NT(n, R); +, -, е12,., eni>n) для любого п > 3. К.Р. Видела [52] показал, что для любого кольца R орбита кортежа (ei2,., &п-\.п) под действием группы автоморфизмов кольца NT(ii.R) определима в NT(n,R). Отсюда и из очевидной определимости кольца NT(n,Ii) в R следует, что теории £NT(n.R) и SR для п > 3 одновременно разрешимы или неразрешимы.

Из приведенных результатов видно, что почти всегда вопрос о разрешимости элементарных теорий матричных алгебр над кольцом R решается "по модулю" разрешимости элементарной теории самого кольца R. Особую роль в подобных исследованиях играет кольцо Z целых чисел. Тем более, что неразрешимость диофантовой теории кольца целых чисел, вытекающая из отрицательного решения Ю.-В. Матиясевичем в [34] 10-й проблемы Гильберта, позволяет уста,побить неразрешимость не только элементарных, но и некоторых ограниченных теорий первого порядка матричных алгебр над Z рассмотренных выше типов.

В цитированной работе [32] была доказана, неразрешимость теорий £GL(n, Z), £SL(n,Z) для любого п > 3. A.M. Слободской в [40] значительно усилил этот результат для группы GL{3,Z), доказав неразрешимость универсальной теории этой группы. Из указанных выше результатов следует неразрешимость теорий £UT(n, Z) и £NT(n, Z) для любого п > 3. Анализируя интерпретацию кольца целых чисел в группе (7T(3,Z), построенную в [31], В.Г. Дурнев [18], [19] доказал неразрешимость диофантовых теорий групп GL(3, Z), SL(3,Z), рассматриваемых в сигнатуре с константами ti2, t2z, а также сколемских теорий групп GL(n, Z), SL(n,Z) для любого п > 3, рассматриваемых в сигнатуре без констант. Кроме того, используя [31], [51], нетрудно показать неразрешимость диофантовых теорий группы UT(n,Z) и кольца. NT (п. Z), а также сколемских теорий группы иТ(п. Z) и кольца NT(n, Z) для любого п > 3.

Опираясь на результат Ю.В. Ма.тиясевича, В.А. Рома.нькои в [38] доказал неразрешимость 3-теории свободной нильпотентной группы ступени п > 9 счетного ранга с двумя свободными образующими. Отсюда следует неразрешимость 3-теории свободной нильпотентной группы Тп ступени п > 9 ранга п в этой же сигнатуре, а значит, и неразрешимость УЗ-теории группы Тп в сигнатуре без констант. Хорошо известно, что для п > 3 группа Тп-\ изоморфна группе UT(;ri,Z). Следовательно, для любого п > 10 неразрешимы 3-хеория группы UT(n, Z) в сигнатуре с константами, интерпретируемыми матрицами t\2 и ¿23- и V3-теория группы UT(n, Z) в сигнатуре без констант. Наконец, отметим неразрешимость сколемской теории кольца Znxn, очевидным образом вытекающую из результата Ю.В. Матиясевича и упомянутой выше интерпретации Z в Znxn.

Обилие результатов по неразрешимости элементарных и ограниченных теорий классических целочисленных матричных групп и колец приводит к рассмотрению проблемы, сформулированной Ю.М. Важениным в [б] для произвольного класса алгебраических систем: описать все в некоторых рамках разрешимые теории рассматриваемого класса, алгебраических систем. Для решения этой проблемы Ю.М. Важениным в [5]-[7] был разработан продуктивный метод критических теорий. Для точных формулировок введем соответствующие понятия из [5]-[7]. Пусть £ — множество всех формул логики первого порядка некоторой сигнатуры т, записанных в предваренной нормальной форме [21]. Множества Ь С £ будем называть языками. Для класса К алгебраических систем сигнатуры г и языка Ь через ЬК будем обозначать совокупность всех предложений из Ь, истинных на К. Пусть Н — рекурсивная и фундированная иерархия языков, т.е. семейство языков, покрывающее £, упорядоченное рекурсивным отношением включения и удовлетворяющее условию минимальности. Иерархия Н языков определяет для класса К иерархию теорий НК = {ЬК | Ь € Н}. Теория ЬК называется Н-критической, если она является минимальной в НК неразрешимой теорией. Множество всех языков Ь £ Н таких, что теории ЬК являются //-критическими, называется границей разрешимости!. данного класса. К относительно иерархии Н и обозначается через Нахождение границы разрешимости класса 1С означает установление полной в рамках иерархии Н алгоритмической картины для 1С, поскольку теория ЬК 6 НК будет разрешимой тогда и только тогда, когда Ь 2 ¿а Лля любого языка Ь\ 6 Вн{К).

Введем иерархии, построенные в [5]-[7]. Пусть € {V,3}, ф для г € — 1} и г, .ч,/, {0,1}. Определим язык . . 0,-р-? А5 V4 из £, где г1 совпадает с г и — пустой символ для г 6 {—Л, V}, следующим образом. Во-первых, блочная схема кванторной приставки каждой из формул (¿1. С}р-°г Л* V4 является подсловом слова С^г . Во-вторых, связка -1, А, V допускается в записи бескванторной части этих формул, если соответственно г = 1, 5 — 1, ^ = 1, и не допускается, если соответственно г = 0, з — 0, £ = 0. Обозначим, кроме того, через А3 V4 объединение и . С^-р-Г А5 V4, а через в — слово А V. Семейство Я А всех языр€М ков вида I . С^р-*7" А3 V4, ->г Ая V4 и А5 V4 вместе с отношением включения называется схемно-альтернативной иерархией языков. Более бедной по сравнению с этой иерархией языков является схемная иерархия, т.е. семейство 3 всех языков вида (¿г. (ЭР9 и ъуО, упорядоченное включением. Пусть п < ш, пв — {(¿1 | р < п}. Переменной иерархией называется упорядоченное включением семейство языков V = {пв | п < и}. Наконец, альтернативной и переменно-альтернативной иерархией называются семейства А = {ъ7~1г А5 V4 | г, .ч, I € {0,1}} и УА = {X П У | А' е V, У € А} соответственно.

В [7] показано, что все определенные выше иерархии рекурсивны и удовлетворяют условию минимальности. Наиболее сложная из них иерархия ЗА содержит такие известные языки как позитивный, сколемский, универсальный, экзистенциальный, диофантов и эквациональный. Чаще всего рассматривается имненно эта иерархия и поэтому приставка ЗА— в выражении "5,4-критическая", а также индекс 5 А в записи Вза{К-) часто опускаются.

Диаграммы иерархий 3, V приведены на рис. 1, а иерархий А, VА, З'А на рис. 2, 3, 4 соответственно. Иерархия V представляет собой цепь типа ш + 1, иерархия А — решетку подмножеств трехэлементного множества, иерархия

V А — это прямое произведение цепи и + 1 на решетку подмножеств трехэлементного множества, а иерархия Б А — прямое произведение иерархии .9 на эту решетку.

Основополагающие результаты по описанию границ разрешимости получены Ю.М. Важениным в [6]-[9]. Дальнейшие результаты опубликованы в [10]-[14], [30], [35], [36], [39].

Итак, проблема описания всех разрешимых теорий алгебр целочисленных матриц сводится к нахождению границ разрешимости этих алгебр. В главе 1 исследуются границы разрешимости группы СЬ(3, 2) и тесно связанного с ней моноида МЬ{3, 2) всех целочисленных матриц порядка 3. а также границы разрешимости некоторых естественных классов групп ОЬ(п,Ъ) и моноидов МЬ(п, Ъ) для п > 3 в сигнатурах с константами и без констант. В [7] были найдены границы разрешимости кольца Z в сигнатуре без констант и в сигнатуре с единицей. Ими оказались множества {УЗ, ЗУ, V—■ V, 3—>Л} и {3,У->} соответственно. А в [10] доказано совпадение границы разрешимости кольца Ъпхг\ п > 1, в сигнатуре с множеством всех матричных единиц порядка п в качестве констант с границей разрешимости кольца целых чисел в сигнатуре с единицей. Глава 2 посвящена описанию границ разрешимости колец Ъг' п

1 в различных сигнатурах, а также границ разрешимости естественных классов таких колец. Полученные в ней утверждения являются существенным обобщением результатов работ [7] и [10].

D-i Л V

З'-i Л V

2-1 Л V

1 -i Л V

0-> Л V w-1 Л V

Рис. 2

Как уже отмечалось, разрешимость элементарных теорий матричных алгебр над данным кольцом определяется разрешимостью элементарной теории самого кольца. Поэтому возникает естественный вопрос о связи границы разрешимости матричной алгебры с границами разрешимости этого кольца в различных сигнатурах. Ясно, что из совладения этих границ следует, в частности, одновременная разрешимость или неразрешимость элементарных теорий кольца и рассматриваемой алгебры. Проблема совпадения границ разрешимости в иерархиях £ и »5*.4 колец Я и ЯпХп, а также кольца Я и некоторой матричной алгебры Мп (Я) над Я изучается в главе 3.

Группа Я) и кольцо ЯпХп для произвольного бесконечного кольца

Я изоморфны группе всех автоморфизмов и соответственно кольцу всех эндоморфизмов свободного /¿-модуля Яп [43]. Таким образом, группу ОЬ(п,Я) и мультипликативную полугруппу кольца ЯаХп можно рассматривать как некоторые группу и полугруппу преобразований бесконечного множества. Все такие группы и полугруппы являются подгруппами и соответственно подполугруппами подходящих бесконечных симметрических групп и полугрупп. Наследственная неразрешимость элементарной теории бесконечной симметрической группы доказана Ю.М. Важениным в [4]. В.В. Маевским в [30] показано, что границы разрешимости бесконечной симметрической полугруппы и класса всех бесконечных симметрических полугрупп равны множеству {УЗ, ЗУ, У->\/, 3-°Л}. Там же анонсирован следующий результат: теории языков V—■ V, 3—>А бесконечной симметрической группы и класса всех бесконечных симметрических групп являются критическими, а теории языков УЗУ, ЗУЗ этих группы и класса неразрешимы. В главе 4 доказывается разрешимость теорий языка ЗУ Л V рассматриваемых группы и класса. Это позволяет, в частности, выписать все шесть возможных границ разрешимости бесконечной симметрической группы.

Основные результаты диссертации

Обозначим через С группу в сигнатуре а = (-,-1 ) и через С — группу (7Д3, Ъ) в сигнатуре а = (-,-1, с\,с2) с константами, интерпретируемыми матрицами ¿12, ¿-¿з- Из цитированных выше работ [40], [18] следует неразрешимость теорий У~> V О, 3 Л О.

В главе 1 изучаются границы разрешимости групп (7 и С. В ней доказываются следующие утверждения.

Теорема 1. Теории V О, 3-> Л С являются критическими, а теория ЗУ Л разрешима.

Теорема 2. Теории ЗУ&', У-^УС? неразрешимы, а теорияУЛУО разрешима.

Исходя из теорем 1-2, атакже учитывая неразрешимость теорий УЗиТ(п, 2), 311Т{п,Ж) для п > 10, естественно предположить, что теории УЗ О и ЗС/ неразрешимы. Если это так, то будет справедлива

Гипотеза 1. Имеют место равенства

В(О) = {УЗ,ЗУ-,У-У,Э-Л}, В (в) = {3,у-}.

В.Г. Дурневым в [18] была доказана неразрешимость теории У3->Л\/ОЬ(п, Ъ) для любого п > 3, а значит и теории 3\/-> Л УСЬ(п,Ъ). Поэтому определенный интерес представляет следующее утверждение, вытекающее из доказательства теоремы 1.

Следствие 1. Теория Э\/Л \/(7£(п,2) разрешима для любого п >2.

Согласно [15], [44] обобщенным групповым тождеством в группе А назовем формулу где аь ., ат € А, аг,. ,ат G Z\{0}, {гь . ,гт} С {1,., ?г}. Причем для любого j € {1,. ,т — 1} из условия ij = ij+i, ajctj+1 < 0 следует, что элемент üj+i нецентральный, а из условия i\ = im, а\ат < 0 следует, что элемент а, нецентральный. В [44] Г.М. Томановым доказана невыполнимость обобщенных групповых тождеств в группе GL(n, F) для произвольного замкнутого нормированного поля F и п > 2. А в [15] И.З. Голубчиком и A.B. Михалевым доказана невыполнимость обобщенных групповых тождеств в группе GL(n,D) для произвольного тела D с бесконечным центром и п > 2. К этим результатам примыкает

Следствие 2. В группе GL(n,Z) для любого п > 2 невыполнимо ни одно обобщенное групповое тождество.

Наряду с группами G, G будем изучать класс Q групп GL(n, Z) для всех п > 3, рассматриваемых в сигнатуре <т, и класс Q этих групп, рассматриваемых в сигнатуре а. Для классов Q. Q справедливы следующие утверждения, аналогичные теоремам 1-2.

Теорема 3. Теории У-* У Q, З-1 Л Q являются критическими, а теории V-> Л Q, 3-1 V Q, 3V Л \JQ разрешимы.

Теорема 4. Теории 3 Л Q, 3VC?, V^ V Q неразрешима,, а, т,еория V Л VQ разрешима.

Как и в случае групп G и G, есть основания полагать, что теории V3^, 3V~>£/, 3Q, У-^Q неразрешимы. В этом случае будет справедлива

Гипотеза 2. Имеют место равенства

В главе 1 помимо полной линейной группы СЬ{3,2) исследуются границы разрешимости и полного линейного моноида МЬ(3, Ъ). Обозначим через М этот моноид в сигнатуре р = (-,1), а через М — этот же моноид в сигнатуре р = (•, 1, Сх, С2). где константы с\, с2 интерпретируются матрицами ¿а2, ¿23- Для моноидов М и М справедливы следующие аналоги теорем 1,2.

Теорема 5. Теории V-1 V М, а-1 Л М являются критическими, а теория ЗУ Л УМ разрешима.

B{Q) = { V3,3V-.,V-V,3-V\}, ß(Q) = { 3, V—>}.

Теорема 6. Теории 3 Л М, 3УМ, У-> V М неразрешимы, а теория У Л УМ разрешима.

Из теорем 2, 6 следует, что

В(0), В (И) € {{З,У-},{ЗЛ,УЗ,ЗУ,У-У},

ЗЛ;ЗУ,УЗУ,УЭ-,У-У},{ЗЛ,ЗУ,УЗ-,У-У}}.

Из упомянутого выше результата [18] о неразрешимости теории ЗУ—' Л УОЬ(п,Щ для любого п > 3 нетрудно получить неразрешимость теории ЗУ~| А УМЬ(п,Х), а значит и теории УЗ-> А УМЬ(п,Ъ) для любого п > 3. Таким образом, представляет интерес следующее утверждение, вытекающее из доказательства теоремы 5.

Следствие 3. Теория ЗУ Л V М Ь(п,Ъ) разрешима для любого а >2.

Обозначим через М (соответственно, через М) класс моноидов МТ(п, Ъ) для всех п > 3 в сигнатуре р (р). Для классов М и М справедливы следующие утверждения, аналогичные теоремам 3,4.

Теорема 7. Теории У-^ V М, 3-> Л М являются критическими, а теории У-| Л М, 3-> V М, ЗУ Л УМ разрешимы.

Теорема 8. Теории 3 Л М, ЗУ^М, У-> V М неразрешимы, а теория У Л УМ. разрешима.

Рассмотрим теперь границы разрешимости многообразий, порожденных группами 2) и моноидами МЬ{п,Ъ) для п > 1. Поскольку в группу

ОЬ(2,2) изоморфно вложима свободная группа любого конечного ранга [28], для любого п > 2 многообразия уаг ОЬ{п,%) и уъх МЬ{п,Ъ) совпадают соответственно с многообразиями всех групп и всех полугрупп. В [6] доказано, что граница разрешимости этих многообразий равна с множеству {У->У}. Многообразие уагС£(1,2) состоит только из абелевых полугрупп. Из [23] следует, что элементарная теория этого многообразия разрешима, следовательно, £(уаг(?1(1,2)) = 0.

В главе 2 описываются границы разрешимости колец мп ^ {ъпхп- +, •), Мп(Ь) ^ (2ПХП; +,-,Ь), где Ь — произвольная ненулевая матрица из ЪпХп. Кроме того, в этой главе исследуются границы разрешимости некоторых естественных классов таких колец.

Для непустого множества К натуральных чисел введем следующие обозначения:

Мк ^ {Мп I п е К}, Мк{8) - {Мп{Ьп) I п е К}, £ ^ {Еп I п е К}, где ¡3 ^ {Ьп € ЪпХп | п £ А'}, а Еп — единичная матрица порядка п. Пусть также Кт,п ^ {к \ т < к < п}, Кп {к | к > п}, где п > га > 1. Множества Кт<п, Кп, очевидно, рекурсивны.

В [7] доказано, что В{М1) = {УЗ, ЗУ,У-У, 3-Л}, В{М1{1)) = {3,У-}. Отсюда и из следующих утверждений непосредственно следует описание границ разрешимости классов Л4к, -М-к (Р) Для произвольных непустого рекурсивного множества К и множества ¡3 ненулевых матриц.

Теорема 9. Для любого непустого рекурсивного множества К натуральных чисел справедливо равенство В(ЛЛк) = В(М\).

Теорема 10. Если К — непустое конечное множество натуральных чисел и множество ¡3 ^ {Ьп 6 Ъп*п | п 6 К} состоит из ненулевых матриц, то В(Л4ц(/3)) = В(М\(1)). Если К — бесконечное рекурсивное множество, то В(Мк(е)) е {В(М1(1)),{\/^,3}}.

В [10] анонсировано совпадение границы разрешимости кольца (2гаХга, +, •. бц, ег2,., епп) с границей разрешимости кольца Мг(1). Из теорем 9,10 вытекает следующее значительное обобщение и дополнение этих результатов.

Следствие 4. Пусть п > 1 и Ь — ненулевая матрица из 2ПХ". Тогда справедливы следующие равенства В(Мп) = В(М\), В(Мп(Ь)) = В(М\( 1)).

Следствие 5. Пусть п > т > 1 и лтожество /3 =■ £ Ъкхк \ к £ АГТО)П} состоит из ненулевых матриц. Тогда выполняются следующие равенства В[МКт,п) = В{Мкп) = В(МХ), В(МКтМ) = В(М1(1)). Кроме того, справедливо включение В(Мкп(е)) Е {В(М1(1)), {У^У, 3} } .

Обозначим через 21, <£, 211, С1 многообразия всех ассоциативных колец, ассоциативно-коммутативных колец, ассоциативных колец с единицей и ассоциативно-коммутативных колец с единицей. Анализируя утверждение теоремы 9, естественно поставить вопрос, будут ли выцолняться соответствующие равенства границ разрешимости для многообразий, порожденных классами М/с, Л4/с(е). Сначала заметим, что, очевидно, у&тМк — у&тМп, уагуИл'(е) = уат Мп(Еп), где п = тах АГ, если К конечно, и уаг М.к = уаг.Мк, уаг Мк(^) = уаг где N — множество всех натуральных чисел, если К бесконечно.

Кроме того, из точного представления свободного ассоциативного кольца с единицей бесконечными вправо и вниз матрицами над свободным ассоциативно-коммутативным кольцом, с единицей [28] следует, что что уаг.'И^ = 21. Таким образом, наш вопрос сводится к рассмотрению границ разрешимости многообразий Уп = уат Мп, \¥п = уаг Мп(Еп). За,метим при этом, что многообразие Уп является унитарно замкнутым [22] многообразием колец, \¥п — это класс всех колец с единицей из Уп, рассматриваемых в сигнатуре (+, -, 1). Очевидно, К С Уп+1 и С для любого п > 1. Кроме того, в [17] доказано, что

Кг ф Уп+1 и \\"п ф ЪУп+1 для любого п > 1. Далее, многообразие уаг М\ совпадает с многообразием С. Действительно, если для некоторого многочлена ¡(х) с целыми коэффициентами тождество Ух ¡(х) = 0 истинно на кольце то по теореме о корнях многочлена в поле комплексных чисел [26] многочлен /(ж) — нулевой. Стало быть, выполняются следующие соотношения с = К с у2 с . с V» с . с 21, с1 = И/\ с т с . с с . с а1.

В [6] доказано, что В(Я1) = {УЗ,У->\/}. Отсюда нетрудно вывести, что 23(21г) = {3, V—IV}. В [35] отмечено, что В(£) = {УЗ, ЗУ—'V}. Из [7] следует, что тогда Б^1) = {3}. Отсюда и из следующего утверждения вытекает полное решение рассматриваемого вопроса при тг = 1 и п > 3.

Предложение 1. Для любого п > 3 справедливы равенства В(Уп) = В(Я1), В(1Уп) = В(Я11).

Будем говорить, что алгебраические системы А — (А; а') и В— {В; сг") Погранично эквивалентны если Вн(А) = Вн{Щ. Это понятие, введенное Ю.М. Ва-жениным, интересно само по себе и весьма полезно при описании границ разрешимости. Из следствия 4 имеем б'А-граничную эквивалентность кольца целых чисел и кольца целочисленных матриц порядка п > 1 в сигнатуре без констант и в сигнатуре с произвольной ненулевой константой. Естественно поэтому поставить общий вопрос о граничной эквивалентности ассоциативных колец с единицей и соответствующих матричных колец. При положительном ответе на этот вопрос граница разрешимости данного матричного кольца будет найдена "по модулю" границы разрешимости самого кольца. Этот вопрос изучается в главе 3.

Всюду ниже считаем, что характеристика кольца Л известна. Обозначим через Я-1 кольцо Я в сигнатуре с единицей, а через 'Ль — кольцо Л в сигнатуре с константой Ь. Соответственно через /2™Х71, Я£хп и Лпхп обозначим кольца всех матриц порядка п над Л в соответствующих сигнатурах.

Теорема 11. Если кольцо Л является телом нулевой или нечетной характеристики или целостным кольцом, то для любого п > 1 справедливы равенства Вз{Лпхп) = Вв{Л), = Вз(Лг)- Если Л — произвольное ассоциативное кольцо с единицей, то для любых п > 1 иг,; £ {1,., п} истинно равенство В3{Лпехп) =

Теорема 12. Пусть Л — целостное кольцо и существует многочлен (р{х,у) с целыми коэффициентами такой, что <¿>(£,77) = 0 ^ (£ = 0 и 7] = 0) для любых £,т) 6 Л. Тогда для любого п > 1 справедливы равенства

Вза{Япхп) = ВЗА(Я), ВЗА(Щхп) = ¿ЫДа).

Зная об Я-граничной эквивалентности колец Лпхп и Л, а также колец Л™Хп и естественно сравнить границы разрешимости относительно иерархии Н колец Л и. Л\ для кольца Л, удовлетворяющего условиям из теорем 11,12.

Теорема 13. Если кольцо Л имеет единицу и вложимо в тело, то =

Вз(Лг). Если же, кроме того, Л является целостным кольцом и существует многочлен (р(х,у) с целыми коэффициенталт такой, что (р(£,г)) = 0 = 0 и г] = 0) для любых £,r] £ R, то справедливы следующие утверждения: (1) если теория 3Ri неразрешима, moBsA^R) = {V3,3V. V->V, 3-<Л}, Bsa{Ri) = {3, V—1}; (2) если теория 3Ri разрешима, то Bsa(R) = Bsa{R\)

Легко понять, что 3Zi = BZi[xi,. .хт]. И поэтому из теорем 12,13 и работы [34] следуют равенства

Bsa{Z[xu ., хт]пхп) = ВЗА(Щхъ ., хт]) = {V3, 3V, V-V, 3-А},

BSA(Z[Xl, • • •, ®ш]?хп) = ЯзаЩХ!, ., xmb) = {V-, 3}.

В [48] Д. Робинсон доказала неразрешимость элементарной теории поля Q, а Р. Робинсон в [49] доказал неразрешимость элементарной теории кольца полиномов над областью целостности с единицей. Таким образом, границы разрешимости Bsa(Q), • • • ,хт]) непусты. A.M. Слободской в [40] анонсировал результат о разрешимости теории V-> Л VQ. Из теоремы 13 следует, что теория 3Qi неразрешима, а значит неразрешима и теория 3Qi[xi,. ,хт] — 3Qi. Применяя теоремы 12,13, получаем равенства вза(®пхп) = bsamxn) = bsa(q) = bsa(q 1),

BSA{Q[xi, • • • , Хт]ПХП) = Bsa(Q[XI,. . . , Х,П]ГП) = Bsa(Q[zi, . . . , xm)) = £sa№i, • • • • ®OT]i).

Назовем коммутативное ассоциативное кольцо F с единицей специальным локальным, если оно является локальным [3] кольцом с нильпотентным максимальным идеалом Т и элемент 2 = 1+1 в нем обратим. Поскольку F/T является полем, то класс колец с единицей, вложимых в специальные локальные кольца содержит класс целостных колец нулевой или нечетной характеристики. Поэтому следующий результат является обобщением теоремы 11 на случай целостных колец нулевой или нечетной характеристики.

Предложение 2. Пусть кольцо R вложимо в специальное локальное кольцо, тогда Bs{Rnxn) = BS(R) и Bs(R%Xn) = Bs{Ri) для любого п> 1.

Наряду с кольцом RnXn в главе 3 исследуется более богатая и тесно связанная с Rnxn матричная алгебра Мп (R) над Л, определение которой принадлежит Ю.М. Важенину. Внимание к ней объяняется тем, что она как алгебраический объект сама по себе интересна и тем, что некоторые алгоритмические свойства этой алгебры представляется возможным распространить и на кольцо Rnxn. Пусть Mn(R) ^ (МП(Я);+, •), где операции + и • на основном множестве Mn(R) ^ (J Rkxl заключаются в расширении при необходимости ис

1<А<" l<i<n ходных матриц "оптимальным" количеством нулевых строк и столбцов, добавляемых снизу и справа, с последующими обычными сложением и умножением полученных матриц (строгое определение алгебры Mn(R) приводится в в главе 3). Естественность введения Mn(R) можно объяснить следующим образом.

Пусть е\,е-2, ■ ■ ■ ,сп — базис свободного В—модуля Вп. Тогда матричную алгебру Мп{В) можно рассматривать как множество эндоморфизмов Л—модуля (ех, е2,., е^) в Д—модуль {е\, ег, • • •, ег), где к, I пробегает множество {1,., п}, с естественно определенными на нем операциями сложения и суперпозиции.

Теорема 14. Если В — произвольное ассоциативное кольцо с единицей, то для любого п > 1 справедливо равенство Вя(Мп(В)) = В${В).

Если рассмотреть случай, когда Я = то можно явно описать гра.ницу разрешимости Вял(МГ1(В)). А именно, справедлива

Теорема 15. Для любого п > 1 имеет м,есто равенство

ВЗА(МП(Х)) ={^у,з-л,уз,зу}.

Отсюда и из следствия 4 вытекает б'Л-граничная эквивалентность колец ЪпХп и алгебры Мп(Ж). Это еще один факт в пользу.изучения алгоритмических свойств алгебры Мп(В). В связи с этим возникает естественная

Гипотеза 3. Для любого ассоциативного кольца В с единицей и любого п > 1 справедливы равенства

В3л(В,пХп) = В3а{Мп(Е)) = В8А{В), ВЗА(Щ*п) = ВЗА(Ва).

Введем обозначения Уп(В.) — уаг ВпХп, \¥п(В) = уаг Щ*п. Легко понять, что если характеристика кольца В, нулевая, то Уп С Уп(В), \\гп С \¥п{В), причем если В коммутативно, то Уп = У„.(В), — \¥п(В).

Проблему описания границ разрешимости многообразий Уп(В), ~№'п{Я) при п > 3 решает следующее

Предложение 3. Пусть Я — произвольное ассоциативное кольцо с единицей нулевой характеристики такое, что теория у В разрешима. Тогда для любого п > 3 справедливы равенства В(Уп(В)) — В(21), В(\¥п(В)) = В(211).

В главе 4 изучаются границы разрешимости произвольной бесконечной симметрической группы Бут, а также класса ¿> всех бесконечных симметрических групп.

Теорема 16. Теории зуд У Бут и зу А у«? разрешимы.

Применяя эту теорему и пользуясь цитированным выше результатом [30] В.В. Маевского, можно выписать все шесть возможных границ разрешимости группы Бут: у-у, 3-а,узу, зуз}, {у-у, 3--а, уз, зу-}, {у-у, з-а,узу, зуз, уза}, {у-у, 3-а, узу, зуз, узу}, {у-у,з-л,узу,зуз,узл,узу},{у-у,з-л,узу, зуз,узлу}

Завершая введение, договоримся о следующем. Кроме ранее введенных мы будем всюду использовать такие обозначения: (5, & и Ш — многообразия всех групп, полугрупп и моноидов соответственно. Для многообразия X алгебраических систем через ., хт) будем обозначать свободную в X алгебраическую систему над алфавитом {хх,., хт}; для кольца 72 через Л[х\,., жт] обозначим множество всех многочленов над Я от переменных х\,. ,хт.

Пусть <5 / — множество всех квазитождеств сигнатуры т. И пусть /С — класс алгебраических систем этой сигнатуры. Согласно [1], [47] будем говорить, что в 1С разрешилиг проблема равенства слов, если эта проблема разрешима в любой конечно определенной в 1С алгебраической системе из 1С. Будем говорить, что в 1С разрешима универсальная проблема равенства слов, если существует алгоритм, который для любой конечно определенной в 1С алгебраической системы А из К~ и любым двум термам ?/,, ?; от порождающих системы А сигнатуры т проверяет равенство и = V в А. Если класс является псевдомногообразием, то универсальная проблема равенства слов эквивалентна разрешимости тео-риии 1К. [16]. Пусть V — некоторое подмногообразие многообразия X. Будем также говорить, что проблема равенства слов в V сильно неразрешима [47], если существует конечно определенная в X алгебраическая система из V, в которой неразрешима проблема равенства слов. Ясно, что из сильной неразрешимости проблемы равенства слов в многообразии V следует неразрешимость проблемы равенства слов в любом над-многообразии 11 С X многообразия V, а значит, и неразрешимость универсальной проблемы равенства слов в 17, что эквивалентно неразрешимости теории (¿Ш.

Пусть даны языки Ь2 £ ЗА сигнатуры т1? т2 и алгебраические системы А\ ^ {Аг; г2) и (Л2;т2). Говорят, что теория Ь\А\ интерпретируема в теории Ь2А2 и пишут Ь\А± < Ь2А2, если существует алгоритм, который по каждому предложению и сигнатуры тг языка Ьг строит предложение V* сигнатуры т2 языка, Ь2 та,к, что |= и тогда и только тогда,, когда. А^ ¡= у'. Легко понять, что если теория Ь\А± интерпретируема в теории Ь2А2, то из неразрешимости первой следует неразрешимость последней.

Для матриц А <Е /?тх"\ В 6 Япхп, где Я — некоторое кольцо, через А 0 В произведение матриц А и В. Наконец, через 0п обозначим нулевую матрицу порядка п.

Основные утверждения диссертации были представлены на Международных алгебраических конференциях в Санкт-Петербурге (1997), Новосибирске, (1997,1998), в Москве (1998), на Международной конференции "Комбинаторные и вычислительные методы в математике" в Омске (1998), докладывались на заседаниях семинаров "Алгебра и логика" (Новосибирск, 1997, 1998) и "Алгебраические системы" (Екатеринбург, 1995-2000). Все результаты диссертации отражены в публикациях [53]—[62] автора. Работы [53], [59]—[62] написаны в нераздельном соавторстве.

1. Бокутъ Л.А. Алгоритмические проблемы и теоремы вложения: некоторые открытые вопросы для колец, групп и полугрупп// Изв. вузов. Математика. 1982. Т.246, №11. С.3-11.

2. Белеградек О.В. Теория моделей унитреугольных и экзистенциально замкнутых групп// Дисс.докт. физ.-ма.т. наук. Кемерово. 1995.

3. Бурбаки Н. Коммутативная алгебра. М.: Наука, 1971.

4. Важенин Ю.М. Об элементарных теориях симметрических групп и полугрупп// Изв. вузов. Математика. 1974. № 1. С.419-434.о. Важенин Ю.М. О критических теориях// УП. Вс. конф. по матем. логике. Новосибирск. 1984. С.27.

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

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

7. Важенин Ю.М. О критических теориях свободных полугрупп и моноидов// III Вс. симпозиум по теории полугрупп. Тезисы докладов. Свердловск. 1988. С. 11.

8. Важенин Ю.М. Критические теории некоторых классов неассоциативных колец// Алгебра и логика. 1989. Т.28, № 5. С.393-401.

9. Важенин Ю.М. О границах разрешимости матричных колец// Вторые математические чтения, посвященные памяти М.Я. Суслина. Тезисы докладов. Саратов, 1991. С.82.

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

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

12. Магнус В., Каррас А., Солитэр Д. Комбинаторная теория групп. М.: Наука, 1974.

13. Марков В. Т. О размерности некоммутативных афинных алгебр// Изв. АН СССР. Сер.матем. 1973. Т.37, № 2. С.284-288.

14. Маевский В.В. Об ограниченных теориях бесконечных групп и полугрупп// Международ, конф. по алгебре, посвященной памяти А.И. Мальцева. Тезисы докладов: Новосибирск, 1989. С.73.

15. Мальцев А.И. Об одном соответствии между кольцами и группами// Ма-тем. сб. 1960. Т.50, № 3. С.257-266.

16. Мальцев А.И. Об элементарных свойствах линейных групп// Некоторые проблемы математики и механики. Новосибирск, 1961. С.110-132.

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

18. Матиясевич Ю.В. Диофантовость перечислимых множеств// Докл. АН СССР. 1970. Т. 191, 2. С.279-282.

19. Попов В.Ю. Критические теории пад-коммутативпо-ассоциативпых мпого-обрзий колец// Сиб. матем. журн. 1995. Т.36, № 6.С. 1364-1374.

20. Попов В.Ю. Критические теории многообразий нильпотентных колец// Сиб. матем. журн. 1997. Т.38, № 1. С.182-192.

21. Размыслов Ю.П. Об одной проблеме Капланского// Р1зв. АН СССР, сер.матем. 1973, Т.37, № 3. С.483-501.

22. Романьков В.А. О неразрешимости проблемы эндоморфной сводимости в свободных нильпотентных группах и в свободных кольцах// Алгебра и логика. 1977. Т.16, № 4. С.457-471.

23. Сизый C.B. Критические теории некоторых классов графов и унарных алгебр// Алгебра и логика. 1989. Т.28, № 4. С.454-462.

24. Слободской A.M. Универсальная теория группы (71,(3,2)// Алгоритмические вопросы алгебраических систем и ЭВМ. Иркутск, 1979. С.200-217.

25. Слободской A.M., Фридман Э.И. Разрешимость универсальной теории Q// Всесоюзн. конф. по матем. логике. Тезисы докладов. Новосибирск, 1979. С.140.

26. Слободской A.M. Неразрешимость универсальной теории конечных групп// Алгебра и логика. 1981. Т.20, ."4-° 2. С.207-230.

27. Супруненко Д.А. Группы матриц. М.: Наука, 1972.

28. Томанов Г.М. Обобщенные групповые тождества в линейных группах// Матем. сборник. 1984. Т. 123, № 1. С.35-49.

29. Belov A.J. Solution one Maltzev problem// II Международная конференция "Полугруппы: теория и приложения" в честь профессора Е.С.Ляпина. Тезисы докладов. Санкт-Петербург. 1999. С.9.

30. Formanek Е. Central polinomials for matrix rings// J. of Algebra. 1972. V.23. P.129-132.

31. Kharlampovich O.G. Sapir M.V. Algorithmic problems in variaties// International Jornal of Algebra and Computations. 1995. V.5, № 4-5. P.379-602.

32. Robinson J. The undercibility of algebraic rings and fields// Pros. Amer. Math. Soc. 1953. V.10. P.437-449.

33. Robinson R.M. Undercidable rings// Trans. Amer. Math. Soc. 1951. V.70. P.137-159.

34. McKinsey J.C.C. The desition problem for some classes of sentences without quantifiers// J. Symbolic Logic. 1943. V.8, № 3. P. 61-76. MR 5-85.

35. Rose B. The Ki-categority or stricly upper triangular matrix ring over algebraically closed fields// J. Symbol. Log. 1978. V.43, P.250-259.

36. Videla C.R. On the model theory of ring NTn(R)// J. Pure Appl. Algebra 1988. V.55, P.289-302.Работы автора по теме диссертации

37. Важ,енин Ю.М., Нагребецкая Ю.В. Критические теории групп и моноидов целочисленных матриц// Изв. вузов. Математика. 1998. № 7. С.77-79;

38. Нагребецкая Ю.В. Разрешимость теорий первого порядка групп и моноидов целочисленных матриц// Алгебра и логика. 2000. Т.39, № 3.

39. Нагребецкая Ю.В. О границе разрешимости бесконечной симметрической группы// Изв. УрГУ. 1999. № 14. С.109-118.

40. Нагребецкая Ю.В. О границах разрешимости колец целочисленных матриц/ Урал. гос. техн. ун-т, 2000. Деп. в ВИНИТИ. 2000, № 286. 22 с.

41. Нагребецкая Ю.В. О граничной эквивалентности колец и матричных колец над ними/ Урал. гос. техн. ун-т, 2000. Деп. в ВИНИТИ. 2000, № 287. 29 с.

42. Нагребецкая Ю.В. О теориях первого порядка групп и моноидов целочисленных матриц/ Урал. гос. техн. ун-т, 2000. Деп. в ВИНИТИ. 2000, № 288. 30 с.

43. Важенин Ю.М., Нагребецкая Ю.В. О границах разрешимости колец целочисленных матриц// Международная алгебраическая конференция, посвященная памяти Д.К. Фаддеева. Тезисы докладов. Санкт-Петербург, 1997. С.178.

44. Важенин Ю.М., Нагребецкая Ю.В. О совпадении границ разрешимости колец и матричных колец над ними// Международная алгебраическая конференция, посвященная памяти А.Г. Куроша. Тезисы докладов. М., 1998. С.193-194.

45. Важенин Ю.М., Нагребецкая Ю.В. О граничной эквивалентности колец и матричпых колец над ними// Мсждуиарод. копф. "Комбинаторные и вычислительные методы в математике". Тезисы докладов. Омск, 1998. С.44.

46. Вао/ссиии Ю.М., Нагребецкая Ю.В. О границах разрешимости групп и полугрупп преобразований бесконечного множества// Международ, конф. ''Комбинаторные и вычислительные методы в математике". Тезисы докладов. Омск, 1998. С.43.