Теорема Кэли — различия между версиями

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

Текущая версия на 19:35, 4 сентября 2022

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

Теорема Кэли

Теорема (Кэли(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] — перестановка, так как

  1. Для любых [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] — инъекция.
  2. Мощность [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].

Заметим, что

  1. Отображение [math]\varphi [/math] взаимно однозначно.
  2. Для любых [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].

См. также

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