Универсальная алгебра и теория квазимногообразий

Министерство науки и высшего образования Российской Федерации
НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
______________________________________________________________________
А. В. КРАВЧЕНКО, М. В. ШВИДЕФСКИ 
УНИВЕРСАЛЬНАЯ АЛГЕБРА 
И ТЕОРИЯ КВАЗИМНОГООБРАЗИЙ
Утверждено Редакционно-издательским советом 
университета в качестве учебного пособия
НОВОСИБИРСК
2020

УДК 512.57+512.565](075.8)
        К772
Рецензенты: 
д-р физ.-мат. наук А.Г. Пинус,
канд. физ.-мат. наук С.С. Оспичев 
Работа подготовлена на кафедре алгебры и математической логики 
НГТУ для студентов и аспирантов, интересующихся алгеброй 
и математической логикой
Кравченко А.В.
К772         Универсальная алгебра и теория квазимногообразий: учебное пособие / А.В. Кравченко, М.В. Швидефски. – Новосибирск: Изд-во НГТУ, 2020. – 80 с.
            ISBN 978-5-7782-4145-9
В пособии изложены основы универсальной алгебры и теории квазимногообразий, разделов математики, находящихся на стыке алгебры и
математической логики. От читателя требуется владение основами алгебры в рамках курса «Линейная алгебра», читаемого на I курсе всех факультетов НГТУ.
УДК 512.57+512.565](075.8)
ISBN 978-5-7782-4145-9                              ©  Кравченко А. В., Швидефски М. В., 2020
© Новосибирский государственный 
технический  университет, 2020

Оглавление
Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
Глава 1.
Основные конструкции универсальной алгебры. . .
7
1.
Алгебраические системы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
2.
Изоморфизмы, вложения и подсистемы. . . . . . . . . . . . . . .
9
3.
Гомоморфизмы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
4.
Конгруэнции алгебраических систем. . . . . . . . . . . . . . . . . . 14
5.
Прямые произведения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
6.
Подпрямые произведения . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
22
7.
Определяющие соотношения . . . . . . . . . . . . . . . . . . . . . . . . . .
24
8.
Прямые и надпрямые пределы . . . . . . . . . . . . . . . . . . . . . . . . 28
8.1.
Прямые и надпрямые спектры . . . . . . . . . . . . . . . . . . . . . .
28
8.2.
Категорное определение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
8.3.
Алгебраическое определение . . . . . . . . . . . . . . . . . . . . . . . .
30
8.4.
Надпрямые пределы и решетки конгруэнций . . . . . . .
32
8.5.
Локальное строение надпрямого предела. . . . . . . . . . . . 35
9.
Полугруппа операторов и порядок на ней. . . . . . . . . . . . . 37
Глава 2.
Универсальные хорновы класы. . . . . . . . . . . . . . . . . . . . 39
1.
Аксиоматизируемые классы. . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.
Характеризация многообразий . . . . . . . . . . . . . . . . . . . . . . . . 40
2.1.
HSP-теорема Биргкофа. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
2.2.
Лемма Йонссона . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.
Характеризация квазимногообразий . . . . . . . . . . . . . . . . . .
42
3.1.
Квазикомпактные классы . . . . . . . . . . . . . . . . . . . . . . . . . . .
42
3.2.
Характеристические формулы. . . . . . . . . . . . . . . . . . . . . . . 44
3

3.3.
Квазимногообразия и невложимость . . . . . . . . . . . . . . . .
50
4.
Антимногообразия алгебраических систем . . . . . . . . . . . . 53
Глава 3.
Решетки квазимногообразий . . . . . . . . . . . . . . . . . . . . . .
57
1.
Алгебраичность, коалгебраичность и покрытия. . . . . . . 57
2.
Полудистрибутивность и дистрибутивность. . . . . . . . . . . 63
3.
Мощности решеток квазимногообразий . . . . . . . . . . . . . . . 65
4.
Конечные решетки квазимногообразий . . . . . . . . . . . . . . .
68
5.
Сложность решеток квазимногообразий . . . . . . . . . . . . . .
72
5.1.
Q-универсальность . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
73
5.2.
Независимая базируемость . . . . . . . . . . . . . . . . . . . . . . . . . .
76
5.3.
Алгоритмическая сложность . . . . . . . . . . . . . . . . . . . . . . . .
77
5.4.
Категорная универсальность . . . . . . . . . . . . . . . . . . . . . . . .
78
Литература. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
4

