Лекции по прикладной алгебре. v2.0 (1127112), страница 26
Текст из файла (страница 26)
множества P = h P, 6 i∅ 6= Q ⊆ P ⇒ dim(Q) 6 dim(P), при удалении 1-гоэлемента его размерность уменьшается не более, чем на 1;dim(P + Q) = max dim(P), dim(Q) , если хотя быодно из множеств не является цепью и dim(P + Q) = 2;dim(P × Q) 6 dim(P) + dim(Q);dim(P) 6 |P|/2 при |P| > 4 (теорема Хирагучи).Теорема («компактности»)Пусть P — такое ч.у. множество, что любое его конечное ч.у.подмножество имеет размерность, не превосходящую d. Тогдаdim(P) 6 d.355 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествЛинеаризацияО размерности ч.у.
множества P = h P, 6 i∅ 6= Q ⊆ P ⇒ dim(Q) 6 dim(P), при удалении 1-гоэлемента его размерность уменьшается не более, чем на 1;dim(P + Q) = max dim(P), dim(Q) , если хотя быодно из множеств не является цепью и dim(P + Q) = 2;dim(P × Q) 6 dim(P) + dim(Q);dim(P) 6 |P|/2 при |P| > 4 (теорема Хирагучи).Теорема («компактности»)Пусть P — такое ч.у. множество, что любое его конечное ч.у.подмножество имеет размерность, не превосходящую d. Тогдаdim(P) 6 d.wp1 :n4c1nc21−6 dim(P) 61−, n = |P|.log n4log n355 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествЛинеаризацияd-несводимые ч.у. множестваОпределениеЧ.у.
множество P называется d-несводимым для некоторогоd > 2, если dim(P) = d и dim(P 0 ) < d для любогособственного ч.у. подмножества P 0 ⊂ P .... несводимые множества:2 — двухэлементная антицепь (единственное);3 — s3 , sh, shd + ... — описаны, регулярны и хорошо изучены;4 — достаточно часто встречаются и весьма причудливы;t — St (единственное 2t-элементное) + ...;каждое t-несводимое ч.у. множество являетсяч.у.
подмножеством некоторого (t + 1)-несводимого.356 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествЛинеаризация4-несводимое ч.у. множество[[[◦◦' '◦ ''A'A ◦A''A'A''' '''AAA AA'A'' '''' AA A'◦◦◦ [◦ [[◦◦◦357 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествЛинеаризацияПроблема НогинаКаково наибольшее значение π(d, n) мощности множествамаксимальных элементов d-несводимого n-элементного ч.у.множества при d > 4?Данная проблема до сих пор остаётся открытой.358 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествЛинеаризацияПроблема НогинаКаково наибольшее значение π(d, n) мощности множествамаксимальных элементов d-несводимого n-элементного ч.у.множества при d > 4?Данная проблема до сих пор остаётся открытой.Утверждениеπ(d, n) 6 n − d .358 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествЧто надо знатьРаздел I1Конечные поля или поля ГалуаПоля вычетов по модулю простого числаВычисление элементов в конечных поляхЛинейная алгебра над конечным полемКорни многочленов над конечным полемСуществование и единственность поля Галуа из pnэлементовЦиклические подпространстваЗадачиЧто надо знать2Коды, исправляющие ошибкиПонятие помехоустойчивого кодирования.
Коды ХэммингаГрупповые (линейные) коды359 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествЧто надо знатьРаздел IIЦиклические кодыКоды БЧХЗадачиЧто надо знать3Теория перечисления ПойаДействие группы на множествеПрименение леммы Бёрнсайда для решениякомбинаторных задачПрименение теоремы Пойа для решения комбинаторныхзадачЗадачиЧто надо знать4Некоторые вопросы теории частично упорядоченныхмножеств360 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествЧто надо знатьРаздел IIIОсновные понятия теории ч.у. множествОперации над ч.у. множествамиЛинеаризацияЧто надо знать5Алгебраические решёткиРешётки: определение, основные свойстваМодулярные и дистрибутивные решёткиПрименение теории решёток к задаче классификацииЧто надо знать361 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествЧто надо знатьЧастично упорядоченные (ч.у.) множества: определение,примеры, основные понятия.
Диаграммы Хассе и особыеэлементы ч.у. множеств.Ранжированные ч.у. множества. Цепное условиеЖордана-Дедекинда. Порядковые гомоморфизмыИдеалы и фильтры ч.у. множеств. Конусы. Точные грани.Операции над ч.у. множествами.Теорема Шпильрайна. Линейное продолжение ч.у.множества и топологическая сортировка.Линеаризации и вероятностное пространство над ними.XYZ-теорема.
Проблема сортировки и «1/3 – 2/3предположение».Спектр и размерность ч.у. множеств. Свойстваразмерности, d-несводимые множества и проблема Ногина.362 / 432Прикладная алгебраАлгебраические решёткиРешётки: определение, основные свойстваРаздел I1Конечные поля или поля ГалуаПоля вычетов по модулю простого числаВычисление элементов в конечных поляхЛинейная алгебра над конечным полемКорни многочленов над конечным полемСуществование и единственность поля Галуа из pnэлементовЦиклические подпространстваЗадачиЧто надо знать2Коды, исправляющие ошибкиПонятие помехоустойчивого кодирования. Коды ХэммингаГрупповые (линейные) коды363 / 432Прикладная алгебраАлгебраические решёткиРешётки: определение, основные свойстваРаздел IIЦиклические кодыКоды БЧХЗадачиЧто надо знать3Теория перечисления ПойаДействие группы на множествеПрименение леммы Бёрнсайда для решениякомбинаторных задачПрименение теоремы Пойа для решения комбинаторныхзадачЗадачиЧто надо знать4Некоторые вопросы теории частично упорядоченныхмножеств364 / 432Прикладная алгебраАлгебраические решёткиРешётки: определение, основные свойстваРаздел IIIОсновные понятия теории ч.у.
множествОперации над ч.у. множествамиЛинеаризацияЧто надо знать5Алгебраические решёткиРешётки: определение, основные свойстваМодулярные и дистрибутивные решёткиПрименение теории решёток к задаче классификацииЧто надо знать365 / 432Прикладная алгебраАлгебраические решёткиРешётки: определение, основные свойстваРешёточно упорядоченное множествоОпределениеЧ.у. множество, в котором для любых элементов a и bсуществуют inf {a, b} и sup {a, b} называют решёточноупорядоченным.Решётка называется полной, если любое подмножество еёэлементов имеет точные верхнюю и нижнюю грани.366 / 432Прикладная алгебраАлгебраические решёткиРешётки: определение, основные свойства367 / 432Алгебраические решётки: определениеОпределениеАлгебраическая решётка — это тройка 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.Прикладная алгебраАлгебраические решёткиРешётки: определение, основные свойства367 / 432Алгебраические решётки: определениеОпределениеАлгебраическая решётка — это тройка 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.Прикладная алгебраАлгебраические решёткиРешётки: определение, основные свойстваРешётка всех разбиений множества — беллианРис.
10. Беллианы множеств { a, b, c } и { 1, 2, 3, 4 } Πn = B(n) — количество всевозможных эквивалентностейn-элементном множестве, число Белла.B(3) = 5, B(4) = 15, . . . , B(20) =368 / 432Прикладная алгебраАлгебраические решёткиРешётки: определение, основные свойстваРешётка всех разбиений множества — беллианРис. 10. Беллианы множеств { a, b, c } и { 1, 2, 3, 4 } Πn = B(n) — количество всевозможных эквивалентностейn-элементном множестве, число Белла.B(3) = 5, B(4) = 15, .
. . , B(20) = 51724158235372, . . ..368 / 432Прикладная алгебраАлгебраические решёткиРешётки: определение, основные свойства369 / 432Эквивалентность решёточно упорядоченных множеств ирешётокТеорема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 будет решёточно упорядоченныммножеством.Прикладная алгебраАлгебраические решёткиРешётки: определение, основные свойства370 / 432Эквивалентность решёточно упорядоченных множеств ирешёток...Теорема устанавливает взаимно-однозначное соответствиемежду решёточно упорядоченными множествами и решётками:из одной АС всегда можно получить другую.Поэтому термин «решётка» применяют для обоих понятий:любую решётку можно представить либо как упорядоченноемножество, либо как алгебру.решёточномножестваh R, 6 ih N, | ih P(A), ⊆ iупорядоченныерешёткиh R, max, min ih N, ∨, ∧ ih P(A), ∪, ∩ iВозможность такого рассмотрения решёток позволяет вводитьв них как порядковые, так и алгебраические операции, чтоприводит к богатой и многообразной в приложениях теории.Прикладная алгебраАлгебраические решёткиРешётки: определение, основные свойстваРешётки: примерыРешётки (A 6= ∅) —все булевы алгебры;все цепи;единственные 1-, 2-, 3-элементные решётки — цепи 1, 2, 34-элементные решётки — 4 и B 2 :◦ [[◦ [◦[ ◦371 / 432Прикладная алгебраАлгебраические решёткиРешётки: определение, основные свойства372 / 4325-элементные решётки —[[[c [b[[aιιo[[[cb [[[ oaПрикладная алгебраАлгебраические решёткиРешётки: определение, основные свойства373 / 4325-элементные решётки — пятиугольник N5 и бриллиант M3cι44[[[a[cb[[ oι44444hhha[h[[ hhhob+ цепь 5Прикладная алгебраАлгебраические решёткиРешётки: определение, основные свойстваРешётки: универсальные грани и атомыНаименьший элемент решётки (как р.у.м.) — её ноль (o),наибольший — единица (ι).o и ι решётки — её универсальные грани.374 / 432Прикладная алгебраАлгебраические решёткиРешётки: определение, основные свойстваРешётки: универсальные грани и атомыНаименьший элемент решётки (как р.у.м.) — её ноль (o),наибольший — единица (ι).o и ι решётки — её универсальные грани.Решётка может и не иметь универсальных граней: Z, h N, | i —только o = 1.374 / 432Прикладная алгебраАлгебраические решёткиРешётки: определение, основные свойстваРешётки: универсальные грани и атомыНаименьший элемент решётки (как р.у.м.) — её ноль (o),наибольший — единица (ι).o и ι решётки — её универсальные грани.Решётка может и не иметь универсальных граней: Z, h N, | i —только o = 1.Все конечные решётки содержат o и ι.374 / 432Прикладная алгебраАлгебраические решёткиРешётки: определение, основные свойстваРешётки: универсальные грани и атомыНаименьший элемент решётки (как р.у.м.) — её ноль (o),наибольший — единица (ι).o и ι решётки — её универсальные грани.Решётка может и не иметь универсальных граней: Z, h N, | i —только o = 1.Все конечные решётки содержат o и ι.ОпределениеЭлемент a 6= o решётки L с нулём o называется атомом еслидля любого элемента x этой решётки пересечение a u x равнолибо o, либо a.В последнем случае говорят, что элемент x содержит атом a.374 / 432Прикладная алгебраАлгебраические решёткиРешётки: определение, основные свойства375 / 432Гомоморфизмы решётокОпределениеОтображение ϕ решётки L в решётку L 0 называетсяалгебраическим или решёточным гомоморфизмом, если длялюбых x, y ∈ L справедливы равенстваϕ(x t y) = ϕ(x) t ϕ(y)иϕ(x u y) = ϕ(x) u ϕ(y).Биективный решёточный гомоморфизм есть решёточныйизоморфизм.
Изоморфизм решётки в себя называетсяавтоморфизмом.Инъективные и сюръективные решёточные гомоморфизмыназывают решёточными (или алгебраическими)мономорфизмами (вложениями) и эпиморфизмамисоответственно.Прикладная алгебраАлгебраические решёткиРешётки: определение, основные свойства376 / 432Связь порядкового и решёточного гомоморфизмов решётокПрикладная алгебраАлгебраические решёткиРешётки: определение, основные свойства376 / 432Связь порядкового и решёточного гомоморфизмов решёток1) Порядковые гомоморфизмырешёток как ч.у.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
