5. Группы. Изоморфизм групп. Симметрическая группа перестановок. Подгруппы. Теорема Кэли (1124130)

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

Текст из файла

Лекция 5. Группы. Изоморфизм групп.Симметрическая группа перестановок.Подгруппы. Теорема Кэли.Лектор — Селезнева Светлана Николаевнаselezn@cs.msu.suфакультет ВМК МГУ имени М.В. ЛомоносоваЛекции на сайте http://mk.cs.msu.suГруппыСимметрическая группа перестановокПодгруппыТеорема КэлиАлгебраические структурыПусть S — произвольное множество.Алгебраической операцией ∗ на множестве S называетсяотображение ∗ : S × S → S.Элемент e ∈ S называется нейтральным элементомотносительно операции ∗, если для каждого элемента a ∈ Sверноa ∗ e = e ∗ a = a.Теорема 1. Нейтральный элемент (если он существует)единственен.Доказательство проведем от противного: пусть найдутся дванейтральных элемента e 0 ∈ S и e 00 ∈ S, e 0 6= e 00 .Тогдаe 0 ∗ e 000e = e 0 ∗ e 00 = e 00ГруппыСимметрическая группа перестановокПодгруппыТеорема КэлиАлгебраические структурыДля элемента a ∈ S элемент a0 ∈ S называетсясимметричным, еслиa ∗ a0 = a0 ∗ a = e,где e ∈ S — нейтральный элемент относительно операции ∗.Теорема 2.

Симметричный элемент относительноассоциативной операции (если он существует) единственен.Доказательство проведем от противного: пусть длянекоторого элемента a ∈ S найдутся два симметричныхэлемента a0 ∈ S и a00 ∈ S, a0 6= a00 .Тогдаa0=a0∗e =a0a0 ∗ a ∗ a00∗ (a ∗ a00 ) = (a0 ∗ a) ∗ a00 = e ∗ a00 = a00ГруппыСимметрическая группа перестановокПодгруппыТеорема КэлиГруппыМножество S с одной или несколькими введенными на немоперациями называется алгебраической структурой.Структура G = (S; ∗) (т.е. множество S с введенной на немалгебраической операцией ∗) называется группой, если1) операция ∗ ассоциативна, т.е.

для любых элементовa, b, c ∈ S верно(a ∗ b) ∗ c = a ∗ (b ∗ c);2) cуществует нейтральный элемент относительно операции ∗,т.е. найдется такой элемент e ∈ S, что для каждого элементаa ∈ S верноa ∗ e = e ∗ a = a;3) для каждого элемента a ∈ S найдется симметричный к немуэлемент a0 ∈ S, т.е. такой чтоa ∗ a0 = a0 ∗ a = e.ГруппыСимметрическая группа перестановокПодгруппыТеорема КэлиГруппыЕсли для группы G = (S; ∗) дополнительно выполнено, что4) операция ∗ коммутативна, т.е. для любых элементов a, b ∈ Sверноa ∗ b = b ∗ a,то такая группа называется коммутативной, или абелевой.ГруппыСимметрическая группа перестановокПодгруппыТеорема КэлиГруппыТеорема 3 (правило сокращения).Пусть G = (S; ∗) — группа.

Тогда если для некоторыхэлементов a, b, c ∈ G верноa ∗ b = a ∗ c (или b ∗ a = c ∗ a),то b = c.Доказательство. Пусть элемент a0 ∈ G симметриченотносительно операции ∗ к элементу a ∈ G . Элемент a0 ∈ Gнайдется, т.к. G – группа. Тогдаa∗b =a∗ca0 ∗ a ∗ b = a0 ∗ a ∗ cb = e ∗ b = (a0 ∗ a) ∗ b = (a0 ∗ a) ∗ c = e ∗ c = cГруппыСимметрическая группа перестановокПодгруппыТеорема КэлиПримеры групп1. S = {e}; e ∗ e = e — тривиальная группа.2. S = {e, a}; x ∗ e = e ∗ x = x, где x = e, a;Чему равно a ∗ a =?Пусть a ∗ a = a ? Тогда a ∗ a = a ∗ e, и a = e?! — противоречие.Получаем a ∗ a = e.3. S = {e, a, b};∗eabeeabaabebbeaПеречисленные группы коммутативны.ГруппыСимметрическая группа перестановокПодгруппыТеорема КэлиИзоморфизм группДве группы G = (S; ∗) и G 0 = (S 0 ; ×) называютсяизоморфными, если найдется взаимно однозначноеотображениеϕ : S → S 0,сохраняющее операцию, т.е. для любых элементов a, b ∈ Sверноϕ(a ∗ b) = ϕ(a) × ϕ(b).Перечисленные в п.п.

