__TOC__
Теорема Кэли позволяет найти для любой конечной группы с определённой бинарной операцией изоморфную ей подгруппу группы всех перестановок.
==Теорема Кэли==
{{
Теорема
|about=о вложении любой конечной группы в группу перестановок
|statement=
Любая [[Конечная группа| конечная группа ]] <tex>G</tex> порядка <tex>n</tex> изоморфна некоторой подгруппе [[Умножение перестановок, обратная перестановка, группа перестановок|группы перестановок ]] (подгруппе симметрической группегруппы <tex>S_n</tex>).
|proof=
<tex>S_n</tex>(симметрическая группа) {{---}} множество перестановок с <tex>n</tex> элементами с операцией <tex>\circ</tex>. Пусть <tex>*\circ</tex> {{---}} бинарная операция в конечной группе <tex>G=\{g_1, g_2,\ldots,g_n\}</tex>.Рассмотрим некоторый элемент Для каждого элемента <tex>g \in G</tex> и функцию построим соответствующую перестановку <tex>f_g \in S_n: G </tex><tex> f_g=\begin{bmatrix} g_1 & g_2 & \ldots & g_n \\ f_g(g_1) & f_g(g_2) & \ldots & f_g(g_n) \rightarrow Gend{bmatrix}, </tex> где <tex>f_g(x) = g*\circ x</tex>.
<tex>f_g</tex> {{---}} перестановка, так как
# Для любых <tex>xa, yb\in G</tex> таких, что <tex>x a \neq yb</tex> верно, что <tex>g*x \circ a \neq g*y\circ b</tex> <tex>\Rightarrow f_g</tex> {{---}} инъекция.
# Мощность <tex>G</tex> {{---}} конечна <tex>\Rightarrow f_g</tex> {{---}} биективно, и является перестановкой.
Пусть <tex>\circ</tex> {{---}} композиция двух перестановок.
Если <tex>f_g</tex> {{---}} перестановка, то <tex>f_{g^{-1}}</tex> {{---}} обратная перестановка, где <tex>g^{-1}</tex> {{---}} обратный элемент <tex>g</tex>, так как <tex> (f_{g^{-1}} \circ f_g) (x) = f_{g^{-1}}(f_g (x)) =g^{-1} * \circ g * \circ x = x </tex>.
Если <tex>e</tex> {{---}} нейтральный элемент в группе, то <tex>f_e</tex> {{---}} тождественная перестановка.
Таким образом Докажем,что множество всех функций перестановок <tex>K = \{f_g : g \in G\}</tex> {{---}} подгруппа симметрической группы<tex>S_n</tex>. Пусть <tex>g_i, так g_j\in G</tex>.Рассмотрим перестановку <tex>(f_{g_i} \circ f_{g_j})(x)</tex>. Так как композиция двух функций из <tex>KG</tex> не выводит из {{---}} группа, то для любого <tex>Kx\in G</tex>, потому что верно <tex>(f_a f_{g_i} \circ f_bf_{g_j})(x) = f_af_{g_i}(f_bf_{g_j}(x)) = a * b * {g_i} \circ {g_j} \circ x = f_{a*bg_i \circ g_j}(x) = f_c(x) </tex>, где Так как <tex>c G</tex> {{---}} группа, то <tex>g_i \circ g_j = a * b g_k\in G</tex> и <tex>f_{g_i \circ g_j}=f_{g_k}</tex>, значит откуда <tex>f_a f_{g_i} \circ f_b f_{g_j}\in K</tex>. Значит, <tex>K</tex> {{---}} подгруппа группы <tex>S_n</tex>.
Рассмотрим множество <tex>K</tex>. По доказанному выше, оно является подгруппой симметрической группы. Осталось доказать, что <tex>G</tex> и <tex>K</tex> изоморфны. Для этого рассмотрим функцию отображение <tex>T \varphi : G \rightarrow K,\, T(x) = f_x</tex>. Заметим, что для всех которое переводит элемент <tex>x g\in G </tex> в элемент <tex>\quad(f_g \circ f_h)(x) = f_g(f_h(x)) = g*(h*x) = varphi(g*h)*x = f_{(g*h)^\prime}(x)\in K</tex>, то есть где <tex>T({g)^\circ T(h) = T(prime}</tex> симметричен элементу <tex>g*h)</tex> в группе <tex>G</tex>.
Значит Заметим, что #Отображение <tex>T\varphi </tex> взаимно однозначно.#Для любых <tex>g_i,g_j\in G</tex> верно <tex>\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)</tex>, то есть отображение <tex>\varphi</tex> сохраняет операцию.
#<tex>T</tex> {{---}} инъекцияЗначит, потому что оно является изоморфизмом групп <tex>f_g(x) = f_{g'}(x) \Rightarrow g = f_g(x)*x^{-1} = f_{g'}(x)*x^{-1} = g'G</tex>.#Сюрьективность <tex>T</tex> очевидна из определения и <tex>K</tex>.}}
То есть <tex>T</tex> {{---}} гомоморфизм и биекция, а значит изоморфизм <tex>G</tex> и <tex>K</tex> установлен.
}}
==Примеры==
Тривиальным примером и иллюстрацией для данной теоремы является группа Рассмотрим конечную группу <tex> G= \mathbb Z_3=\{0, 1, 2\}</tex> с операцией <tex>\circ </tex> {{---}} группа остатков сложения по модулю <tex>3</tex>. Найдём подгруппу <tex>K</tex>, изоморфную группе <tex>\mathbb{Z}_3</tex>, то есть найдём отображение <tex>\mathbb{Z}_3</tex> в <tex>K</tex>. Пусть <tex>\ \varphi :\mathbb{Z}_3\rightarrow K</tex> <tex>K = \{\varphi(g) : g \in \mathbb{Z}_3\}</tex> и <tex> \varphi(g)=\begin{bmatrix} 0 & 1 & 2 \\ f_g(0) & f_g(1) & f_g(2) \end{bmatrix},</tex> где <tex> f_g(x) = g \circ x</tex>. При этом <tex>K\subseteq S_3</tex>, где <tex>S_3</tex> {{---}} группа всех перестановок с <tex>3</tex> элементами с операцией сложения<tex>\circ</tex>. То есть <tex> \varphi(g)=\begin{bmatrix} 0 & 1 & 2 \\ g\circ 0 & g\circ 1 & g\circ 2 \end{bmatrix}</tex>.
Пусть Тогда находим три перестановки, составляющие группу <tex>\ \varphi :\mathbb{Z}_3\rightarrow S_3K</tex>:
<tex> \varphi(0)=\begin{bmatrix} 0 & 1 & 2 \\ 0 & 1 & 2 \end{bmatrix} </tex>
<tex> \varphi(2)=\begin{bmatrix} 0 & 1 & 2 \\ 2 & 0 & 1 \end{bmatrix} </tex>
Таким образом, мы нашли подгруппу <tex>K</tex> группы перестановок <tex>S_3</tex>, изоморфную конечной группе <tex>\mathbb{Z}_3</tex>.
==См. также==
* [[Умножение перестановок, обратная перестановка, группа перестановок]]
* [[Действие перестановки на набор из элементов, представление в виде циклов]]
* [[Таблица инверсий]]
* [[Матричное представление перестановок]]
==Источникиинформации==* [http://en.wikipedia.org/wiki/Cayley's_theorem Wikipedia {{---}} Cayley's theorem - Wikipedia, the free encyclopedia]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]
[[Категория: Свойства комбинаторных объектов]]
