Группы. Действие группы на множестве — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 36 промежуточных версий 2 участников)
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 
|id=group_action  
 
|id=group_action  
|definition=Группа <tex>G</tex> '''действует на множестве''' <tex>X</tex>, если задано отображение <tex>G \times X \rightarrow X</tex> (обозначается <tex>g \cdot x</tex>), такое что для любого <tex>x \in X</tex>, а также для любых <tex>g_1, g_2 \in G</tex> оно обладает свойствами:
+
|definition=[[Группа]] <tex>G</tex> '''действует на множестве''' (англ. ''acts on a set'') <tex>X</tex>, если задано отображение <tex>G \times X \rightarrow X</tex> (обозначается <tex>g \cdot x</tex>), такое что для любого <tex>x \in X</tex>, а также для любых <tex>g_1, g_2 \in G</tex> оно обладает свойствами:
# <tex>(g_1 \cdot g_2) \cdot x = g_1 \cdot (g_2 \cdot x)</tex>
+
# <tex>(g_1 \circ g_2) \cdot x = g_1 \cdot (g_2 \cdot x)</tex> (здесь <tex>g_1 \circ g_2</tex> — групповая операция)
# <tex>\varepsilon \cdot x = x</tex>
+
# <tex>e \cdot x = x</tex>
 
}}
 
}}
 
== Примеры ==
 
* TODO
 
  
 
== Эквивалентность по группе ==
 
== Эквивалентность по группе ==
 
{{Определение
 
{{Определение
 
|id=eq  
 
|id=eq  
|definition=Пусть группа <tex>G</tex> действует на множестве <tex>X</tex>. Введем на <tex>X</tex> '''отношение эквивалентности''' <tex>\sim</tex> для <tex>x, y \in X</tex>: <tex>x \sim y</tex>, если <tex>\exists g \in G : x = g \cdot y</tex>.
+
|definition=Пусть группа <tex>G</tex> действует на множестве <tex>X</tex>. Введем на <tex>X</tex> [[отношение эквивалентности]] <tex>\sim</tex> для <tex>x, y \in X</tex>: <tex>x \sim y</tex>, если <tex>\exists g \in G : x = g \cdot y</tex>. Тогда, если <tex>x \sim y</tex>, то говорят, что <tex>x</tex> и <tex>y</tex> '''равны с точностью до группы'''.
 +
}}
 +
 
 +
{{Утверждение
 +
|id=eqcontinue
 +
|statement=Отношение <tex>\sim</tex> является отношением эквивалентности.
 +
|proof=
 +
# Рефлексивность. Для любого <tex>x \in X</tex> верно <tex>x = e \cdot x</tex>, значит <tex>x \sim x</tex>.
 +
# Симметричность. Пусть <tex>x \sim y</tex> для некоторых <tex>x, y \in X</tex>. Тогда существует <tex>g \in G</tex>, такое что <tex>x = g \cdot y</tex>. Пользуясь свойствами групп, получаем следующие равенства: <tex>g^{-1} \cdot x = g^{-1} \cdot (g \cdot y) = (g^{-1} \cdot g) \cdot y = e \cdot y = y</tex>. То есть <tex>g^{-1} \cdot x = y</tex>. Значит, <tex>y \sim x</tex>.
 +
# Транзитивность. Пусть <tex>x \sim y</tex> и <tex>y \sim z</tex> для некоторых <tex>x, y, z \in X</tex>. Тогда существуют такие <tex>g_1, g_2 \in G</tex>, что <tex>x = g_1 \cdot y</tex>, а <tex>y = g_2 \cdot z</tex>. Отсюда следует, что <tex>x = g_1 \cdot (g_2 \cdot z) = (g_1 \cdot g_2) \cdot z</tex>. То есть, <tex>x \sim z</tex>.
 
}}
 
}}
  
Строка 18: Строка 24:
 