Введение
В учебном пособии приводятся начальные сведения по теории квазимногообразий алгебраических систем (без ограничений
на сигнатуру) и необходимые для понимания материала базовые
сведения из универсальной алгебры.
Для чтения настоящего пособия от читателя требуется некоторая подготовка. Мы считаем, что он, как минимум, знаком
с университетским курсом математической логики (например,
с учебными пособиями Новосибирского госуниверситета [1, 2]
или Новосибирского государственного технического университета [6]). Часть материала первой главы (в случае алгебр) изложена в учебном пособии [4]. Еще одним источником информации
по универсальной алгебре в случае функциональной сигнатуры
может служить учебное пособие [5].
В частности, мы предполагаем известными определения формулы логики первого порядка и ее истинности, классических алгебр (включая решетки), таких свойств решеток, как полнота,
алгебраичность, модулярность и дистрибутивность.
При изложении мы используем алгебраический подход к исследованию квазимногообразий и следуем в этом монографии [3].
Не определенные в пособии понятия или являются хорошо
известными, или могут быть найдены в приведенных выше источниках.
Пособие разбито на три главы. В каждой из них, кроме теоретического материала, приводится ряд задач и упражнений для
5

самостоятельной работы, выполнение которых позволит лучше
познакомиться с излашаемым материалом.
В первой главе приводятся основные сведения из универсальной алгебры, касающиеся таких конструкций, как гомоморфизмы, конгруэнции, произведения и пределы, вводятся операторы на классах систем. Частично материал этой главы изложен
в [4] для алгебр.
Во второй главе рассматриваются вопросы о характеризации
универсальных хорновых классов: многообразий, квазимногообразий и антимногообразий.
Наконец, в третьей главе основным объектом исследования
становятся квазимногообразий и решетки квазимногобразий. В
заключительном параграфе этой главы приводятся недавние результаты о сложности решеток квазимногообразий, что позволяет читателю познакомиться с современным состоянием исследований в этой области.
6

Глава 1
Основные конструкции универсальной
алгебры
1. Алгебраические системы
Основным объектом изучения будут алгебраические системы, т. е. непустые множества с определенной на них структурой.
Под последней будут пониматься операции над элементами и отношения между элементами этого множества.
Чтобы отличать множество от соответствующей алгебраической системы, будем обозначать множества курсивными буквами, а системы  каллиграфическими.
Определение 1.1. Пусть A  непустое множество. Назовем
его носителем системы A.
Пусть σ = F ∪R  множество сигнатурных символов, т. е.
имен операций и отношений на A. Считаем, что F ∩R = ∅. С
каждым элементом f ∈F свяжем натуральное число (возможно,
ноль), а с каждым элементом r ∈R  положительное целое число. Такое число называется арностью (или местностью) символа и соответствующей операции или отношения. Запись sn в
дальнейшем будет означать, что s является n-местным сигнатурным символом.
Для каждого f ∈F определим функцию f A : An →A, а
для каждого r ∈R  отношение rA ⊆An, где n  арность соответствующего символа. Множество A с определенной на нем
структурой {f A : f ∈F} ∪{rA : r ∈R} называется алгебраической системой и обозначается A или (A; σ).
7

Заметим, что мы рассматриваем только всюду определенные
функции.
Определения классических алгебраических систем оказываются частными случаями определения 1.1. Например,
группоид  это система G = (G; ·2) с одной бинарной операцией;
полугруппа  это группоид с ассоциативной операцией ·, т. е.
такой, что x · (y · z) = (x · y) · z для всех x, y, z ∈G;
моноид  это система M = (M; ·2, 1) такая, что (M; ·) 
полугруппа, а 1  константа для нейтрального элемента, т. е.
x · 1 = 1 · x = x для любого x ∈M;
группа  это система G = (G; +2, −1, 0) с ассоциативной бинарной операцией +, константой 0 для нейтрального элемента и
унарной операцией −взятия обратного элемента, т. е. x+(−x) =
(−x) + x = 0 для любого x ∈G;
граф  это система G = (G; r2) с одним бинарным отношением (в зависимости от дополнительных требований к rG можно
говорить об ориентированных или неориентированных графах,
а также графах без петель);
частично упорядоченное множество  это система A =
(A; ⩽2) с рефлексивным, антисимметричным и транзитивным
отношением ⩽, т. е. такая, что x ⩽x, из x ⩽y и y ⩽x следует, что x = y, а из x ⩽y и y ⩽z следует, что x ⩽z для всех
x, y, z ∈A;
решетка  это система L = (L; ∧2, ∨2) с двумя бинарными
операциями, удовлетворяющая следующим условиям для всех
x, y, z ∈L:
x ∨(y ∨z) = (x ∨y) ∨z и x ∧(y ∧z) = (x ∧y) ∧z,
x ∨y = y ∨x и x ∧y = y ∧x,
x ∨x = x и x ∧x = x,
x ∨(x ∧y) = x и x ∧(x ∨y) = x
(кроме того, решетку можно считать частично упорядоченным
множеством (L; ⩽) таким, что для любых a, b ∈L существуют
точная верхняя и точная нижняя грани множества {a, b}).
8