符号付き文字列が自由群であることの証明

　この記事では符号付き文字列というものを導入し、これが自由群であることを証明します。そのために、次のような順序を踏みます。
（１）符号付き文字列の始代数による整理
（２）指数関数、連接・逆連接、挿入関数の定義
（３）諸性質の整理
（４）群であることの証明
（５）自由であることの証明

（１）符号付き文字列の始代数による整理

　符号付き文字列は、文字集合が与えられたとき、符号付き文字（正の文字と負の文字）の有限列からなる集合です。また、列を構成している2つの隣接する符号付き文字が、符号が異なり値が等しいときは打ち消し合います。

　たとえば、"+a-b+c"は符号付き文字列です。また、"+a-b+b-c"は-bと+bが打ち消し合うための条件を満たすので、"+a-c"へ約分（reduction）されます。

　文字の集合をΣとして、符号付き文字列の集合をΣ^±1とします。この記法は一般的ではないので注意してください。Σ^±1は次のように再帰的に定義されます。
・空列εはΣ^±1上の符号付き文字列である。
・aがΣ上の文字、xがΣ^±1上の符号付き文字列のとき、x:+aとx:-aはΣ^±1上の符号付き文字列である。
・Σ^±1上の符号付き文字列は、以上の操作のみによって構成される。

　以上の3つの条件では、打ち消し合う性質が与えられていません。そのため、consに逆演算の性質を与えます。2番目の条件で文字を符号付き文字列に追加する操作として、(:+)と(:-)が現れました。これらは、次のような関数の定義を与えます。
\[(:+) : Σ^{±1}×Σ → Σ^{±1} \\ (:-) : Σ^{±1}×Σ → Σ^{±1}\]
　この2つが逆演算であるという条件を最後に加えることで、打ち消し合う条件が与えられます。つまり、任意の文字aと符号付き文字列xについて、次が成り立つということです。
\[ x:+a:-a = x = x:-a:+a\]
　(:+)と(:-)をそれぞれ、正のconsと負のconsと呼びましょう。

　以上の再帰的定義から次の始代数性が与えられます。
　任意の集合Xとその定数c、可逆な演算h : X × Σ → X が与えられたとき、次の漸化式を満たす関数f : Σ^±1 → X がただ一つ存在する。
\[\begin{eqnarray*}
f(ε) &=& c \\
f(x:+a) &=& h(f(x), a)\\
f(x:-a) &=& h^{-1}(f(x), a)
\end{eqnarray*}\]

　hは可逆であるという条件がありました。次のようなh^-1が存在するということです。

\[ h(h^{-1}(x, a), a) = x = h^{-1}(h(x,a),a)\]

　この性質は別の「逆演算について」の記事で整理されているので、詳しくはそちらを参照してください。

（２）指数関数、連接、挿入関数の定義

　（１）で与えられた始代数性から、いくつか関数を与えることができます。まずは、指数関数を与えます。

　ここで、f を Σから 任意の群Gへの関数 f : Σ → G とします。群Gでは、単位元はe、乗法は・、xの逆元はx^-1で表されるとします。このとき、次の条件を満たすような、fを底とする指数関数Σ^±1 → Gを２つ（右指数関数f^と左指数関数^f）を定義できます。

右指数関数

\[\begin{eqnarray*}f^ε &=& e \\f^{x:+a} &=& f^x \cdot f(a) \\f^{x:-a} &=& f^x \cdot (f(a))^{-1} \\\end{eqnarray*}\]

左指数関数

\[\begin{eqnarray*}^ε f&=& e \\ ^{x:+a}f &=& f(a) \cdot \ ^af\\ ^{x:-a}f &=& (f(a))^{-1} \cdot \ ^af\\\end{eqnarray*}\]

　3つ目の条件ではf(a)の逆元を掛けています。

連接・逆連接

　ここでは、consを底とする指数関数を考えることで、2つの二項演算（連接と逆連接）を導入します。連接は通常の文字列の足し算のようなものですが、逆連接はいわば引き算のようなものです。次で証明するように、これらは群における乗法と除法に対応します。

　連接・逆連接は、それぞれ次のように定義される「正のconsを底とする左指数関数」と「負のconsを底とする右指数関数」を使います。

正のconsを底とする左指数関数

\[\begin{eqnarray*}^ε (:+)&=& e \\ ^{x:+a}(:+) &=& (:+a) \cdot \ ^a(:+)\\ ^{x:-a}(:+) &=& (:-a) \cdot \ ^a(:+)\\\end{eqnarray*}\]

