Критические теории первого порядка тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

II о

м О ^

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

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

вшннн •

1)рий Михайлович КРИТИЧЕСКИЕ ТЕОРИИ ПЕРВОГО ПОРЯДКА

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

Автореферат диссертации на соискание учёной степени доктора физико-математических наук

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

Работа выполиона на кафедре алгебры и геометрии Уральского ордена Трудового Красного Знамени государственного университета им. А.М.Горького

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

док.тпр физико-математических наук профессор Григорчук Р.И. доктор физико-математических наук Макашн Г.С. доктор физико-мьтематических наук Морозов А.С

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

Институт теоретической и прикладной математики АН Казахской CGP

Защита состоится " /У " 1992 г. в

час. на заседании специализированного совета Д 002.23.01 при Институте математики СО АН СССР по адресу: 630090, Новосибирск, 90, Университетский проспект, 4

С диссертацией ^ожно ознакомиться в библиотеке Институтг математики СО АН СССР '

Автореферат разослан 1992 г.

Ученый секретарь специализированного соната

кандидат физико-математических наук " В.Г.Скоснрский

I - 3 -

1 ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

.-"■ •' -Л ктуальносгь темы. В 30-х годах в работах К.Гёделл, А.Чёрча, А.Тьюринга, Э.Поста и в 40-50-х годах и работах А.А.Маркова, А.Н.Колмогорова и В.А.Успенского (си. библиографии а [б] , [3?])были сформулированы и изучены различные математические версии понятия алгоритма. В результате этого в. математике офоралось плодотворное налравление - исследование алгоритмических проолеи, то есть проблем существования алгоритмов для решения массовых задач из того или иного класса. Среди таких проблей стали различать разрешимые (соответствующий алго-рити существует) и неразрешимые (такого алгоритма нет).

Если разрешимые алгоритмические проблемы под другими ик-нами известны в математике с ее возникновения, то первые нераэ-решишэ алгоритмические проблемы были обнаружены лишь в 30-х годах в математической логике. Затем выяснилось, что такие проблемы есть и в других областях математики и прежде всего в алгебре: в 1947 году А.А.Марковым и, независимо, Э.Постом была доказана неразрешимость проблемы равенства в полугруппах, а о 1952 году П.С.Новиковым бил получен знаменитый результат о неразрешимости проблемы равенства в группах. Эти результаты решали стародавние проблемы, позтавлешшв, соответственно, А.Туэ в 1914 году и М.Дэном в 1911 году (подробности см. в [2] , [3], [6] , [10] , [37] , [38] ).

К началу 50-х годов благодаря основополагатацим работам А.И.Мальцева и А.Тарского сформировалась новая математическая дисциплина - теория моделей. К настоящему времени вышел целый ряд посвященных ей книг, среди которых особо выделим монографии А.И.Мальцева [35] , А.Робинсона [зэ] , Г.Кейслера и Ч.Чена [¿й] , Ю.Л.Ершова £¿2] , коллектива авторов [43] , Ю.Л.Ершова и Е.А.Палютина [¿3] .

Одним из центральных вопросов теории моделей стал впервые сформулированный А.Тарским вопрос о разрешимости элементарных теорий. Пусть - класс алгебраических систем не более чем счетной сигнатуры О" ; £ - совокупность всех (Г- формул логики первого поряцка; £ УС - элементарная теория класса УС , т.е. совокупность всех предложений из § , истинных на каясдой системе из УС . Пусть, далее, £: со —^ гэделева нумерация из ^22] и

Элементарная теория ^^ называется

^чз^ешимсй, если множество номеров рекурсивно, н

делимой в пртивном случае.- Иными словами, разрешима , (неразрешима), если разрешима (соответственно, неразрешима) алгоритмическая проблема вхождения произвольной формулы из Ш в множество ^

ПРОБЛЕМА РАЗРЕШИМОСТИ ЭЛЕМЕНТАРНОЙ ТЕОРИИ (А.Тарский): для данного класса ЭС алгебраических систем установить разрешима ли его олементарная теория •

