1632
правки
Изменения
м
rollbackEdits.php mass rollback
|id=group_action
|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 circ g_2) \cdot x = g_1 \cdot (g_2 \cdot x)</tex> (здесь <tex>g_1 \cdot circ g_2</tex> — групповая операция)
# <tex>e \cdot x = x</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
|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>.Задача подсчета количества классов эквивалентности является нетривиальной и решается в общем случае при помощи [[Лемма Бёрнсайда и Теорема Пойа|Леммы Бёрнсайда]].
{{Определение
|id=point
|definition=Элемент <tex>x \in X</tex> называется '''неподвижной точкой''' (англ. ''fixed point'') элемента <tex>g \in G</tex>, если <tex>g \cdot x = x</tex>
}}
{{Определение
|id=stabilizer
|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>|X| = 2^6 = 64</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> против часовой стрелки.
{|
== Источники информации ==
* [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::Лемма Бернсайда. Теорема Пойа]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]
[[Категория: Теория групп]]
