Теорема Кэли

НЕТ ВОЙНЕ

24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. Антивоенный комитет России

Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.

meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки.

Теорема Кэли позволяет найти для любой конечной группы с определённой бинарной операцией изоморфную ей подгруппу группы всех перестановок.

Теорема Кэли

Теорема (Кэли(Cayley), о вложении любой конечной группы в группу перестановок):

Любая конечная группа [math]G[/math] порядка [math]n[/math] изоморфна некоторой подгруппе группы перестановок (подгруппе симметрической группы [math]S_n[/math]).

Доказательство:

[math]\triangleright[/math]

[math]S_n[/math](симметрическая группа) — множество перестановок с [math]n[/math] элементами с операцией [math]\circ[/math]. Пусть [math]\circ[/math] — бинарная операция в конечной группе [math]G=\{g_1, g_2,\ldots,g_n\}[/math]. Для каждого элемента [math]g\in G[/math] построим соответствующую перестановку [math]f_g\in S_n:[/math] [math] f_g=\begin{bmatrix} g_1 & g_2 & \ldots & g_n \\ f_g(g_1) & f_g(g_2) & \ldots & f_g(g_n) \end{bmatrix},[/math] где [math]f_g(x) = g \circ x[/math]. [math]f_g[/math] — перестановка, так как Для любых [math]a, b\in G[/math] таких, что [math]a \neq b[/math] верно, что [math]g \circ a \neq g \circ b[/math] [math]\Rightarrow f_g[/math] — инъекция. Мощность [math]G[/math] — конечна [math]\Rightarrow f_g[/math] — биективно, и является перестановкой. Пусть [math]\circ[/math] — композиция двух перестановок. Если [math]f_g[/math] — перестановка, то [math]f_{g^{-1}}[/math] — обратная перестановка, где [math]g^{-1}[/math] — обратный элемент [math]g[/math], так как [math] (f_{g^{-1}} \circ f_g) (x) = f_{g^{-1}}(f_g (x)) =g^{-1} \circ g \circ x = x [/math]. Если [math]e[/math] — нейтральный элемент в группе, то [math]f_e[/math] — тождественная перестановка. Докажем,что множество всех перестановок [math]K = \{f_g : g \in G\}[/math] — подгруппа симметрической группы [math]S_n[/math]. Пусть [math]g_i,g_j\in G[/math].Рассмотрим перестановку [math](f_{g_i} \circ f_{g_j})(x)[/math]. Так как [math]G[/math] — группа, то для любого [math]x\in G[/math] верно [math](f_{g_i} \circ f_{g_j})(x) = f_{g_i}(f_{g_j}(x)) = {g_i} \circ {g_j} \circ x = f_{g_i \circ g_j}(x) = f_c(x) [/math], Так как [math]G[/math] — группа, то [math]g_i \circ g_j =g_k\in G[/math] и [math]f_{g_i \circ g_j}=f_{g_k}[/math], откуда [math]f_{g_i} \circ f_{g_j}\in K[/math]. Значит, [math]K[/math] — подгруппа группы [math]S_n[/math]. Осталось доказать, что [math]G[/math] и [math]K[/math] изоморфны. Для этого рассмотрим отображение [math]\varphi : G \rightarrow K\[/math], которое переводит элемент [math]g\in G[/math] в элемент [math]\varphi(g)=f_{g^\prime}\in K[/math], где [math]{g^\prime}[/math] симметричен элементу [math]g[/math] в группе [math]G[/math]. Заметим, что Отображение [math]\varphi [/math] взаимно однозначно. Для любых [math]g_i,g_j\in G[/math] верно [math]\varphi (g_i \circ g_j) = f_{(g_i \circ g_j)^\prime} = f_{{g}^\prime_i \circ {g}^\prime_j}=f_{{g}^\prime_i}\circ f_{{g}^\prime_j}=\varphi (g_i)\circ \varphi (g_j)[/math], то есть отображение [math]\varphi[/math] сохраняет операцию. Значит, оно является изоморфизмом групп [math]G[/math] и [math]K[/math].

[math]\triangleleft[/math]

Примеры

Рассмотрим конечную группу [math]G= \mathbb Z_3=\{0, 1, 2\}[/math] с операцией [math]\circ [/math] — сложения по модулю [math]3[/math]. Найдём подгруппу [math]K[/math], изоморфную группе [math]\mathbb{Z}_3[/math], то есть найдём отображение [math]\mathbb{Z}_3[/math] в [math]K[/math].

Пусть [math]\ \varphi :\mathbb{Z}_3\rightarrow K[/math]

[math]K = \{\varphi(g) : g \in \mathbb{Z}_3\}[/math] и

[math] \varphi(g)=\begin{bmatrix} 0 & 1 & 2 \\ f_g(0) & f_g(1) & f_g(2) \end{bmatrix},[/math] где [math] f_g(x) = g \circ x[/math].

При этом [math]K\subseteq S_3[/math], где [math]S_3[/math] — группа всех перестановок с [math]3[/math] элементами с операцией [math]\circ[/math].

То есть

[math] \varphi(g)=\begin{bmatrix} 0 & 1 & 2 \\ g\circ 0 & g\circ 1 & g\circ 2 \end{bmatrix}[/math].

Тогда находим три перестановки, составляющие группу [math]K[/math]:

[math] \varphi(0)=\begin{bmatrix} 0 & 1 & 2 \\ 0 & 1 & 2 \end{bmatrix} [/math]

[math] \varphi(1)=\begin{bmatrix} 0 & 1 & 2 \\ 1 & 2 & 0 \end{bmatrix} [/math]

[math] \varphi(2)=\begin{bmatrix} 0 & 1 & 2 \\ 2 & 0 & 1 \end{bmatrix} [/math]

Таким образом, мы нашли подгруппу [math]K[/math] группы перестановок [math]S_3[/math], изоморфную конечной группе [math]\mathbb{Z}_3[/math].

См. также

• Умножение перестановок, обратная перестановка, группа перестановок
• Действие перестановки на набор из элементов, представление в виде циклов
• Таблица инверсий
• Матричное представление перестановок

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

• Wikipedia — Cayley's theorem