Работы А.И.Мальцева и его учеников вместе с работаш других математиков показали, в частности, что класс с рглреэкыой слементарной теорией - довольно редкое явление. Этот тезиг сфор?<сулирован и обоснован в обзорной работе (1§3 . Вместе с тем, ещё в 50-г годах было замечено, что, например, такая классическая алгоритмическая проблема, как проблема равенства с данном классе & , моятет бить переформулирована как проблема разрешимости подходящей ограниченной теории класса ^ . Указанные два обстоятельства привели в середине 60-х годов к резкому росту числа исследований по разрешимоста ограниченных теорий. Это побудило А.И.Мальцева в явной виде сформировать п [З43 естественно возникаодуто программу алгоритшгчесиит: иг-следований. Пусть / - некоторый язык логики первого порядка сигнатуры з- , т.е. / ё . Для класса через ¿. & .обозначим его ограниче.'гнул языком теорию первого порядка или I- -теорию, т.е множество ¿.Л .

ПР0ГРА!,Я.1А ИССЛЕДОВйНШ РАЗРНЖОСТИ'ТЕОРИЙ ПЕРВОГО. ПОРЯДКА (А.И.Ыальцеп [34^ ): для наиболее важных классов ^ и наиболее интересных языков Л еыпснить разрешимость теории I- УС .

В гтрограл.гу Мальцева вписывается большинство результатов по алгоритмическим проблемам алгебры и, в частности, указанные вышетеореш Маркова-Поста и Новикова. Отметим ещё ряд относящихся сюда фундаментальных результатов. Разрешимы элементар-кыо теории полей действительных и комплексных чисел (А.Тарский) ; неразрешима элементарная теория поля .рациональных чисел (Ю.Робинсон); разрешима элементарная теория многообразия всех тбелевых групп (В.Шмелёва); разрешима элементарная теория класса всех дистрибутивных решёток с относительными дополнениями (Ю.Л.Ершов^; разрешима проблема равенства в многообразиях коммутативных и антикоммутативных алгебр над конструктивным полем _ и,стало быть, разрешимы универсальные теории этих многообразий

(А.И.Ширшов); разрешима проблема равенства в полугргппах с одним несократимым слепа и справа определявшим соотношением (С.И. Ацян); сутпествует линейно упорядоченное множество с нгразреши'.-ий элементарной теорией, для которого любая теория с ограниченным числом перемен кванторов разрешима (Ю.Л.Ершов); неразрешима диофантова теория кольца целых чисел (Ю.В.Матиясепич); неразрешима проблема равенства в алгебрах Ли (Л.А.Бокуть);' разрешима проблема совместности систем уравнений в свободном моноиде конечного ранга и разрешимы позитивная и универсальная теории свободной группы конечного ранга (Г.С.Мяканин) (см.ра-

сследования по программе Мальцева занимают одну из центральных позиций в теории моделей. Они тесно связаны с целым рядом разделов математики. Среди таких разделов конструктивные модели (см. монографию Ю.Л. Белова[22~] и статью С.С. Гончарова [17]). неклассическис логики (см. работу В.В.Рыбакова pjj}) , комбинаторная теория алгебраических систем (см. статьи Р.И.Григорчука [18]).

В настоящее время можно считать, что программа Мальцева в значительной степени выполнена (см. обзоры[3], ¡[б], £lC>], [зг/], [38],[боЗи библиографию к ним). Поэтому актуальной, на нага взгяд, становится развивагшая её

ПРОБЛШ* ОПИСАНИЯ РАЗРЕШИМЫХ ТЕОРИИ: для данного класса^ алгебраических систем и семейства языков H описать все разрешимые теории Itt для L е И.

Рассматривая проблему, удобно считать, что семейство язь^р ков H упорядочено включением и объединение всех входящих в него языков равно £ . Подобные семейства будем называть ие2а2хиями^языков. Иерархия языков H определяет для данного класса УС алгебраических систем ие]эа]охию_те2]зий HX^-tL-Z/L

Теперь проблема описания разрешимых теорий приобретает геометрический оттенок:она требует описать "разрешимые" точки диаграммы частично упорядоченного множества . При этом мы замечаем, что особую роль должны играть точки, лежащие на границе разрешимости или, точнее, составляющие эту границу. Это наблюдение позволяет дать следующее естественное и при-

_ 6-

нципиалыюе для namtpc рассмотрений

ОИРВДЕЛЕНИЕ. Теория LVC е-Н называется /г-критической, если она является минимальной среди неразрешимых теорий в иерархии

Понятие /^-критической теории является, по существу, математической версией "границы разрешимости" [273 • Кроме того, оно играет центральную роль при изучении проблемы описания разрешимых теорий. А именно, справедливо следующее очевидное

ЗАМЕЧАНИЕ. Пусть иерархия языков И рекурсивна и фундиро ванна, т.е. рекурсивны множества tb(i-) для любого/¿//и индексное множество семейства iH-(L)/ ¿_ G И}■ (^21J , а частично упорядоченное множество И удовлетворяет условию минимальности. Тогда иерархия теорий НУС фундированна и в не разрешимость наследуется для подтеорий, а неразрешимость - для надтеорий. В частности, теория

LXgHX

разрешима тогда и только тогда, когда она не включает ни одну //-критическую теории класса .

Стало быть, в случае рекурсивности и фундировэнности иерархии // проблема описания разрешимых теориЦ сводится к еле-' душей существенно более обозримой проблеме.

• ПРОБЛЕМА ОПИСАНИЯ КРИТИЧЕСКИХ ТЕОРИЙ: для данного класса ^алгебраических систем и иерархии// описать Dee И-критические теории класса & .

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

ш будем рассматривать многообразия }£ ,

всех полугрупп, всех колец, всех коммутативных, антикоммутатин ных,лиевых и ассоциативных колец, соответственно, к одноэле»^ ные классы, состоящие из алгебр, свободных в указанных многооС резнях и заданных в многообразиях If и Ш- одним определяющим соотношением. Роль иерархии Н будет играть определяемая ниже достаточно богатая схемно-альтернативная иерархия

SA

и ее

"антипод" - тривиальная иерархия

Общая методика исследованил ФСлючевую роль при доказательстве основных результатов работы i рают методы интерпретаций и базирующаяся нэ них схема описан®

