Тождества и квазитождества алгебр отношений тема автореферата и диссертации по математике, 01.01.06 ВАК РФ



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

БРЕДИХИН Дмитрий Александрович

ТОЖДЕСТВА И КВАЗЙТОЖДЕСТВА АЛГЕБР ОТНОШЕНИЙ

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

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

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

Работа выполнена на кафедре высшей математики Саратовского государственного технического университета и кафедре алгебры и дискретной математики Уральского государственного университета

Научный консультант: доктор физико-математических наук, профессор Шеврин JT.H.

Официальные оппоненты: доктор физико-математических наук, профессор Михалев A.B. доктор физико-математических наук, профессор Пинус А.Г. доктор физико-математических наук, профессор Рыбаков В.В.

Ведущая организация: Институт математики и механики Уральского отделения РАН,

г. Екатеринбург

Защита состоится " I ^ " а А 199 ?т. в час.

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

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

Автороеферат разослан " ^ ^ " А^рт^ 199

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

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

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность темы. Множество бинарных отношений, замкнутое относительно некоторой совокупности А операций над ними, образует алгебру, называемую О-алгеброй отношений. Не вдаваясь сколь-нибудь обстоятельно в историю развития и современные достижения теории алгебр отношении (см., например, [1, 7, 10, 14, 15, 18-22, 24-36,' 32-35]), заметим прежде всего, что она берет свое начало в исследованиях Де Моргана, Пирса, Фреге и Шредера, направленных на создание алгебраического аппарата, адекватного логике предикатов первого порядка. Среди рассматривавшихся в этих исследованиях операций, наряду с булевыми, центральное место занимали операции умножения о и обращения ~5 отношений.

Новый этап в развитии теории алгебр отношений связан с именем Тарского. Им был предложен аксиоматический подход к исследованию алгебр отношений и сформулирован ряд фундаментальных проблем, сыгравших важную методологическую роль и во многом определивших дальнейшее развитие теории (см. - [37-40]). Рассмотрение алгебр отношений в рамках аксиоматического подхода предполагает изучение их свойств, выразимых на языке логики предикатов первого порядка и, в частности, на языке тождеств и квазитождеств. .

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

1<3(1У). Для заданного класса алгебр отношенийИ, найти базис квазитождеств (тождеств) кваэимногообразиж (многообразия УК), порожденного %.

Если проблема 1 решена и найденный базис оказывается бесконечным, естественным образом встает вопрос о существовании конечного базиса. Соответствующая проблема заслуживает самостоятельного выделения:

2СЗ(2У). Длг заданного класса алгебр отношений Я выяснить, яьляется ли квазимногообразие (многообразие конечно базируемым.

В том случае, когда абстрактное замыкание 171 класса алгебр отношений 71 образует квазимногообразие, а для многих классов алгебр отношений это как раз так, проблема нахождения базиса квазитождеств приобретает особое значение и становится экви-" валентной одной из центральных в теории алгебр отношений задач отыскания элементарной характеристики (системы элементарных аксиом) класса 1И. Что "касается вопроса о том, является ли класс 1Я или, в более .общем случае, квазимногообразие многообразием, то это далеко не всегда имеет место. Вместе с тем, для ряда важных классов алгебр отношений указанное свойство выполняется. Перечисленные обстоятельства побуждают выделить еще одну проблему:

ЗС^(ЗУ). Для заданного класса алгебр отношений выяснить, образует ли абстрактное замыкание ТЯ класса К (квазимногообразие <371, порожденное классом %) квазимногообразие (многообразие).

Постановке и решению сформулированных выше проблем для различных классов алгебр отношений посвящены работы многочисленных авторов (см., например, [3, 8, 9, 10, 14-20, 24-26, 32. 35]). Исторически первым был класс ад^гебр отношений Тарско-го, представляющих собой {о,-?, Д,и,П,~,0,и}-алгебры отношений (здесь ~ - операция дополнения, а Д и II - соответственно тождественное и универсальное отношение на базисном множестве). Изучение этого класса играет важную роль в вопросах приложения теории алгебр отношений к логике (см. [35]). Квазимногообразие, порожденное классом алгебр отношений Тарского,

является многообразием [34 poro был найден Линдоном

бесконечный базис тождеств кото-17]. Манком [19] было показано, что указанное многообразие не имеет конечного базиса тождеств.

Класс {о, _1,П,Д}-алгебр отношений (полурешеточно упорядоченных инволютированных моноидов отношений)^ играющий важную роль в теории решеток, был рассмотрен йонсооном в [14], где им было показано, что абстрактное замыкание этого класса образует квазимногообразие и найден бесконечный базис его квазитождеств. Указанное квазимногообразие, а также порожденное им многообразие, не являются конечно базируемыми 12 . Проблема $У для этого класса, поставленная Жонссоном в 14],оставалось открытой.

Согласно хрестоматийной в теории полугрупп теореме

Вагнера-Престона абстрактное замыкание класса {о, -1}-алгебр частичных взаимно однозначных преобразование совпадает с многообразием всех инверсных полугрупп. Абстрактное замыкание класса {о }-алгебр отношений (инволютированных полугрупп отношений) образует квазимногообразие. Проблема 1(} для этого класса была поставлена Вагнером в 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 наименований.

СОДЕРЖАНИЕ РАБОТЫ

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

Всюду в дальнейшем N - множество натуральных чисел, К0 = N U -{0}, [ш,п] = {*е№:т<*<п}и Rel{U) - множество всех бинарных отношений, заданных на U. Всякая формула </>(zo,2i, ri,..., гт) исчисления предикатов первого порядка с равенством, содержащая две свободные индивидуальные переменные го, и бинарные предикатные символы rj,... ,rm, определяет операцию F^ на множестве Rel(U), задаваемую следующим образом:

F4,{RU...,RW) = {(я,у) 6 tfx U: р(®,у,Яь...,Ят)Ь где Rm € Rel(U) и запись йт) означает,

что формула <f(zo, z\, n,..., rm) выполняется при интерпретации r0, z\ как i, у и га,...,гт как Ri,...,Rm.

Формула называется дьофантовой [5], если она содержит в

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

Множество отношений Ф С Яе/(£/), замкнутое относительно некоторой совокупности А операций над ними, образует алгебру (Ф, П) , называемую П-алгеброй (шш просто алгеброй) отношений. Алгебру отношений назовем ¿иофантовой, если таковыми являются все ее операции. Нетрудно заметить, что отношение теоретико-множественного включения С стабильно относительно диофактовых операции и, следовательно, всякая диофантова алгебра отношений может быть рассмотрена как упорядо-

ченная отношением включения С.

Обозначим через [через {П, С}] класс всех алгебр

[упорядоченных алгебр] отношений с множеством операций П, Абстрактное замыкание класса % [соответственно квазимногообразие и многообразие, порожденное классом Щ будем обозначать ТЯ [соответственно <37? и У72].

Удобным способом описание диофантовых операций над отношениями является представление их с помощью графов. Графом (более точно - помеченным графом с метками из М) мы будем называть пару С ~ (V, £), где V = У (С?) - множество, называемое множеством вершин, и Е = Е(р) С V х N х V - тернарное отношение. Тройку (и, к, и) 6 Е будем называть ребром с меткой к, соединяющим вершину и с вершиной V, и графически изображать следующим образом: и- Д -п. Множество 1аЬ(С?) = {А; : (Эи, и)(и, к,у) Е Е} назовем множеством меток графа С.

Двухполюсником назовем граф С? с двумя выделенными вершинами гпС и огг<(? (не обязательно различными), называемыми соответственно входом и выходом этого двухполюсника. Двухполюсник С с входом { = гпС и выходом о = оиЮ будем в дальнейшем также обозначать через С?^0) или (V, ¿2, I, о).

Всякий двухполюсник С = (У,Е,{,о), где V = {но,... , V,,}, « = ио, о = «1 и £аЬ(С?) С [1,т], задает диофантову формулу </?((?) с двумя свободными переменными 2о и %\ и бинарными предикатными символами ^,..., гт, определяемую следующим образом:

¥>(С7) = (322,...,2т) Д *,■) Л»г,

где тг - атомная формула вида г0 — если г = о, и пустая формула в противном случае.

Обратно, всякая диофалтова формула <р, содержащая две свободных переменных го и 2\ задает двухполюсник С = С(^), определяемый следующим образом: У((7) - множество индексов индивидуальных переменных формулы т(7 = 0, отПС? = 1; (г, к,]) 6 2?(£?) тогда и только тогда, когда атомная формула входит в запись формулы <р\ если атомная формула

— ^ входит в запись формулы <р, то вершины г и 3 отождествляются.

Таким образом, всякий конечный двухполюсник <7 задает дио-фантову операцию ^ = -Р^о) и обратно, всякая диофантова операция Рр может быть задана с помощью двухполюсника соответствующего формуле <р. В следующей таблице для иллюстрации приведены формулы и двухполюсники, определяющие рассматриваемые в диссертации операции умножения о, обращения пересечения П, проектирования О [5, 29] и рестркк-тивного умножения >, < [1,-8] отношений, а также трактуемые •как нульарные операция тождественное отношение Д и универсальное отношение и = V х V (ребра с меткой 1 изображены с помощью сплошной, а ребра с меткой 2-е помощью пунктирной стрелки).

ч>

О (Зг2)г](гг0,г2) А Г2(г2,г1) » О

П П(.г0,г])Л г2(г0,21) * Ч ж' 1 - 0

-1 Ы-Ь^о) » 0

(Зг2)го = Лг1(г0,г2) ¡=0

(Зг2)г0 = И Лг1(22,г3) «=о

> (Зг2)г1(го,22)Л Г2(г0,г1) » 0

<3 (Зг2)г1(г0,г1)Л г2(г2,21) « о

Д Ло = 21 1 = 0

и 0 1 0

Отображение / : У(0) —»■ У(С) называется гомоморфизмом двухполюсника (7 в двухполюсник (?', если (/(и), £,/(и)) € Е(С) для всякой ребра («,&,«) € -Е(С) и /(мС) = тС?', ¡(оиЮ) =

outG'. Взаимно однозначный гомоморфизм / : V{G) V(G') называется изоморфизмам, двухполюсников, если обратное к нему отображение /-1 является гомоморфизмом G' в G. В дальнейшем, если не оговорено противное, двухполюсники будут рассматриваться с точностью до изоморфизма.

Пусть G ц G' - двухполюсники, V(G)nF(G') = 0 и u,v £ V(G). Обозначим через G[u, v, <?'] двухполюсник, полученный из двухполюсника (V(G) UV(G')}E(G).U E(G'),inG,outG) отождествлением вершины tnff' c вершиной и и вершины ouiG' с вершиной и. Двухполюсник G[u, v,G'] фактически получен из двухполюсника G "приклеиванием" к его вершинам «и« двухполюсника <?'.

Пусть G и Gjt (k = 1 ,...,т) - двухполюсники и Láb(G) С [1,...,т]. Композицией G(Gj,...,Gm) назовем двухполюсник, полученный из двухполюсника б? заменой всякого его ребра с метками ¿ на двухполюсник G*.

Основные результаты первой главы диссертации содержатся в §3, который посвящен описанию эквациональных и квазиэквацио-нальных теорий классов диофантовых алгебр отношению и отысканию базисов их тождеств-и квазитождеств.

Фиксируем класс диофантовых алгебр отношений некоторого типа г = {n/}jeJ с множеством операций ü — (jF;);€J, задаваемых с помощью системы двухполюсников {С} igjr, каждый из которых содержит nj ребер с метками 1,...,n¿ (входы и выходы двухполюсников GJ предполагаются различными). Пусть Р - множество термов с функциональными символами /,• арности п) U € «Г) и переменными x¡¡ (к 6 N). Всякому терму р 6 Р сопоставим двухполюсник G(p) посредством следующей индуктивной процедуры:

