Изменения

|author=Артур Кэли(''Arthur Cayley'')|about=о вложении любой конечной группы в группу перестановок

Любая [[Конечная группа| конечная группа ]] <tex>G</tex> порядка <tex>n</tex> изоморфна некоторой подгруппе [[Умножение перестановок, обратная перестановка, группа перестановок|группы перестановок ]] (подгруппе симметрической группегруппы <tex>S_n</tex>).

<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>a, b\in G</tex> таких, что <tex>a \neq b</tex> верно, что <tex>g \circ a \neq g \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_1) = f_g(x_2x) \Rightarrow x_1 = f_{g^{-1}*}(f_g(x_1x)) = g^{-1}*f_g(x_2) \circ g \circ x = x_2x </tex>.Если <tex>e</tex> {{---}} нейтральный элемент в группе, то есть <tex>f_gf_e</tex> {{- --}} тождественная перестановка.

Пусть <tex>\circ</tex> - композиция двух Докажем,что множество всех перестановок.Рассмотрим множество <tex>K = \{f_g : g \in G\}</tex>. По доказанному выше, оно является подгруппой {{---}} подгруппа симметрической группы. Осталось доказать, что <tex>G</tex> и <tex>K</tex> изоморфны. Для этого рассмотрим функцию <tex>T : G \rightarrow K,\, T(x) = f_xS_n</tex>. Заметим, что

*Пусть <tex>g_i,g_j\in G</tex>.Рассмотрим перестановку <tex>T(g)f_{g_i} \circ T(hf_{g_j}) = T(g*hx)</tex>.Так как <tex>G</tex> {{---}} группа, то для любого <tex>x\in G</tex> верно

Действительно, для всех <tex>x \in G \quad(f_g f_{g_i} \circ f_hf_{g_j})(x) = f_gf_{g_i}(f_h(x)) = f_g(h * x) = g*f_{g_j}(h*x) = (g*h)*x = f_{(g*h)g_i}(x)</tex>, а тогда <tex>T(g)\circ T(h) = f_g {g_j} \circ f_h x = f_{g_i \circ g_j}(g*hx)} = Tf_c(g*hx)</tex>.,

*Так как <tex>TG</tex> {{--- инъекция}} группа, потому что то <tex>g*x g_i \circ g_j = g'*x g_k\in G</tex> и <tex>f_{g_i \Rightarrow g circ g_j}= g'f_{g_k}</tex>, откуда <tex>f_{g_i} \circ f_{g_j}\in K</tex> (после домножения обеих частей на . Значит, <tex>K</tex>x^{{---1}} подгруппа группы <tex>S_n</tex>).*Сюрьективность Осталось доказать, что <tex>G</tex> и <tex>K</tex> изоморфны. Для этого рассмотрим отображение <tex>\varphi : G \rightarrow K\</tex>, которое переводит элемент <tex>Tg\in G</tex> очевидна из определения в элемент <tex>\varphi(g)=f_{g^\prime}\in K</tex>, где <tex>{g^\prime}</tex> симметричен элементу <tex>g</tex> в группе <tex>G</tex>.

То есть Заметим, что #Отображение <tex>T\varphi </tex> - биекциявзаимно однозначно.#Для любых <tex>g_i, а значит изоморфизм g_j\in G</tex>Gверно <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>K\varphi</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>K</tex>: <tex> \varphi(0)=\begin{bmatrix} 0 & 1 & 2 \\ 0 & 1 & 2 \end{bmatrix} </tex> <tex> \varphi(1)=\begin{bmatrix} 0 & 1 & 2 \\ 1 & 2 & 0 \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] [[Категория: Дискретная математика и алгоритмы]][[Категория: Комбинаторика]][[Категория: Свойства комбинаторных объектов]]