AA3-0 (PDF-лекции от Гурова)

ПРИКЛАДНАЯ АЛГЕБРАПРИКЛАДНАЯ АЛГЕБРАЛекции для групп 320–328 (III-й поток)5-й семестрЛектор — Гуров Сергей Исаевичассистент — Кропотов Дмитрий АлександровичМГУ имени М.В. ЛомоносоваФакультет Вычислительной математики и кибернетикиКафедра Математических методов прогнозированиякомн. 530, 537, 682e-mail: sgur@cs.msu.ruПРИКЛАДНАЯ АЛГЕБРАЛитератураВоронин В.П.

Дополнительные главы дискретнойматематики. — М.: ф-т ВМК МГУ, 2002.http://padabum.com/d.php?id=10281Гуров С.И. Булевы алгебры, упорядоченные множества,решетки: Определения, свойства, примеры. — М.: Либроком,2013.Журавлёв Ю.И., Флёров Ю.А., Вялый М.Н. Дискретныйанализ. Основы высшей алгебры. — М.: МЗ Пресс, 2007.Лидл Р., Нидеррайтер Г. Конечные поля: В 2-х т. — М.: Мир,1988.Мак-Вильямс Ф. Дж., Слоэн Н. Дж. А. Теория кодов,исправляющих ошибки.

— М.: Связь, 1979.Нефедов В.Н., Осипова В.А. Курс дискретной математики. —М.: Изд-во МАИ, 1992.Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. — М.:Мир, 1976.ПРИКЛАДНАЯ АЛГЕБРА. Тема 0: Группы, кольца, поля (напоминание)Тема 0Группы, кольца, поля(напоминание)3 / 24ПРИКЛАДНАЯ АЛГЕБРА. Тема 0: Группы, кольца, поля (напоминание)ГруппыРазделы1Группы2Кольца и поля4 / 24ПРИКЛАДНАЯ АЛГЕБРА. Тема 0: Группы, кольца, поля (напоминание)ГруппыГруппы: определение и нотацияОпределениеГруппой G называется пара h G, ∗ i, где G — непустоемножество (носитель), а ∗ — бинарная операция на нём такая,что для любых x, y, z ∈ G выполняются следующие законы илиаксиомы группы:G1: (x ∗ y) ∗ z = x ∗ (y ∗ z) — ассоциативность;G2: ∃e ∀x (e ∗ x = x ∗ e = x) — существование единицы;G3: ∀x ∃!y (y ∗ x = x ∗ y = e) — существование обратногоэлемента к x, символически y = x−1 .G0: x ∗ y ∈ G — устойчивость носителя.Если |G| = n, то группа называется конечной и n — еёпорядок.При мультипликативной записи x · y (или xy) единичныйэлемент называют единицей и обозначают e или 1.5 / 24ПРИКЛАДНАЯ АЛГЕБРА.

Тема 0: Группы, кольца, поля (напоминание)ГруппыГруппы: определение и нотация...Группы со свойством a ∗ b = b ∗ a называютсякоммутативными или абелевыми, а для их обозначения обычноиспользуют аддитивная запись x + y, а единичный элементназывают нулем (0), а обратный к x — противоположным (−x).В конечной группе операцию ∗ задают таблицей умножения(таблицей Кэли).Пример (Таблица умножения группы Клейна V4 )∗eabceeabcaaecbbbceaccbae(и часто c обозначают ab)6 / 24ПРИКЛАДНАЯ АЛГЕБРА. Тема 0: Группы, кольца, поля (напоминание)ГруппыГруппы: примеры1. Числовые группы: Z, Q, R,относительно сложения.C — абелевы группыМножества ненулевых элементовотносительно умножения.Q, R, C — абелевы группы2. Бинарные наборы: элементы B n относительно ⊕.3.

Симметрическая группа Sn : все перестановки n-элементногомножества относительно композиции перестановок; |Sn | = n!.Симметрическая группа не абелева.Группа всех преобразований правильноготреугольника в себя — симметрическая группаS3 = h t, r i == { e, (ABC), (ACB), (A)(BC), (B)(AC), (C)(AB) }.7 / 24ПРИКЛАДНАЯ АЛГЕБРА. Тема 0: Группы, кольца, поля (напоминание)Группы8 / 24Группы: примеры...4. Циклические группы: в них есть порождающий элементгруппы — такой, что каждый элемент группы может бытьполучен многократным применением к нему групповойоперации.Обозначения:defa0 = e,defan = a.