переменной г* сопоставим двухполюсник (0- -1, 0,1);

терму /¿(pi,... ,Pn¡) сопоставим композицию двухполюсников

G'J(G(Pl),...,G(p„,)).

Описание квазиэквациональных теорий классов R{Ü] и С} основано на специальным образом построенной дедуктивной системе - исчислении двухполюсников CD. Предложениями CD являются формальные выражения вида G i G2, где Gi и Gj - двухполюсники. Предложение Gj Gz является аксиомой CV в одном из следующих случаев: (Al) G1=G2;

А2) (?1 получен из (?2 отождествлением двух его вершин; АЗ) (?2 получен из (?] удалением некоторого его ребра.

Правила вывода для С7? задаются следующим образом:

г Р1 \ (?2) (?2 =» (?3 (ту)\_Ф =» _

Будем писать <р\, • • •, у?п Н ее™ предложение у о выводимо из предложений <£>],...,</>„ в исчислении

Пусть >1 = (А, {/у}<) упорядоченная алгебра типа г. Заметим, что так как равенство термов p = q может быть представлено в виде конъюнкции (р < д) Л (д < р), то всякое квазитождество на Л сводится к одному или двум квазитождествам вида:

*=п

(2.1) Д рк<Чк~* Ро < 9о,

глерк^к £ Р (£ = 0,.-..,п). • •

ТЕОРЕМА 2.1. Квазитождестпео (2.1) тогда и только тогда принадлежит квазиэквационалъпой теории класса С}, когда щ,..., Ь у>0, г<?е у* = (7(рк) => С?^) (й = 0,... ,«,).

В качестве непосредственного следствия теоремы 2.1 получено описание квазиэквалщональной теории класса К{Щ (следствие 2.1). Еще одним важным следствием теоремы 2.1 является следующий результат, характеризующий эква-пиональные теории классов К {О,} и с}. Будем писать С -< (л, если существует гомоморфизм (7 в С, и С = С, если С -< <? и С -< С.

Следствие 2.2. Тождество р = д [р < д] принадлежит эквационалъной теории Ед{й} [.Е7д{0,с}] класса класса с}] тогда и только тогда, когда й(р) = &'(д)

эд ад.

Из следствия 2.2 непосредственно вытекает разрешимость эквациональных теорий классов Т1{£1] и Щй, с} (следствие 2.3). Далее в §2 этот результат используется для описания свободных алгебр указанных классов (следствие 2.4) и нахождения базиса тождеств классов алгебр отношений с операцией объединения (следствие 2.5).

Конструкция, используемая при доказательстве теоремы 2.1, позволяет также найти бесконечный базис квазитождеств квазимногообразия с}. Он приводится в теореме 2.2. Завершает §2 следующая теорема, дающая частичное решение проблемы ЗС^ для классов диофантовых алгебр отношений. Назовем дио-фантову операцию Ра связной, если таковым является задающий ее двухполюсники б, и сильно несвязной, если вход и выход двухполюсника С? принадлежит разным его компонентам связности.

