AA3-5(Lattice) (PDF-лекции от Гурова)

ПРИКЛАДНАЯ АЛГЕБРА. Часть V: Алгебраические решёткиЧасть VАлгебраические решётки1 / 62ПРИКЛАДНАЯ АЛГЕБРА. Часть V: Алгебраические решёткиРешётки: определение, основные свойстваРазделы1Решётки: определение, основные свойства2Модулярные и дистрибутивные решётки3Применение теории решёток к задаче классификации4Что надо знать2 / 62ПРИКЛАДНАЯ АЛГЕБРА.

Часть V: Алгебраические решёткиРешётки: определение, основные свойстваРешёточно упорядоченное множествоОпределениеЧ.у. множество, в котором для любых элементов a и bсуществуют inf {a, b} и sup {a, b} называют решёточноупорядоченным.Решётка называется полной, если любое подмножество еёэлементов имеет точные верхнюю и нижнюю грани.3 / 62ПРИКЛАДНАЯ АЛГЕБРА. Часть V: Алгебраические решёткиРешётки: определение, основные свойства4 / 62Алгебраические решётки: определениеОпределениеАлгебраическая решётка — это тройка L = h L, t, u i, где L —непустое множество, а t (объединение), u (пересечение) —бинарные операции на нём, подчиняющимися парам законовкоммутативности, ассоциативности, идемпотентности ипоглощения:x t y = y t x;x u y = y u x;x t (y t z) = (x t y) t z; x u (y u z) = (x u y) u z;x t x = x;x u (x t y) = x;x u x = x,x t (x u y) = x.Принцип двойственности для решётокЛюбое утверждение, истинное для любых произвольныхэлементов решётки, остаётся таковым при замене u ↔ t.ПРИКЛАДНАЯ АЛГЕБРА.

Часть V: Алгебраические решёткиРешётки: определение, основные свойстваРешётка всех разбиений множества — беллианБеллианы множеств { a, b, c } и { 1, 2, 3, 4 } Πn = B(n) — количество всевозможных эквивалентностейn-элементном множестве — число Белла.B(3) = 5, B(4) = 15, .

. . , B(20) = 51724158235372, . . ..5 / 62ПРИКЛАДНАЯ АЛГЕБРА. Часть V: Алгебраические решёткиРешётки: определение, основные свойства6 / 62Эквивалентность решёточно упорядоченных множеств ирешётокТеорема1Пусть h P, 6 i — решёточно упорядоченное множество.Если для любых элементов x и y из P положитьdefx t y = sup {x, y} ,defx u y = inf {x, y} ,то структура h P, t, u i будет решёткой.2Пусть h L, t, u i — решётка.

Если для любых элементовx и y из L положитьdefx6y = xuy =xdef(или x 6 y = x t y = y),то структура h L, 6 i будет решёточно упорядоченныммножеством.ПРИКЛАДНАЯ АЛГЕБРА. Часть V: Алгебраические решёткиРешётки: определение, основные свойстваЭквивалентность решёточно упорядоченных множеств ирешёток...Теорема устанавливает взаимно-однозначное соответствиемежду решёточно упорядоченными множествами и решётками:из одной АС всегда можно получить другую.Поэтому термин «решётка» применяют для обоих понятий:любую решётку можно представить либо как упорядоченноемножество, либо как алгебру.решёточномножестваh R, 6 ih N, | ih P(A), ⊆ iупорядоченныерешёткиh R, max, min ih N, ∨, ∧ ih P(A), ∪, ∩ iВозможность такого рассмотрения решёток позволяет вводитьв них как порядковые, так и алгебраические операции, чтоприводит к богатой и многообразной в приложениях теории.7 / 62ПРИКЛАДНАЯ АЛГЕБРА.

