7. Действие группы на множестве. Орбита и стабилизатор элемента, теорема о порядке стабилизатора элемента. Лемма Бернсайда (1124131)

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

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

Лекция 7. Действие группы на множестве.Орбита и стабилизатор элемента, теорема опорядке стабилизатора элемента. ЛеммаБернсайда.Лектор — Селезнева Светлана Николаевнаselezn@cs.msu.suфакультет ВМК МГУ имени М.В. ЛомоносоваЛекции на сайте http://mk.cs.msu.suДействие группыОрбита элементаСтабилизатор элементаЛемма БернсайдаГомоморфизм группЕсли G1 = (S1 ; ∗) и G2 = (S2 ; ×) — группы, то отображениеϕ : S1 → S2 ,называется гомоморфизмом из группы G1 в группу G2 , еслионо сохраняет операцию, т.е. для любых элементов a, b ∈ Sверноϕ(a ∗ b) = ϕ(a) × ϕ(b).В отличие от изоморфизма групп при гомоморфизме нетребуется взаимная однозначность отображения.Действие группыОрбита элементаСтабилизатор элементаЛемма БернсайдаСвойства гомоморфизма группПусть ϕ : S1 → S2 — гомоморфизм из группы G1 = (S1 ; ∗) вгруппу G2 = (S2 ; ×). Тогда1) ϕ(e1 ) = e2 , где e1 , e2 — соответственно нейтральныеэлементы групп G1 , G2 .

В самом деле, если a ∈ S1 , тоϕ(a) = ϕ(a ∗ e1 ) = ϕ(a) × ϕ(e1 ),откуда ϕ(e1 ) = e2 .2) ϕ(a0 ) = ϕ(a)0 , где a0 ∈ S1 , ϕ(a)0 ∈ S2 — соответственносимметричные элементы к элементам a ∈ S1 , ϕ(a) ∈ S2групп G1 , G2 . В самом деле,e2 = ϕ(e1 ) = ϕ(a ∗ a0 ) = ϕ(a) × ϕ(a0 ),откуда ϕ(a0 ) = ϕ(a)0 .Действие группыОрбита элементаСтабилизатор элементаЛемма БернсайдаСимметрическая группа множестваПусть N — конечное множество.Симметрическую группу перестановок элементов множества Nобозначим как S(N).Отметим, что каждый элемент из S(N) является взаимнооднозначным отображением из N на N, т.е. перестановкойэлементов множества N.Действие группыОрбита элементаСтабилизатор элементаЛемма БернсайдаДействие группы на множествеПусть G — конечная группа, а N — конечное множество.Действием группы G на множестве N называетсяпроизвольный гомоморфизм ϕ : G → S(N).При этом действие элемента группы g ∈ G на элементмножества a ∈ N определяется какg (a) = (ϕ(g ))(a).Т.е.

g ∈ G определяет перестановку ϕ(g ) = πg ∈ S(N), и дляa ∈ N верно g (a) = πg (a) ∈ N.Действие группыОрбита элементаСтабилизатор элементаЛемма БернсайдаТождественное действиеПусть G — подгруппа симметрической группы перестановок Sn ,а N = {1, 2, . . . , n} — множество.Пусть ϕ : G → S(N) — тождественное действие, т.е. ϕ(g ) = g ,где g ∈ G .Тогда ϕ определяет действие группы G на множестве N.Как правило, мы будем рассматривать такое действие группына множестве.Действие группыОрбита элементаСтабилизатор элементаЛемма БернсайдаЦикловой индекс группы при действии на множествеПусть конечная группа G действует намножестве N = {1, 2, .

. . , n}.Тогда цикловым индексом группы G при действии намножестве N называется многочлен переменных t1 , . . . , tnZG (t1 , . . . , tn ) =1 X λ1 (πg )λ (π )t1· . . . · tn n g ,|G |g ∈Gгде λ(πg ) = (λ1 (πg ), . . . , λn (πg )) — типперестановки πg ∈ S(N).Если G — подгруппа симметрической группы перестановок Sn ,тождественно действующая на множестве N, то цикловойиндекс при таком действии совпадает с цикловым индексомгруппы G .Действие группыОрбита элементаСтабилизатор элементаЛемма БернсайдаЭквивалентность по группеПусть конечная группа G действует на множествеN = {1, 2, . . . , n}.Определим бинарное отношение RG на множестве N: еслиa, b ∈ N, тоaRG b ⇔ ∃g ∈ G : πg (a) = b.Действие группыОрбита элементаСтабилизатор элементаЛемма БернсайдаЭквивалентность по группеТеорема 1.

