符号付き文字列について

符号付き文字列について

文字列の拡張

  ある文字の集合はある操作によって文字列の集合を与えます。この文字列について代数的な視点で見れば、モノイドという代数構造を持つこと、文字とのあいだに自由という関係があることを確認しました。符号付き文字列はこれを群に拡張したものに相当するものです。

符号付き文字列の直観的な説明

  直観的な説明から与えましょう。通常の文字列は文字の有限列として捉えることができます。符号付き文字列の場合は、符号がついた文字の有限列です。ここで言われている「符号sign」とは「符号付き整数」などで使われている符号のことで、符号付きであるとは、それらに「正 positive」と「負 negative」のいずれかが付与されていることを意味します。つまり、正の文字と負の文字を考えて、それらの有限列を考えたものが符号付き文字列です。

符号付き文字列の例

  例えば"+a-b+c"や"+d-e"といったものが符号付き文字列です。各文字について符号（プラス+とマイナス-）が付与されています。
　単純に２種類の符号を与えるだけではありません。正と負には互いに打ち消し合う性質を与えます。符号付き文字列の場合は、正の文字と負の文字が隣接していて、その値（つまり、符号を無視した文字）が等しい場合は、打ち消し合います。たとえば、"+a+b-b+c"という符号付き文字列は2文字目と3文字目がそのような関係にありますので、この文字列は"+a-c"という文字列と「等しい」という定義を与えます。

符号付き文字列が群構造を持つこと

  このような性質を与えることで、符号付き文字列は群の構造を持ちます。つまり、任意の符号付き文字列について、連接したら空列になるような符号付き文字列が存在するということです。たとえば、"+a-b+c"という符号付き文字列は"-c+b-a"という符号付き文字列と連接したら、次のように空列になります。

"+a-b+c"+"-c+b-a"= "+a-b+c-c+b-a" = "+a-b+b-a" = "+a-a" = ""

符号付き文字列の定義

　文字列の場合は、空列とconsから再帰的に定義することで文字列を定義することができました。再帰的に定義したので、帰納法による証明をすることができたり、始代数性から再帰的な関数の定義を与えることができたりと、扱いやすい性質を持っていました。符号付き文字列の場合は、consを拡張することでそれが達成されます。consとは文字列に文字を追加する操作を表すものでした。符号付き文字列の場合は、追加する文字に符号が加わるので2つのconsが考えられます。これを正のconsと負のconsと呼びましょう。打ち消し合う性質を与えるためには、正のconsと負のconsが「逆演算」であるという条件を与えることで達成されます。この「逆演算」については、次の記事を参照してください。

逆演算について

符号付き文字列が群であること

　ここでは形式的な証明は行いませんが、その概要を述べておきます。文字列の場合は、consを底とする指数関数が連接になりました。同様に、正のconsを底とする指数関数を考えることができ、これが符号付き文字列上の連接になります。負のconsを底とする指数関数を考えると連接の逆演算（乗法に対しては除法に相当するもの）が現れます。文字列の連接を足し算と考えたときは、これは引き算になるでしょう。次のような計算になります。

"+a-b+c" - "+c" = "+a-b+c-c" = "+a-b"

"+a-b+c" - "-b+c" = "+a-b+c-c+b" = "+a"

　このように符号を反転・順序を反転して連接させるという演算が現れます。これにより群の構造を持っていることを示すためには、従来の群の公理（モノイド＋逆元）ではなく、別の記事で導入した群の公理（モノイド＋除法）が簡単です。逆元を作る場合には、この引き算（除法）から定義することになるので、遠回りになるからです。

逆元による群と除法による群

証明の要

　文字列の場合では、指数関数の性質が直接モノイドの条件に変化することがありました（たとえば、指数法則が結合法則へ）。そのように、除法の条件（逆演算性と結合性）は、それぞれ、正のconsと負のconsの逆演算であることと、指数法則から直接導かれます。

整数について

　整数も特殊な符号付き文字列であると考えられるので、再帰的に定義することができます。正のconsと負のconsに対応するのは、後者関数successorと前者関数predecessorです。逆演算であるというのはこの場合は逆射関係になります。また、連接に対応するのは足し算＋でその逆は引き算-になります。

　従来の代数の議論では整数を定義する場合は、自然数の組を考えて、その同値類を取るという人工的な方法を取ることが多いですが、おそらくこの方が自然であると思われます。