Диаграмма хассе

Диаграмма Хассе

Диаграмма Хассе — вид диаграмм. используемый для представления конечного частично упорядоченного множества в виде рисунка его транзитивного сокращения. Конкретно, для частично упорядоченного множества ( S. ≤ ) <\displaystyle (S,\leq )> диаграмма представляет каждый элемент S <\displaystyle S> как вершины на плоскости и отрезки или кривые, идущие вверх от элемента x <\displaystyle x> к элементу y <\displaystyle y> . если x ≤ y <\displaystyle x\leq y> и не существует элемента z <\displaystyle z> . для которого x ≤ z ≤ y <\displaystyle x\leq z\leq y> . Эти кривые могут пересекаться, но не должны проходить через вершины, если только они не являются концами линии. Такая диаграмма с помеченными вершинами однозначно определяют частичный порядок.

Впервые систематически такого рода визуализация описана Биркгофом в 1948 году [1]. им же дано название в честь использовавшего подобные диаграммы Хельмута Хассе. однако такого рода рисунки встречаются и в более ранних трудах, например, в учебнике французского математика Анри Фохта (нем. Henri Vogt ) 1895 года издания [2] .

Содержание

Хотя диаграммы Хассе является простым и интуитивно ясным средством для работы с конечным частично упорядоченным множеством. весьма сложно нарисовать «хорошую», удобную для визуального восприятия диаграмму для достаточно нетривиального множества из-за большого количества возможных вариантов отображения. Простая техника, предполагающая начать с минимальных элементов и рисовать вышележащие элементы последовательно часто дает плохие результаты — симметрии и внутренние структуры легко потерять.

Например, булеан множества из четырёх элементов, упорядоченного операцией включения ⊆ <\displaystyle \subseteq > может быть представлен любой из четырёх нижеприведённых диаграмм (каждое подмножество снабжено меткой с бинарной кодировкой, показывающей, содержится соответствующий элемент в подмножестве — 1, или нет — 0):

Диаграмма хассе

Диаграмма хассе

Диаграмма хассе

Диаграмма хассе

Первая диаграмма демонстрирует структуру уровней. Второй диаграмма имеет ту же структуру уровней, но на ней некоторые рёбра удлинены, чтобы подчеркнуть, что четырёхмерный куб является объединением двух трёхмерных. Третья диаграмма показывает некоторую внутреннюю симметрию. В четвёртой диаграмме вершины упорядочены подобно матрице 4×4.

Диаграмма хассе

Диаграмма Хассе подгрупповой решётки диэдрической группы D i h 4 <\displaystyle \mathrm _<4>> не имеет пересекающихся рёбер.

Некоторые свойства частичных порядков относительно планарности их диаграммы Хассе (то есть возможности нарисовать её без пересечения рёбер):

  • Если частичный порядок является решёткой. то его можно нарисовать без пересечений тогда и только тогда, когда размерность порядка не менее двух [3] [4] .
  • Если частичный порядок имеет по меньшей мере один минимальный или максимальный элемент, то можно за линейное время проверить, существует ли диаграмма без пересечений [5] .
  • Определить, можно ли частичный порядок представить планарной диаграммой Хассе, в общем случае NP-полная задача [6] .
  • Если заданы y <\displaystyle y> -координаты элементов частичного порядка, то за линейное время может быть найдена его диаграмма Хассе, сохраняющая заданные координаты, если только такая диаграмма существует [7]. В частности, если частный порядок имеет уровни, можно за линейное время определить, имеется ли диаграмма Хассе без пересечений, у которой высота каждой вершины пропорциональна её рангу.
  • K. A. Baker, P. Fishburn, F. S. Roberts. Partial orders of dimension 2 // Networks. — 1971. — Т. 2. № 1. — С. 11–28. — DOI :10.1002/net.3230020103.
  • G. Birkhoff. Lattice Theory. — 2nd. — American Mathematical Society. 1948. Перевод на русский: Г. Биркгоф . Теория структур / Пер. М. И. Граева. — 2-е изд. — М. Иностранная литература, 1952. — 408 с.
  • A. Garg, R. Tamassia Upward planarity testing // Order. — 1995. — Т. 12. № 2. — С. 109–133. — DOI :10.1007/BF01108622.
  • R. Freese Automated lattice drawing // Concept Lattices. — Springer-Verlag, 2004. — Т. 2961. — С. 589–590.
  • M. Jünger, S. Leipert. Level planar embedding in linear time // Proc. of International Symposium on Graph Drawing GD ’99. — 1999. — Т. 1731. — С. 72–81. — ISBN 978-3-540-66904-3. — DOI :10.1007/3-540-46648-7_7 .
  • H. G. Vogt. Leçons sur la résolution algébrique des équations. — Nony, 1895. — С. 91.

Диаграммы Хассе

Диаграмма Хассе – это графическое изображение конечных частично или линейно упорядоченных множеств.

Пусть М – упорядоченное множество и элементы x. y ÎM. причем x <y. Говорят, что y покрывает x. если не существует элемента z ÎM такого, что x £ z £y .

На диаграмме Хассе элементы множества М изображаются в виде точек. Две точки x и y соединяются отрезком прямой в том и только том случае, когда y покрывает x. При этом точку x рисуют ниже точки y .

1) M =< 1, 2, 3, 4, 5, 6 > упорядочено отношением £. Тогда его диаграмма выглядит так, как показано на рисунке 8. Такая диаграмма характерна для линейно упорядоченных множеств.

Диаграмма хассе
3) M =< 1, 3, 5, 7, 15, 21, 35, 105 > упорядочено отношением P =< (x. y ). y делится на x >. Его диаграмма Хассе изображена на рисунке 10 и совпадает с предыдущей диаграммой с точностью до обозначения элементов. Между элементами этих множеств можно установить биективное отображение, сохраняющее имеющуюся упорядоченность элементов. Говорят, что такие множества изоморфны (подобны) между собой относительно заданных на них отношений порядка.

