Теорема Кэли — различия между версиями
TTFH (обсуждение | вклад) |
м (rollbackEdits.php mass rollback) |
||
(не показаны 32 промежуточные версии 6 участников) | |||
Строка 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>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:</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> | + | # Для любых <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>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} | + | Пусть <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>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>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> | + | Так как <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>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> | + | Заметим, что |
− | + | #Отображение <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>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>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> | ||
Строка 41: | Строка 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 | + | * [http://en.wikipedia.org/wiki/Cayley's_theorem Wikipedia {{---}} Cayley's theorem] |
[[Категория: Дискретная математика и алгоритмы]] | [[Категория: Дискретная математика и алгоритмы]] | ||
[[Категория: Комбинаторика]] | [[Категория: Комбинаторика]] | ||
+ | [[Категория: Свойства комбинаторных объектов]] |
Текущая версия на 19:35, 4 сентября 2022
Содержание
Теорема Кэли позволяет найти для любой конечной группы с определённой бинарной операцией изоморфную ей подгруппу группы всех перестановок.
Теорема Кэли
Теорема (Кэли(Cayley), о вложении любой конечной группы в группу перестановок): |
Любая конечная группа порядка изоморфна некоторой подгруппе группы перестановок (подгруппе симметрической группы ). |
Доказательство: |
(симметрическая группа) — множество перестановок с элементами с операцией . Пусть — бинарная операция в конечной группе . Для каждого элемента построим соответствующую перестановку где .— перестановка, так как
Пусть — композиция двух перестановок. Если — перестановка, то — обратная перестановка, где — обратный элемент , так как . Если — нейтральный элемент в группе, то — тождественная перестановка.Докажем,что множество всех перестановок — подгруппа симметрической группы .Пусть .Рассмотрим перестановку . Так как — группа, то для любого верно, Так как — группа, то и , откуда . Значит, — подгруппа группы .Осталось доказать, что и изоморфны. Для этого рассмотрим отображение , которое переводит элемент в элемент , где симметричен элементу в группе .Заметим, что
|
Примеры
Рассмотрим конечную группу
с операцией — сложения по модулю . Найдём подгруппу , изоморфную группе , то есть найдём отображение в .Пусть
и
где .
При этом
, где — группа всех перестановок с элементами с операцией .То есть
.
Тогда находим три перестановки, составляющие группу
:
Таким образом, мы нашли подгруппу
группы перестановок , изоморфную конечной группе .См. также
- Умножение перестановок, обратная перестановка, группа перестановок
- Действие перестановки на набор из элементов, представление в виде циклов
- Таблица инверсий
- Матричное представление перестановок