Введение к работе
Актуальность темы. Множество бинарных отношений, замкнутое относительно некоторой совокупности 9, операций над ними, образует алгебру, называемую fi-алгеброй отношений. Не вдаваясь сколь-нибудь обстоятельно в историю развития и современные достижения теории алгебр отношении (см., например, [1, 7, І0, 14, 15, 18-22, 24-36,' 32-35]), заметим прежде всего, что она берет свое начало в исследованиях Де Моргана, Пирса, Фреге и Шредера, направленных на создание алгебраического аппарата, адекватного логике предикатов первого порядка. Среди рассматривавшихся в этих исследованиях операций, наряду с булевыми, центральное место занимали операции умножения о и обращения -1 отношений.
Новый этап в развитии теории алгебр отношений связан с именем Тарского. Им был предложен аксиоматический подход к исследованию алгебр отношений и сформулирован ряд фундаментальных проблем, сыгравших важную методологическую роль и во многом определивших дальнейшее развитие теории (см.- [37-40]). Рассмотрение алгебр отношений в рамках аксиоматического подхода предполагает изучение их свойств, выразимых на языке логики предикатов первого порядка и, в частности, на языке тождеств и квазитождеств. .
Изучение тождеств и квазитождеств алгебр отношений означает фактически исследование многообразий и квазимногообразий, порожденных различными их классами. Одной из центральных в теории многообразий и квазимногообразий проблем является проблема нахождения базиса. Применительно к классам алгебр отношений эта проблема может быть сформулирована следующим образом:
1Q(1V). Для заданного класса алгебр отношенийTZ, найти базис квазитождеств (тождеств) квазимногообразия QR (многообразия VR), порожденного %.
Если проблема 1 решена и найденный базис оказывается бесконечным, естественным образом встает вопрос о существовании конечного базиса. Соответствующая проблема заслуживает самостоятельного выделения:
2Q(2V). Длі заданного класса алгебр отношений Я выяснить, является ли квазимногообразие QTZ (многообразие VTZ) конечно базируемым.
В том случае, когда абстрактное замыкание YR класса алгебр отношений Л образует квалимногообразие, а для многих классов алгебр отношений это как раз так, проблема нахождения базиса квазитождеств приобретает особое значение и становится экви-" валентной одной из центральных в теории алгебр отношений задач отыскания элементарной характеристики (системы элементарных аксиом) класса TR. Что касается вопроса о том, является ли класс ТЯ или, в более .общем случае, квазимногообразие Q7?. многообразием, то это далеко не всегда имеет место. Вместе с тем, для ряда важных классов алгебр отношений указанное свойство выполняется. Перечисленные обстоятельства побуждают выделить еще одну проблему:
3Q(3V). Для заданного класса алгебр отношений И, выяснить, образует ли абстрактное замыкание 1% класса V, (квазимногообразие ($Я, порожденное классом %) квазимногообразие (многообразие).
Постановке н решению сформулированных выше проблем для различных классов алгебр отношений посвящены работы многочисленных авторов (см., например, [3, 8, 9, 10, 14-20, 24-26, 32-35]). Исторически первым был класс алгебр отношений Тарско-го, представляющих собой {о,-?,Д,и,П,~,0,и}-апгебры отношений (здесь ~ - операция дополнения, а Д и U - соответственно тождественное и универсальное отношение на базисном множестве). Изучение этого класса играет важную роль в вопросах приложения теории алгебр отношений к логике (см. [35]). Квазимногообразие, порожденное классом алгебр отношений Тарского,
является многообразием [34 рого был найден Линдоном
бесконечный базис тождеств кото-17]. Манком [19] было показано, что указанное многообразие не имеет конечного базиса тождеств.
Класс {о,-1,Л,Д}-алгебр отношений (шлурешеточно упорядоченных инволютированных моноидов отношений)^ играющий важную роль в теории решеток, был рассмотрен Ибнссоном в [14], где им было показано, что абстрактное замыкание этого класса образует квазимногообразие и найден бесконечный базис его квазитождеств. Указанное квазимногообразие, а также по-эожденное им многообразие, не являются конечно базируемыми 12. Проблема SV для этого класса, поставленная Ибнссоном в 14],оставалась открытой.
Согласно хрестоматийной в теории полугрупп теореме
і
Вагнера-Престона абстрактное замыкание класса {о,-1}-алгебр частичных взаимно однозначных преобразование совпадает с многообразием всех инверсных полугрупп. Абстрактное замыкание класса {о -1 }-алгебр отношений (инволютированных полугрупп отношений) образует квазимногообразие. Проблема 1Q для этого класса была поставлена Вагнером в 1953 году и оставалась открытой, (формулировка этой проблемы содержится также в [62]).
Предметом нашего внимания являются алгебры отношений с операциями, принадлежащими к числу операций алгебр отношений Тарского, или, в более общем случае, выразимыми через них. Такие алгебры отношений называются рсдуктами алгебр отношений Тарского. Интерес к рассмотрению редуктов алгебр отношений Тарского обусловлен следующими обстоятельствами. Во-первых, изучение редуктов является фактически продолжением изучения алгебр отношений Тарского с точки зрения свойств рассматриваемых операций. Во-вторых, встречающиеся в различных областях алгебры множества отношений (такие, например, как множества отношений, согласованных со структурой алгебр) оказываются далеко не всегда замкнутыми относительно всех операций алгебр отношений Тарского. Особый интерес представляют редукты, в число операций которых входит одна из важнейших операций над отношениями - операция умножения. Такие редукты, называемые в дальнейшем мультипликативными, могут быть рассмотрены как полугруппы отношений, оснащенные рядом дополнительных операций. Обзор некоторых результатов, посвященных редуктам алгебр отношений Тарского,можно найти в [26].
Алгебры отношений и, в частности, редукты алгебр отношений Тарского могут быть классифицированы по виду формул, задающих их операции. Операция над отношениями называется диофантовои, если она может быть задала с помощью диофантовои [5] (в другой терминологии - примитивно-позитивной [4]) формулы исчисления предикатов, т.е. формулы, содержащей в своей записи лишь кванторы существования и операцию конъюнкции. Изучение диофантовых операций играет важную роль при рассмотрении производных объектов над универсальными алгебрам (см. [22]).
Цепь работы - создание по возможности завершенной картины в решении проблем 1-3 для классов мультипликативных ре-дуктов алгебр отношений Тарского с диофалтовьши операциями и, в частности, решение упомянутых выше проблем Йбнссона и Вагнера, а также проблем, поставленных в [8, 26]. Характерной особенностью работы является то обстоятельство, что решение многих из этих проблем найдены в результате применения полученных автором общих результатов, касающихся описания эквациональных и квазиэквациональных теорий классов алгебр отношений с диофантовыми операциями и позволяющих строить базисы, порожденных ими многообразий и квазимногообразий.
Общая методика исследований. Важнейшим инструментом решения поставленных задач являются разработанные автором методы описания эквациональных и квазиэквационвльных теорий классов алгебр отношений и построения их базисов тождеств и квазитождеств с помощью графов.
Научная новизна. Все основные результаты диссертации являются новыми. В качестве следствий также получен ряд результатов, пршіадлежащих другим авторам.
Теоретическая и практическая ценность. Работа носит теоретический характер. Полученные результаты даіот ответ ла ряд пршщишюльных вопросов в теории многообразий и квазимногообразии алгебр отношений и позволяют решить некоторые из проблем, давно стоявших в этой области. Общность полученных результатов и методов открывают возможности для их использования как для изучения различных конкретных классов алгебр отношений, так и в смежных областях алгебры (теории полугрупп и решеток, теории клонов и производных объектов над универсальными алгебрами), а также в исследованиях по "computer science". Результаты диссертации могут служить основой для чтения спецкурсов и подготовки учебных пособий и монографий.
Апробация работы. Результаты диссертации докладывались на ряде всесоюзных и международных конференций (Свердловск-73 [87], Гомель-75, Новосибирск-77, Кншинев-85 [99], Свердловск-88 [102], Саратов-89 [105], Новосибирск-89 [106], Сегед-89 [107], Алма-Ата-89 [108], Саратов-91 [109], Новосибирск-91 [110], Веспрем-92 [124], Сегед-93 [120], Кольчестер-93 [121], Йорк-93, Кенигштайн-94 [127], Порто-94 [128], Сегед-94 [129],
Новосибирск-94 [130],'Санкт-гіетербург-95 [132], Хайфа-95 [133], Прага-95, Шалготорьян-96 [139]), а также на научных семинарах городов Брно, Будапешта, Варшавы, Екатеринбурга, Кишинева, Кошице, Москвы, Новосибирска, Одессы, Праги, Санкт-Петербурга, Саратова, Сегеда, Тарту, Харькова,
Публикации. Результаты диссертации опубликованы в 55 работах. Основные публикации автора приведены в конце авторефе-!>ата. Включенный в диссертацию результаты совместной работы А5] получены в нераздельном соавторстве с Шайном. Результат, касающийся решения проблемы Йонссона [14], анонсированный автором в [all], был независимо получен Андрейкой и опубликован в совместной работе [А.16].
Объем и структура работы. Рабата состоит из введения и 12 параграфов, сгруппированных в 4 главы, и занимает 300 страниц машинописного текста. Библиография содержит 139 наименований.