ТЕОРЕМА 2.3. Пусть все операции из О связные. Тогда классы Г£{0} ис} образуют квазимногообразия. Обратно, ссли'О, содержит хотя бы одну сильно несвязную операцию и о £ £1, то классы и С} «е являются квазимного-

образиями.

Основные результаты второй главы диссертации, объединяющей параграфа 3-6, посвящены решению проблем 1, 2 и ЗУ для классов редуктов алгебр отношений Тарского с совокупностью операций {о} С & С {о,-1,П,и,Д}. Что касается проблемы то согласно теореме 2.3 для указанных классов.она решается положительно, если и £ й, и отрицательно в противном случае.

В §3 рассмотрены алгебры отношений с множеством операций . {о} С й С {о,П}. Общеизвестно, что абстрактное замыкание класса {о}-алгебр отношений (полугрупп отношений) совпадает с классом всех полугрупп. Как показано в [4], абстрактное замыкание класса упорядоченных полугрупп отношений совпадает с классом всех упорядоченных полугрупп. Следующая теорема значительно усиливает этот результат и позволяет решить проблемы 1-3 для класса 7£{о, П} полурешеточно упорядоченных полугрупп отношений.

Отношение Я называется плотным, если его проекции совпадают с базисным множеством, и асимметричным, если ЛП Л-1 = 0.

ТЕОРЕМА 3.1. Для всякой упорядоченной полугруппы (•<45 ■) <) существует изоморфизм / в некоторую упорядоченную полугруппу плотных асимметричных отношений, удовлетворяющий условию

/ИВ)=пдь) 1 №

для всякого подмножества В С А, имеющего точную нижнюю грань ШВ.

Следствие 3.1. Абстрактное замыкание класса {о, П] -алгебр отношений совпадает с многообразием всех полу-решсточно упорядоченных полугрупп.

Далее в §3 в качестве следствия получен результат из [91, дающий описание базиса тождеств многообразию У7£{о,и,П) (следствие З.2.).

Теорема 3.1 имеет также ряд интересных приложений (следствия 3.3 -3.7) к вопросам представления упорядоченных полугрупп и решеток, среди которых особо отметим

Следствие 3.6. Абстрактное замыкание класса {о,П}-алгебр отношений порядка совпадает с классом всех решеток.

Следствие 3.7. ([23]) Всякая решетка изоморфно вкладывается в решетку топологий на некотором множестве.

В §4 рассмотрены алгебры отношений с множеством операций {о,и} С й С {о,Л,и). Назовем а-полугруппой алгебру (А,-,и) типа (2,0), где (Л, •) - полугруппа и и - некоторый элемент из А. Всякая {о, и}-алгебра отношений является и-полугрупгой, называемой и - полугруппой отношений. Формулируемые ниже результаты не только решают проблемы 1-3 для классов алгебр отношений <37С{о,и,с} и <ЗЯ{°,П,и}, но и дают элементарную характеристику этих классов.

ТЕОРЕМА 4.1. Упорждоченпаж и-полугруша (А, -,и,<) тогда и только тогда принадлежит классу 17£{о,и,С} [соответственно квазимногообразию С^{о,и,с}], когда она удовлетворяет следующим условиям:

(4.1) и2 = и, (4.2) х < и, (4.3) I < жиж, (4.4) ихи ф и ту = ух = х, (4.5) ии ф и -* х < у [соответственно условиям (4.1)-(4.3)].

ТЕОРЕМА 4.2. Полурешеточно упорядоченная и-полугруппа (А, Л, и) тогда и только тогда принадлежит классу Г£{о,П,и} [соответственно квазимногообразию С}7£{о,П, и,}], когда она удовлетворяет условиям (4.1)-(4.5) [соответственно условиям (4.1)—(4.3)] теоремы 4.1 и тождествам

х(у А иг) = ху Л иг, (хи Л у)г = хи Л уг, х(у Л ги) — ху А хги (их Л у)г = ихг Л уг.

Далее в качестве следствия (следствие 4.1) теоремы 4.1 найде-

на элементарная характеристика класса 1&{о,и} и бесконечный базис квазитождеств квазимногообразия Q'R■{o,U} и, тем самым, решена соответствующая проблема, поставленная в [26]. Что касается многообразия УЩо, и}, конечный базис его тождеств дает следующая

ТЕОРЕМА 4.3 и-полугруппа (А, и) тогда и только тогда принадлежит многообразию У7£{о,и}, когда она удовлетворяет тождеству (4.1) теоремы 4.1 и тождествам

