置換

$X$ の元が高々 $2$ 個なら、$X$ の置換は恒等置換 $e$ と（元が 2 個のときの）互換 $s$ だけであり、$es=s=se$ なのでどの 2 元も可換である。$X$ が相異なる元 $a,b,c$ をもつとする。互換 $(a\,b)$ と $(b\,c)$ について、右から施すと $(a\,b)(b\,c)$ は $c\mapsto b\mapsto a$ と $c$ を $a$ に移し、$(b\,c)(a\,b)$ は $c\mapsto c\mapsto b$ と $c$ を $b$ に移す。$a\ne b$ なので $(a\,b)(b\,c)\ne(b\,c)(a\,b)$ である。$\square$

$x\in A$ とする。$\sigma(x)\notin A$ なら $\sigma(\sigma(x))=\sigma(x)$ であり、$\sigma$ の単射性から $\sigma(x)=x$ となって $x\in A$ に反する。よって $\sigma(x)\in A$ である。
$\sigma\tau(x)=\tau\sigma(x)$ をすべての $x\in X$ について示す。$x\in A$ なら、$x\notin B$ なので $\tau(x)=x$ であり、$\sigma(x)\in A$ も $B$ に属さないので $\tau(\sigma(x))=\sigma(x)$ である。よって $\sigma\tau(x)=\sigma(x)=\tau\sigma(x)$ である。$x\in B$ の場合は $\sigma$ と $\tau$ の役割を入れ替えて同様である（前段と同じ理由で $\tau$ は $B$ を $B$ に移す）。$x$ が $A$ にも $B$ にも属さなければ、両辺とも $x$ である。$\square$

存在を示す。$x\in X$ をとる。$X$ は有限なので $x,\sigma(x),\sigma^2(x),\dots$ のうちに等しいもの $\sigma^i(x)=\sigma^j(x)$（$0\le i< j$）があり、両辺に $\sigma^{-i}$ を施すと $\sigma^{j-i}(x)=x$ である。そこで $\sigma^\ell(x)=x$ となる最小の $\ell\ge1$ を $\ell(x)$ とおく。$\ell=\ell(x)$ について $x,\sigma(x),\dots,\sigma^{\ell-1}(x)$ は相異なる。実際、$\sigma^i(x)=\sigma^j(x)$（$0\le i< j<\ell$）なら $\sigma^{j-i}(x)=x$、$0< j-i<\ell$ となって $\ell$ の最小性に反する。任意の整数 $m$ を $m=q\ell+r$（$0\le r<\ell$）と書くと $\sigma^m(x)=\sigma^r(x)$ なので、
$$ O(x):=\{\sigma^m(x)\mid m\in\mathbb{Z}\}=\{x,\sigma(x),\dots,\sigma^{\ell-1}(x)\} $$
であり、$|O(x)|=\ell(x)$ である。$O(x)$ を $x$ の 軌道 という。2 つの軌道 $O(x),O(y)$ が元 $z=\sigma^a(x)=\sigma^b(y)$ を共有すれば $y=\sigma^{a-b}(x)\in O(x)$ なので $O(y)\subset O(x)$ であり、同様に $O(x)\subset O(y)$ である。よって $X$ は互いに交わらない軌道に分かれる（軌道が群の作用の軌道の、$\sigma$ の冪による場合であることは 群の作用 の記事の命題「軌道による分割と安定化群」も参照）。
元が $2$ 個以上の軌道 $O$ ごとに、その元 $x$ を 1 つ選んで
$$ c_O:=(x\ \ \sigma(x)\ \ \cdots\ \ \sigma^{\ell-1}(x))\qquad(\ell=|O|) $$
とおく。$c_O$ の台は $O$ なので、異なる軌道の $c_O$ は互いに素であり、lem-perm-disjoint-commute によりどの順序で掛けても同じ置換 $\pi$ を与える。$\pi=\sigma$ を示す。$y\in X$ をとる。$y$ の軌道が 1 元なら $\sigma(y)=y$ であり、どの $c_O$ も $y$ を動かさないので $\pi(y)=y$ である。$y$ が元 $2$ 個以上の軌道 $O$ に属するなら、$y=\sigma^i(x)$（$0\le i<\ell$）と書けて、$c_O(y)=\sigma^{i+1}(x)=\sigma(y)$ である（$i=\ell-1$ のときも $\sigma^\ell(x)=x$ なので正しい）。$O$ 以外の軌道の $c_{O'}$ は $y$ と $\sigma(y)\in O$ を動かさないので、$\pi$ を「$c_O$ 以外を先に、$c_O$ を最後に」施す積と見て $\pi(y)=c_O(y)=\sigma(y)$ である。よって $\pi=\sigma$ である。
一意性を示す。$\sigma=d_1d_2\cdots d_r$ を互いに素な長さ $2$ 以上の巡回置換の積とし、$d_i=(b_1\,b_2\,\cdots\,b_k)$ とする。他の $d_j$（$j\ne i$）は $d_i$ の台 $\{b_1,\dots,b_k\}$ の元を動かさないので、上と同様に $\sigma(b_t)=d_i(b_t)=b_{t+1}$（添字は $k$ を法として読む）である。よって $b_1$ の $\sigma$ による軌道は $\{b_1,\dots,b_k\}$ であり、$d_i=(b_1\ \ \sigma(b_1)\ \ \cdots\ \ \sigma^{k-1}(b_1))$ はその軌道の巡回置換 $c_O$ に一致する。逆に、元 $2$ 個以上の軌道 $O$ の元 $y$ は $\sigma$ で動くので、ある $d_i$ の台に属し、その $d_i$ は $y$ の軌道の巡回置換 $c_O$ に等しい。したがって $\{d_1,\dots,d_r\}$ は $\{c_O\}$ の全体に一致し、分解は積の順序を除いて一意である。$\square$

$\rho:=(a_k\,a_{k-1}\,\cdots\,a_1)$ は $a_{t+1}\mapsto a_t$（添字は $k$ を法として読む）と移し、他の元を動かさない。$c:=(a_1\,\cdots\,a_k)$ について、$\rho c(a_t)=\rho(a_{t+1})=a_t$、$c\rho(a_t)=c(a_{t-1})=a_t$ であり、$\{a_1,\dots,a_k\}$ の外の元はどちらも動かさないので $\rho c=c\rho=e$、すなわち $c^{-1}=\rho$ である。後半について、$(c_1\cdots c_r)^{-1}=c_r^{-1}\cdots c_1^{-1}$ であり、$c_i^{-1}$ の台は $c_i$ の台と同じなので互いに素であり、lem-perm-disjoint-commute により並べる順序によらない。$\square$