188.123.231.15 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам.

Отношения порядка. Диаграмма Хассе

Отношение эквивалентности является обобщением отношения равенства: эквивалентные элементы считаются «равными». Обобщением обычного отношения служат отношения порядка.

Отношение называется предпорядком или квазипорядком, если R рефлексивно и транзитивно.

на множестве X =<1,2,3> является предпорядком.

Рефлексивное, антисимметричное, транзитивное отношение называется отношением нестрогого порядка и обозначается символом .

Антирефлексивное, антисимметричное, транзитивное отношение называется отношением строгого порядка и обозначается символом . Отношения строгого и нестрогого порядков иначе называют отношениями упорядоченности. Отношение, обратное отношению упорядоченности, также является отношением упорядоченности, т.е. ( ) = .

1. Пусть Y – некоторое множество, тогда отношение включения на множестве всех подмножеств P (Y ) является отношением нестрогого порядка.

2. Отношение «х старше у » на некотором множестве людей является отношением строгого порядка.

Множество Х с заданным в нем отношением порядка называется упорядоченным этим отношением. Если любые два элемента х и у множества Х находятся между собой в отношении порядка, то множество Х называется линейно упорядоченным или цепью, иначе множество Х называется частично упорядоченным. В частично упорядоченном множестве можно выделить цепь. Цепь с повторяющимися элементами называется мультицепью. Если между элементами х и у установлено отношение порядка, то они называются сравнимыми, иначе – несравнимыми. Антицепью (семейством Шпернера) называется подмножество частично упорядоченного множества, в котором любые два элемента несравнимы. Специальным типом частично упорядоченного множества является интервал |x,y]= (замкнутый) или (x,y)P= (открытый).

Двойственным к частично упорядоченному множеству называется частично упорядоченное множество, определенное на том же носителе с помощью обратного отношения. Это понятие лежит в основе принципа двойственности, который часто формулируют в виде: если некоторое утверждение справедливо для частично упорядоченных множеств, то справедливо и двойственное утверждение, то есть утверждение, касающееся двойственных частично упорядоченных множеств.

Рассмотрим множество Х с заданным на нем отношением частичного порядка .

Говорят, что элемент y покрывает элемент x. если х у и не существует никакого элемента zX. такого что х z у. Таким образом, у покрывает х тогда и только тогда, когда х у и [х,у ]=<х,у >. Любое частично упорядоченное множество можно представить в виде схемы. Диаграммой Хассе частично упорядоченного множества Х называ­ется граф, вершинами которого являются элементы множества X. а пара (х,у ) образует ребро, если элемент у покрывает элемент х. и такой что, если ху. то у рисуют с большей вертикальной координатой чем х .

Пример. Отношение включения на булеане Р (Х ), где Х =<а, b, с >. Оно является частично упорядоченным множеством. Множество Р (Х ) содержит восемь элементов: < . <a >, <b >, <c >, <a ,b >, <a ,c >, <b ,c >, <a ,b ,c >>. Диаграмма Хассе для этого отношения будет иметь вид (рис. 2.2).

Правило чтения диаграмм Хассе состоит в том, что ху. если можно пройти из точки х в точку у. следуя вдоль восходящих отрезков соединяющих точки. Смена направления движения разрешается только в точках диаграммы.

Пример. Пусть А=<1, 2, 3, 5, 6, 10, 15, 30>. Рассмотрим отношение частичного порядка ≤ на этом множестве, задаваемое по правилу: xyy делится на x. Диаграмма Хассе изображена на рис.2.3.

Заметим, что диаграммы Хассе этих двух отношений совпадают

Пусть Х и Y два частично упорядоченных множества. Если их диаграммы Хассе совпадают, то эти частично упорядоченные множества имеют одинаковую структуру.

Пример. На рис. 2.4 изображена диаграмма Хассе линейно упорядоченного множества Х=<1, 2, 3, 4, 5, 6, 7, 8> с обычным отношением порядка (≤) на множестве натуральных чисел, не превосходящих восьми.

Пусть задано частично упорядоченное множество X. Для элементов х и у из множества Х их верхней гранью называется любой элемент zХ такой, что и . а их нижней гранью – любой элемент tX. такой, что х и tу. На языке диаграмм Хассе ху означает, что существует путь из x в y ; верхняя грань x и y – это вершина, в которую есть путь из x и y ; нижняя грань x и y – это вершина из которой есть путь и в x и в y. В общем случае для некоторых элементов верхняя и нижняя грань может не существовать или быть неединственной, причем различные верхние (или нижние) грани могут быть несравнимы.

Пример. На рис. 2.5 а) изображена диаграмма Хассе множества . у которого элементы не имеют верхней грани, а элементы – нижней грани. На рис. 2.5 б) изображена диаграмма Хассе множества у которого все элементы имеют верхние и нижние грани, однако, например, и имеют две несравнимые верхние грани.

Решетки. Диаграмма Хассе.

Решеткой называют алгебраическую структуру, заданную конечным множеством M с двумя бинарными операциями.

Отношение является отношением частичного порядка.

Множество M с отношением частичного порядка называется упорядоченным множеством.

Для графического представления упорядоченного множества используют диаграмму Хассе.

Каждому элементу ставится в соответствие точка на плоскости, причем если выполняется соответствие Диаграмма хассе, точку, соответствующую элементу a, располагают ниже точки, соответствующей элементу b Диаграмма хассе.

Точки a и b соединены линией или ребром, если Диаграмма хассе Диаграмма хассе

Пусть имеется отношение порядка

Диаграмма хассе

Диаграмма хассе

Диаграмма Хассе помогает лучше понимать взаимосвязь элементов, принадлежащих одному и тому же упорядоченному множеству.

Дистрибутивная решетка.

