Лекции по прикладной алгебре. v2.0 (1127112), страница 27

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 27)

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

множество до (полной)решёткиТеорема (замыкание Макнила)Всякое ч.у. множество можно вложить в подходящую полнуюрешётку с сохранением всех точных граней.Универсальные грани и элементы,отмеченные знаком • суть сечения Макнила.377 / 432Прикладная алгебраАлгебраические решёткиРешётки: определение, основные свойстваПополнение произвольного ч.у. множество до (полной)решёткиТеорема (замыкание Макнила)Всякое ч.у. множество можно вложить в подходящую полнуюрешётку с сохранением всех точных граней.Универсальные грани и элементы,отмеченные знаком • суть сечения Макнила.Теорема показывает, что знаменитое построениеР.

Дедекиндом действительных чисел «сечениями»на самом деле применимо для любого ч.у. множества.377 / 432Прикладная алгебраАлгебраические решёткиРешётки: определение, основные свойства378 / 432Идеалы решётокОпределениеПусть h L, t, u i — решётка. Непустое подмножество Iэлементов L называется её (решёточным) идеалом, если1) (x ∈ I) N (y 6 x) ⇒ y ∈ Iи2) x, y ∈ I ⇒ x t y ∈ I .Двойственно, непустое подмножество F элементов Lназывается её решёточным фильтром, если1) (x ∈ F ) N (x 6 y) ⇒ y ∈ Fи2) x, y ∈ F ⇒ xuy ∈ F .Непустое подмножество I оказывается решёточным идеалом,iff для любых её элементов x и y справедливаэквивалентность x, y ∈ I ⇔ x t y ∈ 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[[◦ [◦ [[[◦ [• [[ ◦ [[[◦ [a[◦[ [ b [[ ◦ [•◦[ [[ ◦ [◦[ ••Рис.

11. { a, b, •, • } 6 42 , но { a, b, •, • } 66 42Прикладная алгебраАлгебраические решёткиМодулярные и дистрибутивные решёткиРаздел I1Конечные поля или поля ГалуаПоля вычетов по модулю простого числаВычисление элементов в конечных поляхЛинейная алгебра над конечным полемКорни многочленов над конечным полемСуществование и единственность поля Галуа из pnэлементовЦиклические подпространстваЗадачиЧто надо знать2Коды, исправляющие ошибкиПонятие помехоустойчивого кодирования. Коды ХэммингаГрупповые (линейные) коды382 / 432Прикладная алгебраАлгебраические решёткиМодулярные и дистрибутивные решёткиРаздел IIЦиклические кодыКоды БЧХЗадачиЧто надо знать3Теория перечисления ПойаДействие группы на множествеПрименение леммы Бёрнсайда для решениякомбинаторных задачПрименение теоремы Пойа для решения комбинаторныхзадачЗадачиЧто надо знать4Некоторые вопросы теории частично упорядоченныхмножеств383 / 432Прикладная алгебраАлгебраические решёткиМодулярные и дистрибутивные решёткиРаздел IIIОсновные понятия теории ч.у.

множествОперации над ч.у. множествамиЛинеаризацияЧто надо знать5Алгебраические решёткиРешётки: определение, основные свойстваМодулярные и дистрибутивные решёткиПрименение теории решёток к задаче классификацииЧто надо знать384 / 432Прикладная алгебраАлгебраические решёткиМодулярные и дистрибутивные решёткиМодулярные решёткиОпределениеРешётка h L, t, u i называется модулярной, если для любыхx, y, z ∈ 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 ∈ 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Решётка всех эквивалентностей на данном множестве вобщем случае не модулярна.385 / 432Прикладная алгебраАлгебраические решёткиМодулярные и дистрибутивные решётки386 / 432Пятиугольник N5 — немодулярная решёткаРешётка всех эквивалентностей на данноммножестве в общем случае не модулярна.

α = (1234), β = (1234), γ = (1234), α 6 γαt(γuβ) = αto = α 6= γu(αtβ) = γuι = γ.Прикладная алгебраАлгебраические решёткиМодулярные и дистрибутивные решётки386 / 432Пятиугольник N5 — немодулярная решёткаРешётка всех эквивалентностей на данноммножестве в общем случае не модулярна. α = (1234), β = (1234), γ = (1234), α 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[[[ {a, b}OcbaOO∅Рис.

Характеристики

Список файлов лекций