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

рг б од

г ч хпр ^

Институт математики

ОССИЙСКАЯ АКАДЕМИЯ НАУК СИБИРСКОЕ ОТДЕЛЕНИЕ

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

Белеградек Олег Вильгельмович

ТЕОРИЯ МОДЕЛЕЙ УНИТРЕУГОЛЬНЫХ И ЭКЗИСТЕНЦИАЛЬНО ЗАМКНУТЫХ ГРУПП

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

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

Новосибирск - 1995

Работа выполнена в Кемеровском государственном университете

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

доктор физико-математических наук, профессор Ю. М. Важешш доктор физико-математических наук, профессор Е. А. Палютин доктор физико-математических наук, профессор В. А. Романьков

Ведущая: организация:

Математический институт РАН им. В. А. Стеклова

— л""

Защита состоится 'ЫЛгЗКЛ 1995 г. в часов на заседании

специализированного совета Д 002.23.01 при Институте математики

СО РАН ио адресу: 630090, Новосибирск, Университетский пр. 4.

С диссертацией можно ознакомиться в библиотеке ИМ СО РАН. Автореферат разослан ю 1995 г.

/

Ученый секретарь

слециализировнного совета '

кандидат физико-математических наук ' С. Т. Федоряев

Общий обзор и характеристика работы

Тема работы относится к теоретико-модельной алгебре. Объектами исследования являются, во-первых, теоретико-модельные свойства унптрсугольных групп и, во-вторых, экзистенциально замкнутые модели теорий, подобных теории групп, и их связь е алгоритмическими проблемами.

Теория моделей, изучающая отношение истинности, связывающее предложения формальных языков п алгебраические структуры, берет начало с работ А. Тарского и А. И. Мальцева и в настоящее время является глубокой, разветвленной п активно развивающихся областью математики. Имеется ряд книг по теории моделей, среди которых отметим этапные монографии Ч. Ч. Чэна и Дж. X. Ксйслера [7] и У. Ходжеса [33]. Направленно теории моделей, в котором в роли объектов изучения выступают классические структуры — группы, кольца, поля и т.п., прпнято называть теоретико-модельной алгеброй. Значительное место в теоретике-.модель поп алгебре занимают теоретико-групповые исследования. Многие результаты теории моделей различных классов групп отражены в обзорах [19, 16, 17], книгах Б. Пуаза [42], А. В. Боровика и А. Нссина [24], Р. У. Кэя и X. Д. Макферсона [34] п сборнике [40],

В семидесятых годах методами логики активно изучались экзистенциально замкнутые модели различных теорий и, в частности, группы. Эта тематика подробно отражена в монографиях У. Ходжеса [32, 33], Г. Хигмэпа п Э. Скотт [29] п обзоре Ф. Лайнена [ЗС].

А. И. Мальцев [И] положил начало изучению элементарных свойств классических линейных групп. В. А. Толстых [18] исследовал элементарные свойства бесконечномерных классических групп.

Важной оказалась работа А. И. Мальцева [10], в которой он исследовал соответствие 7? > иТз(Д) между кольцами с единицей п группами верхних унитреугольных 3x3 матриц. Он показал, что кольцо К может быть интерпретировано в группе иТз(7?) с двумя параметрами — трансвекциями ¿¡г(1) и /2:1(1) — и нашел алгебраическую характернзацию обогащенных групп вида иТ;*(Л) = (иТ3(Л), /12(1), *2з(1)). Соответствие Мальцева пеполь-

човалоеь Ю. Л. Ершовым {6], А. Г. Мясниковым и В. Н. Ремеслен-никовым [14, 15], К. Грюненвальдом и Ф. Хаугом [26].

Работа [10] оставила без ответа ряд естественных вопросов. Этн вопросы группируются; вокруг следующего ключевого: какова роль параметров е характперизации Мальцева? Кольцо Я и обогащенная группа иТз(1?) интерпретируются друг в друге без параметров, поэтому в определенном смысле Я п иТ:*{Я) — один и тот лее объект. Однако можно ли то же самое утверждать об Я и ИТ а (Л)?

Очевидно, еелн иТ^Л) ~ иТз(5), то Л ~ 5; однако неясно, насколько группа иТз( Я) без параметров определяет кольцо Я. Например, верно ли, что и Та (71) = 1]Т;!(5) влечет Я ~ 5? Легко видеть, что теории обогащенной группы иТ^(Д) и кольца Я рекурсивно изоморфны. Ясно, теория группы иТз(Я) разрешима, если разрешима теория кольца Я\ однако верно ли обратное? (Интерпретация Мальцева даст неразрешимость теории группы иТз(И) лишь для колец Я с наследственно неразрешимой теорией.) Аксиоматизируем ли класс всех групп вида иТ3(Я)? Отметим, что для доказательства неаксиоматизнруемоети этого класса соображения компактности помочь не могут, поскольку он ультразамкнут. В случае, если этот класс не аксиом атизцру ем, какие группы попадают в его аксиоматизируемое замыкание? Каковы группы, элементарно эквивалентные группе иТ-ДД)? Верно ли, что это в точности группы иТз(£>), где 5 = Я'! Совпадают ли функции спектра теории группы иТз(7?) и кольца Я, то есть одинаково лп число моделей этих теорий в каждой бесконечной мощности? Естественно также попытаться обобщить мальцевскую характердэацшо и ответить на перечисленные вопросы для произвольного п > 3.

Применяя идею работы Мальцева [10], Б, Роуз [44], У. Уилер [52], К. Р. Видела [50, 51] изучали кольцо 1ЧТ„(Л) всех верхних нильтре-угольных п х л матриц над ассоциативным кольцом с единицей Я для п > 3. Было показано, что кольцо Я интерпретируется (равномерно по Я) в кольце 1ЧТ„(.Я) с параметрами сц,... п орбита кортежа (в12,... ,еп-1,») под действием группы автоморфизмов кольца 1ЧТ„(Я) определима без параметров в этом кольце (равно-

мерно но веем Я). В частности, этот кортеж реализует главный тип в ]ЧГТ,,(/?). Таким образом, для любых ассоциативных колец Я, £>, сели ]\ТП(Я) ~ ГЧТ„(5), то Я ~ 5; в частности, =

влечет Я г 5. Из того, что кортеж (е^, • реализует глав-

ный тпп в ГЧТДЛ), легко следует, что теории колец Я. и 1ЧТ„(/1') рекурсивно изоморфны. Видела описал кольца, элементарно эквивалентные кольцу ГчГТ,,(/?). Это позволило ему показать, что функция спектра теории этого кольца совпадает с функцией спектра теории кольца Я.

Таким образом, аналоги естественных вопросов, сформулированных выше для у 1шт р еу г о л ы тих групп, получили решение для шшь-треугольных колец. Однако для уннтреугольных групп ситуация существенно сложнее. Впдела пишет п [51], что он изучает теорию моделей шшьтреугольных колец отчасти потому, что это может помочь понять отношение между теорией моделей кольца Л и группы иТ„(/?). В качестве наиболее интересного открытого вопроса он отмечает вопрос о совпадении функций спектра теорий ТЬ(7?) и Т1).(иТи(7?)). В [50, 51] ему удалось получить лишь частичные результаты по этому вопросу. Подход Виделы состоит в попытке перенести на унптреугольные группы схему доказательства, сработавшую для шшьтреугольных колец. Методом Мальцева нетрудно интерпретировать кольцо Я в группе иТ„(Л) с параметрами 1 < г < п. Естественно попытаться длказать, т1То орбита кортежа (¿12(1), • • •, ¿11-1,4(1)) под действием группы автоморфизмов группы иТ,,(Я) определима без параметров в этой группе. Впделе удалось найти определяющую формулу в случае п > 5 и коммутативной области целостности Я (равномерно по всем таким Я). В случае п — 3,4 это сделать не получилось, однако для полей случаи малых п также удалось разобрать. Таким образом, Впдела на основе анализа автоморфизмов показал, что для п > 3 п любых полей и К, если Шда ^ иТ„(А'). то Г ~ К; поэтому, если иТ„(^) = иТ„(Л"), то Р = К. Для коммутативных областей целостности Р и К ему удалось сделать это только при п > 5. Для любого поля ? и п > 3, модели теории ТЬ(иТ„(Г)) — это в точности группы иТ„(Л'), где

К = F. Отсюда следует, что для любого поля F функции спектра для Th{F) II Tli(UT„(F)) совпадают.

Цель первой главы диссертации — получить ответы на перечисленные выше естественные вопросы о теоретико-модельных свойствах унитреуголышх групп. Оказалось, что в общей ситуации метод, которым пользовался Видела, не ведет к успеху. Причина в том, что, вообще говоря, кортеж (f12(l),..., f„_iir,(l)) не обязан ре-ллпчшшть главный тип в UTJß), и UT„№) ~ UT„(S) не влечет Д ~ S. Эти обстоятельства позволили построить неожиданные контрпримеры в теории моделей унитреугольных групп, которые демонстрируют рад принципиальных отличий от ситуации с ниль-треугольными кольцами. Оказалось, однако, что для естественных широких классов колец патологии невозможны. Кроме того, унитре-уголыше группы применяются к решению ряда вопросов теоретико-модельной алгебры, отмечавшихся в литературе.

