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

Новосибирский государственный университет

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

Кравченко Александр Владимирович

УДК 512.57

Универсальные хорновы классы графов и формальных языков

(01.01.06 — Математическая логика, алгебра и теория чисел)

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

Новосибирск — 1999

Оглавление

Введение 3

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Литература

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 и Р обозначают соответстве