自由群

1. $x\ne y$ を $X$ の元とする。位数 $2$ の巡回群 $\mathbb{Z}/2\mathbb{Z}$ への写像 $f\colon X\to\mathbb{Z}/2\mathbb{Z}$ を、$f(x)=[1]$、$z\ne x$ に対して $f(z)=[0]$ で定める。普遍性により $\varphi\circ\iota=f$ を満たす準同型 $\varphi$ があり、$\varphi(\iota(x))=[1]\ne[0]=\varphi(\iota(y))$ である。ゆえに $\iota(x)\ne\iota(y)$ である。
2. $H$ を $\iota(X)$ を含む $F$ の部分群とし、$j\colon H\to F$ を包含写像とする。$\iota$ の終域を $H$ に制限した写像 $\iota_H\colon X\to H$ に普遍性を適用すると、$\psi\circ\iota=\iota_H$ を満たす準同型 $\psi\colon F\to H$ が存在する。合成 $j\circ\psi\colon F\to F$ は準同型であり、$(j\circ\psi)\circ\iota=j\circ\iota_H=\iota$ を満たす。一方、恒等写像 $\mathrm{id}_F$ も $\mathrm{id}_F\circ\iota=\iota$ を満たす準同型である。普遍性の一意性の部分（$G=F$、$f=\iota$ の場合）により $j\circ\psi=\mathrm{id}_F$ である。したがって $j$ は全射であり、$H=F$ である。$\square$