. · a} ,| · .{zn разdefna = a. . + a} ,| + .{zn рази справедливы все обычные свойства степени (a−n = (a−1 )n ).C — циклическая группа:∃ c ∀ x ∃ k ck = x ,CCNdefhci = C.Порядок элемента: deg a = arg min { an = e }.nПРИКЛАДНАЯ АЛГЕБРА. Тема 0: Группы, кольца, поля (напоминание)ГруппыИзоморфизм группОпределениеПусть G = h G, ∗ i и G 0 = h G 0 , ◦ i — группы. Отображениеϕ : G → G 0 называется изоморфизмом, если оно1взаимно однозначно;сохраняет операцию: ∀ a, b ∈ G ( ϕ(a ∗ b) = ϕ(a) ◦ ϕ(b) ),а такие группы — изоморфными, символически G ∼= G 0.2Свойства изоморфизма ϕ: ϕ(e) = e0 (сохранение единицы),ϕ(a−1 ) = ϕ(a)−1 (образ обратного элемента — обратный к егообразу)...Теорема (Кэли)Любая конечная группа порядка n изоморфна некоторойподгруппе симметрической группы Sn .9 / 24ПРИКЛАДНАЯ АЛГЕБРА. Тема 0: Группы, кольца, поля (напоминание)ГруппыПодгруппы и смежные классыЕсли G = h G, ∗ i — группа, а H — подмножество G,устойчивое относительно групповой операции ∗,то H = h H, ∗ i — подгруппа G, символически H 6 G.H 6 G, x ∈ G ⇒ xH = { xh | h ∈ H } и Hx = { hx | h ∈ H }— соответственно левый и правый смежные классы поподгруппе H (с представителем x).В абелевой группе всегда xH = Hx.УтверждениеСмежные классы с разными представителями либо непересекаются, либо совпадают.10 / 24ПРИКЛАДНАЯ АЛГЕБРА.

Тема 0: Группы, кольца, поля (напоминание)ГруппыЦиклические группы: свойстваВсе циклические группы абелевы.Каждая конечная циклическая группа изоморфна группеZn = h {0, 1, . . . , n − 1}, +mod n i,а каждая бесконечная — изоморфна h Z, + i.Каждая подгруппа циклической группы циклична.В применении к единственной бесконечной циклическойгруппе Z это даёт, что любая нетривиальная подгруппа Hгруппы Z имеет вид H = { mn | n ∈ Z } = mZ , где m —наименьшее положительное число из H.Например: H = { .

. . − 6, −3, 0, 3, 6, . . . } = 3Z.У циклической группы порядка n существует ровно ϕ(n)порождающих элементов, где ϕ(·) — функция Эйлера.Если p — простое число, то любая группа порядка pциклическая и единственна с точностью до изоморфизма.11 / 24ПРИКЛАДНАЯ АЛГЕБРА. Тема 0: Группы, кольца, поля (напоминание)Группы12 / 24Индекс подгруппы. Нормальные подгруппыКоличество смежных классов группы G по подгруппе Hназывается индексом подгруппы, символически (G : H).ПримерРассмотрим подгруппу H = h(12)i = { e, (12) } группыS3 = { e, (123), (132), (1)(23), (2)(13), (3)(12) }.Разбиение G на левые смежные классы по подгруппе H:H =e(3)(12)(123)(1)(23)(132)(2)(13)(G : H) = 3 =Подгруппа H группы G называется нормальной, если∀ g ∈ G (gH = Hg), символически H G.Группы можно факторизовать («делить») по нормальнымподгруппам.6.2ПРИКЛАДНАЯ АЛГЕБРА.

Тема 0: Группы, кольца, поля (напоминание)Группы13 / 24Теорема Лагранжа и следствия из неёТеоремаЕсли H — подгруппа конечной группы G, то|G| = (G : H) · |H|.Следствия1Порядок любого элемента есть делитель порядка группы.2Группа G простого порядка p:циклическая и любой её отличный от единицы элемент —порождающий;т.е. всего p − 1 порождающих элементов;defне имеет нетривиальных подгрупп ( E = {e} и G ).Замечание. Обращение теоремы Лагранжа неверно.ПРИКЛАДНАЯ АЛГЕБРА.

Тема 0: Группы, кольца, поля (напоминание)ГруппыПорядок элемента конечной группыЛемма (о порядке элемента конечной группы)Пусть m — максимальный порядок элемента в конечнойабелевой группе G = h G, ◦, e i.Тогда порядок любого элемента x ∈ G делит m.14 / 24ПРИКЛАДНАЯ АЛГЕБРА. Тема 0: Группы, кольца, поля (напоминание)ГруппыПорядок элемента конечной группыЛемма (о порядке элемента конечной группы)Пусть m — максимальный порядок элемента в конечнойабелевой группе G = h G, ◦, e i.Тогда порядок любого элемента x ∈ G делит m.ДоказательствоГруппа G однозначно разлагается в прямую сумму циклическихгрупп, порядки которых являются степенями простых чисел.Для каждого простого делителя pi порядка группы найдемциклическую группу максимального порядка pki .Обозначим произведение чисел pki через M .

Для любогоx ∈ G выполняется xM = e, т.е. порядок x делит M .Но произведение всех выбранных циклических групп имеетпорядок M . Поэтому m = M .14 / 24ПРИКЛАДНАЯ АЛГЕБРА. Тема 0: Группы, кольца, поля (напоминание)Кольца и поляРазделы1Группы2Кольца и поля15 / 24ПРИКЛАДНАЯ АЛГЕБРА. Тема 0: Группы, кольца, поля (напоминание)Кольца и поляКольца: определениеОпределениеКольцом R называется тройка h R, +, · i, где R — непустоемножество (носитель), а + (сложение) и · (умножение) —бинарные операции на нём такие, что для любых x, y, z ∈ Rвыполняются следующие законы или аксиомы кольца:R1: относительно сложения R — коммутативная группа(аддитивная группа кольца);R2: (x · y) · z = x · (y · z) — ассоциативность умножения;R3: x · (y + z) = x · y + x · z и (y + z) · x = y · x + z · x —дистрибутивность умножения относительно сложенияслева и справа.Если в R имеется единичный элемент для умножения (1), токольцо называется кольцом с единицей (унитальным).Если x · y = y · x, то кольцо называется коммутативным.16 / 24ПРИКЛАДНАЯ АЛГЕБРА.

Тема 0: Группы, кольца, поля (напоминание)Кольца и поляКольца: основные свойства, примерыОбратного элемента по умножению в кольце может и небыть.В любом кольце a · 0 = 0.Если ∀ r1 , r2 ( r1 · r2 = 0 ⇒ (r1 = 0) ∨ (r2 = 0) ) — то этокольцо без делителей нуля.Ассоциативно-коммутативное кольцо без делителей нуля —целостное кольцо.Примеры колец:1. Классический пример — множество целых чисел Z соперациями сложения и умножения (целостносное унитальноекольцо). Обратные элементы по умножению есть только для±1.2. Zn = h {0, 1, .