критических теорий, названная нами JleтoдoмJ^egeния^ хни. Суть последнего в следующем: (а) отыскивается ряд несравнимых в данной иерархии неразрешимых теорий исследуемого класса; (б) доказывается, что любая теория, покрываемая в иерархии хотя бы одной из найденных в (а^, разрешима; (в) показывается, что любая теория из нашей иерархии, не включающаяся строго ни п одну из найденных в (а^ теорий, неразрешима тогда и только тогда, когда она включает хотя бы одну из них. Из пунктов (б) и (в) непосредственно вытекает, что теории, найденные в (а), и только они являются критическими теориями данного класса.

В доказательстве теорем 1-4, кроме того, активно исполь-1 зуется комбинаторная техника работы с ассоциативными и неассоциативными словами.

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

Практическая и теоретическая ценность. Работа носит теоретический характер. Полученные результаты решают некоторые вопросы, отмечавшиеся в литературе, обобщают ряд известных фактов или придают им новое звучание. Развиваемый в работе подход позволяет включить предшествующие результаты по программе Мальцева в единую' для данного класса алгоритмическую картину, оценить степень завершенности этой картины в зависимости от определяемого иерархией "масштаба" и наметить возможные пути ее завершения. Формирова»-ние проблематики обсуждаемого подхода позволило вычленить ряд проблем для дальнейшего исследования, Результаты и методы работы уже находят применение в не вошедших в диссертацию публикациях автора, а таете в статьях его учеников (см., например, [V] , [8] , [II] - [16] , [29] , [30] , [42] ). Они могут быть использованы и отчасти уже иепофзуютсл при чтении специальных курсов и при подготовке монографий и учебников; укажем в связи с этим обзорную статью [бО] , учебное пособие [59] и п. 8.2

в £44}

Апробация. Результаты диссертации были представлены на У1 (Тбилиси, 1982), УН (Новосибирск, 1984), УШ (Москва, 1986), IX (Ленинград, 1988), X (Алма-Ата, 1990) Всесоюзных конференциях по математической логике, на I и II Всесоюзных ко^еренциях по прикладной логике (Новосибирск, 1985, 1988), на Всесоюзном совещании по прикладной логике (Владивосток, 1988), на УШ Всесоюзной конференции "Проблемы теоретической кибернетики" (Горький, 1988), на ХУ1 (Ленинград, 1981), ХУЛ (Минск, 1983), ХУШ (Кишинев, 1985), XIX- (Львов, 1987)

Всесоюзных алгебраических конференциях, на III Всесоюзном симпозиуме по теории полугрупп (Свердловск, 1988), на Всесоюзной школе по иеассоциативной алгебре и её приложениям (Новосибирск, 1987), на Международных конференциях по теории кодог (®;нь, Франция, 1979), по теории полугрупп (Сегед, Венгрия, 1931), по алгебре (Новосибирск, 1989), на Международном цонгра< се по логике, методологии и философии науки (Москва, 1987). При этом на конференциях в Тбилиси и в Алма-Ате, а таюке на сях позиуме в Свердловске были сделаны пленарные доклады. По результатам работы автор выступал с докладами на заседаниях научных семинаров в Москве (1984—1990: семинар по алгоритмическим вопросам алгебры в МИ АН СССР; кольцевой и алгебраический семинары МГУ; семинар МГУ по алгоритмическим вопросам алгебры), Ленинграде (1987, 1991: семинар ЛОМИ по математической логике), Новосибирске (1986-1991: семинары "Теория моделей", "им.А.И. Шлршоса по теории колец", "Прикладная логика", "Алгебраические система", ^Алгебра и логика"), Кишинёве (1988: семинар по математической логике №1 с ВЦ АН МССР и семинар "Общая олгебр.я и математическая логика"), Киеве (1988: семинар Института кибернетики им.В.Ы.Глушкова АН УССР и республиканский семинар "Про-граммология и её приложения"), Свердловске (1978-1991: городской алгебраический семинар, семинары "Алгебраические системы" и "Алгебра, логика, алгоритмы"), Париже (1979: семинар Института теоретического программирования), Бордо (1979: семинар университета Бордо), Руане (1979: семинар руанского университета), Монпелье (1979: семинар'Лшиэдокского университета), на заседании Уральского математического общества (1986), Результаты диссертации отражены в публикациях автора [47] - [_73]

Объём и структура работы. Диссерга-

ция изложена на 224 страницах и состоит из введения и четырёх глав. В глявр I представлена техническая база работы, главы II и Ш посвягаены 5Л-критичсским и ¿г-критическим теориям, соответственно, в главе 1У исследуются иерархии как самостоятельные объекты и изучаются степени неразрешимости теорий. Библиография состоит из 88 наименований.

СОДЕРЖАНИЕ ДИССЕРТАЦИИ

Б главе I приводятся вспомогательные результаты, используемые в последующих двух главах. Первый параграф посвятен изложению метода описания критических теорий и доказательству общего утверждения, позволяющего при определённых условиях находить критические теории некоторого класса УС- относительно схемно-яльтеркативной иерархии ¿А . Поскольку эта и близкие ей иерархии потребуются для формулировок, дадим их определение.

Пусть & - совокупность всех формул логики первого порядка фиксированной еигнатуш, записанных п пренексной нормальной форме, т.е. в виде ц/,Щ У Д 7 ЭЧу где , \

,X - пустой символ цля любого символа х ; ЭТ.- - атомарная формула. Пусть - совоку-V

пность всех, включая пустое, альтернирующих слов,'т.е. слов из чередующихся символов К, 3 . Пусть, далее, /ь ^ и)} С,...СН , ъЬ^е^о,/} .Рассмот-

рим тон языка:

ЯГ7¿К*

ОПРЕДЕЛЕНИЕ. Тдидичльной, схето^, ^льтернати-внзй., проемеччг^^гьт^^ и ^хи^го^^Д^Х^Д^^^ иерар-

хии и языков назовём, соответственно, следующие упорядоченные включением семейства языков :

* ¿л *//, У4,/*» е <0,1}}

Названия иегчтзхий выбраны по главны)/ определяющим их классификационным параметрам. Первые две из них давно известны

(см., например, £13 , £203 ), ч остальные введены автором п \j5l3 , [533 . Наиболее сложная из них схемчо-яльтгрнятивная иерархия £А достаточно богата. Она содержит такие известные языки, как позитивный Солу , экзистенциальный 39 , примитивный 3~7А , сколемский У39 , диофантов (по терминелогии ¡^343 и позитивно-примитивный по терминялогии []233 ) ЗЯ, , универсяльный У& и эквяционяльный V . Для четырёх из указанных языков используются следующие обозначения: ¿ом/ , V. Все введённые иерархии облядяют рядом интересных свойств, о которых идёт речь в четвёртой главе. Среди свойств главными являются их рекупсивность и ф.унди-рованносгь. Стало быть, кяк отмечено выше, решив проблему ' описания критических теоиий некоторого класса алгебраических систем относительно любой из этих иерярхий, мы Автоматически получаем и решение проблемы описания разрешимых теорий данного класса.

Второй пяраграф главы I посвящен систематическому изложению трёх известных интерпретаций теорий в теориях. Сделано это на единой основе, которую составляет алгоритм Ершова{221. В этом яе параграфе определяются введённые автором машины с двумя, головкэми н указывается их связь с двухленточными • машинами Минского.

Глава П целиком посвящена описанию -критических теорий полугрупповой и кольцевой сигнатур. Из этого описания в качестве следствий легко получается решение для соответствующих классов алгебраических систем проблемы описания И -критических теорий для 17/5^ .. Введем необходимые для фирлулировок. обозначения и понятия. Пусть Т", , } Л- - многообразия всех полугрупп, всех колец, всех коммутативных, антикоьагутативных, лиевых и ассоциативных колец. Если не оговорено противное, то, рассматривая теории полугрупп и колец, мы будем иметь в виду теории сигнатур <•■>, >* , О , соответственно. Для многообразия алгебраических систем через обозначим свободную в систему ранга ^ . Как обычно, через мы обозначаем кольцо целых чисел. Для класса алгебраических систем И -границей разрешимости этого класса будем называть список ВСЖ-,Н} всех языков 6 М

таких, что является //-критической теорией.

Условимся всюду ниже вместо " S>4 -граница" говорить просто, "граница". Утверждения, доказываемые в работе, нумеруются следующим образом. Основные результаты (теоремы) имеют сквозную нумерацию; предложения и следствия имеют номера вида к,б , где к - номер параграфа, содержащего доказательство соответствующего утверждения, - очередность в тексте работы доказательства утверждения данного типа.

Основными результатами этой главы являются следующие две теоремы.

ТЕОРЕМА I. Граница разрешимости многообразия равнч

ТЕОРЕМА 2. Границы разрешимости многообразий £ , , <УЬ совпадают и равны

Сформулированные теоремы полностью решают в соответствующих случаях проблему описания ЭА -критических теорий и, стало быть, проблему описания разрешимых теорий. Из теоремы I вытекает

СЛЕДСТВИЕ 3.1. Справедливы следующие равенства:

3(^)4^}, а(Г^А) ^ -{5-7*} .

Аналогичные следствия справедливы для теоремы 2 и для нижеследующих предложений 4.1-4.3, на которые опирается доказательство этой теоремы.

ПРЕДЛОЖЕНИЕ 4.1. Граница разрешимости кольца

равна

Описание границы разрешимости кольца .2? в этом предложении, основываясь на известном результате Ю.В.Матиясевичд по.10-й проблеме Гильберта, завершает в рамках иерархии алгоритмическую картину для этого кольца. Развитие указанного описания содержится в работе ¡^153 . В ней, в частности, показано, что граница разрешимости кольца 2?" совпадает с Границей разрешимости алгебраической системы где | - отношение делимости целых чисел.

ПРЕДЛОЖЕНИЕ 4.2. Граница разрешимости кольца для любого равна 4

Заметим, что граница В(.24) и, скажем, граница ЗА) равны по мощности, однако различаются "на втором месте". Поскольку -ЭУ^ЗЪ/-? < кольцо

имеет

- № -

"более низкую" границу разрешимости, чем кольцо

Иными словами, кольцо имеет в рамках иерархии боль-

гае разрешимых теорий, чем кольцо 2 ,

ПРЕДЛОЖЕНИЕ 4.3. Границы разрешимости колец для любых ^ $ & Я. совпадают и равны Э^-г, ¥т1/,7гл}.