Вторая глава посвяшена вопросам алгебраической характериза-ции разрешимости алгоритмических проблем в теории групп и подобных ей теориях в терминах экзистенциально замкнутых моделей.

В связи с алгоритмическими проблемами в алгебре естествен вопрос: как чисто алгебраически охарактеризовать ситуации, в которых та или иная алгоритмическая проблема разрешима?

Г. Хпгмэн [28] дал алгебраическую характерпзащпо конечно порожденных групп с рекурсивно перечислимой проблемой равенства слов как конечно порожденных подгрупп конечно определенных групп. Позже аналоги теоремы Хигмэна были доказаны и для ряда других многообразий — полугрупп, инверсных полугрупп, ассоциативных п лиевых алгебр [13, 5, 4, 9].

Б. Нойман [41] и А. Макинтайр [38] дали алгебраическую харак-теризацию конечно порожденных групп с разрешимой проблемой слов как конечно порожденных групп, вложимых в любую экзистенциально замкнутую группу.

Напомним, что модель £ индуктивной теории Т называется экзистенциально замкнутой в Т, если для любой экзистенциальное формулы ф(х) и любого кортежа й в £ из того, что ф(а) истинна i

некоторой модели теории Т, содержащей £, следует, что ф(а) истинна п самой £. Понятие; экзистенциально замкнутой модели активно изучалось d теории моделей и в алгебре; многие результаты этих исследований отражены в книгах [30, 32, 33, 29) и обзоре [30].

Начало серьезному изучению экзистенциально замкнутых групп положил А.Макинтанр [37, 38]. Многие из проблем, поставленных им в этих статьях, были решены автором в 1973 -74 годах и изложены в его кандидатской дпссертащш [2], защищенной в феврале 1975 года. Эти результаты были передоказаны в хабиталитацион-ной диссертации М. Цпглсра [53], защищенной им в июне 197G года и опубликованной в виде статьи [54] в 1980 году.

Одна из проблем, поставленных А. Макннтайром в [37, 38], п решенная автором в [1], состояла в следующем. Макпнтайр доказал, что, если конечно порожденная группа Н\ вложима в любую экзистенциально замкнутую группу, в которую вложима конечно порожденная группа Н% то проблема равенства слов для 77 j сводится по Тьюрннгу к проблеме равенства слов для Ну, и поставил проблему, верно ли обратное. Оказалось, что это не так. Тем не менее, автор показал, что для рекурсивно определенных групп обратное становится верным, если заменить !Г-сводпмость на более сильную сводимость рекурсивно перечнелимых множес-TD, так называемую Q-сводимость. Пусть II¡, H-¿ — конечно порожденные рекурсивно определенные группы. Автор доказгш равносильность следующих условий: (i) Н\ вложима в любую экзистенциально замкнутую группу, в которую вложима H'¿] (ii) проблема равенства слов в II¡ (^-сводится к проблеме равенства слов в Кроме того, проблема равенства слов в Н\ Т-сводится к проблеме равенства слов в H¿, если и только если II\ вложима в любую экзистенциально замкнутую группу, в которую вложима H-¿ * Z. Это и есть правильная алгебраическая характеризацпя Т-сводимости проблем равенства слов.

М. Циглер [54] распространил определение (^-сводимости на произвольные, не обязательно рекурсивно перечпелпмые, множества, п доказал равносильность (i) и (ii) для произвольных конечно порожденных, не обязательно рекурсивно определенных, групп II¡ ц H-¿.

Для этого ему потребовалось доказать релятивизованную версию теоремы Хигмэна.

У. У. Буи и Г. Хлгыэн [22] нашли еще одну алгебраическую ха-рактерцзащпо конечно порожденных групп с разрешимой проблемой равенства слов, а именно, характеризацию их как групп, вложим ых в простые подгруппы конечно определенных групп. Отметим, что достаточность последнего условия для разрешимости проблемы равенства по-сушеству была доказана еще б [8]. Другие алгебраические характеризации, являющиеся вариациями тех же пдей, были предложены Е. Рипсом [43] и А. Манном [39]. Обзор результатов Ноймана-Макинтайра и Буна-Хпгмэна был опубликован Г. Сабба-хом в трудах семинара Бурбаки [45].

У. У. Бун и Г. Хигмэн [21, 22], а также Г. Саббах [45], пропагандируют рад проблем, связанных с их работой. В частности, они ставят вопрос о нахождении алгебраических характеризаций разрешимости для других алгоритмических проблем в теории групп, например, характеризации конечно порожденных групп с разрешимой проблемой сопряженности, классов конечно определенных групп с разрешимой проблемой изоморфизма и т.д. Например, Буя и Хигмэн [23] нашли характеризацию конечно порожденных групп групп с разрешимой проблемой порядка. Ряд результатов в этом направлении были получены Дж. Сакердоутом [47] п автором [57, 59].

Аналоги теорем Ноймана-Макинтайра и Буна-Хигмэна были доказаны также и для полугрупп; доказательства здесь похожи, но вместо теоремы Хигмэна использовался ее аналог для полугрупп -теорема Мурского. У. У. Бун [21] ставит следующую общую проблему: для каких алгебраических и логических систем имеют место аналоги характеризаций Ноймана-Макинтайра и Буна-Хигмэна? В обзоре Т. Эванса [25] обсуждается, в частности, эта проблема.

Цель второй главы диссертации — для некоторого класса теорий (названных теориями, подобными теории групп) доказать общую теорему, позволяющую для широкого класса алгоритмических проблем найти алгебраические характеризации. В рассматриваемый класс теорий, кроме теории групп, попадают теории групп без

кручения, полугрупп, ассоциативных алгебр над полем. Для этих теорий удалось доказать аналоги п рслятпвпзованной теоремы Хиг-мэна, и результата о связи Q-сводимости с экзистенциальной замкнутостью.

Общая методика исследования. В работе используется разнообразный аппарат теории групп, теории колец, универсальной алгебры, теории моделей и теории алгоритмов. Ключевым в исследовании теоретико-модельных свойств ушгтреугольных групп является введенное и детально изученное в диссертации понятие квазп-уиитреугольноп группы.

Научная новизна. Новы все основные результаты, а также значительная часть аппарата исследований. В делом, новый результат — обнаруженные принципиальные различия между теоретико-модельными свойствами нпльтреугольных колец я унитреугольных групп. Новым результатом является и выделение общих свойств ква-зимногообразшг, позволяющих получать алгебраические характери-зации разрешимости многих интересных алгоритмических проблем.

Практическая и теоретическая ценность. Работа ноент теоретический характер. Полученные результаты решают ряд вопросов, отмеченных в литературе, обобщают и дают переосмысление ряда известных фактов. Детально изучены, прояснены и обобщены свойства соответствия Мальцева между кольцами и группамп. Найден общий подход к нахождению алгебраических характерпзаций разрешимости ряда алгоритмических проблем для широкого класса ква-зпмногообразий. Результаты п методы работы могут найти применение в исследованиях по алгебре п математической логике, при подготовке специальных курсов, монографий п учебников. Некоторые из них уже нашли применение и отражены в монографиях и статьях [19, 24, 26, 27, 29, 31, 32, 33].

Апробация. Результаты диссертации сообщались на всесоюзных и международных конференциях по математической логике (Новосибирск 1979, 1994; Алма-Ата 1990; Казань 1992), на всесоюзных п международных конференциях по алгебре (Ленинград 1981, Львов 1987, Новосибирск 1989, Барнаул 1991, Красноярск 1993), казахстан-

ской конференции по математике и механике (Алма-Ата 1977), всесоюзном симпозиуме по теории колец, алгебр п модулей (Новосибирск 1982), школе по многообразиям алгебраических систем (Омск 1978), советско-французских и казахско-французских коллоквиумах по теории моделей (Караганда 1991, Марсель 1992, Алматы 1994), международном конгрессе математиков (Варшава 1983), международных логических коллоквиумах (Западный Берлин 1989, Хельсинки 1990), международных конференциях по теории моделей (Дарэм 1988, Обервольфах 1992, 1994), пасхальных конференциях по теории моделей (Венднш-Рптц 1989, 1990, 1993), среднеатлантичссюш конференции по математической логике (Нью-Брансуик 1994). Они докладывались на семинарах в Кемеровском, Московском, Новосибирском, Тверском госунпверситстах, Институте математики СО РАН в Новосибирске, университете Тюбингена (ФРГ), университете Париж 7 (Франция), университетах Лидса, Манчестера, Куин Мэри колледже Лондонского университета (Великобритания), Веслеев-ском университете в Мидлтауне, университете Иллинойса в Чикаго, университете Мэриленда в Колледж Парке (США).

Результаты диссертации опубликованы в работах [55] [85].

Объем и структура диссертации. Диссертация изложена на 213 страницах. Она состоит из введения, двух глав, каждая пз которых разбита на 4 раздела, и библиографии. Разделы разбиты на подразделы, общее число которых равно 45. Библиография содержит 154 наименования.

Содержание диссертации

Во введении дается подробный обзор проблематики, которой посвящена диссертация, формулируются постановки решаемых в диссертации задач и основные результаты.

В первой главе изучается теория моделей унитреугольных групп.

Раздел 1.1 посвящен обобщению унитреугольных групп — ква-зи-унитреугольным группам — ключевому понятию в теории моделей унитреугольных групп. Важность изучения этих алгебраических объектов обусловлена тем, что любая модель теории класса всех

ит,.-групп является квазп-унптрсугольной группой. Этот раздел самый большой в диссертации — имеет 23 подраздела.

В 1.1.1 напоминаются известные свойства унитреугольных групп, а в 1.1.2 — необходимые сведения из теории расширений групп.

В 1.1.3 вводится понятпе квазн-упнтреуголыюй группы следующим образом. Пусть п > 3, и Л — кольцо с единицей, ассоциативное при п > 3. Пусть «л,... ,//„_1 симметричные 2-коцпклы пз П+ в Л+. Для матриц а = (а^) н Ь= (/?у) пз иТ„(Л) положим

а 0 Ь = а ■ Ь+ (Е|<?г(а1-,{+1,/3;1,-+1))е1„.

Оказывается, множество иТ7,(Л) образует группу относительно операции О; новая группа обозначается через ЦТ„(Л, <ц,...,д„-\), а группы такого вида называются квази-унитреугольными (пли, короче, квази-иТ„-группами). Если все //; —- нулевые коциклы, получаем обычную группу иТп(Я). Показывается, что понятпе квазн-унытреугольной группы является частным случаем одной общей конструкции из теории расширений групп. Оказывается, в группах иТ„(Л,01,... ,5,1-1) п иТ„(Л) операции сопряжения н коммутирования, а также нижние центральные ряды совпадают; таким образом, группа иТ„(Л,51,..., г/„_1) нпльпотентна ступепп п - 1.

В 1.1.4 выписываются порождающпе элементы и определяющие соотношения квазп-унптреугольных групп.

Для г < j мы обозначаем через <,;(«) трансвекцпю е + ае1;- из группы и = иТ„(Л,/л,...,цп-]). Для краткости будем писать tij вместо *у(1). Для г + 1 < ] будем обозначать Щ = {%(а) : а Е Л}; для г < п будем обозначать (/¡¿+[ = {¿¡¿^(га) + ¡ЗеУп : а,/3 € Л). Очевидно, Щ — подгруппа в и для г < Положим

1= : 1 <i<j< п}, Н = {Щ •' 1 < г < < п}.

В 1.1.5 перечисляется ряд свойств обогащенной группы (II,И, I), а в 1.1.6 показывается, что эти свойства дают абстрактную характе-рпзацпю обогащенных групп вида (II,ИД): если удовле-

творяет определенному конечному множеству предложении первого порядка, то в ()) пнтерпрстнруется без параметров некоторое

кольцо Я - Ш1Ь) такое, что для некоторых симметричных 2-коциклов <71,... ,</„-1 из в имеем (иМЛ) - (//,#,{)) Для и — ит„(л, ди ■ • ■ В качестве следствия получаем абстракт-

ную характернзацню обогащенных групп (II, 11,1) в случае, когда V — обычная унитреугольная группа: к характеризующим аксиомам для квазп-ит„-групп добавляется (неэлементарная) аксиома '(/]„ — прямое слагаемое в ^,¿+1 1 < г < п\

В 1.1.7 доказывается, что все подгруппы 11ц определимы в II с параметрами I. Поэтому результаты выше можно сформулировать как абстрактные характерпзацип обогащенных групп вида (V, V), а вместо ^Э, ()) писать Кн^Я, I)). Отсюда видно,