1–3 группы единственные с точностью доизоморфизма группы соответственно из одного, двух и трехэлементов.ГруппыСимметрическая группа перестановокПодгруппыТеорема КэлиПорядок группыГруппа G = (S; ∗) называется конечной, если в множестве Sконечное число элементов.Если группа G = (S; ∗) конечна, то число элементов вмножестве S называется ее порядком и обозначается |G |.Пусть G = (S; ∗) — группа с нейтральным элементом e.Для элемента a ∈ G наименьшее натуральное число n (еслионо существует), такое что|a ∗ a ∗{z· · · ∗ a} = e,nназывается его порядком.ГруппыСимметрическая группа перестановокПодгруппыТеорема КэлиКонечные коммутативные группыТеорема 4.

Пусть G = (S; ∗) — конечная коммутативнаягруппа, и e ∈ S — ее нейтральный элемент. Тогда для любогоэлемента a ∈ S верно a| ∗ ·{z· · ∗ a} = a|G | = e.|G |Доказательство. Пусть S = {a1 , . . . , an }, и a ∈ S. Рассмотримэлементы группыa ∗ a1 , a ∗ a2 , . . . , a ∗ an .Все эти элементы различны (почему?). И их ровно n. Значит,здесь перечислены все элементы группы.Поэтому, с учетом коммутативности и ассоциативностиоперации ∗, получаем:nYi=1ai =nYi=1(a ∗ ai ) = a|G |nYai .i=1По правилу сокращения (теорема 3) получаем a|G | = e.ГруппыСимметрическая группа перестановокПодгруппыТеорема КэлиМалая теорема ФермаСледствие 4.1 (малая теорема Ферма).

Если p — простоечисло, то для каждого натурального числа a, 1 ≤ a ≤ (p − 1),верно ap−1 = 1(mod p).Доказательство. Пусть S = {1, 2, . . . , (p − 1)} и ·(mod p) —операция умножения по модулю p чисел из S.Несложно проверить, что G = (S, ·(mod p)) — коммутативнаягруппа порядка (p − 1) с нейтральным элементом e = 1.Поэтому, по теореме 4 получаем, что ap−1 = 1(mod p) длякаждого a ∈ S.ГруппыСимметрическая группа перестановокПодгруппыТеорема КэлиТерминологияОбщая∗ операцияe нейтральныйa0 симметричный|a ∗ a ∗{z· · · ∗ a}nАддитивная+ сложение0 ноль−a противоположныйnaМультипликативная· умножение1 единицаa−1 обратныйan степеньГруппыСимметрическая группа перестановокПодгруппыТеорема КэлиПерестановкиПусть N = {1, 2, .

. . , n}, где n ≥ 1.Перестановкой (n элементов) π называется взаимнооднозначное отображениеπ : N → N.Множество всех перестановок n элементов обозначим как Sn .ГруппыСимметрическая группа перестановокПодгруппыТеорема КэлиЗадавать перестановки можно1 2 3 41) таблицей: π =— в каждом столбце элемент2 1 4 3в первой строке перестановкой переводится в элемент вовторой строке;2) строкой: π = [2143] — в строке на i-м месте стоит элементπ(i);3) произведением циклов: π = (12)(34) — каждая скобкаявляется отдельным циклом, в каждой скобке следующийэлемент получен из предыдущего применением перестановки,первый элемент получен из последнего применениемперестановки.ГруппыСимметрическая группа перестановокПодгруппыТеорема КэлиПерестановкиДлиной цикла перестановки называется число элементов внем.Типом перестановки π ∈ Sn называется наборλ(π) = (λ1 (π), .

. . , λn (π)),где λi (π) — число циклов длины i в перестановке π.Заметим, что для любой перестановки π ∈ Sn верноnPi · λi (π) = n, т.к. каждый элемент принадлежит ровноi=1одному циклу.1 2 3 4Например, для перестановки π =ее тип2 1 4 3λ(π) = (0, 2, 0, 0), т.е. в ней два цикла, каждый из которыхсодержит по два элемента.ГруппыСимметрическая группа перестановокПодгруппыТеорема КэлиПерестановкиВведем операцию композиции ◦ на множестве перестановок.Композицией (или произведением) перестановок π и ρназывается такая перестановка π ◦ ρ, что для любого элементаx ∈ N верно(π ◦ ρ)(x) = π(ρ(x)).ГруппыСимметрическая группа перестановокПодгруппыТеорема КэлиПерестановкиТеорема 5.

