대칭군(Symmetric group)

정의1

치환, 순열(permutation) :

공집합이 아닌 임의의 집합 $A$에서 $A$로의 전단사 함수 $\phi : A \to A$를 $A$의 치환 또는 순열로 정의한다.

집합 $A$의 모든 치환들의 집합족을 $S_A$로 표기한다.

항등치환 :

모든 $a \in A$에 대해 $\iota(a) = a$인 치환 $\iota \in S_A$를 항등치환으로 정의한다.

대칭군 :

아래 정리로 $(S_A,\circ,\iota)$는 군이므로 $(S_A,\circ,\iota)$를 $A$의 대칭군으로 정의한다.

치환군, 순열군(permutation group) :

대칭군 $(S_A,\circ,\iota)$의 임의의 부분군을 $A$의 치환군 또는 순열군으로 정의한다.

 

 

 

정리1

공집합이 아닌 임의의 집합 $A$의 모든 치환들의 집합족 $S_A$는 합성연산 $\circ$에 대해 닫혀있다.

증명

합성함수 정리로 임의의 $\sigma, \tau \in S_A$의 합성함수 $\sigma \circ \tau : A \to A$는 전단사이므로 $\sigma \circ \tau \in S_A$이다.

 

 

 

정리2

공집합이 아닌 임의의 집합 $A$에 대해 $($$S_A$$,$ $\circ$$,\iota)$는 군이다.

증명

$\circ$에 대한 결합법칙

이항연산 정리로 $S_A$는 $\circ$에 대한 결합법칙이 성립한다.

$\circ$에 대한 항등원

모든 $a \in A$에 대해 $\iota(a) = a$인 함수 $\iota : A \to A$는 전단사이므로 $\iota \in S_A$이고

임의의 $\phi \in S_A$에 대해 $(\iota \circ \phi)(a) = \iota(\phi(a)) = \phi(a) = \phi(\iota(a)) = (\phi \circ \iota)(a) $이므로 

$\iota \circ \phi = \phi = \phi \circ \iota$가 되어 $\iota$는 $\circ$에 대한 항등원이다.

$\circ$에 대한 역원

임의의 $\phi \in S_A$는 전단사이므로

역함수 $\phi^{-1} : A \to A$이 존재하고 역함수 정리로 $\phi^{-1}$은 전단사이므로 $\phi^{-1} \in S_A$이다.

또 모든 $a \in A$에 대해 $(\phi \circ \phi^{-1})(a) = \phi(\phi^{-1}(a)) = a = \phi^{-1}(\phi(a)) = (\phi^{-1}\circ \phi)(a)$이므로

$\phi^{-1} \circ \phi = \iota = \phi \circ \phi^{-1}$이 되어 $\phi^{-1}$은 $\circ$에 대한 $\phi$의 역원이다.

따라서 $(S_A,\circ,\iota)$는 군이다.

 

 

 

정리3

공집합이 아닌 임의의 집합 $A,B$에 대해 $A$에서 $B$로의 전단사 함수가 존재하면

$A,B$의 대칭군 $($$S_A$$,$ $\circ$$,\iota_A)$와 $(S_B,\circ,\iota_B)$는 동형이다.

증명

전단사 함수 $f : A \to B$는 역함수 $f^{-1} : B \to A$이 존재하고 역함수 정리로 $f^{-1}$도 전단사이다.

모든 $\sigma_A \in S_A$에 대해

합성함수 정리로 $( f\circ \sigma_A) \circ f^{-1} = f\circ (\sigma_A \circ f^{-1})$이고

합성함수 정리로 $\sigma_B = f\circ \sigma_A \circ f^{-1} \in S_B$는 전단사이므로

$\phi(\sigma_A) = f\circ \sigma_A \circ f^{-1}$인 함수 $\phi : S_A \to S_B$를 정의하면

모든 $\sigma_B \in S_B$에 대해 합성함수 정리로 $\sigma_A = f^{-1} \circ \sigma_B \circ f \in S_A$가 존재하므로 $\phi$는 전사이고

모든 $\sigma_{A,1},\sigma_{A,2} \in S_A$에 대해 $\phi(\sigma_{A,1}) = \phi(\sigma_{A,2})$이면

$ f\circ \sigma_{A,1} \circ f^{-1} = f\circ \sigma_{A_2} \circ f^{-1}$이므로

$f^{-1}\circ f\circ \sigma_{A,1} \circ f^{-1} \circ f = f^{-1} \circ f\circ \sigma_{A_2} \circ f^{-1} \circ f$가 되어

모든 $a \in A$에 대해 $ (f^{-1}\circ f\circ \sigma_{A,1} \circ f^{-1} \circ f)(a) = (f^{-1} \circ f\circ \sigma_{A,2} \circ f^{-1} \circ f)(a)$이고

$\begin{align*} (f^{-1}\circ f\circ \sigma_{A,1} \circ f^{-1} \circ f)(a)  = (f^{-1}\circ f \circ \sigma_{A,1})(f^{-1}(f(a)))  = (f^{-1} \circ f \circ \sigma_{A,1})(a)  = f^{-1}(f(\sigma_{A,1}(a)))  = \sigma_{A,1}(a) \text{ 이고} \end{align*}$

비슷하게 $\sigma_{A,1}(a) = (f^{-1}\circ f\circ \sigma_{A,1} \circ f^{-1} \circ f)(a) = (f^{-1} \circ f\circ \sigma_{A_2} \circ f^{-1} \circ f)(a) = \sigma_{A,2}(a)$이므로

$\sigma_{A,1} = \sigma_{A,2}$이고 $\phi$는 단사이다.

또 모든 $a \in A$와 모든 $\sigma_A, \tau_A \in S_A$에 대해

$\phi(\sigma_A) = f\circ \sigma_A \circ f^{-1} =\sigma_B$와 $\phi(\tau_A) = f\circ \tau_A \circ f^{-1} =\tau_B$로 두면

$f((\sigma_A \circ \tau_A)(a)) = f(\sigma_A( \tau_A(a) )) = \sigma_B(f(\tau_A(a))) = \sigma_B(\tau_B(f(a))) = (\sigma_B \circ \tau_B)(f(a))$이므로

$f \circ \sigma_A \circ \tau_A = \sigma_B \circ \tau_B \circ f$가 되어

$\phi(\sigma_A \circ \tau_A) = f \circ \sigma_A \circ \tau_A \circ f^{-1} = \sigma_B \circ \tau_B \circ f \circ f^{-1} = \sigma_B \circ \tau_B = \phi(\sigma_A) \circ \phi(\tau_A)$이다.

따라서 $\phi$가 전단사이고 준동형사상 성질을 만족하므로 $(S_A,\circ,\iota_A)$와 $(S_B,\circ,\iota_B)$는 동형이다.

 

 

 

정리4

$n \in \mathbb{Z}^+$개의 원소를 갖는 임의의 유한집합 $A,B$의 대칭군 $($$S_A$$,$ $\circ$$,\iota_A)$와 $(S_B,\circ,\iota_B)$는 동형이다.

증명

$A,B$가 $n \in \mathbb{Z}^+$개의 원소를 가지므로

$\mathbb{Z}_n = \{ 0,1, 2,\cdots , n-1\}$에 대해 전단사 함수 $f : \mathbb{Z}_n \to A$와 $g : \mathbb{Z}_n \to B$가 존재하고

역함수 $f^{-1} : A \to \mathbb{Z}_n$과 $g^{-1} : B \to \mathbb{Z}_n$이 존재하여 역함수 정리로 $f^{-1}$와 $g^{-1}$도 전단사이다.

따라서 합성함수 정리로 $g \circ f^{-1} :A \to B $와 $f \circ g^{-1} : B \to A$는 전단사이므로

위 정리로 $(S_A,\circ,\iota_A)$와 $(S_B,\circ,\iota_B)$는 동형이다.

 

 

 

정의2

$n \in \mathbb{Z}^+$개의 원소를 갖는 유한집합 $\mathbb{N}_n = \{ 1,2,\cdots , n \}$의 모든 치환들의 집합족을 $S_n$으로 표기하고

$\mathbb{N}_n$의 대칭군 $(S_n,\circ,\iota_{n})$을 $n$문자 대칭군(symmetric group on $n$ letters)으로 정의한다.

 

 

 

정리5

$n \in \mathbb{Z}^+$개의 원소를 갖는 임의의 유한집합 $A$에 대해 $S_A$는 $n!$개의 원소를 갖는 유한집합이다.

증명

$S_n$이 $n!$개의 원소를 갖음을 $n \in \mathbb{Z}^+$에 대한 귀납법으로 보인다.

$n = 1$일때

$\mathbb{N}_1 = \{ 1\}$이므로 $\mathbb{N}_1$에서 $\mathbb{N}_1$로의 전단사 함수는 $1 = 1!$개만 존재한다.

모든 $k \in \mathbb{Z}^+$에 대해 $S_k$가 $k!$개의 원소를 갖는다고 가정할때

집합 $\mathbb{N}_{k+1} = \{ 1,2,\cdots,k , k+1 \}$에서 임의의 $i \in \mathbb{N}_{k+1}$를 제외한

집합 $A_i = \mathbb{N}_{k+1} \setminus \{ i \} =  \{ 1,2,\cdots, k , k+1 \} \setminus \{ i \}$는 유한집합 정리로 $k+1 -1 = k$개의 원소를 가지므로 

$A_i$의 대칭군 $(S_{A_i},\circ,\iota_{A_i})$는 위 정리로 $($$S_k$$,\circ,\iota_k)$와 동형이다.

$S_{A_i}$에서 $S_k$로의 전단사 함수 $f : S_{A_i} \to S_k$가 존재하고 귀납가정으로 $S_k$가 $k!$개의 원소를 가지므로

모든 $i \in \mathbb{N}_{k+1}$에 대해 유한집합 정리로 $S_{A_i}$는 $k!$개의 원소를 갖는다.

 

$i \in \mathbb{N}_{k+1}$인 모든 $\sigma_{i} \in S_{A_i}$와 모든 $j \in \mathbb{N}_{k+1} \setminus \{ i \}$에 대해

$(\sigma_i(j) + (k+1 - i)) \bmod{(k+1)}$인 함수가 $\mathbb{N}_{k+1} \setminus \{ i \}$에서 $\mathbb{N}_k$로의 전단사임을 보인다.

$\sigma_i : \mathbb{N}_{k+1} \setminus \{ i\} \to \mathbb{N}_{k+1}\setminus \{ i \} $는

모든 $j \in \mathbb{N}_{k+1} \setminus \{  i\}$에 대해 $\sigma_i(j) \ne i$이므로 $1\le \sigma_i(j) < i \le k+1$ 또는 $1\le  i < \sigma_i(j) \le k+1$이다.

$1\le \sigma_i(j) < i \le k+1$이면

$1\le \sigma_i(j) \le i -1$로 $1-i \le \sigma_i(j) - i \le -1$이고 $i \le k+1$로 $-k \le 1-i $이므로