{{Определение
 
{{Определение
 
|id=orbit  
 
|id=orbit  
|definition=Пусть группа <tex>G</tex> действует на множество <tex>X</tex>. Тогда '''орбитой''' элемента <tex>x \in X</tex> называется множество: <tex>Orb(x) = \{y \in X \mid \exists g \in G : g \cdot x = y\}</tex>
+
|definition=Пусть группа <tex>G</tex> действует на множество <tex>X</tex>. Тогда '''орбитой''' (англ. ''orbit'') элемента <tex>x \in X</tex> называется множество: <tex>Orb(x) = \{y \in X \mid \exists g \in G : g \cdot x = y\}</tex>. Множество всех орбит обозначается так: <tex>X/G</tex>.
 
}}
 
}}
Иными словами, орбитой элемента множества <tex>X</tex> в группе <tex>G</tex> называется порожденный им класс эквивалентности по отношению <tex>\sim</tex>.
+
Иными словами, орбитой элемента множества <tex>X</tex> в группе <tex>G</tex> называется порожденный им класс эквивалентности по отношению <tex>\sim</tex>. Задача подсчета количества классов эквивалентности является нетривиальной и решается в общем случае при помощи [[Лемма Бёрнсайда и Теорема Пойа|Леммы Бёрнсайда]].
 +
 
 
{{Определение
 
{{Определение
 
|id=point  
 
|id=point  
|definition=Элемент <tex>x \in X</tex> называется '''неподвижной точкой''' элемента <tex>g \in G</tex>, если <tex>g \cdot x = x</tex>
+
|definition=Элемент <tex>x \in X</tex> называется '''неподвижной точкой''' (англ. ''fixed point'') элемента <tex>g \in G</tex>, если <tex>g \cdot x = x</tex>
 
}}
 
}}
 +
 
{{Определение
 
{{Определение
 
|id=stabilizer  
 
|id=stabilizer  
|definition=Пусть группа <tex>G</tex> действует на множество <tex>X</tex>. Тогда '''стабилизатором''' элемента <tex>g \in G</tex> называется множество его неподвижных точек: <tex>St(g) = \{x \in X \mid g \cdot x = x\}</tex>
+
|definition=Пусть группа <tex>G</tex> действует на множество <tex>X</tex>. Тогда '''стабилизатором''' (англ. ''stabilizer'') элемента <tex>g \in G</tex> называется множество его неподвижных точек: <tex>St(g) = \{x \in X \mid g \cdot x = x\}</tex>
 
}}
 
}}
 +
 +