При n ≥ 3 операция композиции перестановок nэлементов не является коммутативной.Доказательство. Рассмотрим перестановкиπ=1 2 3 4 ...2 1 3 4 ...nnиρ=1 2 3 4 ...2 3 1 4 ...nn.Тогда(π ◦ ρ)(1) = 1,а(ρ ◦ π)(1) = 3.ГруппыСимметрическая группа перестановокПодгруппыГруппа перестановокТеорема 6. Множество перестановок n элементов Sn соперацией композиции ◦ является группой.Доказательство. Проверим свойства группы.1) Ассоциативность операции ◦.Пусть π, ρ, τ ∈ Sn . Тогда для любого элемента x ∈ N((π ◦ ρ) ◦ τ )(x) = (π ◦ ρ)(τ (x)) = π(ρ(τ (x)))и(π ◦ (ρ ◦ τ ))(x) = π((ρ ◦ τ )(x)) = π(ρ(τ (x))).Теорема КэлиГруппыСимметрическая группа перестановокПодгруппыТеорема КэлиГруппа перестановокДоказательство.2) Cуществование нейтрального элемента e.Нейтральным элементом является перестановка1 2 ...

nπe =,1 2 ... nоставляющая каждый элемент на месте.3) Для каждого элемента π существование симметричногоэлемента π 0 .Для перестановки1...i...nπ=π(1) . . . π(i) . . . π(n)обратным (симметричным) элементом является перестановкаπ(1) . . . π(i) . . . π(n)π −1 =.1...i...nГруппыСимметрическая группа перестановокПодгруппыТеорема КэлиГруппа перестановокДоказательство.Следовательно, (Sn , ◦) — группа.По теореме 5 при n ≥ 3 эта группа не коммутативна.Группа всех перестановок n элементов с операцией композиции◦ называется симметрической группой перестановок иобозначается как Sn .Теорема 7. Порядок симметрической группы перестановок Snравен n!, т.е.|Sn | = n!ГруппыСимметрическая группа перестановокПодгруппыТеорема КэлиГруппа S3Рассмотрим симметрическую группу перестановок S3 .π1 = e = [123] = (1)(2)(3) — нейтральный элемент (единицагруппы);π2 = [132] = (1)(23) — элемент 1 остается на месте, элементы2 и 3 меняются местами;π3 = [321] = (13)(2) — элемент 2 остается на месте, элементы1 и 3 меняются местами;π4 = [213] = (12)(3) — элемент 3 остается на месте, элементы1 и 2 меняются местами;π5 = [231] = (123) — элементы 1, 2 и 3 сдвигаются по циклу почасовой стрелке;π6 = [321] = (132) — элементы 1, 2 и 3 сдвигаются по циклупротив часовой стрелки.Порядок группы |S3 | = 3! = 6.ГруппыСимметрическая группа перестановокПодгруппыПодгруппыПусть G = (S; ∗) — группа, и T ⊆ S.Если H = (T ; ∗) является группой, то она называетсяподгруппой группы G = (S; ∗).Если при этом T 6= {e} и T 6= S, то подгруппа называетсясобственной.Теорема КэлиГруппыСимметрическая группа перестановокПодгруппыТеорема КэлиПодгруппыТеорема 8.

Пусть G = (S; ∗) — группа, и T ⊆ S.H = (T ; ∗) является группой тогда и только тогда, когда длялюбых элементов a, b ∈ T верно, что a ∗ b 0 ∈ T .Доказательство.⇐. Проверим свойства группы.1) ассоциативность операции ∗: т.к. G — группа;2) существование нейтрального элемента e: если a ∈ T , тоa ∗ a0 = e ∈ T ;3) для каждого элемента существование симметричногоэлемента: если a ∈ T , то e ∗ a0 = a0 ∈ T ;алгебраичность операции ∗ для множества T : если a, b ∈ T , топо п. 3) b 0 ∈ T , и a ∗ (b 0 )0 = a ∗ b ∈ T .ГруппыСимметрическая группа перестановокПодгруппыТеорема КэлиПодгруппыПримеры подгрупп в группах.1. Если G = (S, ·) — мультипликативная группа, и a ∈ G —элемент порядка n в ней, то множествоT = {a, a2 , . .

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

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

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