Одним из ключевых моментов в доказательстве теореме 2 является установление неразрешимости Ууу -теорий рассматриваемых пяти многообразий. Требуемая неразрешимость' следует из неразрешимости проблемы равенства в этих многообразиях. И если для многообразия Л. неразрешимость такой проблемы почти очевидна в силу теоремы Маркова-Поста, а для многообразия достаточно просто получается из конструкцт

Н.укина £28^ конечно определенной алгебры Ли (над полем) с неразрешимой проблемой равенства, то для многообразий^,^ и 5Г ситуация оказалась значительно сложнее. В психологическом плане дело усугублялось тем, что, как показали А.И.Куков £243 и А.И.Ширшов [453 , в многообразиях всех неассоциативных алгебр и всех коммутативных и антикоммутативных алгебр над конструктивным полем проблема равенства разрешима. Оказалось, однако, что существуют кольца, конечно определенные в многообразиях и ^ , в которых

обсуждаемая проблема неразрешима. _

ПРЕДЛОЖЕНИЕ 4.5. В многообразиях £ ,

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

Это удалось сделать при помощи интерпретации в неассоциативных, кольцах работы введенных автором машин с двумя головками.

Глава 111 посвящена изучению £ -критических теорий. Поскольку £ - тривиальная иерархия языков, состоящая из одного элементарного языка, ясно, что ¿г-критическая теория класса Я: - это его элементарная теория Иными словами, проблема описания Я-критических теорий данного класса

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

неассоциативных колец с одним определяющим соотношением.

Особый интерес к элементарным теориям таких полугрупп обусловлен исследованиями, предпринятыми С.И.Адяном (см.[2] -

Исчерпывающий ответ на соответствующий вопрос дает первый основной результат главы Ш:

ТЕОРЕМА 3. Элементарная теория полугруппы А^Яц*?}

разрешима тогда и только тогда, когда"' ()"=-/ или У^Л и соотношение «■•«=»>* имеет один из следующих видов, где

, 'ЛГ)04=е«.% (П) а41,2, ... \

(Ш) (У) А^аЛа-,

т)л€ = 6а£гч (УП) , (УШ) (IX) л-^