Отношение RG является отношениемэквивалентности на множестве N.Доказательство. Свойства отношения эквивалентности.1) Рефлексивность. Для каждого элемента a ∈ N выберемe ∈ G — нейтральный элемент группы G . Тогда πe (a) = a,поэтому aRG a.2) Симметричность. Пусть для элементов a, b ∈ N верно aRG b,т.е. найдется такой элемент g ∈ G , что πg (a) = b. Тогдаπg (a) = b, πg−1 (πg (a)) = πg−1 (b) = πg 0 (b), a = πg 0 (b),где элемент g 0 симметричен к элементу g в группе G . ПоэтомуbRG a.Действие группыОрбита элементаСтабилизатор элементаЛемма БернсайдаЭквивалентность по группеДоказательство.3) Транзитивность. Пусть для элементов a, b, c ∈ N верноaRG b и bRG c, т.е.

найдутся такие элементы g1 ∈ G и g2 ∈ G ,что πg1 (a) = b и πg2 (b) = c. Тогдаπg2 ∗g1 (a) = (πg2 ◦ πg1 )(a) = πg2 (πg1 (a)) = πg2 (b) = c.Т.к. G — группа, g2 ∗ g1 = g ∈ G , поэтому aRG c.Действие группыОрбита элементаСтабилизатор элементаЛемма БернсайдаЭквивалентность по группеПусть конечная группа G действует на множествеN = {1, 2, .

. . , n}.Отношение эквивалентности RG обозначается как ∼G .Если для элементов a, b ∈ N верно a ∼G b, то говорят, чтоэлементы a и b эквивалентны по группе G (илиотносительно группы G ).Действие группыОрбита элементаСтабилизатор элементаЛемма БернсайдаОрбита элементаПусть группа G = {g1 = e, g2 , . . . , gm } действует намножестве N = {1, 2, . . . , n}.Для элемента a ∈ N его орбитой (в группе G ) называетсяпорожденный им класс эквивалентности по отношению ∼G .Обозначение:Oa = {b ∈ N | ∃g ∈ G : πg (a) = b},илиOa = {πg1 (a) = a, πg2 (a), . . .

, πgm (a)}.Действие группыОрбита элементаСтабилизатор элементаЛемма БернсайдаПример: вращение треугольника в плоскостиПример. Пусть группа вращений правильного треугольника вплоскости H = {π1 = e = (1)(2)(3), π2 = (123), π3 = (132)}тождественно действует на множестве N = {1, 2, 3}.Найдем орбиту элемента 1 ∈ N в группе H:O1 = {π1 (1), π2 (1), π3 (1)} = {1, 2, 3}.Другими словами, перестановками группы H элемент 1 можетбыть переведен в любой другой элемент множества N.Т.е. вращениями правильного треугольника в плоскостивершина 1 может перейти в любую другую его вершину.Действие группыОрбита элементаСтабилизатор элементаЛемма БернсайдаСтабилизатор элементаПусть конечная группа G действует намножестве N = {1, 2, .

. . , n}.Для элемента a ∈ N его стабилизатором (в группе G )называется подмножество элементов группы G , оставляющихего на месте.Обозначение:Ga = {g ∈ G | πg (a) = a}.Действие группыОрбита элементаСтабилизатор элементаЛемма БернсайдаПример: симметрическая группа перестановок S3Пример. Пусть N = {1, 2, 3}. Рассмотрим тождественноедействие симметрической группы перестановокS3 = {π1 = e = (1)(2)(3), π2 = (123), π3 = (132),π4 = (1)(23), π5 = (13)(2), π6 = (12)(3)},на множестве N.Найдем стабилизатор элемента 1 ∈ N в группе S3 :G1 = {π1 = (1)(2)(3), π4 (1) = (1)(23)}.Несложно увидеть, что G1 — подгруппа группы S3 .Оказывается, что стабилизатор элемента в группе всегдаявляется подгруппой этой группы перестановок.Действие группыОрбита элементаСтабилизатор элементаЛемма БернсайдаСтабилизатор элементаТеорема 2. Пусть конечная группа G действует на конечноммножестве N. Тогда для каждого элемента a ∈ N егостабилизатор Ga является подгруппой группы G .Доказательство проведем по критерию подгруппы.Пусть g1 , g2 ∈ Ga .

