群とは
なにか「2項演算」ができる、空集合でない集合$G$であって、
(つまり、$g, h \in G$とすると、2項演算$g\cdot h$があり、演算結果もGの元、つまり$g\cdot h\in G$となるものであって)
次の条件を満たすもののことを群といいます。
- (単位元) 単位元と呼ばれる元$e\in G$があり、任意の元$a \in G$に対し、$e\cdot a = a \cdot e = a$が成り立つ
- (逆元) 任意の元$a\in G$に対し、ある元$b \in G$が存在し、$a\cdot b = b \cdot a = e$が成り立つ。$b$は$a$の逆元と呼ばれ、$a^{-1}$と書く
- (結合法則) 任意の元$a, b, c \in G$に対し、$(a\cdot b)\cdot c = a \cdot (b \cdot c)$が成り立つ
群の例
- 足し算ができる整数は、群です(単位元→$0$, $a$の逆元→$-a$, 結合法則→足し算は結合法則が成り立つことが知られている)
- 足し算ができる有理数も群です(同上)。また、掛け算ができる、有理数から0を除いたもの、も群です。(0も含む有理数だと、0の逆元が定義できないので群ではありません)
自由群
群の定義以外、何も制約がないのが自由群です。
ここでは、自由群の中でも2つの元から生成される$F_2$について考えます。つまり、単位元と、2つの元$a, b \in F_2$と、その逆元$a^{-1}, b^{-1}$から、好きなのを選んで演算して、を好きなだけ繰り返してできるものを考えます。
$F_2 = \{e, a, b, a^{-1}, b^{-1}, aa, ab, ab^{-1}, ba, ba^{-1}, bb, a^{-1}b, a^{-1}a^{-1}, a^{-1}b^{-1}, \dots\}$
逆元は?
$a$の逆元が$a^{-1}$なのは分かりましたが、では、$ab^{-1}aab$など、組み合わさったものの逆元はどうなるでしょう?
実はこれは、それぞれの元の逆元を取って、さらに、順番を逆転させたもの、つまりこの場合は$b^{-1}a^{-1}a^{-1}ba^{-1}$が逆元になります。
実際、これらを演算してみると
\begin{eqnarray}
ab^{-1}aab\cdot b^{-1}a^{-1}a^{-1}ba^{-1} & = & ab^{-1}aa \cdot a^{-1}a^{-1}ba^{-1}\\
& = & ab^{-1}a \cdot a^{-1}ba^{-1}\\
& = & ab^{-1} \cdot ba^{-1}\\
& = & a \cdot a^{-1}\\
&=&e\\
\\
b^{-1}a^{-1}a^{-1}ba^{-1}\cdot ab^{-1}aab & = & b^{-1}a^{-1}a^{-1}b\cdot b^{-1}aab\\
& = & b^{-1}a^{-1}a^{-1}\cdot aab\\
& = & b^{-1}a^{-1}\cdot ab\\
& = & b^{-1}\cdot b\\
& = & e
\end{eqnarray}
確かに、逆元になっていることが分かります。
Pythonでやってみよう
Pythonは演算子オーバーロードが簡単なのでやりやすいですね。
早速やってみます。
実装方針として、$a$とか$ab$とかを、文字列で持つことにします。
また、逆元は大文字のA, Bで持つことにします。
逆元計算のためには、str.swapcaseメソッドを使い、文字列をひっくり返します。
長年Pythonを使っていましたが、swapcaseを使ったのは人生で初めてです。
なんと、このメソッドは、大文字は小文字に、小文字は大文字にする、というメソッドです。
'heLLo woRLd, ゎぃゎ ヵッォ ゃ ωπ'.swapcase() # => 結果は次行
'HEllO WOrlD, ゎぃゎ ヵッォ ゃ ΩΠ'
残念ながら(?)、小さいひらがなは大きくなりませんが、ASCII文字じゃなくてもギリシャ文字は変換されるらしいです。まぁ、そんなことはどうでもいいので実装しましょう。
大事なことは大体考えたので、コードをガーッと書きましょう。
from collections import namedtuple
FreeGroupBase = namedtuple('FreeGroupBase', 's')
class FreeGroup(FreeGroupBase):
def __init__(self, s: str):
if s.lower().replace('a', '').replace('b', ''):
# a, bのみから生成されているか確認
raise ValueError('Unexpected element is contained')
# 逆元を ~a のように取ることにします
def __invert__(self) -> 'FreeGroup':
return FreeGroup(self.s.swapcase()[::-1])
# 演算を * で行うことにします
def __mul__(self, other: 'FreeGroup') -> 'FreeGroup':
return FreeGroup(self._mul_impl(self.s, other.s))
@classmethod
def _mul_impl(cls, lhs: str, rhs: str) -> str:
'演算の実装'
if not lhs: # lhsが単位元
return rhs
if not rhs: # rhsが単位元
return lhs
if lhs[-1].swapcase() == rhs[0]: # ...a * ~a... の形だと、a * ~aを打ち消せる
return cls._mul_impl(lhs[:-1], rhs[1:])
return lhs + rhs # そうでなければ、文字列を単にくっつけたもの
def __repr__(self) -> 'str':
if not self.s:
return 'e'
return ' * '.join(e if e.lower() else '~' + e.tolower() for e in self.s)
a = FreeGroup('a')
b = FreeGroup('b')
e = FreeGroup('')
g = a * b * b * a * ~b * ~b * ~a * a * b * (a * a * b)
print(g)
print(g * ~g)
print(~g * g)
うん、なんかいい感じにできてますね。