Доказательство неразрешимости элементарных теорий в теореме проводится методом Ершова относительно элементарней определимости в исследуемых полугруппах свободной полугруппы ранга 2. Это вместе с использованием результатов работы [46 ^ позволяет вскрыть алгебраические причины разрешимости элементарных теорий полугрупп с одним определяющим соотношением: СЛЕДСТВИЕ 5.1. Для полугруппы

с одним определяющим соотношением следующие условия равносильны: элементарная теория $ разрешима; на & выполнено нетривиальное тождество; среди подполугрупп $ нет свободной подполугруппы ранга 2.

В отличие от полугрупп ситуация-.с неассоциативными . кольцами иная. В § б строится пример кольца, заданного в многообразии ^ одним определяющим соотношением, имеющего неразрешимую элементарную теорию, на котором выполнено нетривиальное тождество. Однвко и здесь вопрос об устройстве колец с одним определяющим соотношением и разрешимой элементарной теорией является столь ие интересным как и для полугрупп. Его полностью решает второй основной результат главы Ш:

ТЕОРЕМА 4. Элементарная теория кольца разрешима тогда и только тогда, когда и

Главы П и Ш составляют первую евтеетную линию работы и кульминацию здесь составляют теоремы 1-4, решающие в соответствующих случаях проблему описания //-критических теорий^ В заключительной главе 1У реализуется вторая, методологически связанная с первой, сюжетная линия:' изучение свойств иерархий языков и теорий. Ее ядро составляют характеризуемые ниже теоремы 5-8. Рассмотрение известных языков

,логики первого порядка и их иерархий показывает, что их можно определять либо в терминах формульности, либо в терминах кодируемости. В первом параграфе главы 1У вводится в рассмотрение некоторая сигнатура метаязыка для описания синтаксических особенностей формул и в ее терминах дается определение формульного языка и формульной иерархий языков. Кроме того, в терминах и)ки)—матриц над множеством 3, .зг^зг/агё^Я^, где - язык, состоящий из всех квазиатомарных формул фиксированной сигнатуры, дается определение кодируемого языка и кодируемой иерархии. Основным утверждением этого параграфа является теорема 5, в которой доказывается формульность известных языков и иерархийУА? кодируемость этих иерархий и характеризуются кодируемые иерархии.

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

Иерархия в самом общем смысле-это классификация математических объектов по их сложности. Не вдаваясь в детали теории сложности, можно понять, что отношение "не сложнее" является квазипорядком. Поэтому, естественно дать следующее

ОПРЕДЕЛЕНИЕ. на квазиупорядоченнои

множестве <' У; ^ назовем упорядоченное включением семейстг такое, что

и любое множество К ^И является объединением подходящей цепи главных идеалов. . ^

Первым основным результатом этого параграфа является