負のconsを底とする右指数関数

\[\begin{eqnarray*}(:-)^ε &=& e \\(:-)^{x:+a} &=& (:-)^x \cdot (:-a) \\(:-)^{x:-a} &=& (:-)^x \cdot (:+a) \\\end{eqnarray*}\]

　ここで登場している(:+a)と(:-a)はconsが与えた、負または正の文字aを追加する単項演算子です。これらは合成すると恒等関数になることから、群上の逆元の関係にあります。そのため、それぞれの定義は以上のようになります。

　xを任意の符号付き文字列として、単項演算^x(:+)と(:-)^xについて少し説明しましょう。^x(:+)は各符号付き文字列の後ろ（右）に、xをそのまま追加する演算です。(:-)^xは各符号付き文字列の後ろにに、xの逆の順序と逆の符号で追加する演算です。

　これらを使って、符号付き文字列上の二項演算子である連接・と逆連接／を次のように定義します。

\[\begin{eqnarray*}x\cdot y &=& \ ^y(:+)\ x \\x / y &=& (:-)^y \ x \\\end{eqnarray*}\]

　これらの漸化式を定義から確かめましょう。次のようになります。

・連接・

\[\begin{eqnarray*}x\cdot ε &=& x \\x\cdot (y:+a) &=& (x \cdot y):+a \\x\cdot (y:-a) &=& (x \cdot y):-a \end{eqnarray*}\]

・逆連接／

\[\begin{eqnarray*}x/ ε &=& x \\x/ (y:+a) &=& (x:-a) / y \\x/ (y:-a) &=& (x:+a) / y \end{eqnarray*}\]

挿入関数η

文字の集合から符号付き文字列への挿入関数というものを定義します。これは各文字aを長さ1の符号付き文字列"+a"へ写す関数η : Σ → Σ^±1です。次のように定義されます。
\[ η(a) = ε:+a\]
　これは整数では1に対応するものです。

（３）諸性質の整理

指数法則（右指数法則と左指数法則）

・右指数法則

\[ f^{x \cdot y} = f^x \cdot f^y \\
f^{x / y} = f^x \cdot (f^y)^{-1} \]
・左指数法則
\[\ ^{x \cdot y}f = \ ^yf \cdot \ ^xf \\
\ ^{x / y}f = (^yf)^{-1} \cdot \ ^xf\]

挿入関数と指数関数の関係

\[ f^{η(a)} = f(a) \]

連接と挿入関数の関係

\[ x:+a = x \cdot η(a) \\
x:-a = x / η(a)) \]

　「挿入関数と指数関数の関係」はfの"+a"乗はf(a)になるという意味で、整数におけるxの1乗はxであるという性質に対応します。また、連接と挿入関数の関係は正の文字aを追加するという操作は"+a"を連接すること、負の文字aを追加する操作は"+a"を逆連接すること（これは"-a"を連接と等しくなる）と等しいという意味で、整数における後者関数が+1と等しいこと、前者関数が-1と等しいことと対応します。
　証明については、文字列のものとほとんど同じなのでほとんど省略しますが、一つだけ行います。

証明

\[ f^{x / y} = f^x \cdot (f^y)^{-1} \]

これをyについての性質として帰納法で示します。

・εのとき

　これは、x / ε = x と fのε乗が単位元になることから明らかです。

・(y:+a)のとき

\[\begin{eqnarray*} f^{x / (y:+a)} &=& f^{(x:-a)/y} \\&=& f^{x:-a} \cdot (f^y)^{-1}\\ &=& f^x \cdot (f(a))^{-1} \cdot (f^y)^{-1} \\&=& f^x \cdot (f^y \cdot f(a))^{-1} \\ &=& f^x \cdot (f^{y:+a})^{-1} \end{eqnarray*}\]

　1行目から2行目は、帰納法の仮定から導かれます。3行目から4行目は、逆元の積は順序を入れ替えた積の逆元であるという群の性質によって導かれます。

・(y:-a)のとき

　上とほとんど同じなので省略します。

　その他の指数法則はこれの多少形を変えたものなので、証明は難しくありません。

（４）群であることの証明

　ここでは、群の公理について通常の逆元による公理ではなく、別の記事「逆元による群と除法による群」で与えた除法についての公理を採用します。今までの定義で符号付き文字列上の逆元は導入されていませんが、除法が与えられていること、また、証明が容易であるというのが理由です。逆元は(ε/x)によって与えられます。

