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

• Кравченко, Александр Владимирович
• кандидат физико-математических наук
• 1999

Оглавление диссертации кандидат физико-математических наук Кравченко, Александр Владимирович

Оглавление

Введение

1. Цветосемейства предикатных систем

1. Определения и предварительные результаты

2. Универсальные хорновы классы

3. Ядра, цветосемейства и нормальные формы

4. Конечно порожденные цветосемейства

5. Цветосемейства формальных языков

2. Антимногообразия и цветосемейства графов

6. Гомоморфизмы и конгруэнции графов

7. Цветосемейства графов

8. Решетка цветосемейств графов

9. Решетка антимногообразий графов

10. Решетка квазимногообразий графов

11. Квазитождества и антитождества цветосемейств

3. Сложность решеток квазимногообразий графов и эндографов

12. Квазимногообразия ориентированных графов

13. Квазимногообразия эндографов

Литература

82

Введение диссертации (часть автореферата) на тему «Универсальные хорновы классы графов и формальных языков»

Введение

Универсальная хорнова логика является одним из важнейших фрагментов логики первого порядка. Это объясняется тем, что она достаточно проста, но при этом выразительна. Язык универсальной хорновой логики позволяет формулировать многие задачи, возникающие в математике. Это, например, проблемы вложения в алгебре, допустимые правила вывода в логике, аффинные пространства и отношение "между" в геометрии, алгебраические пространства замыкания в комбинаторике, цветосемейства графов и семейства интерпретируемости в формальных языках (см. [1]).

Основы теории универсальных хорновых классов были заложены А. И. Мальцевым в 50-60-х годах (см. [2]). В настоящее время эта теория является интенсивно развивающимся направлением и имеет приложения в теории моделей и универсальной алгебре, неклассической и алгебраической логике, теории дедуктивных систем, логическом программировании и теории баз данных. Универсальная хорнова логика взята за основу для создания новых языков программирования, для обработки баз данных, и становится одним из основных инструментов представления знания (см. Ковальски [3]).

Основным объектом исследования эквациональной логики (теории многообразий) являются алгебры, т. е. системы функциональной сигнатуры. Эта теория представлена в монографиях Грет-цера [4], Бурриса, и Санкаппанавара [5], Маккензи, Макналти и Тейлора [6] и Д. М. Смирнова [7]. В отличие от эквациональной логики, наибольший интерес для исследования в универсальной хорновой логике представляют предикатные системы. По мнению

Биркгофа [8] сейчас актуально изучать именно предикатные системы, и эта актуальность сохранится еще несколько десятилетий. Действительно, в различных областях математики естественно возникают классы систем, сигнатура которых состоит только из предикатных символов. Примерами таких классов могут служить, например, графы, формальные языки [9], пространства замыкания [10].

Алгебраический подход в универсальной хорновой логике был предложен в работах В. А. Горбунова и представлен в его монографии [1]. С помощью этого подхода удалось решить ряд известных проблем, стоявших в этой области, а также по-новому посмотреть на многие другие другие задачи.

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

Изучение гомоморфизмов графов было начато Сабидусси в конце 50-х-начале 60-х годов. Полученные им тогда результаты были опубликованы в [11]. Позднее, он же начал изучение еще одной алгебраической конструкции, подпрямых произведений, в случае графов и доказал аналог теоремы о подпрямом разложении [12]. В б0-е-70-е годы изучение гомоморфизмов графов и более общих предикатных систем было продолжено так называемой пражской школой теории категорий во главе с Хедрлином и Пултром. Полученные в это время результаты представлены в [13]. В конце 70-х-начале 80-х годов большое внимание уделялось вопросам иерархии классов интерпретаций формальных языков и цветосемейств

графов. Эти вопросы были подняты в работах Нешетрила и Пул-тра [14], Маурера, Саломаа и Вуда [15, 16], а также Маурера, Судборо и Велзля [17]. Основным результатом в этом направлении стало доказательство теоремы плотности для цветосемейств графов (см. Саломаа [18] и Велзль [19]).

С другой стороны в работах Уилера [20] и И. Е. Бененсона [21] было начато исследование теоретико-модельных свойств классов п-раскрашиваемых графов. Они независимо доказали, что такие классы графов (дополненные тривиальными графами) являются квазимногообразиями, каждое из которых порождается одним конечным графом. Таким образом, оказалось возможным переформулировать проблемы об тг-раскрашиваемых графах в терминах универсальной хорновой логики. Например, проблема четырех красок формулируется в терминах существования специального базиса квазитождеств для квазимногообразия 4-раскрашиваемых графов.

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

Основные результаты работы следующие:

1. Определено понятие антимногообразия и доказан аналог НБР-теоремы Биркгофа для антимногообразий.

2. Установлено, что главное цветосемейство [Ь —Л], где Л — конечная система предикатной сигнатуры, является конечно порожденным универсальным хорновым классом тогда и только тогда, когда множество ребер системы А конечно, и показано, что это утверждение не обобщается на системы, сигнатура которых содержит функциональные символы.

3. Описаны максимальные подпрямо неразложимые системы в цветосемействах графов.

4. Определено понятие направленного базиса антитождеств (квазитождеств) и показана связь этого понятия с коразложения-ми в решетках относительных антимногообразий и известной проблемой в теории графов.

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

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

Результаты диссертации были представлены на международной конференции по математической логике, посвященной 85-летию со дня рождения А. И. Мальцева (Новосибирск, 1994), международной конференции "50. Arbeitstagung Allgemeine Algebra" (Darmstadt, 1995), Второй международной летней школе "Пограничные вопросы теории моделей и универсальной алгебры" (Эр-лагол, 1997), международной конференции "55. Arbeitstagung Allgemeine Algebra" (Darmstadt, 1997), международной конференции "Мальцевские чтения" (Новосибирск, 1997), на семинарах "Теория решеток", "Универсальная хорнова логика" и "Алгебра и логика" Новосибирского государственного университета, а также на семинаре Дармштадтского технического университета (1997).

Все основные результаты диссертации опубликованы в [66, 67, 68, 69, 70, 71]. Результаты из совместных с В. А. Горбуновым работ [70, 71], включенные в диссертацию, принадлежат автору. Часть основных результатов диссертации (теоремы 2.2, 4.2, 7.3,

11.8) включены В. А. Горбуновым в его монографию "Алгебраическая теория квазимногообразий" [1].

Диссертация состоит из введения, трех глав, разбитых на 13 параграфов, и списка литературы. Нумерация параграфов сквозная. Утверждения нумеруются двумя цифрами; первая — номер параграфа, вторая — номер утверждения в нем. Выносные формулы нумеруются аналогично. Список литературы содержит 71 наименование. Объем диссертации составляет 86 страниц.

Перейдем к изложению содержания диссертации.

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

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

определение. Антитождествами называются универсальные хорновы предложения вида (\/x)(^Ri(x) V ... V ^Rm(x)), где Ri — атомные формулы. Класс систем К называется антимногообразием, если К = Mod Е для некоторого множества антитождеств Е. Подкласс К' класса К называется К-антимногообразием, если К' = К П Mod S.

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

ЛЕММА 2.1. Подкласс К' универсального хорнова класса К, К' ф К, является К.-антимногообразием тогда и только тогда, когда существует множество В конечно определенных систем в К такое, что К' = "[В —» К].

Первым основным результатом является следующее утверждение.

Теорема 2.2. Пусть К — универсальный хорнов класс и К' — подкласс в К. Следующие условия равносильны:

(1) К' — К.-антимногообразие]

(2) К' — универсальный хорнов класс и Н_1(К') ПК С К';

(3) К' = Н"18Р*(К') ПК.

Параграф 3 посвящен обсуждению понятия ядра конечной системы и связи этого понятия с конечно порожденными антимногообразиями (цветосемействами). Напомним, что ядром системы называется ее минимальный (по включению) ретракт. Известно [22], что ядро системы во многом отвечает за гомоморфизмы всей системы. Мы показываем, что любое антимногообразие определяется множеством ядер своих систем, что позволяет рассматривать это множество как нормальную форму.

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