что класс всех квазп-иТ„-групп конечно аксиоматизируем в логике первого порядка. Для краткости пишем ЦТ*(Д, </],..., </„_!) вместо (иТ„(Л,51,..., 5,1-1), 1). Приведенные результаты, характеризующие квази-иТ„-группы и ит^-группы обобщают мальцевскую характеризацию иТз-групп.

В 1.1.8 мы вводим понятие базы квази-иТ„-группы. Кортеж I) называется базой группы Я, если (Я, I)) ~ иТ*(Я,</1,... ,дп-1) Для некоторых Я, д 1,... ,<у„_1. Кортеж I называется стандартной базой группы иТ„(й, <7х,..., <7„-1). База {) группы Я называется расщепляющей, если (II, (}) ~ иТ*(Я) для некоторого Я. Таким образом, 1.1.6 характеризует базы и расщепляющие базы в группах. База () в Я называется чистой, если (Я,Р)) ~ иТ*(Я, <71,... ,уи-\) для некоторого кольца Я и чистых коциклов д\,... ,дп-\- Для I Си база [) в Я называется /-чистой, если (Я, I)) ~ иТ*(Я, <71,..., //,,-1) для некоторого кольца Я и /-чистых коциклов Я, д\,... (Здесь симметричный 2-коцикл называется чистым (/-чистым), если соответствующее расширение абелевых групп чисто (/-чисто); расширение абелевых групп А < В называется /-чистым, если А Г) тВ — тА для всех т £ /.)

В 1.1.9 изучаются декартовы произведения квазц-ит,ггрупп, Оказывается, декартово произведение семейства групп является квази-иТ„-группой, если и только если все сомножители таковы; кваз1ьитп-группа над декартово неразложимым кольцом декартовс

неразложима; группа иТ„(/?) декартово разложима, если и только если кольцо Я таково. Эти факты в дальнейшем используются при построении примеров.

В 1.1.10 доказано, что группа иТ„(Л,<л,... ,(/,,-1) изоморфна группе иТ„(Л°р, д,,_!,..., т) Для любых Я, ¡ц,.... //,,_!; в частности, иТ„(Л) ~ иТ„(/?ор). Показано, что существуют ассоциативные кольца Я и Б такие, что иТ„(/?) ~ иТ„(5') для любого п > 3, но Я ф. 5, 5ор. Однако в 1.1.11 -1.1.14 доказывается, что для любого п > 3 и любых ассоциативных колец II и 5 таких, что иТ;1(Л,уь... 1) ~ ит„(5,(г[,.. .,дп-0, имеем Я ~ 5, если В коммутативно, и Б или Я ~ если Я целостно. Этот результат нов даже для обычных унптреугольных групп.

В 1.1.15 описываются базы в 11Тл(5, <71, (¡-¿) в случае п = 3 и коммутативного асоциативпого 5. В 1.1.16 находятся, в случае п — 3 и коммутативного ассоциативного й, явные формулы перехода к новой базе — формулы, позволяющие по базе [) н коциклам г/х, <72 найти коциклы п, ?-2 такие, что (иТз(5, </ь </'Д Ь) — иТд(5, п, г2). Эти формулы служат инструментом изучения квазн- иту групп над коммутативными кольцами.

В 1.1.17 изучаются центральные изоморфизмы квазп-ит„-групп. Изоморфизм 0 : иТп(Я,уи.. ) -> иТ„(7г, ,..., _х) называется центральным, если он тождествен на центре н действует на стандартную базу тождественно по модулю центра. Показывается, что любые две базы квазп-унитреугольнои группы, сравнимые по модулю центра, сопряжены центральным автоморфизмом.

В 1.1.18 рассматривается вопрос о том, когда изоморфизм колец Л п 5 индуцирует изоморфизм квазп-иТ„(Л)-группы па квазп-иТ„(5)-группу. В случае, когда это так, соответствующий изоморфизм групп называется кольцевым.

В 1.1.19 изучаются так называемые естественные изоморфизмы квазп-унптреугольных групп. Изоморфизм квази-иТп(Л)-группы на квазп-иТ„(5)-группу называется естественным, если образ стандартной базы первой группы сравним по модулю центра со стандартной базой второй группы. Оказывается, естественные пзо-

морфизмы — это и точности композиции кольцевых и центральных изоморфизмов. Две квазн-иТ„-группы называются естественно изоморфными, если они изоморфны с помощью естественного изоморфизма. Оказывается, группы иТ„(Д,.(/1> ■ • - ,^-1) и иТ„ (5,01,... ,</„-1) естественно изоморфны, если и только если иТ'ДЛ,^,...,^,-]) с- иТ(/!,...,<7„_1). Доказано, что группа иТ„(Д,й1,..., </„_ 1) естественно изоморфна любой группе, которой она изоморфна, если и только если л \ у-. .., (]) все базы автоморфно сопряжены.

В 1.1.20 изучается вопрос, при каких условиях на кольцо Я все базы в любой квази-иТ„(Д)-группе автоморфно сопряжены. Оказывается, если это так, то Я ~ Я°р и Ех1(й+, Я+) = 0, а если Я целостно или коммутативно, то верно и обратное. Показано, однако, что в общем случае обратное неверно. Естествен вопрос, для каких колец Я все базы в иТ„(Л) автоморфно сопряжены. Мы решаем этот вопрос в случае коммутативного ассоциативного Я п п = 3. Оказывается, для коммутативного ассоциативного Я в группе иТ;|(Л) все базы автоморфно сопряжены, если и только если 2-коцпкл рг : (х, у) н-+ ху из Я+ в Я+ является кограницей.

В 1.1.21 мы изучаем вопрос о том, для каких коммутативных ассоциативных колец Я (не обязательно с единицей) коцикл рг является кограницей. Достаточным для этого является, конечно, условие ЕхЬ(Я+,Я+) — 0; поэтому рг — кограница, если Я+ делимая пли свободная абелева группа. Другим достаточным условием является 2-биномиальность кольца Я, то есть истинность в Я. предложения УхЗ\у(х(х — 1) = 2у). Новые примеры колец, для которых рг — кограница, позволяет получать следующее замечание: для кольца Я\ х Я'2 коцикл рг является кограницей, если и только если рг является кограницей для и Ну. Показано, что, если рг — кограница для Я, то 2па = 0 влечет па = 0 в Я, для любого натурального и и любого идемпотента а. Поэтому, если Я — область целостности и рг — кограница в Я, то Л не имеет 2-кручения. Доказано, что в кольце Я конечной характеристики рг является кограницей, если в только если сЬаг(й) нечетна. Поэтому для поля Я коцикл рг являет-

ся кограницей, если II только если сЬаг(/?) ф 2. Показано, что, если кольцо Л.1 получено из Л присоединением единицы, то для Л1 коцикл рг является кограницей, если и только если это так для Л. Поэтому, присоединяя к кольцам с нулевым умножением на произвольных абелевых группах единицу, мы получаем кольца, для которых рг — кограница, с весьма разнообразными аддитивными группами, в том числе и с 2-крученисм. Если рг — - кограница для Л, то для любой свободной коммутативной ассоциативной Л-алгебры коцикл рг также является кограницей.

Еслп (/],..., </„_) — кограницы, то, как легко показать, имеем иТ„ (Л, <7х,... ,</,,„1) ~ иТ„(Л). Однако, обратное, вообще говоря, неверно. Например, для любого коммутативного ассоциативного Л имеем иТ3(7?, рг, 0) ~ иТ3(Д,0,рг) ~ иТ:1(7?), хотя коцикл рг может и не являться кограницей для Л. Для контраста отметим, что ит3(22,рг,рг) ф. ит3(г2), но, для любых Сх ? С2 £ К, иТз(/(\ С1Р1', С2Р1') — иТз(7?), еслп Л — алгебраически замкнутое поле характеристики 2.

В 1.1.22 мы получаем результаты, касающихся следующей гипотезы: для любого Л равносильны условия: (1) иТ„(Л, //!,..., /;„__]) ~ ит„(л) для любых //!,..., <771_1? (2) Е хЦЛ+, Л+) - 0. Легко видеть, всегда (2)=>(1); однако, даже для коммутативных ассоциативных Л и п = 3 неизвестно, всегда ли верно (1)=>(2). Мы сосредоточимся на этом случае. Следующий результат является некоторой аппроксимацией (1)=^(2). Именно, еслп (1), то ЕхЦЛ+,Л+) мала в следующем смысле: любой симметричный 2-коцшш из Л+ п Л+ когомологи-чен ("рг для некоторого ( £ П. Пример ситуации, когда Ех^Я+, Л+) мала, но нетривиальна, доставляет кольцо Z2; более того, если Л имеет подкольцо 5, изоморфное Z2 и такое, что Л+ ~ ф Л, где абелева группа А делима и без кручения, то ЕхЧ(/?+, Л+) мала', по нетривиальна. Эти примеры не случайны: если Ех1(Л+, Л+) мала, но нет])ппиальна, то Л+ содержит инволюцию. Кроме того, если Л+ разлагается в прямую сумму конечных циклических групп, то Емала, если и только если Л ~ Ъ<х- Еслп Я целостно, то Ех1(Л+,Л+) мала, но нетривиальна, тогда п только тогда, ко-

гда Л ~ г2. Из перечисленных результатов следует справедливость гипотезы (1)<=Ц2) для п — 3 п коммутативного ассоциативного Я при следующем дополнительном предположении: Я целостно или К+ разлагается в прямую сумму конечных циклических подгрупп.

Для любого п > 3 кольцо Я и обогащенная группа иТ*(Я) интерпретируются друг в друге (равномерно по Я). В 1.1.23 изучается взаимосвязь этих двух интерпретаций. Пусть Г — естественная интерпретация иТ*(Д) в Д, а Д — интерпретация Я в иТ*(Д), введенная в 1.1.6. Оказывается, пара (Г,Д) является бшштерпре-тацией (в смысле Циглера, см. [33]), если и только если Я ~ Zm для некоторого т. Более того, в случае, когда Я — алгебраически замкнутое поле, удается доказать, что Я и иТ„(Л) вообще не бинн-терпретируемы с произвольными параметрами. Группа иТ„(72) интерпретируется в кольце Я без параметров; естествен вопрос, можно ли интерпретировать Я в иТ„(Л) без параметров пли хотя бы с определимыми параметрами (в смысле [33], с. 213). Показано, что, вообще говоря, это не так. Однако, если Я коммутативно и ассоциативно, то для любого п > 3 кольцо Я интерпретируемо в группе иТГ1(7?) с определимыми параметрами, а в случае п = 3 — даже без параметров. Если Я — ассоциативное целостное кольцо, то для любого п > 3 кольцо Я х Я°р и группа иТ„(Л) интерпретируются друг в друге с определимыми параметрами.

Раздел 1.2 посвящен изучению моделей элементарных теорий классов унитреугольных групп.

В 1.2.1 показывается, что, для любого я > 3 и любого конечно аксиоматизируемого класса колец .Я, класс всех групп, изоморфных группам вида иТ„(.Д, <71,... ,дп-1), где Я £ Я., является конечно аксиоматизируемым. Имеются примеры, показывающие, что в этой формулировке нельзя убрать слово 'конечно'.

В 1.2.2 доказано, что для любого п > 3 класс всех обогащенных групп вида ИТ* (Я) не аксиоматизируем. Однако его теория рекурсивно аксиоматизируема; ее модели — это обогащенные группы вида ИТ* (Я, д},..., дп-\), где /л...., дп-\ — чистые коциклы. Для любого Я модели теории ТЬ(иТ* (Я)) — это в точности обогащенные

группы вида ит*(5, г/ь •• • ,Чп-\), где 5 = Я, а </ь ..., ч„-\ чисты. Итак, для обогащенных групп иТ*(7?) ситуация похожа на ситуацию с нильтрсугольнымп кольцами, изученную К. Р. Виделой [51]. Оказывается, для групп иТ„(/{) ситуация существенно сложнее.

Квазп-унптреугольная группа называется чистой, если она обладает чистой базой, и локально чистой, если она обладает /-чистой базой для любого конечного I С си- Оказывается, эти два понятия не совпадают. В 1.2.2 показывается, что для любого п > 3 теория класса всех ит„-групп ¡эекурсивно аксиоматизируема; ее модели — это в точности локально чистые квази-иТ„-группы. Для любого класса колец Д п любого п > 3 охарактеризованы модели теории класса групп вида иТ„(Л), где Л £ Л.

Показано, что, если 5 — ассоциативное кольцо, которое коммутативно пли целостно, то иТ„(Л, </],... ,яп-\) = иТ„(5,</1,- • • ></«-1) влечет II = 5 или Я = 5ор. Отметим, что для произвольных ассоциативных 5 утверждение неверно: существуют конечные ассоциативные 7? и 5 такие, что иТ„(/?) ~ ит„(5), но Я не изоморфно ни 5, ни .Ет1'1. Это дает отрицательный ответ на вопрос Впделы о том, верно ли, что из 15Тп(Я) = иТ„(5) следует В = 5.

Доказано, что, если 5 — ассоциативное кольцо без кручения, которое коммутативно плп целостно, то С4 = ЦТ,,(5), если и только если группа С имеет вид иТп(Я,[л,... ,дп_{) для некоторого Я = 5.

Показано, что, если аддитивная группа кольца 5" является прямой суммой группы ограниченной экспоненты и делимой группы, то (1) любая группа, элементарно эквивалентная иТ„(£), имеет внд иТ„(7?) для некоторого Я; (и) обогащенные группы, элементарно эквивалентные ЦТ* (5)— это в точности обогащенные группы вида иТ*(Я), где Л. = 5; (ш) если Т11(5) конечно аксиоматизируема, то и ТЬ(иТ„(5)) конечно аксиоматизируема. Утвержденне (ш) позволяет строить примеры бесконечных групп с конечно аксиоматизируемыми теориями; например, можно взять в качестве 5 безатомное булево кольцо. Отмстим, что в 1.2.4 построен пример, показывающий, что в (¡), вообще говоря, нельзя выбрать кольцо Я элементарно эквивалентным кольцу 5. Однако, если вдобавок 5 коммутативно-

или целостно, то группы, элементарно эквивалентные иТ„(5) — это в точности группы вида иТ„(Л), где Я = Б. В частности, это так, если Б — тело.

Кроме того, мы доказываем в 1.2.2, что класс всех иТ3-групп не является элементарно замкнутым; более того, существует группа, элементарно эквивалентная иТу(г), которая не изоморфна никакой иТз-группе. Тот факт, что для Я = Ъ возможна ситуация, когда группа вида иТ3(^,51,52) не изоморфна. Т1Тп(/?). далеко не очевиден. Его доказательство опирается на приведенные выше результаты об особой роли коцикла рг и тот факт, что ЕхЬ(Я+,Я+) ф 0 для некоторого Я = Z.

Основной результат в 1.2.3 — пример локально чистой не чистой квази-ит3-груцпы. Мы задаем образующими и определяющими соотношениями коммутативное ассоциативное кольцо Я такое, что группа иТз(Д,рг,рг) имеет требуемое свойство. В качестве следствия получаем элементарную незамкнутость классов иТз-групп и чистых квази-иТ3-групп. Побочным продуктом доказательства является то, что теория класса всех иТз-групп не является конечно аксиоматизируемой, хотя она и рекурсивно аксиоматизируема.

В 1.2.4 мы доказываем, что теория иТ„-группы над кольцом Я не определяет теорию этого кольца. Мы строим ассоциативное кольцо Я (простой характеристики) такое, что для любого п > 3 некоторая группа С? = иТ„(Л) не может быть представлена в виде иТп(5,д1,...,вп.1),где5 = Л.

В разделе 1.3 мы изучаем вопрос о числе моделей теории унитре-угольной группы.

В 1.3.4, отвечая на вопрос К. Р. Виделы [50, 51], мы строим пример ассоциативного кольца Я такого, что /(Л,иТ„(Л)) и 1(Х,Я) конечны и различны для некоторого несчетного Л. Из результатов Лахлана следует, что указанная ситуация возможна лишь если кольцо Я Ио-категорично и к0-стабильно, а А < ¡V

В 1.3.5 мы показываем, что невозможна ситуация, когда /(А, Я) и /(А, иТ„(Л)) различны для некоторого несчетного А, и один из этих кардиналов конечен, а другой бесконечен. Это вытекает из следую-

гцсго общего результата: если М' — обогащение структуры М конечным числом констант и Л > Ко, то /(Л, М) конечно, если и только если 1{\,М!) конечно. Этот результат вытекает, в свою очередь, из следующей теоремы: полная счетная теория Т имеет конечное число моделей в некоторой несчетной мощности, если и толыда если Т несчетно категорична или некоторое ее расширение с помощью определений почтп тотально категорично. Последний результат можно рассматривать как ответ на следующий, не очень точный, вопрос А. Лахлана [35]: "В некотором смысле каждый известный пример теории с конечным числом моделей в некоторой несчетной мощности можно рассматривать как комбинацию конечного числа тотально категоричных теорий. Можно ли формализовать и доказать эту идею для всех таких теорий?"

В 1.3.3 излагаются положительные результаты о связи /(А, Я) и ДЛ,иТя(Д)). Доказано, что Г(А,ит„(Д)) = 1(Х, К) для любого коммутативного ассоциативного Я и любого бесконечного А. Если 11 — целостное ассоциативное кольцо, то 7(А,иТ„(Л)) = /(А, Я) для любого несчетного Л, и /(к0, иТ„(Я)) < при этом < имеет

место тогда и только тогда, когда Я — тело, 1{щ,Я) конечно, и существует счетиое 5 такое, что 5 = 5ор = Я, но 5 ф. 5ор. Вопрос о том, возможна ли такая ситуация, открыт; однако, существование такого тела Я кажется маловероятным.

В 1.3.1 дается несколько применений унитреугольных групп к построению примеров, дающих ответы на вопросы, отмечавшиеся в литературе. Доказывается существование стабильных несуперста-бпльных групп ограниченной экспоненты, что дает ответ на вопрос Дне. Болдуина и Дж. Саксла [20]. Строится пример нестабильной группы, имеющей определимую стабильную подгруппу индекса 2, что дает ответ на вопрос К. А. Мейрембекова [12].

В 1.3.6 изучаются унитреугольные группы иад несчетно категоричными кольцами и связанные с этим вопросы. Доказывается, что кольцо Я несчетно категорично, если и только если группа иТ„(Д) несчетпо категорична. Однако для любого кольца Я и любого п> 3 группа иТ„(Д) не является почти сильно минимальной.

Если кольцо Я счетно категорично, то С = иТ„(Л), если н только если С са ит„(5) для некоторого 5 = 7?. Вопрос о том, верно лп аналогичное утверждение для несчетно категоричного Я, отхсрыт. Доказывается следующее утверждение. Пусть кольцо Я несчетно категорично, Ло - простая модель теории ТЬ( Л). Тогда равносильны условия : Ст = иТ„(Л), если и только если С ~ иТ„(5) для некоторого 5 = Л; (а) иТн(/?о) — простая модель теории Т11(иТ„(Д)); (¡11) стандартная база I реализует главный тип в иТ„(Ло). Если вдобавок Я коммутативно пли целостно, то (Г)-(ш) выполнены. Для контраста отмстим, что для кольца 5 — (а) Б - простая мини-

мальная модель; (Ь) иТз(5) — минимальная, но не простая модель; (с) тип стандартной базы в иТз(5) главный.

Доказано, что тип стандартной базы в группе иТ„(Я) является главным, если и только если группы, элементарно эквивалентные иТ„(Я)— это в точности группы вида иТ„(5, (¡\,..., (¡п-\), где

= Я и коциклы </,- чисты. Таким образом, возможны две причины, по которым стандартная база в иТ„(Л) реализует неглавцый тип; в диссертации построены примеры, показывающие, что обе они встречаются в действительности. Эти примеры демонстрируют принципиальные отличия ситуации в унитреугольных группах от ситуации в нильтреугольных кольцах.

В этом же подразделе унптреугольные группы применяются для построения контрпримера, отвечающего на следующий вопрос К. А. Мсйрембекова [12]: верно ли, что если Н — определимая нормальная подгруппа в группе й, то для любого кардинала Л имеет место /(А, О) > /(А, С / II)'! Показывается, что существует несчетно категоричная группа С такая, что С^(С) не является несчетно категоричной.

В разделе 1.4 изучаются вопросы неразрешимости теорий унитреугольных групп. Основная проблема, изучаемая в 1.4.1, — вопрос о взаимосвязи степеней неразрешимости теорий ТЬ(иТ„(Л)) и ТЦД). Ввиду интерпретируемости Я в \]Т„(Я,щ,... ,//,¡-1) с параметрами, если ТЦД) наследственно неразрешима, то и Т11(иТ„(72,..., <7„_1)) тоже наследственно неразрешима. Поэтому

теории классов всех иТп-групп п квази-ЧТ,,-групп неразрешимы, хотя и рекурсивно перечислимы. Показано, что если Я — коммутативное или целостное ассоциативное кольцо, то теории ТЬ(Я) и ТЬ(иТ,,(/?)) рекурсивно изоморфны. Однако, в общем случае это не так. Доказывается, что для любых тьюринговых степеней с1 х и вг таких, что с!) < сЬ, существует ассоциативное кольцо /?, такое, что для любого п > 3 теория ТЬ(иТ„(Л)) имеет степень с11, а теория ТЫЛ) — степень сЬ. В частности, ТЬ(иТ,,(/?)) может быть разрешимой, даже если ТЬ(Л) неразрешима.

Проблема, изучаемая в 1.4.2, по постановке, казалось бы, далека от унптреугольных групп, однако с помощью соответствия Мальцева допускает простое решение. Для групповой формулы ф(х) алгоритмическая проблема первого порядка ?х ф(х) а конечно определенной группе — это проблема распознавания по кортежу из О, удовлетворяет ли он формуле ф(х) в С. Легко видеть, любая такая проблема имеет арифметическую тьюрингову степень. Дж. Сакер-доут [4С] высказал следующую гипотезу: для любой арифметической степени неразрешимости Ю существуют алгоритмическая проблема первого порядка Р и конечно определенная группа С такие, что Р имеет степень Ю для (?. Этот вопрос был стимулирован проблемой У. У. Буна, который предполагал, что тыорингова степень любой алгоритмической проблемы первого порядка в любой конечно определенной группе рекурсивно перечислила. Дж. Сакердоут опроверг это предположение, построив конечно определенную группу О и формулу ф(х) такие, что проблема '!х ф(х) имеет степень 0" в С. В диссертации гипотеза Сакердоута доказывается в следующей сильной форме. Пусть V = иТз(%). Эта группа является свободной двусту-пенно нильпотентной группой ранга 2 п конечно определена. Показывается, что для любой арифметической т-степенп с! существует групповая формула ф^х) с одной свободной переменной такая, что проблема ?хфл(х) имеет т-степень <3 в I/.

Вторая глава диссертации посвящена изучению связи экзистенциально замкнутых моделей теорий, подобных теории групп, с алгоритмическими проблемами.

Раздел 2.1 посвящен понятию теории, подобной теории групп. В 2.1.1 это понятие вводится следующим образом. Теория Т эффективной сигнатуры L называется подобной теории групп, если

(a) класс ее моделей — рекурсивно аксиоматизируемое квазпмно-гообразие со свойством совместного вложения;

(b) любая ее счетная модель вложпма в конечно порожденную модель в следующем сильном смысле: существует эффективная последовательность L-термов (ьп(х) : п < uj) такая, что для любой модели А теории Т с порождающими («„ : п < ш) существует модель В Э Л теории Т и кортеж Ь в В такие, что sft(l) = «„ для всех п;

(c) для Т справедлив аналог теоремы Хпгмэна: любая конечно порожденная рекурсивно определенная модель теории Т вложпма в конечно определенную модель теории Т;

(cl) для Т справедливо следующее утверждение, которое, как показано, является 'равномерной и эффективной' версией вложимости любой модели теории Т в Т-простую модель: для любых атомарных L-формул ф0(х),..., фп(х) можно эффективно найти позитивную примитивную L-формулу ф(х) такую, что для любой модели А теории Т н любого кортежа а в А равносильны условия:

(ii) существует модель В Э А теории Т такая, что В </>(â);

(е) для любого « > 1 можно эффективно найти позитивную примитивную ¿-формулу ф(х,у), где 7;, у — п-ки переменных, такую, что для любой модели А теории Т и любых ?г-ок a,b А равносильны условия:

(i) существует гомоморфизм (й) в (б), переводящий а в Ь,

(ii) существует модель В D А теории Т такая, что В ф(а, Ь). В 2.1.2 и 2.1.3 показано, что перечисленным условиям удовлетворяют теории групп, групп без кручения, полугрупп п ассоциативных алгебр над полем, конечно порожденным над простым подполем. В то же время теория ассоциативных колец не подобна теории групп; именно, для нее не вьгаолнепо (d), хотя все остальные свойства из списка (а)-(е) и выполнены.

Попутно устанавливается следующий факт, представляющий самостоятельный интерес: для любого и > 1 можно указать групповой терм ¡"„(х-,//), где Т. -■ и-ка, такой, что для любой группы С и любого отображения / : Ст'" —> С существуют группа Н > С и кортеж Ъ. в Я такие, что /(у) = ¡-н(д,к) для любого у 6 С". Аналогичное свойство было известно для полугрупп [3]. Основываясь на работе автора [61] и отвечая на его вопрос, У. Ходжес [31] доказал аналог этого результата для класса всех конечных групп.

В разделе 2.2 релятпвизованная теорема Хигмэна, доказанная Циглером для групп [54], обобщается на теории, подобные теорпп групп: если А и В — конечно порожденные модели теории Т, подобной теории групп, и Л С В, то В рекурсивно определена над А, если и только если существует модель С теории Т такая, что Б С С, и С конечно определена над А-

В разделе 2.3 изучаются конечно порожденные подмодели экзистенциально замкнутых моделей. Конечно порожденная модель универсальной теории Т называется неизбежной для Т, если она вло-жима в любую экзистенциально замкнутую модель теории Т. Теорема Ноймана-Макинтайра утверждает, таким образом, что неизбежные группы — это в точности конечно порожденные группы с разрешимой проблемой равенства слов. В 2.3.1 изучается понятие неизбежной модели. Очевидно, конечно порожденная модель неизбежна, если и только если бескванторный тип ее порождающих реализуется в любой экзистенциально замкнутой модели. Следующее утверждение описывает такие типы п является экзистенциальной версией классической теоремы об опускании неглавных типов; его доказательство основано на идее [38]. Пусть (¡(х) — бескванторный тип индуктивной ¿-теории Т со свойством совместного вложения. Тогда ц(х) реализуется в любой экзистенциально замкнутой модели теории Т, если и только если существует экзистенциальная (равносильно, примитивная) ¿-формула ф{х) такая, что ф(х) совместна с

Этот результат позволяет охарактеризовать неизбежные модели для любого квазпмногообразпя Л счетного языка со свойством

совместного вложения. Пусть В — структура из Л, и 5 С £>(#). Гомоморфизм этой структуры называется 5-гомоморфизмом, если он сохраняет истинность предложений из 5. Доказывается, что конечно порожденная модель Л из Л неизбежна для Л, если и только если существуют конечно определенная в Л модель В Э Ли конечное й1 С П(В) такие, что ограничение на А любого ¿-гомоморфизма модели В на модель пз Л является мономорфизмом.

Следующий результат обобщает теорему Ноймана-Макпнтайра: конечно порожденная модель теории Т, подобной теории групп, неизбежна для Т. если и только если имеет разрешимую проблему равенства слов. Отметим, что в доказательстве этого результата свойство (е) определения теории, подобной теории групп, не используется. Для ассоциативных колец этот результат неверен: строится конечно порожденное ассоциативное кольцо с разрешимой проблемой слов, не являющееся неизбежным. Доказательство того, что построенное кольцо не является неизбежным, базируется на данном выше критерии неизбежности. Последний результат показывает, что в теореме Ноймана-Макинтанра и ее аналогов ключевую роль играет не только свойство Хпгмэна (для ассоциативных колец оно имеет место!), но и свойство (с1).

Показывается, что если Л — квазимногообразие счетного языка, в котором число конечно порожденных моделей не более чем счетно и каждая конечно определенная модель финитно аппроксимируема, то Д имеет локально конечную экзистенциально замкнутую модель; поэтому, если вдобавок сигнатура конечна и Л имеет свойство совместного вложения, то неизбежные в Л модели — это в точности конечные модели из Л. Это обобщает результаты Са-расино [48, 49] о существовании локально конечных экзистенциально замкнутых моделей в классах метабелевых н двуступенно ниль-потентных групп. Отметим, что условиям теоремы удовлетворяют классы коммутативных колец, коммутативных колец без ннльпо-тентов, коммутативных полугрупп, произвольные подмногообразия многообразий групп 2191,,.

В 2.3.2 изучается связь (¡^-сводимости с экзистенциально замкну-

тыми моделями. Для А, В С и> говорят, что Л ¿¿-сводится к В (символически, Л <q В), если Л сводится к В по перечислимости и существует F С сводимое к В по перечислимости и такое, что Va; (х 6 А « {у : (х,у) £ F} С В). Легко ппдеть, что Л <q В влечет А <т В; известно, что обратное неверно уже для рекурсивно перечнелпмых А, В.

Доказывается, что для конечно порожденных моделей Ль А а теории Т, подобной теории групп, равносильны условия: (i) А\ вложи-ма в любую экзистенциально замкнутую модель теории Т, содержащую А г- (ii) проблема равенства слов для Л[ Q-сводима к проблеме равенства слов для A-¿- Если A-¿ неедннпчная модель, то эти условия равносильны следующему условию: (iii) существует модель Т Э А[ * А-2 теории Т, конечно определенная над A-i, любой гомоморфизм которой в модель теорпп Т, являющийся мономорфизмом на подмодели A-¿, является мономорфизмом п на подмодели А\.

В разделе 2.4 предлагается некоторый достаточно общий подход к нахождению алгебраических характерпзаций разрешимости алгоритмических проблем.

Пусть Т — теория рекурсивного языка L, и S — рекурсивное множество L-предложений. Мы говорим, что проблема совместности с Т для S разрешима, если множество 5Т всех предложений из S, совместных с Т, рекурсивно.

Многие известные алгоритмические проблемы в алгебре могут быть сформулированы как проблемы совместности для подходящих Т и S. Многочисленные примеры этого приведены п 2.4.1. Для конечно определенных групп таковы проблема равенства слов, проблема вхождения в подгруппы, проблема вхождения в центр, проблема порождения, проблема порядка элементов; для класса конечных ко-представленнй таковы проблема тривиальности, проблема коммутативности, равномерная проблема равенства слов. Во всех перечисленных примерах Т — теория групп, а соответствующее S можно выбрать состоящим пз экзистенциальных хорновекпх предложений.

В 2.4.2 дается следующий критерий разрешимости проблемы совместности с Т для S. Пусть L-теория Т подобна теории групп,

5 - рекурсивное множество экзистенциальных хорновских /.-предложений. Тогда равносильны три условия: (1) проблема совместности с У для 5 разрешима; (и) существует примитивное 1,-пред-ложение ф, совместное с Г и такое, что Т, ф Н Бт', (111) любая экзистенциально замкнутая модель теории Т имеет конечно порожденную подмодель, являющуюся моделью 5у.

Варьируя Т и 5, можно автоматически получать характеризации для конкретных алгоритмических проблем: в 2.4.2 даются многочисленные иллюстрации из теории групп. Здесь мы приведем лишь два примера.

Для конечно определенной группы С равносильны три условия: (¡) С имеет разрешимую проблему равенства слов; (11) существует конечная система уравнений и неравенств такая, что С резпдуаль-но вложима в любую группу, в которой эта система имеет решение; (111) любая экзистенциально замкнутая группа имеет конечно порожденную подгруппу, в которую б резидуально вложима. Отметим, что для конечно порожденных рекурсивно определенных групп, вообще говоря, это неверно: именно, (н)х>(1), (ш)*>(1). Таким образом, конечная определенность здесь существенна; этим данная ха-рактеризация принципиально отличается от характерпзаций Буна-Хигмэна и Ноймана-Макинтайра.

Если К — рекурсивный класс конечных групповых копредставле-ний, то равносильны условия: (1) для К разрешима проблема тривиальности; (и) существует конечная совместная система уравнений и неравенств такая, что любая неединпчная группа с копредставленп-ем из К имеет неединпчный гомоморфизм в любую группу, в которой эта система имеет решение; (111) любая экзистенциально замкнутая группа имеет конечно порожденную подгруппу такую, что любая неединпчная группа с копредставленпем из К имеет неедшшчныи гомоморфизм в эту подгруппу.

Аналоги этих характерпзаций имеют место для любой теории, подобной теории групп.

Литература

[1] Белсградек 0.13. Об алгебраически замкнутых гриппах // Алгебра и логика.

- 197'). - 'Г. 13, N 3. - С. 239 255.

[2] Белсградек О. И- Алгебраически замкнутые группы: Лис...канд. фих-мат. наук: 01.0l.0G. - Новосибирск, 1974. - 101 с.

[3] Беляев В. Я. Об алгебраически замкнутых полугруппах // Сиб. мат. жури.

- 1977. - Т. 18, N 2. - С. 32-39.

[4] Беляев В. Я. Подколъца конечно определенных ассоциативных колец // Алгебра н логика. - 1978. - Т. 17, N С. - С. 627-638.

[5] Беляев В. Я. Вложимостъ рекурсивно определенных инверсных полугрупп а конечно определенные // Сиб. мат. жури. - 1984. - Т. 25, N 2. - С. 50-54.

[G] Ершов 10. J1. Об элементарных теориях групп // Докл. АН СССР. - 1972.

- Т. 203, N б, С. 1240 1243.

[7] Кейслср Г., Чэн Ч. Ч. Теории моделей. - М.: Мир, 1977. - 611 с.

[8] Кузнецов А. В. О проблемах тождества и функциональной полноты для алгебраических систем // Тр. 3 Всесоюзн. матем. съезда. - М.: Наука, 195С.

- Т. 2,- С. 145-146.

[9] Кукиц Г. II. Подалгебры конечно определенных лиевых колец // Алгебра и логика. - 1979. - Т. 18, N 3. - С. 311-327.

[1Ü] Мальцев А. И. Об одном соответствии между кольцами и группами Ц Мат. сб. - 19G0. - Т. 50, N 3. - С. 257-266.

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

[12] Мейрембеков К. А. О сохранении стабильности при конечном расширении группы // Алгебра и логика. - 1986. - Т. 25, N 3. - С. 273-291.

[13] Мурский В. JI. Изоморфная вложимостъ полугруппы с псречислимым множеством определяющих соотношении о конечно определенную полугруппу И Мат. заметки. - 1967. - Т. 1, N 2. - С. 217-224.

[14] Мясников А. Г., Ремесленников В. II. Формульность множества мальцев-ских баз и элементарные теории конечномерных алгебр. I // Сиб. мат. жури. - 1982. - Т. 23, N 5. - С. 152-167.

[15] Мясников А. Г., Ремесленников В. II. Формульность множества мальцев-ских баз и элементарные теории конечномерных алгебр. II // Сиб. мат. журн. - 1983. - Т. 24, N 2. - С. 97-113.

¡10] Носков Г. А., Ремесленников В. II., Романьков В. А. Бесконечные группы // Итоги науки и техн. ВИНИТИ. Алгебра. Топол. Гсом. - М., 1979. - Т. 17, С. 65-157.

[17] Ремесленников В. П., Романьков В. А. Теоретико-модельные и алгоритмические вопросы теории групп // Итоги науки и техн. ВИНИТИ. Алгебра. Топол. Геом. - М., 1983. - Т. 21, С. 3-79.

[18] Толстых В. А. Теории бесконечномерных линейных групп: Дцсс...каид. фнэ,-мат. наук: 01.01.06. - Кемерово, 1992. - 112 с.

[19] Baldwin J. Т. Stability theory and algebra // J. symbol, log. - 1979. -Vol. 44. -P. .599-008.

[20] Baldwin J. Т., Saxl J. Logical stability in group theory // J. Austral. Math. Soc. - 1976. - Vol. 21. - P. 2G7-27C.

[21] Boone W. YV. Between loyic and group theory // Proc. 2nd intern, conf. theory of groups, Canberra, 1973. - Berlin a.o., 1974. - P. 90-102. - (Lecture notes in mathematics, 372)

[22] Boone W. W., Higman G. An algebraic characterization of groups with soluble word problem // J. Austral. Math. Soc. -1974. - Vol. 18, N 1. - P. 41-53.

[23] Boone W. W., Higman G. An algebraic chamcterization of groups with soluble order problem // Proc. Logic Colloq.' 73, Bristol, July 1973. - Amsterdam: North-Holland. - 1975. - P. 53-54.

[21] Borovik A., Nesin A. Groups ojfinite Morley rank - Oxford: Clarendon Press, 1994. - 422 p. - (Oxford logic guides, N 26)

[25] Evans T. Word problems // Bull. Amer. Matli. Soc. - 1978. - Vol. 84, N 5. -P. 789-802.

[26] Griincnvvald K., Haug F. On stable torsion-free nilpotuit groups // Arch. math, log. - 1993. - Vol. 32. - P. 451-462.

[27] Hickin K., Macintyre A. Algebraically closed groups: embedding and ccntralizers 11 Word problems II. - Amsterdam a. o.: North-Holland, 1980. - P. 141-155. (Studies in logic and foundations of math., 95)

[28] Higman G. Subgroups of finitely presented group // Proc. Royal Soc. London, Ser. A. - 1961. - Vol. 262. - 455-475.

[29J Higman G., Scott E. Existentially closed groups. - 1988. - Oxford: Clarendon Press. - 156 p. - (London Math. Soc. monographs. New ser., N 3)

[30] Hirschfeld J., Wheeler W. II. Forcing, arithmetic, division rings. - Berlin: Springer, 1975. - 266 p. (Lecture notes in mathematics, 454)

31] Hodges W. finite ertensions of jinile groups// Models and sets; Pro«'./ Logic Colloquium's:!, Aaben, 1983. - Berlin: Springer, 198-1. - I». li)3 20G (Lecture notes in niatlicmalics, 1103).

32] Building models by games. Cambridge: Cambridge Univ. Picks, 1985. 311 c. (London Mal,li. Soc. student texts, 2).

33] Hodges W. Model theory. - Cambridge: Cambridge Univ. Press, 19<J3. - 772 c. (Encyciopcdia of mathematics and its applications, Vol. <¡2).

34] Kaye R. W., Macpherson II. D. Automorphisms oj first order structures. -Oxford: Clarendon l'jess, 1994. - 400 p.

35] Lachlan A. (I. Theories with a finite number of models in an uncountable power arc categorical // Pacif. J. Math. - 1975. - Vol. 61. - P. 465-481.

[30] Leincn F. Existentially closed, groups in specific classes. - Mainz, 1994. - 11 p. (Preprint-reiiie des fachbereiclis inatlieinatik / Johannes Gutenberg Uiiiversitât Mainz, Nr. 22)

Л7] Macintyre Л. On algebraically closed groups // Ann. Math. - 1972. - Vol. 96. -P. 53- 97.

38] Macintyre A. Omitting quantifier-free types in generic structures // J. symbol, log. - 1972. - Vol. 37. - P. 512-520.

;39] Alarm A. A note on recursively presented and co-recursively presented groups // Bull. London Math. Soc. - 1982. - Vol. 14. - P. 112-118.

40] The model theory of groups / Ed. by A. Nesin and A. Pillay. - Notre Dame, Indiana: Univ. Notre Dame Press, 1989. - 209 p. (Notre Dame math, lectures, 11).

41] Neumann 1). II. The isomorphism problem for algebraically closed groups // Word problems. - Amsterdam a. o.: North-Holland, 1973. - P. 553-562.

42] Poizat B. Groupes stables: Villeurbanne: iNur al-Mantiq wal-Ma'rifah, 1987. -215 p.