$(F,\iota)$ の普遍性を $G=F'$、$f=\iota'$ に適用して、$\theta\circ\iota=\iota'$ を満たす準同型 $\theta\colon F\to F'$ を得る。同様に $(F',\iota')$ の普遍性から $\theta'\circ\iota'=\iota$ を満たす準同型 $\theta'\colon F'\to F$ を得る。合成 $\theta'\circ\theta\colon F\to F$ は $(\theta'\circ\theta)\circ\iota=\theta'\circ\iota'=\iota$ を満たす準同型であり、$\mathrm{id}_F$ も同じ性質を持つので、$(F,\iota)$ の普遍性の一意性により $\theta'\circ\theta=\mathrm{id}_F$ である。同様に $\theta\circ\theta'=\mathrm{id}_{F'}$ である。よって $\theta$ は同型である。$\theta\circ\iota=\iota'$ を満たす準同型は普遍性によりただ一つなので、この同型は一意である。$\square$

既約語 $w=b_1\cdots b_m$ をとる。
(i) $m=0$ または $b_1\ne a^{-1}$ のとき、$L_a(w)=ab_1\cdots b_m$ である。この語の先頭の文字 $a$ は $(a^{-1})^{-1}$ に等しいので、$L_{a^{-1}}$ の定義の第 2 の場合により $L_{a^{-1}}(L_a(w))=b_1\cdots b_m=w$ である。
(ii) $b_1=a^{-1}$ のとき、$L_a(w)=b_2\cdots b_m$ である。$w$ が既約語なので $b_2\ne b_1^{-1}=a$ である（$m=1$ なら $b_2\cdots b_m$ は空語）。したがって $L_{a^{-1}}$ の定義の第 1 の場合により $L_{a^{-1}}(L_a(w))=a^{-1}b_2\cdots b_m=b_1b_2\cdots b_m=w$ である。
以上で $L_{a^{-1}}\circ L_a=\mathrm{id}$ が示された。$a$ を $a^{-1}$ で置き換えれば $L_a\circ L_{a^{-1}}=\mathrm{id}$ も得られる。よって $L_a$ は全単射で、逆写像は $L_{a^{-1}}$ である。$\square$

1. 長さ $n$ に関する数学的帰納法で示す。$n=0$ なら $L_\varepsilon(\varepsilon)=\varepsilon$ である。$n\ge1$ とし、$w=a_1a_2\cdots a_n$ を既約語とする。$w'=a_2\cdots a_n$ も既約語なので、帰納法の仮定により $L_{w'}(\varepsilon)=w'$ である。$w$ が既約語なので $a_2\ne a_1^{-1}$（$n=1$ なら $w'$ は空語）であり、$L_{a_1}$ の定義の第 1 の場合により $L_w(\varepsilon)=L_{a_1}(L_{w'}(\varepsilon))=L_{a_1}(w')=a_1a_2\cdots a_n=w$ である。
2. 語の長さに関する帰納法で示す。$w$ が既約語なら $\rho(w):=w$ とすればよく、1 により $\rho(w)=L_w(\varepsilon)$ である。$w$ が既約語でなければ、ある $i$ について $a_{i+1}=a_i^{-1}$ であり、$w=u\,a_ia_i^{-1}\,v$（$u=a_1\cdots a_{i-1}$、$v=a_{i+2}\cdots a_n$）と書ける。lem-free-group-letter-bijection により $L_{a_i}\circ L_{a_i^{-1}}=\mathrm{id}$ なので
   $$ L_w=L_u\circ L_{a_i}\circ L_{a_i^{-1}}\circ L_v=L_u\circ L_v=L_{uv} $$
   である。$uv$ は $w$ から一回の簡約で得られる、長さ $n-2$ の語である。帰納法の仮定により、$uv$ に簡約を有限回施して得られる既約語 $\rho(uv)$ で $L_{uv}=L_{\rho(uv)}$ かつ $\rho(uv)=L_{uv}(\varepsilon)$ を満たすものがある。$L_w=L_{uv}$ なので、$\rho(w):=\rho(uv)$ とおけば $L_w=L_{\rho(w)}$ かつ $\rho(w)=L_w(\varepsilon)$ である。
   最後の主張を示す。$w$ から簡約を繰り返して既約語 $u$ に到達したとする。上で見たように一回の簡約は $L$ を変えないので $L_w=L_u$ であり、1 により $u=L_u(\varepsilon)=L_w(\varepsilon)$ である。$\square$

$S:=\{L_w\mid w\in W(X)\}\subset\mathrm{Sym}(W(X))$ とおく（各 $L_w$ が全単射であることは、lem-free-group-letter-bijection により全単射の合成だからである）。
(a) $S$ は部分群である。 $L_\varepsilon=\mathrm{id}\in S$ である。$w,w'\in W(X)$ に対し、$L_w\circ L_{w'}=L_{ww'}=L_{\rho(ww')}\in S$ である（連接についての $L_{uv}=L_u\circ L_v$ と lem-free-group-reduction）。$w=a_1\cdots a_n\in W(X)$ に対し $\bar w:=a_n^{-1}\cdots a_1^{-1}$ とおくと、$\bar w$ は既約語である。実際、$\bar w$ の隣り合う文字 $a_{i+1}^{-1},a_i^{-1}$ について $a_i^{-1}=(a_{i+1}^{-1})^{-1}=a_{i+1}$ ならば $a_{i+1}=a_i^{-1}$ となり $w$ の既約性に反する。lem-free-group-letter-bijection により
$$ L_{\bar w}\circ L_w=L_{a_n^{-1}}\circ\cdots\circ L_{a_1^{-1}}\circ L_{a_1}\circ\cdots\circ L_{a_n}=\mathrm{id} $$
であり、同様に $L_w\circ L_{\bar w}=\mathrm{id}$ なので、$L_w^{-1}=L_{\bar w}\in S$ である。よって $S$ は $\mathrm{Sym}(W(X))$ の部分群である。
(b) $w\mapsto L_w$ は $W(X)$ から $S$ への全単射である。 全射は $S$ の定義による。単射は、lem-free-group-reduction の 1 により $L_w=L_{w'}$ ならば $w=L_w(\varepsilon)=L_{w'}(\varepsilon)=w'$ となることによる。
(c) 群構造の移送。 (b) の全単射 $\Lambda\colon W(X)\to S$、$\Lambda(w)=L_w$ によって $S$ の群構造を $W(X)$ に移す。すなわち $w\cdot w':=\Lambda^{-1}(L_w\circ L_{w'})$ と定めれば、$W(X)$ は群になり $\Lambda$ は同型である。(a) で見たように $L_w\circ L_{w'}=L_{\rho(ww')}$ であり $\rho(ww')\in W(X)$ なので、$w\cdot w'=\rho(ww')$ である。これは定理の積の定義と一致する。単位元は $\Lambda^{-1}(\mathrm{id})=\varepsilon$ であり、$w$ の逆元は $\Lambda^{-1}(L_w^{-1})=\Lambda^{-1}(L_{\bar w})=\bar w=a_n^{-1}\cdots a_1^{-1}$ である。$\Lambda$ が単射準同型であることは (b)・(c) による。$\square$

存在。 文字 $a\in X^{\pm}$ に対し $\hat f(a)\in G$ を、$\hat f(x):=f(x)$、$\hat f(x^{-1}):=f(x)^{-1}$ で定める。すると任意の文字 $a$ について $\hat f(a^{-1})=\hat f(a)^{-1}$ である。任意の語 $w=a_1\cdots a_n$（既約とは限らない）に対し
$$ \tilde f(w):=\hat f(a_1)\hat f(a_2)\cdots\hat f(a_n)\in G $$
と定める（$n=0$ なら単位元 $e_G$）。$G$ の積の結合法則により、連接について $\tilde f(uv)=\tilde f(u)\tilde f(v)$ である。また一回の簡約は $\tilde f$ の値を変えない。実際
$$ \tilde f(u\,aa^{-1}\,v)=\tilde f(u)\,\hat f(a)\hat f(a)^{-1}\,\tilde f(v)=\tilde f(u)\tilde f(v)=\tilde f(uv) $$
である。lem-free-group-reduction により $\rho(w)$ は $w$ から有限回の簡約で得られるので、任意の語 $w$ について $\tilde f(\rho(w))=\tilde f(w)$ である。
$\varphi$ を $\tilde f$ の $W(X)=F(X)$ への制限とする。既約語 $w,w'$ に対し
$$ \varphi(w\cdot w')=\tilde f(\rho(ww'))=\tilde f(ww')=\tilde f(w)\tilde f(w')=\varphi(w)\varphi(w') $$
なので $\varphi$ は準同型である。また $\varphi(\iota(x))=\tilde f(x)=\hat f(x)=f(x)$ なので $\varphi\circ\iota=f$ である。
一意性。 $\psi\colon F(X)\to G$ を $\psi\circ\iota=f$ を満たす準同型とする。$\psi$ は準同型なので $\psi(x^{-1})=\psi(\iota(x)^{-1})=\psi(\iota(x))^{-1}=f(x)^{-1}=\hat f(x^{-1})$ であり、したがって任意の文字 $a$ について $\psi(a)=\hat f(a)$ である。既約語 $w=a_1\cdots a_n$ は $F(X)$ の中で長さ $1$ の語の積 $a_1\cdot a_2\cdots a_n$ に等しいので、
$$ \psi(w)=\psi(a_1)\psi(a_2)\cdots\psi(a_n)=\hat f(a_1)\cdots\hat f(a_n)=\varphi(w) $$
である。よって $\psi=\varphi$ である。$\square$

$A$ がアーベル群なので $h([g,g'])=h(g)h(g')h(g)^{-1}h(g')^{-1}=e$ である。よって $h$ の核 $\ker h$ はすべての交換子を含み、部分群なので $[G,G]\subset\ker h$ である。準同型定理（剰余群の普遍性）により、$\bar h([g]):=h(g)$ は well-defined な準同型 $G^{\mathrm{ab}}\to A$ を定め、$h=\bar h\circ\pi$ を満たす。$\pi$ が全射なので、この性質を満たす $\bar h$ は一意である。
後半。$\theta$ は交換子を交換子に写す（$\theta([g,g'])=[\theta(g),\theta(g')]$）ので $\theta([G,G])\subset[G',G']$ であり、$\theta^{-1}$ についても同様なので $\theta([G,G])=[G',G']$ である。よって $[g]\mapsto[\theta(g)]$ は well-defined な準同型 $G^{\mathrm{ab}}\to G'^{\mathrm{ab}}$ であり、$\theta^{-1}$ が誘導する準同型がその逆写像である。$\square$

$F:=F(X)$、$\pi\colon F\to F^{\mathrm{ab}}$ を標準的な全射とする。
(a) $\mathbb{Z}^{(X)}$ の普遍性。 アーベル群 $B$（加法的に書く）と写像 $f\colon X\to B$ に対し、$h(n):=\sum_{x\in X}n_xf(x)$（$n_x\ne0$ となる $x$ は有限個なので有限和）は準同型 $h\colon\mathbb{Z}^{(X)}\to B$ で $h(e_x)=f(x)$ を満たす。任意の $n$ は $n=\sum_xn_xe_x$ と書けるので、$e_x\mapsto f(x)$ を満たす準同型は $h$ に限る。
(b) $F^{\mathrm{ab}}$ の普遍性。 アーベル群 $B$ と写像 $f\colon X\to B$ に対し、自由群の普遍性により $\varphi\circ\iota=f$ を満たす準同型 $\varphi\colon F\to B$ があり、lem-free-group-abelianization により $\varphi=\bar\varphi\circ\pi$ を満たす準同型 $\bar\varphi\colon F^{\mathrm{ab}}\to B$ がある。$\bar\varphi([\iota(x)])=f(x)$ である。$F$ が $\iota(X)$ で生成され $\pi$ が全射なので、$F^{\mathrm{ab}}$ は $\{[\iota(x)]\}_{x\in X}$ で生成され、$[\iota(x)]\mapsto f(x)$ を満たす準同型は $\bar\varphi$ に限る。
(c) 同型の構成。 (a) を $B=F^{\mathrm{ab}}$、$f(x)=[\iota(x)]$ に適用して準同型 $h\colon\mathbb{Z}^{(X)}\to F^{\mathrm{ab}}$、$h(e_x)=[\iota(x)]$ を得る。(b) を $B=\mathbb{Z}^{(X)}$、$f(x)=e_x$ に適用して準同型 $k\colon F^{\mathrm{ab}}\to\mathbb{Z}^{(X)}$、$k([\iota(x)])=e_x$ を得る。$k\circ h$ は各 $e_x$ を固定する準同型なので、(a) の一意性により恒等写像である。$h\circ k$ は各 $[\iota(x)]$ を固定する準同型なので、(b) の一意性により恒等写像である。よって $h$ は同型である。$\square$

後半は、全単射 $\beta\colon X\to Y$ に対し $(F(Y),\iota_Y\circ\beta)$ が $X$ 上の自由群になること（写像 $f\colon X\to G$ に対し $f\circ\beta^{-1}\colon Y\to G$ に $F(Y)$ の普遍性を適用する）と prop-free-group-uniqueness から従う。
前半を示す。同型 $F(X)\cong F(Y)$ は lem-free-group-abelianization によりアーベル化の同型を誘導し、thm-free-group-abelianization-free-abelian により群の同型 $\theta\colon\mathbb{Z}^{(X)}\to\mathbb{Z}^{(Y)}$ を得る。$\theta(2n)=2\theta(n)$ なので $\theta(2\mathbb{Z}^{(X)})\subset2\mathbb{Z}^{(Y)}$ であり、$\theta^{-1}$ についても同様なので $\theta(2\mathbb{Z}^{(X)})=2\mathbb{Z}^{(Y)}$ であり、$\theta$ は剰余群の同型 $\mathbb{Z}^{(X)}/2\mathbb{Z}^{(X)}\cong\mathbb{Z}^{(Y)}/2\mathbb{Z}^{(Y)}$ を誘導する。一方、$n\mapsto(n_x\bmod2)_x$ は全射準同型 $\mathbb{Z}^{(X)}\to(\mathbb{Z}/2\mathbb{Z})^{(X)}$ で、その核は $2\mathbb{Z}^{(X)}$ である。よって準同型定理により
$$ V_X:=(\mathbb{Z}/2\mathbb{Z})^{(X)}\cong\mathbb{Z}^{(X)}/2\mathbb{Z}^{(X)}\cong\mathbb{Z}^{(Y)}/2\mathbb{Z}^{(Y)}\cong(\mathbb{Z}/2\mathbb{Z})^{(Y)}=:V_Y $$
である。
$X$ が有限集合で $|X|=m$ のとき、$V_X$ は $2^m$ 個の元を持つ有限群である。$V_X\cong V_Y$ なので $V_Y$ も有限であり、$Y$ が無限集合なら $V_Y$ は相異なる元 $e_y$（$y\in Y$）を無限個含むので、$Y$ は有限である。$|Y|=m'$ とすれば $2^m=2^{m'}$ なので $m=m'$ であり、$X$ と $Y$ の間に全単射がある。
$X$ が無限集合のとき、上の議論により $Y$ も無限集合である。$V_X$ は位数 $2$ の有限体 $\mathbb{F}_2=\mathbb{Z}/2\mathbb{Z}$ 上のベクトル空間であり、$\{e_x\}_{x\in X}$ はその基底である（任意の元は有限個の $e_x$ の和として一意に書ける）。$V_Y$ についても同様である。加法群の同型 $V_X\to V_Y$ は、$\mathbb{F}_2$ のスカラーが $0,1$ だけなので $\mathbb{F}_2$ 線型な同型でもある。線型同型は基底を基底に写すので、$V_Y$ は $X$ で添字づけられた基底 $\{\theta(e_x)\}$ と $Y$ で添字づけられた基底 $\{e_y\}$ を持つ。ベクトル空間の二つの基底の間には全単射が存在する（次元の一意性、無限次元の場合を含めて Lan02 Chapter III §5）ので、$X$ と $Y$ の間に全単射がある。$\square$

既約語 $v=b_1\cdots b_m$ が巡回既約であるとは、$m\le1$ であるか、または $b_m\ne b_1^{-1}$ であることをいう。
主張。 空でない既約語 $w$ は、既約語 $u$ と空でない巡回既約な既約語 $v$ を用いて、連接 $u\,v\,\bar u$（$\bar u$ は $u$ の文字を逆順に並べて各文字を逆文字に替えたもの）が既約語であるように $w=u\,v\,\bar u$ と書ける。
$w$ の長さ $n$ に関する帰納法で示す。$w$ が巡回既約なら $u:=\varepsilon$、$v:=w$ とすればよい。$w=a_1\cdots a_n$ が巡回既約でなければ $n\ge2$ かつ $a_n=a_1^{-1}$ であり、$n=2$ なら $w=a_1a_1^{-1}$ は既約でないので $n\ge3$ である。$w':=a_2\cdots a_{n-1}$ は長さ $n-2\ge1$ の既約語なので、帰納法の仮定により $w'=u'\,v\,\bar u'$（$v$ は空でない巡回既約語、連接は既約語）と書ける。$u:=a_1u'$ とおくと $\bar u=\bar u'a_1^{-1}=\bar u'a_n$ であり、$w=a_1w'a_n=u\,v\,\bar u$ である。この連接は $w$ そのものなので既約語である。
結論。 $w=u\,v\,\bar u$ を主張のように分解する。$k\ge1$ に対し、連接 $u\,v\,v\cdots v\,\bar u$（$v$ を $k$ 個並べる）が既約語であることを確かめる。$u$、$v$、$\bar u$ の内部と、$u$ と $v$ の境目、$v$ と $\bar u$ の境目は、連接 $u\,v\,\bar u$ が既約語であることから既約である。$v$ と $v$ の境目は、$v=b_1\cdots b_m$ の最後の文字 $b_m$ の次に $b_1$ が来る箇所であり、$m\ge2$ なら巡回既約性 $b_m\ne b_1^{-1}$ により、$m=1$ なら $b_1\ne b_1^{-1}$ により既約である。したがって、この連接は既約語であり、既約化しても変わらない。$\bar u$ は $u$ の逆元なので $w^k=(u\cdot v\cdot\bar u)^k=u\cdot v^k\cdot\bar u$ であり、この既約語に等しく、その長さは $2|u|+k|v|\ge k\ge1$ である。ゆえに $w^k\ne\varepsilon$ である。$\square$