ТЕОРЕМА 4.2. Пусть Л — конечная предикатная система сигнатуры Л. Цветосемейство К = [К —> Л] является конечно порожденным универсальным хорновым классом, если и только если множество ребер системы А конечно.

Это утверждение является вторым основным результатом.

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

Наконец, в параграфе 5 полученные результаты применяются к цветосемействам формальных языков. Это, в частности, позволяет дать простое доказательство результата Маурера — Саломаа — Вуда о компактности.

Глава 2 посвящена применению развитой в главе 1 теории антимногообразий и цветосемейств к неориентированным графам без петель. Параграф 6 содержит необходимые сведения о гомоморфизмах и конгруэнциях (конгруэнц-раскрасках) графов. Показано на примере построение решетки (относительных) конгруэнц-раскрасок графа. Также приведены теоремы из теории графов, которые будут существенно использоваться в дальнейшем. В параграфе 7 доказан аналог теоремы 4.2 для цветосемейств графов. При доказательстве конечной порожденности цветосемейств как универсальных хорновых классов в явном виде приводится конструкция максимальных подпрямо неразложимых графов (теорема 7.3). Эта теорема является третьим основным результатом диссертации.

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

Параграф 8 посвящен исследованию свойств решетки Ь0(С) цветосемейств графов. В нем доказывается, что эта решетка является дистрибутивной и плотной, а также описываются неразложимые элементы и доказывается, что вполне неразложимых и вполне конеразложимых элементов в этой решетке нет (теорема 8.1).

В параграфе 9 рассматривается решетка Ь(С) антимногообразий графов и ее связь с решеткой цветосемейств. Оказывается, что решетка Ь(в) изоморфна решетке идеалов решетки цветосемейств, а также решетке порядковых идеалов частично упорядоченного множества ядер графов (теорема 9.2). Отсюда, в частности, следует, что решетка антимногообразий графов является решеткой с относительными псевдодополнениями (следствие 9.3).

Далее мы исследуем интервалы решетки Цв). Следующее утверждение показывает, что строение интервалов (а следовательно, и всей решетки ЦС)) достаточно сложное.

ТЕОРЕМА 9.4. Каждый интервал [К1,К2] решетки Ь(С) имеет мощность 2х, где А — конечный или счетный кардинал. Более того, для любого А ^ и> существует интервал решетки мощность

которого равна 2х. Интервал [К^Кг] является булевой решеткой тогда и только тогда, когда любое ядро из К 2 \ Кг максимально в Соге(К2).

В параграфе 10 мы применяем теорему 9.4 к исследованию мощностей идеалов решетки квазимногообразий графов. В частности, мы доказываем, что для любого квазимногообразия графов К решетка квазимногообразий ЬЧ(К) либо конечна, либо имеет мощность континуума (теорема 10.2). Это утверждение дает ответ на вопрос Кайседо о числе квазимногообразий п-раскрашиваемых графов.

В параграфе 11 мы переходим к рассмотрению базисов квазитождеств и антитождеств для цветосемейств. По теореме Неше-трила — Пултра (см. [14], а также [21]), никакой недвудольный конечный граф не имеет конечного базиса квазитождеств в классе всех графов. Обобщением этого утверждения является теорема 11.2.

теорема 11.2. Пусть О и Н — конечные недвудольные графы и пусть С — ядро. Если Н является О-раскрашиваемым графом, все подграфы которого не изоморфны (3, то квазимногообразие С1(Н) не имеет конечного базиса квазитождеств в [в —> О]+ . Более того, квазимногообразия С^(6?) и С£(С(и)), где и Е У(0), также не имеют конечного базиса квазитождеств в [С —>■ С]+.

Естественно возникает вопрос о существовании независимых базисов квазитождеств для цветосемейств. Теоремы 11.3-11.5 показывают, что никакое нетривиальное цветосемейство графов не

имеет независимого базиса антитождеств, квазимногообразие двудольных графов не имеет независимого и ¿¿-независимого базиса квазитождеств.

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

Определение. Пусть К — собственный универсальный хор-нов класс. Будем говорить, что множество антитождеств (квазитождеств) Е = {Фг- : г £ 1} направленно в К, если для любых i,j G I существует к £ / такое, что Ф4- и являются следствиями Ф^г в классе К. Если Е — направленное в К множество антитождеств (квазитождеств) и К' = К П Mod Е, то говорим, что Е — направленный базис антитождеств (квазитождеств) для К' в К.

Двойственность этого понятия понятию независимого базиса заключается в том, что если антимногообразие N С К имеет направленный базис антитождеств Е и независимый базис антитождеств Е' в классе К, то |Е'| = 1. Для базисов квазимногообразий аналогичное утверждение не имеет места (см. предложение 11.7).

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

ТЕОРЕМА 11.8. Для любого собственного универсального хор-нова класса К и любого К.-антимногообразия N следующие условия эквивалентны:

(1) N имеет направленный базис антитождеств в К;

(2) N — конеразложимый элемент решетки К.-антимногообра-зий L(K);

(3) Л х Ъ е К \ N для любых систем Л, Ъ е К \ N.

В главе 3 мы рассматриваем два обобщения неориентированных графов: ориентированные графы и неориентированные эндо-графы. Из результатов параграфов 9 и 10 следует, что решетка квазимногообразий графов является достаточно сложно устроенной. Формализацией понятия сложности для решеток квазимногообразий служит понятие О-универсальности, введенное М. Сапи-ром [23]: квазимногообразие К систем конечной сигнатуры называется ^-универсальным, если для любого квазимногообразия К' конечной сигнатуры решетка квазимногообразий ЬЧ(К') является гомоморфным образом некоторой подрешетки в ЬЧ(К).

В параграфах 12 и 13 доказывается пятый основной результат диссертации. Пусть N и Р обозначают соответственно множества натуральных и простых чисел, и пусть а — конечное подмножество в Р. Через 1Ча обозначим квазимногообразие антирефлексивных графов, определенное квазитождествами

(Ухуг)(11(х,у)&;Н(х,г) ->• у = г), (Ухуг)(Я(у,х)&сЯ(г,х) ->• у = г), а также квазитождествами

