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


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

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

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

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





НОВОСИБИРСК
2019

УДК 512.57+512.565](075.8) К772


Рецензенты:
академик РАН С.С. Гончаров, канд. физ.-мат. наук М.С. Шеремет



Работа подготовлена на кафедре алгебры и математической логики НГТУ для студентов и аспирантов, интересующихся алгеброй и математической логикой




      Кравченко А.В.
К772     Универсальная алгебра и теория решеток: учебное пособие /
      А.В. Кравченко, М.В. Швидефски. - Новосибирск: Изд-во НГТУ, 2019. - 75 с.



           ISBN 978-5-7782-4061-2



         В пособии изложены основы универсальной алгебры и теории решеток, разделов математики, находящихся на стыке алгебры и математической логики. От читателя требуется владение основами алгебры в рамках курса «Линейная алгебра», читаемого на I курсе всех факультетов НГТУ.








УДК 512.57+512.565](075.8)


ISBN 978-5-7782-4061-2

© Кравченко А. В., Швидефски М. В., 2019
                                            © Новосибирский государственный технический университет, 2019

                Оглавление




    Введение........................................... 5

    Глава 1. Начальные понятия теории решеток.......... 7
      1.  Определения решеток.......................... 7
      2.  Некоторые алгебраические понятия............. 9
      3.  Операторы замыкания......................... 13
      4.  Дистрибутивные и модулярные решетки......... 22

    Глава 2. Основные конструкции универсальной алгебры... 29
      1.  Гомоморфизмы алгебр......................... 29
      2.  Прямые произведения......................... 33
      3.  Подпрямые произведения...................... 35
      4.  Конгруэнции произвольных систем............. 36
      5.  Конгруэнц-свойства и условия Мальцева....... 40
      6.  Определяющие соотношения.................... 45
      7.  Прямые и надпрямые пределы.................. 49

    Глава 3. Аксиоматизируемые классы................. 59
      1.  Полугруппа операторов и порядок на ней...... 59
      2.  Характеризация многообразий................. 60
      3.  Квазикомпактные классы...................... 61
      4.  Характеризация квазимногообразий............ 63
      5.  Квазимногообразия и невложимость............ 68
      6.  Антимногообразия алгебраических систем...... 71

з

                Введение




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

    Определение 0.1. Пусть A — произвольное непустое множество. Назовем его носителем системы. Пусть L = FUR — множество сигнатурных символов, т. е. имен операций и отношений на A. С каждым элементом f G F свяжем натуральное число (возможно, ноль), а с каждым элементом r G R — положительное натуральное число. Такое число называется арностью (или местностью) символа и соответствующей операции или отношения. Для каждого f G F определим функцию fA : Aⁿ ^ A, а для каждого r G R — отношение rA С Aⁿ, где n — арность соответствующего символа.
    Множество A с определенной на нем структурой {fA : f G F }U{rA : r G R} называется алгебраической системой и обозначается A ил и (A; ст).

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

5

сигнатура предполагалась алгебраической, т. е. не содержащей символов отношений).
    Определения классических алгебраических систем оказываются частными случаями определения 0.1:
    группоиды — это системы с бинарной операцией •;
    полугруппы — это группоиды с ассоциативной операцией •;
    моноиды — это системы сигнатуры {-²,1} такие, что (A; •) — полугруппа, а 1 — константа для нейтрального элемента;
    группы — это системы сигнатуры {+², — 1,0} с ассоциативной бинарной операцией +, унарной операцией — взятия обратного элемента выделенным элементов (константой) 0 для нейтрального элемента;
    кольца — это системы сигнатуры {+², -², — 1, 0} такие, что (A; +, —, 0) — абелева группа, (A; •) — полугруппа, и выполняются правый и левый законы дистрибутивности для операций сложения и умножения;
    модули над кольцами, решетки, булевы алгебры, частично упорядоченные множества, графы и т. д.
    В главе 1 мы познакомимся с алгебраическими системами, возникающими в различных областях математики. Это решетки. Они позволяют описывать иерархии объектов (решетки подпространств, решетки замкнутых подмножеств, решетки конгруэнций ит. и.) и, как многие классические алгебры, обладают достаточно интересной структурной теорией.
    В главе 2 мы вернемся к произвольным алгебраическим системам и познакомимся с общими понятиями подсистемы, изоморфизма, гомоморфизма, произведений и пределов систем. Эти основные конструкции приводят к понятию операторов на классах систем и позволяют описывать классы, аксиоматизируемые формулами специальных видов.
    В главе 3 мы встретимся с хорошо изученными специальными аксиоматизируемыми классами (многообразиями и квазимногообразиями) и познакомимся с описаниями таких классов в терминах замкнутости относительно операторов и с помощью предложений специального вида.