43] Rips E. Another characterization of finitely generated groups with solvable word problem // Bull. London Math. Soc. - 1982. - Vol. 14. - P. 43- 44.

44] Rose B. The Rj-catcgoricity of strictly upper triangular matrix ring over algebraically closed fields // J. symbol, log. - 1978. - Vol. 43. - P. 250-259.

45] Sabbagh G. Curacterisation algébmique des groupes de type fini ayant un problème de mots résoluble. [Théorème de Boone-Iligman, travaux de B. //. Neumann et Macintyre] // Séminaire Bourbaki. - 27e année, 1974/75, nu 457. -Berlin a. o.: Springer, 1976. - P. 61-80. - (Lecture notes in mathematics, 514).

46] Saccrdote G. S. On a problem of Boone // Math. Scaiid. - 1972. - Vol. 31. -P. 111-117.

[47] Sacerdote G. S. The Boone-IHgman theorem and the conjugacy problem // J. algebra. - 1977. - Vol. 49, N 1. - P. 212-221.

[48] Sarac.ino D. Wraith products and existentially complete solvable ¡/roups // Trans Anicr. Math. Soc. - 1974. - Vol. 197. - P. 327-339.

[49] Saracino U. Existentially complete nilpolcnt groups // Isr. J. Math. - 1976. Vol. 25. - P. 241-248.