(\/х1...хп)[ & К{х1,Х1+1)кК{хп,хг) ^ хх = х-Л, п е Л^,

где ЛГа = N \ {к Пч60 V •• к > 1} и {0,1}.

ТЕОРЕМА 12.1. Для любого конечного подмножества а С Р квазимногообразие ГЧа является 0,-универсальным.

Эта теорема позволяет построить пример бесконечной убывающей цепи О-универсальных квазимногообразий, пересечение которой имеет счетную дистрибутивную решетку квазимногообразий (см. следствие 12.5). Наконец, в параграфе 13 мы доказываем □-универсальность квазимногообразия симметричных эндографов (теорема 13.2).

1. Цветосемейства предикатных систем

1. Определения и предварительные

результаты

1.1. Предикатные системы и гомоморфизмы. Под предикатной системой (или просто системой) понимается алгебраическая система Л, сигнатура которой состоит из множества % предикатных символов с определенной на нем функцией арности V : & —> {1,2,... }. В дальнейшем, если это не приводит к недоразумениям, мы будем использовать для интерпретации предиката Р в системе Л тот же символ Р. Считаем, что символ равенства и принадлежит 51 и интерпретируется на каждой системе как отношение равенства. Множество п-арных предикатных символов будем обозначать через Лп. Предикатная система называется конечной, если ее носитель конечен (вне зависимости от мощности Как обычно, системы будем обозначать рукописными буквами, а их носители — соответствующими курсивными.

Пусть Л — предикатная система и ах,... ,ап € А. Кортеж (ах,... ,ага) будем называть ребром системы А, соответствующим предикату Р € или Р-ребром, если А |= Р(ох,... ,ап). Множество всех Р-ребер обозначается через Ер(А). Множеством ребер системы Л называется множество Е(А) = иреЯ(-А)' ^-Ребро системы Л вида (а,... , а) называется Р-петлей в а. Тривиальной системой данной предикатной сигнатуры называется система, носитель которой состоит из одного элемента е, имеющая в е Р-петлю для каждого Р £

Гомоморфизмом из системы А в систему Ъ той же сигнатуры называется отображение / из А в В такое, что А |= P(ai,... ,ап) влечет Ъ |= P(f(a1),... ,f(an)) для всех аг,... , ап G А и Р € 31. Изоморфизмом между системами А и Ъ называется отображение / из А в В такое, что А |= Р(а\,... , ап) тогда и только тогда, когда Ъ |= P(/(ai),... ,/(а„)). Для любого класса К через 1(К) будем обозначать класс систем, изоморфных системам из К. В дальнейшем все рассматриваемые классы считаются абстрактными, т. е. замкнутыми относительно оператора I.

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

Предложение называется универсальным хорновым, если оно является конъюнкцией предложений следующего вида:

где Щ(х) — атомные формулы данной сигнатуры. Класс систем называется универсальным хорновым, если он является классом моделей для некоторого множества универсальных хорновых предложений. Предложения вида (1.1), (1.2), (1.3) называются, соответственно, тождествами, антитождествами и квазитождествами, а классы систем, определяемые такими предложениями, называются, соответственно, многообразиями, антимногообразиями и квазимногообразиями.

Пусть / — гомоморфизм из предикатной системы А в предикатную систему Ъ. Определим ядро кег/ = ((кег/)(Р) : Р £ Ж) гомоморфизма / следующим образом:

(1.1) (1.2) (1.3)

(Уж)(Д1(ж)&...&Дп(ж)),

(Vx)f Ri(x) V ... V ^Rm{x)),

(Vх)(Д!(ж)& . . . kRk{x) Rk+l{x)),

(ker tp)(P) = {(ai, ...,ап):Ъ\= Р(/(<ц),..., f(an))}.

1.2. Конгруэнции и подпрямые произведения. С понятиями гомоморфизма и ядра гомоморфизма в алгебре связано понятие конгруэнции. Согласно классической теореме о гомоморфизме задачи нахождения всех гомоморфных образов системы и всех ее конгруэнций равносильны; именно, конгруэнции на системы Л — это в точности ядра гомоморфизмов из Л на ее гомоморфные образы. В случае предикатных систем использование классического понятия конгруэнции (см. [2]) не приводит к такому соответствию. Поэтому мы будем пользоваться определением конгруэнции, введенным В. А. Горбуновым и В. И. Тумановым в [24].

определение 1.1. Пусть Л — предикатная система и пусть С (А) — Презг 2А"(Р), где 2А"(Р) — булева решетка подмножеств множества Элемент в — (в(Р) : Р £ 31) £ С (А) называется

конгруэнцией на Л, если выполняются следующие условия:

(1) является отношением эквивалентности на А;

(2) А \= Р{ах... ,ап) влечет (й!,... ,ап) £ в(Р) для любых ах,... ,ап е А и Р £ 31п;

(3) если аь . .. ,ап £ А, Ъг,... ,Ьп € А, Р е («1, ■■• ,ап) Е в(Р) и (а,-, Ьг-) £ для всех г, то (Ьх,... , Ьп) € в(Р).

Нетрудно убедиться, что при таком определении конгруэнции для любого гомоморфизма / предикатной системы Л ядро кег/ является конгруэнцией на Л и справедлива теорема о гомоморфизме, т. е. имеет место взаимно однозначное соответствие между конгруэнциями на Л и гомоморфизмами системы Л.

Пусть Л — предикатная система. Фактор-системой системы Л по конгруэнции в называется система А/9 с основным множеством А/в = {а/0(и) : а € А} такая, что Л |= Р(<ц/0(«),... ,ап/0(&)) тогда и только тогда, когда (а15... ,ап) € 0{Р).

Пусть Л — предикатная система, К — произвольный класс систем той же сигнатуры, что и Л. Пусть Сопк Л обозначает множество конгруэнций в на Л таких, что фактор-система Л/в принадлежит К. Такие конгруэнции называются К-конгруэнциями.

Согласно [24], если К — квазимногообразие, то для любой системы Л множество СопкЛ является алгебраической решеткой относительно порядка, индуцированного решеткой С {А). Наибольшим элементом 1л в СопкЛ является конгруэнция : Р £ Л),

а наименьшим элементом Од является конгруэнция в такая, что (ai,... , ап) € в{Р) тогда и только тогда, когда Л |= P(ai,... , ап).

С конгруэнциями и гомоморфизмами алгебраических систем связано понятие подпрямого разложения. Напомним, что система Л называется подпрямым произведением семейства систем {®¿) : i £ /}, той же сигнатуры, если существует вложение е : Л —у Ъ{ и для любого г £ / композиция pte : A —f 23¿, где p¡., i £ /, — проектирования, является гомоморфизмом на. Система называется подпрямо неразложимой в классе К, если для любого представления ее в виде подпрямого произведения семейства систем из К найдется i £ / такое, что композиция рге является изоморфизмом.

Следующий результат из [24] описывает связь между подпря-мыми разложениями системы Л в квазимногообразии К и К-кон-груэнциями на Л.

предложение 1.2. Пусть К — квазимногообразие, А £ К и {Oí : i £ 1} — множество 'К-конгруэнций на А. Если р)ieI9i = 0А, то А является подпрямым произведением семейства систем {А/вг : i £ /}. В частности, любая система из любого универсального хорнова класса К является подпрямым произведением семейства подпрямо неразложимых в К систем. Более того, система А подпрямо неразложима в К тогда и только тогда нуль решетки Сопк(Л) вполне конеразложим.

Связь между различными понятиями конгруэнции и подпрямого разложения в случае предикатных систем (в частности, графов) изучалась в [12, 14, 25, 26, 27, 28]. Так в [12] требовалось, чтобы все pie были сильными эпиморфизмами, и было дано описание подпрямо неразложимых (в классе неориентированных графов

без петель) графов и доказано, что любой граф представим в виде подпрямого произведения семейства подпрямо неразложимых графов. В [14, 25, 27, 28] рассматривались представления, при которых pie являются эпиморфизмами, а в [26] изучалась связь между подпрямой неразложимостью в смысле [12] и [27]. Также различные варианты подпрямой разложимости для предикатных систем изучались в [29].

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

определение 1.3. Пусть К — универсальный хорнов класс предикатных систем, X = {ж,- : г Е /} — множество переменных и R — множество формул вида Р(хi,... , жга), где Р Е !Лп, x¡ Е X. Система Л определяется в К порождающими X и определяющими соотношениями R, если существует отображение / : X —> А такое, что

(1) система Л порождается элементами {/(ж,) : i Е /};

(2) все формулы из R истинны в Л при подстановке жг- ь-» /(ж,-), i Е /;

(3) если в некоторой системе 23 Е К истинны все формулы из R при подстановке ж,- bt, то существует гомоморфизм из Л в Ъ, переводящий /(ж,-) в 6¿.

Если Л — система, заданная в К порождающими X и соотношениями R, то пишем Л = (X, R)k- Если К — класс всех систем данной сигнатуры или из контекста ясно, о каком классе К идет речь, то используем более краткое обозначение Л = (X, R).

Заметим, что в случае предикатной сигнатуры нет термов, отличных от переменных, т. е. все термы имеют вид ж,, где ж¿ — переменная. Это позволяет привести множества порождающих и определяющих соотношений к каноническому виду следующим образом.

Поскольку все термы являются переменными, получаем, что если А = (X, К) и / — соответствующее отображение из X в А, то / должно быть отображением на. Для каждого элемента а € А рассмотрим полный прообраз f~1(a), добавим к X переменную га, а для каждой переменной х^ £ /-1(а) добавим к К формулу

= га. Аналогично, если в Я есть формула ,ждля

некоторого Р € \ и некоторых х£ («Л:), 1 ^ А; < п, то добавим к Я, формулу Р(,г01,... , 2а„). Проведя всевозможные преобразования такого вида, удалим из получившейся совокупности формул те, которые содержат переменные из X. Согласно теоремам Тице и Дика (см. [2]) полученная совокупность переменных % — {га : а £ А} и определяющих соотношений Г задают в К ту же систему А, причем в качестве отображения f : Z —¥ А можно взять отображение га 1-4- а. Такой вид определяющих соотношений для предикатных систем будем называть каноническим и в дальнейшем считать, что системы заданными определяющими соотношениями в каноническом виде.

Теперь легко видеть, что предикатная система конечна тогда и только тогда, когда каноническое множество порождающих Z конечно, а система имеет конечное множество ребер тогда и только тогда, когда конечно каноническое множество соотношений Г. Системы с конечным числом порождающих и соотношений называются конечно определенными.

В дальнейшем при рассмотрении гомоморфизмов предикатных систем нам потребуются следующие две конструкции. Пусть А — конечно определенная система с каноническими порождающими X = {ж!,... ,хп} и соотношениями Я = ,Ят}. Через

