Группы. Действие группы на множестве

Определение:

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

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

Определение:

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

Утверждение:

Отношение $\sim$ является отношением эквивалентности.

$\triangleright$

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

$\triangleleft$

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

Определение:

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

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

Определение:

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

Определение:

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

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

Утверждение:

$Orb(x) \cap Orb(y) \neq \varnothing \Rightarrow Orb(x) = Orb(y)$

$\triangleright$

$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)$ Заметим, что $\forall g \in G: g \cdot x \in Orb(y) \Rightarrow Orb(x) \subseteq Orb(y)$ Аналогично доказывается, что $Orb(y) \subseteq Orb(x)$ Таким образом, $Orb(x) = Orb(y)$

$\triangleleft$

Утверждение:

$\sum\limits_{x \in X} |\{g \in G \mid g \cdot x = x \}| = \sum\limits_{g \in G} |St(g)|$

$\triangleright$

$\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)|$

$\triangleleft$

Примеры

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

Ожерелье $x$

Ожерелье $g_1 \cdot x$

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

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

Ожерелье $g_0 \cdot x$

Ожерелье $g_1 \cdot x$

Ожерелье $g_2 \cdot x$

Ожерелье $g_3 \cdot x$

Ожерелье $g_4 \cdot x$

Ожерелье $g_5 \cdot x$

См. также

• Теорема Кэли
• Лемма Бёрнсайда и Теорема Пойа
• Задача об ожерельях

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

• Wikipedia | Действие группы
• Wikipedia | Group action
• Теория групп
• MAXimal::algo::Лемма Бернсайда. Теорема Пойа