[50] Videla С. K. Definability in unipotent matrix group and in fields of non-zcr characteristic: Thcs...doct. philosophy (mathematics). - Rutgers Univ., 1986. 125 p.

¡51] Videla C. R. Оii the model theory of the ring NTn(R) // J. pure appl. algebrf

- 1988. - Vol. 55. - P. 289-302.

[52] Wheeler W. Model theory of strictly upper triangular matrix rings // J. syrabo log. - 1980. - Vol. 45. - P. 205-200.

[53] Ziegler M. Ahjebraisth abgeschlossenc gruppen: IlabilitationsKchrifl. -Tech. Uiii' Berlin, 1976.

[54] Ziegler M. Algcbraisch abgeschlossenc gruppen // Word problems II. Amsterdam a. o.: North-Holland, 1980. - P. 449-576. (Studies in logic an foundations of math., 95)

Публикации автора по теме диссертации

[55] Велеградек О. В. Стабильная ш-иестабилъна! группа ограниченной зкет непты II Математика и механика, ч. I, Математика: Тез. докл. / VI Каза: межвуз. науч. коиф. но мат. и мех., иосвящ. С0-летшо Вел. Окт. Соц. Реп Алма-Ата, окт. 1977 г. - Алма-Ата, 1977. - С. 127.