Далее приведены несколько несложных и полезных на практике утверждений.
 +
 +
{{Утверждение
 +
|id=stab
 +
|statement=<tex>Orb(x) \cap Orb(y) \neq \varnothing \Rightarrow Orb(x) = Orb(y)</tex>
 +
|proof=<tex>Orb(x) \cap Orb(y) \neq \varnothing \Rightarrow \exists g_1, g_2 \in G : g_1 \cdot x = g_2 \cdot y \Rightarrow x = g_1^{-1} \cdot (g_2 \cdot y) = (g_1^{-1} \cdot g_2) \cdot y \Rightarrow x \in Orb(y)</tex>
 +
 +
Заметим, что <tex>\forall g \in G: g \cdot x \in Orb(y) \Rightarrow Orb(x) \subseteq Orb(y)</tex>
 +
 +
Аналогично доказывается, что <tex>Orb(y) \subseteq Orb(x)</tex>
 +
 +
Таким образом, <tex>Orb(x) = Orb(y)</tex>
 +
}}
 +
 +
 +
{{Утверждение
 +
|id=stab
 +
|statement=<tex>\sum\limits_{x \in X} |\{g \in G \mid g \cdot x = x \}| = \sum\limits_{g \in G} |St(g)|</tex>
 +
|proof=<tex>\sum\limits_{x \in X} |\{g \in G \mid g \cdot x = x \}| = \sum\limits_{x \in X} \sum\limits_{g \in G} \left\{ \begin{array}{ll} 1 & \textrm{если $g \cdot x = x$}\\ 0 & \textrm{иначе}  \end{array} \right. = \sum\limits_{g \in G} \sum\limits_{x \in X} \left\{ \begin{array}{ll} 1 & \textrm{если $g \cdot x = x$}\\ 0 & \textrm{иначе}  \end{array} \right. = \sum\limits_{g \in G} |St(g)|</tex>
 +
}}
 +
 +
== Примеры ==
 +
В качестве примера рассмотрим ожерелья, состоящие из <tex>6</tex> бусин, которые бывают красного и черного цвета. Таким образом, множество <tex>X</tex> — это множество всевозможных ожерелий из <tex>6</tex> бусин, окрашенных в один из двух цветов.
 +
Теперь введем группу <tex>G</tex>, в которой будет <tex>6</tex> элементов: <tex>g_0, g_1, \dots g_5</tex>, где <tex>g_i</tex> будет означать поворот ожерелья на угол <tex>\dfrac{2\pi i}{6}</tex> против часовой стрелки.
 +
{|
 +
|[[Файл:First.png|thumb|Ожерелье <tex>x</tex>]]
 +
|[[Файл:Second.png|thumb|Ожерелье <tex>g_1 \cdot x</tex>]]
 +
|}
 +
Таким образом, правое ожерелье получено из левого путем действия на него элементом <tex>g_1</tex>. Из этого следуют, что левое и правое ожерелья '''равны с точностью до группы''' <tex>G</tex>, а значит они находятся в одном классе эквивалентности.
 +
 +
Теперь в качестве примера рассмотрим '''орбиту''' левого ожерелья — все элементы множества <tex>X</tex>, полученные из элемента <tex>x</tex> путем поворотов на <tex>6</tex> различных углов.
 +
{|
 +
|[[Файл:First.png|thumb|Ожерелье <tex>g_0 \cdot x</tex>]]
 +
|[[Файл:Second.png|thumb|Ожерелье <tex>g_1 \cdot x</tex>]]
 +
|[[Файл:Third.png|thumb|Ожерелье <tex>g_2 \cdot x</tex>]]
 +
|[[Файл:Fourth.png|thumb|Ожерелье <tex>g_3 \cdot x</tex>]]
 +
|[[Файл:Fifth.png|thumb|Ожерелье <tex>g_4 \cdot x</tex>]]
 +
|[[Файл:Sixth.png|thumb|Ожерелье <tex>g_5 \cdot x</tex>]]
 +
|}
 +
 +
== См. также ==
 +
* [[Теорема Кэли]]
 +
* [[Лемма Бёрнсайда и Теорема Пойа]]
 +
* [[Задача об ожерельях]]
 +
 +
== Источники информации ==
 +
* [https://ru.wikipedia.org/wiki/Действие_группы Wikipedia | Действие группы]
 +
* [https://en.wikipedia.org/wiki/Group_action Wikipedia | Group action]
 +
* [https://mipt.ru/diht/students/courses/group_theory.pdf Теория групп]
 +
* [http://e-maxx.ru/algo/burnside_polya MAXimal::algo::Лемма Бернсайда. Теорема Пойа]
 +
 +
[[Категория: Дискретная математика и алгоритмы]]
 +
[[Категория: Комбинаторика]]
 +
[[Категория: Теория групп]]

Текущая версия на 19:03, 4 сентября 2022

Определение:
Группа [math]G[/math] действует на множестве (англ. acts on a set) [math]X[/math], если задано отображение [math]G \times X \rightarrow X[/math] (обозначается [math]g \cdot x[/math]), такое что для любого [math]x \in X[/math], а также для любых [math]g_1, g_2 \in G[/math] оно обладает свойствами:
  1. [math](g_1 \circ g_2) \cdot x = g_1 \cdot (g_2 \cdot x)[/math] (здесь [math]g_1 \circ g_2[/math] — групповая операция)
  2. [math]e \cdot x = x[/math]


Эквивалентность по группе

Определение:
Пусть группа [math]G[/math] действует на множестве [math]X[/math]. Введем на [math]X[/math] отношение эквивалентности [math]\sim[/math] для [math]x, y \in X[/math]: [math]x \sim y[/math], если [math]\exists g \in G : x = g \cdot y[/math]. Тогда, если [math]x \sim y[/math], то говорят, что [math]x[/math] и [math]y[/math] равны с точностью до группы.


Утверждение:
Отношение [math]\sim[/math] является отношением эквивалентности.
[math]\triangleright[/math]
  1. Рефлексивность. Для любого [math]x \in X[/math] верно [math]x = e \cdot x[/math], значит [math]x \sim x[/math].
  2. Симметричность. Пусть [math]x \sim y[/math] для некоторых [math]x, y \in X[/math]. Тогда существует [math]g \in G[/math], такое что [math]x = g \cdot y[/math]. Пользуясь свойствами групп, получаем следующие равенства: [math]g^{-1} \cdot x = g^{-1} \cdot (g \cdot y) = (g^{-1} \cdot g) \cdot y = e \cdot y = y[/math]. То есть [math]g^{-1} \cdot x = y[/math]. Значит, [math]y \sim x[/math].
  3. Транзитивность. Пусть [math]x \sim y[/math] и [math]y \sim z[/math] для некоторых [math]x, y, z \in X[/math]. Тогда существуют такие [math]g_1, g_2 \in G[/math], что [math]x = g_1 \cdot y[/math], а [math]y = g_2 \cdot z[/math]. Отсюда следует, что [math]x = g_1 \cdot (g_2 \cdot z) = (g_1 \cdot g_2) \cdot z[/math]. То есть, [math]x \sim z[/math].
[math]\triangleleft[/math]

Орбита и стабилизатор

Определение:
Пусть группа [math]G[/math] действует на множество [math]X[/math]. Тогда орбитой (англ. orbit) элемента [math]x \in X[/math] называется множество: [math]Orb(x) = \{y \in X \mid \exists g \in G : g \cdot x = y\}[/math]. Множество всех орбит обозначается так: [math]X/G[/math].

Иными словами, орбитой элемента множества [math]X[/math] в группе [math]G[/math] называется порожденный им класс эквивалентности по отношению [math]\sim[/math]. Задача подсчета количества классов эквивалентности является нетривиальной и решается в общем случае при помощи Леммы Бёрнсайда.


Определение:
Элемент [math]x \in X[/math] называется неподвижной точкой (англ. fixed point) элемента [math]g \in G[/math], если [math]g \cdot x = x[/math]


Определение:
Пусть группа [math]G[/math] действует на множество [math]X[/math]. Тогда стабилизатором (англ. stabilizer) элемента [math]g \in G[/math] называется множество его неподвижных точек: [math]St(g) = \{x \in X \mid g \cdot x = x\}[/math]


Далее приведены несколько несложных и полезных на практике утверждений.

Утверждение:
[math]Orb(x) \cap Orb(y) \neq \varnothing \Rightarrow Orb(x) = Orb(y)[/math]
[math]\triangleright[/math]

[math]Orb(x) \cap Orb(y) \neq \varnothing \Rightarrow \exists g_1, g_2 \in G : g_1 \cdot x = g_2 \cdot y \Rightarrow x = g_1^{-1} \cdot (g_2 \cdot y) = (g_1^{-1} \cdot g_2) \cdot y \Rightarrow x \in Orb(y)[/math]

Заметим, что [math]\forall g \in G: g \cdot x \in Orb(y) \Rightarrow Orb(x) \subseteq Orb(y)[/math]

Аналогично доказывается, что [math]Orb(y) \subseteq Orb(x)[/math]

Таким образом, [math]Orb(x) = Orb(y)[/math]
[math]\triangleleft[/math]


Утверждение:
[math]\sum\limits_{x \in X} |\{g \in G \mid g \cdot x = x \}| = \sum\limits_{g \in G} |St(g)|[/math]
[math]\triangleright[/math]
[math]\sum\limits_{x \in X} |\{g \in G \mid g \cdot x = x \}| = \sum\limits_{x \in X} \sum\limits_{g \in G} \left\{ \begin{array}{ll} 1 & \textrm{если $g \cdot x = x$}\\ 0 & \textrm{иначе} \end{array} \right. = \sum\limits_{g \in G} \sum\limits_{x \in X} \left\{ \begin{array}{ll} 1 & \textrm{если $g \cdot x = x$}\\ 0 & \textrm{иначе} \end{array} \right. = \sum\limits_{g \in G} |St(g)|[/math]
[math]\triangleleft[/math]

Примеры

В качестве примера рассмотрим ожерелья, состоящие из [math]6[/math] бусин, которые бывают красного и черного цвета. Таким образом, множество [math]X[/math] — это множество всевозможных ожерелий из [math]6[/math] бусин, окрашенных в один из двух цветов. Теперь введем группу [math]G[/math], в которой будет [math]6[/math] элементов: [math]g_0, g_1, \dots g_5[/math], где [math]g_i[/math] будет означать поворот ожерелья на угол [math]\dfrac{2\pi i}{6}[/math] против часовой стрелки.

Ожерелье [math]x[/math]
Ожерелье [math]g_1 \cdot x[/math]

Таким образом, правое ожерелье получено из левого путем действия на него элементом [math]g_1[/math]. Из этого следуют, что левое и правое ожерелья равны с точностью до группы [math]G[/math], а значит они находятся в одном классе эквивалентности.

Теперь в качестве примера рассмотрим орбиту левого ожерелья — все элементы множества [math]X[/math], полученные из элемента [math]x[/math] путем поворотов на [math]6[/math] различных углов.

Ожерелье [math]g_0 \cdot x[/math]
Ожерелье [math]g_1 \cdot x[/math]
Ожерелье [math]g_2 \cdot x[/math]
Ожерелье [math]g_3 \cdot x[/math]
Ожерелье [math]g_4 \cdot x[/math]
Ожерелье [math]g_5 \cdot x[/math]

См. также

Источники информации