ТЕОРЕМА 6. Справедливы следующие два утверждения: (А) частично упорядоченное множество </} • ^ > изоморфно некоторо{ абстрактной иерархии тогда и только тогда, когда любая его цепь С- обладает точной верхней гранью ^ и

^хеАЭ^бСОг*-

<£ х^^-) ; (Б) абстрактная иерархия, содержащая все главные идеалы исходного квазиупорядоченного множества, фундированна тогда и только тогда, когда этому условию удовлетворяет исходное квазиупорядоченное множество.

В сделанном выше замечании отмечалось, что в случае рекурсивных фундированных иерархий языков описание критических теорий дает описание всех разрешимых теорий из соответствующей иерархии теорий. Поэтому интересно понять, когда рекурсивной и фундированной будет, скажем, произвольная'кодируемая иерархия и что в этом плане можяо сказать об используемых нами шести иерархиях. По определению кодируемой иерархии ей сопутствуют так называемая иерархическая система особой сигнатуры т , эквивалентность и квазипорядок на множестве всех формул $ . 1Сласс кодируемых иерархий называется «гг -аксиоматизируемым, если аксиоматизируем соответствующий класс иерархических систем. Вторым основным результатом § 8 является теорема 7, в которой указываются • необходимые и достаточные условия рекурсивнорти и фундиро-ванности произвольной кодируемой иерархии и утверждается, что класс иерархий /в, V, А , УД , 5 является рекурсивных», фундированным и задается одной 'С-аксиомой в классе всех рекурсивных, фундированных и кодируемых иерархий языков.