Решетка называется дистрибутивной решеткой, если для всех элементов, принадлежащих множеству M, выполняется условие:

Диаграмма Хассе для дистрибутивной решетки

Диаграмма хассе Диаграмма хассе

Булева алгебра.

Булева алгебра — ограниченная дистрибутивная решетка, в которой имеется унарная операция дополнения на множестве М такое, что

Диаграмма хассе;

Диаграмма хассе.

Тема 5. Поля Галуа и их применение. Классическая теория Галуа. Расширения полей и их классификация. Сепарабельные и нормальные расширения. Расширения полей q, f_q, c(t).

5.1 Поля Галуа и их применение

Полем мы называем непустое множествоP комплексных чисел, обладающее следующими свойствами:

Полями являются, например, поле рациональных чисел R, поле действительных чиселD, поле комплексных чисел С.

Поле Галуаили Конечное поле — поле, состоящее из конечного числа элементов. Конечное поле обычно обозначается Диаграмма хассеили GF(q), где q — число элементов поля. Простейшим примером конечного поля является Диаграмма хассе—кольцовычетов по модулюпростого числа.

Характеристикаконечного поля являетсяпростымчислом.

Число элементов любого конечного поля есть его характеристика в натуральной степени: Диаграмма хассе.

Для каждого простогочисла p инатуральногоn существует конечное поле из q = pn элементов, единственное с точностью доизоморфизма. Это поле изоморфно полюразложениямногочлена Диаграмма хассе.

В каждом поле существует по крайней мере один примитивный элемент α, то есть такой, что Диаграмма хассе. Любой ненулевой элемент β является некоторой степенью примитивного элемента: Диаграмма хассе.

Мультипликативнаягруппа Диаграмма хассеконечного поля Диаграмма хассеявляетсяциклической группойпорядка q − 1. Поэтому, в частности, в конечном поле всегда существует примитивный элемент α, порядок которого равен q − 1, то есть αq − 1 = 1 и Диаграмма хасседля 0 < i < q − 1.

Поле Диаграмма хассесодержит в себе в качестве подполя Диаграмма хассетогда и только тогда, когда k является делителем n.

Диаграмма хассе, где p — простое: Диаграмма хассеи так далее.

Диаграмма хассе, где Диаграмма хассе—главный идеалкольца Диаграмма хассе, порожденный неприводимым многочленом Диаграмма хассестепени n.

Существует два варианта построения, в зависимости от количества элементов поля, которое необходимо построить:

Поле содержит p элементов, где p — простое.

Кольцо Диаграмма хассевычетов по модулю n в случае простого n = p не имеетделителей нуляи являетсяполем.

Элементы Диаграмма хассе— числа Диаграмма хассе. Операции проводятся как с обычными целыми числами с приведениемпо модулюp.

Поле содержит q = pn элементов, где p — простое, n — натуральное.

Кольцо Диаграмма хассеявляется полем тогда и только тогда, когда многочлен f(x)неприводимнад полем Диаграмма хассе. При этом Диаграмма хассе, где m = deg(f). Таким образом, для построения поля из q = pn элементов достаточно отыскать многочлен степени n, неприводимый над полем Диаграмма хассе, и определить Диаграмма хассекак указано выше.

Элементами поля Диаграмма хассеявляются все многочлены степени меньшей n с коэффициентами из Диаграмма хассе. Операции (сложение и умножение) проводятся по модулю многочлена f(x), то есть результат соответствующей операции — это остаток от деления на f(x) с приведением коэффициентовпо модулюp.

Пример построения поля GF(9)

Пусть надо построить поле GF(9) = GF(32). Для этого необходимо найти многочлен степени 2, неприводимыйв Диаграмма хассе. Такими многочленами являются: x 2 + 1

5.2 Классическая теория Галуа

Тео́рия Галуа́ — разделалгебры, изучающий симметрии корнеймногочленов. Симметрии описываются в терминахгруппы перестановоккорней многочлена (группа уравнения) — термин, впервые использованныйЭваристом Галуа

Созданная Э. Галуа теория алгебраических уравненийвысшихстепеней с одним неизвестным, т. е. уравнений вида

Диаграмма хассе

устанавливает условия сводимости решения таких уравнений к решению цепи др. алгебраических уравнений (обычно более низких степеней). Т. к. решением двучленного уравнения xm= А является радикал Диаграмма хассе, то уравнение (*) решается в радикалах, если его можно свести к цепи двучленных уравнений. Все уравнения 2-й, 3-й и 4-й степеней решаются в радикалах. Уравнение 2-й степениx2+ px + q = 0 было решено в глубокой древности по общеизвестной формуле

Диаграмма хассе

уравнения 3-й и 4-й степеней были решены в 16 в. Для уравнения 3-й степени вида x3+ px + q = 0 (к которому можно привести всякое уравнение 3-й степени) решение даётся т. н. формулой Кардано:

Диаграмма хассе

опубликованной Дж. Карданов 1545, хотя вопрос о том, найдена ли она им самим или же заимствована у др. математиков, нельзя считать вполне решенным. Метод решения в радикалах уравнений 4-й степени был указан Л.Феррари.

В течение трёх последующих столетий математики пытались найти аналогичные формулы для уравнений 5-й и высшихстепеней. Наиболее упорно над этим работали Э.Безуи Ж.Лагранж. Последний рассматривал особые линейные комбинации корней (т. н резольвенты Лагранжа), а также изучал вопрос о том, каким уравнениям удовлетворяют рациональные функции от корней уравнения (*). В 1801 К.Гаусссоздал полную теорию решения в радикалах двучленного уравнения видаxn = 1, в которой свёл решение такого уравнения к решению цепи двучленных же уравнений низших степеней и дал условия, необходимые и достаточные для того, чтобы уравнениеxn = 1 решалось в квадратных радикалах. С точки зрения геометрии, последняя задача заключалась в отыскании правильных n-угольников, которые можно построить при помощи циркуля и линейки; поэтому уравнениеxn = 1 и называется уравнением деления круга. Наконец, в 1824 Н.Абельпоказал, что общее уравнение 5-й степени (и тем более общие уравнениявысшихстепеней) не решается в радикалах. С другой стороны, Абель дал решение в радикалах одного общего класса уравнений, содержащего уравнения произвольно высоких степеней, т. н. абелевых уравнений.

