語の問題(群論)

$S$ は $G$ を生成するので、各 $s'\in S'$ について $\overline{u_{s'}}=s'$ となる $S$ 上の語 $u_{s'}$ がある。$u_{s'}=b_1\cdots b_m$ に対し $u_{s'}^{-1}:=b_m^{-1}\cdots b_1^{-1}$（$(s^{-1})^{-1}:=s$）とおくと $\overline{u_{s'}^{-1}}=s'^{-1}$ である。$S'$ 上の語 $w$ の各文字 $s'$、$s'^{-1}$ をそれぞれ $u_{s'}$、$u_{s'}^{-1}$ に置き換えた $S$ 上の語を $\tau(w)$ とすると、$\overline{\tau(w)}=\overline{w}$ である。$S'$ は有限なので、語 $u_{s'}$ の有限個の表を持っておけば $w\mapsto\tau(w)$ は計算できる。よって「$\tau(w)$ を作り、$S$ に関する判定の手続きにかける」という手続きが $W(G,S')$ を決定する。$\square$

$S$ を $G$ の有限な生成系、$T$ を $H$ の有限な生成系とする。$S\cup T$ も $G$ の有限な生成系なので、prop-wp-generators により $W(G,S\cup T)$ は決定可能である。$T$ 上の語は $S\cup T$ 上の語でもあり、$H$ で計算した値と $G$ で計算した値は同じなので、$W(H,T)=W(G,S\cup T)\cap\{T\text{ 上の語}\}$ である。語が $T$ の文字だけからなるかは判定できるので、$W(H,T)$ は決定可能である。$\square$

$N(R)$ は、$R$ の元とその逆元の共役 $uru^{-1}$（$u\in F(X)$）の有限個の積の全体である。そのような積の形の語 $u_1r_1^{\pm1}u_1^{-1}\cdots u_kr_k^{\pm1}u_k^{-1}$（$k\ge0$、$u_i$ は語、$r_i\in R$）は、全体の長さの小さい順に 1 つずつ列挙できる。語 $w$ が与えられたら、この列挙を進めながら、各語と $w$ をそれぞれ既約化（隣り合う $ss^{-1}$、$s^{-1}s$ を消せなくなるまで消す操作）して比べ、一致したら止まる。自由群では 2 つの語が同じ元を表すことと既約化が一致することは同値なので（自由群 の定理「既約語の群」）、この手続きは $w\in N(R)$、すなわち $\overline{w}=1$ のときちょうど止まる。後半は、集合が決定可能であることと、その集合と補集合がともに半決定可能であることが同値であること（停止問題 の定理「決定可能性と半決定可能性」）による。$\square$

$S$ を $G$ の有限な生成系、$1=c_1,c_2,\dots,c_k$ を $H$ の左剰余類 $cH$ の代表系とする。各文字 $a\in S\cup S^{-1}$（$G$ の元と読む）と各 $i$ について、$ac_i$ の属する左剰余類を $c_{\sigma_a(i)}H$ とし、
$$ ac_i=c_{\sigma_a(i)}\,h_{a,i},\qquad h_{a,i}\in H $$
と書く。$T:=\{h_{a,i}\}$ は有限集合である。
語 $w=a_1\cdots a_\ell$ について、右端から $i_\ell:=\sigma_{a_\ell}(1)$、$i_{j}:=\sigma_{a_j}(i_{j+1})$ と剰余類の番号を定めると、等式を繰り返し使って
$$ \overline{w}=a_1\cdots a_\ell\,c_1=c_{i_1}\,h_{a_1,i_2}\,h_{a_2,i_3}\cdots h_{a_\ell,1} $$
（$i_{\ell+1}:=1$ とおき、$h_{a_j,i_{j+1}}$ を並べる）となる。$\overline{w}\in H$ なら $c_{i_1}\in H$、すなわち $i_1=1$ なので、$H$ の元はすべて $T$ の元の積で書ける。よって $T$ は $H$ の有限な生成系である。
$\overline{w}=1$ であるのは、$i_1=1$ で、かつ $T$ 上の語 $h_{a_1,i_2}\cdots h_{a_\ell,1}$ が $H$ の単位元を表すときに限る（$i_1\ne1$ なら $\overline{w}\notin H$）。番号 $i_j$ と $T$ 上の語は、$\sigma_a$ と $h_{a,i}$ の有限個の表から計算できるので、$H$ の語の問題を解く手続きと合わせて $W(G,S)$ が決定できる。$\square$

語 $w$ が与えられたとき、次の 2 つの手続きを交互に 1 段ずつ進める。
(1) prop-wp-enumerable の手続き。$\overline{w}=1$ のとき、かつそのときに限り止まる。
(2) $m=1,2,3,\dots$ の順に、集合 $\{1,\dots,m\}$ の上の乗積表で群の公理を満たすものを列挙し（各 $m$ について有限個）、得られた各有限群 $Q$ と各写像 $f\colon X\to Q$（有限個）について、$R$ の各元の $Q$ での値を計算する。すべて単位元なら、$f$ は準同型 $\bar f\colon G\to Q$ に延びる（群の表示 の命題「表示からの準同型」）。そのうえで $\bar f(\overline{w})\ne1$ なら止まる。
$\overline{w}=1$ なら、どの準同型も $\overline{w}$ を単位元に写すので (2) は止まらず、(1) が止まる。$\overline{w}\ne1$ なら (1) は止まらない。一方、剰余有限性から有限群 $Q$ への準同型 $\pi$ で $\pi(\overline{w})\ne1$ となるものがあり、$Q$ は $m=\lvert Q\rvert$ の段で列挙される乗積表のどれかと同型で、$\pi$ は生成元の像 $f=\pi|_X$ で決まるので、(2) がいずれ止まる。よって「(1) が止まれば $\overline{w}=1$、(2) が止まれば $\overline{w}\ne1$ と答える」手続きは、どの $w$ でも止まって正しく答える。$\square$

$g_i$ と $g_i^{-1}$ の成分（有限個の有理数）を表として持つ。語 $w=a_1\cdots a_\ell$ が与えられたら、行列の積 $a_1a_2\cdots a_\ell$ を、有理数の四則演算（整数の組の計算）で正確に計算し、単位行列 $I$ と成分ごとに比べる。積は $\ell-1$ 回の行列の掛け算で、有理数の加法と乗法は有限回の整数演算で行えるので、この手続きは必ず止まる。$\overline{w}=1$ は、計算した行列が $I$ に等しいことにほかならない。$\square$