對於任何有限非空集S，A(S) 是S到S的所有一對一變換（對映）的集合，它形成一個稱為置換群的群，並且A(S) 的任何元素，即從S到自身的對映，被稱為置換。
定理 1： 令 A {\displaystyle A} A {\displaystyle A} S A {\displaystyle S_{A}} f : , A → A {\displaystyle f\,:,A\rightarrow A}
證明 : 我們必須驗證群公理。結合律成立，因為函式的複合運算總是結合的: ( f ∘ g ) ∘ h ( x ) = f ∘ g ( h ( x ) ) = f ( g ( h ( x ) ) ) = f ( g ∘ h ( x ) ) = f ∘ ( g ∘ h ) ( x ) {\displaystyle (f\circ g)\circ h(x)=f\circ g(h(x))=f(g(h(x)))=f(g\circ h(x))=f\circ (g\circ h)(x)} i d A ( a ) = a {\displaystyle \mathrm {id} _{A}(a)=a} a ∈ A {\displaystyle a\in A} f {\displaystyle f} f − 1 {\displaystyle f^{-1}} f ( a ) {\displaystyle f(a)} a {\displaystyle a} a ∈ A {\displaystyle a\in A} f {\displaystyle f} S A {\displaystyle S_{A}} ∎
S A {\displaystyle S_{A}} A {\displaystyle A} A = { 1 , 2 , . . . , n } , n ∈ N {\displaystyle A=\{1,2,...,n\}\,,\,n\in \mathbb {N} } S n {\displaystyle S_{n}} n {\displaystyle n} n {\displaystyle n}
我們將使用不同的符號 ι {\displaystyle \iota } e {\displaystyle e} S n {\displaystyle S_{n}}
當 σ ∈ S n {\displaystyle \sigma \in S_{n}} σ {\displaystyle \sigma } σ {\displaystyle \sigma } n × n {\displaystyle n\times n} ( i , σ ( i ) ) {\displaystyle (i,\sigma (i))} 1 {\displaystyle 1} 0 {\displaystyle 0} ρ {\displaystyle \rho } ( i , ρ ( i ) ) {\displaystyle (i,\rho (i))} 1 {\displaystyle 1} ( σ ( j ) , ρ ( σ ( j ) ) ) {\displaystyle (\sigma (j),\rho (\sigma (j)))} ( j , ρ ( σ ( j ) ) ) {\displaystyle (j,\rho (\sigma (j)))} 1 {\displaystyle 1}
我們可以用 2 × n {\displaystyle 2\times n} ( 1 2 … n σ ( 1 ) σ ( 2 ) … σ ( n ) ) {\displaystyle \left({\begin{array}{cccc}1&2&\dots &n\\\sigma (1)&\sigma (2)&\dots &\sigma (n)\end{array}}\right)} σ ∈ S n {\displaystyle \sigma \in S_{n}}
注 2: 令 σ , ρ ∈ S n {\displaystyle \sigma ,\rho \in S_{n}} σ ρ ≡ σ ∘ ρ {\displaystyle \sigma \rho \equiv \sigma \circ \rho } ρ {\displaystyle \rho } σ {\displaystyle \sigma } σ ρ ( x ) = σ ( ρ ( x ) ) {\displaystyle \sigma \rho (x)=\sigma (\rho (x))} S n {\displaystyle S_{n}} ( x ) ρ σ {\displaystyle (x)\rho \sigma } S n {\displaystyle S_{n}}
例 3: 我們將展示 S 3 {\displaystyle S_{3}} S 3 {\displaystyle S_{3}} ι = ρ 0 {\displaystyle \iota =\rho _{0}} ρ 1 = ( 1 2 3 2 3 1 ) {\displaystyle \rho _{1}=\left({\begin{array}{ccc}1&2&3\\2&3&1\end{array}}\right)} ρ 2 = ( 1 2 3 3 1 2 ) {\displaystyle \rho _{2}=\left({\begin{array}{ccc}1&2&3\\3&1&2\end{array}}\right)} μ 1 = ( 1 2 3 1 3 2 ) {\displaystyle \mu _{1}=\left({\begin{array}{ccc}1&2&3\\1&3&2\end{array}}\right)} μ 2 = ( 1 2 3 3 2 1 ) {\displaystyle \mu _{2}=\left({\begin{array}{ccc}1&2&3\\3&2&1\end{array}}\right)} μ 3 = ( 1 2 3 2 1 3 ) {\displaystyle \mu _{3}=\left({\begin{array}{ccc}1&2&3\\2&1&3\end{array}}\right)} S 3 {\displaystyle S_{3}}
∘ ρ 0 ρ 1 ρ 2 μ 1 μ 2 μ 3 ρ 0 ρ 0 ρ 1 ρ 2 μ 1 μ 2 μ 3 ρ 1 ρ 1 ρ 2 ρ 0 μ 3 μ 1 μ 2 ρ 2 ρ 2 ρ 0 ρ 1 μ 2 μ 3 μ 1 μ 1 μ 1 μ 2 μ 3 ρ 0 ρ 2 ρ 1 μ 2 μ 2 μ 3 μ 1 ρ 1 ρ 0 ρ 2 μ 3 μ 3 μ 1 μ 2 ρ 2 ρ 1 ρ 0 {\displaystyle {\begin{array}{c|cccccc}\circ &\rho _{0}&\rho _{1}&\rho _{2}&\mu _{1}&\mu _{2}&\mu _{3}\\\hline \rho _{0}&\rho _{0}&\rho _{1}&\rho _{2}&\mu _{1}&\mu _{2}&\mu _{3}\\\rho _{1}&\rho _{1}&\rho _{2}&\rho _{0}&\mu _{3}&\mu _{1}&\mu _{2}\\\rho _{2}&\rho _{2}&\rho _{0}&\rho _{1}&\mu _{2}&\mu _{3}&\mu _{1}\\\mu _{1}&\mu _{1}&\mu _{2}&\mu _{3}&\rho _{0}&\rho _{2}&\rho _{1}\\\mu _{2}&\mu _{2}&\mu _{3}&\mu _{1}&\rho _{1}&\rho _{0}&\rho _{2}\\\mu _{3}&\mu _{3}&\mu _{1}&\mu _{2}&\rho _{2}&\rho _{1}&\rho _{0}\end{array}}} 定理 4： S n {\displaystyle S_{n}} n ! {\displaystyle n!}
證明 ：這可以透過計數論證得出。我們可以在 S n {\displaystyle S_{n}} i ∈ { 1 , 2 , . . . , n } {\displaystyle i\in \{1,2,...,n\}} σ ∈ S n {\displaystyle \sigma \in S_{n}} σ ( 1 ) {\displaystyle \sigma (1)} n {\displaystyle n} σ ( 2 ) {\displaystyle \sigma (2)} { 1 , . . . , n } − { σ ( 1 ) } {\displaystyle \{1,...,n\}-\{\sigma (1)\}} n − 1 {\displaystyle n-1} σ ( i ) {\displaystyle \sigma (i)} { 1 , . . . , n } − { σ ( 1 ) , . . . , σ ( i − 1 ) } {\displaystyle \{1,...,n\}-\{\sigma (1),...,\sigma (i-1)\}} n + 1 − i {\displaystyle n+1-i} S n {\displaystyle S_{n}} | S n | = ∏ i = 1 n ( n + 1 − i ) = n ( n − 1 ) . . . ⋅ 2 ⋅ 1 = n ! {\displaystyle |S_{n}|=\prod _{i=1}^{n}(n+1-i)=n(n-1)...\cdot 2\cdot 1=n!} ∎
定理 5： S n {\displaystyle S_{n}} n ≥ 3 {\displaystyle n\geq 3}
證明 ：設 σ = ( 1 2 3 … n 2 1 3 … n ) {\displaystyle \sigma =\left({\begin{array}{ccccc}1&2&3&\dots &n\\2&1&3&\dots &n\end{array}}\right)} ρ = ( 1 2 3 … n 1 3 2 … n ) {\displaystyle \rho =\left({\begin{array}{ccccc}1&2&3&\dots &n\\1&3&2&\dots &n\end{array}}\right)} σ ρ = ( 1 2 3 … n 2 3 1 … n ) {\displaystyle \sigma \rho =\left({\begin{array}{ccccc}1&2&3&\dots &n\\2&3&1&\dots &n\end{array}}\right)} ρ σ = ( 1 2 3 … n 3 1 2 … n ) {\displaystyle \rho \sigma =\left({\begin{array}{ccccc}1&2&3&\dots &n\\3&1&2&\dots &n\end{array}}\right)} σ ρ ≠ ρ σ {\displaystyle \sigma \rho \neq \rho \sigma } S n {\displaystyle S_{n}} ∎
定義 6： 設 σ ∈ S n {\displaystyle \sigma \in S_{n}} σ k = ι {\displaystyle \sigma ^{k}=\iota } k ∈ Z {\displaystyle k\in \mathbb {Z} } σ {\displaystyle \sigma } k {\displaystyle k} -迴圈 ，其中 k {\displaystyle k} σ ∗ {\displaystyle \sigma ^{*}} a {\displaystyle a} σ ( a ) ≠ a {\displaystyle \sigma (a)\neq a} σ , ρ {\displaystyle \sigma ,\rho } 不相交 的，如果 σ ∗ ∩ ρ ∗ = ∅ {\displaystyle \sigma ^{*}\cap \rho ^{*}=\emptyset } 對換 。
備註 3: 重要的是要認識到，如果 a ∈ σ ∗ {\displaystyle a\in \sigma ^{*}} σ ( a ) {\displaystyle \sigma (a)} σ ( a ) = b ≠ a {\displaystyle \sigma (a)=b\neq a} σ ( b ) = b {\displaystyle \sigma (b)=b} σ {\displaystyle \sigma }
定理 7: 令 σ , ρ ∈ S n {\displaystyle \sigma ,\rho \in S_{n}} σ ∗ ∩ ρ ∗ = ∅ {\displaystyle \sigma ^{*}\cap \rho ^{*}=\emptyset } σ ρ = ρ σ {\displaystyle \sigma \rho =\rho \sigma }
證明 : 對於任何整數 1 ≤ a ≤ n {\displaystyle 1\leq a\leq n} a ∈ σ ∗ {\displaystyle a\in \sigma ^{*}} a ∉ ρ ∗ {\displaystyle a\not \in \rho ^{*}} σ ρ ( a ) = σ ( ι ( a ) ) = σ ( a ) = ι ( σ ( a ) ) = ρ ( σ ( a ) ) = ρ σ ( a ) {\displaystyle \sigma \rho (a)=\sigma (\iota (a))=\sigma (a)=\iota (\sigma (a))=\rho (\sigma (a))=\rho \sigma (a)} a ∈ ρ ∗ {\displaystyle a\in \rho ^{*}} a ∉ σ ∗ {\displaystyle a\not \in \sigma ^{*}} a ∉ σ ∗ ∪ ρ ∗ {\displaystyle a\not \in \sigma ^{*}\cup \rho ^{*}} σ ρ ( a ) = σ ( a ) = a = ρ ( a ) = ρ σ ( a ) {\displaystyle \sigma \rho (a)=\sigma (a)=a=\rho (a)=\rho \sigma (a)} σ ∗ ∩ ρ ∗ = ∅ {\displaystyle \sigma ^{*}\cap \rho ^{*}=\emptyset } a ∈ { 1 , . . . , n } {\displaystyle a\in \{1,...,n\}} ∎
定理 8: 任何置換都可以表示為不相交迴圈的複合。
證明 ：令 σ ∈ S n {\displaystyle \sigma \in S_{n}} a ∈ σ ∗ {\displaystyle a\in \sigma ^{*}} σ ( a ) , σ 2 ( a ) , . . . , σ k ( a ) = a {\displaystyle \sigma (a),\sigma ^{2}(a),...,\sigma ^{k}(a)=a} S n {\displaystyle S_{n}} n ! {\displaystyle n!} k {\displaystyle k} k ≤ n ! {\displaystyle k\leq n!} k {\displaystyle k} σ 1 {\displaystyle \sigma _{1}} a {\displaystyle a} σ 1 ∗ = { a , σ ( a ) , . . . , σ k − 1 ( a ) } {\displaystyle \sigma _{1}^{*}=\{a,\sigma (a),...,\sigma ^{k-1}(a)\}} σ {\displaystyle \sigma } σ = σ 1 σ ′ {\displaystyle \sigma =\sigma _{1}\sigma ^{\prime }} σ ∗ {\displaystyle \sigma ^{*}} σ {\displaystyle \sigma } ∎
現在我們已經證明了所有置換都只是不相交迴圈的組合，我們可以引入置換的最終簡寫符號。對於一個 n {\displaystyle n} σ {\displaystyle \sigma } a ∈ σ ∗ {\displaystyle a\in \sigma ^{*}} σ = ( a σ ( a ) σ 2 ( a ) . . . σ n − 1 ( a ) ) {\displaystyle \sigma =\left(a\ \sigma (a)\ \sigma ^{2}(a)\ ...\ \sigma ^{n-1}(a)\right)}
定理 9： 任何 n {\displaystyle n}
證明 ：令 σ = ( a σ ( a ) σ 2 ( a ) . . . σ n − 1 ( a ) ) {\displaystyle \sigma =\left(a\ \sigma (a)\ \sigma ^{2}(a)\ ...\ \sigma ^{n-1}(a)\right)} σ = ( a σ 2 ( a ) . . . σ n − 1 ( a ) ) ( a σ ( a ) ) {\displaystyle \sigma =\left(a\ \sigma ^{2}(a)\ ...\ \sigma ^{n-1}(a)\right)\left(a\ \sigma (a)\right)} ∘ {\displaystyle \circ } σ = ( a σ n − 1 ( a ) ) . . . ( a σ 2 ( a ) ) ( a σ ( a ) ) {\displaystyle \sigma =\left(a\ \sigma ^{n-1}(a)\right)...\left(a\ \sigma ^{2}(a)\right)\left(a\ \sigma (a)\right)} ∎
注10： 這種用對換乘積表示 σ {\displaystyle \sigma } 不是 唯一的。 然而，正如我們現在將要看到的，這種表示的“奇偶性”是明確定義的。
定義11： 如果一個置換可以表示為偶數個對換的乘積，則該置換的奇偶性 為偶數 。 否則，它是奇數 。 我們定義函式 sgn ( σ ) = 1 {\displaystyle \operatorname {sgn}(\sigma )=1} σ {\displaystyle \sigma } sgn ( σ ) = − 1 {\displaystyle \operatorname {sgn}(\sigma )=-1} σ {\displaystyle \sigma }
引理12： 單位元 ι {\displaystyle \iota }
Proof : Observe first that ι ≠ ( a b ) {\displaystyle \iota \neq (a\ b)} a ≠ b {\displaystyle a\neq b} ι {\displaystyle \iota } ι = ( a b ) ( a b ) {\displaystyle \iota =(a\ b)(a\ b)} k {\displaystyle k} ι = ( a 1 b 1 ) . . . ( a k b k ) {\displaystyle \iota =(a_{1}\ b_{1})...(a_{k}\ b_{k})} ι ( a 1 ) = a 1 {\displaystyle \iota (a_{1})=a_{1}} a 1 ∈ ( a i b i ) ∗ {\displaystyle a_{1}\in (a_{i}\ b_{i})^{*}} 1 < i ≤ k {\displaystyle 1<i\leq k} ( a r a s ) ( a i a r ) = ( a i a s ) ( a r a s ) {\displaystyle (a_{r}\ a_{s})(a_{i}\ a_{r})=(a_{i}\ a_{s})(a_{r}\ a_{s})} a i ≠ a r ≠ a s {\displaystyle a_{i}\neq a_{r}\neq a_{s}} ( a 1 b 1 ) ( a 1 b 1 ) = ι {\displaystyle (a_{1}\ b_{1})(a_{1}\ b_{1})=\iota } ( a 1 b 1 ) ( a 1 b 2 ) = ( a 1 b 2 ) ( b 1 b 2 ) {\displaystyle (a_{1}\ b_{1})(a_{1}\ b_{2})=(a_{1}\ b_{2})(b_{1}\ b_{2})} a 1 {\displaystyle a_{1}} a 1 {\displaystyle a_{1}} k − 2 {\displaystyle k-2} k − 2 {\displaystyle k-2} k {\displaystyle k} ∎
定理13： 置換的奇偶性，以及 sgn {\displaystyle \operatorname {sgn} }
證明 ：設 σ ∈ S n {\displaystyle \sigma \in S_{n}} σ {\displaystyle \sigma } σ = τ 1 . . . τ k = τ 1 ′ . . . τ k ′ ′ {\displaystyle \sigma =\tau _{1}...\tau _{k}=\tau _{1}^{\prime }...\tau _{k^{\prime }}^{\prime }} ι {\displaystyle \iota } ι = σ σ − 1 = τ 1 . . . τ k τ k ′ ′ . . . τ 1 ′ {\displaystyle \iota =\sigma \sigma ^{-1}=\tau _{1}...\tau _{k}\tau _{k^{\prime }}^{\prime }...\tau _{1}^{\prime }} k + k ′ ≡ 0 m o d 2 {\displaystyle k+k^{\prime }\equiv 0\ \mathrm {mod} \ 2} k ≡ k ′ m o d 2 {\displaystyle k\equiv k^{\prime }\ \mathrm {mod} \ 2} σ {\displaystyle \sigma } sgn {\displaystyle \operatorname {sgn} } ∎
定理 14： 設 σ , ρ ∈ S n {\displaystyle \sigma ,\rho \in S_{n}} sgn ( σ ρ ) = sgn ( σ ) sgn ( ρ ) {\displaystyle \operatorname {sgn}(\sigma \rho )=\operatorname {sgn}(\sigma )\operatorname {sgn}(\rho )}
證明 ：將 σ {\displaystyle \sigma } ρ {\displaystyle \rho } σ = μ 1 . . . μ k {\displaystyle \sigma =\mu _{1}...\mu _{k}} ρ = ν 1 . . . ν l {\displaystyle \rho =\nu _{1}...\nu _{l}} σ ρ = μ 1 . . . μ k ν 1 . . . ν l {\displaystyle \sigma \rho =\mu _{1}...\mu _{k}\nu _{1}...\nu _{l}} k + l {\displaystyle k+l} k + l {\displaystyle k+l} sgn ( σ ) sgn ( ρ ) = 1 ⋅ 1 = 1 = sgn ( σ ρ ) {\displaystyle \operatorname {sgn}(\sigma )\operatorname {sgn}(\rho )=1\cdot 1=1=\operatorname {sgn}(\sigma \rho )} k + l {\displaystyle k+l} sgn ( σ ) sgn ( ρ ) = ( − 1 ) ⋅ 1 = − 1 = sgn ( σ ρ ) {\displaystyle \operatorname {sgn}(\sigma )\operatorname {sgn}(\rho )=(-1)\cdot 1=-1=\operatorname {sgn}(\sigma \rho )} ∎
引理 15： S n {\displaystyle S_{n}}
證明 ：令 σ {\displaystyle \sigma } τ {\displaystyle \tau } τ σ {\displaystyle \tau \sigma } E {\displaystyle E} O {\displaystyle O} f ( σ ) = τ σ {\displaystyle f(\sigma )=\tau \sigma } f : E → O {\displaystyle f:E\rightarrow O} σ ∈ E {\displaystyle \sigma \in E} τ {\displaystyle \tau } S S n {\displaystyle S_{S_{n}}} E {\displaystyle E} O {\displaystyle O} ∎
定義 16： 令 S n {\displaystyle S_{n}} A n {\displaystyle A_{n}} A n {\displaystyle A_{n}} n {\displaystyle n} 交錯群 。
定理 17： A n {\displaystyle A_{n}} 是 一個群，並且是 S n {\displaystyle S_{n}} n ! 2 {\displaystyle {\frac {n!}{2}}}
證明 ：我們首先證明 A n {\displaystyle A_{n}} S n {\displaystyle S_{n}} A n {\displaystyle A_{n}} S n {\displaystyle S_{n}} ι ∈ A n {\displaystyle \iota \in A_{n}} A n {\displaystyle A_{n}} S n {\displaystyle S_{n}} | A n | = | S n | 2 = n ! 2 {\displaystyle |A_{n}|={\frac {|S_{n}|}{2}}={\frac {n!}{2}}} ∎
定理 18： 設 n ≥ 3 {\displaystyle n\geq 3} A n {\displaystyle A_{n}} S n {\displaystyle S_{n}}
證明 ：我們必須證明任何偶置換都可以分解成 3-迴圈。只要證明對一對換位成立就足夠了。設 a , b , c , d ∈ S n {\displaystyle a,b,c,d\in S_{n}}
i) ( a b ) ( a b ) = ( a b c ) 3 {\displaystyle (a\ b)(a\ b)=(a\ b\ c)^{3}} ii) ( a b ) ( b c ) = ( c a b ) {\displaystyle (a\ b)(b\ c)=(c\ a\ b)} iii) ( a b ) ( c d ) = ( a d c ) ( a b c ) {\displaystyle (a\ b)(c\ d)=(a\ d\ c)(a\ b\ c)} 證明了定理。 ∎
在前面的章節中，我們證明了拉格朗日定理：任何子群的階數都整除其母群的階數。但是，反過來，即一個群對於其階數的每個除數都存在一個子群，則是錯誤的！最小的反例是交錯群 A 4 {\displaystyle A_{4}} C 3 {\displaystyle C_{3}} A 4 {\displaystyle A_{4}}
這些線代表正六邊形的反射對稱 二面體群 D 16 {\displaystyle D_{16}} 二面體群是正多邊形的對稱群。因此，它們是對稱群的子群。一般來說，一個正 n {\displaystyle n} n {\displaystyle n} n {\displaystyle n}
定義 19： 階數為 2 n {\displaystyle 2n} 的二面體群 ，記為 D 2 n {\displaystyle D_{2n}} n {\displaystyle n}
定理 20： D 2 n {\displaystyle D_{2n}} 2 n {\displaystyle 2n}
證明 : 令 ρ {\displaystyle \rho } D 2 n {\displaystyle D_{2n}} n {\displaystyle n} ⟨ ρ ⟩ {\displaystyle \langle \rho \rangle } n {\displaystyle n} μ {\displaystyle \mu } D 2 n {\displaystyle D_{2n}} ⟨ ρ ⟩ {\displaystyle \langle \rho \rangle } μ {\displaystyle \mu } D 2 n = { ι , ρ , . . . , ρ n − 1 , μ , μ ρ , . . . , μ ρ n − 1 } {\displaystyle D_{2n}=\{\iota ,\rho ,...,\rho ^{n-1},\mu ,\mu \rho ,...,\mu \rho ^{n-1}\}} D 2 n {\displaystyle D_{2n}} 2 n {\displaystyle 2n} ∎
備註 21: 從這個證明中我們也可以看到 { ρ , μ } {\displaystyle \{\rho ,\mu \}} G {\displaystyle G} ρ {\displaystyle \rho } μ {\displaystyle \mu } ρ n = ι {\displaystyle \rho ^{n}=\iota } μ 2 = ι {\displaystyle \mu ^{2}=\iota } ρ μ = μ ρ − 1 {\displaystyle \rho \mu =\mu \rho ^{-1}}