Т. о. когда Галуа начал свои исследования, в теории алгебраических уравнений было сделано уже много, но общей теории, охватывающей все возможные уравнения вида (*), ещё не было создано. Например, оставалось: 1) установить необходимые и достаточные условия, которым должно удовлетворять уравнение (*) для того, чтобы оно решалось в радикалах; 2) узнать вообще, к цепи каких более простых уравнений, хотя бы и не двучленных, может быть сведено решение заданного уравнения (*) и, в частности, 3) выяснить, каковы необходимые и достаточные условия для того, чтобы уравнение (*) сводилось к цепи квадратных уравнений (т. е. чтобы корни уравнения можно было построить геометрически с помощью циркуля и линейки). Все эти вопросы Галуа решил в своём «Мемуаре об условиях разрешимости уравнений в радикалах», найденном в его бумагах после смерти и впервые опубликованном Ж. Лиувиллем (См. Лиувилль) в 1846. Для решения этих вопросов Галуа исследовал глубокие связи между свойствами уравнений и групп (См.Группа) подстановок, введя ряд фундаментальных понятий теории групп. Своё условие разрешимости уравнения (*) в радикалах Галуа формулировал в терминах теории групп. Г. т. после Галуа развивалась и обобщалась во многих направлениях. В современном понимании Г. т. — теория, изучающая те или иные математические объекты на основе их групп автоморфизмов (так, например, возможны Г. т. полей, Г. т. колец, Г. т. топологических пространств и т. п.).

Расширение полей и их классификация

Расшире́ние Галуа́ — алгебраическое расширение поляEÉ K, являющеесянормальнымисепарабельным. При этих условиях E будет иметь наибольшее количествоавтоморфизмовнад K (если E -конечно, то количество автоморфизмов также конечно и равно степени расширения [E:K]).

Группа автоморфизмов E над K называется группой Галуа и обозначается Gal(E/K) (или G(E/K)).

Если Gal(E/K) абелева,циклическаяи т.д. то расширение Галуа называется соответственно абелевым, циклическим и т.д. соответственно.

Иногда рассматривают группу Галуа для расширения E, которое сепарабельно, но необязательно нормально. В этом случае под группой Галуа E/K понимают группу Gal(Ē/K), где Ē — минимальное нормальное расширение K, содержащее E (в конечном случае, когда сепарабельное расширение является простым E=K(α) для некоторого α, являющегося корнем неприводимогонад K многочлена f(x), Ē являетсяполем разложенияэтого многочлена).

Согласно определению, полем называется множество, на котором заданы операции сложения и умножения, причём выполняются групповые аксиомы (см. теорию групп; должно быть обеспечено выполнение переместительного закона сложения и умножения, наличие нейтральных элементов относительно сложения и умножения).

Говоря обычным языком, для любых элементов должны выполняться равенства a+b=b+aиa*b=b*a. И должен существовать такой элемент е, принадлежащий нашему множеству (полю), что для всех элементов множестваaвыполняетсяa=a+e, и такой элементu, чтоa=a*u. Для обычного сложенияe=0, аu=1.

Однако, умножение и сложение, которые определены для полей, могут не иметь ничего общего с обычным сложением или умножением (кроме выполнения вышеупомянутых законов).

Полями Галуа называются поля, в которых присутствует конечное число элементов. Поле Галуа с количеством элементов NобозначаетсяGF(N).

Определим сложение, как операцию «исключающее ИЛИ» (XOR). Очевидно, что в таком случае, операция сложения является обратной самой себе. Операция умножения в двоичном виде будет выглядеть так

Т.е. обычное умножение «столбиком» со сложением определённым как XOR.

Такую операцию часто представляют как умножение полиномов. (x+1)*(x+1) =x 2 +1

Можно определить также операцию деления чисел (или полиномов) с остатком — по аналогичным правилам, например:

Число 11011000 (или полином x 7 +x 6 +x 4 +x 3 ) является остатком от деления.

Теперь рассмотрим поле Галуа, состоящее из 2 4 = 16 элементов. Операция сложения для этого поля определена какXOR, операция же умножения дополнена получением остатка по некоторому модулю.

Выберем в качестве модуля полином x 4 +x+1 (т..е число 10011).

Возьмём единицу и будем последовательно умножать её на 2 и рассмотрим числа, которые будут при этом получаться: (рассмотрим двоичную форму и представление в виде полинома)

1 = 2 0 = 0001 = x 0

2 0 *2 = 2 1 = 0010 mod 10011 =2 = x 1

2 1 *2 = 2 2 = 0100 mod 10111 =4 = x 2

2 2 *2 = 2 3 = 1000 mod 10011= 8 = x 3

Эти три строки повторяют обычное умножение, однако дальше всё не так просто

2 4 *2 = 2 4 = 10000 mod 10011 = 0011 = 3 = x+1

2 4 *2 = 2 5 = 100000 mod 10011 = 0110 = 6 = x 2 +x

Таким образом, 2 15 = 1 и, как нетрудно догадаться, при дальнейшем умножении весь цикл повторится снова. Полученные «степени двойки» несложно умножать между собой, например, 13 * 15 = 2 13 * 2 12 =2 12+13 = 2 25 mod 15 = 2 10 = 7

Тот же результат, разумеется, можно получить умножив 13 на 15 по описанным правилам по модулю 10011