$ -k \le 1 - i \le \sigma_i(j) - i \le -1$이고 $1 \le (k+1 - i) + 1 \le \sigma_i(j) + (k + 1 -i) \le k$가 되어

모듈러 연산의 정의로 $(\sigma_i(j) + (k+1 - i)) \bmod{(k+1)} = \sigma_i(j) + (k+1 - i)$이다.

$1\le  i < \sigma_i(j) \le k+1$이면

$i + 1 \le \sigma_i(j) \le k+1$이고 $1\le i$로 $1-i \le 0$이고 $k +1-i \le k$이므로 $1 \le \sigma_i(j) - i \le k + 1 -i \le k$가 되어

모듈러 연산 정리로 $(\sigma_i(j) + (k+1 - i)) \bmod{(k+1)} = (\sigma_i(j) - i) \bmod{ (k+1)} = \sigma_i(j) - i$이다.

모듈러 연산의 정의로 어떤 $q \in \mathbb{Z}$에 대해 

$\sigma_i(j) + (k+1 - i) - q\cdot (k+1) =  (\sigma_i(j) + (k+1-i) ) \bmod {(k+1)}$이므로

모든 $j_1,j_2 \in \mathbb{N}_{k+1}\setminus \{ i \}$에 대해

$(\sigma_i(j_1) + (k+1-i) ) \bmod {(k+1)} = (\sigma_i(j_2) + (k+1 -i) ) \bmod{(k+1)}$이면

어떤 $q_1, q_2 \in \mathbb{Z}$에 대해 $\sigma_i(j_1) + (k+1 - i) - q_1\cdot (k+1) = \sigma_i(j_2) + (k+1 - i) - q_2\cdot (k+1) $이고

$\sigma_i(j_1) - \sigma_i(j_2) = (q_1 - q_2)\cdot (k+1)$인데 $ 1 \le \sigma_i(j_1) \le k+1$이고 $1 \le \sigma_i(j_2) \le k+1$이므로

$-k \le \sigma_i(j_1) - \sigma_i(j_2) = (q_1 - q_2)\cdot (k+1) \le k$는 $q_1 - q_2 =0$으로 $\sigma_i(j_1) = \sigma_i(j_2)$가 되어

$\sigma_i$가 단사임에 따라 $j_1 = j_2$이고 $(\sigma_i(j) + (k+1-i) ) \bmod {(k+1)}$도 단사이다.

또 $\sigma_i(j) \in \{ 1,2,\cdots , i-1 \}$이면

$(\sigma_i(j) + (k+1 - i)) \bmod{(k+1)}  = (\sigma_i(j) + (k+1 -i))\in \{ (k +1 - i) +1 , (k+1 - i) +2,\cdots ,  (k+1 - i) + i-1=k \}\text{ 이고}$

$\sigma_i(j) \in \{ i + 1, i+ 2,\cdots ,  i + (k + 1 - i) = k +1 \}$이면

$(\sigma_i(j) + (k+1 - i)) \bmod{(k+1)} = (\sigma_i(j) - i) \in \{ 1, 2, \cdots, k + 1 - i\}$이므로

전사가 아니면 단사임에 모순이 되어

$(\sigma_i(j) + (k+1 - i)) \bmod{(k+1)}$는 $\mathbb{N}_{k+1} \setminus \{ i \}$에서 $\mathbb{N}_k$로의 전단사이다.

 

$i \in \mathbb{N}_{k+1}$인 모든 $\sigma_{i} \in S_{A_i}$과 모든 $j \in \mathbb{N}_{k+1}$에 대해

$\overline{\sigma}_{i}(j) = \begin{cases} (\sigma_i(j) + (k+1 -i)) \bmod{(k+1)} , &  j \ne i \text{ 일때} \\ i + (k + 1 - i) = k+1, & j = i \text{ 일때} \end{cases}$인 함수 $\overline{\sigma}_i : \mathbb{N}_{k+1} \to \mathbb{N}_{k+1}$는 전단사이다.

임의의 $\sigma_{i} , \tau_i \in S_{A_i}$가 $\sigma_i \ne \tau_i$이면

$\sigma_i(j_0) \ne \tau_i(j_0)$인 $j_0 \in \mathbb{N}_{k+1} \setminus \{ i \}$이 존재하므로 일반성을 잃지 않고 $\sigma_i(j_0) > \tau_i(j_0)$이라 가정할때

모듈러 연산의 정의로

$\sigma_i(j_0) + (k+1 - i) - q_1\cdot (k+1) =  (\sigma_i(j_0) + (k+1-i) ) \bmod {(k+1)}$인 $q_1 \in \mathbb{Z}$이 존재하고

$\tau_i(j_0) + (k+1 - i) - q_2\cdot (k+1) =  (\tau_i(j_0) + (k+1-i) ) \bmod {(k+1)}$인 $q_2 \in \mathbb{Z}$가 존재하여

$(\sigma_i(j_0) + (k+1-i))\bmod{(k+1)} = (\tau_i(j_0) + (k+1 - i)) \bmod{(k+1)}$이라 가정하면

$\sigma_i(j_0) - q_1\cdot (k+1) = \tau_i(j_0) - q_2\cdot (k+1)$이고 $\sigma_i(j_0) - \tau_i(j_0) = (q_1-q_2)\cdot (k+1) > 0$이다.

$k +1 > 0$이므로 $q_1 - q_2 \ge 1$이고 $\sigma_i(j_0) - \tau_i(j_0) = (q_1-q_2)\cdot (k+1) \ge k+1$인데

$ 1 \le \sigma_i(j_0) \le k+1$이고 $1 \le \tau_i(j_0) \le k+1$이므로

$ -k \le \sigma_i(j_0) - \tau_i(j_0) = (q_1-q_2)\cdot (k+1) \le k$가 되어 모순이다.

따라서 $\sigma_i(j_0) \ne \tau_i(j_0)$인 $j_0 \in \mathbb{N}_{k+1} \setminus \{ i \}$이 존재하면

$(\sigma_i(j_0) + (k+1-i))\bmod{(k+1)} \ne (\tau_i(j_0) + (k+1 - i)) \bmod{(k+1)}$이므로 $\sigma_i \ne \tau_i$이면 $\overline{\sigma}_i \ne \overline{\tau}_i$이다.

또 $a \ne b$인 모든 $a ,b \in \mathbb{N}_{k+1}$와 모든 $\sigma_{a} \in S_{A_a}$와 $\sigma_{b} \in S_{A_b}$에 대해 

$\overline{\sigma}_a , \overline{\sigma}_b \in S_{k+1}$는 전단사이므로 $\overline{\sigma}_a(b) \ne \overline{\sigma}_a(a) = k+1 = \overline{\sigma}_b(b)$로 $\overline{\sigma}_a \ne \overline{\sigma}_b $가 되어

$k +1$개의 $i \in \mathbb{N}_{k+1}$에 대해

$k!$개의 $A_i = \mathbb{N}_{k+1} \setminus \{ i \}$의 치환으로 만든 $\mathbb{N}_{k+1}$의 치환들이 모두 다르고 $S_{k+1}$에 속하므로

$S_{k+1}$은 $k! \cdot (k +1) = (k+1)!$개 이상의 원소를 갖는다.

 

$S_{k+1}$이 정확히 $(k+1)!$개의 원소를 갖는다는 것을 보인다.

임의의 $\mathbb{N}_{k+1}$의 치환 $\sigma \in S_{k+1}$에 대해

$\sigma : \mathbb{N}_{k+1} \to \mathbb{N}_{k+1}$은 전단사이므로 $\sigma(i) = k+1$인 $i \in \mathbb{N}_{k+1}$가 존재하고

$(\sigma(j) + i ) \bmod{(k+1)} = i$인 $j \in \mathbb{N}_{k+1} \setminus \{ i \}$가 존재한다고 가정하면

모듈러 연산의 정의로 어떤 $q \in \mathbb{Z}$에 대해 $\sigma(j) +i = q\cdot (k+1) + i$이고 $\sigma(j)  = q\cdot (k+1) $인데

$1 \le \sigma(j)  \le k $이므로 모순이 되어 모든 $j \in \mathbb{N}_{k+1} \setminus \{ i \}$에 대해 $(\sigma(j) + i ) \bmod{(k+1)} \ne i$이다.

$\sigma_{i}(j) = \begin{cases} (\sigma(j) +i) \bmod{(k+1)} , &  (\sigma(j) +i) \bmod{(k+1)} \ne 0 \text{ 일때} \\ k+1, & (\sigma(j) +i) \bmod{(k+1)} = 0 \text{ 일때} \end{cases}$ 로 정의되는 함수는

$(\sigma(j) + i) \bmod{(k+1)} \ne 0$일때 $\sigma_i(j) = (\sigma(j) + i) \bmod{(k+1)} \ne i$이고

$(\sigma(j) + i) \bmod{(k+1)} = 0$일때 $\sigma_i(j) = k+1 = i$인 $j \in \mathbb{N}_{k+1} \setminus \{ i \}$가 존재한다고 가정하면

$\sigma(k+1) = k+1$이므로 $1\le \sigma(j) \le k$인데

$0 =(\sigma(j)+k+1)\bmod{(k+1)} = \sigma(j) \bmod{(k+1)} = \sigma(j)$로 모순이 되어 $\sigma_i :\mathbb{N}_{k+1} \setminus \{ i \} \to \mathbb{N}_{k+1} \setminus \{ i \}$이다.

모든 $j_1,j_2 \in \mathbb{N}_{k+1}\setminus \{ i \}$에 대해

$\sigma_i(j_1) = \sigma_i(j_2)$이면

$(\sigma(j_1) +i) \bmod{(k+1)}= \sigma_i(j_1)\bmod{(k+1)} = \sigma_i(j_2)\bmod{(k+1)}  = (\sigma(j_2) +i) \bmod{(k+1)}  $이므로

$\sigma(j_1) +i = q_1\cdot (k+1) + \sigma_i(j_1) \bmod{(k+1)}$이고

$\sigma(j_2) +i = q_2\cdot (k+1) + \sigma_i(j_2) \bmod{(k+1)}$인 $q_1, q_2 \in \mathbb{Z}$가 유일하게 존재하여

$\sigma(j_1) - \sigma(j_2) = (q_1 - q_2) \cdot (k+1)$이다.

따라서 $1 \le \sigma(j_1)  \le k+1 $이고 $1 \le \sigma(j_2)  \le k+1 $이므로 $-k \le \sigma(j_1) - \sigma(j_2) = (q_1 - q_2) \cdot (k+1) \le k$가 되어

$\sigma(j_1) = \sigma(j_2)$이고 $\sigma$가 단사이므로 $j_1 = j_2$이고 $\sigma_i$도 단사이다.

또 $\sigma_i :\mathbb{N}_{k+1} \setminus \{ i \} \to \mathbb{N}_{k+1} \setminus \{ i \}$가 전사가 아니면 단사임에 모순이므로 전단사가 되어 $\sigma_i \in S_{A_i}$이다.

$\sigma_i \in S_{A_i}$로 만든 $\overline{\sigma}_i $는 모든 $j \in \mathbb{N}_{k+1}$에 대해

