Введение к работе
',.-" :--А ктуальносгь темы. В 30-х годах в работах К.Гёделл, А.Чёрча, А.Тьюринга, Э.Поста и в 40-50-х годах в работах А.А.Маркова, А.Н.Колмогорова и В.А.Успенского (си. библиографию а [б] , Гз?3)били сформулированы и изучены различные м&теыатнческие версии понятия алгоритма. В результате этого в. иатеыатике оформилось плодотворное направление - исследование алгоритмических проилеи, то есть проблем существования алгоритмов для реиения массовых задач из того или иного класса. Среди таких проблей стали различать разрешимые (соответствующий алго-рити существует) и неразрешимые (такого алгоритма нет).
Если разрешимые алгоритмические проблемы под другими именами известны в математике с ее возникновения, то первые нераэ-решншэ алгоритмические проблемы были обнаружены лють в 30-х годах в математической логике. Затеы выяснилось, что такие проблемы есть и в других областях математики и прежде всего в алгебре: в 1947 году А.А.Марковым и, независимо, Э.Постом была доказана неразрешимость проблемы равенства в полугруппах, а в 1952 году П.С.Новиковым бил получен знаменитый результат о неразрешимости проблемы равенства в группах. Эти результаты решали стародавние проблемы, позтавлешшв, соответственно, А.Туэ в 1914 году и М.Дэном в 191I году (подробности см. в [2] , [3J, [6] , [іО] , [37J ,.[38] ).
К началу 50-х годов благодаря основополагающим работам А.И.Мальцева и А.Тарского сформировалась новая математическая дисциплина - теория моделей. К настоящему времени вышел целый ряд посвященных ей книг, среди которых особо выделим монографии А.И.Мальцева [35] , А.Робинсона JJ39J , Г.Кейслера и Ч.Чена jiio] , Ю.Л.Ершова ^2] , коллектива авторов Г43І , Ю.Л.Ершова и Е.А.Палютина Г^З] .
Одним из центральных вопросов теории моделей стал впервые сформулированный А.Тарским вопрос о разрешимости элементарных теорий. Пусть jC - класс алгебраических систем не более чем счетной сигнатуры G" ; & - совокупность всех tT-формул логики первого порядка; УС - элементарная теория класса УС , т.е. совокупность всех предложений из , истинных на каясдой системе из УС . Пусть, далее, о; и? —=* гёделева нумерация из ^22J и «. = ?-»,
Элементарная теория < і& называется
- A -р^чз^ешимсй, если множество номеров 'Ч-б^Зу рекурсивно, и дедаз^' рушимой D пртивном случае.- Иными словами, 5 разрешима . (неразрешима), если разрешима (соответственно, неразрешима) алгоритмическая проблема вхождения произвольной формули из в множество %С '.
ПРОБЛЕМ РАЗРЕШИМОСТИ ЭЛЕМЕНТАРНОЙ ТЕОРИИ (А.Тарский): для донного класса $ алгебраических систем установить разра-шима ли его елементарная теория Ё&.
Работы А.И.Мальцева и его учеников вместе с работаш других математиков показали, в частности, что класс с рглреэкыой елементарной теорией - довольно редкое явление. Этот тезиг сфор?<сулирован и обоснован в обзорной работе (jSj . Вместе с тем, ещё в 50-х годах было замечено, что, например, такая классическая алгоритмическая проблема, как проблема равенства с данном классе -л? , моятет бить переформулирована как проблема разрешимости подходящей ограниченной теории класса & . Указанные два обстоятельства привели в середине 60-х годов к резкому росту числа исследований по разрешило ста ограничении* теорий. Это побудило А.И.Мальцева в явном виде сформулировать в \34~\ естественно возникашг/го nporpasmy алгоритшгчєскш: исследований. Пусть / - некоторый язык логики первого порядка сигнатуры s- , т.е. / " ё . Для класса $С черезZ.& .обозначим его ограниче.'їнуя языком L теорию первого порядка или L. -теорию, т.е множество L<7&&.
ПРОГРАШ ІІССЛЕДОВйНШ РАЗРЫ1Ж0СТИ'ТЕОРИЙ ПЕРВОГО. ПОРЯДКА (А.И.Ыальцеп [343 ^* Для наиболее важных классов ^ и наиболее интересных языков L. выпенить разрешимость теории L Ж- .
В програ*(ыу Пальцева вписывается большинство результатов по алгоритмическим проблемам алгебры и, в частности, указанные выше теоремы Маркова-Поста и Новикова. Отметим ещё ряд относящихся сюда фундаментальных результатов. Разрешимы элементарные теории полей действительных и комплексных чисел (А.Тар-екчй); неразрешима элементарная теория поля .рациональных чисел (Ю.Робинсон); разрешима элементарная теория многообразия всех абелевых групп (В.Шмелёва); разрешима элементарная теория класса зсех дистрибутивных решёток с относительными дополнениями (Ю.Л.Ершов^; разрешима проблема равенства в многообразиях коммутативных и антикоммутативных алгебр над конструктивным полем _ и,стало быть, разрешимы универсальные теории этих многообразие
(А.И.Ширшов); разрешима проблема равенства в полугруппах с одним несократимым слепя и справа определяшим соотношением (СИ. Ацян); существует линейно упорядоченное множество с нгрязрс-ши'.-иП элементарной теорией, для которого любая теория с ограниченным числом перемен кванторов разрешима (Ю.Л.Ершов); неразрешима диофянтовя теория кольца целых чисел (Ю.В.Мятиясспич); неразрешима проблема равенства в алгебрах Ли (Л.А.Бокуть);' разрешима проблема совместности систем уравнений в свободном моноиде конечного ранга и разрешимы позитивная и универсальная теории свободной группы конечного ранга (Г.С.Мяканин) (см.ра-
Й".% %i %?9} м м о* -&о --ВД &1
Исследования по программе Мальцева занимают одну из центральных позиций в теории моделей. Они тесно связнны с целым рядом разделов математики. Среди таких разделов конструктивные модели (см. монографию Ю.Л. ЕрісовяГ22~] и стятью С.С. Гончарова IJ7J ), неклассическис логики (см. работу В.В.Рыбакова Г/ц}) , комбинаторная теория алгебраических систем (см. статьи Р.И.Григорчука [18]).
В настоящее время можно считать, что программа Мальцева в значительной степени выполнена (см. обзоры[3], б], [іО], Г37], [38],[б0]и библисграфио к ним). Поэтому актуальной, ня нага взгяд, становится ряэвиваггаая её
ПРОБЛЕМ ОПИСАНИЯ РАЗРЕШИЛИ ТЕОРИЙ: для данного класса^ алгебраических систем и семейства языков п описать все разрешимые теории /. Л ДЛЯ L& п.
Рассматривая проблему, удобно считать, что семейство яэыр ков Н упорядочено включением и объединение всех входящих в него языков равно Є . Подобные семейства будем называть ие^я^х^»^и^язьгков. Иерархия языков И определяет для данного класса УС алгебраических систем ие]эакию_т0_рий
JfX*?-/L&/L* И}.
Теперь проблема описания разрешимых теорий приобретает геометрический оттенок:она требует описать "разрешимые" точки диаграммы частично упорядоченного множества НуС . При этом мы замечаем, что особую роль должны играть точки, лежащие на границе разрешимости или, точнее, составляющие эту границу. Это наблюдение позволяет дать следующее естественное и при-
_ 6-
нципиалыюе для наших рассмотрений
ОПРЕДЕЛЕНИЕ. ТеорияL^C^-H^ называется ^-Щптеско^, если она является минимальной среди неразрешимых теорий в иерархии
Понятие Л'-критической теории является, по существу, математической версией "границы разрешимости" \ТП\ . Кроме того, оно играет центральную роль при изучении проблемы описания разрешимых теорий. А именно, справедливо следующее очевидное
ЗАМЕЧАНИЕ. Пусть иерархия языков И рекурсивна и фундиро
ванна, т.е. рекурсивны множества n,(L) для любого/Є/У и ин
дексное множество семейства t'n~(t~)/ (_ Є И j C^-U t
а частично упорядоченное множество И удовлетворяет условию
минимальности. Тогда иерархия теорий НУС фундирование и в не
разрешимость наследуется для подтеорий, а неразрешимость - для
надтеорий. В частности, теорияL$CgH%разрешима тогда и то
лько тогда, когда она не включает ни одну //-критическую теории)
класса {fc .
Стало быть, в случае рекурсивности и фундировэнности иерархии н проблема описания разрешимых теориД сводится к еле-' дующей существенно более обозримой проблеме.
ПРОБЛЕМА ОПИСАНИЯ КРИТИЧЕСКИХ ТЕОРИИ: для данного класса ^алгебраических систем и иерархии// описать Dee И -критические теории класса jC* .
Цель работы. Развить направление, посвященное изучении проблемы описания критических теорий, и исследовать тесно связанные с ней вопросы, касающиеся иерархии языков первого порядка и степеней неразрешимости теорий. 3 качестве класса (/с мы будем рассматривать многообразия 0 ,?&,,С , ^f, &С всех полугрупп, всех колец, всех коммутативных, антикоммутатив ных,лиевых и ассоциативных колец, соответственно, к одноэлеме? ные классы, состоящие из алгебр, свободных в указанных многооС резнях и заданных в многообразиях ІҐ и Ht. одним определяющим соотношением. Роль иерархии Н будет играть определяемая ниже достаточно богатая схемно-альтернативная иерархия SA и ее "антипод" - тривиальная иерархия Є = 1 ь},
Общая методика исследованил ФСлючевую роль при доказательстве основных результатов работы і рают методы интерпретаций и базирующаяся на них схема описати
критических теорий, названная нами J^er^oj^^e^ejiHfl_jvo_jieap-хни. Суть последнего в следующем: (а) отыскивается ряд несравнимее в данной иерархии неразрешимых теорий исследуемого класса; (б) доказывяется, что любая теория, покриваеиая в иерархии хотя бы одной из найденных в (а^, разрешима; (в) показывается, что любая теория из нашей иерархии, не включающаяся строго ни п одну из найденных в (а^ теорий, неразрешима тогда и только тогда, когда она включает хотя бы одну из них. Из пунктов (б) и (в) непосредственно вытекает, что теории, найденные в (а), и только они являются критическими теориями данного класса.
В доказательстве теореи 1-4, кроме того, активно исполь-1 зуется комбинаторная техника работы с ассоциативными и кеас-социативными словами.
Научная новизна. Новой является прежде всего, постановка проблемы описания критических теорий. Она определяет комплексность рассмотрения алгоритмических проблем, при которойметоды доказательства разрешимости органично переплетаются с методами получения неразрешимости. Новыми являются и все основные результаты, а такие значительная часть аппарата исследований.
Практическая и теоретическая ценность. Работа носит теоретический характер. Полученные результаты решают некоторые вопросы, отмечавшиеся в литературе, обобщают ряд известных фактов или придаст им новое звучание. Развиваемый в работе подход позволяет включить предшествующие результаты по программе Мальцева в единую' для данного класса алгоритмическую картину, оценить степень завершенности этой картины в зависимости от определяемого иерархией "масштаба" и наметить возможные пути ее завершения. Формирова*-ние проблематики обсуждаемого подхода позволило вычленить ряд проблем для дальнейшего исследования, Результаты и методы работы уже находят применение в не вошедших в диссертацию публикациях автора, а также в статьях его учеников (см., например, [V] , [8] , [II] - [іб] , [29] , [ЗО] , [42] ). Они могут быть ігйпользованн и отчасти уже используются при чтении специальных курсов и при подготовке монографий и учебников; укажем в связи с этим обзорную статью [_60] , учебное пособие [59] и п. 8.2 в 44}
&
г*.
55 .
?
>
со я
|
^
&
-й
Е?
S го t- со
Е?
|>
%
&
Г,
ция изложена на 224 страницах и состоит из введения и мптирох глав. В главе I представлена техническая база работы, главы II и Ш посвятаекы S/J-крипгчсским и Zr-критическим теориям, соответственно, в главе ІУ исследуются иерархии КЧК самостоятельные объекты и изучаются степени неразрешимости теорий. Библиография состоит из 88 наименований.