Ф(Л) будем обозначать антитождество (\/ж!... 1V.. .УКт).

Обратно, если Ф — квазитождество (\/ж!... жп)(Й1& . . . —Ко)

или антитождество (У®!... жп)(_,/?1 V ... V ^-йш), то через А(Ф) обозначаем систему, определенную порождающими ... . хп и соотношениями Р1,... , Ит.

Следующее простое предложение показывает значение введенных конструкций.

Предложение 1.4. Имеют место следующие утверждения.

(1) Пусть А — конечно определенная система и Ъ — произвольная система. Гомоморфизм из А в Ъ существует, если и только если Ъ \= "^(Л). Обратно, антитождество Ф истинно в системе Ъ, если и только если не существует гомоморфизма из системы А(Ф) в систему Ъ.

(2) Антитождество Ф является следствием антитождества Ф тогда и только тогда, когда существует гомоморфизм из А(Ф) е А(Ф).

доказательство. Утверждение (1) очевидно, поэтому докажем только утверждение (2).

Пусть существует гомоморфизм из А(Ф) в А(Ф). Если А (= Ф для некоторой системы Л, то по (1) не существует гомоморфизма из А(Ф) в Л. Если при этом А (= ~'Ф, то по (1) существует гомоморфизм из А(Ф) в А. Но тогда имеем гомоморфизм А(Ф) —у А(Ф) —У Л, противоречие. Обратно, пусть Ф является следствием Ф. Очевидно, А(Ф) |= "Ф. Тогда имеем также А(Ф) \= ""Ф. В силу (1) это означает, что существует гомоморфизм из А(Ф) в А(Ф). □

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

ЛЕММА 1.5. Если А — конечно определенная система и существует гомоморфизм из А в ультрапроизведение по некоторому ультрафильтру и над I, то для некоторого г € / существует гомоморфизм из А в Ъ;.

доказательство. Рассмотрим предложение Ф(Л). Поскольку существование гомоморфизма из Л в некоторую систему Ъ равносильно ложности предложения Ф(Л) в 23, имеем Д|= ~"Ф(Л). Если предложение "'Ф(Л) ложно во всех системах !В;, г £

/, то по теореме Лося получаем ГЪе/^Зг-/С/ |= Ф(Л), противоречие. □

1.4. Операторы. В дальнейшем мы будем использовать следующие обозначения для операторов на классах (не обязательно предикатных) систем:

С^(К) — наименьшее квазимногообразие, содержащее К;

У(К) — наименьшее многообразие, содержащее К;

V- ' (К) — наименьшее антимногообразие, содержащее К;

Н(К) — класс всех гомоморфных образов систем из К;

Н-1(К) — класс всех гомоморфных прообразов систем из К;

8(К) — класс всех подсистем систем из К;

Р(К) — класс всех прямых произведений систем из К;

Ри(К) — класс всех ультрапроизведений систем из К;

Р*(К) — класс всех нетривиальных прямых произведений систем из К;

Р*(К) — класс всех нетривиальных ультрапроизведений систем из К.

Согласно теореме Биркгофа для любого класса К имеет место равенство У(К) = Н8Р(К). Аналогичное соотношение верно для оператора С^(К) = 8РРи(К). Известны также аналоги этих формул для представления наименьшего универсального хорнова класса, содержащего данный класс (см. [1]). Далее мы рассмотрим характеризацию антимногообразий в терминах введенных операторов.

2. Универсальные хорновы классы

В этом параграфе мы подробнее рассмотрим строение универсальных хорновых классов. Основные результаты параграфа верны в случае произвольной (не обязательно предикатной) сигнатуры.

Поскольку любое тождество эквивалентно конъюнкции квазитождеств (с тождественно истинными посылками), любое многообразие является квазимногообразием. Таким образом, достаточно ограничиться рассмотрением только антимногообразий и квазимногообразий. Заметим, что любое антитождество ложно на тривиальной системе, в то время как все квазитождества истинны на такой системе. Для произвольного универсального хорнова класса К возможны два случая:

(1) К содержит тривиальную систему £,

(2) К не содержит £ такие классы называются собственными.

Из характеризационной теоремы Мальцева [2] немедленно получаем следующий факт: в первом случае К является квазимногообразием, а во втором случае, добавляя к К тривиальные системы, мы получаем квазимногообразие, которое обозначаем К+.

Таким образом, изучение универсальных хорновых классов может быть сведено к изучению одних только квазимногообразий. Однако, как мы увидим далее, в некоторых случаях удобнее и естественнее рассматривать произвольные собственные универсальные хорновы классы и, в частности, антимногообразия. Такие классы естественно возникают в различных областях математики: это, например, графы без петель, алгебраические пространства замыкания, нетривиальные кольца с единицей, полугруппы без идем-потентов (см. [70]).

Хорошо известно, что эквациональная логика (или теория многообразий) в языке без функциональных символов является очень бедной. Например, для сигнатуры, состоящей из одного бинарного предикатного символа Р существуют следующие нетривиальные тождества: (Уж)Р(ж, х), (Уху)Р(х,у), (Ужу) ж ~ г/, а также их всевозможные конъюнкции. Поэтому эквациональная логика получила сильное развитие только в случае алгебр. Далее мы покажем, что в случае предикатных систем роль многообразий играют, в определенном смысле, антимногообразия.

Пусть К — произвольный класс. Подкласс К' класса К называется К-антимногообразием, если К' = К П Мос1(Е) для некоторого множества антитождеств Е.

Пусть В — некоторое множество систем и К — произвольный класс систем. Через ""[В —у К] будем обозначать класс всех систем А £ К таких, что для любой системы Ъ € В не существует гомоморфизма из Ъ в А. Приведем простое утверждение характеризующее К-антимногообразия в терминах несуществования гомоморфизмов.

ЛЕММА 2.1. Подкласс К' универсального хорнова класса К является К.-антимногообразием, К ф К', тогда и только тогда, когда существует множество В конечно определенных систем в К такое, что К' = "'[В —У К].

доказательство. Если Ъ — конечно определенная система в К, то по предложению 1.4 имеем —У К] = Мос1(Ф(!В)) П К. Поэтому для любого семейства В = {23,- : % £ 1} конечно определенных систем в К имеем

"[В К] = П,-еГ[®.' К] = Мо(1{Фф) : г е /} П К.

Обратно, пусть К' = К П Мо<1(£) для некоторого множества антитождеств Е и К' ф К. Для каждого Ф £ Е рассмотрим систему А(Ф). По предложению 1.4 получаем К' = ""[В —К], где В = {А(Ф) : Ф € Е}. □

Следующая теорема является аналогом НЭР-теоремы Биркго-фа для антимногообразий. Заметим, что она верна для случая произвольной (не обязательно предикатной) сигнатуры.

ТЕОРЕМА 2.2. Пусть К — универсальный хорное класс и К' — подкласс в К. Следующие условия равносильны:

(1) К' — К-антимногообразие-,

(2) К' — универсальный хорное класс и Н-1(К') ПК С К';

(3) К' = Н-^Р^К') ПК.

В частности, У^К') П К = Н^БР^К') П К.

Доказательство. Если К = К' то К' определяется в К пустым множеством антитождеств. Поэтому, не ограничивая общности, считаем, что К ^ К'. Импликация (1)=>(2) очевидна, поскольку оператор Н-1 сохраняет антитождества. Поскольку К' — универсальный хорнов класс, имеет место импликация (2)=Ф-(3).

