PA_full (1127144), страница 26
Текст из файла (страница 26)
множествамиЛинеаризацияЧто надо знать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} ,2defx u y = inf {x, y} ,то структура h P, t, u i будет решёткой.Пусть 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 , 6ih , |ih P(A), ✓ iупорядоченныерешёткиh , max, min ih , _, ^ ih P(A), [, \ iВозможность такого рассмотрения решёток позволяет вводитьв них как порядковые, так и алгебраические операции, чтоприводит к богатой и многообразной в приложениях теории.Прикладная алгебраАлгебраические решёткиРешётки: определение, основные свойстваРешётки: примерыРешётки (A 6= ?) �все булевы алгебры;все цепи;единственные 1-, 2-, 3-элементные решётки � цепи 1, 2, 34-элементные решётки � 4 и B 2 :371 / 432Прикладная алгебраАлгебраические решёткиРешётки: определение, основные свойства372 / 4325-элементные решётки �◆c◆abaocboПрикладная алгебраАлгебраические решёткиРешётки: определение, основные свойства373 / 4325-элементные решётки � пятиугольник N5 и бриллиант M3◆◆cabboao+ цепь 5cПрикладная алгебраАлгебраические решёткиРешётки: определение, основные свойстваРешётки: универсальные грани и атомыНаименьший элемент решётки (как р.у.м.) � её ноль (o),наибольший � единица (◆).o и ◆ решётки � её универсальные грани.374 / 432Прикладная алгебраАлгебраические решёткиРешётки: определение, основные свойстваРешётки: универсальные грани и атомыНаименьший элемент решётки (как р.у.м.) � её ноль (o),наибольший � единица (◆).o и ◆ решётки � её универсальные грани.Решётка может и не иметь универсальных граней: , h , | i �только o = 1.374 / 432Прикладная алгебраАлгебраические решёткиРешётки: определение, основные свойстваРешётки: универсальные грани и атомыНаименьший элемент решётки (как р.у.м.) � её ноль (o),наибольший � единица (◆).o и ◆ решётки � её универсальные грани.Решётка может и не иметь универсальных граней: , h , | i �только o = 1.Все конечные решётки содержат o и ◆.374 / 432Прикладная алгебраАлгебраические решёткиРешётки: определение, основные свойстваРешётки: универсальные грани и атомыНаименьший элемент решётки (как р.у.м.) � её ноль (o),наибольший � единица (◆).o и ◆ решётки � её универсальные грани.Решётка может и не иметь универсальных граней: , h , | 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 2 L справедливы равенства'(x t y) = '(x) t '(y)и'(x u y) = '(x) u '(y).Биективный решёточный гомоморфизм есть решёточныйизоморфизм.
Изоморфизм решётки в себя называетсяавтоморфизмом.Инъективные и сюръективные решёточные гомоморфизмыназывают решёточными (или алгебраическими)мономорфизмами (вложениями) и эпиморфизмамисоответственно.Прикладная алгебраАлгебраические решёткиРешётки: определение, основные свойства376 / 432Связь порядкового и решёточного гомоморфизмов решётокПрикладная алгебраАлгебраические решёткиРешётки: определение, основные свойства376 / 432Связь порядкового и решёточного гомоморфизмов решёток1) Порядковые гомоморфизмырешёток как ч.у. множеств,вообще говоря,не являются алгебраическими.2) Любое отображение одной решётки на другую, сохраняющеехотя бы одну из решёточных операций, являетсяпорядковым гомоморфизмом.Прикладная алгебраАлгебраические решёткиРешётки: определение, основные свойства376 / 432Связь порядкового и решёточного гомоморфизмов решёток1) Порядковые гомоморфизмырешёток как ч.у.
множеств,вообще говоря,не являются алгебраическими.2) Любое отображение одной решётки на другую, сохраняющеехотя бы одну из решёточных операций, являетсяпорядковым гомоморфизмом.В случае изоморфизма проблемы снимаются.Теорема (об эквивалентности двух видов изоморфизмарешёток)Две решётки алгебраически изоморфны, iff они изоморфны какч.у.
множества.Прикладная алгебраАлгебраические решёткиРешётки: определение, основные свойстваПополнение произвольного ч.у. множество до (полной)решёткиТеорема (замыкание Макнила)Всякое ч.у. множество можно вложить в подходящую полнуюрешётку с сохранением всех точных граней.Универсальные грани и элементы,отмеченные знаком • суть сечения Макнила.377 / 432Прикладная алгебраАлгебраические решёткиРешётки: определение, основные свойстваПополнение произвольного ч.у.
множество до (полной)решёткиТеорема (замыкание Макнила)Всякое ч.у. множество можно вложить в подходящую полнуюрешётку с сохранением всех точных граней.Универсальные грани и элементы,отмеченные знаком • суть сечения Макнила.Теорема показывает, что знаменитое построениеР. Дедекиндом действительных чисел �сечениями�на самом деле применимо для любого ч.у. множества.377 / 432Прикладная алгебраАлгебраические решёткиРешётки: определение, основные свойства378 / 432Идеалы решётокОпределениеПусть h L, t, u i � решётка.
Непустое подмножество Iэлементов L называется её (решёточным) идеалом, если1) (x 2 I) N (y 6 x) ) y 2 Iи2) x, y 2 I ) x t y 2 I .Двойственно, непустое подмножество F элементов Lназывается её решёточным фильтром, если1) (x 2 F ) N (x 6 y) ) y 2 Fи2) x, y 2 F ) xuy 2 F .Непустое подмножество I оказывается решёточным идеалом,iff для любых её элементов x и y справедливаэквивалентность x, y 2 I , x t y 2 I и аналогично дляфильтров.Прикладная алгебраАлгебраические решёткиРешётки: определение, основные свойстваРешётки: теоремы о вложенияхТеорема (о представлении решёток)Всякая решётка может быть вложена в булеан подходящегомножества с сохранением всех точных нижних граней.379 / 432Прикладная алгебраАлгебраические решёткиРешётки: определение, основные свойстваРешётки: теоремы о вложенияхТеорема (о представлении решёток)Всякая решётка может быть вложена в булеан подходящегомножества с сохранением всех точных нижних граней.Теорема (Макнил)Всякую решётку можно вложить в подходящую полнуюрешётку с сохранением всех точных граней.379 / 432Прикладная алгебраАлгебраические решёткиРешётки: определение, основные свойстваРешётки: теоремы о вложенияхТеорема (о представлении решёток)Всякая решётка может быть вложена в булеан подходящегомножества с сохранением всех точных нижних граней.Теорема (Макнил)Всякую решётку можно вложить в подходящую полнуюрешётку с сохранением всех точных граней.ТеоремаВсякую конечную решётку можно вложить в конечную решёткуразбиений.379 / 432Прикладная алгебраАлгебраические решёткиРешётки: определение, основные свойстваПодрешёткиОпределениеНепустое подмножество L 0 решётки L = h L, t, u i называетсяеё подрешёткой (символически L 0 6 L), если L 0 устойчивоотносительно сужений t и u.380 / 432Прикладная алгебраАлгебраические решёткиРешётки: определение, основные свойстваПодрешёткиОпределениеНепустое подмножество L 0 решётки L = h L, t, u i называетсяеё подрешёткой (символически L 0 6 L), если L 0 устойчивоотносительно сужений t и u.Каждое подмножество решётки L является подрешёткой, iffL � цепь.Из определения следует, что подмножество элементов решёткиL может быть решёткой относительно наследуемого частичногопорядка, но не подрешёткой L.380 / 432Прикладная алгебраАлгебраические решёткиРешётки: определение, основные свойства381 / 432Подрешётка и не-подрешётка решётки L = 4 ⇥ 4••ab••Рис.
11. { a, b, •, • } 6 42 , но { a, b, •, • } 66 42Прикладная алгебраАлгебраические решёткиМодулярные и дистрибутивные решёткиРаздел I1Конечные поля или поля ГалуаПоля вычетов по модулю простого числаВычисление элементов в конечных поляхЛинейная алгебра над конечным полемКорни многочленов над конечным полемСуществование и единственность поля Галуа из pnэлементовЦиклические подпространстваЗадачиЧто надо знать2Коды, исправляющие ошибкиПонятие помехоустойчивого кодирования. Коды ХэммингаГрупповые (линейные) коды382 / 432Прикладная алгебраАлгебраические решёткиМодулярные и дистрибутивные решёткиРаздел IIЦиклические кодыКоды БЧХЗадачиЧто надо знать3Теория перечисления ПойаДействие группы на множествеПрименение леммы Бёрнсайда для решениякомбинаторных задачПрименение теоремы Пойа для решения комбинаторныхзадачЗадачиЧто надо знать4Некоторые вопросы теории частично упорядоченныхмножеств383 / 432Прикладная алгебраАлгебраические решёткиМодулярные и дистрибутивные решёткиРаздел IIIОсновные понятия теории ч.у.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