Важным фактом является то, что в этой таблице в колонке «результат» повторились все числа от 1 до 15. Если задуматься, то из этого следует, что операция умножения обратима: в самом деле, раз a 13 *a 12 =a 10. тоa 10 /a 12 =a -2+15 =a 13

Таким образом, операция деления может быть выполнена так: находим в таблице «логарифм» — то есть «в какую степень нужно возвести 2 чтобы получить нужное число» — для делимого и делителя, после этого вычитаем логарифм делителя из логарифма делителя и прибавляем 15 (чтобы получить положительное число) и возводим 2 в эту степень.

Наша таблица обладает таким свойством не случайно; это обусловлено выбором основания 2 и модуля 10011. При выборе другого модуля и основания этого вполне могло и не получиться! Число 2 называется в данном случае «примитивным элементом поля». Формализуя, можно сказать что примитивный элемент поля Галуа GF(p) – это такое числоa, что для любыхt

Таким образом, построенное поле Галуа задаёт правила арифметики для чисел от 0 до 15 (т.е. для двоичных 4-разрядных чисел). В качестве сложения и вычитания используется XOR, умножение выполняется описанным выше способом и операция умножения всегда обратима, т.е. для любое число всегда без остатка делится на другое число (кроме 0: на 0 делить нельзя).

Все дальнейшие наши действия будут подразумевать применение такой арифметики над полями Галуа.

Аналогичным образом можно построить и арифметику для 256-битовых чисел – например, с помощью полинома x 8 +x 4 +x 3 +x 2 +1 (100011101)

Несмотря на то, что арифметика «странная», для неё можно выводить формулы, аналогичные формулам обычной арифметики. Что и будет делаться ниже.

Теория Галуа́ — раздел алгебры, изучающий симметрии корней многочленов. Симметрии описываются в терминах группы перестановок корней многочлена (группа уравнения) — термин, впервые использованный Эваристом Галуа.

Приложение к классическим задачам

Теория Галуа даёт единый элегантный подход к решению таких классических задач как

Какие фигуры можно построить циркулем и линейкой?

Какие алгебраические уравнения разрешимы с помощью стандартных алгебраических операций (сложение, вычитание, умножение, деление и извлечение корня)?

Симметрии корней — такие перестановки на множестве корней многочлена, для которых любому алгебраическому уравнению с рациональными коэффициентами, которому удовлетворяют корни, удовлетворяют и переставленные корни.

Пример: квадратное уравнение

У многочлена второй степени a x² + b x + c имеются два корня x1 и x2, симметричных относительно точки x=-b/2a. Возможны два варианта:

Если эти корни рациональны, то уравнению x-x1=0 удовлетворяет только один корень, и группа уравнения тривиальна.

Если корни иррациональны, то группа содержит один нетривиальный элемент x1 Диаграмма хассеx2, и изоморфна Z/2Z.

Более сложный пример.

Рассмотрим теперь многочлен. Диаграмма хассе -24

Диаграмма хассе

Существует 4!=24 различных перестановки корней этого уравнения, но не все они являются симметриями. Элементы группы Галуа должны сохранять любые алгебраические уравнения с рациональными коэффициентами.

Одно из таких уравнений — a+d=0. Поскольку a+c≠0, перестановка a→a, b→b, c→d, d→c не входит в группу Галуа.

Кроме того, можно заметить, что (a+b)²=8, но (a+c)²=12. Поэтому перестановка a→a, b→c, c→b, d→d не входит в группу.

Окончательно можно получить, что группа Галуа многочлена состоит из четырёх перестановок:

(a, b, c, d) → (a, b, c, d)

(a, b, c, d) → (c, d, a, b)

(a, b, c, d) → (b, a, d, c)

(a, b, c, d) → (d, c, b, a)

и является четверной группой Клейна, изоморфной (Z/2Z) Диаграмма хассе(Z/2Z).

Формулировка в терминах теории полей

Теория полей даёт более общее определение группы Галуа.

Пусть есть основное поле K и многочлен Р Диаграмма хассеК [x]. Рассмотрим алгебраическое расширение L поля K корнями многочлена. Тогда группа Галуа многочлена это группа автоморфизмов поля L, оставляющих элементы поля K на месте.

В классической теории Галуа в качестве основного поля используется поле рациональных чисел Q.

Разрешимые группы и решение уравнений в радикалах

Решения полиомиального уравнения P(x)=0 выражаются в радикалах тогда и только тогда, когда группа уравнения разрешима.

Для уравнения n-й степени в общем виде группа Галуа изоморфна симметрической группеSn, то есть состоит из всех возможных перестановок. Поскольку группыSnприn>4 не являются разрешимыми, существуют многочлены степениn, корни которых не представимы в виде радикалов — теорема Абеля-Руффини.

Диаграмма Хассе частично упорядоченного множества

Напомним, что ориентированным графом называется пара (V,A). состоящая из множества V и подмножества AÍV9acute;V. Элементы из A называются стрелками, а из V – вершинами. Для стрелки (u,v) вершина u называется началом, а из v – концом.