Докажем теперь импликацию (3)=^(1). В силу леммы 2.1 достаточно показать, что существует множество В конечно определенных систем в К такое, что К' = "'[В —> К].

Очевидно, К' замкнут в К относительно оператора Б. Покажем, что К' замкнут в К относительно оператора Р*. Пусть (23,; : г € /} С К'. Тогда для каждого г 6 / существует гомоморфизм /г из 23,; на некоторую систему Л,; £ БР* (К7) П К. Для любого ультрафильтра Л над I семейство гомоморфизмов {/» : г £ /} индуцирует гомоморфизм из Р~[;е1Ъ{/17 на ДТаким образом, цг£1 Ъ^и € Н-^Р^К') П К, а по условию Н_18Р*(К) П К = К'.

Получили, что К' — универсально аксиоматизируемый подкласс универсально аксиоматизируемого класса К. Поскольку К' -ф К, множество Е всех конечно порожденных систем в К, не принадлежащих К', не пусто. Пусть Е = {23 г : г € /}. Рассмотрим произвольную систему 23£ Е. Пусть 23г определяется в К порождающими ,хп и соотношениями {К3 : ] £ «/}. Если

для каждого конечного подмножества ^ С 3 система Ъ?, определенная порождающими ,хп и соотношениями {Д^ : ] £ принадлежит классу К', то 23; £ К', так как 23; = НцхЗЗ;-7, см. [1]. Полученное противоречие показывает, что существует конечное подмножество ^ С ] такое, что конечно определенная система Ър не принадлежит К'. Рассмотрим множество В всех таких конечно определенных систем Ър, г £ /, и покажем, что для него выполняется равенство К' = "'[В —> К].

Пусть Л € К' и пусть для некоторого г £ / существует гомоморфизм из Ър в Л. Поскольку Л € К' и класс К' замкнут

в К относительно оператора Н~', получаем Ър Е К', противоречие. Таким образом, К' С ""[В К]. Предположим, что это включение строгое. Тогда найдется конечно порожденная система С Е ""[В —У К] \ К'. Очевидно, что С = 23г- для подходящего г £ /. Поскольку существует гомоморфизм из 23 f! в 23, получаем противоречие.

Теорема доказана □

Из теоремы 2.2 получаем аналог формулы Биркгофа для антимногообразий: V-1 = H_1SP*.

Относительные антимногообразия естественно возникают в теории графов (через обобщение понятия раскраски) и в теории формальных языков (через понятие интерпретации), см. [70]. Приведем еще один алгебраический пример.

пример 2.3. Напомним, что конечная система Л из класса К называется делителем нуля в К, если существуют конечные неизоморфные системы 23 и С в К такие, что Л х 23 = Л х С. Для данного простого числа р пусть Ср обозначает ориентированный граф с вершинами 1,... ,р, в котором пара (п, т) является ребром, если и только если n +1 = га (mod р). Для любых орграфов 23 и С пусть также 23UC обозначает их раздельное объединение. Согласно теореме Ловаса [30], конечный ориентированный граф Л является делителем нуля в классе D конечных ориентированных графов, если и только если Л имеет гомоморфизм в ориентированный граф вида CPl U ... U СРп, где pi; i ^ п, — простые числа. Таким образом, класс делителей нуля в D является D-антимногообразием, порожденным конечными раздельными объединениями ориентированных графов вида Ср. где р — простое число. Отсюда следует, что в классе конечных неориентированных графов делителями нуля являются в точности 2-раскрашиваемые графы. В [31] дана аналогичная характеризация делителей нуля для произвольных предикатных систем конечной сигнатуры.

3. Ядра, цветосемейства и нормальные

формы

В этом параграфе мы покажем, как в конечной системе выделить подсистему, которая отвечает за гомоморфизмы всей системы. Развитие этой теории для бесконечных систем приводится в [32].

Пусть Л — конечная система предикатной сигнатуры. Рассмотрим множество М всех подсистем 23 системы А таких, что существует гомоморфизм из А в 23. Поскольку для любой такой системы существуют гомоморфизмы из А в 23 и из 23 в А, заключаем, что для любой системы С той же сигнатуры существование гомоморфизма из С в Л равносильно существованию гомоморфизма из С в 23. Пусть т = тш®ем \В\. Рассмотрим подмножество М' С М, состоящее из систем мощности т. По построению, системы 23 G М' являются минимальными (по включению) с тем свойством, что Л имеет гомоморфизм в 23.

Лемма 3.1. Для любых систем 23, С g М' имеем 23 = С.

Доказательство. Пусть 23,6 е М'. Тогда существуют вложения е® : 23 —У Л и ее : С —У Л, а также гомоморфизмы /® : Л —у 23 и /е : Л —у С. Композиции этих отображений /ее® : 23 —У С и /®ее : С —23 являются гомоморфизмами. Поскольку мощности 23 и С являются минимальными среди мощностей подсистем в Л, в которые существует гомоморфизм из Л, гомоморфизмы /ее® и /вее являются гомоморфизмами на. Тогда отображение / = /ее®/® ее является гомоморфизмом из С на С. В силу конечности системы С существует натуральное число к такое, что гомоморфизм fk является тождественным автоморфизмом системы С. Тогда гомоморфизмы /®ее//:_1 и /ее® являются взаимно обратными гомоморфизмами на. Отсюда следует, что системы 23 и С изоморфны. □

Системы из М' будем называть ядрами системы Л. В силу леммы 3.1 можно говорить о ядре системы. Если ядро системы Л совпадает с самой Л, то будем говорить, что система Л является ядром. Если Ъ — ядро системы Л, то пишем Ъ = Соге(Л). Приведем некоторые свойства ядер конечных систем. Напомним, что если Л — система и Ъ — ее подсистема и существует гомоморфизм / из Л на Ъ такой, что ¡{х) = х для всех х £ В, то / называется ретракцией, а 23 — ретрактом А относительно /.

предложение 3.2. Пусть А и Ъ — конечные системы. Тогда

(1) если Ъ — ядро А, то система Ъ является ядром;

(2) Ъ является ядром А тогда и только тогда, когда Ъ — минимальный по включению ретракт Л;

(3) Л является ядром тогда и только тогда, когда любой эндоморфизм А является автоморфизмом;

(4) существует гомоморфизм из А в Ъ тогда и только тогда, когда существует гомоморфизм из ядра А в ядро 23.

Все утверждения легко проверяются (см., например, [22], где приведены доказательства некоторых из них в случае графов). Для бесконечных систем данные утверждения, вообще говоря, перестают быть верными. Например, бесконечные системы могут не иметь ядер или иметь несколько неизоморфных ядер (см. [22, 33]). В [34] исследован класс бесконечных ориентированных графов, для которых приведенные выше утверждения остаются верными.

Для данной конечной системы Л из универсального хорнова класса К пусть [К —» Л] обозначает класс систем 23 из К таких, что существует гомоморфизм из Б в Л. Такие классы называются главными К.-иветосемействами. Конечные объединения главных К-цветосемейств, т. е. классы вида [К —А] = [К -> Лх]и.. .и[К Ап], где А = {А\,... , Лп}, называются ~К-цветосемействами. Если К совпадает с классом всех систем данной сигнатуры или из

контекста ясно, о каком классе К идет речь, то мы говорим просто о цветосемействах.

В силу предложения 3.2 одно и то же К-цветосемейство может быть представлено в виде [К —> А] неоднозначно. Например, пусть существует гомоморфизм из конечной системы Ъ £ К в конечную систему Л £ К. Тогда цветосемейства [К —У Л] и [К —)■ Л, 23] совпадают. Также, если Ъ — ядро Л, то цветосемейства [К —> Л] и [К —23] совпадают. Предложение 3.2 позволяет определить для любого К-цветосемейства некоторую нормальную форму.

Определение 3.3. Пусть К — универсальный хорнов класс и К7 = [К —»■ А]. Если все системы из А являются ядрами и для любых Л, 23 £ А существование гомоморфизма из Л в 23 влечет равенство Л = 23, то множество А называется нормальной формой для К'.

Легко видеть, что для любого К-цветосемейства существует единственная нормальная форма. По определению, если А — нормальная форма для К-цветосемейства К', то имеет место следующее представление в терминах операторов на классах систем:

