Nielsen–Schreierの定理

右剰余類 $C$ に対し、$C$ に属する元の長さの最小値を $\ell(C)$ とおく。$\ell(C)\le m$ となる剰余類 $C$ の全体に、次の性質をもつ代表元 $t_C\in C$ を $m$ についての帰納法で選ぶ：$t_C$ は長さ $\ell(C)$ の既約語で、その頭の部分はどれも、すでに選んだ代表元である。
$\ell(C)=0$ となるのは $C=H$ だけで、$t_H:=\varepsilon$ とする。$m\ge1$ とし、$\ell(C)\le m-1$ の剰余類には代表元が選ばれているとする。$\ell(C)=m$ の剰余類 $C$ ごとに、長さ $m$ の元 $w\in C$ を 1 つ選び（選択公理を使う）、その既約語の最後の文字を $a$ として $w=ua$（$\lvert u\rvert=m-1$）と書く。
剰余類 $Hu$ について $\ell(Hu)=m-1$ である。実際 $\ell(Hu)\le\lvert u\rvert=m-1$ であり、$v\in Hu$ が $\lvert v\rvert< m-1$ を満たせば $va\in Hua=C$ かつ $\lvert va\rvert\le\lvert v\rvert+1< m$ となって $\ell(C)=m$ に反する。よって $t_{Hu}$ は選ばれていて長さ $m-1$ である。$t_{Hu}a\in Hua=C$ なので $\lvert t_{Hu}a\rvert\ge m$ であり、語の連接 $t_{Hu}a$ の長さは $m$ だから、この連接は簡約されない既約語である（簡約が起これば長さは $m-2$ 以下になる）。$t_C:=t_{Hu}a$ とおくと、その頭の部分は $t_C$ 自身と $t_{Hu}$ の頭の部分なので、性質が保たれる。
すべての剰余類は有限の $\ell(C)$ をもつので、$T:=\{t_C\}$ はすべての剰余類の代表元を 1 つずつ含み、頭の部分で閉じている。$\square$

$h\in H$ を語 $a_1\cdots a_n$（$a_i$ は文字）で表し、$t_i:=\overline{a_1\cdots a_i}$（$0\le i\le n$）とおく。$t_0=\overline{\varepsilon}=\varepsilon$、$t_n=\overline{h}=\varepsilon$ なので、
$$ h=(t_0a_1t_1^{-1})(t_1a_2t_2^{-1})\cdots(t_{n-1}a_nt_n^{-1}) $$
である（隣り合う $t_i^{-1}t_i$ が消える）。$Ht_{i-1}a_i=Ha_1\cdots a_i$ なので $t_i=\overline{t_{i-1}a_i}$ である。
$a_i=x\in X$ ならば $t_{i-1}a_it_i^{-1}=\gamma_{t_{i-1},x}$ である。$a_i=x^{-1}$（$x\in X$）ならば、$Ht_ix=Ht_{i-1}x^{-1}x=Ht_{i-1}$ より $\overline{t_ix}=t_{i-1}$ なので、
$$ t_{i-1}x^{-1}t_i^{-1}=\bigl(t_i\,x\,t_{i-1}^{-1}\bigr)^{-1}=\gamma_{t_i,x}^{-1} $$
である。よって $h$ は Schreier 生成元とその逆元の積である。$\square$

1. $t$ の最後の文字が $x^{-1}$ だとすると、$t=t'x^{-1}$ と書けて $t'\in T$（頭の部分）であり、$tx=t'$ なので $s=\overline{t'}=t'=tx$、すなわち $\gamma_{t,x}=1$ となる。よって連接 $tx$ は既約語である。この既約語が $T$ に属せば $s=\overline{tx}=tx$ となり、やはり $\gamma_{t,x}=1$ である。
2. $s$ の最後の文字が $x$ だとすると、$s=s'x$ と書けて $s'\in T$ であり、$Hs'=Hsx^{-1}=Htxx^{-1}=Ht$ なので $s'=t$、したがって $s=tx$ で $\gamma_{t,x}=1$ となる。よって連接 $sx^{-1}$ は既約語である。これが $T$ に属せば、$Hsx^{-1}=Ht$ から $sx^{-1}=t$、すなわち $s=tx$ となり、$\gamma_{t,x}=1$ である。
3. $t$ と $s^{-1}$ は既約語であり、境目 $t\mid x$ は 1 により、境目 $x\mid s^{-1}$ は 2 により（$xs^{-1}$ は $sx^{-1}$ の逆の語）簡約されない。よって $txs^{-1}$ は既約語である。$\square$