6

Глава 1





                Начальные понятия теории решеток




1. Определения решеток

   Решетки — алгебраические системы, которые можно определить двумя способами. Первый из них ставит решетки в один ряд с такими классическими алгебрами, как группы и кольца, а другой основан на понятии порядка и допускает геометрическое представление.
   Определение 1.1. Решетка — это алгебра с двумя основными бинарными операциями Л и V, удовлетворяющая для всех х, у и z следующим условиям
   ассоциативности: xV(yVz) = (xVy)Vz и хЛ(уЛz) = (xЛy)Лz, коммутативности: х V у = у V х х х Л у = у Л х, идемпотентности: х V х = хих Л х = х, поглощения: х V (х Л у) = хих Л (х V у) = х.
   Упражнение 1. Проверьте, что следующие алгебры суть решетки:
   (а)    множество натуральных чисел с операциями наибольшего общего делителя и наименьшего общего кратного;
   (б)    множество подмножеств произвольного множества с операциями пересечения и объединения;
   (в)    множество вещественных чисел с операциями минимума и максимума.
   Определение 1.2. Решеткой называется частично упорядоченное множество (P; 6) такое, что для любых a,b € P существуют точная верхняя и точная нижняя грани множества {a, b}.

7

    Теорема 1.3. Если L = (L; Л, V) — решетка в смысле определения 1.1, то С = (L; 6) является решеткой в смысле определения 1.2, где a 6 b тогда и только тогда, когда a = а Л b.
    Если P = (P; 6) — решетка в смысле определения 1.2, то P' = (P; Л, V) является решеткой в смысле определения 1.2, где а Л b = inf (a, b) и а V b = sup(a, b).
    Доказательство. Пусть С — решетка в смысле первого из определений.
    Проверим сначала, что отношение 6 на L, определенное по правилу a 6 b тогда и только тогда, когда a Л b = a, является отношением частичного порядка. Рефлексивность является следствием идемпотентности, антисимметричность — коммутативности, а транзитивность — ассоциативности операций решетки.
    Проверим, что a V b = sup(a, b). В силу условия поглощения a Л (a V b) = a, т. е. a 6 a V b. В силу условий коммутативности и поглощения bЛ(aVb) = bЛ(bVa) = b, т. е. b 6 aVb. Следовательно, a V b — верхняя грань для a и b. Рассмотрим любую верхнюю грань и для a и b и покажем, что a V b 6 и. Вычислим (a V b) V и. Так как a 6 и, имеем a = aЛu, откуда в силу условия поглощения u = (a Л и) V и = a V и. Аналогично и = b V и. Следовательно, в силу условий на решеточные операции, а также двух только что полученных равенств
  (a V b) = (a V b) Л ((a V b) V и) = (a V b) Л (a V (b V и)) =
                            = (a V b) Л (a V и) = (a V b) Л и,
откуда a V b 6 и, t. e. a V b = sup(a, b).
    Доказательство равенства a Л b = inf(a, b) аналогичное.
    Пусть теперь P — решетка в смысле второго из определений. Нетрудно проверить, что алгебра P0 удовлетворяет всем четырем условиям определения 1.1. Например, коммутативность операции V следует из очевидного равенства sup(a, b) = sup(b, a), а условие поглощения a = a V (a Л b) получается из равенства a = sup(a, inf(a, b)), которое, очевидно, верное в силу неравенства inf(a, b) 6 a.                                   □

8

    Упражнение 2. Заполните оставленные пробелы в доказательстве теоремы 1.3.
    Замечание 1.4. Нетрудно заметить, что конструкции, позволяющие переходить от одного определения решетки к другому, являются обратными друг к другу. Поэтому в дальнейшем будем без дополнительных пояснений использовать более удобное определение.
    Упражнение 3. Покажите, что, меняя ролями операции Л и V, мы опять получим решетку (двойственную к исходной). Как связаны диаграммы двойственных друг другу решеток?
    Упражнение 4. Пусть G — группа, SG и NG — частично упорядоченные множества всех подгрупп и нормальных подгрупп группы G (относительно включения). Покажите, что эти ч. у. множества являются решетками и опишите решеточные операции.

2. Некоторые алгебраические понятия

    В частном случае решеток рассмотрим важные алгебраические понятия изоморфизма, подсистемы и гомоморфизма. Далее (по алгебраической традиции) не будем различать решетку и ее носитель, если ясно, какой из этих объектов имеется в виду.
    Говорят, что решетки L1 и L2 изоморфные, если существует биективное отображение (шолщде/шам) а : L1 ^ L2 такое, что для любых a,b G L1 выполняются равенства