(3.1) К' = Н_18(А) ПК = БГ^Р*(А) П К.

Рассмотрим теперь аналог понятия нормальной формы для К-антимногообразий.

Пусть К' = У-1(К') П К и пусть Соге(К) обозначает множество всех типов изоморфизма конечно определенных ядер в К'. Следующее утверждение показывает, что это множество можно рассматривать как нормальную форму для К'.

ЛЕММА 3.4. Для любого К.-антимногообразия К' имеет место равенство К' = У_1(Соге(К')) П К.

Доказательство. Очевидно, К' Э У_1(Соге(К')) ПК. Рас- . смотрим произвольную систему Л £ К'. По теореме Мальцева [2], Л вложима в ультрапроизведение своих локальных подмоделей:

Л ^ Р[ге/ У1г//7. Пусть е — соответствующее вложение. Для каждого г £ / существует гомоморфизм /г- : Лг- —> Соге(Лг). По построению, все А', — конечно определенные системы, поэтому все системы Соге(Лг) также конечно определены. Семейство гомоморфизмов {/,■ : ъ £ 1} индуцирует гомоморфизм / : [|ге/Лг/(/ —у П^е/ Соге(Л{)/£/. Композиция /е является гомоморфизмом из Л в ультрапроизведение систем из Соге(К'), а в силу теоремы 2.2 имеем у-1(Соге(К')) П К = ЙГ^Р^Соге^')) ПК. □

4. Конечно порожденные

цветосемейства

Из теоремы 2.2 и представления (3.1), в частности, получаем следующее утверждение.

предложение 4.1. Любое К-цветосемейство является является универсальным хорновым классом. В частности, любое К-

цветосемейство замкнуто в К относительно операторов 8, Р* р*

и •

Рассмотрим вопрос о том, когда цветосемейство является конечно порожденным универсальным хорновым классом. Напомним, что универсальный хорнов класс К называется конечно порожденным, если К = 8Р(Л1;... ,ЛТО) для некоторых конечных систем г ^ т.

Пусть & — предикатная сигнатура. Рассмотрим случай, когда класс К совпадает с классом II всех систем сигнатуры Ясно, что достаточно ограничиться рассмотрением главных цветосемейств.

Если Л — конечная система, то цветосемейство [Л, —> Л] однозначно определяется ядром системы Л. Поэтому можем считать, что Л — ядро. Нетрудно также видеть, что ядро конечной системы конечно и что ядро системы с конечным множеством ребер также является системой с конечным множеством ребер.

теорема 4.2. Пусть Л — конечная предикатная система сигнатуры Л. Цветосемейство К = [И —У Л] является конечно порожденным универсальным хорновым классом, если и только если множество ребер системы Л конечно.

доказательство. Пусть Л имеет конечное число ребер и арности предикатов, к которым относятся эти ребра, ограничены некоторым натуральным числом п. Покажем, что любая система в К аппроксимируется конечным числом систем в К, мощности которых не превосходят |А| + п.

Пусть Ъ £ К и пусть / — гомоморфизм из Ъ в Л. Рассмотрим произвольный кортеж (Ъх,... ,Ьт) на В, не являющийся Р-ребром системы Ъ. Пусть /(6,-) = а;, г ^ т, и пусть (а^ ... ,ат) является Р-ребром системы Л. Рассмотрим два случая.

Пусть Р — символ равенства Тогда имеем ф Ъ2 £ В и ДЬ= /(Ь2) = а. Построим систему С следующим образом: основным множеством является С = Л и {а'}, где а' ^ А, а предикаты из

{«} определены по правилу С |= тогда и только тогда, когда С |= Я[Ь*)- где Ь* обозначает кортеж, полученный из Ъ заменой каждого а' на а. Определим отображение д : В —^ С следующим образом: ^(£>1) = а' и д(Ь) = f(b) для всех Ъ ф Ъ\. Из построения системы С следует, что д — гомоморфизм, причем, очевидно,

д(Ъ 1) ф д(Ъ2).

Пусть Р £ Рассмотрим множество {сх,... , ст} элемен-

тов, не принадлежащих А, где с; = сесли и только если ^ = Построим систему С следующим образом. Основным множеством является С = А II {с; : ! ^ ш}; кортеж (сх,... ,ст) не является Р-ребром системы С, а любой другой кортеж («1,... , ина С является ф-Ребром системы С, где ф £ & \ если и только

если Л |= ,и*к), где и* = и при и £ А и (сг-)* = а; для

всех г ^ т. Очевидно, что отображение, оставляющее элементы из А на месте и переводящее сг в аг-, г ^ т, является гомоморфизмом. Поэтому С € К. По построению |С| = |А| + т ^ |Л| + п.

Определим отображение д : В —» С, полагая д(Ь) = f(b) для всех Ъ {¿i,... ,Ьт} и = c¿ для г ^ т. Проверим, что

д — гомоморфизм. Пусть (ui,... ,Uk) является Q-ребром системы Ъ и пусть Vi — д{щ), i < к. По определению отображения д и системы С имеем С \= Q(v 1,... ,Vf.) тогда и только тогда, когда Л |= Q(f(ui),... ,f(uk))- Поскольку / — гомоморфизм, отсюда следует, что д также является гомоморфизмом. Остается заметить, что С |= ~^P(g(bi),... ,g(bm)) в силу определения отображения д.

По данному Р-ребру ар = (ai,... , ап), где Р 6 системы

А построим систему А(ар) следующим образом:

— А(ар) = A U {a'l5... где a- A, i ^ п, причем а- = а^ тогда и только тогда, когда ai = a,j\

— А(аР)^-Р(а[,... ,<)j

— если Q G & \ {f} или Ъ ф (a'l5... , aJJ, то А(ар) \= Q(b), если и только если А |= Q(b*), где Ь* получается из Ъ заменой каждого а\ на a¿.

Из определения легко следует, что А — ядро системы Л (ар), в частности, Л(ар) £ К.

Покажем, что для любого Р-ребра а, не являющегося петлей, система А(ар) подпрямо неразложима в К.

Пусть д — гомоморфизм из Л(ар) на некоторую систему Ъ € К. Через / обозначим гомоморфизм из !В в Л. Пусть |A(áp)| — |А| = s. Тогда найдутся различные пары элементов х\ ф г/i,... ,xs ф ys такие, что fg(xi) = fg(yi). Очевидно, s 2.

Случай 1. Пусть для некоторого i ^ s найдется j ^ п такое, что {xi,yi} = {cij, a'j}. Тогда (a'1;... ,а'п) G (ker fg){R).

Случай 2. Пусть для любого i ^ s множество {:/;„ уг} отлично от всех {aj,aj}, j ^ п. Если £ А, то через h обозначим тождественное вложение Л в Л(ар); если |{жг-, y¿} П {а'1;... , а'п}\ = 1 и = а^, то через h обозначим вложение Л в Л (ар), переводящее а;/ в a'j и оставляющее остальные элементы на месте. В первом

случае, (жг-,уг) £ (кега во втором (уг,а^ Е (кег т. е. в обоих случаях при эндоморфизме ¡дЬ, отождествляются некоторые два элемента из А. Поэтому fgh ^ Аи^Л). Так как Л — ядро, получаем противоречие с предложением 3.2. Пусть Х{ = а'-ж хц = а'ь где а^ ф щ. Если 5 ^ 3, то отображение Н из А в А(ар), переводящее а^ в а'-, щ в а\ ж оставляющее остальные элементы на месте, является вложением. Как и выше, /дк £ Аи1;(Л), противоречие. Наконец, пусть 5 = 2. Тогда жх = ух = а'2 (или наоборот). Так как {х1,у1} ф {ж2,Уг}, имеем |{жх,2/х} П {ж2,У2}| < 1. Если {жх,г/х} П {х2,у2} = 0, то х2,у2 Е А, что невозможно в силу доказанного выше. Если же |{жх,ух} П {ж2,г/2}| = 1, то, как и в случае |{ж,-, у,} П {ах,... , а'п}\ = 1, рассмотренном выше, получаем противоречие.

Таким образом, если а не является Р-петлей, то для любой ненулевой К-конгруэнции 0 на А(а,р) имеем (ох,... , а'п) Е 0(Р), причем кортеж (а[,... , а'п) не является ребром. По предложению 1.2 система Л(ар) подпрямо неразложима в К.

Пусть Л — конечная система, имеющая бесконечно много ребер. Если Л содержит бесконечно много ребер, не являющихся петлями, то по доказанному выше в К существует бесконечно много неизоморфных подпрямо неразложимых систем, и в этом случае универсальный хорнов класс К не является конечно порожденным, см. [1]. Пусть система Л имеет конечное число ребер, не являющихся петлями. В силу конечности А, существуют элемент а £ А ж бесконечное семейство предикатов {Pi : г Е 1} в 91 \ такие, что (а,... , а) является Р,:-ребром для всех г Е /. Пусть А% = Л(а7р,), где а' обозначает элемент а' в /1г, а сц — набор (а,... , а) в Аг. Покажем, что подпрямо К-разложимых систем среди Ai лишь конечное число.

Пусть fi — произвольный гомоморфизм из А{ на систему Ъг Е К, а д, — гомоморфизм из 23 г- в Л. Поскольку Л — ядро, ограничение гомоморфизма является автоморфизмом системы Л.

Допустим, что найдутся такие г ф- ] € /, что #¿/¿(0^) = = х.

Если х ф а, то по построению системы Лг для любого предикатного символа (¡) £ Л \ и любого набора элементов Ь, кроме случая, когда <3 = -Р; и Ъ = (ж,... , ж), из А \= 6) следует Л |= С^(Ь*), где 6* обозначает набор элементов, получающийся из 6 заменой всех вхождений а на ж. Аналогичное утверждение верно для системы А^, поэтому для любого предикатного символа С^ £ {~} и любого набора элементов Ъ жз А \= (¿(Ь) следует Л (= Q(b*). В частности, отображение, отождествляющее элементы а и ж и оставляющее остальные элементы на месте, является гомоморфизмом из Л на собственную подсистему с носителем А \ {а}, что невозможно. Таким образом, для всех г £ /, за исключением не более, чем \А\ - 1, имеем (а-,... ,а<) € (кег^/)(Р;), причем (а-,... , а-) не является Рг-ребром системы Лг-. Так как /,• — произвольный гомоморфизм, для всех г £ /, кроме конечного числа, система Лг-является подпрямо неразложимой в К. □

следствие 4.3. Пусть "Л — конечная предикатная сигнатура и К — антимногообразие систем сигнатуры Л. Тогда для любой конечной системы Л € К цветосемейство [К —У Л] резидуально конечно. Более точно, если \А\ = п и все предикаты из имеют арность меньше, чем т, то [К —Л] резидуально меньше, чем п + т.

Следующий пример показывает, что условие, что сигнатура предикатная, в теореме 4.2 существенно.

пример 4.4. Пусть сигнатура состоит из одного унарного функционального символа Р. Для к ^ 2 определим систему С к следующим образом: носителем является множество {ах,... ,а,к}, а операция Р определена по правилу = аг+1, г ^ п — 1, и

Р{ап) = ах. Рассмотрим класс К всех систем Л данной сигнатуры таких, что существует гомоморфизм из Л в 62- Легко видеть, что

для любого простого числа р > 2 система С2Р принадлежит этому классу. При этом для любого р > 2 решетка К+-конгруэнций системы С2р изоморфна трехэлементной цепи. По предложению 1.2 все такие системы подпрямо неразложимы в К+. Но это означает, что цветосемейство К, имеющее вид [В. —У Л], где Л — конечная система, не является конечно порожденным универсальным хор-новым классом.

Теперь построим примеры, показывающие, что достаточные условия на класс К, сформулированные в следствии 4.3, существенны, но не являются необходимыми.

пример 4.5. Модифицируем пример 4.4 следующим образом. Рассмотрим сигнатуру, состоящую из одного бинарного предикатного символа Р и класс К систем данной сигнатуры, определенный предложениями

(УХУР(х,Х), (4.1) (Ухуг){Р{х, у)кР{х, г)->у = z),

{Ухуг)(Р(у,х)кР(г,х) -»■ у = г).

Пусть С к, к ^ 2, обозначает систему из К с носителем {с\,... , с к}, где предикат Р определен следующим образом: С^ |= Р(сг-, сг-+1), 1 ^ г ^ к — 1, С& |= Р(сь,с1) и С/г |= для всех осталь-

ных пар (сг-,с^). По лемме 12.2, для любого простого числа р > 2 все гомоморфные образы системы С2р в классе К (с точностью до изоморфизма) — это сама система 62^, системы С2 и Ср, а также тривиальная система; причем классу [К —> б2]+ принадлежат только С2р и е2, а также тривиальная система. Таким образом, решетка К+-конгруэнций системы при любом простом р изоморфна трехэлементной цепи. По предложению 1.2, все системы С2р подпрямо неразложимы в [К —у С2]. Таким образом, это К-цветосемейство не является конечно порожденным универсальным хорновым классом.

ПРИМЕР 4.6. Покажем, что существует универсальный хорнов класс К, не являющийся антимногообразием, и система Л € К такие, что К-цветосемейство [К Л] является конечно порожденным универсальным хорновым классом.

Пусть опять сигнатура состоит из одного бинарного предикатного символа Р, а класс К определен предложениями (4.1) и системой квазитождеств

Список литературы диссертационного исследования кандидат физико-математических наук Кравченко, Александр Владимирович, 1999 год

Литература

[1] V. A. Gorbunov, Algebraic theory of quasivarieties, Plenum, New York-London-Moscow, 1998.

[2] А. И. Мальцев, Алгебраические системы, M., Наука, 1970.

[3] Р. Ковальски, Логика в решении проблем, М., Наука, 1990.

[4] G. Gratzer, Universal algebra, Springer Verlag, New York-Heidelberg-Berlin, 1979.

[5] S. BURRis and H. P. Sankappanavar, A course in universal algebra, Springer Verlag, New York-Heidelberg-Berlin, 1981.

[6] R. McKenzie, G. McNulty, and W. Taylor, Algebras, lattices, varieties, vol. I, Wadsworth & Brooks/Cole, Monterrey, 1987.

[7] Д. M. Смирнов, Многообразия алгебр, Наука, Новосибирск, 1992.

[8] G. BlRKHOFF, Lattices and their applications, Lattice Theory and its Applications (Darmstadt, 1991), Res. Exp. Math., vol. 23, Heldermann, Lemgo, 1995, pp. 7-25.

[9] А. Саломаа, Жемчужины теории формальных языков, М., Мир, 1986.

10] A. Pasxni, On the 1°-order translations of the theory of the geometric closure structures, Boll. Un. Mat. Ital. В (5) 18, no. 1, 217-230, 1981.

11] G. Sabidussi, Graph derivatives, Math. Z. 76 (1961), 385-401.

L2] G. Sabidussi, Subdirect representations of graphs, Colloq. Math. Soc. Janos Bolyai 10 (1973), 1199-1226.

13] A. Pultr and V. trnkova, Algebraic and topological representations of groups, semigroups and categories, North-Holland, Amsterdam, 1980.

14] J. Nesetr.IL and A. Pultr, On classes of relations and graphs determined by subobjects and factorobjects, Discrete Math. 22 (1978), no. 3, 287-300.

15] H. A. Maurer, A. Salomaa, and D. Wood, Colorings and interpretations: a connection between graphs and grammar forms, Discrete Appl. Math. 3 (1981), 119-135.

16] H. A. Maurer, A. Salomaa, and D. Wood, Finitary and infinitary interpretations of languagues, Math. Systems Theory 15 (1981/82), no. 3, 251-265.

17] H. A. Maurer, J. H. Sudborough, and E. Welzl, On the complexity of the general colouring problem, Inform. Control 51 (1981), 123-145.

18] A. Salomaa, On color-families of graphs, Ann. Acad. Sci. Fenn. Ser. A I Math. 6 (1981), no. 1, 135-148.

19] E. Welzl, Color-families are dense, Theoret. Comput. Sci. 17 (1982), 29-41.

20] W. H. Wheeler, The first order theory of N-colorable graphs, Trans. Amer. Math. Soc. 250 (1979), 286-310.

21] И. E. Бененсон, О структуре квазимногообразий моделей, Изв. ВУЗов, Матем. 1979, по. 12, 14-20.

