3+5=35 ?：文字列の和・結合、自由群とは何か

どうも、木村（@kimu3_slime）です。

次のツイートを見て、”\(3+5=35\)”となる世界を数学的に作れることを思い出しました。今回は、文字列の和・結合、自由モノイドとは何か、簡単に紹介します。

3＋5がどうしても35だとしか思えない人の数がどんなに多くても3＋5は本当は8だとはいえるにしても、そのことを3＋5が35だとしか思えない大多数の人々に決して説明できない(納得させることができない)場合はどうなるかという問題はやはり存在しますよ。
— 永井均 (@hitoshinagai1) June 16, 2021

文字列の和とは
形式言語、自由群
こちらもおすすめ

文字列の和とは

プログラミング言語では、数以外のデータとして、文字列（string）を扱えます。例えばJuliaなら、文字列3と文字列5を結合すると、35という文字列が得られるわけです。

こういった文字列の計算を、数学的に定式化してみましょう。数学というと数しか扱えないイメージがあるかもしれませんが、文字や記号は数学の範囲内です。

文字列とは何かというと、文字をいくつか並べたものです。そこでまず、文字の集合を指定しましょう。

今回は、\(X=\{1,2,3,4,5\}\)という文字の集合を考えます。\(1,2,3,4,5\)というのは単なる文字・記号（symbol）であり、\(a,b,c,d,e\)と書いても同じ議論です。文字列を作るための記号を、アルファベット（alphabet）と呼ぶこともあります。

\(X\)上の文字列（string）、単語（word）とは、文字を順番を考えて並べた有限列と定義します。例えば、\(A=(3,5)\)や\(B=(1,2,3,2,1)\)は文字列です。

\(n\)文字の文字列\((a_1,\dots,a_n)\)は、数学的には順序対と捉えれば良いでしょう。数列が関数であるのと同じように、文字列を有限集合から\(X\)への写像と見ても良いです。

文字列を省略した表記法として、\(35 =(3,5)\)、\(12321=(1,2,3,2,1)\)と書くことにします。より文字列に見えやすくなりました。1文字の文字列を\(3 =(3)\)と書きます。文字そのもののの記号と1文字からなる文字列は厳密に言えば別物なのですが、同じ記号を使って書いていることに注意。

文字列は有限個並んだものですから、必ずそこに文字列の長さ（length）、文字数が定まっています。それを\(|35|=2\)、\(|12321|=5\)と書くことにしましょう。

では、文字列に対して和を考えましょう。文字列の連結（string concatenation）とも呼ぶようです。ここでは和と暫定的に呼んでいますが、積と呼び、積の記号を使っても全く問題ないです。

\(3+5 =35\)となるような”和”を考えたいです。つまり、\((3)+(5) = (3,5)\)とすれば、文字列から新たに文字列が作れます。

一般に、文字列\(A=(a_1,\dots,a_n)\)、\(B=(b_1,\dots,b_m)\)に対し、その和を

\[ \begin{aligned}A+B:=(a_1,\dots,a_n,b_1,\dots,b_m)\end{aligned} \]

と定義します。文字の長さを比べると、\(|A|+|B|=|A+B|=n+m\)が成り立っていますね。

このようにすれば、\(3+5=35\)という式が正当化されました。このルールにおいては、\(5+3 =53\)で、\(3+5 \neq 5+3\)です。文字列の和では、交換法則（可換性）が成り立ちません。

後の都合のため、文字を何も使わない文字列（空文字列）を導入しましょう。\(” “\)と空白記号を使ったら見えないので、\(I\)で表すことにします。\(35 + I =35\)で、一般には\(A+I = I+A =A\)です。空文字列の長さは0 \( |I| =0\)と考えれば良いでしょう。

形式言語、自由群

\(L:=\{X 上の文字列\}\)という集合を、\(X\)上の言語（language）、形式言語（formal language）と言います。

以上で定めた演算\(+\)は、文字列\(A,B \in L\)に対し、和も新たな文字列として\(A+B \in L\)を満たしています。さらに、\(L\)に一定の規則（代数的構造）を与えていることがわかります。

結合法則：\(A,B,C \in L\)ならば、\((A+B)+C =A+(B+C)\)
単位元の存在：\(A \in L\)に対し、\(A+I =I+A =A\)

結合法則は、どちらを優先して足しても結果が同じであることからわかります。単位元は、そういうものがあるように空文字列\(I\)を定めたのでした。

以上の条件を満たしているとき、\(L\)（と演算\(+\)）をモノイド（monoid）と呼びます。

抽象代数学では、モノイドにひとつ条件

逆元の存在：\(A \in L\)に対し、\(A+B = B+A =I\)を満たす\(B\)が存在する。

を加えた群（group）をよく考えます。

参考：群論入門～回転群と巡回群を例に、群の定義・同型・位数を解説

今までのセッティングだと、\(L\)はモノイドではあっても群にはなりません。文字列の和は足し合わせであり、文字数が減ることがなく、文字列に何かを加えて空文字にはしようがないのです。

しかし、少し工夫をすると群にできることが知られています。\(X^{-1}:=\{1^{-1},2^{-1},3^{-1},4^{-1}, 5^{-1}\}\)という消す用の（形式的な）文字を用意し、\(L(X \cup X^{-1})\)を舞台にする。そして、\(322^{-1}5 \sim 35\)と、「逆」の文字が隣り合ったらキャンセルできるようにします。つまり、文字の簡約で移り合う文字列を同一視して、同値関係\(\sim\)を考えるわけです。すると、商集合\(L(X \cup X^{-1})/ \sim\)は群になると言えます。例えば、\([35]\)の逆元としては、\([5^{-1} 3^{-1}]\)が選べるわけですね。

詳しくは、例えば堀田「代数入門: 群と加群」4章を参照。

今回紹介したような、文字列からなるモノイド、群は、それぞれ自由モノイド（free monoid）、自由群（free group）と呼ばれるものです。

参考：自由群 – Wikipedia、Free group – Wikipedia

（例えば、1文字\(X=\{1\}\)から生成される自由群は、整数\(\mathbb{Z}\)と考えることができます。どんな整数も、\(1,-1\)を足してできた文字列として捉えられますね。）

以上、\(3+5=35\)となる世界として、文字列の和・結合とは何か、それが自由モノイド・自由群と呼ばれる枠組みを生み出すことを紹介してきました。

\(3+5\)という表現があったから、多くの場合は数の足し算であると解釈して\(8\)と考えるでしょう。ただ、文字列との和として解釈すれば、\(35\)とも言えるわけですね。表現は、解釈が決まらなければ定まった意味を持ちません。

文字列の和や形式言語の考え方は、計算機科学（コンピュータサイエンス）や数理論理学でも用いられるものです。もし興味を持ったら、少し勉強してみてはいかがでしょうか。

木村すらいむ（@kimu3_slime）でした。ではでは。