Сформулированные выше утверждения по иерархиям языков первого порядка позволяют получить некоторые результаты по степеням неразрешимости теорий. Этому посвящены теорема 8 и следствия из нее. Конкретизируем сказанное. А.И.Мальцев в работе (З43 поставил следующий вопрос: какие степени неразрешимости могут иметь элементарная, универсальная, квази-эквацнональчая и эквациональная теории некоторого рекурсивно аксиоматизируемого класса алгебраических систем? Там зе отмечено, что Ханфом показано, как построить конечно аксиоматизируемое многообразие алгебраических систем , для которого элементарная теория имеет наперед заданную рекурсивно перечислимую степень неразрешимости. В заключение сказано, что у всех "естественных" конечно аксиоматизируемых классов с известной степенью неразрешимости теории эта степень либо нулевая, либо равна о/ , то есть является наивысшей среди рекурсивно перечислимых степеней. В связи с этим "интересными представляются вопросы о представимости рекурсивно перечислимых степеней неразрешимости теориями •

^¡естественных" классов и о согласованности "хороших" иерархий теорий таких классов с известными иерархиями рекурсивно перечислимых множеств [413 • Ответы на эти вопросы и дает теорема 8.

Предварительно условимся многообразие называть

м|^ообра£ие^ если для

любой рекурсивно ^еречислимой степени неразрешимости о( существует алгебраическая система, конечно определенная в многообразии № , степень неразрешимости проблемы равенства в которой равна о<

ТЕОРЕМ 8. Пусть многообразие

алгебраических

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

существуют языки , для которых

ц ^¿^¿^¿^,

Из этой теорбы вытекают следующие интересные утверждения.

СЛЕДСТВИЕ 8Л.' Если многообразие полно по сте-

пеням неразрешимости, то для любой рекурсивно перечислимой степени неразрешимости °< существует язык I <£ И ^ тако!:, что

СЛЕДСТВИЕ 8.2. Если многообразие

полно по степеням неразрешимости, то любая рекурсивно персчислимая степень неразпешимости не превосходит степени неразрешимости теории

СЛЕДСТВИЕ 8.3. Утверждения теоремы 8 и следствий 8.1 и 8.2 справедливы для многообразий >С, , .

Автор благодарит профессора Л.Н.Шеврина за постоянное внимание к работе и многочисленные полезные беседы

ЛИТЕРАТУРА

I. Аддисон Дж. Теория иерархий//Математическая логика и ее применение. М., 1965.С.23-36.

- 1 с

2. Адян С.И. Определяющие соотношения и алгоритмические проблемы для групп и полугрупп//Тр.Матем.ин-та АН СССР им.В.А.Стеклова. I95S.T.85.

3. Адян С.И. О работах П.С.Новикова и его учеников по алгоритмическим вопросам алгебры//Тр.Матем..ин-та АН СССР им.В.А.Стеклова. 1973.Т.133.С.23-32. -

4. Адян С.И. О преобразованиях слов в полугруппе, заданной системой определяющих соотиопений/Длгебра и логика. 1976.Т.15,$ 6.C.6II-62I.

5. Адян С.И., Оганесян Г.Х. К проблеме равенства и делимости в полугруппах с одним определяющим соотношением// Из в. АН СССР. Сер.мат. 1978 .Т. 42.fi 2. C.2I9-225.

6. Адян С.И., Маканин Г.С. Исследования по алгоритмическим вопросам алгебры/./Трллатем.ин-та АН СССР им.В.А.Стеклова I984.T.168.С.197-217.

7. Баясгалан Б. Разрешимость элементарных теорий решеток подполугрупп полугрупп//Сиб.матем.;курнЛ990.Т.31.Гз I.

8. Баясгалан Б., Ваяенин Ю.М. О разрешимости теорий классов степеней полугрупп//Изв.вузов.Матемятика.1988.№ II. С.62-64.

. 9. Бокуть Л.А.Неразрешимость проблемы равенства и подалгебры конечно определенных алгебр Ли//Изв.АН СССР. Сер.мэт¿972.Т.36, »6. С.1173-1219.

10. Бокуть Л.Л., Кукин Г.П. Неразрешимые алгоритмические проблем для полугрупп, групп и колец//Итоги науки и техники. ВИНИТИ.Алгебра. Топология. Геометрия. T.25.I987.C.3-66.

11. Важенин Ю.М., Розенблат Б.В'. О позитивных теориях Свободных алгебраических систем/АГзв.иузов. Математика. 1983.

з.с.70-73.

12. Валенин Ю.М., Розенблат Б.В. Разрешимость: позитивной теории свободной счетнопорсжденной полутруппы//Матем.сб.1981 » Т..116,№ I.С.120-127.

13. Ваясенин Ю.М., Сизый C.B. Квазимногообразия эндомо-Делей//Изв.вузов.Математика.1988.№ 3. С.66-67.

14. Важенин Ю.М., Попов В.Ю. Критические теории свободных нильпот'2птных колец некоторых типов//Изв.вузов.Математика. 1990.№ И.С.?4-?6-

о

Ib. Вакенин Ю.М., Попов B.D., Шибаков А.Ю. Критические теории свободных нилъпотентных колец и кольца целых чисел с делимостью//Меясдународная конференция по алгебре. Тезисы докладов по теории колец. Новосибирск. 1989. С.28.

16. Важенин D.M. Об элементарных теориях лиевых колец с одним определяющим соотношением//У1 Симп.ср теории колец, алгебр и модулей? Тез.докл. Львов. 1990. С.31.

17. Гончаров С.С. Группы с конечным числом конструктиви-заций//Цокл.АН СССР.1981.Т.256, № 2. С.269-272.

18. Григорчук Р.И. Степени pojrra конечно порожденных групп и теория инвариантных средннх//Изв.АН СССР.Сер.мат. 1984.Т.48,№ 5. С.939-985.

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

20. Ершов Ю.Л. Ограниченные теории вполне упорядоченных множеств//Алгебра и логика.1968.Т.7,№ 3.C.38-47.

21. Ершов Ю.Л. Теория нумераций. М.,1977.

22. Ершов 1)91. Проблемы разрешимости и конструктивные модели.'M., 1980.

23. Ершов ЮД.,'Палютин Е.А. Математическая логика. M., 1987.

24. Жуков А.И. Приведенные системы определяющих соотношений в неассоциативных алгебрах//Матем.сб.1950. Т.27,№ 2. С.267-280.

25. Замятин А,П. Неабелево многообразие групп имеет неразрешимую элементарную теорню//Алгебра и логика. 1978. Т.17, № I. С.20-27.

26. Кейслер Г., Чэн Ч.Ч. Теория моделей. M., 1977.

27. Кокорин А.И., Пинус А.Г. Вопросы разрешимости расширенных теорий//Успехи мат.наук. 1978.Т.33,№ 2.С.49-84.

28. Кукин Г.П. О проблеме равенства для алгебр Ли// Сиб.матем.журн.1977.Т.18,№ 5.С.1194-1197.

29. Маевский В.В. Об ограниченных теориях бесконечных симметрических групп и полугр.упп/Д'еждународная копр. по алгебре. Тез.докл.по теории моделей.Новосибирск.1989.С.73.

30. Маевский В.В. Об универсальных словах на бесконечных симметрических группах//Советско-француэкий коллоквиум по теории моделей.Тез.докл.Караганда.1990.С.25.

31. Макании Г.С. Проблема разрешимости уравнений в свободной полугруппе//Матем.сб.1977.Т.103,я* 2.С. 147-236.

- 32. Мокянин Г.С. Уравнения в свободной группе // Изв.АН СССР. Сер. матем.1982, Т.46, № 46. С.I199-1273.

33.. Маканин Г.С. Разрешимость универсальной и позитивной теории свободной групгш//Изв.АН СССР. £ер.Матем.I984.T.48, » 4.С.735-749.

34. Мальцев А.И. О некоторых пограничных вопросах алгебры и математической логики//Мездународкый конгресс математиков. M., I966.C.217-23I.

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

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

37. Матиясевич D.E. Об исследованиях по некоторым алгоритмическим проблемам алгебры и теории чйсел//Тр.матем. ин-тя км.В.А.Стеклова.1984.Т.168.С.218-235.

38. Ремесленников В.Н., Романьков В.А. Теоретико-модельные и алгоритмические вопросы теории групц//Итоги науки и техники.ВИНИТИ. Алгебра. Топология. Геометрия. T.2Ï.M.I983. С .3-79.

■ 39. Робинсон А. Введение в теория моделей и метаматематику алгебры. M., 1967.

40. Родтсерс X. Теория рекурсивных функций и эффективная вычислимость. M., 1972.

41. Рыбаков В.В. Уравнения в свободной топобулевой алгебре//Алгебра и логика. 1966. Т.25," 2. С.171-204.

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

43. Справочная книга по математической логике. Часть I. Теория моделей. Под ред.Дт.Барвайса. M., 1982.

44. Шеврин Л.Н. Полугруппы//Общая алгебра.Т.2,гл.1У. Под общей ред.Л.А.Скорнякова. M., 1991.

45. Ииршов А.И. Некоторые алгоритмические проблемы для S -алгебр//Сиб.матем.лурн.1962.Т.ЗI .С.132-137.

46} Шнеерсон Л.М. Тождества з полугруппах с одним определяющим соотношением//Логика, алгебра и вычислительная математика.Ивановский пед.ин-т.Иваново,1972.T.I3-4.C.II2-I24.