22] P. Hell and J. Nesetril, The core of a graph, Discrete Math. 109 (1992), 117-126.

23] M. Sapir, The lattice of quasivarieties of semigroups, Algebra Universalis 21 (1985), 172-180.

24] В. А. Горбунов и В. И. Туманов, Строение решеток квазимногообразий, Труды ин-та матем. СО АН СССР 2 (1982), 12-44.

25] A. Pultr, Subdirect irreducibility and congruences, Category Theory (Gum-merbach, 1981), Lecture Notes Math., vol. 962, Springer, Berlin-New York, 1982, pp.256-266.

26] A. Pultr, On Sabidussi-Fawcett subdirect representation, Discrete Math. 109 (1992), 239-253.

27] A. Pultr and J. Vinarek, Productive classes and subdirect irreducibility, in particular for graphs, Discrete Math. 20 (1977), 159-177.

[28] J. Vinarek, On hereditary subdirectly irreducible graphs, Acta Univ. Carolin. — Math. Phys. 25 (1984), 3-10.

[29] J. Vinarek, On subdirect irreducibility and its variants, Czechosl. Math. J. 32 (1982), 116-128.

[30] L. Lovasz, On the cancellation law among finite relational structures, Period. Math. Hung. 1 (1971), no. 2, 145-156.