(1)     а(а Л b) = a(a) Л a(b) и a(a V b) = a(a) V a(b).
    Легко заметить, что для любого изоморфизма а обратное отображение а⁻¹ существует и является изоморфизмом.
    Если рассматривать решетки как частично упорядоченные множества, то определение изоморфизма изменится: отображение а, по-прежнему, должно быть биекцией, но сохраняющей структуру ч. у. множества, т. е.
(2)     a 6 b -^^- a(a) 6 a(b).

9

    Упражнение 5. Верно ли, что биекция а является изоморфизмом решеток как алгебр (в смысле определения 1.1) тогда и только тогда, когда она является изоморфизмом соответствующих ч. у. множеств (в смысле определения 1.2)?
    Отображение а : L1 ^ L2 называется (решеточным) гомоморфизмом, если оно удовлетворяет условию (1).
    Гомоморфизмом ч. у. множеств (или монотонным отображением) называется отображение а : L1 ^ L2, удовлетворяющее прямой импликации в (2), т. е.
(3)     a 6 b ^ а(а) 6 а(Ь).
    Упражнение 6. Покажите, что существует биективный гомоморфизм из ч. у. множества подмножеств двухэлементного множества на четырехэлементную цепь, который не является изоморфизмом.
    Упражнение 7. Укажите монотонное отображение решетки подмножеств трехэлементного множества в себя такое, что образ не является решеткой.
    Хотя приведенные выше примеры показывают, что решеточные гомоморфизмы и монотонные отображения решеток заметно различаются по свойствам, следующее утверждение дает удобный критерий изоморфности в терминах существования монотонных отображений.
    Предложение 1.5. Решетки L1 l L2 изоморфны, если и только если существует биекция а между L1 и L2 такая, что а а а⁻¹ являются монотонными отображениями.
    Доказательство. Пусть а : L1 ^ L2 — изоморфизм и условие a 6 b выполняется в L1. Тогда a = a Л b, откуда получаем а(а) = а^,Л b) = а^,) Л а(Ь). Следовательно, а^,) 6 а(Ь). Так как а⁻¹ — изоморфизм, аналогично заключаем, что а⁻¹ — гомоморфизм из частично упорядоченного множества L2 в частично упорядоченное множество L1.

10

    Докажем обратную импликацию. Пусть а и а⁻¹ сохраняют порядок. Для любых a,b € L1 имеем a 6 a V b и b 6 a V b. Следовательно, a(a) 6 a(a V b) и a(b) 6 a(a V b), откуда заключаем, что a(a) V a(b) 6 a(a V b). Рассмотрим произвольный элемент u € L2 такой, что a(a) V a(b) 6 u. Имеем a(a) 6 u a a(b) 6 u, откуда заключаем, что a 6 a⁻¹(u) и b 6 a⁻¹(u). Следовательно, aVb 6 a⁻¹(u) и a(aVb) 6 u. Таким образом, a(a)Va(b) = a(aVb). Для другой операции рассуждения аналогичные.           □
    Пусть L — решетка, L1 С L и L1 = 0. Если для любых a,b € L1 выполняются условия a V b € L1 и a Л b € L1, то множество L1 с сужениями онераций решетки L на L1 называется подрешеткой решетки L (запись: L1 6 L). Говорим, что решетка L1 вложима в решетку L2 (и также пишем L1 6 L₂), если существует подрешетка решетки L2, изоморфыая решетке L1.
    Упражнение 8. Пусть L — решетка, получающаяся из решетки подмножеств двухэлементного множества присоединением нового наибольшего элемента. Покажите, что не любое подмножество L1 С L является подрешеткой. Приведите пример четырехэлементного подмножества, которое является решеткой, но не является подрешеткой решетки L.
    Для любой решетки L и подмножества X С L определим подрешетку, порожденную X как наименьшее подмножество, содержащее X и замкнутое относительно операций решетки L.
    Подрешетка I решетки L называется идеалом, если для любых i € I и a € L элемент a Л i принадлежит I. Идеал I собственный, если I = L, и простой, если из того, что a Л b € I следует a € I или b € I.
    Упражнение 9. Покажите, что пересечение любого множества идеалов снова является идеалом.
    Наименьший идеал, содержащий подмножество X, называется идеалом, порожденным X. В силу упражнения 9, в любой решетке L для любого непустого подмножества X С L существует идеал I, порожденный X в L.

11