$j = i$이면 $\overline{\sigma}_i(i) = k+1 = \sigma(i)$이고

$j \ne i$이면

$\begin{align*} \overline{\sigma}_i(j) & = (\sigma_i(j) + (k+1-i)) \bmod{(k+1)} \\[0.5em] & = ( (\sigma_i(j)\bmod{(k+1)}) +(k+1-i) )\bmod{(k+1)} \\[0.5em] & =  ( ( (\sigma(j) +i) \bmod{(k+1)} ) + (k+1-i)) \bmod{(k+1)} \\[0.5em] & = ( \sigma(j) +i + (k+1-i)) \bmod{(k+1)} \\[0.5em] & = ( \sigma(j) + (k+1)) \bmod{(k+1)} \\[0.5em] & = \sigma(j)  \text{이므로 }\end{align*}$

임의의 $\mathbb{N}_{k+1}$의 치환 $\sigma \in S_{k+1}$는 $\overline{\sigma}_i = \sigma$이고 $S_{k+1}$은 정확히 $(k+1)!$개의 원소를 갖는다.

 

종합하여 모든 $n \in \mathbb{Z}^+$에 대해 $S_n$이 $n!$개의 원소를 갖고

위 정리로 $(S_n ,\circ,\iota_n)$과 $(S_A ,\circ,\iota_A)$는 동형이므로 유한집합 정리로 $S_A$는 $n!$개의 원소를 갖는다.

 

 

 

정리6

$(G,*_{\!G},e_G)$와 $(H, *_{\!H},e_H)$가 군일때

단사함수 $\phi : G \to H$가 모든 $x ,y \in G$에 대해 $\phi(x *_{\!G}y) = \phi(x) * _{\!H} \phi(y)$이면

$($$\phi(G)$$,*_{\!H},e_H)$는 $(H, *_{\!H},e_H)$의 부분군이고 $(G,*_{\!G},e_G)$와 $(\phi(G),*_{\!H},e_H)$는 동형이다.

증명

$\phi(G) \subseteq H$이고 $(G,*_{\!G},e_G)$가 군이므로 모든 $x ,y \in G$에 대해 $x *_{\!G} y \in G$이고

$ \phi(x) * _{\!H} \phi(y) = \phi(x * _{\!G} y) \in \phi(G)$가 되어 $\phi(G)$는 $*_{H}$에 대해 닫혀있다.

각각의 항등원 $e_G \in G$와 $e_H \in H$에 대해 $e_H *_{\!H} \phi(e_G) = \phi(e_G) = \phi(e_G *_{\!G} e_G) = \phi(e_G) *_{\!H} \phi(e_G) $이고 

$(H, *_{\!H},e_H)$가 군이므로 우측 소거법칙으로 $e_H = \phi(e_G) \in \phi(G)$이다.

또 임의의 $g \in G$에 대해 $g^{-1} \in G$이고 $(\phi(g))^{-1} *_{\!H} \phi(g) = e_H = \phi(e_G) = \phi(g^{-1} *_{\!G} g) = \phi(g^{-1}) *_{\!H} \phi(g)$이므로

우측 소거법칙으로 $(\phi(g))^{-1} = \phi(g^{-1}) \in \phi(G)$이다.

따라서 부분군 정리로 $(\phi(G),*_{\!H},e_H)$는 $(H, *_{\!H},e_H)$의 부분군이다.

또 모든 $x \in G$에 대해 $\phi_1(x) = \phi(x)$인 함수 $\phi_1 : G \to \phi(G)$는 함수 정리로 전단사이고

모든 $x ,y \in G$에 대해 $\phi_1(x *_{\!G} y) = \phi(x *_{\!G}y) = \phi(x) * _{\!H} \phi(y) = \phi_1(x) *_{\!H} \phi_1(y)$이므로

$(G,*_{\!G},e_G)$와 $(\phi(G),*_{\!H},e_H)$는 동형이다.

 

 

 

정리7(케일리[Cayley] 정리)

모든 군 $(G,*,e)$에 대해 다음이 성립한다.

좌측 정칙표현

모든 $x,g \in G$에 대해 $\lambda_x(g) = x* g$인 함수 $\lambda_x : G \to G$는 전단사이고

$\phi(x) = \lambda_x$인 단사 함수 $\phi : G \to $ $S_G$를 좌측 정칙표현이라 할때

$($$\phi(G)$$,$ $\circ$$,\iota)$는 $G$의 치환군이고 $(G,*,e)$와 동형이다.

우측 정칙표현

모든 $x,g \in G$에 대해 $\rho_x(g) = g*x$인 함수 $\rho_x : G \to G$는 전단사이고

$\mu(x) = \rho_{x^{-1}}$인 단사 함수 $\mu : G \to $ $S_G$를 우측 정칙표현이라 할때 

$($$\mu(G)$$,$ $\circ$$,\iota)$는 $G$의 치환군이고 $(G,*,e)$와 동형이다.

증명

좌측 정칙표현

모든 $x, c \in G$에 대해

$\lambda_x(x^{-1}*c) = x * (x^{-1} * c) = (x* x^{-1})*c = c$인 $x^{-1} * c \in G$가 존재하므로 $\lambda_x$는 전사이고

모든 $a,b\in G$에 대해 $\lambda_x(a) = \lambda_x(b)$이면 $x * a = x *b$이므로 좌측 소거법칙으로 $a = b$이고 $\lambda_x$는 단사이다.

$\lambda_x$는 $G$에서 $G$로의 전단사이므로 $G$의 치환이 되어 $\lambda_x \in S_G$이다.

모든 $x,y \in G$에 대해 $\phi(x) = \phi(y)$이면 $\lambda_x = \lambda_y$이므로

항등원 $e \in G$에 대해 $ x= x* e= \lambda_x(e) = \lambda_y(e) = y*e = y$가 되어 $\phi$는 단사이다.

또 모든 $x,y,g \in G$에 대해 $\lambda_{x*y}(g) = (x*y)*g = x * y*g = \lambda_x(y*g) = \lambda_x( \lambda_y(g)) = (\lambda_x \circ \lambda_y )(g)$이므로

$\phi(x*y) = \lambda_{x*y} = \lambda_x \circ \lambda_y = \phi(x) \circ \phi(y)$가 되어 위 정리로

$(\phi(G),\circ,\iota)$는 $G$의 대칭군 $(S_G,\circ,\iota)$의 부분군이므로 $G$의 치환군이고 $(\phi(G),\circ,\iota)$와 $(G,*,e)$는 동형이다.

우측 정칙표현

모든 $x, c \in G$에 대해

$\rho_x(c *x^{-1}) =  (c *x^{-1} )*x = c* (x^{-1} * x)  = c$인 $c *x^{-1} \in G$가 존재하므로 $\rho_x$는 전사이고

모든 $a,b\in G$에 대해 $\rho_x(a) = \rho_x(b)$이면 $a*x  = b*x$이므로 우측 소거법칙으로 $a = b$이고 $\rho_x$는 단사이다.

$\rho_x$는 $G$에서 $G$로의 전단사이므로 $G$의 치환이 되어 $\rho_x \in S_G$이다.

모든 $x,y \in G$에 대해 $\mu(x) = \mu(y)$이면 $\rho_{x^{-1}} = \rho_{y^{-1}}$이므로

항등원 $e \in G$에 대해 $ x^{-1} = e *x^{-1} = \rho_{x^{-1}}(e) = \rho_{y^{-1}}(e) = e*y^{-1} = y^{-1}$이 되어

거듭연산 정리로 $x = (x^{-1})^{-1} = (y^{-1})^{-1} = y$이므로 $\mu$는 단사이다.

또 모든 $x,y,g \in G$에 대해 역원 정리로

$\begin{align*} \rho_{(x*y)^{-1}}(g) & = g * ((x*y)^{-1}) \\[0.5em] & = g * (y^{-1} * x^{-1}) \\[0.5em] & = (g* y^{-1}) * x^{-1} \\[0.5em] & = \rho_{x^{-1}}(g * y^{-1}) \\[0.5em] & = \rho_{x^{-1}}(\rho_{y^{-1}}(g)) \\[0.5em] & = (\rho_{x^{-1}} \circ \rho_{y^{-1}})(g) \text{ 이므로} \end{align*}$

$\mu(x*y) = \rho_{(x*y)^{-1}} = \rho_{x^{-1}} \circ \rho_{y^{-1}} = \mu(x) \circ \mu(y)$가 되어 위 정리로

$(\mu(G),\circ,\iota)$는 $G$의 대칭군 $(S_G,\circ,\iota)$의 부분군이므로 $G$의 치환군이고 $(\mu(G),\circ,\iota)$와 $(G,*,e)$는 동형이다.

 

 

 

정의3

$\sigma$아래서 $a$의 궤도(orbit of $a$ under $\sigma$) : 

공집합이 아닌 집합 $A$의 임의의 치환이 $\sigma \in S_A$일때

임의의 $a \in A$에 대해 $\mathcal{O}_{a,\sigma} = \{ $$\sigma^n(a)$ $ : n \in \mathbb{Z} \}$인 집합을 $\sigma$아래서 $a$의 궤도로 정의한다.

아래 정리로 $\mathcal{O}_{a,\sigma} =$ $\langle \sigma(a) \rangle^{\!*}$이다.

$\sigma$의 궤도(orbits of $\sigma$) :

아래 정리의 임의의 $a,b \in A$에 대해 $(a,b) \in \mathcal{R}_\sigma$이면 $\sigma^n(a) = b$가 되는 정수 $n \in \mathbb{Z}$이 존재하는

$A$의 동치관계 $\mathcal{R}_\sigma$에 대한 동치류를 $\sigma$의 궤도로 정의한다.

집합 $O$가 $\sigma$의 궤도이면

동치류 정의로 $O = [a]_{\mathcal{R}_\sigma}$인 $a \in A$가 존재하고 아래 정리로 $[a]_{\mathcal{R}_\sigma} = \mathcal {O}_{a,\sigma}$이므로

$\sigma$의 궤도인 집합 $O$는 $O = [a]_{\mathcal{R}_\sigma} = \mathcal{O}_{a,\sigma}$인 $a \in A$가 존재한다고 정의한다.

$\sigma$의 궤도인 집합 $O$는 동치류 정리와 아래 정리로 모든 $x \in O$에 대해 $O = [x]_{\mathcal{R}_\sigma} = \mathcal{O}_{x,\sigma}$이다.

 

 

 

정리8

공집합이 아닌 집합 $A$의 치환이 $\sigma \in S_A$일때

$\sigma$아래서 $a,b \in A$의 궤도에 $c \in \mathcal{O}_{a,\sigma}$이고 $c \in \mathcal{O}_{b,\sigma}$인 $c \in A$가 존재하면 $\mathcal{O}_{a,\sigma} = \mathcal{O}_{b,\sigma}$이다.

증명

$c \in \mathcal{O}_{a,\sigma}$이고 $c \in \mathcal{O}_{b,\sigma}$이면