[31] R. R. Appleson and L. Lovasz, A characterization of cancellable k-ary strutures, Period. Math. Hung. 6 (1975), no. 1, 17-19.

[32] В. А. Горбунов и А. В. Кравченко, Универсальные хорновы классы и антимногообразия алгебраических систем, Алгебра и логика, в печати.

[33] В. Bauslaugh, Core-like properties of infinite graphs and structures, Discrete Math. 138 (1995), 101-112.

[34] B. L. Bauslaugh, Compactness and finite equivalence of infinite digraphs, Discrete Math. 167/168 (1997), 115-126.

[35] M. Bottcher and U. Knauer, Endomorphism spectra of graphs, Discrete Math. 109 (1992), 45-57.

[36] G. HaHN and C. tardiff, Graph homomorphisms: structure and symmetry, Graph symmetry: algebraic methods and applications, NATO ASI Ser., Ser. C, Math. Phys. Sci., vol. 497, Kluwer, Dordrecht, 1997, pp. 107-166.

[37] Ф. харари, Теория графов, M., Мир, 1973.

[38] Н. А. Куликов, Об определимости графов решетками конгруэнций, Алгебра и логика 24 (1985), no. 1, 13-25.

[39] P. Erdos, Graph theory and probability, Canad. J. Math. 11 (1959), 34-38.

[40] X. Zhu, Uniquely H-colorable graphs with large girth, J. Graph Theory 23 (1996), no. 1, 33-41.

[41] B. Bollobas and N. Sauer, Uniquely colorable graphs with large girth, Canad. J. Math. 28 (1976), 1340-1344.

[42] L. Lovasz, On chromatic number of finite set-systems, Acta Math. Acad. Sci. Hung. 19 (1968), 59-67.

[43] N. G. de Bruijn and P. Erdos, A color problem for infinite graphs and a problem in the theory of relations, Indag. Math. 13 (1951), 371-373.

[44] V. Glivenko, Sur quelques points de la logique de M. Brouwer, Bull. Acad. Sci. Belgique 15 (1929), 183-188.

[45] R. Balbes and P. R. Dwinger, Distributive lattices, Univ. Missouri Press, Columbia, Missouri, 1974.

[46] X. Caicedo, Finitely axiomatizable quasivarieties of graphs, Algebra Universalis 34 (1995), no. 2, 314-321.

[47] А. И. Будкин и 13. А. Горбунов, К теории квазимногообразий алгебраических систем, Алгебра и логика 14 (1975), по. 2, 123-142.

[48] В. А. Горбунов, Покрытия в решетках квазимногообразий и независимая аксиоматизируемость, Алгебра и логика 16 (1977), по. 5, 507-548.

[49] A. Pultr, On productive classes of graphs determined by prohibiting given subgraphs, Colloq. Math. Soc. Janos Bolyai 18 (1978), 805-820.

[50] G. Hajos, Uber eine konstruktion nicht n-farbbarar graphen, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 10 (1961), 116-117.

[51] С. В. Сизый, Квазимногообразия графов, Сиб. матем. ж. 35 (1994), по. 4, 879-892.

[52] S. Burr, P. Erdos, and L. Lovasz, On graphs of Ramsey type, ARS Combinatoria 1 (1976), 167-190.

[53] D. Duffus, B. Sands, and R. E. Woodrow, On the chromatic number of the product of graphs, J. Graph Theory 9 (1985), 487-495.

[54] M. El-Zahar and N. W. Sauer, The chromatic number of the product of two A-chromatic graphs is 4, Combinatorica 5 (1985), no. 2, 121-126.

[55] R. Haggkwist, P. Hell, D. J. Miller, and V. Neumann Lara, On multiplicative graphs and the product conjecture, Combinatorica 8 (1988), no. 1, 63-74.

[56] E. Welzl, Symmetric graphs and interpretations, J. Combin. Theory, Ser. В 37 (1984), 235-244.

[57] S. T. Hedetniemi, Homomorphisms of graphs and automata, Tech. Report 03105-44-T, Univ. Michigan, 1966.

[58] S. klavzar, Coloring graph products, Discrete Math. 155 (1996), 135-145.

[59] N. W. Sauer and X. Zhu, An approach to Hedetniemi's conjecture, J. Graph Theory 16 (1992), no. 5, 423-436.

[60] A. Hajnal, The chomatic number of the product of two alpha-one chromatic graphs can be countable, Combinatorica 5 (1985), 137-139.

[61] D. Duffus and N. Sauer, Lattices arising in categorial investigations of Hedetniemi's conjecture, Discrete Math. 152 (1996), 125-139.

[62] Ю. M. Важенин и С. В. Сизый, Квазимногообразия эндомоделей, Изв. ВУЗов, Матем. 1988, по. 2, 66-67.

[63] С. В. Сизый, Решетки квазимногообразий эндомоделей, Алгебраические системы и их многообразия, Свердловск, 1988, с. 122-129.

[64] С. В. Сизый, О минимальных квазимногообразиях эндографов, Мат. заметки 51 (1992), по. 6, 59-68.

[65] В. А. Горбунов, Строение решеток многообразий и решеток квазимногообразий: сходство и различие. И, Алгебра и логика 34 (1995), по. 4, 369-397.

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

[66] А. В. Кравченко, О квазимногообразиях G-раскрашиваемых графов, Ме-ждунар. конф. по мат. логике, посвященная 85-летию со дня рождения А. И. Мальцева, тезисы сообщений, Новосибирск, 1994, с. 56-57.

[67] А. В. Кравченко, О сложности решеток квазимногообразий ориентированных графов, Междунар. конф. по мат. логике, посвященная 85-летию со дня рождения А. И. Мальцева, тезисы сообщений, Новосибирск, 1994, с. 101-102.

[68] А. V. Kravchenko, On quasivarieties of G-colourable graphs, 50. Arbeitstagung Allgemeine Algebra. Abstracts, Technische Hochschule Darmstadt, Darmstadt, 1995, p. 10.

[69] А. В. Кравченко, О решеточной сложности квазимногообразий графов и эндографов, Алгебра и логика 36 (1997), по. 3, 273-281.

[70] V. A. Gorbunov and А. V. Kravchenko, Universal Horn logic, colour-families and formal languages, General Algebra and Applications in Discrete Mathematics (Proc. Conf. General Algebra Discrete Math.), Shaker Verlag, Aachen, 1997, pp.77-91.

[71] V. A. Gorbunov and A. V. Kravchenko, Universal Horn classes and colour-families of graphs, Preprint Np<T957, Technische Universität Darmstadt, Darmstadt, 1997.

/