65
правок
Изменения
Нет описания правки
__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>f_{g^{-1}}</tex> {{---}} обратная перестановка, где <tex>g^{-1}</tex> {{---}} обратный элемент <tex>g</tex> в группе инъекция.# Мощность <tex>G</tex>Если <tex>e</tex> {{---}} нейтральный (относительно бинарной операции <tex>*конечна </tex>) элемент в группе, то <tex>f_e</tex> {{---}} тождественная перестановка.Таким образом множество всех функций <tex>K = \{Rightarrow f_g : g \in G\}</tex> {{---}} подгруппа симметрической группыбиективно, и является перестановкой.
Пусть <tex>\circ</tex> {{- --}} композиция двух перестановок.Рассмотрим множество Если <tex>Kf_g</tex>. По доказанному выше{{---}} перестановка, оно является подгруппой симметрической группы. Осталось доказатьто <tex>f_{g^{-1}}</tex> {{---}} обратная перестановка, что где <tex>Gg^{-1}</tex> и {{---}} обратный элемент <tex>Kg</tex> изоморфны. Для этого рассмотрим функцию , так как <tex>T : G (f_{g^{-1}} \rightarrow K,\, Tcirc f_g) (x) = f_{g^{-1}}(f_g (x) ) =g^{-1} \circ g \circ x = f_xx </tex>. ЗаметимЕсли <tex>e</tex> {{---}} нейтральный элемент в группе, чтото <tex>f_e</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>
==См. также==
* [[Умножение перестановок, обратная перестановка, группа перестановок]]
* [[Действие перестановки на набор из элементов, представление в виде циклов]]
* [[Таблица инверсий]]
* [[Матричное представление перестановок]]
==Источникиинформации==* [http://en.wikipedia.org/wiki/Cayley's_theorem Wikipedia {{---}} Cayley's theorem - Wikipedia, the free encyclopedia]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]
[[Категория: Свойства комбинаторных объектов]]