2016-05-19 問題群論文字列

文字列の連結について……

問題

\(\newcommand{\STR}[1]{\text{#1}}\)

\(\STR{A},\STR{B},\ldots,\STR{Z}\)を「文字」とし、「文字」が\(0\)個以上有限個並んだものを「文字列」とします。表記の都合上、\(0\)個の「文字」からなる「文字列」を\(\varepsilon\)と書きます。

「文字列」全体の集合を\(S\)とします。\(+\)を「文字列を連結する演算子」としたとき、集合\(S\)は演算\(+\)に関して群になりますか。

解答表示

群にはなりません。

集合\(S\)が演算\(+\)に関して群になるためには、単位元が存在し、結合法則が成り立ち、任意の元に逆元がある必要があります。

集合\(S\)は演算\(+\)に関して単位元が存在します。\(\varepsilon\)です。

結合法則も成り立ちます。任意の「文字列」\(x,y,z\)に関して、\((x + y) + z = x + (y + z)\)が成り立つからです。

しかし、\(\varepsilon\)以外の元に逆元はありません。ですから、群にはなりません。

たとえば、\(\STR{A}\)の逆元\(x\)は\(\STR{A} + x = \varepsilon\)になる必要がありますが、このような\(x\)は存在しません。結合演算子\(+\)で長さが短くなることはないからです。

ちなみに、\(S\)の要素は有限長の「文字列」ですが、\(S\)自身は無限集合です。そして、\(S\)は演算\(+\)について閉じています。