В центре внимания современной теоретико-модельной алгебры находятся вопросы разрешимости теорий первого порядка классов алгебраических систем. Их общая постановка восходит к А. Тьюрингу, Э. Посту, А. Черчу, А.А. Маркову. Решающий вклад в развитие соответствующего направления внесен А.И. Мальцевым, А. Тарским и Ю.Л. Ершовым.
Огромная роль матричных групп и колец, которую они играют в алгебре, обуславливает важность их исследования в рамках теории моделей. Начало изучению элементарных свойств классических линейных групп было положено А.И. Мальцевым. В [17] им доказана взаимная формульность произвольного поля Е нулевой характеристики в полной линейной группе СЬ(п,Р) и в специальной линейной группе ЯЦт, Я) для любых п> 2, тп > 3. Это означает одновременную разрешимость или неразрешимость элементарных теорий £ОЦп,Р), £ЗЬ(т,Р) и £Я. Определяющей для дальнейших исследований разрешимости теорий матричных групп и колец явилась работа [16], в которой исследовано соответствие между ас-социативным кольцом Я с единицей и группой иТ(п, Я) всех унитреугольных матриц порядка п над Я. А именно, показана определимость кольца Я в группе ЯТ(3,Я) {иТ(3, Я); -,-1 ,<12,<2з),
где = Е + е^, Е — единичная матрица, а — матричная единица. Используя этот результат, нетрудно доказать определимость произвольного ассоциативного кольца Я с единицей в группе иТ(п, Я) # (иТ(п, Я); -,-1,/12, ) для любого п> 3, откуда непосредственно следует, что теории £иТ(п,Я) и £Я одновременно разрешимы или неразрешимы. О.В. Белеградек [1] усилил этот результат, доказав, что для любого ассоциативного коммутативного или ассоциативного без делителей нуля кольца К с единицей элементарная теория группы иТ(п, К) в сигнатуре без констант разрешима тогда и только тогда, когда разрешима элементарная теория кольца К. В этой же работе показано, что для произвольного ассоциативного кольца это неверно, ибо существует такое ассоциативное кольцо Я, для которого теория £Я неразрешима, а теория £иТ(п, Я) разрешима для любого п > 3.
Обозначим через Я"х" кольцо всех матриц порядка п> 1 над ас-социативным кольцом Я с единицей. Если Я коммутативно, то оно очевидным образом выделяется в кольце Дпхп при помощи формулы ^(¡с) # Уу(ху = ух), откуда легко следует, что для любого п> 1 теория £ВР*п разрешима тогда и только тогда, когда разрешима теория £R.Легко понять, что произвольное ассоциативное кольцо Rс единицей определимо в кольце Rnynпри помощи констант 611,612,..., ein. И поэтому элементарная теория кольца /?”хп в сигнатуре с этими константами разрешима тогда и только тогда, когда разрешима элементарная теория самого кольца R.Обозна¬чим через NT(n, R)кольцо всех верхних нильтреугольных матриц порядка п над ассоциативным кольцом R.Б. Роуз [29] применил рассуждения из [16] к кольцу NT(n, R)для произвольного ассоциативного кольца Rс единицей и доказал определимость Rв кольце NT(n,R) {NT(n.7?); +, ■, ei2, ■. ., 6n-i,n) Для любого п> 3. К.Р. Видела [30] показал, что для любого ассоциативного кольца Rс единицей орбита кортежа (ei2,..., ел-1,п) под действием группы автоморфизмов кольца NT(n, R)определима в NT(n, R).Таким образом, теории £NT(n,R)и £R для п> 3 одновременно разрешимы или неразрешимы.
Из приведенных результатов видно, что почти всегда вопрос о разрешимости элементарных теорий матричных алгебр над кольцом Rрешается ”по модулю” разрешимости элементарной теории самого кольца R.Особую роль в подобных исследованиях играет кольцо Z целых чисел. Тем более, что неразрешимость диофантовой теории кольца целых чисел, вытекающая из отрицательного решения Ю.В. Матиясевичем в [18] 10-й проблемы Гильберта, позволяет установить неразрешимость не только элементарных, но и некоторых ограниченных теорий первого порядка матричных алгебр над Z рассмотренных выше типов.
В цитированной работе [17] была доказана неразрешимость теорий £GLn,%), £SL(n,3,) для любого п > 3. А.М. Слободской в [23] значительно усилил этот результат для группы GL(3, Z), доказав неразрешимость универсальной теории этой группы. Из указанных выше результатов следует неразрешимость теорий £UT(n,%) и £NT(n.'Z)для любого п > 3. Анализируя интерпретацию кольца целых чисел в группе UTfö^),построенную в [16], В.Г. Дурнев [13], [14] доказал неразрешимость диофантовых теорий групп GL(3, Z), SL(3,2), рассматриваемых в сигнатуре с константами ii2, /•23, а также сколемских теорий групп GL(n,Z), 5£(n.Z) для любого п> 3, рассматриваемых в сигнатуре без констант. Кроме того, используя [16], [29], нетрудно показать неразрешимость диофантовых теорий группы UT(n, Z) и кольца NT(n, Z), а также сколемских теорий группы UT(n,%)и кольца ArT(n. Z) для любого п> 3.
Опираясь на результат Ю.В. Матиясевича, В.А. Романьков в [21] доказал неразрешимость 3-теории свободной нильпотентной группы ступени п> 9 счетного ранга в сигнатуре с двумя свободными образующими. Отсюда следует неразрешимость 3-теории свободной нильпотентной группы 3~п ступени п> 9 ранга п в этой же сигнату¬ре, а значит, и неразрешимость УЗ-теории группы Fnв сигнатуре без констант. Хорошо известно, что для п> 3 группа J-n-iизоморфна группе ит(п,%). Следовательно, для любого п> 10 неразрешимы 3-теория группы C7T(n,Z) в сигнатуре с константами, интерпретируемыми матрицами ¿12 и ¿23, и УЗ-теория группы UT(n, Z) в сигнатуре без констант. Наконец, отметим неразрешимость сколемской теории кольца Znxn, очевидным образом вытекающей из результата Ю.В. Матиясевича и упомянутой выше интерпретации Z в Znx”.
Обилие результатов по неразрешимости элементарных и ограниченных теорий классических целочисленных матричных групп и колец приводит к проблеме, сформулированной Ю.М. Важениным в [4] для произвольного класса алгебраических систем: описать все в некоторых рамках разрешимые теории рассматриваемого класса алгебраических систем. Для решения этой проблемы Ю.М. Важениным в [3]—[5] был разработан продуктивный метод критических теорий. Для точных формулировок введем соответствующие понятия из [3]—[5]. Пусть 8 — множество всех формул логики первого порядка некоторой сигнатуры ст, записанных в предваренной нормальной форме. Множества LС 8 будем называть языками. Для класса К алгебраических систем сигнатуры ст и языка Lчерез LKбудем обозначать совокупность всех предложений из L,истинных на /С. Пусть Н —рекурсивная и фундированная иерархия языков, т.е. семейство языков, покрывающее 8, упорядоченное рекурсивным отношением включения и удовлетворяющее условию минимальности. Иерархия Н языков определяет для класса К иерархию теорий НК - {LK | L G Н}. Теория LKназывается Н-критической, если она является минимальной в НК неразрешимой теорией. Множество всех языков L G Н таких, что теории LKявляются Я-критическими, образуют границу разрешимости Вц(К) данного класса К относительно иерархии Я. Нахождение границы разрешимости класса К означает установление полной в рамках иерархии Я алгоритмической картины для К, поскольку теория LK G НК будет разрешимой тогда и только тогда, когда L2 ¿1 Для любого языка G Вн(К).
Введем иерархии, построенные в [3]—[5]. Пусть Ci G {V, 3}, CiС«+1 Для i G {l,...,p — 1} и r,s,t G {0,1}. Определим язык С1...Ср-1г Л1Vfиз 8, где z1= zи z°— пустой символ для 2 £ {-I, Л, V}, следующим образом. Во-первых, блочная схема кванторной приставки каждой из формул С1.. . Ср->г Л3 V1 является подсловом слова С1 .. .Ср. Во-вторых, связка Л, V допускается в записи бескванторной части этих формул, если соответственно г=1,а=1,/ = 1,ине допускается, если соответственно г = О, 5 О, I = 0. Обозначим, кроме того, через &->г Л3 V1 объединение и Ст .. .Ср->г Л3 а через 0 — слово -> Л V. Семейство ЗА всех реи,
языков вида С1 ... Ср->г Л3 V*, ->г Л3 V* и ст->г Л3 V* вместе с отношением включения называется схемно-альтернативной иерархией языков. Более бедной по сравнению с этой иерархией языков является схемная иерархия, т.е. семейство 3 всех языков вида С.. -Срв и ъэб, упорядоченное включением. Пусть п < ш, пб — {С1£... Сру£ | р< п}. Переменной иерархией называется упорядоченное включением семейство языков V = {й$ | п< ш}. Наконец, альтернативной и переменно-альтернативной иерархией называются семейства А = {у--г Л3 Vе I г, в,г е {0,1}} и УА = {ХПУ I X е У,У е А} соответственно.
В [5] показано, что все определенные выше иерархии рекурсивны и удовлетворяют условию минимальности. Наиболее сложная из них иерархия ЗА содержит такие известные языки как позитивный, сколемский, универсальный, экзистенциальный, диофантов и эквациональный. Чаще всего рассматривается именно эта иерархия и поэтому приставка ЗА— в выражении ”5А-критическая”, а также индекс ЗА в записи А (£) часто опускаются.
Основополагающие результаты по описанию границ разрешимости получены Ю.М. Важениным в [4]-[б]. Дальнейшие результаты опубликованы в [7]-[11], [15], [19], [20], [22].
В [5] было доказано, что границей разрешимости кольца целых чисел в сигнатуре без констант является множество {УЗ, ЗУ, V—'V, В—>А}, а в сигнатуре с единицей — множество {3,У->}. В [7] анонсировано совпадение границы разрешимости кольца 2пХп, п> 1, в сигнатуре с множеством всех матричных единиц порядка п в качестве констант с границей разрешимости кольца целых чисел в сигнатуре с единицей. В диссертации эти результаты существенно дополняются и обобщаются. Наряду с кольцом 2ПХ" в настоящей работе исследуются границы разрешимости группы (7£(3,2) и моноида М£(3,2) всех целочисленных матриц порядка 3, а также границы разрешимости некоторых классов групп ОЦп, 2) и моноидов М£(п,2), п> 3, в сигнатурах с константами и без констант.
Как уже отмечалось, разрешимость элементарных теорий матричных алгебр над данным кольцом определяется разрешимостью элементарной теории самого кольца. В диссертации исследуется естественный вопрос о связи границ разрешимости матричных алгебр с границами разрешимости этого кольца в различных сигнатурах.
Группа С?£(п,Я) и кольцо Япхп для произвольного бесконечного ассоциативного кольца Я с единицей изоморфны группе всех автоморфизмов и соответственно кольцу всех эндоморфизмов свободного Я-модуля Я". Таким образом, группу С£(п,Я) и мульти-пликативную полугруппу кольца Япхп можно рассматривать как некоторые группу и полугруппу преобразований бесконечного множества. Все такие группы и полугруппы являются подгруппами и соответственно подполугруппами подходящих бесконечных сим-метрических групп и полугрупп. Наследственная неразрешимость элементарной теории бесконечной симметрической группы доказана Ю.М. Важениным в [2]. В.В. Маевским в [15] описаны границы разрешимости бесконечной симметрической полугруппы и класса всех бесконечных симметрических полугрупп. Они совпали с множеством {УЗ, ЗУ, У-Д/, Э->А]. Там же анонсирован следующий результат: теории языков У->У, 3~>Л бесконечной симметрической группы и класса всех бесконечных симметрических групп являются критическими, а теории языков УЗУ, ЗУЗ этих группы и класса неразрешимы. Эти исследования продолжены в нашей диссертации.
В работе используются методы, конструкции и результаты теории моделей, математической логики, а также теории групп и теории колец.
В диссертации получены следующие теоретические результаты: сделано существенное продвижение в описании границ разрешимости группы С£(3,2) и моноида М£(3,2), а также класса групп (?£>(п,2) и класса моноидов МЦп, 2) для п> 3 в сигнатуре без констант и в сигнатуре с двумя константами;
описаны границы разрешимости колец всех целочисленных матриц порядка п> 1 в различных сигнатурах, а также некоторых естественных классов таких колец;
доказано совпадение границ разрешимости ряда колец и матричных колец над ними;
доказана разрешимость теорий языка ЗУ Л V бесконечной симметрической группы и класса всех бесконечных симметрических групп, в частности, выписаны все шесть возможных границ разрешимости бесконечной симметрической группы.
Все перечисленные результаты являются новыми.
Диссертационная работа носит теоретический характер. Полученные результаты могут быть применены в теории моделей, а также использованы при чтении специальных курсов по алгебре и математической логике.
Основные утверждения диссертации были представлены на Международных алгебраических конференциях в Санкт-Петербурге (1997), Новосибирске (1997,1998), Москве (1998), на Международной конференции "Комбинаторные и вычислительные методы в математике” в Омске (1998), докладывались на заседаниях семинаров ’’Алгебра и логика” (Новосибирск, 1997, 1998) и "Алгебраические системы” (Екатеринбург, 1995-2000). Все результаты диссертации отражены в публикациях [31]—[40] автора. Работы [31], [37]—[40] на-писаны в нераздельном соавторстве.. Диссертация состоит из введения, четырех глав, разделенных на 10 параграфов. Общий объем диссертации составляет 100 страниц. Библиография содержит 62 наименования. Нумерация параграфов и утверждений диссертации сквозная.
Помощь студентам и аспирантам в выполнении работ от наших партнеров