игиуи = иуихи, хуиги = хуи, иуиху = ту. В §5 рассмотрены алгебры отношений с множеством операций {о,"1} С П С {о,-1, Д,и}. Инволютированной полугруппой называется алгебра (А,-,-1) типа (2,1), где (Л,-) - полугруппа и - унарная операция, удовлетворяющая тождествам (х-1)-1 = х, (г:/)-1 = у~1х~1. Всякая {о, _1}-алгебра отношений является инволютированной полугруппой, называемой инволютированной полугруппой отношений.

Назовем п-диадои пару а? = {'-р,ф), где у,ф-: [1,п] [0, и] -отображения, удовлетворяющие условию <к и ф(к) < к для

всякого к = 1____, п. Каждой п-диаде ш = (<р, ф) сопоставим граф

= (К,, где К, = [0, тг] и Еи = {(0,1,1)} и {{<р{к),2к,к+ 1),(к+ 1,2* +1,^)): к € [1, п]}.

Со всякой цепью а графа (?ы, последовательно проходящей по ребрам с метками ассоциируем терм з(х) = х^ .,.х|™,

где ^ = 1 = -1), если ребро с меткой ¿ц проходится по (против) его ориентации. Обозначим через (к = 1.... ,п,

!,_/ < к) множество всех цепей графа из вершины г в вершину содержащих лишь ребра с метками 1,... ,2к - 1. Следующая теорема решает проблемы 1С}, IV и 2У для класса упорядоченных инволютированных полугрупп отношений.

ТЕОРЕМА 5.1. Упорядоченная инволютпированная полугруппа А = (А, •,-1,<) тогда и только тогда принадлежит классу 171{о,-1, с}, когда для всякой п-диады ш — и-любых цепей «о € 5^(0?), € ^*)(<*>) (к = выполняется

■квазитождество

п

А з*(х) < Х2АХгН1 х\ < к=\

Более того, если при этом А содержит единичный элемент е [соответственно наибольший элемент и], то упорядоченная алгебра (А,-,-1,е,<) [соответственно (А, •,-1,и,<) ] принадлежит классу1Л{о,~,А,с} [соответственно квазимногообразию ЪП{о,-\Х5,с}}.

Упорядоченная инволютированная полугрупп А тогда и только тогда принадлежит многообразию когда она удовлетворяет тождеству х < хх~1х.

Заметим, что базис квазитождеств для класса 172{о, _1,С) впервые был получен автором [А.4]. Шайном [25] была предложена удобная форма записи аксиом этого класса с помощью графов.

В качестве следствия теоремы 5.1 (следствие 5.1) получен бесконечный базис квазитождеств квазимногообразия 17£{о,-1,} и тем самым решена проблема, поставленная Вагнером в 1953 году. Далее в §5 в качестве следствия получен результат из [9], дающий описание базиса тождеств многообразию У7?.{о,-1,и} (следствие 5.2.).

Следующая теорема решает проблему 2<3 для квазимногообразия 1Щ°Г1}- '

ТЕОРЕМА 5.2. Квазимногообразие 1К.{о,-1} не имеет конечного базиса квазитождеств.

В качестве следствия "теоремы 5.2 получен следующий результат из [25].

Следствие 5.3. Класс 172{о, ~3} кс является многообразием. Многообразие У7?.{о,-1} совпадает с классом всех тволютиро-ванных полугрупп.

Несмотря на бесконечность найденной в теореме 5.1 системы квазитождеств, она оказалась достаточно удобной для приложений й позволяет полутать конечные базисы квазитождеств для упорядоченных инволютированных полугрупп отношений различного специального вида и ряд достаточных условий представимости (теоремы 5.3, 5.4 и следствия 5.3 - 5.10). Сформулируем лишь один из соответствующих результатов.

Инволютированную полугруппу (А, -1) назовем вполне простой, если таковой является полугруппа (А,-). Инволютированную полугруппу отношений (Ф,о,-1) назовем примитивной, если для любых Я, # Е Ф, ЙСЯ-+Л=Я,и С рг\Н -» рглН — рпЯ, рг2Я С яг2Я рг2Я = рг2Я. Отношение Я

называется бифункциональным [5], если Л о Я-1 о Я С Я- Ди-функциональные отношения играют важную роль в различных разделах современной алгебры (см. [8]).

ТЕОРЕМА 5.4. Для инволютированной полугруппы А = (А, ~1) следующие условия эквивалентны:

a) Л вполне проста и удовлетворяет тождеству хх-1г = х

b) А изоморфна некоторой примитивной инволютированной полугруппе дифункционалъных отношений;

c) А удовлетворяет тождеству х = ху~1ух~1х.

В §6 рассмотрены алгебры отношений с множеством операции

{о,-1,п}сас{о,-1,п,д,и}.

ТЕОРЕМА 6.1. Полурешето чно упорядоченная инволюти-рованная полугруппа А = (А,-,-1,Л) тогда и только тогда принадлежит классу -1,П}, когда для всякой диады ш = (у?,*/») и любых термов рк (к = 0,.,.,п) таких, что б!?'1' ■< (*(ро) « @{Рк) (к = 1,... п) выполняется квазитождество

■ я*

ДРк<*2*»2*+1-*®1<Р0.

А=1

Более того, если при этом А содержит единичный элемент е [соответственно наибольший элемент и], то алгебра (А,•,-1,Л,е) [соответственно (А,-,-1,Л,и) } принадлежит классу ГК.{о,-1,П, Д} [соответственно квазимногообразию дя{о,-1,п,и}].

Отметим, что базис квазитождеств квазимногообразия 17£{о, _1,П,Д}, несколько отличный от приведенного в теореме 6.1, впервые был найден Йонссоном [14]. Предложенная им конструкция доказательства существенно использовало наличие единичного элемента.

Следующая теорема решает проблему, поставленной Йонссоном в [14] (проблема ЗУ для класса Д}).

ТЕОРЕМА 6.2. Квазимногообразия Г£{о,-1,Л} и 172.{о, , П, Д} не являются многообразиями.

