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


Министерство науки и высшего образования Российской Федерации НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ



А. В. КРАВЧЕНКО, М. В. ШВИДЕФСКИ


УНИВЕРСАЛЬНАЯ АЛГЕБРА И ТЕОРИЯ КВАЗИМНОГООБРАЗИЙ



Утверждено Редакционно-издательским советом университета в качестве учебного пособия







НОВОСИБИРСК
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. Квазимногообразия и невложимость............. 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 U R — множество сигнатурных символов, т. е. имен операций и отношений на A. Считаем, что F П R = 0. С каждым элементом f G F свяжем натуральное число (возможно, ноль), а с каждым элементом r G R — положительное целое число. Такое число называется арностью (или местностью) символа и соответствующей операции или отношения. Запись sⁿ в дальнейшем будет означать, что s является n-местным сигнатурным символом.
       Для каждого f G F определим функцию fA : Aⁿ ^ A, а для каждого r G R — отношение rA С Aⁿ, где n — арность соответствующего символа. Множество A с определенной на нем структурой {fA : f G F} U {rA : r G R} называется алгебраической системой и обозначается A ил и (A; а).


7

        Заметим, что мы рассматриваем только всюду определенные функции.
        Определения классических алгебраических систем оказываются частными случаями определения 1.1. Например,
        группоид — это система G = (G; -²) с одной бинарной операцией;
        полугруппа — это группоид с ассоциативной операцией •, т. е. такой, что x • (у • z) = (x • у) • z для всех x, y, z G G;
        моноид — это система M = (M; -²,1) такая, что (M; •) — полугруппа, a 1 — константа для нейтрального элемента, т. е. x • 1 = 1 • x = x для любого x G M;
        группа — это система G = (G; +², — 1,0) с ассоциативной бинарной операцией +, константой 0 для нейтрального элемента и унарной операцией — взятия обратного элемента, т. е. x + (—x) = (—x) + x = 0 для любого x G G;
        граф — это система G = (G; r²) с одним бинарным отношением (в зависимости от дополнительных требований к rG можно говорить об ориентированных или неориентированных графах, а также графах без петель);
        частично упорядоченное множество — это система A = (A; 6²) с рефлексивным, антисимметричным и транзитивным отношением 6, т. е. такая, что x 6 x, из x 6 у и у 6 x следует, что x = у, а из x 6 У и у 6 z следует, что x 6 z для всех x,y,z G A;
        решетка — это система L = (L; Л², V²) с двумя бинарными операциями, удовлетворяющая следующим условиям для всех x, у, z G L:
        x V (у V z) = (x V у) V z и x Л (у Л z) = (x Л у) Л z,
        x V у = у V x x x Л у = у Л x,
        x V x = x x x Л x = x,
        x V (x Л у) = x x x Л (x V у) = x
    (кроме того, решетку можно считать частично упорядоченным множеством (L; 6) таким, что для любых a, b G L существуют точная верхняя и точная нижняя грани множества {a, b}).

8

        Определение 1.2. Если а = R, т. е. F = 0, то алгебраические системы сигнатуры а называются предикатными. Если а = F, т. е. R = 0, то алгебраические системы сигнатуры а называются алгебрами.

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

        Определение 1.3. Пусть A = (A; а) — алгебраическая система и пусть а' D а. Естественно считать, что L С L', R С R', арности общих символов s в а а а' совпадают, равно как и интерпретации sA на любом множестве A. Ес ли A = (A; а) и A' = (A; а'), то говорим, что система A' — обогащение системы A, а система A — редукт системы A'.

        Среди приведенных выше примеров, например, полугруппы являются редуктами соответствующих групп, а моноиды — обогащениями полугрупп.

2. Изоморфизмы, вложения и подсистемы

        В универсальной алгебре системы изучаются «с точностью до изоморфизма», а классы считаются «абстрактными», т. е. замкнутыми относительно образования изоморфных копий систем. Неформально это означает, что системы, отличающиеся только природой элементов множества A, не различаются. Более формально, определим понятие изоморфных систем следующим образом.

        Определение 1.4. Пусть A и B — алгебраические системы сигнатуры а = F U R. Биективное отображение а : A ^ B называется изоморфизмом, если для любого n-местного функционального символа f € F и любого набора (ai,..., aₙ) элементов из A имеет место равенство

    (1)       a(f A(ai,..., an)) = fB (a(ai), ..., a(an))