$\sigma^{p}(a) = c = \sigma^{q}(b)$인 $p,q \in \mathbb{Z}$가 존재하고 위 정리로 $(S_A,\circ,\sigma^0)$은 군이므로 거듭연산 정리로

$b = \sigma^{-q}(\sigma^{p}(a)) = (\sigma^{-q} \circ \sigma^{p})(a) = \sigma^{p-q}(a)$이고 $a = \sigma^{-p}(\sigma^{q}(b)) = (\sigma^{-p} \circ \sigma^{q})(b) = \sigma^{q-p}(b)$이다.

따라서 모든 $\sigma^n(a) \in \mathcal{O}_{a,\sigma}$에 대해

$\sigma^n(a) = \sigma^n(\sigma^{q-p}(b)) = (\sigma^n \circ \sigma^{q-p})(b) = \sigma^{n + q -p}(b) \in \mathcal{O}_{b,\sigma}$이므로 $ \mathcal{O}_{a,\sigma} \subseteq \mathcal{O}_{b,\sigma}$이고

모든 $\sigma^n(b) \in \mathcal{O}_{b,\sigma}$에 대해

$\sigma^n(b) = \sigma^n(\sigma^{p-q}(a)) = (\sigma^n \circ \sigma^{p-q})(a) = \sigma^{n + p -q}(a) \in \mathcal{O}_{a,\sigma}$이므로 $ \mathcal{O}_{b,\sigma} \subseteq \mathcal{O}_{a,\sigma}$가 되어

$\mathcal{O}_{a,\sigma} = \mathcal{O}_{b,\sigma}$이다.

 

 

 

정리9

$A$가 $n \in \mathbb{Z}^+$개의 원소를 갖는 유한집합일때 다음을 만족하는 $A$의 치환군 $(H,\circ,\sigma^0)$이 존재한다.

1. 집합 $H$가 $n$개의 원소를 갖는다.

2. $\langle \sigma \rangle^{\!\circ}$ $ = H$가 되는 $\sigma \in $ $S_A$가 존재하여 $(H,\circ,\sigma^0)$은 $(S_A,\circ,\sigma^0)$의 순환 부분군이다.

3. 모든 $a,b \in A$에 대해 $\tau(a) = b$가 되는 $\tau \in H$가 존재한다.

증명

$A = \{ a_1, a_2, \cdots ,a_n \}$일때

모든 $i = 1,2,\cdots, n-1$에 대해 $\sigma(a_i) = a_{i+1}$이고 $\sigma(a_n) = a_1$인 함수 $\sigma : A \to A$는 전단사이므로 $\sigma \in S_A$이다.

또 위 정리로 $(S_A,\circ,\sigma^0)$은 군이고 모든 $i = 1,2,\cdots, n$에 대해

$\sigma^n(a_i) = \sigma^{n-(n-i)}(a_{i+(n-i)}) = \sigma^{i}(a_n) = \sigma^{i-1}(a_1) = \sigma^{i-1 - (i-1)}(a_{1 + (i-1)}) = \sigma^0(a_i) = a_i$이므로

$\circ$에 대한 항등원 $\sigma^0 = \sigma^n$이 되는 최소 양의 정수는 $n$이다.

따라서 $\sigma$에 의해 생성된 $(S_A,\circ,\sigma^0)$의 순환 부분군 $(\langle \sigma \rangle^{\! \circ}, \circ,\sigma^0 )$에 대해

순환군 정리로 $\langle \sigma \rangle^{\! \circ} = \{ \sigma^0, \sigma^1, \cdots, \sigma^{n-1} \} = H$인 집합은 $n$개의 원소를 갖고 $(H,\circ,\sigma^0)$이 순환군이므로

모든 $i,j = 1,2,\cdots ,n$에 대해 $\sigma^{j-i}(a_i) = a_{i+ (j-i) } = a_j$가 되는 $\sigma^{j-i} \in H$가 존재한다.

 

 

 

정리10

공집합이 아닌 집합 $A$의 임의의 치환이 $\sigma \in S_A$일때 임의의 $a,b \in A$에 대해 $(a,b) \in \mathcal{R}_\sigma$이면

$\sigma^n$$(a) = b$가 되는 정수 $n \in \mathbb{Z}$이 존재하는 관계 $\mathcal{R}_\sigma$는 $A$의 동치관계이다.

증명

위 정리로 $(S_A,\circ,\iota)$는 군이므로 모든 $n \in \mathbb{Z}$에 대해 $\sigma^n \in S_A$이고 $\sigma^n$의 역원은 $\sigma^{-n} \in S_A$이다.

반사성

모든 $a \in A$에 대해 $\sigma^0(a) = a$인 $0 \in \mathbb{Z}$이 존재하므로 $(a,a) \in \mathcal{R}_\sigma$이다.

대칭성

임의의 $a,b \in A$에 대해 $(a,b) \in \mathcal{R}_\sigma$이면

$\sigma^n(a) =b$가 되는 $n \in \mathbb{Z}$이 존재하므로 $-n \in \mathbb{Z}$에 대해 $ \sigma^{-n}(b) = a$가 되어 $(b,a) \in \mathcal{R}_\sigma$이다.

추이성

임의의 $a,b,c \in A$에 대해 $(a,b) \in \mathcal{R}_\sigma$이고 $(b,c) \in \mathcal{R}_\sigma$이면 $\sigma^p(a) =b$이고 $\sigma^q(b) = c$인 $p,q \in \mathbb{Z}$가 존재하여

$q + p \in \mathbb{Z}$에 대해 $\sigma^{q+p}(a) = \sigma^q(\sigma^p(a)) = \sigma^q(b) = c$이므로 $(a,c) \in \mathcal{R}_\sigma$이다.

 

 

 

정리11

공집합이 아닌 집합 $A$의 임의의 치환이 $\sigma \in S_A$일때 임의의 $a,b \in A$에 대해 $(a,b) \in \mathcal{R}_\sigma$이면

$\sigma^n$$(a) = b$가 되는 정수 $n \in \mathbb{Z}$이 존재하는 $A$의 동치관계 $\mathcal{R}_\sigma$에 대한 $a$의 동치류는 $[a]_{\mathcal{R}_\sigma} = $ $\mathcal{O}_{a,\sigma}$이다.

증명

$x \in [a]_{\mathcal{R}_\sigma}$이면 $(a,x) \in \mathcal{R}_\sigma$이므로 $\sigma^n(a) = x$인 정수 $n \in \mathbb{Z}$이 존재하여 $x \in \mathcal{O}_{a,\sigma}$이고 $[a]_{\mathcal{R}_\sigma} \subseteq \mathcal{O}_{a,\sigma} $이다.

$x \in \mathcal{O}_{a,\sigma}$이면 $\sigma^n(a) = x$인 정수 $n \in \mathbb{Z}$이 존재하므로 $(a,x) \in \mathcal{R}_\sigma$이고 $x \in [a]_{\mathcal{R}_\sigma}$이 되어 $\mathcal{O}_{a,\sigma} \subseteq [a]_{\mathcal{R}_\sigma}$이다.

따라서 $\mathcal{O}_{a,\sigma} = [a]_{\mathcal{R}_\sigma}$이다.

 

 

 

정리17

공집합이 아닌 집합 $A$의 임의의 치환이 $\sigma \in S_A$일때 임의의 $x \in A$에 대해

이항연산 $* : \mathcal{O}_{x,\sigma} \times \mathcal{O}_{x,\sigma} \to \mathcal{O}_{x,\sigma}$가 $i,j \in \mathbb{Z}$에 대해 $\sigma^i(x) * \sigma^j(x)  = (\sigma^i \circ \sigma^j)(x) = \sigma^{i+j}(x)$로 정의되면

$\sigma$아래서 $x$의 궤도는 $\mathcal{O}_{x,\sigma}$ $=$ $\langle \sigma(x) \rangle^{\!*}$이고 $(\mathcal{O}_{x,\sigma},*,\sigma^0(x))$는 순환군이다.

증명

$*$의 타당성

$\mathcal{O}_{x,\sigma}$의 정의로

모든 $a,b,c \in \mathcal{O}_{x,\sigma}$에 대해 $a= \sigma^i(x)$이고 $b= \sigma^j(x)$이고 $c= \sigma^k(x)$인 정수 $i,j,k \in \mathbb{Z}$가 존재한다.

또 $\sigma^i(x) = a = \sigma^n(x)$이고 $\sigma^j(x) = b = \sigma^m(x)$인 $n,m \in \mathbb{Z}$이 존재하면

$\sigma^n(x) * \sigma^j(x) = \sigma^{n + j}(x) = \sigma^{j + n}(x) = \sigma^j(\sigma^n(x)) = \sigma^j(\sigma^i(x)) = \sigma^{j + i}(x) = \sigma^{i+j}(x) = \sigma^i(x) *\sigma^j(x)$이고

$\sigma^i(x) * \sigma^m(x) = \sigma^{i + m}(x) = \sigma^i(\sigma^m(x)) = \sigma^i(\sigma^j(x)) = \sigma^{i + j}(x) =\sigma^i(x) *\sigma^j(x)$이므로 $*$는 함수이다.

$*$에 대해 닫힘

 $a*b = \sigma^i(x) * \sigma^j(x) = \sigma^{i+j}(x) \in \mathcal{O}_{x,\sigma}$이다.

$*$에 대한 결합법칙

$\begin{align*}(a*b)*c & = (\sigma^i(x) * \sigma^j(x)) * \sigma^k(x) \\[0.5em] & = \sigma^{i+j}(x) * \sigma^k(x) \\[0.5em] & = \sigma^{i+j+k}(x) \\[0.5em] & = \sigma^i(x) * \sigma^{j+k}(x) \\[0.5em] & =  \sigma^i(x) * (\sigma^j(x) * \sigma^k(x)) \\[0.5em] & = a * (b*c)  \text{ 이다. }\end{align*}$

$*$에 대한 항등원

$e = \sigma^0(x) \in \mathcal{O}_{x,\sigma}$로 두면

$e * a = \sigma^0(x) * \sigma^i(x) = \sigma^{0+i}(x) = a = \sigma^{i+0}(x) = \sigma^i(x) * \sigma^0(x) = a *e$이다.

$*$에 대한 역원

$a^{-1} = \sigma^{-i}(x) \in \mathcal{O}_{x,\sigma}$로 두면

$a * a^{-1} = \sigma^{i}(x) * \sigma^{-i}(x) = \sigma^{i-i}(x) = e = \sigma^{-i+i}(x) = \sigma^{-i}(x) * \sigma^i(x) = a^{-1} * a$이다.

따라서 $(\mathcal{O}_{x,\sigma},*,\sigma^0(x))$는 군이고 $*$에 대해 $\langle \sigma(x) \rangle^{\!*}$ $ = \mathcal{O}_{x,\sigma}$이므로 $(\mathcal{O}_{x,\sigma},*,\sigma^0(x))$는 순환군이다.

 

 

 

정의4

순환치환(cycle) : 

공집합이 아닌 유한집합 $A$의 

치환 $\sigma \in S_A$의 모든 궤도 중 원소개수가 $2$개 이상인 $\sigma$의 궤도가 없거나 하나뿐일때

