§E7.4対称群

証明. 二つの全単射の合成は全単射であるため、積は$\operatorname{Sym}(X)$上で閉じている。写像の合成は結合的であり、恒等写像$\operatorname{id}_X$は単位元である。全単射$\sigma$の逆写像$\sigma^{-1}$も全単射であり、

を満たす。したがって$\operatorname{Sym}(X)$は群である。

$n=0$のとき、空集合から空集合への写像は一つだけであり、$0!=1$と一致する。$n\geq1$のとき、$X$の元を一つの順序で並べる。第1の元の像には$n$通り、第2の元の像には残る$n-1$通りがある。同じ選択を続けると、全単射の個数は$n(n-1)\cdots1=n!$である。▨

証明.$x\in X$を任意に取る。$x\notin\operatorname{supp}(\alpha)\cup \operatorname{supp}(\beta)$ならば、二つの積はいずれも$x$を固定する。

$x\in\operatorname{supp}(\alpha)$とする。台が交わらないため$\beta(x)=x$である。また、$\alpha$は自身の台を自身へ移すので$\alpha(x)\in\operatorname{supp}(\alpha)$であり、$\beta(\alpha(x))=\alpha(x)$である。したがって

となる。$x\in\operatorname{supp}(\beta)$の場合も$\alpha$と$\beta$を交換した同じ計算で等式を得る。すべての$x\in X$で値が一致するため、$\alpha\beta=\beta\alpha$である。▨

証明.$x,y\in X$に対して、ある整数$k$が存在して$y=\sigma^k(x)$となるとき$x\sim y$と定める。$x=\sigma^0(x)$であるから反射律が成り立つ。$y=\sigma^k(x)$ならば$x=\sigma^{-k}(y)$であるから対称律が成り立つ。$y=\sigma^k(x)$かつ$z=\sigma^\ell(y)$ならば$z=\sigma^{k+\ell}(x)$であるから推移律が成り立つ。したがって$\sim$は同値関係であり、$X$を$\sigma$の軌道へ分割する。

軌道$O$を一つ取り、$a\in O$とする。$X$は有限であるから、$a,\sigma(a),\sigma^2(a),\ldots$の中には同じ元が二度現れる。全単射$\sigma$の逆写像を用いると、ある正の整数$r$が存在して$\sigma^r(a)=a$となる。そのような$r$の最小値を取れば

は相異なり、軌道$O$のすべての元を尽くす。$r\geq2$の軌道に対して

と定める。この巡回表示は$a$の選び方を変えても開始点が巡回移動するだけである。

相異なる軌道から得られる巡回置換の台は交わらない。非自明な軌道に対応する$c_O$をすべて掛けると、各非自明な軌道上では$\sigma$と同じ値を取り、一元だけの軌道上では$\sigma$と積の双方がその元を固定する。したがって、その積は$\sigma$に等しい。互いに素な置換は命題 2.2によって可換であるため、因子の順序は積を変えない。

一意性を示す。$\sigma=c_1\cdots c_t$が互いに素な長さ2以上の巡回置換の積であるとする。$x\in\operatorname{supp}(\sigma)$を取ると、$x$はただ一つの因子$c_i$の台に属する。他の因子は$c_i$の台を各点ごとに固定するため、任意の整数$k$に対して

が成り立つ。したがって$c_i$の台は$x$の$\sigma$軌道に一致し、その軌道上で$c_i$は$\sigma$と同じ作用をする。よって$c_i$は

に限られる。各因子は非自明な軌道と一対一に対応するため、別の分解との違いは因子の順序と各巡回表示の開始点だけである。▨

証明. 長さ$r\geq2$の巡回置換について

が成り立つ。実際、右辺は$a_1$を$a_2$へ移し、$2\leq j<r$に対して$a_j$を$a_{j+1}$へ移し、$a_r$を$a_1$へ移す。$a_1,\ldots,a_r$以外の元はすべての因子によって固定されるため、右辺は左辺と一致する。

定理 3.1によって任意の置換は有限個の巡回置換の積であり、各巡回因子へ (1) を適用すれば互換の積を得る。恒等置換は互換を一つも含まない空積で表される。▨