Согласно результату Халмана [12], квазимногообразия 1П{о,-\п), 1Я{о,-1,П,Д} и многообразия У7г{о,"1,П}, УИ{о,, П, Д}, ими порожденные, не являются конечно базируете

мыми. Тем не менее, как оказалось, при некоторых дополнительных условиях система квазитождес.тв, найденная в теореме 6.1, может быть сведена к конечной системе аксиом.

Полурешеточно упорядоченную инволютированную полугруппу назовем дистрибутивной, если она удовлетворяет тождеству х(у А г) = ху А хг.

ТЕОРЕМА 6.3. Дистрибутивная полурешеточно упорядоченная инволютированная полугруппа тогда и только тогда принадлежит классу Г£{о,-1,п}, когда она удовлетворяет тождествам, х<хх~*х, ху А г < хх~1г.

Далее в §6 в качестве следствия теоремы 7.2 получена конечная система тождеств, характеризующая класс {о,-1,П, Д}-алгебр частичных взаимно однозначных преобразований (следствие 6.2) и доказана вложимость произвольной дистрибутивной инволюти-ровэнной решетки в инволютированную решетку отношений квазипорядка на некотором множестве (следствие 6.3).

Основные результаты третьей главы диссертации, объединяющей параграфы 7-9, касаются решения проблемы для классов алгебр отношений с операциями проектирования и рестриктив-ного умножения. В §7 рассмотрены алгебры отношений с множеством операций С С {о,—Ж,

Назовем полугруппой -алгебру (А, •,* ,*) типа (2,1,1), где (Л,-) - полугруппа и *, * - унарные операции, удовлетворяющие следующим тождествам:

{х'У = х*, (я*)' = х*, (х'у'У = х*у% (х*у*)* = х*у\ х*х = X = XX*, х*у* = у*х*, (ху)* = (гу*)*, (ху)* = (х*у)*.. Всякая {о,3{,3;}-алгебра отношений является С?-полугруппой, называемой ^-полугруппой отношений.

Заметим, что понятие КЗ-полугруппы является обобщением введенного Швайцером и Скляром в [29] понятия системы функций. Система функций Швайцера и Скляра представляет собой полугруппу, удовлетворяющую дополнительному тождеству х*у = у(ху)*. Указанное тождество справедливо для о, 9}-алгебр частичных преобразований, но ложно в классе о, Ж,-алгебр отношений.

Итолчотированной Ш^-полугруппой назовем алгебру (А,-,-1,*,*) типа (2,1,1,1), где (А, •,~1) - инволютированная полугруппа, (А,-,*,*) - 3?3-полугруппа и х* = (х-1)*. Всякая {о,-1,К,5}-алгебра отношений является инволютированной

^-полугруппой, называемой инволютированной полугруппой отношений.

ТЕОРЕМА 7.1. Упорядоченная инволютированная ШЗ-полугруппа Л = (А,-,"1,тогда и только тогда при-надлщищ классу I72.{oJ—1,3fi,^»С.}, когда она удовлетворяет тождествам: х*у < у, х* < хх

В качестве следствия теоремы 7.1 (следствие 7.1) получен бесконечный базис квазитождеств квазимногообразия который для случая алгебр дисфункциональных отношений сведен к конечной системе тождеств (следствие 7.2). Теорема 7.1 имеет еще одно интересное следствие, касающееся представления полурешеточно упорядоченных инволютирован-ных моноидов. Заметим, что в приложениях теории алгебр отношений к логике важную роль играет следующее условие (см. [35]): (*) (3ti,w)(Vx)u_1ii < е Л v-1t; < е Л х < u-1v.

Следствие 7.3. Полурешеточно упорядоченный инволюти-рованный моноид (Л,-,-1^^) удовлетворяющий условию (*)} тогда, и только тогда принадлежит классу ГК{о,-1,П, Д], когда он удовлетворяет тождеству ху А z < (х Л yz~1)y.

Заметим, что в общем случае множество D(Ü) всех дифунк-циональных отношений, заданных на U,' не замкнуто относительно относительно операции умножения отношений. Поэтому естественно рассмотрение новой операции • на D(U), определяемой следующим образом:

R*H = (){Q€D(U):RoH CQ).

Отношение R • Н представляет собой дифунзщпональвое замыкание произведения R о Я отношений Л и Я. Интерес к этой операции в первую очередь обусловлен тем, что для частичных взаимно однозначных преобразований R • Я совпадает с их произведением Я о Я, а для отношений эквивалентности - с точной верхней гранью RVH в решетке отношений эквивалентности, т.е. с. транзитивным замыканием объединения R U Н отношений R и Я. Это позволяет использовать результаты, относящиеся к алгебрам дифункциональных отношений с операцией для представления инверсных полугрупп и решеток.

ТЕОРЕМА 7.2. Для всякой упорядоченной инволютированной полугруппы (Л,,*,*,<), удовлетворяющей условиям теоремы 7.1 и тождеству хх~гх = х, существует изоморфизм

Р в упорядоченную {•, 1 -алгебру дифунщиональных отношений такой, что

р(ыв)= 0^(6)

для любого подмножества В С А, имеющего точную нижнюю грань т£ В.

В качестве следствий теоремы 7.2 (следствие 7.5 - 7.8) получен рад результатов, касающихся представления инверсных полугрупп и решеток, в частности, известная теорема Уитмена [36] о вложимости произвольной решетки в решетку отношений эквивалентности на некотором множестве.

В §8 рассмотрены алгебры отношений с множеством операций {о, Е>, <]} С & С {о, _1,Е>, <,П}. Приведем ряд определений, необходимых для формулировки основных результатов этого параграфа. Рестриктивной полугруппой 1-го [2-го] рода называется полугруппа (А,►) [(А,-*)], удовлетворяющая тождествам. х > х — х, х ► у > г = у ► х г [х <' х = х, х 4 ;у < г = х г < у]. Рестриктивной биполугруп-■ пой называется алгебра (А, -4), где (А,*►) и (А, «$) - рестрик-тивные полугруппы 1-го и 2-го рода соответственно и выполняется тождество (х ► у) ■< г = х ► (у < г). Следуя [8], назовем стогом алгебру (А, где (А,-) - полугруппа,

(А, <) - рестриктивная биполугруппа и выполняются тождества: х ► уг = {х > у)г, ху < г — х(у < г) (здесь и в дальнейшем мы будем предполагать, что операция умножения связывает переменные сильней чем операции ► и Всякая {о, [>, о]-алгебра отношений являются стогом, называемым стогом отношений.

ТЕОРЕМА 8.1. Упорядоченный стог (А, •,►,«,<) тогда и только тогда принадлежит классу 17?.{о,С>,<,С}, когда он удовлетворяет следующим тождествам: (8.1) ху ► х(у > г) = х(у ► г), (8.2) (х 4 у) « уг = (х <4 у)г, (8.3) х(уг ► ь) = х((у « ху)г ► »), (8.3) (х 4 уг)у = (х 4 у(гу ► г)),

(8.5) х>у*г<у, где переменная г в тождестве (8.3) и переменная у в тождестве (8.4) может быть пустым символом.

ТЕОРЕМА 8.2. Еолурешеточно упорядоченный стог (А, Л) тогда и только тогда принадлежит классу

>,<!,(!}, когда он удовлетворяет тождествам (8.1), (8.2) теоремы 8.1 и тождествам

х ► (у Л г) = х ► у Л г, (х А у) * г = х Л у < г.

Иивалютиравакным стогом назовём алгебру (А,-,-1,►,■<), где (А,-,-1) - инволютированная полугруппа, (А, - стог

и выполняется тождество (1 [> у)-3 = у-1 <3 х-1. Всякая {о,-1,>,<}-алгебра отношений являются инволютированньш стогом, называемым инволютированньш стогом отношений.

ТЕОРЕМА 8.3. Упорядоченный инволютированный стог (А,-,"1,►,«,<) тогда и только тогда принадлежит классу 171{о,>, <, с}, когда он удовлетворяет тождеству (8.5) теоремы 8.1 « тождествам

ху ► г = (х < у"1) ► г), х{у ► г) = {х < у~х)г, х>у<хх~1у.

В качестве следствий сформулированных результатов в §8 также получены бесконечные базисы квазитождеств квазимногообразий иг{0, >, <} и 1И{о, -1 >, <,}.

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

Класс группоидов отношений с операцией, задаваемой с помощью двухреберного двухполюсника С, обозначим через %{0}. Операции рестриктивного умножения отношений > и < задаются

с помощью двухполюсников • ------и------. Измене-

«010 ние ориентации ребер указанных двухполюсников приводит нас к

следующим четырем новым классам (с точностью до двойственных) группоидов отношений: %{---•. ——}, И{---• *• — },

ТЕОРЕМА 9.1. Группоид (А, •) тогда и только тогда принадлежит классу группоидов •—»-• --•*•}, когда он удовле-

творхет тождествам

фу) = ХУ> x(yz) = y(xz), (xy)(yz) = (xy)z.

ТЕОРЕМА 9.2. Группоид (А, •) тогда и только тогда принадлежит классу группоидов -------}, когда он удовлетворяет тождествам х{у(ч)) = ХУ> х{у(™)) = г(у(хи)), x(y(x(z(uz)))) = x{y(uz)), (ф(уг)))и = х(и(уг)и)), (xy)(z(uv)) = x(z(uy)v)).

Системы тождеств, характеризующие классы группоидов Щ\------*•} и -------} двойственны полученным в

«о го

теоремах 9.1 и 9.2,

Четвертая глава диссертации, объединяющая параграфы 10 -11, посвящена некоторым приложениям результатов главы I для описания клонов операций над отношениями (§10) и характериза-щш производных структур над универсальными алгебрами (§11).

Одна из проблем, сформулированная Тарским, связана с харак-теризацией формул исчисления предикатов, выразимых с помощью тождеств алгебр отношений. Рассмотрение этой проблемы естественным.образом приводит к задаче изучению "выразительных возможностей" заданного набора Ü операций над отношениями. Алгебраическая трактовка этой задачи состоит в описании клона операций над отношениями, порожденного операциями из Ü. Обзор некоторых результатов в этом направлении можно найти в [11, 15]. Другим побудительным мотивом изучения клонов операций над отношениями является возможность применения результатов из этой области к проблемам отыскания конкретных характеристик производных объектов над универсальными алгебрами (см. [22]).

Клон операций, порожденный множеством операций Ü, заданных на А, обозначим Со всяким двухполюсником

G ~ (V,E,i,o) ассоциируем неориентированный граф без кратных ребер б?+ = (У,Е+), рассматриваемый как бинарное отношение на У, множество ребер которого определяется следующим образом:

£+ = i;ul;-1u{(t», (о,»)}, где Ё = {(«,«) : (3fc) {u,k,v) € Е}.

Рассмотрим следующее свойство двухполюсника G: (*) существует эндоморфизм f двухполюсника. G такой, что граф jf(G)+, ассоциируемый с образом двухполюсника G при

этом эндоморфизме, не содержит подграфов гомеоморфных полному графу на четырехэлементном множестве.

Следующая теорема дает критерий принадлежности диофанто-вой операции к клону, порожденному днофантовыми операциями алгебр отношений Тарского.

ТЕОРЕМА 10.1. Для всякого множества 17 и двухполюсника (?, удовлетворяющего условию (*), имеем

Обратно, если Ев 6 С7де#(/){о,-"1,П, Д,и} и множество V не менее чем счетно, то двухполюсник й удовлетворяет условию

(*)■

Известно [11], что клон всех диофантовых операций на Ле/((7) не может быть порожден конечным набором операций. Однако, как это следует из приводимых ниже результатов, клон всех диофантовых операций на множестве 1(11) всех частичных взаимно однозначных преобразований, заданных на £7, является конечно порожденным. Обозначим через (соответственно через

клон всех диофантовых операций на 1{и) (соответственно клон всех диофантовых операций на J(U), задаваемых связными двухполюсниками). Рассмотрим унарную диофантову операцию V, определяемую следующим двухполюсником: . • • —» •

1—0

= Д, если К ф 0, и 7(Д) = 0 в противном случае).

ТЕОРЕМА 10.2. = С/^К^АД} и

Со всякой универсальной алгеброй Ы может быть ассоциирован ряд производных объектов таких, например, как решетка подалгебр 5и(14), группа автоморфизмов Аи^К), моноиды эндоморфизмов Епв,{Ы) и мономорфизмов Мт{Ы) и т.д. К числу таких объектов относится и инверсная полугруппа локальных автоморфизмов универсальной алгебры.

Локальным автоморфизмом универсальной алгебры называют изоморфизм между ее подалгебрами. Множество всех локальных автоморфизмов универсальной алгебры Ы относительно операций умножения и обращения отношений образует инверсную полугруппу, которую мы назовем инверсной полугруппой локальных автоморфизмов алгебры и и обозначим Ьа(Ы).

Под цепью частичных взаимно однозначных преобразований

мы будем понимать такое множество Ф С /(У), которое является цепью относительно отношения включения. Множество Ф С 3{Р) назовем совместным, если уФ € J(U).

Следующий результат, доказательство которого существенно использует теорему 10.2, дает конкретную характеристику инверсных полугрупп локальных автоморфизмов универсальных алгебр [унарных алгебр]. ' .

ТЕОРЕМА 11.1. Инверсная полугруппа Ф частичных взаимно однозначных преобразований множества и тогда и только тогда является инверсной полугруппой локальных автоморфизмов некоторой универсальной алгебры [унарной алгебры], заданной на и, когда она удовлетворяет следующим условиям:

В) р|Ф 6 Ф для всякого непустого подмножества Ф С Ф; <?) уФ € Ф для всякой непустой цепи [совместного подмножества] Ф С Ф ;

4) {(и,и)},{(»,«} £ Ф влечет {(и,и)] £ Ф.

• Отметим, что несколько отличная от приведенной в теореме 11.1 характеристика инверсных полугрупп локальных автоморфизмов универсальных алгебр была независимо получена в [31]. Далее в §11 в качестве следствий (следствия 11.1 - 11.9) получена совместная конкретная характеристика полугрупп мономорфизмов и решеток подалгебр универсальных алгебр и ряд результатов усиливающих соответствующие результаты работ [2,12, 30].

ЦИТИРУЕМАЯ ЛИТЕРАТУРА

1. Вагнер В.В. Теория отношений и алгебра частичных преобразований // Теория полугрупп и ее приложения. - Саратов, 1965.

- Вып. 1. - С.3-197.

2. Доманов О.И. Полугруппы всех частичных автоморфизмов универсальных алгебр // Изв. вузов. Математика. - 1971. - N 8. -С.52-58.

3 Зарецкии К.А. Представление упорядоченных полугрупп бинарными отношениями // Изв. вузов. Математика. - 1959. - N 6.

- С.48-50.

4. Ершов Ю.Л., Лавров И.А., Тайманов А.Д., Тайцлин М.А. Элементарные теории Ц УМН. - 1965. - Т.20. - N 4. - С.37-108. Матем. сб. - 1940. - N 8. - С.251-264.

5. Мальцев А.И. О некоторых пограничных вопросах алгебры и логики // Труды международного конгресса математиков. -

Москва, 1966. - С.217-231.

6. Мальцев А.И. Алгебраические системы. - М., "Наука", 1970.

7. Риге Ж. Бинарные отношения, замыкания, соответствия Га-луа // Кибернетический сборник. - 1963. - N 7. - C.129-1S5.

8. ШайнВ.М. Рестриктивно-мультипликативные алгебры // Изв. вузов. Математика. - 1970. - N 4. - С.91-102.

9. Andréka H. Representations of distributive lattice-ordered semigroups with binary relations // Alg. Univers. - 1991. - V.28. -P.12-25.

10. Andréka H., Mikulâs Sz. Lambek calculus and its relational semantic: completeness and incompleteness // Journal of Logic, Language and Information. - 1994. - N 3. - P.l-37.

11. Bônex F., Pôschel R. Clones of operations on binary relations // Contributions to general algebras. - Wien, 1991. - V.7. - P.50-70.

12. Gould M. Subalgebra maps induced by endomorpbisms and automorphisms of algebras // Alg. Univers. - 1972. - V. 2. - P.88-94.

13. Haiman M. Arguesian lattices are not type I // Alg. Univers. -1991. - V.28. - P.191-199.

14. Jonsson B. Representation of modular lattices and. of relation algebras // TVans. Amex. Math. Soc. - 1959. - V.92. - P.449-464.

15. Jônssoxi B. The theory of binary relations / / Collog. math. Soc. J. Bolyai. - 1991. - Y.54. - P.201-247.

16. Kozen D. On inductions vs. ^-continuity // Pros. Workshop on Logics of Programs, Lect. Notes in Comput. Sci. - Berlin, 1982. -P. 167-176.

17. Lyndon R.C. The representation of relation algebras, II // Ann. Math. - 1956. V.63. - N 2. - P.294-307.

18. Maddux R.D. The origin of relation algebras in the development and axiomatization of the calculus of relations // Stadia Logica -1991. - V. 51. - P.423 - 455.

19. Monk D.M. On reprcsentable relation algebras // Michigan Math. J. - 1964. - V.H.- P.207-210.

20. Monk D.M. Lattice theory and general algebra. - Lecture notes University of Colorado, Boulder, 1969.

21. Németi I. Algebraizations of quantifies logic: an introductory overview // Stadia Logica, Special issue. - 1990.

22. Pôschel R. A general Galois theory for operations and relations and concrete characterization of related algebraic structure / / Report R-01/80, Institute of Math., AdWdDDR, Berlin, 1980.

23. Rosicky J. Embedding of lattices in the lattice of topologies // Arch. Math. - 1973. - V.9. - P.49-56.

24. Schein B.M. Relation algebras and function semigroups // Semigroup Forum. - 1970. - V.l. - N 1. - P.l-62.

25. Schein B.M. Representation of involuted semigroups by binary relations // Fundamenta Math. - 1974. - V.82. - N 2. - P.121-141.

26. Schein B.M. Representation of reducts of Tarski relation algebras ff Colloq. Math. Soc, J. Bolyai. - 1991. - V.54. - P.379-394.

27. Schmidt E.T. Universale Algebran mit gegebenen Automorphismen - gruppen und Unteralgebren / j Acta Sei. Math. - 1963.- V.42. - P.251 - 254.

28. Schmidt G., Ströhlien T. Relationen und Graphen. Series Mathematik für Informaticer. - Berlin, Springer - Verlag, 1989.

29. Schwizer В., Sklar A. Function system // Math. Ann. - 1967. V.172.- P.l - 16. .

30. Stoöe M.G. Subalgebra and automorphism structure in universal algebras: a concrete characterization // Acta. Sei. Math. - 1972. -V. 33. - P.45 - 48.

31. Sz&bó L. Characterization of some íelated semigroups- of universal algebras // Acta. Sei. Math. - .1975.'- V. 37. - P.143 - 147.

' ' 32. Tarski A. On the calculus of relations //J. Symbolic Logic. -1941. - V.6. - P.73 - 89.

33. Tarski A. Some methodological results concerning the calculus of relations // J. Symbolic Logic. - 1953. - V.18. - P.188 -189.

34. Tarski A. Contribution to the theory of models, III // Indagat. Math. - 1955. - V.17. - P.39 - 46. ^

35. Tarski A., Givant S.F. A formalization of set theory without variables. - Amer. Math. Soc. Publ. 41, Providence, R.I., 1987.

36. Whitman P.M. Lattices equivalence relations, and subgroups // Bull. Math. Soc. - 1946. - V.52. - P.507-522.

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

Al. Бредихин Д.А. Представление упорядоченных инволютиро-ванных полугрупп // Изв. вузов. Математика. - 1975. - N 7. -С.19-29.

А2. Бредихин Д.А. Инверсные полугруппы локальных автоморфизмов универсальных алгебр / / Сибир. матем. журн. - 1975. Т.17. - N 3. - С.490-507.

A3. Бредихин Д.А.Абстрактная характеристика некоторых клас-

сов алгебр бинарных отношении // Алгебра и теория чисел. -Нальчик, 1977. - Вып. 2. - С.3-19.

А4. Бредихин Д.А. Упорядоченные инволютированные полугруппы квазиполных бинарных отношении // Теория полугрупп и ее приложения. - Саратов, 1978. - Вып. 4. - С.3-11. А5. Bredikhin D.A., Schein В.М. Representations of ordered semigroups and lattices by binary relatoins // Colloq. Math. - 1978.-V.49. - P.2-12.

A6. Бредихин Д.А. Инверсные полугруппы локальных автоморфизмов // УМН - 1979. - Т.34. - N 4. - С.181-182. А7. Bredikhin D. A. A representation theorem for similattices // Proc. of Amer. Math. Soc. - 1984.- V.90. - P.219-220. A8. Бредихин Д.А. Рестриктивно-мультипликативные алгебры бинарных отношений // Теория полугрупп и ее приложения. -Саратов, 1985. - Вып.5. - С.9-22.

А9. Бредихин Д.А. Инволютированные полугруппы квазиоднозначных бинарных отношений // Теория полугрупп и ее приложения. - Саратов, 1987. - С.3-9.

А10. Bredikhin D.A. On relation algebras with general superpositions // Coll. Math. Soc. Janos Bolyai. - 1991. - V.54. - P.lll-124. All. Bredikhin D.A. Varieties of groupoids associated with involuted • restrictive bisemigroups of binary relations'// Semigroup Forum. -1992.-V.44. - P.87-92.

A12. Bredikhin D.A. Reducing of relation algebras to semigroups // Tartu Ulikooli Toimedised. - 1992. - V.953. - P.3-6. A13. Бредихин Д.А. О клонах операций на множестве частичных взаимно однозначных преобразований // Теория полугрупп и ее приложения. - Саратов, 1993. - Вып.11. - С. 3-8. А14. Бредихин Д.А. Эквациональная теория алгебр отношений с позитивными операциями // Изв.. вузов. Математика. - 1993. -N 3. - С.23-30.

А15. Bredikhin D.A. On algebras of relations / / Banach Center Publ. - V.28. - Warszawa, 1993. - P.191-199.

A16. Bredikhin D.A. Representation of inverse semigroups by (Afunctional multipermutatioas // Pioc. of Essex Conf. "Transformation semigroups". - Univ. of Essex, Colchester, 1993. - P.l-11. A17. Bredikhin D.A., Andreka H. The equational theory of union-free algebras of relations // Alg. Univers. - 1994. - V.33. - P.516-532. A18. Bredikhin D.A. On semilattice ordered involuted monoids of

relations // In: "Semigroups, Automata and Languages", World Scientific, Singapore, 1996, P.ll-15.

A19. Bredikhin D.A. How representation theories of inverse semigroups and lattices can be united ? // Semigroup Forum. - 1996. -V.53. - N 2. - P.184-193.

A20. Бредихин Д.А. О квазитождествах алгебр отношений с дио-фатновьши операциями // Сибир. матем. журн. - 1997. - N 1. -С. 29-41.

Тезисы сообщений автора на конференциях

al. Бредихин Д. А. Полугруппы квазиполных бинарных отношений // Тезисы сообщений 12 всесоюзного алгебраического коллоквиума. - Свердловск, 1973. - Т. 2. - С. 199. а2. Bredikhin D.A. Local endomorphism monoids of universal algebras // Abstracts of Colloquim on Universal algebras. - Szeged, 1983.

- C.ll.

аЗ. Бредихин Д.А. Полугруппы квазиоднозначных отношений // Тезисы сообщений 18-ой всесоюзной алгебраической конференции.

- Кишинев, 1985. - С.67.

а4. Бредихин Д.А. йнволютированные R-полугруппы бинарных отношений // Тезисы докладов 3-ей всесоюзной конференции по теории полугрупп. - Свердловск, 1988. - С.10. а5. Бредихин Д.А. О слабо представлмом многообразии алгебр отношений Тарского // Тезисы докладов международной конференции по алгебре. - Новосибирск, 1989. - C.1S. аб. Bredikhin D.A. On groupoids of binary relations with general superposition // Abstracts of Colloquim on Universal Algebras. -Szeged, 1989. - P.18.

a7. Бредихин Д.А. Редукция алгебр отношений Тарского // Тезисы докладов X всесоюзной конференции по математической логике. - Алма-Ата, 1990. - С-.25.

а8. Бредихин Д.А. О многообразии, порожденном классом упорядоченных инволютировалных полугрупп бинарных отношений Ц Тезисы докладов 2-ых математических чтений памяти М.Я.Суслина. - Саратов, 1991. - С.27.

а9. Bredikhin D.A. Description f clones of Jonsson's relation algebras // Тезисы докладов международной конференшш по алгебре. -Новосибирск, 1991. С.20.

аЮ. Д.А Бредихин Д.А. Эквашгональная теория алгебр отношений с позитивными операциями // Тезисы докладов XI межрес-

публиканской конференции по логике. - Казань, 1992. - С.З. all. Bredikhin D.A. On Jonsson's relation algebras ) j J. Svmbolic Logic. - 1993. - V.58. - C.1124 (abstracts of the 1992 European Summer Meeting of the ASL.- Abstracts of Colloquim on Universal algebras. - S2eged, 1983. - C.ll.

al2. Bredikhin D.A. The primitive positive clone of operations // Summaries of talks, 16th Algebraic Conferences in Szeged "Lattices, ordered sets and universal algebra". - Szeged, 1993. - P.6. al3. Bredikhin. D.A. Multi-valued transformation semigroups and reducts of Tar ski's relation algebras // Abstracts of Essex Conf. on Transformation Semigroups and their Applications. - Colchester, 1993. - P.l.

a!4. Бредихин Д.А. О многообразиях, порожденных редуктами алгебр отношений Тарского // Тезисы докладов 3 международной конференции по алгебре. - Красноярск, 1993. - С.51. а15. D.A.Bredikhin. On the variety generated by lattice of permuting equivalence relations // Abstracts of the conf. "Algebra and Combinatorics". - Konigstein, 1994, P.l-2.

al6. Bredikhin D.A.'On semilattice ordered monoids of binary relations // Abstracts of Conf. "Semigroups, Automata, Languages". -Porto, 1994. - P. 11.

al7.' Bredikhin D.A. How representation theories of inverse semigroups and lattices can be married ? // Abstracts of Colloq. on semigroups. - Szeged, 1994. - P.9.

al8. Bredikhin D.A.. On lattices of equivalence relation // Тезисы сообщений международной конференции по математической логике. - Новосибирск. 1994. - С.31.

а19. Bredikhin D.A. On semigroups of binary relations pointed by the universal relation // Тезисы докладов международной конференции "Полугруппы и их приложения, включая полугрупповые кольца". - Санкт-Петербург, 1995. С. 6-7. а20. Bredikhin D.A. The quasiequanional theory of relation algebras / / Abstracts of ASL Logic Colloquim 95. Model theorv. - Haifa, 1995. - P.8.

a21. Бредихин Д.А. О многообразии, порожденном классом ре-дуктов алгебр отношений Тарского // Тезисы сообщений II Сибирского конгресса по прикладной и индустриальной математике. - Новосибирск, 1996. - С.187.

а22. Bredikhin D.A. On classes of relation algebras with primitive-

positive operations. / / Abstracts of Colloquim on Universal Algebras and Lattice Theory. - Szeged, 1996. - P.63.

a23. Bredikhin D.A. On clones generated by primitive-positive operations of Tar ski's relation algebras. / / Summaries of talks, 8th International Conferences on Automata and Formal Languages. -Salgotarjan, 1966. - P.27.

a24. Bredikhin D.A. On semilattice-ordered semigroups of binary relations pointed by universal relations // Abstracts of Conf. "Semigroups and their Applications". - Prague, 1996.- P.8-9.