　符号付き文字列は群になります。乗法は連接、除法は逆連接、単位元は空列です。群であるとは、これらが次の条件を満たすということです。

・単位元

\[ x \cdot ε = x = x \cdot ε\]

・乗法の結合法則

\[(x \cdot y)\cdot z = x \cdot (y \cdot z) \]

・逆演算

\[(x \cdot y)/y = x = (x / y) \cdot y \]

・除法の結合法則

\[(x \cdot y)/z =  x \cdot (y / z) \]

　上2つの条件についての証明は、文字列のときとほとんど同じなので省略します。下2つの条件がモノイドから群へ拡張するときに加わった条件になります。これらの条件について、定義から次のように書き換えることができます。

・逆演算

\[\ ^y(:+) \circ (:-)^y = id_{Σ^{±1}} = (:-)^y \circ \ ^y(:+)\]

・除法の結合法則

\[\ ^z(:-) \circ (:+)^y = (:-)^{y/z} \]

　この書き換えの正当性は各式に符号付き文字列xを与えることで直ちに確認できます。

　逆演算についての条件は、負のconsを底とする指数関数と正のcosnを底とする指数関数が逆演算の関係にあることを示しています。（正のconsと負のconsは逆演算でしたが、指数関数は確かめていません）また、除法の結合法則は、右指数法則と負のconsが正のconsの逆演算であることから導かれます。

　それでは、負のconsを底とする指数関数と正のconsを底とする指数関数が逆演算であることを示しましょう。

証明

\[\ ^x(:+) \circ (:-)^x = id_{Σ^{±1}} = (:-)^x \circ \ ^x(:+)\]

　xについての帰納法で示します。

・εのとき

　これは自明です。

・(x:+a)のとき

　左辺

\[\begin{eqnarray*} ^{x:+a}(:+) \circ (:-)^{x:+a} &=& (:+a) \circ \ ^x(:+) \circ (:-)^x \circ (:-a) \\ &=& (:+a) \circ (:-a) \\ &=& id_{Σ^{±1}} \end{eqnarray*}\]

　1行目から２行目は帰納法の仮定から導かれます。

　右辺

\[\begin{eqnarray*} (:-)^{x:+a} \circ \ ^{x:+a}(:+) &=& (:-a) \circ (:-)^x \circ \ ^x(:+) \circ (:+a) \\ &=& (:-a) \circ (:+a) \\ &=& id_{Σ^{±1}} \end{eqnarray*}\]

・(x:-a)のとき

　上とほとんど同じなので省略します。 

以上で、群の条件を確認できました。

（５）自由であることの証明

　これは、右指数関数が、挿入関数と合成したら底になる、群の準同型になっているという2つの条件を満たすこと、そして、その条件を満たす関数はただ一つであることを示すということです。

　挿入関数と合成したら底になることは（３）の「指数関数と挿入関数の関係」ですでに示しました。群の準同型であるとは、次を満たすことです。

\[ f^ε= e \\ f^{x \cdot y} = f^x \cdot f^y \\ f^{x/y} = f^x \cdot (f^y)^{-1} \]

　以上の条件はすでに示しました。

　ただし、通常の群における準同型は逆元を逆元に写すことです。符号付き文字列xの逆元に相当するのはε/xです。3つ目の条件に当てはめれば、通常の準同型の定義を満たすことが確認できます。

　最後にそれがただ一つであることを示します。これは自由モノイドのときとほとんど同じで、始代数であることが効いてきます。

　gが挿入関数と合成したら底になる、群の準同型になっているという条件を満たすとします。つまり、次の条件をgは満たします。

\[g(η(a)) = f(a) \\ g(ε) = e \\ g(x \cdot y) = g(x) \cdot g(y) \\ g(x/y) = g(x) \cdot (g(y))^{-1}\]

　以上の性質から、gは次の性質を満たします。

\[g(ε) = e \\ g(x:+a) = g(x) \cdot f(a) \\ g(x:-a) \cdot (f(a))^{-1} \]

　この証明には、連接と挿入関数の関係と挿入関数と合成したら底になるという性質から示すことができます。

　確認したように、右指数関数が満たすので上の性質を満たします。この3つの等式は、始代数における漸化式と一致しています。そのため、これはただ一つであることが示されます。