Higmanの埋め込み定理(Higman embedding theorem)とは、有限生成の群が有限表示群の部分群と同型になるのは、その群が帰納的に表示されるとき、すなわち有限個の生成元と帰納的可算な関係子の集合による表示をもつときであり、そのときに限るという定理である。必要性は、有限表示群で単位元を表す語が機械的に列挙できることから従う。HNN拡大の構成で可算群を2元で生成される群に埋め込むと、帰納的に表示される可算群も有限表示群に埋め込める。帰結として、すべての有限表示群を部分群に含む有限表示群と、語の問題が解けない有限表示群が存在する。
Higman の埋め込み定理(Higman embedding theorem)は、有限生成の群が有限表示群の部分群として実現できるのは、その群の関係が機械的に数え上げられるときであり、そのときに限る、という定理である。G. Higman が 1961 年に証明したHig61。有限個の生成元と関係式で書ける群の部分群という群論の性質が、関係の集合が帰納的可算であるという計算可能性の性質とちょうど一致する。群の言葉で計算を書き表せることを示す代表的な結果である。
この記事では、主定理の易しい方向と、有限生成でない群に主定理を使うための Higman–Neumann–Neumann の埋め込み(可算群は 2 元で生成される群に埋め込める)を完全に証明する。主定理の難しい方向は証明しないが、それを使って、すべての有限表示群を部分群に含む有限表示群と、語の問題が解けない有限表示群の存在を導く。名前の似た Higmanの補題 は、語の部分列の順序についての別の定理である。
群の表示 $\langle X\mid R\rangle=F(X)/N(R)$ の記法は 群の表示 に従う。$F(X)$ は $X$ 上の自由群、$N(R)$ は $R$ の正規閉包である。語は 語の問題(群論) の定義のとおり自然数で番号付けし、語の集合が帰納的可算であるとは、番号の集合がそうであることをいう。生成元が可算無限個 $x_0,x_1,\dots$ のときも、文字 $x_i^{\pm1}$ を $(i,\pm1)$ の番号で書いて同じように番号付けする。
群の表示 $\langle X\mid R\rangle$ で、$X$ が有限集合または $\{x_0,x_1,\dots\}$ であり、関係子の集合 $R$ が帰納的可算であるものを 帰納的な表示(recursive presentation)という。帰納的な表示をもつ群を 帰納的に表示される群 という。
$R$ が帰納的可算で $r_0,r_1,\dots$ と列挙されるなら、$r_k$ を語 $r_k(x_0x_0^{-1})^k$ に替えた集合は同じ正規閉包をもち、語の長さを見れば所属を判定できる。この意味で、帰納的可算を決定可能に替えても同じ群の族になる。名前の「帰納的」はこれによる。
有限生成の群については、この性質を語の問題の言葉で言い換えられる。$S$ を群 $G$ の有限な生成系とし、$S$ 上の語のうち $G$ で単位元を表すものの集合を $W(G,S)$ と書く(語の問題(群論) の定義「語の問題」)。
$G$ を有限生成の群、$S$ をその有限な生成系とする。$G$ が帰納的に表示されることと、$W(G,S)$ が帰納的可算であることは同値である。特に、帰納的に表示されるかは有限な生成系の選び方によらない。
$W(G,S)$ が帰納的可算なら、$\langle S\mid W(G,S)\rangle$ が $G$ の帰納的な表示である。実際、自然な全射 $F(S)\to G$ の核は、$W(G,S)$ の語が表す $F(S)$ の元の全体であり、これは核自身なので正規閉包をとっても変わらない。
逆に $G=\langle X\mid R\rangle$ を帰納的な表示とする。$R$ の列挙と並行して、すでに列挙した $r\in R$ とその逆の共役の有限個の積 $u_1r_1^{\pm1}u_1^{-1}\cdots u_kr_k^{\pm1}u_k^{-1}$ を 1 つずつ列挙できる(各段で、列挙済みの関係子と長さの上限を 1 つずつ増やす)。語の問題(群論) の命題「有限表示群の単位元を表す語」の証明と同じく、語 $w$ の既約化がそのどれかの既約化と一致するまで探せば、$w\in N(R)$ のときちょうど止まる(自由群 の定理「既約語の群」)。よって $X$ 上の語で単位元を表すものの集合は帰納的可算である。
$X$ が有限でなくても、$G$ は有限な $S$ で生成されるので、各 $s\in S$ の像を表す $X$ 上の語 $v_s$ を 1 つずつ固定できる。$S$ 上の語 $w$ の文字 $s^{\pm1}$ を $v_s^{\pm1}$ に置き換えた語を $\tau(w)$ とすると、$w$ と $\tau(w)$ は $G$ の同じ元を表す。$S$ は有限なので $\tau$ は計算でき、$w\in W(G,S)\iff\tau(w)\in N(R)$ である。右辺が半決定可能なので、$W(G,S)$ は帰納的可算である。$\square$
有限表示群は帰納的に表示される。有限生成でない例として、
$$
Q:=\langle x_1,x_2,\dots\mid x_ix_jx_i^{-1}x_j^{-1}\ (i,j\ge1),\ \ x_n^{\,n}x_{n-1}^{-1}\ (n\ge2)\rangle
$$
を考える。関係子の集合は決定可能である。$x_n\mapsto1/n!$ は関係を保つので準同型 $Q\to(\mathbb Q,+)$ を定め、$1/N!$ たちが $\mathbb Q$ を生成するので全射である。$Q$ は可換で、$n\le N$ なら $x_n=x_N^{N!/n!}$ だから、$Q$ の元は $x_N^{c}$($c\in\mathbb Z$)と書ける。これが $0$ に写れば $c/N!=0$ で $c=0$ である。よって $Q\cong\mathbb Q$ であり、thm-he-hnn と主定理を合わせると、$\mathbb Q$ も有限表示群に埋め込める。
有限生成の群 $G$ について、次は同値である。
この形の主張は Mik23 の Theorem 1.1 による(そこでは Higman の原論文の Theorem 1 として引かれている)。1 ⇒ 2 は次の命題で証明する。2 ⇒ 1 はこの記事では証明しない。証明の筋道は後の節「難しい方向の証明の筋道」で述べる。
有限表示群 $H$ の有限生成部分群は、帰納的に表示される。
$H=\langle Y\mid Q\rangle$ を $Y$、$Q$ がともに有限な表示とし、$G\le H$ を有限な生成系 $S$ で生成される部分群とする。各 $s\in S$ について、$H$ で $s$ を表す $Y$ 上の語 $v_s$ を固定し、$S$ 上の語 $w$ の文字 $s^{\pm1}$ を $v_s^{\pm1}$ に置き換えた語を $\tau(w)$ とする。$w$ が $G$ で表す元と $\tau(w)$ が $H$ で表す元は同じなので、
$$
w\in W(G,S)\iff\tau(w)\in W(H,Y)
$$
である。$W(H,Y)$ は 語の問題(群論) の命題「有限表示群の単位元を表す語」により半決定可能で、$\tau$ は計算できるので、$W(G,S)$ は帰納的可算である。lem-he-wordset により $G$ は帰納的に表示される。単射準同型 $G\to H$ があれば $G$ はその像と同型なので、主定理の 1 ⇒ 2 が従う。$\square$
主定理は有限生成の群についての定理だが、任意の可算群を 2 元で生成される群に埋め込めば、有限生成でない群にも使える。これは Higman、B. H. Neumann、H. Neumann によるHNN49(CV18 §1 の引用による)。この節では、帰納的な表示が保たれることまで含めて証明する。以下、自由群 $F(a,b)$ の元
$$
u_i:=a^{-i}ba^{i}\qquad(i\ge0)
$$
を使う。$u_0=b$ である。
$\{u_i\}_{i\ge0}$ は、それが生成する $F(a,b)$ の部分群の自由基底である。さらに、$S\subseteq\mathbb N$ と $n\in\mathbb N$ について、$u_n\in\langle u_i\mid i\in S\rangle$ となるのは $n\in S$ のときに限る。
$u_i^{\pm1}$ の積で、隣り合う $u_i^{\varepsilon}u_i^{-\varepsilon}$ を含まないものをとる。同じ添字が続くところをまとめると、
$$
w=u_{j_1}^{m_1}u_{j_2}^{m_2}\cdots u_{j_r}^{m_r}\qquad(r\ge1,\ m_l\ne0,\ j_l\ne j_{l+1})
$$
の形になる。$u_j^{m}=a^{-j}b^{m}a^{j}$ なので、$F(a,b)$ では
$$
w=a^{-j_1}\,b^{m_1}\,a^{j_1-j_2}\,b^{m_2}\,a^{j_2-j_3}\cdots a^{j_{r-1}-j_r}\,b^{m_r}\,a^{j_r}
$$
である。$b$ の指数 $m_l$ も、間の $a$ の指数 $j_l-j_{l+1}$ もすべて $0$ でないので、右辺は既約語であり(両端の $a^{-j_1}$、$a^{j_r}$ は $0$ 乗なら省く)、$r\ge1$ だから空でない。自由群 の定理「既約語の群」から $w\ne e$ で、$\{u_i\}$ は自由基底である。
後半について、$u_n\in\langle u_i\mid i\in S\rangle$ とすると、$u_n$ は上の形の $w$ で、すべての $j_l$ が $S$ に属するもので書ける。$u_n$ の既約語は $a^{-n}ba^{n}$ で、$b$ を 1 回だけ含む。既約語は一意なので、$w$ の既約語と比べて $r=1$、$m_1=1$、$a^{-j_1}=a^{-n}$ となり、$n=j_1\in S$ である。逆は明らかである。$\square$
$a$ と $b$ を入れ替える $F(a,b)$ の自己同型で写すと、$v_i:=b^{-i}ab^{i}$($i\ge0$)についても同じことが成り立つ。
可算群 $G$ は、2 元で生成されるある群 $K$ の部分群と同型である。さらに、$G$ が帰納的な表示 $\langle g_1,g_2,\dots\mid R\rangle$ をもつなら、$K$ として、2 つの生成元 $a,t$ をもつ帰納的な表示の群をとれる。
$G$ を生成する元の列 $g_1,g_2,\dots$ をとる($G$ の元を全部並べてもよい。有限個しかなければ単位元を繰り返す。帰納的な表示の生成元が有限個なら、生成元 $g_j$ と関係子 $g_j$ を足して無限個にする)。$g_0:=e$ とおく。自由積 $H:=G\ast F(a,b)$ の中で、
$$
v_i:=b^{-i}ab^{i},\qquad y_i:=g_i\,u_i=g_i\,a^{-i}ba^{i}\qquad(i\ge0)
$$
とし、$A:=\langle v_i\mid i\ge0\rangle$、$B:=\langle y_i\mid i\ge0\rangle$ とおく。
$A$、$B$ は $\{v_i\}$、$\{y_i\}$ を基底とする自由群である。 $A$ については lem-he-free の後の注意による。$B$ については、$G$ を潰して $F(a,b)$ を動かさない準同型 $\pi\colon H\to F(a,b)$(自由積 の命題「自由積は群の圏の余積」)を使う。記号 $z_0,z_1,\dots$ 上の自由群から $H$ への準同型 $\beta\colon z_i\mapsto y_i$ を考えると、$\pi\circ\beta$ は $z_i\mapsto u_i$ で、lem-he-free により単射である。よって $\beta$ も単射であり、$B$ は $\{y_i\}$ を基底とする自由群である。したがって $\varphi(v_i):=y_i$ は同型 $\varphi\colon A\to B$ を定める。
HNN 拡大をとる。 $K:=H\ast_\varphi$ とし、安定文字を $t$ とする。HNN拡大 の系「底群の埋め込み」と、自由積が因子を含むことから、$G\to H\to K$ は単射である。$K$ では $tv_it^{-1}=y_i$ なので、$i=0$ から $tat^{-1}=b$、$i\ge1$ から
$$
g_i=t\,v_i\,t^{-1}\,u_i^{-1}=t\,b^{-i}ab^{i}\,t^{-1}\,a^{-i}b^{-1}a^{i}
$$
が成り立つ。$H$ は $G$ と $a,b$ で生成されるので、$K$ は $a,t$ で生成される。
帰納的な表示。 $G=\langle g_1,g_2,\dots\mid R\rangle$ とすると、自由積 の系「群の表示による自由積の記述」と HNN拡大 の定義の後の注意(結合部分群の生成系で関係を書けばよい)により
$$
K=\langle g_1,g_2,\dots,a,b,t\mid R,\ \ t\,v_i\,t^{-1}=g_i\,u_i\ (i\ge0)\rangle
$$
である。$F(a,t)$ の元を $\bar b:=tat^{-1}$、$\gamma_0:=e$、$\gamma_i:=t\,\bar b^{-i}a\bar b^{i}\,t^{-1}\,a^{-i}\bar b^{-1}a^{i}$($i\ge1$)で定め、$R$ の語の $g_i$ に $\gamma_i$ を代入した語の集合を $R'$ とする。代入は計算できるので $R'$ は帰納的可算である。$L:=\langle a,t\mid R'\rangle$ とおく。
$g_i\mapsto\gamma_i$、$a\mapsto a$、$b\mapsto\bar b$、$t\mapsto t$ は $K$ の関係を保つ。$R$ の語は $R'$ の語に写り、$tv_it^{-1}=g_iu_i$ は $F(a,t)$ の中で $t\,\bar b^{-i}a\bar b^{i}\,t^{-1}=\gamma_i\,a^{-i}\bar ba^{i}$ に写るが、これは $\gamma_i$ の定義そのものである($i=0$ では $tat^{-1}=\bar b$)。よって準同型 $\psi\colon K\to L$ が定まる(群の表示 の命題「表示からの準同型」)。逆に $a\mapsto a$、$t\mapsto t$ は、$K$ で $\gamma_i=g_i$ なので $R'$ の語を単位元に写し、準同型 $\chi\colon L\to K$ を定める。$\psi\chi$ は生成元 $a,t$ を、$\chi\psi$ は生成元 $g_i,a,b,t$ をそれぞれ動かさないので、$K\cong L$ である。$\square$
主定理の 2 ⇒ 1 を認めると、次の 2 つが従う。どちらも主定理と thm-he-hnn を組み合わせるだけで証明できる。
有限表示群 $U$ で、すべての有限表示群を部分群として含むものが存在する。$U$ は、帰納的に表示される有限生成の群もすべて部分群として含む。
記号 $x_1,x_2,\dots$ の上の有限表示 $\langle x_1,\dots,x_m\mid r_1,\dots,r_k\rangle$ を機械的に $P_1,P_2,\dots$ と列挙し、$P_n$ の表す群を $G_n$ とする。$P_n$ の記号 $x_j$ を $x_{n,j}$ に付け替えて全部並べた表示は、生成元が可算個で関係子の集合が帰納的可算(実は決定可能)であり、自由積 の系「群の表示による自由積の記述」により自由積 $G:=\ast_nG_n$ を表す。各 $G_n$ は $G$ の部分群である。thm-he-hnn により $G$ は 2 元で生成される帰納的に表示される群に埋め込まれ、主定理によりそれはある有限表示群 $U$ に埋め込まれる。有限表示群は $G_n$ のどれかと同型なので $U$ に含まれる。帰納的に表示される有限生成の群は主定理によりある有限表示群に埋め込まれるので、やはり $U$ に含まれる。$\square$
次の系は 語の問題(群論) の定理「Novikov–Boone の定理」と同じ結論である。$S\subseteq\mathbb N$ について、群
$$
G_S:=\langle a,b,t\mid t\,u_i\,t^{-1}=u_i\ (i\in S)\rangle
$$
を考える。これは $F(a,b)$ の、$C_S:=\langle u_i\mid i\in S\rangle$ の恒等写像による HNN 拡大である(HNN拡大 の定義の後の注意)。
$G_S$ で $t\,u_n\,t^{-1}=u_n$ となるのは $n\in S$ のときに限る。
$n\in S$ なら定義の関係である。$n\notin S$ とすると、lem-he-free により $u_n\notin C_S$ である。語 $t\,u_n\,t^{-1}u_n^{-1}$ は安定文字を 2 つ含み、その間の $u_n$ が結合部分群 $C_S$ に属さないので、挟み込みをもたない。HNN拡大 の系「Britton の補題」により、この語は $G_S$ で単位元でない。$\square$
語の問題が解けない有限表示群が存在する。
$K:=\{e\mid\varphi_e(e)\!\downarrow\}$ を自己停止集合とする(帰納的可算集合 の例「帰納的可算集合の例」)。$K$ は帰納的可算なので、$G_K$ の関係子の集合 $\{t u_it^{-1}u_i^{-1}\mid i\in K\}$ も帰納的可算で、$G_K$ は帰納的に表示される。主定理により $G_K$ はある有限表示群 $H$ に埋め込まれる。$H$ の語の問題が解けるとすると、語の問題(群論) の命題「有限生成部分群」により $G_K$ の語の問題も解ける。すると lem-he-gs により、$n$ に対して語 $tu_nt^{-1}u_n^{-1}$ を作って判定すれば $n\in K$ が決定できる。これは $K$ が決定可能でないことに反する。$\square$
2 ⇒ 1 の証明はこの記事では行わない。Higman の原論文の流れは、Mik23 §1.1 によれば次のとおりである。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 関係子の集合が帰納的可算 | $G_{\mathbb N\setminus K}$ | 主定理の 1(有限表示群への埋め込み) |
| 群が可算 | 実数の加法群 $(\mathbb R,+)$ | thm-he-hnn の結論(2 元で生成される群への埋め込み) |
| 埋め込み先が有限表示(必要性の方向) | $G_{\mathbb N\setminus K}$ を 2 元で生成される群に埋め込む | prop-he-necessity(部分群は帰納的に表示される) |
| $u_i$ が自由基底 | $u_i$ を $b^{i}$ に替え、$S=\{2,3\}$、$n=5$ | lem-he-free の後半 |
帰納的可算。 $G_{\mathbb N\setminus K}$ は 3 元で生成される可算群である。有限表示群に埋め込めたとすると、prop-he-necessity と lem-he-wordset により $W(G_{\mathbb N\setminus K},\{a,b,t\})$ は帰納的可算で、lem-he-gs により $\mathbb N\setminus K=\{n\mid tu_nt^{-1}u_n^{-1}\in W\}$ も帰納的可算になる。これは 帰納的可算集合 の系「補集合が帰納的可算でない集合」に反する。関係子の集合 $\{tu_it^{-1}u_i^{-1}\mid i\notin K\}$ は帰納的可算でなく、別の帰納的な表示もない。
可算。 有限表示群は可算個の語の類からなるので可算であり、その部分群も可算である。非可算な $\mathbb R$ はどの有限表示群にも、どの有限生成の群にも埋め込めない。
埋め込み先が有限表示。 thm-he-hnn の前半により $G_{\mathbb N\setminus K}$ は 2 元で生成される群 $K'$ に埋め込める。$K'$ は有限生成だが、その有限生成部分群 $G_{\mathbb N\setminus K}$ は、上で見たとおり帰納的に表示されない。prop-he-necessity で $H$ を有限生成の群に弱めると成り立たない。
自由基底。 $\langle b^2,b^3\rangle$ は $b=b^3b^{-2}$ を含むので $b^5$ を含むが、$5\notin\{2,3\}$ である。$b^i$ は自由基底でなく($b^2$ と $b^3$ は可換)、prf-he-free の既約語の比較が使えない。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する