$\sigma$를 $A$의 순환치환(cycle)으로 정의한다.

이때 원소개수가 $2$개 이상인 $\sigma$의 궤도가 존재하면 그 궤도의 원소개수를 순환치환 $\sigma$의 길이로 정의하고

원소개수가 $2$개 이상인 $\sigma$의 궤도가 존재하지 않으면 순환치환 $\sigma$의 길이는 $1$로 정의한다.

순환치환의 길이함수 $\lVert \sigma \rVert$를 순환치환들의 집합에서 양의 정수 집합으로의 함수로 정의한다.

순환치환의 서로소(disjoint) : 

길이가 $2$이상인 $A$의 순환치환 $\sigma, \tau \in S_A$의

원소개수가 $2$개 이상인 궤도가 어떤 $a,b \in A$에 대해 $\mathcal{O}_{a,\sigma}$이고 $\mathcal{O}_{b,\tau}$일때

$\mathcal{O}_{a,\sigma} \cap \mathcal{O}_{b, \tau} = \emptyset$이면 $\sigma$와 $\tau$가 서로소라고 정의한다.

 

 

 

정리12

공집합이 아닌 유한집합 $A$의 길이가 $2$이상인 임의의 순환치환 $\sigma \in S_A$에 대해

원소개수가 $2$개 이상인 $\sigma$의 궤도가 어떤 $a \in A$에 대해 $\mathcal{O}_{a,\sigma}$일때 $x \notin \mathcal{O}_{a,\sigma}$인 모든 $x \in A$는 $\sigma(x) = x$이다.

증명

$x \notin \mathcal{O}_{a,\sigma}$일때 $\sigma(x) \ne x$라고 가정하면 $x , \sigma(x) \in \mathcal{O}_{x,\sigma}$이므로 $ \mathcal{O}_{x,\sigma}$는 $2$개 이상의 원소를 갖는데

$ \mathcal{O}_{x,\sigma} \ne \mathcal{O}_{a,\sigma}$이고 순환치환의 정의로 원소개수가 $2$개 이상인 $\sigma$의 궤도 $\mathcal{O}_{a,\sigma}$는 유일하므로 모순이다.

따라서 $x \notin \mathcal{O}_{a,\sigma}$인 모든 $x \in A$는 $\sigma(x) = x$이다.

 

 

 

정리13

공집합이 아닌 유한집합 $A$의 치환 $\iota \in S_A$가 길이가 $1$인 순환치환이기 위한 필요충분조건은

$\iota$가 모든 $x \in A$에 대해 $\iota(x) = x$인 $A$의 대칭군 $(S_A,\circ,\iota)$의 항등원인 것이다.

증명

임의의 $\sigma \in S_A$와 모든 $x \in A$에 대해

$(\iota \circ \sigma)(x) = \iota(\sigma(x)) = \sigma(x) = \sigma(\iota(x)) = (\sigma \circ \iota)(x)$이므로

$\iota \circ \sigma = \sigma = \sigma \circ \iota$가 되어 $\iota$는 $(S_A,\circ,\iota)$의 항등원이다.

 

순환치환 $\overline{\iota} \in S_A$의 길이가 $1$이면

원소 개수가 $2$개 이상인 $\overline{\iota}$의 궤도가 존재하지 않으므로 $\overline{\iota}$의 모든 궤도는 원소개수가 $1$개이다.

$A$가 유한이므로 동치류 정리로 $\displaystyle \bigcup_{i = 1}^n B_i = A$이고 서로소인 $n \in \mathbb{Z}^+$개의 $\overline{\iota}$의 궤도 $B_1, B_2,\cdots , B_n$이 존재한다.

따라서 모든 $x \in A$에 대해 $x \in B_i$인 $1\le i \le n$가 존재하여

$\overline{\iota}$의 궤도의 정의로 $B_i  = [x]_{\mathcal{R}_\overline{\iota}}= \mathcal{O}_{x,\overline{\iota}}$이고 $B_i$의 원소개수는 1개이므로

위 정리와 순환군 정리로 $\overline{\iota}(x) = x = \iota(x)$가 되어 $\overline{\iota} = \iota$이다.

역으로 $\circ$에 대한 항등원 $\iota$는

모든 $x \in A$에 대해 $\iota(x) = x$이고 모든 정수 $p \in \mathbb{Z}$에 대해 $\iota^p(x) = \iota(x) = x$이므로

$\iota$의 모든 궤도는 원소개수가 $1$개가 되어 길이가 $1$인 순환치환이다.

 

 

 

정리14

공집합이 아닌 유한집합 $A$의 길이가 $2$이상인 순환치환 $\sigma, \tau \in S_A$가 서로소이면

$\sigma \circ \tau = \tau \circ \sigma$로 $\circ$에 대해 가환적이다.

증명

길이가 $2$이상인 순환치환 $\sigma, \tau \in S_A$가 서로소일때

원소개수가 $2$개 이상인 $\sigma$와 $\tau$의 궤도가 각각 어떤 $a,b \in A$에 대해 $\mathcal{O}_{a,\sigma}$이고 $\mathcal{O}_{b,\tau}$이면 $\mathcal{O}_{a,\sigma} \cap \mathcal{O}_{b, \tau} = \emptyset$이므로

$x \in \mathcal{O}_{a,\sigma}$이고 $x \in \mathcal{O}_{b,\tau}$인 $x \in A$는 존재하지 않는다.

임의의 $x \in A$에 대해 위 정리로

$x \notin \mathcal{O}_{a,\sigma}$이고 $x \notin \mathcal{O}_{b,\tau}$이면 $\sigma(x) = x$이고 $\tau(x) = x$이므로

$(\tau \circ \sigma )(x) = \tau(\sigma(x)) = \tau(x) = x = \sigma(x) = \sigma(\tau(x)) = (\sigma \circ \tau)(x)$이다.

$x \notin \mathcal{O}_{a,\sigma}$이고 $x \in \mathcal{O}_{b,\tau}$이면 $\sigma(x) = x$이고 $\tau(x) \in \mathcal{O}_{b,\tau}$이므로 $\tau(x) \notin \mathcal{O}_{a,\sigma}$가 되어

$(\tau \circ \sigma )(x) = \tau(\sigma(x)) = \tau(x) =  \sigma(\tau(x)) = (\sigma \circ \tau)(x)$이다.

$x \in \mathcal{O}_{a,\sigma}$이고 $x \notin \mathcal{O}_{b,\tau}$이면 $\tau(x) = x$이고 $\sigma(x) \in \mathcal{O}_{a,\sigma}$이므로 $\sigma(x) \notin \mathcal{O}_{b,\tau}$가 되어

$(\tau \circ \sigma )(x) = \tau(\sigma(x)) = \sigma(x) =  \sigma(\tau(x)) = (\sigma \circ \tau)(x)$이다.

따라서 모든 $x \in A$에 대해 $(\tau \circ \sigma )(x) = (\sigma \circ \tau)(x)$이므로 $\tau\circ  \sigma = \sigma \circ \tau$이다.

 

 

 

정리15

공집합이 아닌 유한집합 $A$의 대칭군 $(S_A,\circ,\iota)$의 항등원이 아닌 치환 $\sigma \in S_A$는

$\sigma = \mu_1 \circ \mu_2 \circ \cdots \circ \mu_m$이 되는 $m \in \mathbb{Z}^+$개의

$2\le \lVert \mu_1 \rVert \le \lVert \mu_2 \rVert \le \cdots \le \lVert \mu_m \rVert$이고 서로소인 순환치환 $\mu_1 , \mu_2 \cdots , \mu_m \in S_A$이 존재하고

합성 순서만 다른 것들을 같다고 가정하면 $\mu_1 , \mu_2 \cdots , \mu_m \in S_A$는 유일하다.

증명

존재성

$A$가 유한이므로

동치류 정리로 $\displaystyle \bigcup_{i = 1}^r B_i = A$이고 서로소인 $r \in \mathbb{Z}^+$개의 $\sigma$의 궤도 $B_1, B_2,\cdots , B_r$이 유일하게 존재한다.

모든 $x \in A$와 모든 $i = 1,2,\cdots, r$에 대해 $\mu_i(x) = \begin{cases} \sigma(x) , & x \in B_i \text{ 일때} \\ x, & x \notin B_i \text{ 일때} \end{cases}$인 함수 $\mu_i : A \to A$를 정의할때

$\sigma$가 단사이므로 함수정리로 $B_i$에서 $\sigma(B_i)$로의 전단사이고

$\sigma$의 궤도의 정의로 임의의 $a \in B_i$에 대해 $B_i = $ $\mathcal{O}_{a,\sigma}$이므로

모든 $x \in B_i$에 대해 $\sigma^n(a) = x$인 정수 $n \in \mathbb{Z}$이 존재하여

$\sigma(x) \in \sigma(B_i)$이면 $x \in B_i$이고 $\sigma(x) = \sigma(\sigma^n(a)) = \sigma^{n+1}(a) \in B_i$이므로 $\sigma(B_i) \subseteq B_i$이다.

또 $x \in B_i$이면 $\sigma^{n-1}(a) \in B_i$이고 $x = \sigma^n(a) = \sigma( \sigma^{n-1}(a)) \in \sigma(B_i)$이므로 $B_i \subseteq \sigma(B_i)$이고

$ \mathcal{O}_{a,\sigma} = B_i = \sigma(B_i)$가 되어 $\sigma$는 $B_i$에서 $B_i$로의 전단사이므로 $\mu_i$는 $A$에서 $A$로의 전단사이고 $\mu_i \in S_A$이다.

$\mu_i(B_i) = \sigma(B_i) = B_i$이고 모든 $x \in A\setminus B_i$에 대해 $\mu_i(x) = x$이므로

$\mu_i$는 $B_i$의 원소개수가 $2$개이상이면 $A$의 순환치환이고 $1$개이면 위 정리로 $\circ$에 대한 항등원이다.

$\mu_1 \circ \mu_2 \circ \cdots \circ \mu_r$은 $i \ne j$인 $i,j = 1,2,\cdots, r$에 대해 $B_i \cap B_j = \emptyset$이고 $\displaystyle \bigcup_{i = 1}^r B_i = A$이므로

모든 $x \in A$에 대해 $x \in B_i$인 $1\le i \le r$가 존재하여

위 정리로 $(\mu_1 \circ \mu_2 \circ \cdots \circ \mu_r)(x) = \mu_i( x) = \sigma(x)$이므로 $\sigma = \mu_1 \circ \mu_2 \circ \cdots \circ \mu_r$이다.

또 $\sigma$는 $\circ$에 대한 항등원이 아니므로 위 정리로 $\sigma$는 순환치환이 아니거나 순환치환일때 길이가 $2$이상이고

위 정리로 길이가 $1$인 순환치환은 $\circ$에 대한 항등원 $\iota \in S_A$이므로

$1\le i \le r$에 대해 길이가 $1$인 $\mu_i = \iota$를 모두 소거해도 $\sigma$는 하나이상의 순환치환의 합성이다.