Работы автора по теае диссертации

47. Vosenin YuJ'ï. On elementary theory of free inversa semigroups ft Semigroup Forum.1974.V,9.P.189-195.

48. ^eaenin Yu.ti. Quelques theoremes et problenes libs avec la de'cidabllite'des theories élémentaires // Seainair d* Infornatique T'heori que. Inst. Programmation:.Paris. 1979/80. P. 1-9.

49. Vazenin Ju.M. Ьцг la liaison entre probleoea combinatolres et algorithniques// ïheor. Coaput. Soi. 1981. V.16.P.33-41.

50. Важенин Ю.М. Полугруппы с одним определяющим соотношением, элементарные теории которых разрешимы//Сиб.матеы. журн.1983.Т.24,№ I.С.40-49.

51. Важенин Ю.М. 0 критических теориях//УП Вс.кон|>. по матем.логике.Тез.докл.Новосибирск.1984.С.27.

52. Вачсенин Ю.М. Об иерархиях языков первого порядка// ХУШ Вс.алгебраическая конф.Тез.сообщ.,ч.1.Кишинев.1985.С.76.

53. ВажениьРю.М. Иерархии языков и критические теории// УШ Вс.конф. по матем.логике. Тез.докл.Москва.1986.С.28.

54. Важенин Ю.М. Алгоритмические проблемы и критические теории/Успехи матем.наук.1987.Т.42,}р 3.C.235-236.

55. Vazenin Ju.M. Hierarchies and critical theories // УШ Междунар.конгресс по логике, методологии и философии науки.Тез.докл.Т.I.М.1987.С Л81-182.

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

57. Важенин Ю.М. Разрешимые и критические теории некоторых классов полугрупп и колец//Вестник МГУ.Сер.I.Мат., мех.1988,№ 3.C.I02.

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

59. Важенин Ю.М. Алгоритмы и алгебра. Учебное пособие. Свердловск. 1988. 77 с.

60. Важенин Ю.М. Разрешимость теорий первого порядка классов пол>трупп//Алгебраические системы и их .многообразие. Сб.научн.трудов.Свердловск.1988.С.23-40.

.61. Важеннн D.M. Расзмреннь'е иерархии язккоз//П Ее.кс'-й, по прикл.логине.Тез.докл.Нойоснбкрпгг .1968,С.38-40.

б?.. Ведении D.M. Разрешмъго теорт.ч класса конечно определенных полугрутш//УШ Вс.токф, Проблемы тесрзтич'. И1бярн»Те5,докл.19е8. Горький. С.СО.

63. Вменяй D.U. О критических теориях свободных полугрупп :г :,:оно:ст;оз//Ш ßc.симпозиум по теории полугрупп.Тез .докл. СпэрдлоЕСК.19Е8.С.11.

64. Важенин ЙЛ<1. Раэрелктю тэзрии :соы:^\ггатлвиь!Х и антккэмнутативкых иолец//1Х Ес.кок|».по катем.лсгике, Тез .доил. ЛенинградЛS88,С.23,

65.- Ведении Ю.М. Критические теор!ти некоторых классов ¡■еассоцйатиЕкых1 колец/'/Алгебра и логика. 1989.Т.28,fl 4.

С.393-401.

66. Езг.еннн D.M. Языковые и абстрактные иерархпи//Изв, uyaoD.Математика. 1590. Г> I. С. 10-12.

67. Езжешти D.M. Неассоцдагивныэ кольца с одним спр-зде-лящим соотношением, элементарные теории которых, разрешимы// Алгебр.1 и логика. I9S0.T.29,$ 5.С.509-522.

6S. Вялении Ю.11. Проблема равенства в нзассоциативных кольцах//Алгебра к логика. 1991. Т.30,!? I. С.17-27. .

69. Вакснин D.H. Матрогчние иерархия языков йервого порядка. и ну приловеачя/Длгебра и логика. I33I.T.30,.'" 2.C.I54-I67.

70. Вйяскин D.M. Степени неразрешимости полугруппогнх теорий/международная ко!£|).по алгебре. Гез.докл.по теории моделей. НовосибирскЛ969.С.22.

71. Езяенин D.M. Пробле-.sj разрешимости теорий и классификация формул первого поряд;сэ//Советско-французкнй коллоквиум по reopüii моделей.' Тез.докл.Караганда. 1990.С Л2-13,

72. Еаяекин D.M. Проблемы разрешимости йольцсвыя reopHfl//BecraiK МГУ. Сер Л. Мат., мох .1991. V 3.C.S8.

73. Важеннн D.M. Кодируемые и формульные иерархии яаыков/Д Вс. .по мат ем. логике .Тез .докл .Алма-Ате. 1990 .С .32.