Рассмотрим элемент g1 ∗ g20 . Тогда(a)) = πg1 (a) = a.πg1 ∗g20 (a) = (πg1 ◦πg20 )(a) = πg1 (πg20 (a)) = πg1 (πg−12Т.е. g1 ∗ g20 ∈ Ga .Действие группыОрбита элементаСтабилизатор элементаЛемма БернсайдаИндекс стабилизатора в группеТеорема 3. Пусть конечная группа G действует на конечноммножестве N.

Тогда для каждого элемента a ∈ N индекс егостабилизатора Ga в группе G равен мощности его орбиты Oa ,т.е. (G : Ga ) = |Oa |.Действие группыОрбита элементаСтабилизатор элементаЛемма БернсайдаИндекс стабилизатора в группеДоказательство. Рассмотрим левостороннее разложениегруппы G по подгруппе Ga , определяющей отношениеэквивалентности ∼Ga . Пусть g1 , g2 ∈ G .1) Если они из одного смежного класса, т.е. g1 ∼Ga g2 , тонайдется такой элемент h ∈ Ga , что g2 = g1 ∗ h. Тогдаπg2 (a) = πg1 ∗h (a) = (πg1 ◦ πh )(a) = πg1 (πh (a)) = πg1 (a).2) Пусть они из разных смежных классов.

Предположим, чтоπg2 (a) = πg1 (a). Тогда◦ πg2 )(a) = a,πg10 ∗g2 (a) = (πg10 ◦ πg2 )(a) = (πg−11где элемент g10 симметричен к элементу g1 в группе G . Отсюдаg10 ∗ g2 ∈ Ga , и по второму определению отношенияэквивалентности по подгруппе g1 ∼Ga g2 , или они лежат водном смежном классе — противоречие. Т.е. πg1 (a) 6= πg2 (a).Действие группыОрбита элементаСтабилизатор элементаЛемма БернсайдаИндекс стабилизатора в группеДоказательство. Следовательно,πg1 (a) = πg2 (a) ⇔ g1 ∼Ga g2 ⇔ g1 , g2 из одного смежного класса.Т.е. (G : Ga ) = |Oa |.Действие группыОрбита элементаСтабилизатор элементаЛемма БернсайдаПример: индекс подгруппы G1 в группе S3Пример. Мы нашли стабилизатор элемента 1 ∈ N в группе S3 :G1 = {π1 = (1)(2)(3), π4 (1) = (1)(23)}.Найдем разложение симметрической группы перестановок S3на смежные классы по подгруппе G1 :Класс(1)(2)(3)G1(123)G1(132)G1π(1)(2)(3), (1)(23)(123), (12)(3)(132), (13)(2)Несложно увидеть, что (S3 : G1 ) = |O1 |.π(1)123Действие группыОрбита элементаСтабилизатор элементаЛемма БернсайдаЛемма БернсайдаТеорема 4 (лемма Бернсайда).

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

Тип файла PDF

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

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

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