따라서 위 정리로 서로소인 순환치환은 $\circ$에 대해 가환적이므로

길이가 $2\le \lVert \mu_1 \rVert \le \lVert \mu_2 \rVert \le \cdots \le \lVert \mu_m \rVert$이 되도록 첨수를 다시 쓰면

$\sigma = \mu_1 \circ  \cdots \circ \mu_m$인 순환치환 $\mu_1 , \mu_2 \cdots , \mu_m \in S_A$이 존재한다.

유일성

$ \mu_1 \circ  \cdots \circ \mu_m = \sigma = \tau_1\circ \tau_2 \circ \cdots \circ \tau_s$이고 

$2\le \lVert \tau_1 \rVert \le \lVert \tau_2 \rVert \le \cdots \le \lVert \tau_s \rVert$이 되는 서로소인 순환치환이 $\tau_1 , \tau_2 ,\cdots , \tau_s \in S_A$일때

동치류 정리로 $\sigma$의 궤도로 구성된 분할 $\mathcal{P}$는 유일하고

원소개수가 $2$개이상인 $\sigma$의 궤도는 어떤 $a \in A$와 $j = 1,2,\cdots, m$에 대해

$\mathcal{O}_{a,\sigma} = \mathcal{O}_{a, \mu_j} \in \mathcal{P}$이므로 원소개수가 $2$개이상인 $\sigma$의 모든 궤도들의 집합을 $\mathcal{P}_2$로 정의하고

모든 $i = 1,2,\cdots, s$와 어떤 $a_i \in A$에 대해

원소개수가 $2$개이상인 $\tau_i$의 궤도 $\mathcal{O}_{a_i,\tau_i}$의 집합을 $\mathcal{T}_2 = \{ \mathcal{O}_{a_1,\tau_1}, \mathcal{O}_{a_2, \tau_2},\cdots, \mathcal{O}_{a_s,\tau_s}  \}$로 정의한다.

$\tau_1 , \tau_2 ,\cdots , \tau_s$가 모두 서로소이므로 임의의 $i = 1,2,\cdots, s$와 모든 $x \in \mathcal{O}_{a_i,\tau_i} \in \mathcal{T}_2$에 대해 

위 정리로 $\sigma(x) = (\tau_1\circ \tau_2 \circ \cdots \circ \tau_s)(x) = \tau_i(x) $이고 $\sigma(a_i) = \tau_i(a_i)$가 되어

귀납법으로 모든 $k \in \mathbb{Z}^+$에 대해 $\sigma^k(a_i) = \tau_i^k(a_i)$라고 가정할때 $\tau_i^k(a_i) \in \mathcal{O}_{a_i,\tau_i}$이고

 $\sigma^{k+1}(a_i) = \sigma(\sigma^k(a_i)) = \sigma(\tau_i^k(a_i)) = \tau_i(\tau_i^k(a_i)) = \tau_i^{k+1}(a_i)$이므로 모든 $n \in \mathbb{Z}^+$에 대해 $\sigma^n(a_i) = \tau_i^n(a_i)$이다.

또 $\mathcal{O}_{a_i,\tau_i}$와 $\mathcal{O}_{a_i,\sigma}$는 유한집합이므로 위 정리와 순환군 정리로 $\mathcal{O}_{a_i,\tau_i}  = \mathcal{O}_{a_i,\sigma}$이고

$\mathcal{O}_{a_i,\sigma}$는 원소개수가 $2$개이상인 $\sigma$의 궤도이므로 $ \mathcal{O}_{a_i,\tau_i}  = \mathcal{O}_{a_i,\sigma} \in \mathcal{P}_2$가 되어 $\mathcal{T}_2 \subseteq \mathcal{P}_2$이다.

또 어떤 $a \in A$에 대해 원소개수가 $2$개이상인 $\sigma$의 임의의 궤도가 $\mathcal{O}_{a,\sigma} \in \mathcal{P}_2$일때

$\mathcal{O}_{a,\sigma}$는 유한집합이므로 모든 $x \in \mathcal{O}_{a,\sigma}$에 대해 위 정리와 순환군 정리로 $x \ne \sigma(x) = (\tau_1\circ \tau_2 \circ \cdots \circ \tau_s)(x)$인데

$x \in \mathcal{O}_{a_i,\tau_i}$인 $i = 1,2,\cdots, s$가 존재하지 않으면 

모든 $i = 1,2,\cdots, s$에 대해 $x \notin \mathcal{O}_{a_i,\tau_i}$이고 $\tau_1 , \tau_2 ,\cdots , \tau_s$가 모두 서로소이므로

위 정리로 $\tau_i(x) = x$가 되어 $x \ne \sigma(x) = (\tau_1\circ \tau_2 \circ \cdots \circ \tau_s)(x) = x$로 모순이다.

따라서 모든 $x \in \mathcal{O}_{a,\sigma}$에 대해 $x \in \mathcal{O}_{a_i,\tau_i}$인 $i = 1,2,\cdots, s$가 존재하여

$ \sigma(x) = (\tau_1\circ \tau_2 \circ \cdots \circ \tau_s)(x) = \tau_i(x)$이므로 위와 비슷하게 $\mathcal{O}_{a,\sigma} = \mathcal{O}_{a_i,\tau_i} \in \mathcal{T}_2$이고

$\mathcal{P}_2 \subseteq \mathcal{T}_2$이므로 $\mathcal{P}_2 = \mathcal{T}_2$가 되어 $m = s$이다.

또 원소개수가 $2$개이상인 모든 $\sigma$의 궤도는 $\tau_1 , \tau_2 ,\cdots , \tau_s$의 궤도와 같으므로

모든 $i = 1,2,\cdots, s$에 대해 $\tau_i = \mu_j$인 $j = 1,2,\cdots, m$가 존재하고

합성 순서만 다른 것들을 같다고 가정하면 $\mu_1 , \mu_2 \cdots , \mu_m \in S_A$는 유일하다.

 

 

 

정의5

호환(transpostion) :

공집합이 아닌 유한집합 $A$의 순환치환의 길이가 $2$이면 $A$의 호환이라 정의한다.

짝치환(even), 홀치환(odd) :

$A$의 어떤 치환 $\sigma \in S_A$가 $\sigma = \mu_1\circ \mu_2\circ \cdots \circ \mu_k$이고 모든 $i = 1,2,\cdots, k$에 대해 $\mu_i \in S_A$가 호환일때

$k \in \mathbb{Z}^+$가 짝수이면 $\sigma$를 짝치환으로 정의하고

$k \in \mathbb{Z}^+$가 홀수이면 $\sigma$를 홀치환으로 정의한다.

아래 정리로 $A$의 모든 치환 $\sigma \in S_A$는

$\sigma = \mu_1\circ \mu_2\circ \cdots \circ \mu_k$인 호환이 존재하고 짝치환임과 동시에 홀치환일 수 없다.

$n$문자 교대군 :

$n$문자 대칭군 $(S_n,\circ,\iota_n)$에 대해

아래 정리로 $A_n \subseteq S_n$인 집합 $A_n$이 짝치환으로만 구성되어 있으면 $(A_n,\circ,\iota_n)$은 군이므로 

$(S_n,\circ,\iota_n)$의 부분군 $(A_n,\circ,\iota_n)$을 $n$문자 교대군으로 정의한다.

 

 

 

정리16

$n \ge 2$인 임의의 $n \in \mathbb{Z}^+$개의 원소를 갖는 유한집합 $A$에 대해 다음이 성립한다.

1. $A$의 모든 치환 $\sigma \in S_A$는 유한개의 호환들의 합성이다.

2. $A$의 모든 치환 $\sigma \in S_A$는 짝치환이면 홀치환이 아니고 홀치환이면 짝치환이 아니다.

3. $A$의 모든 짝치환들의 집합족이 $E_A$일때 $(E_A,\circ,\iota)$는 $($$S_A$$,\circ,\iota)$의 부분군이고 $E_A$의 원소개수는 $\dfrac{n!}{2}$개이다.

증명

1.

$n \ge 2$인 $n \in \mathbb{Z}^+$에 대한 강귀납법을 사용한다.

$n = 2$이고 $A = \{ a_1, a_2 \}$일때

$\sigma(a_1) = a_2$이고 $\sigma(a_2) = a_1$인 치환 $\sigma \in S_A$는 호환이다.

$\iota(a_1) = a_1$이고 $\iota(a_2) = a_2$인 치환 $\iota \in S_A$는

$(\sigma \circ \sigma )(a_1) = \sigma(a_2) = a_1 = \iota(a_1)$이고 $(\sigma \circ \sigma )(a_2) = \sigma(a_1) = a_2 = \iota(a_2)$이므로 $\iota = \sigma \circ \sigma$는 호환들의 합성이다.

위 정리로 $S_A$는 $2! = 2$개의 치환을 가지므로 $n = 2$에 대해 정리가 성립한다.

모든 $2,3,\cdots ,k \in \mathbb{Z}^+$에 대해 정리가 성립한다고 가정할때

$A = \{ a_1,a_2,\cdots, a_k, a_{k+1} \}$가 $k+1$개의 원소를 가지면 동치류 정리로 $\displaystyle \bigcup_{i = 1}^r B_i = A$이고

서로소인 $r \in \mathbb{Z}^+$개의 $\sigma \in S_A$의 궤도 $B_1, B_2,\cdots , B_r$이 유일하게 존재하고 분할의 정리로 $1\le r\le k+1$이다.

$r = k+1$일때

모든 $x \in A$에 대해 $x \in B_i$인 $1\le i \le k+1$가 존재하여

$\sigma$의 궤도의 정의로 $B_i = $ $\mathcal{O}_{x,\sigma}$이므로 $ \sigma(x) \in B_i$이고 $B_i$가 하나의 원소만 가지므로 $\sigma(x) = x$이다.

따라서 $\tau(a_1) = a_2$와 $\tau(a_2) = a_1$이 성립하고 $j = 3, 4 , \cdots, k+1$에 대해 $\tau(a_j) = a_j$인 호환 $\tau \in S_A$는

$\sigma(a_1) = a_1 = \tau(a_2) = (\tau \circ \tau)(a_1) $과 $\sigma(a_2) = a_2 =\tau(a_1) = (\tau \circ \tau)(a_2)$가 성립하고

$j = 3, 4 , \cdots, k+1$에 대해 $\sigma(a_j) = a_j = \tau(a_j) = (\tau \circ \tau)(a_j)$이므로 $\sigma = \tau\circ \tau$이다.

$r = 1$일때

$\sigma$의 궤도의 정의로 $A = B_1 = $ $\mathcal{O}_{a_1,\sigma}$이고

위 정리로 $(\mathcal{O}_{a_1,\sigma},*,\sigma^0(a_1))$은 순환군이므로 순환군 정리로 $A = \{ \sigma^0(a_1), \sigma^1(a_1), \cdots, \sigma^k(a_1) \}$이다.

따라서 $i= 1,2,\cdots, k$에 대해 $\mu_i(\sigma^i(a_1)) = \sigma^0(a_1)$와 $\mu_i(\sigma^0(a_1)) = \sigma^i(a_1)$이 성립하고