単射性を示す。$F(Y)$ の単位元でない元を既約語 $y_1^{\epsilon_1}\cdots y_m^{\epsilon_m}$（$m\ge1$、$y_i=(t_i,x_i)\in Y$、$\epsilon_i=\pm1$、隣り合う $y_i^{\epsilon_i}y_{i+1}^{\epsilon_{i+1}}$ は $y_{i+1}=y_i$ かつ $\epsilon_{i+1}=-\epsilon_i$ とはならない）とし、その像 $\gamma_1^{\epsilon_1}\cdots\gamma_m^{\epsilon_m}$（$\gamma_i:=\gamma_{t_i,x_i}$）が $1$ でないことを示す。
各因子を次のように書く。$s_i:=\overline{t_ix_i}$ として、$\epsilon_i=1$ なら $u_i:=t_i$、$c_i:=x_i$、$v_i:=s_i$、$\epsilon_i=-1$ なら $u_i:=s_i$、$c_i:=x_i^{-1}$、$v_i:=t_i$ とおく。すると $\gamma_i^{\epsilon_i}$ は既約語 $u_ic_iv_i^{-1}$ で表され、$u_i,v_i\in T$ であり、lem-nielsen-schreier-shape により

• (A) 連接 $u_ic_i$ と $v_ic_i^{-1}$ は既約語で、どちらも $T$ に属さない。
  $c_i$ をこの因子の中心の文字と呼ぶ。積は
  $$ u_1c_1\,(v_1^{-1}u_2)\,c_2\,(v_2^{-1}u_3)\,c_3\cdots(v_{m-1}^{-1}u_m)\,c_m\,v_m^{-1} $$
  と書ける。各 $i< m$ について、$v_i$ と $u_{i+1}$ の共通の頭の部分のうち最長のものを $p_i$ とし、$v_i=p_iv_i'$、$u_{i+1}=p_iu_{i+1}'$ と書く。$v_i^{-1}u_{i+1}$ は $F$ で $r_i:=v_i'^{-1}u_{i+1}'$ に等しく、$p_i$ の最長性から $v_i'$ と $u_{i+1}'$ の先頭の文字は（両方あれば）異なるので、$r_i$ は既約語である。
  語 $W:=u_1c_1r_1c_2r_2\cdots r_{m-1}c_mv_m^{-1}$ が既約語であることを、各境目で確かめる。