9

    (в частности, имеем
    (2)        а(сА) = cB
    для любого константного символа с), а для любого n-местного предикатного символа r G R и любого набора (a1,..., aₙ) элементов из A имеет место эквивалентность
    (3)     (ai,. .., an) G r л z (a(ai),.. ., a(an)) G r .
        Если существует изоморфизм между системами A и B, то говорим, что эти системы Аоморфные и пишем A = B. Нетрудно видеть, что различие между изоморфными системами состоит только в природе элементов их носителей, а отображение а устанавливает взаимно однозначное соответствие между A и B, которое сохраняет структуру (операции и отношения).
        Несколько ослабим требования к а из определения 1.4. Оставим неизменными условия (1), (2) и (3), а вместо биективности отображения а будем требовать только равнозначность, т. е. чтобы выполнялось условие а(х) = а(у) для всех х,у G A таких, что х = у. Отображение а, удовлетворяющее этим ослабленным условиям, называется вложением системы A в систему B.
        Упражнение 1. Проверьте, что для любого вложения а множество а(А) является замкнутым в B в следующем смысле: для любого n-местного функционального символа f G F и любого набора (b1,..., bₙ) элементов из а(А) имеем f A(b1,..., bₙ) G а(А).
        Если а(х) = х для любого х G A, то говорим, что а осуществляет тождественное вложение A в B. В таком случае систему A называем подсистемой системы B и пишем A 6 B. Упражнение 1 показывает, что носитель подсистемы системы B — это замкнутое в B подмножество. Верно и обратное утверждение.
        Упражнение 2. Покажите, что любое замкнутое в B подмножество является носителем подсистемы системы B.
        Заметим, что в случае предикатных систем любое подмножество носителя системы A = (A; а) является замкнутым в A, так

ю

    как множество функциональных символов пустое (а лишь они упоминаются в определении замкнутого подмножества). Если F = 0, то могут существовать подмножества носителя системы, не являющиеся замкнутыми. Например, в моноиде натуральных чисел относительно сложения есть единственное одноэлементное замкнутое подмножество {0} и нет замкнутых двухэлементных подмножеств.
        Из определений изоморфизма, вложения и подсистемы, а также упражнений 1 и 2 непосредственно получаем следующее утверждение.

        Предложение 1.5. Имеют место следующие утверждения:
       (1) любой изоморфизм является вложением,
        (2)   если а : А ^ B — вложение, то а(А) — носитель подсистемы системы B, изоморфной системе A,
        (3)   АЛ6 A 6 B.mo тождественна отображение на А является вложением,
        (4)   подмножество А является замкнутым в B тогда и только тогда, когда оно является носителем некоторой подсистемы системы B.

        Определение 1.6. Если А — наименьшее замкнутое в B подмножество, расширяющее множество X, то пишем А = {XiB и говорим, что А — замыкание множества X (вВ),а подсистема системы B с носи телем А — подсист ема системы B, порожденная X.

        Предложение 1.7. Для любой алгебраической системы B и любого подмножества X С B справедливы следующие представления:
        (1)   множество {XiB совпадает с пересечением всех замкнутых в B подмножеств, расширяющих X,
        (2)   существует бесконечная возрастающая последовательность множеств, расширяющих X, така я, ито {X )B совпадает с объединением этой последовательности множеств.


11

        Доказательство. (1) Так как B — замкнутое множество, достаточно заметить, что пересечение любого непустого семейства замкнутых множеств замкнутое.
        (2)   Для каждого подмножества X С A положим
E(X) = X U {f A(xi, ...,xn) : f € an- и xi,..., xₙ € X}
    и определим E⁰(X) = X, Eⁿ⁺¹(X) = E(Eⁿ(X)). Получим возрастающую последовательность множеств
X С E(X) С E²(X) С E³(X) С ....
    Обозначим через ETO(X) объединение этой последовательности. По построению X С E '■ (X) и множество ETO(X) замкнутое. Для любого замкнутого множества Y такого, что X С Y, индукцией по n легко показать, что Eⁿ(X) С Y. Следовательно, ETO(X) — замыкание X в B.                                        □


3. Гомоморфизмы
        Продолжим ослаблять требования из определения 1.4.
        Определение 1.8. Пусть A и B — системы сигнатуры ст. Отображение а : A ^ B называется гомоморфизмом, если для любого n-местного функционального символа f € ст и набора (ai,..., aₙ) элементов из A имеет место равенство
    (4)       a(fA(ai,... ,an)) = fB (a(ai),... ,a(an)).
    (В частности, для любого константного символа c имеем a(cA) = cB.) Для систем с отношениями дополнительно потребуем сохранение этих отношений, т. е.
    (5)       (ai,.. ., an) € rA ^ (a(ai), .. ., a(an)) € rB
    для любого n-местного предикатного символа r € ст и набора (ai,..., aₙ) элементов из A.
        Гомоморфизмы групп, колец, полугрупп, решеток и т. д. суть частные случаи общего определения гомоморфизма для алгебр.

12