$i \ne j$인 $j = 1,2\cdots, k$에 대해 $\mu_i(\sigma^j(a_1)) = \sigma^j(a_1)$인 치환 $\mu_i \in S_A$는 호환이므로

모든 $i= 1,2,\cdots, k -1$에 대해

$\begin{align*}  (\mu_k \circ \mu_{k-1} \circ \cdots \circ \mu_1)(\sigma^i(a_1))  & = (\mu_k \circ \mu_{k-1} \circ \cdots  \circ \mu_{i+1} \circ \mu_i)(\sigma^i(a_1)) \\[0.5em] & = (\mu_k \circ \mu_{k-1} \circ \cdots \circ \mu_{i+2} \circ \mu_{i+1})(\sigma^0(a_1)) \\[0.5em] & =  (\mu_k \circ \mu_{k-1} \circ \cdots \circ \mu_{i+2} )(\sigma^{i+1}(a_1)) \\[0.5em] & = \sigma^{i+1}(a_1) \\ & = \sigma( \sigma^i(a_1)) \text{ 이고 } \end{align*}$

$\begin{align*}  (\mu_k \circ \mu_{k-1} \circ \cdots \circ \mu_1)(\sigma^0(a_1))  & =  (\mu_k \circ \mu_{k-1} \circ \cdots \circ  \mu_2\circ \mu_1)(\sigma^0(a_1)) \\[0.5em] & =  (\mu_k \circ \mu_{k-1} \circ \cdots \circ \mu_2 )(\sigma^1(a_1)) \\[0.5em] & =  \sigma^1(a_1) \\[0.5em] & =  \sigma( \sigma^0(a_1) ) \text{ 이다. } \end{align*}$

또 $*$에 대한 항등원 $\sigma^0(a_1)$에 대해 순환군 정리로 $\sigma^0(a_1) = \sigma^{k+1} (a_1) = \sigma(\sigma^k(a_1))$이므로

$  (\mu_k \circ \mu_{k-1} \circ \cdots \circ \mu_1)(\sigma^k(a_1))  =  \mu_k(\sigma^k(a_1))  =  \sigma^0(a_1)  =  \sigma( \sigma^k(a_1) )$이 되어 $\sigma = \mu_k \circ \mu_{k-1} \circ \cdots \circ \mu_1 $이다.

$1 < r < k+1$일때

$\sigma$는 $\circ$에 대한 항등원이 아니므로

위 정리로 $\sigma = \mu_1 \circ \mu_2 \circ \cdots \circ \mu_m$이고 길이가 $2$이상인 서로소 순환치환 $\mu_1 , \mu_2 , \cdots , \mu_m \in S_A$이 존재하고

위 정리에서 보였듯이 모든 $i = 1,2,\cdots,m$에 대해 $\mu_i$를 원소개수가 $2$개이상인 $\mu_i$의 궤도 $O_i$로 제한했을때

$\mu_i |_{O_i}$는 $O_i$에서 $O_i$로의 전단사이고 $O_i \subseteq \displaystyle \bigcup_{j = 1}^rB_j$는 $O_i = B_{j_i}$가 존재하여 $2$개이상 $k+1$개미만의 원소를 가지므로

귀납가정으로 $\mu_i |_{ O_i} = \tau_{i,1}\circ \tau_{i,2}\circ \cdots \circ \tau_{i,p_i}$인 $O_i$의 호환 $\tau_{i,1}, \tau_{i,2}, \cdots , \tau_{i,p_i} \in S_{O_i}$이 존재한다.

따라서 모든 $j = 1,2,\cdots, p_i$와 모든 $x \in A$에 대해 $\overline{\tau}_{i,j}(x) = \begin{cases} \tau_{i,j}(x) , & x \in O_i \text{ 일때} \\ x , & x\notin O_i \text{ 일때}  \end{cases}$ 로 확장하면

$\overline{\tau}_{i,j} \in S_A$는 $A$의 호환이고 $ \mu_i  = \overline{\tau}_{i,1} \circ \overline{\tau}_{i,2} \circ \cdots \circ \overline{\tau}_{i,p_i} $이므로

$\sigma = \mu_1 \circ \mu_2 \circ \cdots \circ \mu_m = (\overline{\tau}_{1,1} \circ \cdots \circ \overline{\tau}_{1,p_1} ) \circ (\overline{\tau}_{2,1} \circ \cdots \circ \overline{\tau}_{2,p_2} ) \circ \cdots \circ (\overline{\tau}_{m,1} \circ \cdots \circ \overline{\tau}_{m,p_m} ) $이 되어

$n \ge 2$인 모든 $n \in \mathbb{Z}^+$에 대해 정리가 성립한다.

2.

임의의 치환 $\lambda \in S_A$에 대해 동치류 정리로

$\displaystyle \bigcup_{i = 1}^r B_i = A$이고 서로소인 $r \in \mathbb{Z}^+$개의 $\lambda$의 궤도 $B_1, B_2,\cdots , B_r$이 유일하게 존재하므로

$\lambda$의 궤도 개수를 나타내는 함수를 $\operatorname{orbits}(\lambda) = r$로 정의할때

$\tau \in S_A$가 호환이면 $|\operatorname{orbits}(\tau \circ \lambda) - \operatorname{orbits}(\lambda)| = 1$임을 보인다.

$A = \{ a_1, a_2,\cdots , a_n \}$일때 $i\ne j$인 $i,j = 1,2,\cdots, n$와 모든 $x \in A$에 대해

$\tau(x) = \begin{cases} a_i ,& x = a_j \text{ 일때} \\ a_j , & x = a_i \text{ 일때} \\ x , & x\ne a_i \text{ 이고 } x\ne a_j \text{ 일때 }\end{cases}$ 로 정의하면 $\tau$는 $A$의 호환이다.

 

$\lambda$의 궤도 $B_1, B_2,\cdots , B_r$에 대해 $a_i \in B_{m}$와 $a_j \in B_{k}$가 성립하고 $B_m \ne B_k$일때

$\lambda$의 궤도의 정의로 $B_m = \mathcal{O}_{a_i,\lambda}$이고 위 정리와 순환군 정리로

$B_m$의 원소개수 $p_m \in \mathbb{Z}^+$에 대해 $B_m = \mathcal{O}_{a_i,\lambda} = \{ a_i, \lambda(a_i), \lambda^2(a_i),\cdots, \lambda^{p_m-1}(a_i) \}$이므로

$p_m \ge 2$이면 모든 $q = 1,2,\cdots, p_m-1$에 대해 $\lambda^q(a_i) \ne a_i$이고 $\lambda^q(a_i) \in B_m$이므로 $\lambda^q(a_i) \ne a_j$가 되어

$(\tau\circ \lambda)(a_i) = \tau(\lambda(a_i)) = \lambda(a_i) ,$

$(\tau\circ \lambda)^2(a_i) = (\tau \circ \lambda)(\lambda(a_i)) = \tau(\lambda^2(a_i)) = \lambda^2(a_i),$

                                $\vdots$

$(\tau\circ \lambda)^{p_m-1}(a_i) = (\tau \circ \lambda)(\lambda^{p_m-2}(a_i)) = \tau(\lambda^{p_m-1}(a_i)) = \lambda^{p_m-1}(a_i)$이다.

$x \in B_m$일때

$x \ne a_i$이면 $x = \lambda^q(a_i)$인 $q = 1,2,\cdots, p_m-1$가 존재하여 $x = \lambda^q(a_i) = (\tau \circ \lambda)^q(a_i) \in \mathcal{O}_{a_i, \tau \circ \lambda}$이고

$p_m = 1$이거나 $p_m \ge 2$일때 $x = a_i$이면 $x = a_i = (\tau \circ \lambda)^0(a_i) \in \mathcal{O}_{a_i,\tau \circ \lambda}$이므로 $B_m \subseteq \mathcal{O}_{a_i,\tau \circ \lambda}$이다.

비슷하게 $B_k = \mathcal{O}_{a_j,\lambda}$이므로 $B_k \subseteq \mathcal{O}_{a_j,\tau \circ \lambda}$이다.

$B_m$의 원소개수 $p_m$에 대해 $(\tau\circ \lambda)^{p_m}(a_i) = (\tau \circ \lambda)(\lambda^{p_m-1}(a_i)) = \tau(\lambda^{p_m}(a_i)) = \tau(a_i) = a_j \in \mathcal{O}_{a_i, \tau \circ \lambda }$이므로

위 정리로 $\mathcal{O}_{a_i,\tau \circ \lambda} = \mathcal{O}_{a_j,\tau \circ \lambda}$가 되어 $B_m \cup B_k \subseteq \mathcal{O}_{a_i,\tau \circ \lambda}$이다.

또 $B_k$의 원소개수 $p_k$에 대해

$(\tau\circ \lambda)^{p_k + p_m}(a_i) = ((\tau \circ \lambda)^{p_k} \circ (\tau \circ \lambda)^{p_m})(a_i) = (\tau \circ \lambda)^{p_k}(a_j) =  (\tau \circ \lambda)(\lambda^{p_k -1}(a_j)) = \tau (\lambda^{p_k}(a_j)) = \tau(a_j) = a_i \text{ 이므로}$

위 정리와 순환군 정리로 $\mathcal{O}_{a_i,\tau \circ \lambda} = \mathcal{O}_{a_j,\tau \circ \lambda}$는 $p_m + p_k$개의 원소를 갖고

$B_m \cap B_k = \emptyset$이므로 $B_m \cup B_k$도 $p_m + p_k$개의 원소를 가져 유한집합 정리로 $B_m \cup B_k = \mathcal{O}_{a_i,\tau \circ \lambda}$이다.

$B_s \ne B_m$이고 $B_s \ne B_k$인 $\lambda$의 궤도 $B_s$에 대해 모든 $x \in B_s$는 $x \ne a_i$이고 $x \ne a_j$이므로 $\tau(x) = x$이고

모든 $p \in \mathbb{Z}$에 대해 $(\tau \circ \lambda)^p(x) = \lambda^p(x) \in B_s$가 되어 $B_s$는 $\tau \circ \lambda$의 궤도이다.

따라서 $\lambda$의 궤도 $B_1, B_2,\cdots , B_r$에서 $\tau \circ \lambda$의 궤도 $B_1, B_2,\cdots , B_m\cup B_k,  \cdots, B_r$이 만들어지므로

$\operatorname{orbits}(\tau \circ \lambda) =   \operatorname{orbits}(\lambda) - 1$이 성립한다.

 

$\lambda$의 궤도 $B_1, B_2,\cdots , B_r$에 대해 $a_i, a_j \in B_{m}$일때

$\lambda$의 궤도의 정의로 $B_m = \mathcal{O}_{a_i,\lambda} = \mathcal{O}_{a_j, \lambda}$이고 위 정리와 순환군 정리로

$p \ge 2$인 $B_m$의 원소개수 $p \in \mathbb{Z}^+$에 대해 $B_m = \mathcal{O}_{a_i,\lambda} = \{ a_i, \lambda(a_i), \lambda^2(a_i),\cdots, \lambda^{p-1}(a_i) \}$이므로