Пусть (X,£ ) – частично упорядоченное множество. Множество ]x,y[ = называется открытым интервалом с концами x и y .

Определение 1.Диаграммой Хассе называется ориентированный граф (V,A) с V=X и A =<(u,v) : u и ]u,v[ = Æ >.

Пример 1. На рис. 5.1 показана диаграмма Хассе множества P(<0,1,2>) подмножеств множества <0,1,2>. упорядоченное отношением Í.

Диаграмма хассе

Рис. 5.1. Диаграмма Хассе множества подмножеств

Предполагаются, что ребра направлены сверху вниз.

Пример 2. Для целого неотрицательного числа n³0 будем обозначать через [n] множество <0, 1, ∙ ∙ ∙, n>. с отношением 0 < 1< ∙ ∙ ∙ < n. Его диаграммой Хассе будет ориентированный граф, приведенный на рис. 5.2.

Рис. 5.2. Диаграмма Хассе

Частично упорядоченные множества (X, £) и (Y, £) называются изоморфными, если существуют неубывающие отображения f: X®Y и g: Y®X такие, что f(g(y))=y и g(f(x))=x («x9Icirc;X , «y9Icirc;Y ).

В этом случае f называется изоморфизмом. а gобратным отображением для f .

Рассмотрим множество делителей (Dn . | ) натурального числа n³1. упорядоченное отношением делимости a | b Û a – делитель числа b (в этом случае говорят, что aделит b ).

Пример 3. Пусть p и q – различные простые числа, большие единицы. Диаграмма Хассе множества ( Dn . | ) с n=p 2 q показана на рисунке 5.3.

Диаграмма хассе

Рис. 5.3. Диаграмма Хассе множества делителей

В общем случае диаграмма Хассе частично упорядоченного множества (Dn ,| ) состоит из ребер m -мерного параллелепипеда, где m – число различных простых делителей числа n .

Теорема 1. Пусть n>0 – положительное натуральное число, n = — его разложение в произведение попарно не равных простых множителей pi >1. Тогда частично упорядоченное множество ( Dn . | ) будет изоморфно декартовому произведению [a1 ]´ [a2 ]´ ×9times;9times; ´ [am ] линейно упорядоченных множеств.

Доказательство. Каждый делитель числа n= будет равен числу . для некоторых 0£b1 £a1 ,b2 £a2. × × ×,bm £am . Изоморфизм определяется как отображение, ставящее в соответствие числу элемент (b1. b2. × × ×, bm ).

Пусть (X, £ ) – конечное частично упорядоченное множество. Рассмотрим последовательность функций P n. X´X®Z . определенных при n =0 и n =1 по формулам:

Определение 1. Функцией Мебиуса m. X´X®Z называется функция, определенная по формуле

Определение 2. Пусть X=< x1. x2. ×9times;9times;. xn > – конечное частично упорядоченное множество, матрицей смежности называется матрица A. имеющая коэффициенты

Лемма 1. Пусть X=< x1. x2. ×9times;9times;. xn > – конечное частично упорядоченное множество, A – матрица смежности. Тогда матрица M. коэффициенты которой равны значениям m(xi. xj ). будет обратной к матрице A .

Доказательство. Пусть Id – единичная матрица. Положим Q=A-Id. Тогда A=Id+Q. Откуда

A -1 = Id — Q + Q 2 — Q 3 + ×9times;9times; = .

Легко видеть, что коэффициенты матрицы Q k равны P k (xi ,xj ). откуда . в силу . Что и требовалось доказать.

Отсюда получаем m(i,i)=1, m(i,i+1)=-1. Остальные значения функции Мебиуса равны 0.

Теорема 1. Пусть (X, £) – конечное частично упорядоченное множество. Тогда для любых функций f, g. X® R равносильны следующие свойства

Доказательство. Пусть A – матрица смежности частично упорядоченного множества (X, £ ). Тогда выполнение равенства (1) равносильно соотношениям g(xi )=Sj aij f(xj ). Поскольку это равносильно равенству g=Af. эквивалентного равенству f=A -1 g. то получаем, что (1) верно тогда и только тогда, когда верно (2).

Рассматривая частично упорядоченное множество с двойственным отношением порядка, получаем следующую теорему.

Теорема 2. Пусть (X, £) – конечное частично упорядоченное множество. Тогда для любых функций f. g. X® R равносильны следующие свойства

Теорема о произведении

Теорема 1. Пусть (X,£) и (Y,£) – конечные частично упорядоченные множества, mX. X´X® Z и mY. Y´Y® Z – их функции Мебиуса. Тогда, для любых x1. x2 Î X и

Доказательство. Введем дзета-функцию zX. X´X®Z . с помощью формулы

где da,b – символ Кронекера. Вычислим левую часть доказываемой формулы

Получили, что она равна правой части. Что и требовалось доказать.

Пример 1. Вычислим в частично упорядоченном множестве делителей числа n ≥ 1. По доказанной теореме, в случае разложения n = в произведение степеней различных простых чисел pi >1. будет иметь место соотношение . Поскольку

1. Нарисовать диаграмму Хассе множества подмножеств из <0,1,2,3>, упорядоченное отношением включения.

2. Нарисовать диаграмму Хассе множества делителей числа 1000, упорядоченного отношением делимости.

3. Нарисовать диаграмму Хассе множества делителей числа 360, упорядоченного отношением делимости.

4. Нарисовать диаграмму Хассе множества P3 разбиений множества <1,2,3>.

5. Нарисовать диаграмму Хассе множества P4 разбиений множества <1,2,3,4>.

6. Нарисовать диаграмму Хассе произведения P3 ´[1] .

1. Вычислить значения m(0, x) непосредственно из определения функции Мебиуса для следующих частично упорядоченных множеств, заданных с помощью диаграмм Хассе, приведенных на рис. 5.4.

Диаграмма хассе

Рис. 5.4. Примеры диаграмм Хассе

2. Вычислить значения функции Мебиуса для множества P(<1,2, ×9times;9times;. n>). упорядоченного отношением Í .

3. Пусть a – произвольный элемент частично упорядоченного множества. Доказать, что . Найти значения функций Мебиуса для задачи 1 с помощью этой формулы.

Задача 1. Найти множество X. предполагая множества A. B и C известными. Предполагается, что все множества являются подмножествами некоторого универсума U. При каких условиях заданное уравнение обладает по крайней мере одним решением?

Пример решения задачи 1

Задача . Найти множество X. удовлетворяющее уравнению при заданных A, B и C известными. Все множества являются подмножествами некоторого универсума U. При каких условиях заданное уравнение обладает по крайней мере одним решением?

1 шаг. Уравнение равносильно следующему равенству

Пользуясь формулой . приходим к уравнению

С помощью правил де Моргана и соотношения преобразуем это уравнение к следующему

2 шаг. Обозначим операцию объединения Èзнаком сложения, а операцию пересечения Ç — знаком умножения. Получим уравнение

Преобразуем его с помощью закона дистрибутивности (P+Q)R=PR+QR. Приходим к уравнению

Равенства и XX = X. вместе с соотношениями . и приводят к уравнению

3 шаг. Полученное уравнение равносильно системе двух уравнений

Из первого уравнения получаем . а из второго . Эти соотношения приводят к соотношениям включения .

Ответ: . при условии .

Задача 2. Задано отношение R на множестве E = <1, 2, 3, 4, 5> с помощью матрицы rij , где

Представить данное отношение с помощью ориентированного графа, вершинами которого являются элементы множества E. Вершины i и j соединяются стрелкой, если .

Выписать матрицы, соответствующие отношениям

Является ли это отношение R

Задание . Выполнить действия, указанные в условии задачи 2, если отношение R на множестве E = <1, 2, 3, 4, 5> задано с помощью матрицы

имеющей коэффициенты rij = 1 при (i,j)ÎR. и rij = 0 в других случаях.

Представим отношение с помощью ориентированного графа (рис.6.1), с множеством вершин E=<1, 2, 3, 4, 5>. Вершины i и j соединяются стрелкой, если .

Диаграмма хассе

Рис. 6.1. Ориентированный граф, соответствующий отношению R

Ответим на вопросы.

Рефлексивность выполняется, поскольку rii =1 влечет (i,i)ÎR. для всех iÎE .

Иррефлексивность не выполняется, ибо существуют iÎE. для которых (i,i)ÎR .

Симметричность имеет место, ибо для всех i, j ÎE выполнено rij = rji .

Антисимметричность не выполняется, так как (1,3)ÎR и (3,1)ÎR, но 1¹3.

Транзитивность вытекает из R°R Í R.

Отношение не является отношением порядка, ибо оно не антисимметрично.

Отношение является отношением эквивалентности, поскольку оно рефлексивно, симметрично и транзитивно.

Задача 1. Найти количество подмножеств.

1. Сколько подмножеств множества <1, 2. 1000> не содержат чисел ни кратных 6. ни кратных 4?

2. Сколько подмножеств множества <1, 2. 1000> содержат по крайней мере одно число кратное 5 и ни одного – кратного 7 ?

3. Сколько существует подмножеств множества <1, 2, 3. 1000> имеющих по крайней мере одно число, кратное трем или четырем.

4. Сколько подмножеств множества <1, 2. 1000> не содержат ни одного нечетного числа, но имеют по крайней мере одно число кратное 7 ?

5. Сколько подмножеств из <1,2,3, …, 300> состоят из чисел, делящихся на 4, и не содержат ни одного числа, делящегося на 3?

6. Сколько подмножеств множества <1,2,3, …. 1000> содержат по крайней мере одно число кратное 4, но ни одного кратного 7?

7. Сколько подмножеств множества <1, 2. 1000> не содержат чисел ни кратных 6. ни кратных 15?

8. Сколько подмножеств множества <1, 2. 1000> содержат по крайней мере одно число кратное 5 и ни одного – кратного 18 ?

9. Сколько существует подмножеств множества <1, 2, 3. 1000> имеющих по крайней мере одно число, кратное 15 или 21.

10. Сколько подмножеств множества <1, 2. 1000> не содержат ни одного нечетного числа, но имеют по крайней мере одно число кратное 21 ?

11. Сколько подмножеств из <1,2,3, …, 300> состоят из чисел, делящихся на 6, и не содержат ни одного числа, делящегося на 7?

12. Сколько подмножеств множества <1, 2. 1000> не содержат чисел ни кратных 8. ни кратных 6?

13. Сколько подмножеств множества <1, 2. 1000> содержат по крайней мере одно число кратное 12 и ни одного – кратного 13 ?

14. Сколько существует подмножеств множества <1, 2, 3. 1000> имеющих по крайней мере одно число, кратное 6 или 11.

15. Сколько подмножеств множества <1, 2. 1000> не содержат ни одного нечетного числа, но имеют по крайней мере одно число кратное 17 ?

16. Сколько подмножеств из <1,2,3, …, 300> состоят из чисел, делящихся на 7, и не содержат ни одного числа, делящегося на 3?

17. Сколько подмножеств множества <1, 2. 1000> не содержат чисел ни кратных 6. ни кратных 9?

18. Сколько подмножеств множества <1, 2. 1000> содержат по крайней мере одно число кратное 11 и ни одного – кратного 7 ?

19. Сколько существует подмножеств множества <1, 2, 3. 1000> имеющих по крайней мере одно число, кратное 12 или 13.

20. Сколько подмножеств множества <1, 2. 1000> не содержат ни одного нечетного числа, но имеют по крайней мере одно число кратное 23 ?

21. Сколько подмножеств из <1,2,3, …, 1000> состоят из чисел, делящихся на 7, и не содержат ни одного числа, делящегося на 12?

22. Сколько подмножеств множества <1, 2. 1000> не содержат чисел ни кратных 6. ни кратных 10?

23. Сколько подмножеств множества <1, 2. 1000> содержат по крайней мере одно число кратное 12 и ни одного – кратного 7 ?

24. Сколько существует подмножеств множества <1, 2, 3. 1000> имеющих по крайней мере одно число, кратное 11 или четырем.

25. Сколько подмножеств множества <1, 2. 1000> не содержат ни одного нечетного числа, но имеют по крайней мере одно число кратное 11 ?

26. Сколько подмножеств из <1,2,3, …, 300> состоят из чисел, делящихся на 2, и не содержат ни одного числа, делящегося на 3?

27. Сколько подмножеств множества <1, 2. 1000> не содержат чисел ни кратных 10. ни кратных 4?

28. Сколько подмножеств множества <1, 2. 1000> содержат по крайней мере одно число кратное 4 и ни одного – кратного 7 ?

29. Сколько существует подмножеств множества <1, 2, 3. 1000> имеющих по крайней мере одно число, кратное 3 или 8.

30. Сколько подмножеств множества <1, 2. 1000> не содержат ни одного нечетного числа, но имеют по крайней мере одно число кратное 5 ?

Примеры решения задачи 1

Пример 1 . Сколько подмножеств множества A=<1, 2. 1000> не содержат ни чисел кратных 8, ни чисел кратных 12 ?

Решение. Для произвольного действительного числа x обозначим через [x] его целую часть. (Например [2.5]=2, [1/2]=0, [3]=3.) Пусть 12A – подмножество множества A состоящее из чисел кратных 12, A\12A Í A – подмножество чисел не кратных 12. Элементы, не кратные ни 12 ни 8, составляют множество (A\12A)\8A. Нам нужно найти число подмножеств этого множества. Поскольку число элементов этого множества равно

то количество его подмножеств равно

Пример 2 . Сколько подмножеств множества A=<1, 2. 1000> содержат по крайней мере одно число кратное 8 и ни одного – кратного 12 ?

Решение . Пусть 12A – подмножество множества A состоящее из чисел кратных 12, A\12A Í A – подмножество чисел не кратных 12. Элементы, не кратные ни 12 ни 8, составляют множество (A\12A)\8A.

Каждое подмножество из A\12A может быть одного из следующих типов:

1) оно не содержит ни одного элемента кратного 8,

