PA_full (1127144), страница 27
Текст из файла (страница 27)
множествОперации над ч.у. множествамиЛинеаризацияЧто надо знать5Алгебраические решёткиРешётки: определение, основные свойстваМодулярные и дистрибутивные решёткиПрименение теории решёток к задаче классификацииЧто надо знать384 / 432Прикладная алгебраАлгебраические решёткиМодулярные и дистрибутивные решёткиМодулярные решёткиОпределениеРешётка h L, t, u i называется модулярной, если для любыхx, y, z 2 L в ней выполняется следующий модулярный законM od : x 6 y ) x t (y u z) = y u (x t z).385 / 432Прикладная алгебраАлгебраические решёткиМодулярные и дистрибутивные решёткиМодулярные решёткиОпределениеРешётка h L, t, u i называется модулярной, если для любыхx, y, z 2 L в ней выполняется следующий модулярный законM od : x 6 y ) x t (y u z) = y u (x t z).Пример1Модулярными являются все цепи, решётка h , | i, булевыалгебры и их подрешётки.2Решётка N Sub G всех нормальных подгрупп группы Gобразует модулярна (пересечение групп � всегда группа, аобъединение нормальных подгрупп совпадает с ихпроизведением).3Решётка всех эквивалентностей на данном множестве вобщем случае не модулярна.385 / 432Прикладная алгебраАлгебраические решёткиМодулярные и дистрибутивные решётки386 / 432Пятиугольник N5 � немодулярная решёткаРешётка всех эквивалентностей на данноммножестве в общем случае не модулярна.↵ = (1 23 4),= (12 34),= (12 34), ↵ 6↵t( u ) = ↵to = ↵ 6= u(↵t ) = u◆ = .Прикладная алгебраАлгебраические решёткиМодулярные и дистрибутивные решётки386 / 432Пятиугольник N5 � немодулярная решёткаРешётка всех эквивалентностей на данноммножестве в общем случае не модулярна.↵ = (1 23 4),= (12 34),= (12 34), ↵ 6↵t( u ) = ↵to = ↵ 6= u(↵t ) = u◆ = .Немодулярность N5 оказывается ключевой:Теорема (критерий модулярности решётки)Решётка модулярна, iff никакая её подрешётка не изоморфнапятиугольнику N5 .Прикладная алгебраАлгебраические решёткиМодулярные и дистрибутивные решёткиДистрибутивные решёткиОпределениеРешётка 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).387 / 432Прикладная алгебраАлгебраические решёткиМодулярные и дистрибутивные решёткиДистрибутивные решёткиОпределениеРешётка 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дистрибутивна.387 / 432Прикладная алгебраАлгебраические решёткиМодулярные и дистрибутивные решёткиВсякая дистрибутивная решётка модулярна(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.388 / 432Прикладная алгебраАлгебраические решёткиМодулярные и дистрибутивные решёткиКритерий дистрибутивности решёткиНедистрибутивность M3 , оказывается ключевой: справедливаТеоремаМодулярная решётка является дистрибутивной, iff никакая еёподрешётка не изоморфна ромбу M3 .389 / 432Прикладная алгебраАлгебраические решёткиМодулярные и дистрибутивные решёткиКритерий дистрибутивности решёткиНедистрибутивность M3 , оказывается ключевой: справедливаТеоремаМодулярная решётка является дистрибутивной, iff никакая еёподрешётка не изоморфна ромбу M3 .Следствие (критерий дистрибутивности решётки)Решётка дистрибутивна, iff никакая её подрешётка неизоморфна ни пятиугольнику N5 , ни ромбу M3 .389 / 432Прикладная алгебраАлгебраические решёткиМодулярные и дистрибутивные решёткиДистрибутивность решётки J(P)ЛеммаJ(P) 6 h P(P), [, \ i ) решётка J(P) дистрибутивна.390 / 432Прикладная алгебраАлгебраические решёткиМодулярные и дистрибутивные решётки390 / 432Дистрибутивность решётки J(P)ЛеммаJ(P) 6 h P(P), [, \ i ) решётка J(P) дистрибутивна.cO{a, b}OcabaObO?Рис.
12.Z3 ,J(Z3 )Прикладная алгебраАлгебраические решёткиМодулярные и дистрибутивные решёткиНеразложимые элементы решётокВ конечных дистрибутивных решётках важную роль играют неатомы (например, в конечной цепи всего один атом), анеразложимые в объединение элементы.391 / 432Прикладная алгебраАлгебраические решёткиМодулярные и дистрибутивные решёткиНеразложимые элементы решётокВ конечных дистрибутивных решётках важную роль играют неатомы (например, в конечной цепи всего один атом), анеразложимые в объединение элементы.ОпределениеЭлемент z 6= o решётки назовём неразложимым, если изz = x t y следует либо z = x, либо z = y.391 / 432Прикладная алгебраАлгебраические решёткиМодулярные и дистрибутивные решёткиНеразложимые элементы решётокВ конечных дистрибутивных решётках важную роль играют неатомы (например, в конечной цепи всего один атом), анеразложимые в объединение элементы.ОпределениеЭлемент z 6= o решётки назовём неразложимым, если изz = x t y следует либо z = x, либо z = y.Пример1Атомы любой решётки неразложимы, и в атомной булевойалгебре нет других неразложимых элементов.2В решётке h , | i неразложимы в точности степенипростых чисел.3В цепи ни один элемент не является разложимым.391 / 432Прикладная алгебраАлгебраические решёткиМодулярные и дистрибутивные решёткиНеразложимые элементы решёток...ЛеммаВ конечной решётке каждый ненулевой элемент может бытьпредставлен в виде объединения неразложимых элементов.392 / 432Прикладная алгебраАлгебраические решёткиМодулярные и дистрибутивные решёткиНеразложимые элементы решёток...ЛеммаВ конечной решётке каждый ненулевой элемент может бытьпредставлен в виде объединения неразложимых элементов.ДоказательствоЕсли элемент b неразложим, то b = b t b.
Пусть b = b1 t b2 иb1 6= b 6= b2 .Если и b1 , и b2 неразложимы, то лемма доказана.В противном случае представляем b1 и/или b2 в видеобъединения строго содержащихся в них элементов, и т.д.В силу конечности решётки указанный процесс закончится,и исходный элемент b будет представлен в видеобъединения неразложимых элементов.392 / 432Прикладная алгебраАлгебраические решёткиМодулярные и дистрибутивные решёткиПредставление произвольных элементов решётки черезнеразложимыеОбозначения для подмножеств элементов(дистрибутивной) решётки LIrr L � множество неразложимых в объединениеэлементов L;Irr(x) = { y 2 Irr L | y 6 x } � множество неразложимыхэлементов L, содержащихся в x.393 / 432Прикладная алгебраАлгебраические решёткиМодулярные и дистрибутивные решётки393 / 432Представление произвольных элементов решётки черезнеразложимыеОбозначения для подмножеств элементов(дистрибутивной) решётки LIrr L � множество неразложимых в объединениеэлементов L;Irr(x) = { y 2 Irr L | y 6 x } � множество неразложимыхэлементов L, содержащихся в x.Доказанная лемма утверждает, что в конечной решётке каждыйненулевой элемент x допускает представление:Gx =a.a 2 Irr(x)Прикладная алгебраАлгебраические решёткиМодулярные и дистрибутивные решёткиИзоморфизм ч.у.
множества и неразложимых элементоврешётки его порядковых идеаловЛеммаЕсли P � ч.у. множество, то Irr J(P) ⇠= P.394 / 432Прикладная алгебраАлгебраические решёткиМодулярные и дистрибутивные решётки394 / 432Изоморфизм ч.у. множества и неразложимых элементоврешётки его порядковых идеаловЛеммаЕсли P � ч.у. множество, то Irr J(P) ⇠= P.ДоказательствоПусть P � ч.у. множество и тогда J(P) � дистрибутивнаярешётка его порядковых идеалов. Порядковый идеал решёткинеразложим, iff он является главным:xO ) Irr J(P) ⇠= J0 (P) = { xO | x 2 P }.Ранее был установлен изоморфизм между ч.у. множеством исовокупностью его главных идеалов:' : P ! J(P ),поэтому P ⇠= J0 (P ) = Irr J(P ).'(x) = xO ,Прикладная алгебраАлгебраические решёткиМодулярные и дистрибутивные решётки395 / 432Irr J(P) ⇠= P: примерcO{a, b}OcabaObO?Рис. 13.Z3 ,множество Irr J(Z3 ) выделеноПрикладная алгебраАлгебраические решёткиМодулярные и дистрибутивные решёткиФундаментальная теорема о конечных дистрибутивныхрешёткахТеорема (ФТКДР, Г.
Биркгоф)Всякая конечная дистрибутивная решётка L изоморфнарешётке порядковых идеалов ч.у. множества её неразложимыхэлементов: L = J(Irr L)396 / 432Прикладная алгебраАлгебраические решёткиМодулярные и дистрибутивные решёткиФундаментальная теорема о конечных дистрибутивныхрешёткахТеорема (ФТКДР, Г.
Биркгоф)Всякая конечная дистрибутивная решётка L изоморфнарешётке порядковых идеалов ч.у. множества её неразложимыхэлементов: L = J(Irr L)Доказательство (набросок)Пусть L = h L, t, u i � конечная дистрибутивная решётка иJ(Irr L) � решётка порядковых идеалов ч.у. множества Irr L.Рассмотрим отображение : L ! J(Irr L) ,(x) = Irr(x).)Отображение есть биекция.x 6 y , Irr(x) ✓ Irr(y) , (x) ✓ (y).� (порядковый) изоморфизм между L и J(Irr L).396 / 432Прикладная алгебраАлгебраические решёткиМодулярные и дистрибутивные решётки397 / 432ФТКДР L = J(Irr L): иллюстрация◆◆Oc{a, b}OaboРис. 14.aO◆aLbIrr LbO?J(Irr L)Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификацииРаздел I1Конечные поля или поля ГалуаПоля вычетов по модулю простого числаВычисление элементов в конечных поляхЛинейная алгебра над конечным полемКорни многочленов над конечным полемСуществование и единственность поля Галуа из pnэлементовЦиклические подпространстваЗадачиЧто надо знать2Коды, исправляющие ошибкиПонятие помехоустойчивого кодирования.
Коды ХэммингаГрупповые (линейные) коды398 / 432Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификацииРаздел IIЦиклические кодыКоды БЧХЗадачиЧто надо знать3Теория перечисления ПойаДействие группы на множествеПрименение леммы Бёрнсайда для решениякомбинаторных задачПрименение теоремы Пойа для решения комбинаторныхзадачЗадачиЧто надо знать4Некоторые вопросы теории частично упорядоченныхмножеств399 / 432Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификацииРаздел IIIОсновные понятия теории ч.у.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
