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$は演算$+$について閉じています。

ツイート

関連

合わせて読みたい「自由群」。

http://bit.ly/freegroupw


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