$a_j = \lambda^q(a_i)$가 되는 $q = 1,2,\cdots, p-1$가 존재하여

$B_m = \{ \lambda^0( a_i), \lambda^1(a_i),\cdots, \lambda^{q-1}(a_i), \lambda^{q+0}(a_i) = \lambda^0(a_j) , \lambda^{q +1}(a_i) = \lambda^1(a_j), \cdots , \lambda^{p-1}(a_i) = \lambda^{p-1}(\lambda^{-q}(a_j)) = \lambda^{p-q-1}(a_j) \} \text{ 이다.}$

$q \ge 2$일때 $k = 1,2,\cdots q -1$에 대해 $\lambda^k(a_i) \ne a_i$이고 $\lambda^k(a_i) \ne a_j$이므로 $(\tau \circ \lambda)^k(a_i) = \lambda^k(a_i)$이고

$(\tau \circ \lambda)^q(a_i) = ( \tau \circ \lambda)(\lambda^{q-1}(a_i)) = \tau (\lambda^{q}(a_i)) = \tau(a_j) = a_i$가 되어

위 정리와 순환군 정리로

$\mathcal{O}_{a_i,\tau\circ \lambda} = \{ ( \tau \circ \lambda )^0(a_i) = \lambda^0( a_i),  (\tau \circ \lambda)^1(a_i) = \lambda^1(a_i),\cdots,  (\tau\circ \lambda)^{q-1}(a_i)= \lambda^{q-1}(a_i)\}$이다.

$p- q \ge 2$일때 $k =  1, 2, \cdots,p- q -1$에 대해 $\lambda^k(a_j) \ne a_j$이고 $\lambda^k(a_j) \ne a_i$이므로 $(\tau \circ \lambda)^k(a_j) = \lambda^k(a_j)$이고

$(\tau \circ \lambda)^{p-q}(a_j) = ( \tau \circ \lambda)(\lambda^{p-q-1}(a_j)) = \tau (\lambda^{p-q}(a_j)) = \tau(\lambda^p(a_i)) = \tau(a_i) = a_j$가 되어

위 정리와 순환군 정리로

$\mathcal{O}_{a_j,\tau\circ \lambda} = \{ ( \tau \circ \lambda )^0(a_j) = \lambda^0( a_j),  (\tau \circ \lambda)^1(a_j) = \lambda^1(a_j),\cdots,  (\tau\circ \lambda)^{p-q-1}(a_j)= \lambda^{p-q-1}(a_j)\}$이다.

또 $B_s \ne B_m$인 $\lambda$의 궤도 $B_s$에 대해 모든 $x \in B_s$는 $x \ne a_i$이고 $x \ne a_j$이므로 $\tau(x) = x$이고

모든 $t \in \mathbb{Z}$에 대해 $(\tau \circ \lambda)^t(x) = \lambda^t(x) \in B_s$가 되어 $B_s$는 $\tau \circ \lambda$의 궤도이다.

따라서 $ \mathcal{O}_{a_i,\tau\circ \lambda} \cup \mathcal{O}_{a_j,\tau\circ \lambda} = B_m $이고 $ \mathcal{O}_{a_i,\tau\circ \lambda} \cap \mathcal{O}_{a_j,\tau\circ \lambda} = \emptyset $이므로

$\lambda$의 궤도 $B_1, B_2,\cdots , B_r$에서 $\tau \circ \lambda$의 궤도 $B_1, B_2,\cdots , B_m \setminus \mathcal{O}_{a_i, \tau \circ \lambda}, B_m \setminus \mathcal{O}_{a_j,\tau \circ  \lambda} ,  \cdots, B_r$이 만들어지므로

$\operatorname{orbits}(\tau \circ \lambda) =  \operatorname{orbits}(\lambda) + 1$이 성립한다.

 

종합하여 $|\operatorname{orbits}(\tau \circ \lambda) - \operatorname{orbits}(\lambda)| = 1$이므로 $-1 = -1 \cdot 2 + 1$이고 $1 = 0 \cdot 2 + 1$임에 따라

모듈로 합동은 $\operatorname{orbits}(\tau \circ \lambda) - \operatorname{orbits}(\lambda) \equiv 1 \pmod 2$이고 $\operatorname{orbits}(\tau \circ \lambda) \equiv \operatorname{orbits}(\lambda)+1 \pmod 2$이다.

또 호환 $\tau_1, \tau_2, \cdots, \tau_k , \mu_1, \mu_2, \cdots, \mu_m \in S_A$에 대해

$\begin{align*} \operatorname{orbits}(\tau_1 \circ \tau_2 \circ \cdots \circ \tau_k \circ \lambda) & \equiv \operatorname{orbits}(\tau_2 \circ \tau_3 \circ \cdots \circ \tau_k \circ \lambda) + 1 \pmod 2 \\[0.5em] & \equiv \operatorname{orbits}( \tau_3 \circ \cdots \circ \tau_k \circ \lambda) + 2 \pmod 2 \\[0.5em] & \qquad \qquad \vdots \\[0.5em] & \equiv \operatorname{orbits}( \lambda) + k \pmod 2 \text{ 이고 }\end{align*} $

$\lambda$가 모든 $x \in A$에 대해 $\lambda(x) =x$인 항등치환이면 $\operatorname{orbits}( \lambda) = n$이므로

$ \operatorname{orbits}(\tau_1 \circ \tau_2 \circ \cdots \circ \tau_k) - n  \equiv  k \pmod 2 $이다.

따라서 $1$번으로 임의의 치환 $\sigma \in S_A$는 유한개의 호환들의 합성이므로

$ \sigma = \tau_1 \circ \tau_2 \circ \cdots \circ \tau_k $인 짝수 $k \in \mathbb{Z}^+$와 $ \sigma = \mu_1 \circ \mu_2 \circ \cdots \circ \mu_m $인 홀수 $m \in \mathbb{Z}^+$이 존재하면

짝수 정리로 $ \begin{align*} \operatorname{orbits}(\sigma) - n & \equiv  k \pmod 2 \\ & \equiv 0 \pmod 2 \end{align*}$이고

홀수 정리로 $ \begin{align*} \operatorname{orbits}(\sigma) - n & \equiv  m \pmod 2 \\ & \equiv 1 \pmod 2 \end{align*}$이 되어 $0 \equiv 1 \pmod 2$이므로 모순이다.

3.

모든 $\sigma , \tau \in E_A$에 대해

짝수 정리로 짝수 더하기 짝수는 짝수이므로 $\sigma \circ \tau \in E_A$가 되어 $E_A$는 $\circ$에 대해 닫혀있다.

$A = \{ a_1, a_2,\cdots, a_n \}$일때 모든 $x \in A$에 대해 $\iota(x) = x$인 $\circ$에 대한 항등원 $\iota \in S_A$는 

$\tau(a_1) = a_2$와 $\tau(a_2) = a_1$이 성립하고 $j = 3, 4 , \cdots, n$에 대해 $\tau(a_j) = a_j$인 호환 $\tau \in E_A$에 대해

$\iota(a_1) = a_1 = \tau(a_2) = (\tau \circ \tau)(a_1) $과 $\iota(a_2) = a_2 =\tau(a_1) = (\tau \circ \tau)(a_2)$가 성립하고

$j = 3, 4 , \cdots, n$에 대해 $\iota(a_j) = a_j = \tau(a_j) = (\tau \circ \tau)(a_j)$이므로 $\iota= \tau\circ \tau$이고 $\iota \in E_A$이다.

모든 $\sigma \in E_A$가 호환 $\tau_1, \tau_2, \cdots, \tau_k \in E_A$에 대해 $ \sigma = \tau_1 \circ \tau_2 \circ \cdots \circ \tau_k $이면

역원 정리로

$\begin{align*} \sigma^{ -1} & =  (\tau_1 \circ \tau_2 \circ \cdots \circ \tau_k )^{-1} \\[0.5em] & = \tau_k^{-1} \circ (\tau_1 \circ \tau_2 \circ \cdots \tau_{k-1} )^{-1}  \\[0.5em] & = \tau_k^{-1} \circ \tau_{k-1}^{-1} \circ \cdots \circ \tau_2^{-1} \circ \tau_1^{-1} \text{ 이고 }  \end{align*}$

$\tau_1^{-1}, \tau_2^{-1}, \cdots ,\tau_k^{-1} $은 호환이므로 $\sigma^{-1} \in E_A$이다.

따라서 위 정리로 $(S_A,\circ,\iota)$는 군이므로 부분군 정리로 $(E_A,\circ,\iota)$는 $(S_A,\circ,\iota)$의 부분군이다.

 

$O_A \subseteq S_A$가 홀치환들의 집합이고 $\tau \in E_A$가 위처럼 $\tau(a_1) = a_2$이고 $\tau(a_2) = a_1$인 호환일때

모든 $\sigma \in E_A$에 대해 $\tau \circ \sigma \in O_A$이므로 $f_\tau(\sigma) = \tau \circ \sigma$인 함수 $f_\tau : E_A \to O_A$를 정의한다.

모든 $\sigma,\mu \in E_A$에 대해 $f_\tau(\sigma) =  f_\tau(\mu)$이면

$\tau \circ \sigma = \tau \circ \mu$이고 $\sigma = \tau^{-1} \circ \tau \circ \sigma = \tau^{-1} \circ \tau \circ \mu = \mu$이므로 $f_\tau$는 단사이다.

또 모든 홀치환 $\rho \in O_A$에 대해

$\tau^{-1} \in E_A$이 호환이므로 $\tau^{-1} \circ \rho \in E_A$가 되어 $f_\tau(\tau^{-1} \circ \rho) = \tau \circ \tau^{-1} \circ \rho = \rho$이므로 $f_\tau$는 전사이다.

$E_A$의 원소개수가 $\dfrac{n!}{2} \ne m$인 $m \in \mathbb{Z}^+$개라 가정하면

$f_\tau : E_A \to O_A$가 전단사이므로 유한집합 정리로 $O_A$도 $m$개의 원소를 갖는다.

하지만 2번으로 $E_A \cap O_A = \emptyset$이고 1번으로 $E_A \cup O_A = S_A$이므로

유한집합 정리로 $S_A$는 $n! \ne 2m$인 $2m$개의 원소를 갖게 되어 위 정리에 모순이다.

따라서 $E_A$의 원소개수는 $\dfrac{n!}{2}$개이다.

 

 

 

-------------------------------------------------------------------------------

정의의 링크 : 

https://openknowledgevl.tistory.com/52#def번호

번호는 해당 정의 옆에 붙어있는 작은 숫자입니다.

 

정리의 링크 : 

https://openknowledgevl.tistory.com/52#thm번호

번호는 해당 정리 옆에 붙어있는 작은 숫자입니다.

 

위 내용은 아래의 출처를 기반으로 정리한 내용입니다.

틀린 내용이 존재할 수 있습니다.

 

출처(저자 - 제목 - ISBN13)

John B. Fraleigh - A First course in Abstract Algebra - 9788998308162