2) оно содержит хотя бы один элемент, кратный 8.

Отсюда количество подмножеств множества A\12A равно сумме количеств подмножеств первого и второго типа. Подмножества первого типа – это в точности подмножества не содержащие ни элементов кратных 12, ни элементов, кратных 8. Нам нужно найти количество подмножеств второго типа.

Следовательно, искомое число равно

Пример 3. Сколько подмножеств множества A=<1, 2. 1000> содержат по крайней мере одно число кратное 8 или 12 ?

Решение. Каждое подмножество множества A обладает одним из следующих взаимоисключающих свойств:

1) оно не содержит ни чисел кратных 8, ни чисел кратных 12,

2) оно содержит по крайней мере одно число, кратное 8 или 12.

Отсюда число подмножеств второго типа (которое как раз нам нужно найти) равно

Задача 2. Найти число разложений заданного числа в сумму слагаемых. Разложения, отличающиеся перестановкой слагаемых, считаются различными.

1. Слагаемые состоят из чисел 3 и 4, сумма равна 50.

2. Слагаемые состоят из чисел 3 и 5, сумма равна 50.

3. Слагаемые состоят из чисел 2 и 5, сумма равна 50.

4. Слагаемые состоят из чисел 3 и 4, сумма равна 52.

5. Слагаемые состоят из чисел 3 и 5, сумма равна 52.