[50] Велеградек О. В. Элементарные свойства алгебраически замкнутых груi // Fund. Math. - 1978. - Т. 98. - С. 83-101.

[57] Велеградек О. В. Алгебраические эквиваленты разрешимости теоретик групповых алгоритмических проблем // Снб. мат. жури. - 1979. - Т. 20, N

- С. 954-963.

[58] Велеградек О. В. Разрсхтшые фрагменты универсальных теорий и экз стенциальпо замкнутые модели //5 Всесоюзн. коиф. по мат. логике, Нов сибирск, нояб. 1979 г.: Тез. докл. - Новосибирск, 1979. - С. 15.

[59] Велеградек О. В. То же // Снб. мат. жури. - 1980. - Т. 21, N 6. - С. 196-20

[60] Велеградек О. В. О классах алгебр с внутренними отображениями t 1С Всесоюзн. алгебр, коиф., Лешшград, септ. 1981 г.: Тез., ч. 2. - Лени град, 1981. - С. 11-12.

[01] Белеградек О. Б. Классы алгебр с внутренними отображениями // Исследования по теоретическому программированию. - Алма-Ата, 1981. - С. 3 10.

[62] Белеградек О. Б. О теории унитреугольной группы над безатомным р-коль-цом // Г) Всесоюзи. сими, но теории колец, алгебр и модулой, Новосибирск, септ. 1982 г.: Тсч. сообщ. - Новосибирск, 1982. - С. 18 19.

[63] Белеградек О. В. Нестабильная группа с определимой стабильной подгруппой индекса 2 // 19 Всесоюзл. алгебр, коиф., Льнов, септ. 1987 г.: Тез. сообщ., ч. 1. Львов, 1987. - С. 30.

[04] Белеградек О. В. О мильц< иском соошиешетиии между кольцами а группами // Междуцар. коиф. ло алгебре, поспят, памяти А. И. Мальцева, Новосибирск, авг. 1989 г.: Тез. докл. по теории колец, алгебр и модулей. Новосибирск, 1089. - С. 20.

[65] Белеградек О. В. О моделях теории упитреугольпых групп // 10 Всесоюзи. коиф. по маг. логике, Алма-Ата, нояб. 1990 г.: Тез. докл. -- Алма-Ата, 1990.

- С. 19.

[66] Белеградек О. В. Теории упитреугольпых групп // И Межреси. коиф. по мат. логике, Казань, окт. 1992 г.: Тез. сообщ. - Казань, 1992. - С. 18.

[67] Белеградек О. В. Соответствие Мальцева и неразрешимость // Сиб. мат. жури. - 1992. - Т. 33, N 4. - С. 24- 29.

[68] Белеградек О. В. Унитреугольные группы и неразрешимость // Из», вузов. Математика. - 1993. - N 4(370). - С. 19-22.