• 先頭の $u_1c_1$ と末尾の $c_mv_m^{-1}$ は (A) により既約語である。
• 境目 $c_i\mid r_i$：$v_i'$ が空でなければ、$r_i$ の先頭の文字は $v_i$ の最後の文字の逆であり、$v_ic_i^{-1}$ が既約語なので $v_i$ の最後の文字は $c_i$ でなく、簡約は起きない。$v_i'$ が空で $u_{i+1}'$ が空でなければ、$u_{i+1}=v_iu_{i+1}'$ である。$u_{i+1}'$ の先頭が $c_i^{-1}$ なら、$v_ic_i^{-1}$ は $u_{i+1}\in T$ の頭の部分として $T$ に属し、(A) に反する。
• 境目 $r_i\mid c_{i+1}$：$u_{i+1}'$ が空でなければ、$r_i$ の最後の文字は $u_{i+1}$ の最後の文字で、$u_{i+1}c_{i+1}$ が既約語なので簡約は起きない。$u_{i+1}'$ が空で $v_i'$ が空でなければ、$v_i=u_{i+1}v_i'$ であり、$r_i$ の最後の文字は $v_i'$ の先頭の文字の逆である。それが $c_{i+1}^{-1}$ なら $u_{i+1}c_{i+1}$ は $v_i\in T$ の頭の部分として $T$ に属し、(A) に反する。
• $r_i$ が空のとき（$v_i=u_{i+1}$）：$c_i$ と $c_{i+1}$ が隣り合う。$c_{i+1}=c_i^{-1}$ と仮定する。$\epsilon_i=1$ なら $c_i=x_i\in X$ なので $c_{i+1}=x_i^{-1}$ は $X$ の元ではなく、$\epsilon_{i+1}=-1$、$x_{i+1}=x_i$ である。このとき $v_i=s_i=\overline{t_ix_i}$、$u_{i+1}=s_{i+1}=\overline{t_{i+1}x_i}$ が等しいので $Ht_ix_i=Ht_{i+1}x_i$、よって $Ht_i=Ht_{i+1}$ で $t_i=t_{i+1}$ となる。$\epsilon_i=-1$ のときも同様に $\epsilon_{i+1}=1$、$x_{i+1}=x_i$、$t_i=v_i=u_{i+1}=t_{i+1}$ となる。どちらも $y_{i+1}=y_i$、$\epsilon_{i+1}=-\epsilon_i$ であり、もとの語が既約であることに反する。
  各部分 $u_1$、$r_i$、$v_m^{-1}$ は既約語なので、$W$ は既約語である。$W$ は中心の文字 $c_1,\dots,c_m$ を含むので長さが $m$ 以上（$m\ge1$）であり、$F$ の単位元ではない。$W$ は $F$ で $\gamma_1^{\epsilon_1}\cdots\gamma_m^{\epsilon_m}$ に等しいので、これは $1$ でない。
  よって $\Phi$ の核は自明で、$\Phi$ は同型である。$\Phi$ が単射なので、$Y$ の相異なる元は相異なる $\gamma_{t,x}$ に写る。$\square$

$T$ は $k$ 個の元からなるので、$T\times X$ は $kn$ 個の元をもつ。$\gamma_{t,x}=1$ となる組 $(t,x)$ が $k-1$ 個であることを、$T\setminus\{\varepsilon\}$ からの全単射を作って示す。$t\in T\setminus\{\varepsilon\}$ の最後の文字で場合を分ける。

• 最後の文字が $x\in X$ のとき：$t=t'x$、$t'\in T$ と書き、$t$ に組 $(t',x)$ を対応させる。$t'x=t\in T$ なので $\overline{t'x}=t'x$ で、$\gamma_{t',x}=1$ である。
• 最後の文字が $x^{-1}$（$x\in X$）のとき：$t$ に組 $(t,x)$ を対応させる。$t=t''x^{-1}$、$t''\in T$ と書けば $tx=t''\in T$ なので $\gamma_{t,x}=1$ である。
  前者の組 $(t',x)$ では $t'$ の最後の文字は $x^{-1}$ でなく（$t'x$ が既約）、後者の組 $(t,x)$ では $t$ の最後の文字が $x^{-1}$ なので、両者の像は重ならない。それぞれの場合の中では $t$ が組から復元できるので、この対応は単射である。
  全射を示す。$\gamma_{t,x}=1$、すなわち $tx=\overline{tx}$ とする。$t$ の最後の文字が $x^{-1}$ なら後者の像である。そうでなければ連接 $tx$ は既約語で、$F$ の元として既約語 $\overline{tx}\in T$ に等しい。既約語の一意性から $tx=\overline{tx}$ は語として等しく $tx\in T$ となり、$(t,x)$ は前者の $tx$ の像である。
  以上で自明な組は $k-1$ 個あり、$\lvert Y\rvert=kn-(k-1)=k(n-1)+1$ である。階数の一意性により $H$ の階数はこの値である。$\square$

要点：$N$ が有限生成なら木でない矢印は有限個で、それらの端点と基点を結ぶ部分 $P$ は有限である。指数が無限なので $P$ の外に点がある。正規性により、その点から巡回既約な語 $w\ne1$ を読むと閉じた道になるが、道の中で $P$ の外の最も深い点では引き返すしかなく、巡回既約性に反する。