Часть V: Алгебраические решёткиРешётки: определение, основные свойстваРешётки: примерыРешётки (A 6= ∅) —все булевы алгебры;все цепи;единственные 1-х, 2-х и 3-хэлементные решётки — цепи1, 2, 3;4-элементные решётки — 4 и B 2 :◦ [[◦ [◦[ ◦8 / 62ПРИКЛАДНАЯ АЛГЕБРА. Часть V: Алгебраические решёткиРешётки: определение, основные свойства9 / 625-элементные решётки —[[[c [b[[aιιo[[[cb [[[ oaПРИКЛАДНАЯ АЛГЕБРА.

Часть V: Алгебраические решёткиРешётки: определение, основные свойства10 / 625-элементные решётки — пятиугольник N5 и бриллиант M3cι44[[[a[cb[[ oι44444hhha[h[[ hhhob+ цепь 5ПРИКЛАДНАЯ АЛГЕБРА. Часть V: Алгебраические решёткиРешётки: определение, основные свойстваРешётки: универсальные грани и атомыНаименьший элемент решётки (как р.у.м.) — её ноль (o),наибольший — единица (ι).Это универсальные грани решётки.Решётка может их и не иметь: Z, h N, | i — только o = 1.Все конечные решётки содержат o и ι.ОпределениеЭлемент a 6= o решётки L с нулём o называется атомом еслидля любого элемента x ∈ L справедливоo,aux =a.В последнем случае говорят, что элемент x содержит атом a.11 / 62ПРИКЛАДНАЯ АЛГЕБРА.

Часть V: Алгебраические решёткиРешётки: определение, основные свойства12 / 62Гомоморфизмы решётокОпределениеОтображение ϕ решётки L в решётку L 0 называетсяалгебраическим или решёточным гомоморфизмом, если длялюбых x, y ∈ L справедливы равенстваϕ(x t y) = ϕ(x) t ϕ(y)иϕ(x u y) = ϕ(x) u ϕ(y).Биективный решёточный гомоморфизм — решёточныйизоморфизм.Изоморфизм решётки в себя называется автоморфизмом.Инъективные и сюръективные решёточные гомоморфизмыназывают решёточными (или алгебраическими)мономорфизмами (вложениями) и эпиморфизмамисоответственно.ПРИКЛАДНАЯ АЛГЕБРА.

Часть V: Алгебраические решёткиРешётки: определение, основные свойства13 / 62Связь порядкового и решёточного гомоморфизмов решёток1) Порядковые гомоморфизмырешёток как ч.у. множеств,вообще говоря, не являютсяалгебраическими.2) Любое отображение одной решётки на другую, сохраняющеехотя бы одну из решёточных операций,является порядковым гомоморфизмом.В случае изоморфизма проблемы снимаются.Теорема (об эквивалентности двух видов изоморфизмарешёток)Две решётки алгебраически изоморфны, iff они изоморфны какч.у.

множества.ПРИКЛАДНАЯ АЛГЕБРА. Часть V: Алгебраические решёткиРешётки: определение, основные свойстваПополнение произвольного ч.у. множества до решёткиТеорема (замыкание Макнила)Всякое ч.у. множество можно вложить в подходящую полнуюрешётку с сохранением всех точных граней.Универсальные грани и элементы,отмеченные знаком • суть сечения Макнила.Теорема показывает, что знаменитое построениеР. Дедекиндом действительных чисел «сечениями»на самом деле применимо для любого ч.у. множества.14 / 62ПРИКЛАДНАЯ АЛГЕБРА. Часть V: Алгебраические решёткиРешётки: определение, основные свойства15 / 62Идеалы решётокОпределениеПусть h L, t, u i — решётка.

Непустое подмножество Iэлементов L называется её (решёточным) идеалом, если¶ (x ∈ I) N (y 6 x) ⇒ y ∈ Iи· x, y ∈ I ⇒ x t y ∈ I .Двойственно, непустое подмножество F элементов Lназывается её решёточным фильтром, если¶ (x ∈ F ) N (x 6 y) ⇒ y ∈ Fи· x, y ∈ F ⇒ xuy ∈ F .Непустое подмножество I оказывается решёточным идеалом,iff для любых её элементов x и y справедливоx, y ∈ I ⇔ x t y ∈ Iи аналогично для фильтров.ПРИКЛАДНАЯ АЛГЕБРА.

Часть V: Алгебраические решёткиРешётки: определение, основные свойстваРешётки: теоремы о вложенияхТеорема (о представлении решёток)Всякая решётка может быть вложена в булеан подходящегомножества с сохранением всех точных нижних граней.Теорема (Макнил)Всякую решётку можно вложить в подходящую полнуюрешётку с сохранением всех точных граней.ТеоремаВсякую конечную решётку можно вложить в конечную решёткуразбиений.16 / 62ПРИКЛАДНАЯ АЛГЕБРА. Часть V: Алгебраические решёткиРешётки: определение, основные свойстваПодрешёткиОпределениеНепустое подмножество L 0 носителя решётки L = h L, t, u iназывается её подрешёткой (символически L 0 6 L), если L 0устойчиво относительно сужений t и u.Каждое подмножество решётки L является подрешёткой,iff L — цепь.Из определения следует, что подмножество элементов решёткиL может быть решёткой относительно наследуемогочастичного порядка, но не подрешёткой L.17 / 62ПРИКЛАДНАЯ АЛГЕБРА.

Часть V: Алгебраические решёткиРешётки: определение, основные свойстваПодрешётка и не-подрешётка решётки L = 4 × 4[[◦ [◦ [[[◦ [• [[ ◦ [[[◦ [a[◦[ [ b [[ ◦ [•◦[ [[ ◦ [◦[ ••{ a, b, •, • } 6 42 , но { a, b, •, • } 66 4218 / 62ПРИКЛАДНАЯ АЛГЕБРА. Часть V: Алгебраические решёткиМодулярные и дистрибутивные решёткиРазделы1Решётки: определение, основные свойства2Модулярные и дистрибутивные решётки3Применение теории решёток к задаче классификации4Что надо знать19 / 62ПРИКЛАДНАЯ АЛГЕБРА.

Часть V: Алгебраические решёткиМодулярные и дистрибутивные решёткиМодулярные решёткиОпределениеРешётка h L, t, u i называется модулярной, если для любыхx, y, z ∈ L в ней выполняется следующий модулярный законM od : x 6 y ⇒ x t (y u z) = y u (x t z).Пример1Модулярными являются все цепи, решётка h N, | i, булевыалгебры и их подрешётки.2Решётка N Sub G всех нормальных подгрупп группы Gобразует модулярна (пересечение групп — всегда группа, аобъединение нормальных подгрупп совпадает с ихпроизведением).3Решётка всех эквивалентностей на данном множестве вобщем случае не модулярна.20 / 62ПРИКЛАДНАЯ АЛГЕБРА.

Часть V: Алгебраические решёткиМодулярные и дистрибутивные решёткиПятиугольник N5 — немодулярная решёткаРешётка всех эквивалентностей на данноммножестве в общем случае не модулярна. α = (1234), β = (1234), γ = (1234), α 6 γαt(γuβ) = αto = α 6= γu(αtβ) = γuι = γ.Немодулярность N5 оказывается ключевой:Теорема (критерий модулярности решётки)Решётка модулярна, iff никакая её подрешётка не изоморфнапятиугольнику N5 .21 / 62ПРИКЛАДНАЯ АЛГЕБРА.

Часть V: Алгебраические решёткиМодулярные и дистрибутивные решёткиДистрибутивные решёткиОпределениеРешётка h L, t, u i называется дистрибутивной, если в нейвыполняются дистрибутивные законы(x t y) u z = (x u z) t (y u z);(x u y) t z = (x t z) u (y t z).Пример1Все цепи, булевы алгебры и их подрешётки дистрибутивны.2Решётка всех подпространств векторного пространства,упомянутая выше в качестве примера модулярнойрешётки, не является дистрибутивной.3Решётка Sub C всех подгрупп циклической группы Cдистрибутивна.22 / 62ПРИКЛАДНАЯ АЛГЕБРА. Часть V: Алгебраические решёткиМодулярные и дистрибутивные решёткиВсякая дистрибутивная решётка модулярна(atb)uc = ιuc = c 6= (auc)t(buc) = ato = aМодулярный закон — ослабленная формавторого дистрибутивногозаконаV4 = h e, x, y, xy i —четверная Клейна,решётка Sub V4 ∼= M3 (ромб)подгрупп V4 (все они нормальны) модулярна, ноне дистрибутивна: a = hxi, b = hyi, c = hxyi,(a t b) u c = ι u c = c 6= (a u c) t (b u c) = o t o = o.23 / 62ПРИКЛАДНАЯ АЛГЕБРА.