[69] Белеградек О. В. Степени неразрешимости алгоритмических проблем 7iep-оого порядка в конечно определенных группах // Междуцар. коиф. но мат. логике, посвящ. 85-летию со дня рожд. А. И. Мальцева, Новосибирск, нояб. 1994.: Тез. сообщ. - Новосибирск, 1994. - С. 20-21.

[70] Belegradek О. V. An algebraic characterization of groups with solvable occurence problem // Notic. Amer. Math. Soc. - 1977. - Vol. 24, N 4. - ]>. A-393.

[71] Belegradek О. V. An algebraic characterization of groups with solvable decision problems // Notic. Amer. Math. Soc. - 1977. - Vol. 24, N 5. - P. A-436.

[72] Belegradek О. V. An example of a stable but not supcrstable group of bounded exponent // Notic. Amer. Math. Soc. - 1978. - Vol. 25, N 3. - P. A-3C0.

[73] Belegradek О. V. On Ho-stable it0-categorical theories // Intern, congr. mathematicians, Warszawa, Aug. 1983: Short communications, part I. - Warszawa, 1983.

- C. 5.

[74] Belegradek О. V. On the Mal'cev correspondence between rings and groups // Proc. 7tli Easter conf. on model theory, Wendisch-Rietz, March 1989. -Seminarbericht Nr. 104, Sektion Mathematik, Ilumboldt-Universitat zu Berlin.

- Berlin, 1989. - P. 43-57.

[75] Belegradek О. V. The Mal'cev correspondence revisited // Proc.. Intern, conf on algebra dedicated to the memory of Л. 1. Mal'cev, Novosibirsk, Aug. 1989. -Providence, Rhode Island: Amer. Math. Soc., 1992. - P. 37-59. - (Coiilemporar mathematics; Vol. 131).

[76] Belegradek О. V. Groups elementarily equivalent to UT3(K) // Proc. 8th Easte conf. Oil model theory, Wendisch-Rietz, April 1990. - Semmarberichl Nr. 11С Sektion Mathematik, Humboldt-Universität zu Berlin. Berlin, 1990. P. 31-3S

[77] Belegradek О. V. On the first order theory of a unitriangular group // Logi

o.ii,. inn 11 u: 1..1.. nvm. -----*--r .------ 1 -------1—1 1^... ru

JU, 1 It-lollllvl, tl U1J l.J./U. лианные VJ1 jiUJJ^lO, 4. 13JIHIJ\Jl. T J*

N 3. - P. 1121.

[78] Belegradek О. V. On spectrum Junctions of unitriangvlar groups // Сон.-фраш icojmoKB. по теории моделей, Караганда, июнь 1990 г.: Тез. докл. - Караганде 1990. - С. S-9.

[79] Belegradek О. V. On the axiomatizable closure of the class UT-) // Междуиа конф. no алгебре, яоевящ. намяты А. И. Ширшова, Барнаул, авг. 1991 г.: Те докл. по теории групп. - Новосибирск, 1991. - С. 138.

[80] Belegradek О. V. Some model theory of unitriangular groups // Modelltheor lagung, Oberwolfach, Лап. 1992. - Mathematisches Forschuuginstiti Oberwolfach, 1992. - Tagungsbericht 3/1992. - P. 5-6.

[Sl] Belegradek О. V. Some open problems in the model theory of unitriangul groups // Proc. 10th Easter conf. on model theory, Wendisch-ltietz, April 199 - Scminarbcricht Nr. 93-1, Fachbereich Mathematik, Humboldt-Universität : Berlin. - Berlin, 1993. - P. 9-13.

[82] Belegradek О. V. Quasiunitriangular groups // J. symbol, log.- 1993. - Vol. E N 1. - P. 205-218.

[83] Belegradek О. V. On the spectrum function of a quotient group // Третья Me: дунар. конф. по алгебре памяти М. И. Каргаполова, Красноярск, авг. 1993 Сб. тез. - Красноярск, 1993. - С. 385.

[84] Belegradek О. V. lliyman's embedding theorem in general setting and its с plication to existentially closed algebras // Modelllheorie tagung, Oberw< fach, Jan. 1994. - Mathematisches Forschunginstitul Oberwolfach, 1994. Tagungsbericht 1/1994. - P. 10-11.

[85] Belegradek О. V. The model theory of unitriauguiar groups jj Ann. pure ap log. - 1994. - Vol. 68. - P. 225-261.