6. Слагаемые состоят из чисел 2 и 5, сумма равна 52.

7. Слагаемые состоят из чисел 3 и 4, сумма равна 54.

8. Слагаемые состоят из чисел 3 и 5, сумма равна 54.

9. Слагаемые состоят из чисел 2 и 5, сумма равна 54.

10. Слагаемые состоят из чисел 3 и 4, сумма равна 51.

11. Слагаемые состоят из чисел 3 и 5, сумма равна 51.

12. Слагаемые состоят из чисел 2 и 5, сумма равна 51.

13. Слагаемые состоят из чисел 3 и 4, сумма равна 49.

14. Слагаемые состоят из чисел 3 и 5, сумма равна 49.

15. Слагаемые состоят из чисел 2 и 5, сумма равна 49.

16. Слагаемые состоят из чисел 3 и 4, сумма равна 55.

17. Слагаемые состоят из чисел 3 и 5, сумма равна 55.

18. Слагаемые состоят из чисел 2 и 5, сумма равна 55.

19. Слагаемые состоят из чисел 3 и 4, сумма равна 46.

20. Слагаемые состоят из чисел 3 и 5, сумма равна 46.

21. Слагаемые состоят из чисел 2 и 5, сумма равна 46.

22. Слагаемые состоят из чисел 3 и 4, сумма равна 48.

23. Слагаемые состоят из чисел 3 и 5, сумма равна 48.

24. Слагаемые состоят из чисел 2 и 5, сумма равна 48.

25. Слагаемые состоят из чисел 3 и 4, сумма равна 53.

26. Слагаемые состоят из чисел 3 и 5, сумма равна 53.

27. Слагаемые состоят из чисел 2 и 5, сумма равна 53.

28. Слагаемые состоят из чисел 3 и 4, сумма равна 47.

29. Слагаемые состоят из чисел 3 и 5, сумма равна 47.

30. Слагаемые состоят из чисел 2 и 5, сумма равна 47.

Пример решения задачи 2

Задание. Найти число разложений заданного числа в сумму слагаемых. Разложения, отличающиеся перестановкой слагаемых, считаются различными. Слагаемые состоят из чисел 3 и 5, сумма равна 40.

Решение. Найдем сначала число слагаемых, равных 3, и число слагаемых, равных 5, дающих в сумме число 40. С этой целью решим уравнение в целых числах

3x + 5y = 40, x³0, y³0.

Первое решение x=0, y=8. Чтобы найти другие решения, будем прибавлять по 5 к числу x и вычитать по 3 из числа y. Получим решения;

Число последовательностей чисел, состоящих из x троек и y пятерок, равно . Отсюда находим числа разложений:

Сумма этих чисел будет искомым числом разложений.

Задача 3. Перечисление функций. Для заданных m и n найти число:

· неубывающих функций <0,1,2, …, m > ® <0, 1, 2, …, n >,

· возрастающих функций <0,1,2, …, m > ® <0, 1, 2, …, n >,

· неубывающих сюръекций <0,1,2, …, n > ® <0, 1, 2, …, m >.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *