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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
Строка 7: Строка 7:
  
 
|proof=
 
|proof=
Пусть <tex>*</tex> {{---}} бинарная операция в группе <tex>G</tex>.
+
Пусть <tex>\circ</tex> {{---}} бинарная операция в группе <tex>G</tex>.
Рассмотрим некоторый элемент <tex>g \in G</tex> и функцию <tex>f_g : G \rightarrow G, f_g(x) = g*x</tex>.
+
Рассмотрим некоторый элемент <tex>g \in G</tex> и функцию <tex>f_g : G \rightarrow G, 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>x, y</tex> таких, что <tex>x \neq y</tex> верно, что <tex>g \circ x \neq g \circ y</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>K</tex> не выводит из <tex>K</tex>, потому что <tex>(f_a \circ f_b)(x) = f_a(f_b(x)) = a \circ b \circ x = f_{a \circ b}(x) = f_c(x) </tex>, где <tex>c = a \circ b </tex>, значит <tex>f_a \circ f_b \in K</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>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 \circ h)}(x)</tex>, то есть <tex>T(g)\circ T(h) = T(g \circ h)</tex>.  
  
 
Значит <tex>T</tex> {{---}} гомоморфизм.
 
Значит <tex>T</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>T</tex> {{---}} инъекция, потому что <tex>f_g(x) = f_{g'}(x) \Rightarrow g = f_g(x) \circ x^{-1} = f_{g'}(x) \circ x^{-1} = g'</tex>.
 
#Сюрьективность <tex>T</tex> очевидна из определения <tex>K</tex>.
 
#Сюрьективность <tex>T</tex> очевидна из определения <tex>K</tex>.
  

Версия 02:13, 7 января 2017

Теорема (Кэли(Cayley), о вложении любой конечной группы в группу перестановок):
Любая конечная группа [math]G[/math] изоморфна некоторой подгруппе группы перестановок (симметрической группе).
Доказательство:
[math]\triangleright[/math]

Пусть [math]\circ[/math] — бинарная операция в группе [math]G[/math]. Рассмотрим некоторый элемент [math]g \in G[/math] и функцию [math]f_g : G \rightarrow G, f_g(x) = g \circ x[/math]. [math]f_g[/math] — перестановка, так как

  1. Для любых [math]x, y[/math] таких, что [math]x \neq y[/math] верно, что [math]g \circ x \neq g \circ y[/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]K[/math] не выводит из [math]K[/math], потому что [math](f_a \circ f_b)(x) = f_a(f_b(x)) = a \circ b \circ x = f_{a \circ b}(x) = f_c(x) [/math], где [math]c = a \circ b [/math], значит [math]f_a \circ f_b \in K[/math]

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

Значит [math]T[/math] — гомоморфизм.

  1. [math]T[/math] — инъекция, потому что [math]f_g(x) = f_{g'}(x) \Rightarrow g = f_g(x) \circ x^{-1} = f_{g'}(x) \circ x^{-1} = g'[/math].
  2. Сюрьективность [math]T[/math] очевидна из определения [math]K[/math].
То есть [math]T[/math] — гомоморфизм и биекция, а значит изоморфизм [math]G[/math] и [math]K[/math] установлен.
[math]\triangleleft[/math]

Примеры

Примером и иллюстрацией для данной теоремы является группа [math] \mathbb Z_3[/math] — группа остатков по модулю 3, с операцией сложения.

Пусть [math]\ \varphi :\mathbb{Z}_3\rightarrow S_3[/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]


Источники